基于免疫算法的个性化推荐系统

王玉林 王永鉴 柴争义

（天津工业大学计算机科学与软件学院，天津 300387）

基于免疫算法的个性化推荐系统

王玉林 王永鉴 柴争义

（天津工业大学计算机科学与软件学院，天津 300387）

针对个性化推荐系统中用户的多个不同需求，提出一种基于免疫算法的求解方法。该算法将要求解的个性化推荐列表建模成一个最大化推荐准确性和多样性的多目标优化问题，采用基于用户的协同过滤技术对用户进行分类，设计了适合推荐问题求解的抗体编码方式、克隆、变异算子。仿真实验结果表明，所提算法能够有效求得个性化推荐的最佳解，达到可以同时为多个用户提供多个不同推荐的需求。

免疫算法；多目标优化；个性化推荐；协同过滤

1 引言

随着信息技术的迅猛发展，人类已经进入一个数据爆炸的时代，生活工作中无处不在的是令人困扰的无效信息[1]。于是，如何快速高效地找出对我们有用的信息已经成为一个迫在眉睫的问题。推荐系统，使用自动统计和数据挖掘技术，能够很好地为用户提供若干有用的推荐，被认为是缓解信息过载最有前程和潜力的工具[2]。它涉及的领域较为广泛，包括电影，书籍，歌曲，笑话，旅游等等。此外，随着生活中电子商务在不断推进，推荐系统也正越来越多地参与其中，比如著名的电子商务公司亚马逊[3]。

通常，传统的推荐系统的目的是使向某类用户所推荐的项目精确度最大化[4]。然而，最近研究发现，只考虑推荐的准确性已经完成不能满足用户的需求；必须得针对性地为每个用户“量身定做”项目，并考虑用户多种的需求，最终才能提供满意的结果，这正是个性化推荐系统所具备的能力。然而，提高准确度无疑会使多样性降低；同样，种类越多也会使准确性降低。准确性和多样性已成为相互制约的要素。于是，如何设计出准确度高、多样性强的个性化推荐技术具有重要的意义。

目前，国内外的一些推荐技术已经设计出来。例如用数学方法把准确度和多样性建模成二次性方程数学问题求解。但存在着数学约束条件过高以及参数难以自动调节的弊端。个性化的推荐问题已被证明是NP问题，更适合智能化方法。免疫算法作为一种高效的智能算法，在许多应用领域都有卓越的表现。基于此，本文采用免疫算法对个性化推荐问题进行求解，向用户提供一组既准确又丰富的、令人满意的推荐项目[5]。

2 个性化推荐系统

个性化推荐系统是通过采集记录并了解掌握用户的兴趣偏好，最终向用户提供一些可能会感兴趣的推荐项目。推荐问题可用形式化加以阐明。C表示用户集合，S表示项目集合[6]。函数u作为一个评价函数，它是用来表示用户对项目感兴趣程度。

R是所有用户对项目的评价集合，rij表示用户i对项目j的评价值。因此，就可以形成用户—项目矩阵如表1所示：

表1 用户—项目矩阵

对于用户空间中的每一个用户，推荐所要达到的目的就是从项目空间中寻找能够使用户的满意度和多样性最大化的商品项目[7]。

多目标优化问题是对多个目标函数进行同时优化求得最佳解。它是一个比较复杂的问题，它的约束要求是彼此各自独立的，无法直接比较任意两个解的优劣，所以只能从解集中找到最为接近最好的折中解，即最佳解[8-9]。

3 算法实现

3.1 免疫算法

免疫算法是一种经典的智能优化算法，它是受高级生物的免疫系统具有自发、高效、特异性清除异己的原理启发而产生的。它把要解决的问题看作免疫系统的抗原，把要得到的解看作免疫系统的抗体。通过免疫反应，解决所要处理的问题。在资源分配、地址寻址、安全监测等领域中有优良的表现，得到了广泛应用[10-11]。

3.2 用户聚类

