基于用户行为模型和蚁群聚类的协同过滤推荐算法

任 帅，王浙明，王明敏

基于用户行为模型和蚁群聚类的协同过滤推荐算法

任 帅，王浙明，王明敏

协同过滤技术是推荐系统中应用最为广泛的技术之一，用户的相似性度量是整个算法的核心要素，会对推荐算法准确率产生很大的影响。传统的协同过滤算法过度依赖用户评分机制，影片自身的标签信息没有被考虑为一个影响因素，在用户聚类时采用 K近邻算法，会由于评分矩阵过于稀疏而难以收敛。同时，传统推荐技术仅基于用户历史行为进行推荐，无法为新用户提供合理的推荐。针对以上问题，提出了一种基于用户行为建模的蚁群聚类和协同过滤算法相结合的影片推荐技术。

推荐；用户行为；协同过滤；蚁群聚类

0 引言

推荐技术在整个互联网领域的重要性日益凸显，并越来越受到研究者的重视。在信息爆炸的时代，如何从海量数据中帮用户快速定位到喜欢的内容，是一个有挑战性的难题。目前，几乎所有的大型电商网站、视频网站以及内容提供网站，都已经不同程度的实现了推荐系统。为保证推荐系统在满足实时性要求的前提下能够产生相对较为精确的推荐内容，研究人员提出了许多不同类型的推荐算法，如协同过滤推荐技术、关联规则算法、Horting 图算法等不同算法。Typestry[1]是最早被提出的基于协同过滤算法的内容推荐系统[2]， 但其不足是需要用户自己手动设置与自己兴趣类似的其他用户，其核心思想比较类似 SNS 系统[3]的 Follow 概念。

推荐技术最大的难点在于，随着用户数以及项目（如商品、影视、新闻等）数的增长，用户评分矩阵规模呈指数速度上升，并且矩阵变得十分稀疏，如何找到目标用户喜欢的项目集合，是解决问题的关键。协同过滤算法作为当前应用最为广泛的算法之一，可以给出较好的推荐结果，但是存在一定的缺陷：(1)过度依赖用户评分机制，当用户评分标准不一时，结果差异很大。(2)用户聚类时采用 K 近邻算法[4]，会由于用户评分矩阵过于稀疏[5]而难以收敛。(3)冷启动问题[6]。针对以上问题，本文提出了基于用户行为模型和蚁群聚类的协同过滤推荐算法，将在第二章详细介绍。算法充分结合了内容单元自身信息，通过启发式蚁群聚类对用户进行分类，并结合用户在不同影片之间浏览跳转的行为模型，改善了以上问题现状。

1 传统协同过滤技术

协同过滤推荐技术基于这样一个假设: 如果用户对一些项目的评分比较相似， 则他们对其他项目的评分也会较为接近。 通过与目标用户相似的邻居用户群的评分预测推荐结果，从而达到推荐给目标用户喜欢的项目的目的，蕴含了“目标用户会对其相似用户喜欢的项目也感兴趣”的思想。算法有两个步骤：

1） 通过用户评分矩阵计算用户相似度。常用的计算方法有余弦相似性和关联相似性两种计算方法。具体的如公式（1）和公式（2）所示：

2） 使用 K 近邻算法进行用户聚类，在网站的整个用户空间上寻找最近邻居用户，并使用同类用户的评分来预测目标用户的推荐结果。常用的预测方法有均值法、相似度加权法和归一法。其中相似度加权法是应用最广泛的一种，如公式（3）：

将预测得分最高的一个或多个结果推荐给目标用户，从而完成了推荐的过程。然而随着评分矩阵规模和稀疏度的增加，K近邻的聚类算法在这种情况下往往不能收敛或者运算效率很低，达不到实时性，因此推荐的结果准确性大大降低。

2 基于用户行为建模的蚁群协同过滤技术

2.1 基于蚁群聚类的协同过滤

