基于进化计算理论的推荐系统算法设计

樊鸿

摘要：该文在分析推荐系统和进化计算理论的基础上，提出一种多目标优化思路，给出一种基于进化多目标优化的推荐系统算法。该算法同时考虑推荐的精确度和推荐的新颖度，既要保证精确率又要尽可能地推荐新的物品给用户，算法力求在两者之间得到一种平衡。该文给出算法的设计思想和算法流程，并对算法进行了模拟数据的测试。

关键词：推荐系统；进化优化

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）10-2342-05

Abstract： Based on the theoretical analysis and recommendation system evolution， this paper has proposed a multi-objective optimization idea and an evolutionary multi-objective optimization based recommendation algorithm is proposed. This algorithm simultaneously considers the recommendation precision and novelty， it not only preserves precision but also recommend new items to user， it makes effort to obtain the tradeoff between these two objectives. This paper presents the design of algorithms and algorithmic thinking processes， and tests the algorithm with simulation data.

Key words： recommendation systems； evolutionary optimization

推荐系统是大数据处理和社会计算的一种重要技术和手段，在信息高速发展和个性化的需求之下，推荐系统地位日趋显赫。经过多年的发展，业界已涌现多种推荐算法，还有更加新颖的推荐算法被不断提出，而推荐算法效率优劣与否直接关系到推荐系统的性能及应用，从目前的参考文献分析中可以得出，这些算法没有考虑将推荐过程建模成数学优化问题，更没有考虑用优化算法去解决这种问题。该文试图从进化多目标优化的角度出发，将多目标优化融入到推荐过程中，提出了一种进化多目标优化的推荐算法。

1 设计背景

1）推荐系统定义及分类

推荐系统是在信息革命的背景下应运而生的，推荐系统可以理解为自动联系用户和物品的一种工具，是一种缓解信息过载问题的技术或者平台。目前，业界对推荐系统的定义很多，但是在1997年由Resnick和Varian归纳总结得出：“推荐系统是利用电子商务网站向客户提供商品信息和购买方面的建议，辅助用户决策购买合适的产品，充当模拟销售人员的身份帮助客户完成购买过程”被广泛认可和接受。

按照推荐系统采集的用户的行为数据的类型，一般按以下五类划分推荐系统：

① CBF [1]—基于内容过滤的推荐系统。

② SRS—社会推荐系统。

③ KBRS—基于知识的推荐系统

④ HRS—混合推荐系统。

⑤ CFRS[2]—基于协同过滤的推荐系统。

2）主要推荐方法对比

如表1所示。

3）推荐系统存在的问题

推荐系统主要存在冷启动和数据稀疏两方面的问题。

① 冷启动问题

在推荐系统中，冷启动问题主要分为3类[3]：用户冷启动、项目冷启动和系统冷启动。用户冷启动，即用户刚刚使用系统，自身的信息才被记录。另外一个冷启动就是项目冷启动，即某一项目第一次出现在系统中。另外系统冷启动主要解决如何在一个新开发的系统或网站上设计个性化推荐系统。

② 系统稀疏性问题

对于一个真正的推荐系统而言，推荐系统中的物品个数要远大于用户的数目，反过来，用户更不可能去购买所有的物品，其直接导致的后果是生成的用户与物品评分矩阵是一个超级稀疏的矩阵，因此会导致在计算用户与用户之间的相似度时结果并不符合真实情况。

4）基于帕累托占优的进化多目标算法

Pareto最优的思想被引入到进化多目标优化中，是一种很好的求解多目标优化的思想。图1以两目标优化问题为例展示了Pareto占优的思想。图中所有的点表示Pareto最优解，所有的解组成的一个面叫做Pareto面，称PF面。图中，Pareto最优解A和B由于彼此不能判定谁比谁好，所以它们被称为Pareto最优解，A和B之间互相都不能支配谁。

2 算法设计

1）个体表示和适应度函数

表2给出了一个m个用户对n个物品的评分数据统计情况，第i行第j列的元素代表用户i对项目j的喜好情况评分。

表所示的矩阵数据是很多推荐系统算法的输入，即这些算法试图通过已经得到的评分矩阵通过某种方式或者策略估计用户对其他目前用户还没有评分或者购买或者使用的物品的评分，根据这些估计值来排序，从而按照排序结果给优化进行推荐。该文的设计思路却不一样，该文的算法试图让算法一次运行能够给出很多不同的推荐方案供决策者去自主选择。该文算法个体的编码方法如下：

表所示的个体编码采用的是二进制编码，这样做的好处就是易于理解，物品被推荐就用1表示，不推荐就用0表示，另外这样的编码方法很好解码，操作方便。对于一个进化多目标优化算法来讲，算法一次运行能够得到多个甚至很多个Pareto最优解，每个解都是一种推荐方案，决策者可以根据不同的用户的喜好来选择合适的方案来对用户进行推荐。

进化多目标优化通常要求待优化目标之间具有冲突或者部分冲突，对于推荐系统而言，目标函数的确立就更加至关重要了。目前关于用多目标求解推荐的算法基本就没有，因为推荐系统目前的评价指标比较少，而且现存的指标很难建模成一个多目标优化问题。该文算法力求寻找一种多目标解决方案。

按照推荐系统的推荐原则，该文设计的第一个目标函数就是精确度，精确度越高，推荐效果越好。该文设计了另外一个指标叫新颖度，此新颖度是针对用户的，不是针对物品而言的。因此，该文算法定义的多目标函数如下：

[maxf1=（R+L）/Lf2=（R-L）/R] （1）