为了降低计算的复杂度，用聚类技术将用户拆分成几个集群。过程采用基于用户协同过滤技术，通过度量用户i和用户j之间相似性产生用户分类。首先得到用户和用户评分过的所有项目，然后通过余弦相似性函数计算出用户之间的相似性。其公式为：

分母是两个用户向量模的乘积，分子是两个用户向量的内积。Ui，Uj分别表示的用户i，j对项目评分集，ru,i，ru,j分别表示的是用户对项目的评分，Uij表示的是用户i，j均评价的项目集。

3.3 抗体编码

免疫算法中，抗体对应要求解问题的解，抗体编码是免疫问题求解的关键技术。本文考虑到用户与项目之间的关系，采用实数编码方式，即推荐列表中的每一个数字代表相应的项目编号。例如某个抗体的编码表示为，其中a表示的是某个用户，ai表示的就是此用户推荐列表中的项目编号。

3.4 两个目标函数

第一个目标函数是准确性。准确性在很大程度上能够反映出用户对项目的喜爱程度，也说明推荐系统的质量好坏，准确性越好说明推荐的能力越优秀。用预测评级机制来表示准确度的测量标准。对于一个用户i以及一个项目j来说，用户i对项目j的预测评级用pij来表示，则在一个用户聚类U中，预测评级的定义是：

第二个目标函数是多样性。多样性能够反映推荐列表的丰富程度，多样性越高表示推荐的种类越全面越丰富。给出具体的定义如下：

其中dif表示的是在同一个聚类U中所推荐的不同项目数，Total表示的是所有项目的总数。很明显，准确性不变时，覆盖率的值越大表明一个更好的推荐。

3.5 免疫算子

免疫算子包括交叉和变异。操作中相同项目不允许两次出现在推荐给一个用户的列表中[12]。交叉的过程可以描述如下：首先从两个父代个体中确定彼此相同的项目并直接传给子代。不同的项目执行交叉操作，随机数[0，1]决定产生位置。如果随机数大于0.5，第一个不同项目交叉；否则不动。以此类推完成所有操作。个体交叉过程如图1所示。

图1 个体交叉的过程

变异则是应用于单个个体。如果一个等位基因在父代中发生了突变，则随机从项目集中选取一个可用的项目代替原先的位置，并且所选取的这个项目在父代中不存在。通过这种方式，变异算子可以生成可行的解决方案。

3.6 算法描述

多目标优化问题因为有多个目标，所以通过优化得到的解不是唯一的，它需要种群多次迭代后产生得到折中最优解。本文算法基本流程如图2所示，具体步骤如下：

步骤1初始抗体种群由随机方式产生。给定抗体种群大小N、最大迭代次数gmax。

步骤2对候选抗体种群A(i)进行克隆操作，得到种群B(i)。

步骤3对抗体种群B(i)进行变异操作，得到种群C(i)。

步骤4对种群进行克隆选择：选择n个亲和度高的抗体组成下一代种群A’(i)。

步骤5判断终止条件。当满足终止条件时，输出亲和力最高个体；否则进入步骤2。

图2 算法流程图

4 实验结果分析

本文使用一个经典基准数据集Movielens来评估算法的性能。这个电影类的数据集包含了943个用户和1682部电影。随机选择80%的数据作为实验训练集，20%作为实验探针集。训练集的目的是用来生成推荐；而探针集则是用来评估推荐系统的性能。在实验中设置推荐列表长度L为10，种群大小N为100，交叉概率为0.8，变异概率为0.1，最大迭代数gmax为500。

在实验结果的性能指标中，精确度是被用来作为衡量准确性的指标，它是指推荐列表中用户感兴趣的项目所占的比例大小，即推荐项目既在推荐列表中又在探针集中的项目数与推荐列表项目数的比值。覆盖率是被用来衡量多样性的指标，它是指推荐列表中不同的项目占所有项目的比例大小，即推荐列表中不同种类的项目数与所有项目数的比值。通过运行实验，推荐算法的性能精确度与多样性如图3所示。