蚁群聚类[9]算法的灵感来源于自然界中蚂蚁寻找食物的过程。蚂蚁之间通过一种叫做信息素（pheromone）的物质进行互相通信，协作完成共同的目标；蚂蚁会在走过的路径上留下信息素，走过的蚂蚁越多，路径上的信息素积累的量就越大，信息素会随时间消失，但也会对其他蚂蚁产生吸引的作用；通过信息素交流的蚂蚁群体便产生一种正反馈的现象：某一条路径上走过的蚂蚁越来越多，留下的信息素量越来越大，会吸引更多的蚂蚁选择这条路径，蚂蚁个体之间就是通过这种方式找到距离食物最短的路径。

聚类问题的蚁群算法基本思路如下：在每个模式样本处分别放置1个蚂蚁，蚂蚁倾向于选择信息素最多的一条路径移动，也就是距离最近的一个模式样本。将第i模式样本分配给第 j个聚类中心蚂蚁在模式样本i到聚类中心的路径上留下信息素那么第 i个蚂蚁选择聚类中心的概率为公式（4）：

聚类中心选择好以后，路径上信息素的更新方程为公式（5）：

蚁群聚类的算法流程如下：

（3）计算新的聚类中心，计算每个模式样本到新的聚类中心新的距离

以上步骤的伪代码如下：

For i=1 to 蚂蚁总数 do

生成蚂蚁 i;

For i=1 to 蚂蚁总数 do

初始化蚂蚁 i的参数(a,b,p,Q);

For j=1 to 分类数 do

随机选择j的初始类中心

While(it小于最大循环次数 || 类中心没有改变)

For i=1 to 蚂蚁总数 do

For j=1 to 分类数 do

For j=1 to 分类数 do

更新类中心j

For j=1 to 路径总数 do

根据公式（5）更新路径上信息素

2.2 用户行为模型

影视数据是具有很高内容相关度的数据集，用户行为模型以影视数据为例进行分析和说明。

2.2.1 影片相似度

通过计算影片的相似度可以找到与目标影片在不同维度上相似的影片集合，在用户浏览的历史行为较少的情况下，可针对用户当前正在观看的影片进行推荐。影片信息由不同的字段组成，如 name, director, cast, type，date 等，如下所示：

＜Movie＞

＜id＞35＜/id＞

＜filmName＞阿凡达 Avatar＜/filmName＞

＜filmName＞天神下凡＜/filmName＞

＜director＞詹姆斯·卡梅隆＜/director＞

＜scriptwriter＞詹姆斯·卡梅隆＜/scriptwriter＞

＜cast＞萨姆·沃辛顿＜/cast＞

＜cast＞佐伊·索尔达娜＜/cast＞

＜type＞动作＜/type＞

＜type＞冒险＜/type＞

＜location＞美国＜/location＞

＜release＞2009-12-16＜/release＞

＜rating＞8.9＜/rating＞

＜vote＞215991＜/vote＞

＜/Movie＞

根据影片词条维度和时间维度的信息，可以分别按照公式（6）和（7）计算相似度。

通过相似度的计算，可以对影片各个维度进行相似度的排名，根据排名得到初步的预选集。

2.2.2 用户行为权重

用户行为权重是基于影片相似度的一种度量用户跳转行为的模型。用户在浏览当前影片时，由于兴趣的转变而浏览下一部影片，完成一次跳转行为。对于一个特定用户，使用一个权重向量描述他的跳转行为，它表示用户在浏览影片不同维度信息时会发生跳转的概率，即用户习惯的搜索与拓展方式。当某一维度权重较高时，该用户更倾向于选择该维度上相似的影片观看。是一个用户行为模型的反馈向量，随着用户浏览影片时的跳转行为而不断被反馈和更新：

通过加权平均的方法，可以在根据影片相似度计算得到的初步预选集上面进一步缩小用户可能喜欢的预测范围，并且得到的集合更加适合用户的浏览习惯，提高了推荐的命中率，从而将这个集合的影片推荐给目标用户。

2.3 线性回归模型组合