上式中，R表示一个推荐物品列表，L表示目标用户喜欢的物品列表。从上式可以看出，若要f1最大化，理想情况就是推荐列表包含用户目前所有喜欢的物品，而f2最大化的理想情况是推荐列表不包含用户喜欢的物品，这一点正好符合多目标优化多目标的要求。该文算法力求寻找f1和f2之间的一组折中解。

2）遗传操作

本文算法中使用的交叉操作的步骤就是选择一个位置，然后从该位置开始到一个个体的最后一位，交换两个个体这个位置区域之间的编码内容。

本文算法中使用的变异操作的步骤就是选择一个位置，若随机数大于变异概率，则将个体该位置的编码由原始的0变为1或者由原始的1变为0，否则不做任何操作，该变异操作非常简单。

3）算法流程

本文算法提出的是一种进化多目标优化推荐系统解决方案。按照本文算法具体的操作步骤，下面给出了算法的整体流程图如图3所示。

按照图3的算法流程图，该文算法的具体操作步骤如下：

Step 1）数据读取：从文件读取用户—物品评分矩阵M，其中M是一个[n×m]的矩阵，n表示用户个数，m表示物品个数；

Step 2）初始化种群：将种群的每个个体随机初始化为二进制随机序列；

Step 3）保持非支配解：开辟一个外部种群，按照非支配关系确定非支配解，将非支配解存储在外部种群中；

Step 4）遗传操作：对当前种群进行遗传操作，即每隔两个个体，对该两个个体进行交叉操作，整个种群交叉操作完毕则对种群每个个体进行变异操作；

Step 5）适应度计算：对新产生的种群的个体计算适应度；

Step 6）更新外部种群：计算经过遗传操作之后的新种群的非支配解，并用这些非支配解更新外部种群的历史非支配解；

Step 7）终止条件：为终止条件不满足则跳至步骤4，否则输出算法得出的所有推荐方案，并且选择精确度最大的解作为最终的解。

3 实验测试

1）实验平台

1） 参数设置

种群大小popsize：100

外部种群archive：500

迭代次数loopgene：100

交叉概率pc：0.8

变异概率pm：0.2

2） 软件平台

编程工具：Matlab7.0

操作系统：Windows 7

3） 硬件平台

中央处理器：Intel（R） Core（TM） i3 CPU 3.2GHz

内存：4GB

硬盘：500G

2）实验数据

实验模拟数据是电影推荐数据。该数据是8用户观看8部电影后，给出的记录打分集合，用户及电影名称信息集如表3所示。

由于原始数据是记录的形式给出的，所以要得到矩阵数据需要对原始数据进行预处理。经过数据预处理之后得到的数据矩阵如表4所示。

3）实验结果

程序是在matlab7.0软件中实现的，最终的结果都是在matlab界面中显示的。因为程序是基于数学建模的，结果的输出区域是两个目标函数的坐标系中，该文设定的横坐标是精确度，也即目标参数f1；纵坐标是新颖度，也即是目标函数f2。输出结果是进化迭代的最后一组非支配解，也就是一系列的坐标点（f1，f2）；其数学含义是这些点互不支配，属于目标函数组的一组折中解。每个坐标点代表一种推荐方案，根据算法的设计，算法保留着这些非支配解对应的种群，种群在算法中就是一个行向量为种群大小，列向量为物品个数的矩阵。目标函数值是通过种群矩阵中的行向量与用户-物品评分列表中的行向量集合运算得到的。其中种群中行向量是一个0、1的序列，对应着用户不喜欢或喜欢该物品，所以（f1，f2）解集对应的就是针对单个用户相应的物品推荐方案，验证了本文算法一次运行得到多个推荐解的结果。

图4的PF面的结果可以看出，该文提出的算法可以得到比较理想的推荐情况，因为从进化多目标优化的角度来看，该文算法得到的PF比较光滑，而且数据之间的分布也比较均匀。

从图4可以看出，该文算法一次运行可以得到一组推荐方案，而传统方法一次运行只能得到一种推荐方案，这样就不利于决策者进行决策，而本文算法可以在保证高的正确率情况下给出多种个性化推荐方案。

4 结论

本文系统讲述了推荐系统的相关理论及知识，将推荐系统的推荐过程建模成了一个多目标优化问题，并提出了一种进化多目标求解算法。该文提出的算法一次运行就可以得到很多不同的推荐方案供决策者选择，因此本文提出的算法比传统的协同过滤推荐算法更具有意义，更适合实际应用情况。

该算法的本质是用进化多目标优化算法去优化本文建模的两个推荐系统推荐指标。虽然实验部分证明本文提出的算法是有效的，但是仍然还具有许多需要改进的地方，比如，目标函数的设计。该文设计的目标函数很简单，对于实际中的应用应该考虑一些个性化元素，将这些个性化元素融入到目标函数中，这样得到的推荐方案将会更具有个性化。另外，对于真实的推荐系统而言，由于现实中的推荐系统的数据都是很大的，而进化算法都是一类随机搜索算法，如何更好的设计算法，让算法能够处理大规模数据也是一项值得研究的内容，比如可以考虑加入局部搜索算子加速算法收敛，比如对算法进行并行化，提高算法的执行时间等。

参考文献：

[1] Koren Y， Bell R， Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer， 2009， 42（8）： 30-37.

[2] Boussa?d I， Lepagnot J， Siarry P. A survey on optimization metaheuristics[J]. Information Sciences， 2013.

[3] Chen Y. L.， Cheng L. C. A novel collaborative filtering approach for recommending ranked items[J]. Expert System with Applications， 2008， 34 （4）： 2396-2405.