图3 推荐算法的精确度与多样性

从图3中可以清晰看出，免疫算法可以有效求得不同的解，即不同的推荐项目。随着推荐项目精确度的不断提高，代表多样性的覆盖率的值不断下降，也就说明了准确性和多样性是存在一定的冲突，符合个性化推荐的规律。同时也可以看出，在图中数据的中间部分，可以获取得到一些准确性比较高和多样性也比较高的值，即满足准确性和多样性的推荐项目。

5 结论

本文提出了一种同时优化准确性和多样性的个性化推荐模型，并使用免疫算法进行了交叉和变异算子的设计。为了降低计算复杂度，使用协同过滤技术对用户进行了分类。实验结果显示了算法的有效性。随着用户和项目数量的增加，推荐系统的准确性和多样性仍然可以进一步提升，这也是我们下一步继续深入研究的内容。

[1]MF Alhamid，M Rawashdeh，H Dong，MA Hossain．Exploring Latent Preferences for Context-Aware Personalized Recommendation Systems[J]．IEEE Transactions on Human-Machine Systems，2016，46(4)：1-9．

[2]M Gao，B Ling，Q Yuan，Q Xiong，L Yang．A Robust collaborative filtering approach based on user relationships for recommendation systems [J]．Mathematical Problems in Engineering，2014，2014(2)：1-8．

[3]Y Sun，WK Chong，YS Han，S Rho，KL Man．Key factors affecting user experience of mobile recommendation systems[J]．Lecture Notes in Engineering&Computer Science，2015，2 2 16(1)．

[4]J．Bobadilla，F．Ortega，A．Hernando，A．Gutierrez．Recommend system survey[J]．Knowledge-based system．2013，46：10 9-13 2．

[5]项亮．推荐系统实践[M]．北京．人民邮电出版社，2012．

[6]Y．Guan，D．Zhao，A．Zeng，M．-S．Shang．Preference of online users and personalized recommendations[J]．Physica A．2013，392 (16)：3417-3423．

[7]王国霞，刘贺平．个性化推荐系统综述[J]．计算机工程与应用，2012，48(7)：66-76．

[8]X．Ren，L．Lu，R．Liu，J．Zhang．Avoiding congestion in recommender systems[J]．New J．Phys．2014，16(6)．

[9]孟祥武，胡勋，王立才，等．移动推荐系统及其应用[J]．软件学报，2013，2 4(1)：9 1-108．

[10]孟祥武，刘树林，张玉洁，等．社会化推荐系统研究[J]．软件学报，2015，2 6(6)：13 56-13 72．

[11]许海玲，吴潇，李晓东，等．互联网推荐系统比较研究[J]．软件学报，200 9，2 0(2)：3 50-3 6 2．

[12]F Ricci，L Rokach，B Shapira，PB Kantor．Recommender systems handbook[M]．Springer，2011．

Personalized Recommendation System Based on Immune Algorithm

Wang Yulin Wang Yongjian Chai Zhengyi
（Tianjin Polytechnic University，Tianjin 300387）

To meet different needs of users in the recommendation system,an immune clone algorithm is proposed.The problem is modeled as a multi-objective optimization problem to maximize the accuracy and diversity in the recommendation lists.It uses collaborative filtering technology to finish the user classification.Antibody coding and the immune operator that suitable for solving the problem are designed in the algorithm.The results show that the proposed algorithm can effectively obtain the optimal solutions of personalized recommendation,which satisfies with different needs of multiple users at the same time.

immune algorithm;multi-objective optimization;personalized recommendation;collaborative filtering

TP18

符：A

1008-6609(2016)10-0001-03

王玉林（19 9 1-），男，山西大同人，硕士研究生，研究方向为智能优化算法。

国家自然科学基金项目，项目编号U 150 46 13；中国博士后科学基金，项目编号2015M 58 6 2 2。