通过基于蚁群的协同过滤推荐算法以及基于用户行为的推荐算法，得到两个预测的集合，采用线性回归的方法可以将两个模型自适应地组合在一起，并根据推荐命中率反馈线性方程的系数，达到自适应调节组合结果的目的。因此算法表现为在用户的浏览历史行为数据丰富时，会根据协同过滤的推荐算法给出预测结果，而当用户数据较少时，协同过滤不能有效的进行预测，算法就会倾向通过影片相似度以及用户行为权重计算得到的预测集合。线性回归模型组合方程如公式（10）：

3 实验及结果

3.1 数据集

Netflix Prize 竞赛由在线 DVD 租赁公司 Netflix 创建，旨在推进学术界和工业界对协同过滤算法的研究。它所发布的数据集为目前最大的免费公开的协同数据集。数据集的结构以及规模如表1所示：

表1 Netflix 数据集

取 Probe Set的 80%作为实验数据，剩下的 20%作为实验对比数据。为了测试用户行为模型的准确性，以及与协同过滤算法进行对比，从豆瓣网上抓取 1085 部电影数据，包含 47000 多条词条信息以及 712 个用户的近 10 万个评分以及浏览跳转信息作为用户行为建模的数据集。用户评分数据集的稀疏等级为 1-100000/(712 × 1085)= 0.8706。同样按照80%与 20%的比例划分集合得到实验测试集及对照集。

3.2 评价标准

推荐质量的评价标准通常采用统计精度度量方法中的平均绝对偏差 MAE (mean absolute error)进行计算。平均绝对偏差（MAE）通过计算预测用户的评分与用户实际评分之间的偏差来度量预测的准确性。MAE越小，推荐质量越高。假设预测的用户评分集合为用户的实际评分集合为则 MAE 的计算式表示为公式（11）：

3.3 结果分析

采用K近邻聚类与蚁群聚类的协同过滤算法按照K取从 5 到 100 之间 5 的倍数进行 200 组试验，选取其中具有代表性的6组数据进行分析，实验参数与结果如表2所示：

表2 采用 K 近邻聚类与蚁群聚类的协同过滤算法实验参数与结果

KNN ACO KNN ACO KNN ACO 1 0.952 0.992 0.952 0.962 0.933 0.937 2 0.972 0.949 0.972 0.959 0.945 0.940 3 0.966 0.988 0.966 0.948 0.953 0.929 4 0.985 0.973 0.985 0.963 0.949 0.941 5 0.967 0.963 0.967 0.942 0.941 0.939

结果对比如图1和图2所示：

图1 K=50, it=100 时，两种聚类算法的推荐质量

图2 K=100, it=100 时，两种聚类算法的推荐质量

分别是两种聚类算法在聚类中心个数为 50 和 100，迭代次数为 50 和 100 的参数组合下的推荐质量。

信息素衰减速率参数1/λ在 0.8 左右效果最好。衰减过快会导致蚁群算法过早收敛于局部最优解，而衰减过慢将造成多条路径信息素饱和。信息素初始值Q 为 100。蚁群聚类算法在迭代次数较低时性能并不稳定，但随着迭代次数的增加，基于蚁群的协同过滤算法有很明显的优势。K近邻算法在用户聚类变多的情况下，存在很大不确定性，从算法本质上来分析，当分类集合比较小且类中心相对靠近时，K近邻很难得到理想的结果。

采用两种聚类方法的协同过滤与结合用户行为模型的蚁群协同过滤推荐质量对比数据如表3所示：

表3 K=30, it=100 时，三种算法的推荐质量对比

由于从网站抓取的数据集比 Netfilx 数据集规模小，因此聚类个数参数设为 30，迭代次数设为 100，共进行 30 组实验，推荐质量的效果对比如图3所示：

图3 协同过滤与结合用户行为的蚁群协同过滤推荐质量对比

1085 部影片通过 7 个维度的影片相似度选择出 100 部影片大小的预选集，在初始权重取取 0.78 的情况下结果如图3所示，可以发现结合用户行为之后的蚁群协同过滤算法在大多数情况下具有更小的 MAE，在K近邻和蚁群聚类都难以取得较好效果的情况下，用户行为算法能快速适应数据集，因为结合了影片本身的信息，在用户浏览历史信息较少的情况下也能给出有效推荐。但从稳定性角度来看，用户行为算法略低于传统的协同过滤算法，基于线性回归的协同过滤组合模型虽然在学习初期参数并不平衡时，会表现出不稳定的性能，但经过训练参数趋于稳定之后，结合用户行为的蚁群协同过滤能产生很好的推荐质量。

4 总结

在传统协同过滤推荐技术基础上，本文采用蚁群聚类算法对用户进行分类，在整个用户空间高效的查找邻居用户群，以及结合用户行为模型和基于项目内容的推荐，使前面提到的问题现状得到很大改善。(1)引入基于项目多维度数据的用户权重模型，凸显了用户自身浏览习惯在推荐过程中起到的作用，使推荐系统对于其他用户的评分依赖度降低。(2)采用蚁群聚类启发式搜索算法，提高了聚类效果的准确性、可扩展性及对不规则数据的适应能力。(3)在系统应用初期，用户历史行为较少时，基于内容的推荐算法可以给出有效推荐，结合用户行为的推荐技术能够弥补传统协同过滤中的冷启动问题。

本文经过多重模型组合，得到较传统协同过滤推荐技术的算法更为灵活的推荐技术，可以适应多种场景并提高了推荐质量。如何更好模拟蚁群聚类，选择用户行为模型的更新方程，降低预处理复杂度及进一步挖掘用户行为模型都是非常有意义的研究方向。

[1]W. Pan, E. W. Xiang, N. N. Liu and Q. Yang. Transfer learning in collaborative filtering for sparsity reduction. [G]Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), 2010.

[2]Zhang S. Location based recommendation method for mobile station content: U.S. Patent 8,428,622[P]. 2013-4-23.

[3]Wang LC, Meng XW, Zhang YJ. A cognitive psychology-based approach to user preferences elicitation for mobile network services. [C]Acta Electronica Sinica, 2011,39(11):2547-2553.

[4]Jiang L L, Cao Y X, Yin H K, et al. An Improved Kernel K-Mean Cluster Method and Its Application in Fault Diagnosis of Roller Bearing[J]. 2013.

[5]Khan S, Johnson D. All-electron KKR Calculations for Metallic Systems with Thousands of Atoms Per Cell via Sparse Matrix Iterative Solvers[J]. Bulletin of the American Physical Society, 2010, 55.

[6]Park S T, Chu W. Pairwise preference regression for cold-start recommendation[C]//Proceedings of the third ACM conference on Recommender systems. ACM, 2009: 21-28.

Collaborative Filtering Recommendation Based on Ant Colony Clustering and User Behavior

Ren Shuai1, Wang Zheming1, Wang Mingmin2
(1. Department of Computer Science and Technology, Fudan University, Shanghai201203, China; 2. Shanghai Science Technology Network Co. Ltd., Shanghai200233, China)

Collaborative Filtering Recommendation (CFR)is one of the most widely used technologies in recommendation systems, in which the measurement of user similarity is the core element and can affect the accuracy of results a lot. Traditional CFR only depends on the movie ratings of users. As a result, it generates very different results when different individuals rate movies according to their personal standards. The performance of K-means clustering method is hard to converge when the matrix of user ratings is very sparse. As the traditional CFR only depends on the rating history of users, when a new user registers in the system, traditional CFR can hardly give desirable results. It cannot recommend movies to users according to the movie which the target user is watching or just watched, either. To solve the above problems, a kind of algorithm is proposed based on Ant Colony Clustering and user behavior to combine with traditional CFR algorithm.

Recommendation; User Behavior; Collaborative Filtering Recommendation; Ant Colony Clustering

TP311

A

1007-757X(2014)03-0005-04

2014.02.27)

上海市科委科研计划项目 12dz1500203 和上海市科委科研计划项目 12511504902 资助。

任 帅(1989-)男，复旦大学，硕士研究生，研究方向：人机交互，多媒体信息分析与处理，上海，201203；王浙明(1990-)男，复旦大学，硕士研究生，研究方向：人机交互，多媒体信息分析与处理，上海，201203；王明敏(1973-)女，上海，东方有线网络有限公司，工程博士研究生，研究方向：多媒体信息分析与处理，上海，201203