第 2l 卷 第 1O 期 20 11 年 10 月 计 算 机 技 术 与 发 展 C O M P IJT E R rE C H N O L O G Y A N D D E V E L O P M E N T V oJ．2 1 N 0．1O 0 ct． 20 l 1 基 于蚁群算 法的协 同过滤推荐 系统 的研 究 吴月萍 ，王 娜 ，马 良 (1．上海第二工业大学 计算机与信息学院，上海 20 1209 ； 2．上海理工大学 管理学院，上海 200093 ) 摘 要 ：协同过滤算法是根据基本用户的观点产生对 目标用户的推荐列表 ，现模拟蚂蚁觅食的原理 ，将用户视为具有不同 属性的蚂蚁 ，聚类 中心视为蚂蚁所要寻找的“食物源”，提出基于蚁群算法实现用户聚类 ，以提高协同过滤推荐系统 的最近 邻查询速度 ，降低搜索开销，同时避免了使用 K —M eans 聚类方法受初始聚类中心和聚类个数的影响。最终实验验证蚁群 算法实现用户聚类的有效性 ，且解决了新用户得不到推荐的问题，并提高了协 同过滤推荐算法的精确度。 关键词：蚁群算法；聚类 ；协同过滤 ；推荐 ；用户 中图分类号：TP391 文献标识码：A 文章编号 ：1673-629X (2011)10-0073-1M R esea rch o f C o lla b o ra tion F ilterin g R eco m m en d a tio n S y stem B a se d o n A Ilt A lg o ri th m W U Y u e — p in g ，W A N G N a ，M A L ian g (1．School of C om puter and Inform ation，Shan ghai Second Polytechnic U ni versity , Shanghai 201209 ，C hina ； 2．C ollege of M an agem ent。U ni versity of Shan ghai for Science an d T echnology。Shan gha~200093 。China J A b stra c t：C o llab o ra tio n fil teri n g rec o m m en d a ti o n alg o ri th m is th at g en e ra te th e rec o m m e nda ti o n list acc o rd in g tO b a sic u se r view ．N ow im ita ted an t fo rag in g th eo ry 。th e u sers a re reg ard e d as d iff eren t a ttrib u te s a n ts 。c lu ste ri n g c en te r is re g ar d ed as th e “fo o d SO U l'C e ” th at th e an ts are lo ok in g for ．p ro p o se d to clu ste r u se r b ase d an t algo ri th m ，fo r im p ro v in g th e q u ery sp e~ d o f th e n eare st n eigh bo r in th e c o llabo ra- live filtering recomm enda tion system - reducing th e search spending ．and avoiding the effects of initial clustering centers and cluste rin~ n u m b e rs in th e U Se o f K - M ea n s clu ste ri n g m eth o d ．F in al ly 。th e e xp e rim en t v eri fy th at u se r clu steri n g th rou gh an t al g o ri th m is e ff ec tive 。 an d so lve th e p ro b le m o f n ew u ser n ot rec o m m en d ed ，en h an ce th e p rec isio n o f c o llabo rati o n fi lteri n g re co m m en d a ti o n al g o ri thm ． K e y w o r d s ：an t al g orith m ；clu ste ri n g ；co llab o ra ti o n fi lte ri n g ；rec o m m en da ti o n ；u se r O 引 言 在 电子 商务 推荐 系统 中，协 同过滤 推荐技 术是 应 用最成 功的个 性 化推 荐技 术之 一 ⋯ 。协 同过 滤 的基 本思想是基 于 目标用户会对有共 同爱好 的邻 居用户所 喜欢的商品产生兴趣 ，采用相似性度量算法搜索有共 同爱好 的邻 居用户 ，根据邻居用户所评价 的项 目信息 ， 向目标用户推荐项 目，然后对候选推荐项 目进行预测 评价产 生推荐结果 。随着 电子商 务规 模 的扩大 ，用 户数 目和商品数目呈指数级增长 ，传统协 同过滤技术 的性能越来越差。目前，文献[3 ～5 ]采用 K —M eans实 现用户聚类 ，以解决寻找最近邻居的开销问题 ，而一般 收稿 日期 ：20 11- 03 —2 8 ；修 回日期 ：20 11—06 — 09 基金项 目：国家 自然科学 基金 资助项 目(708710 81 ) ；上海 市重点 学 科建设资助项 目($30 504 ) 作者简介 ：吴月萍 (1979 一) ，女 ，江苏 常熟人 ，硕 士 ，工程师 ，研究 方 向 为数据挖 掘、推荐 算法 ；马 良，教 授 ，博 士 ，博 士生 导师，研究方 向 为算法设计 、系统工程 。 电子商务 系统中的项 目更新 相对缓 慢 ，且本 身 有分类 体系，所以不需要对项 目类别作出调整。但在此聚类 方法 中 ，初始 聚类 中心 和聚类 中心 间的最 小距 离等参 数对聚类效果的影响非常大，如何合理的选取这些参 数 ，仍 是一个 需要考虑 的重要 问题 。 计算机 科学家通过模仿蚂蚁行为提 出了一 系列方 法 ，且这些方 法也 已解决 了一些问题 。例 ：1991 年 D e— neubourg 等通过蚂蚁实现 聚类 和分类 用于机器人作 业调度 中 ；2002 年 Labroche 等提 出基于蚂蚁 化学识别 系统 的聚类 方法。 文中受文献[7 ]启发，采用基于蚂蚁觅食 的聚 类算法。蚂蚁的觅食是一个从搜索食物到搬运食物的 过程。每个蚂蚁在运动过程中通过感知信息素的强弱 来选择路径 ，也就是说蚂蚁倾向于信息素强度高的方 向移动 ，同时蚂蚁在其经过的路径上也释放信息素 ，这 样经过蚂蚁 越多的路径 其信 息素越 强 ，整 个蚁 群 的行 为表现出信息正反馈现象。当然也要考虑信息素 自身 · 74 · 计算机 技术 与发展 第 21 卷 会随时间的流逝 而挥发 。 借鉴基于蚁群算法所模拟的蚂蚁觅食过程 ，文中 将用户视为具有不 同属性 的蚂蚁 ，将 用户 聚类 中心视 为蚂蚁所要寻找的“食物源 ”，用 户聚类 过程就 可 以看 作是蚂蚁寻找“食物源”的过程。 1 协 同过滤算 法相 关概 念 协同过滤算法是基 于这样 的假设 ：如果 一 些用户 对某 些项 目的评分 比较 相似 ，则 他们 对其 它项 目的评 分也将会 比较相 似。协 同过滤推荐系统首先通过相似 性度量算法搜索目标用户的若干最近邻居，然后根据 相邻 用户的评价产生对 目标 用户 的推荐 列表 ，最后预 测 目标用 户对项 目的评分 ，产生推荐结果 。 1．1 数据源描述 推荐系统中的数据源 D = (U ，，，R )，其 中 U = {u ，“：，⋯ ， } 是 基 本 用 户 的集 合 ，l I= m ；，= {，。，，2，⋯ ， } 是项 目集合 ，l，I = n ； 是 m ×n 阶基 本用户对各项 目的评分矩 阵 ，其 中 的元 素 ri，∈ R 表示 用户 i对项 目 的评分。 1．2 相关相似性 度量用户 问的相似性 主要 有两 种方 法 ：余 弦相 似性和相关相似性。余弦相似性实现起来 比较简单， 也能较好地度量用户 间的相似性 ，而且计算速度 较快 。 但是在评分数据极端稀疏的情况下，通过余弦相似性 寻找的邻居不够准确；相关相似性考虑了用户的平均 评分 ，可 以较好地保证 寻找邻居 的准确 性。文献 [10 ] 分别采用余弦相似性和相关相似性进行两组实验。实 验结果显示 ，相关相 似性较余 弦 相似性 所得 的推 荐质 量更高 。因此 ，文 中采 用相 关相 似性度 量用 户 间的评 分相似性 ，也就是说这里用户 。和 b 之 间的相 似性 sim (n ，6) 是通过 Pearson 相关 系数度量 的 ，如公 式(1)。 sim R(口，b) = ∑ (R 一R。)(‰ 一Rb) ， 、 — — [— — — _二二= = — — — — — — — — — — — ／= = = 二 二 二二 二 二 二 = ：= ：= - 二 二 1 √∑ ( 一ko) √∑ ( 厂Rb) 其 中，S 表示用户 n 和 b 共 同评分 的项 目集 合 ， 和 R 分别表示用户 0 和 b 对项 目i的评分 ，R 。和R 分 别表示用户 。和用 户 b 对项 目的平均评分 。 1．3 预 测 评 分 将相似度最高 的若 干用 户作 为 目标 用户 “的邻居 集合 Ⅳ．s ，其 中 “隹N S ，且集合 Ⅳs 中的用户按照与 u 的相 似度从 高到低排 列。根据 相似 邻居 预测 用户 “ 对未评分项 目 i的评分 P 为 ： ∑ sire(u，口) ×( 一 ) P = R u + — _ — — — — _ (2 ) 『sim (／Z，n ) I 其 中， 和尺。分别表示用 户 “和用户 。对项 目的 平均评分 。 2 基于蚁群算法 的协 同过滤 推荐 系统 文中基 于蚁群 觅食原 理 ，实 现协 同过滤 算法 的用 户聚类 ，以提 高最 近邻 的查询速度 ，且解决 了使用 — M eans聚类需人 工确定 k个类及聚类 中心 的问题 ，并基 于用 户属性 获得能见度来 解决新 用户 冷启 动 问题 ，避 免新用户永 远得不 到推荐 的情况 。 2 ．1 数 据 预 处 理 数据预处理 是数 据优 化 、格 式转 化 的过 程 ，通过 此过程建立 用户模 型。文 中使用 空间向量模型表示用 户 ，能够便 于后 面的用户聚类 和相 似性计算 。预处理 过程具体包括数据 清理 、数据转 化 、归一化处理等 。 (1) 数据清理 具体来 说是 一 个数据优 化 的过程 。 删除那些不符合要求的描述信息、不必要的用户属性 以及错码、乱码等，使更加有效地获取高质量的用户分 类 。 (2 ) 数据转化是将用户的属性值用向量来表示。 用户属性信息具有一定 范围的属 性值 ，分类较稳定 ，一 般很少变化 ，容易维护 。 (3 ) 归一化处理是把属性值 限制在 需要的一定范 围内。首先归一化是 为 了后 面数 据处 理 的方 便 ，其 次 是保证程序运行时 收敛加快 。 2．2 蚁群聚类算法 蚂蚁在觅食活 动中能够在 它所经过 的路径上释放 信息素，而且能够感知信息素的存在及其强度，并以此 指导 自己的运 动方 向。借 鉴这 一原理 ，将用 户数 据视 为具有不 同属性 的蚂蚁 ，用 户聚类 中心看作 是蚂 蚁所 要寻找 的“食物源 ”，所 以用 户聚类过 程就 看作是 蚂蚁 寻找 “食物源 ”的过程 。 输入 ：数据源 D = (U ，，，R ) ，参数 和 卢 输 出 ：用户 聚类 (1) 设 U 是 m 个 z维 待进行 聚类分析 的用户数据 集合 ，U = { l ：(Ui。，U ，⋯ ，Ui ) ，i：1，2，⋯ ，m }， 其 中 U 指用户 i的第 个 特征属 性值 ，则 数据对象间 的 欧 氏距离 (相 似度 ) 为 ： 厂 1 — — — — — — — — 一 d(u ， )=√∑( ) (3) ， “，特征属性 越相 似 ，其欧 氏距 离越 小 ，反 之越 大 。 (2) 根据数据源 D = (U ，，， ) ，运用公 式(1) ，可 以获得用户 的评分 数 据相 似度 sim (Id,；，u，) ，考虑 到项 目评分 的不 同时间会 影 响用户 间的评 分相 似度 ，故最 终相似度 sim (u ，u ) ×埘 式 中权值 W ：1／l I t — tj I I ，t 和 tj 分别 为用户 和 M 进行项 目评分时 的时间 第 l0 期 吴 月萍 等 ：基于 蚁群算 法的协同过滤推荐 系统 的研 究 · 75 · 段 ，时间间隔越短 ， 值越大，反之越小。若用户评分 为同一时间段 ，则设 W 为 1。最后 以附带 权值 的评分 相似度作为蚁群算法中的信息素 (3) 运用蚂蚁觅食原理 ，蚂蚁寻找食物源所选择 路 径的概率 (4 )作 为判断用户 u 是否与 归为一类的 依据 。 ’ 7",jrl~ 二 (4 ) 式 中，S = { I s ≠ ，s = 1，2 ，⋯ ，m }，叩 = 1／d(1．t ， u，)称 为能见度 ，这个量基本不变 ，O／和JB 为控 制信息素 和 能见度 之间的可调节参数 。当参数 = 0 ，届= 1 ，以 用户 能见 度来 寻找聚类集 ，因此 ，即使那些从 未评分 过 的新用户 ，也 能通过蚁群算法找到聚类集 ，从 而解决 了 新用户得 不到推荐的问题 。 重复 步骤 (1) 一(3 )，计算 p⋯ ，p ，⋯ ，P 寻找 与 u 最大 的 m ax (p ) ， = 1 ，2 ，⋯ ，m ， ≠ i，则将 M 归 并 到 u 领域 。这里没 有涉及 P 与设定 概 率 P0 的 比 较 ，不管最 大概率 是否大 于 Po，文 中都 以与 “ 的最 大 概率 的 作为归并类 ，这样解决 了用户聚类 的孤立点 问 题 。 2 ．3 协 同过滤推荐算 法 基于蚁群聚类算法获得用户数据对象的聚类 ，然 后在聚类 中寻找 目标用户 的最近邻居 ，基 于最 近邻 居评分实现 目标用户 向未评 分项 目的预测评 分 ，并 从 中选择 前 Ⅳ个评 分 最 高 的项 目，作 为 目标 用 户 的 T op — N 推荐集 。 输 入 ：数据源 D = ( U ，，， ) ，用户 聚类 输出 ：最高评分 的 Ⅳ个推荐集 。 ( 1) 根据公式 (1 ) 计算 目标用户 在 此聚类 中的 用户评 分相似度 ，并按 从高到低 排列 形成 邻居 集合 M = {“，，“ ，⋯ ，“ }，邻居集 中邻居个数 t可通过实验设 定 。 (2) 根据公式 (2 ) 及最近邻居集 即可 预测 目标 用户 “ 对未评分项 目的评分 ，最后选择前 Ⅳ个评分最 高 的项 目推荐 给 目标 用户。 3 实验 结果与分析 3 ．1 实 验 环 境 以 M ovieLens 站点 所 提供 的数据 集 为 实 验环 境 ， 其中用户 943 个 ，项 目( 影片 ) 1682 个 ，用 户对 影 片产 生 10 万条评分记录，但用户评分数据集的稀疏等级只 有 0 ．9370 。 每个用户 由编号 、年 龄 、性别 、职业 等属 性描述 ，将 各用户年龄及性别属性值分别转化成向量表示 ，而职 业属性 不能独立转化 ，需进行用户 间的比较 ，若用 户职 业相同，则此项比值为 0 ，否则比值为 1，经过这些数据 处理后 ，计算 用户问 的欧 氏距离 。用户对 影 片按 五个 (1，2，3，4 ，5 )等级来 评定 ，整个数 据集 按 80％ 和 20％ 来进行划分成训 练集 和测试集 。 3 ．2 评价指标 评价推荐 系统推荐 质量的度量标准有统计精度度 量方法 ，该 方 法 中的 平均 绝对 偏 差 M AE (M ean Abso． 1ute E rror) 易于理解 ，应用较直接 、广泛 。因此 ，文 中采 用平均绝对偏差 M AE 进 行度 量。通 过计算 用户 对 目 标项 目的预测值 与实际评价值之间的偏差来度量评价 预测的准确性。其偏差越小 ，预测精度越高，推荐质量 越高 ，否则相反 。平均 绝对偏 差 M A E 定义为 ⋯ 』： M A E = Ⅳ ∑ lP“_ — q l 型— — 二h ( 10 ) Ⅳ 、 其 中，P 表示用 户 u 对项 目 i 的预测评分 ，q 表 示用户 对项 目 i 的实 际评分 ，Ⅳ为被评估 的用户 “在 测试集 中待评价 的影 片个数 。 3 ．3 实验结果与分析 实验 1 基 于蚁群 聚类算 法实 现 M ovieLens 站点 中 的用户集 分类 。实验首先 比较带时问差和不带 时间差 的评分 相似度 ，结果显示 ：考虑评分时 问因素的 943 个 用户 ，在 参数 a 和J8 的调节过程 中 ，其 聚类数都要达 到 二百 多个 ，可见聚类个数 较多 ，分类 较细 ；而不 考虑 时 间差的聚类 ，其 聚类个数 明显 减少 ，当参数 = 0 ， = 1 时 ，聚类个 数为 13，当参数 = 1， = 0 时 ，聚类个数 为 2l，其余参 数值 ，所 得 聚类 数均 为一百 多个 。因此 ，虽 然考虑 时间因素的评 分 能更精 确地 实现用 户 聚类 ，但 对 于评分数据 相当稀疏 、聚类数据量不大的环境 ．可 以 不考虑 时问差 。文 中实 验 2 未 考虑 时间差 ，当 目标用 户为新用 户时 ，即没有 评分记 录的用户 ，则设参数 = 0 ，卢：1，以用 户能见度来 寻找聚类集 ；否则使用参数 = 1， = 0 ，凭用户信息素来实现聚类。 实验 2 基于实验 1 所 得 的用户 聚类 ，对 已有 用户 评分的项 目进行预测评分 ，分别取 lO 至 50 个最近邻 居数进 行预测评分 ，问隔为 10。在 同一数 据环境 下 与 传统协 同过滤 (T raditional C F ) 、基于 K — M eans 用 户聚 类 的协 同过滤进行 比较 。最终结 果如 图 1 所示 ，基于 蚁群算 法实现协 同过滤推荐 能得 到相对较好的效果 。 4 结束语 为 了避免受 K — M eans 聚类 初始 值 设置 的较 大 影 响 ，文 中基 于 蚂 蚁 觅食 的原 理 ，通 过 蚂蚁 寻 找 “食物 源”的过 程实现 用 户聚类 ，实验 验证 此 方法 的在 降低 最近邻搜索开销的同时，提高了协同过滤推荐的精度， 且调 节参数 O／和 ，可 以解 决新 用户 的冷 启动 问题 。 · 76 · 计算机技术与发展 第 2l 卷 针对用户评分相对密集的数据 ，还可以考虑时间差的 因素，以进一步提 高推荐效果 ；同时可 以考虑文献 [12 ]的方法实现用户属 性 的加 权 ，以提 高聚类 的准确 性 。 1．5 6 1．4 8 1．4 1．3 2 I．24 l_16 1．O8 1 1O 20 30 4 0 5 0 图 1 推荐精度 的比较 参考文献 ： [1] Breese J，Hecherm an D ，K adie C．Em pirical anal ysis of pre— dictive algorithm s for collaborative filtering[C ]／／In：Proceed— in g s of th e 14 th C o nfe ren c e o n U n c e rta in ty in A rtifi cial In te lli— gence (UA I’98)．[s．I．] ：[s．n．] ，1998：43-52． [2] Lee J s ，Jun C H ，Lee J，et a1 ．Classification—based collabora- tive filtering using m arket basket data[J]．Expert System with A p plications，2005 ，2 9 (3 ) ：700 - 704 ． [3 ] A dom avicius G ，Tuzhilin A ．Tow ard the next generation of rec— om m end er system s：a survey of th e state-of- the- art and pos sible extensions [J] ．IEEE Trans on Knowledge and D ata E ngineeri ng ，2005 ，17 (6 ) ：734 -7 49． [4 ] 李 涛，王建东．一种基于用户 聚类的协 同过滤推荐算法 [J]．系统工程与电子技术 ，2007 ，29 (7 )：1178—1182． [5] 黄国言，李有超．基于项 目属性 的用户聚类协同过滤推荐 算法[J]．计算机工程与设计 ，2010 ，31(5) ：1038— 104 1． [6] Deneubourg J L ，Goss s ，Franks N ，et a1 ．Tile dynam ics ofco1． 1ective sorting：Robot-like an ts and ant—like robots[c ]／／Pro - ceedings of th e F irst international C onf erence on Sim ulation of A daptive haviour： Fro m A nim al s to A nim al s J．C am bri dge ． M A ：M IT Press，199 1 ：356 -36 5 ． [7 ] 杨 燕 ，张昭涛．基于 阈值 和蚁群算法结 合的聚类方 法 [J]．西南交通大学学报，2006 ，41(6) ：719—742． [8 ] 马 良，朱 刚 ，宁爱兵．蚁群优化算法[M ]．北京 ：科学出 版社 ，2008 ． [9 ] Aggarwal c C ．O n the effects of dim ensional ity re duction on hish dim ensional sim ilarity search [C ]／／Proceedings of the 20 th A C M S IG M O D — SIG A C T - SIG A R T ．Sym posium on P rin- ciples of Databas e System s．[s．I．]：[s．n．]，2001：256 -266． [1O ] 王明文 ，陶红亮．双向聚类迭代的协 同过滤推荐算法 [J]． 中文信息学报 ，2008，7(22 )：61—65． [11] Sarwar B ，Karypis G ，Konstan J，et a1 ．Item -Based collabora- tire filtering re com m endation al gorithm s[C ]／／In：Proceedings of the 10th intem afional W odd W ide W eb Confere nce．[s． 1．]：[s．n．] ，2001：285—295． [12] 李玲娟 ，李 冰．一种基 于特征加权 的蚁 群聚类新算 法 [J]．计算机技术与发展 ，2010 ，20 (8 )：67—70． (上接 第 72 页) 5 结束语 文中将 不确 定数 据 中形 成 的 可 能世 界进 行 了缩 减 ，以此为基础进行 k 个最 佳结 果查 询 。通过 实验 表 明文 中提出 的 R PW —KBest算 法显 著地 提高 了查询 效 率 ，减小 内存消耗 。 由于概率 查询算 法依 然 面临很 多 挑 战和尚待解 决的问题 ，因此 ，下一步 的工作综合分 析 现有查 询算 法的优缺点 ，在查询算法上进行深入研究 。 参 考文献 ： [1] 周傲英，金澈清，王国仁 ，等．不确定性数据库管理技术研 究综述[J]．计算机学报，2009 ，32(1)：1- 16． [2] Solim an M A ，Ilyas I F ，Chan g K evinChen-Chuan．T0p— k Query Processing in Uncertain D atabases[C ]／／2007 IEEE 23rd International Conference on Data Engineering．[s．1_] ： [s．n．]，2007 ：15-20． [3 ] 孙永佼 ，王国仁．P2P 环境 中不确定数据 Top— k 查询处理 算法[J]．计算机研究与发展，2009 ，46(S) ：280-286． [4 ] R ’e C ，Dal vi N ，Suciu D ．Efficient Top- k Query E val uation on Probabilistie D ata 『C ]／／IE E E 23rd Intern ational C onf er- ence on Data Engineering．[s．1|]：[s．n．]，2007 ：15-20． [5 ] Lian Xiang，Chen Lei．Top-k Dom inating Queries in Uncertain D ata base[C ]／／Data Engineering．ICD E 2007．IEEE 23rd In- ternational Confere nce．[s．I_]：[s．n．] ，2007． [6 ] Pei J，Jian g B ，Lin X ，et a1 ．Probal itistic kyline on uncertain data[C ]／／Proceeding of th e 33rd international confere nce on very large databases．V ienna，Austria：[s．n．]，2007． [7 ] Huang Y ，Chen C ，LEEC．Continuous k-nearest neighbor query fo r m oving objects with uncertain velocity [J]．G eoin form atica ，200 9 ，13 ( 1 ) ：1- 25 ． [8 ] 周 帆 ，李树全，肖春静．不确定数据 Top—k 查询算法[J]． 电子测量与仪器学报 ，2010，30(10 )：2605-2609． [9 ] 韩希先 ，杨东华 ，李建 中．TKEP ：海量数据 上一 种有效 的 Top—K 查询处理算法[J]．计算机学报 ，2010 ，33(8) ：1405— 14 1 8 ． [10 ] 周 逊 ，李建 中，石胜飞．不确定数据上两种查询的分布式 聚集算法[J]．计算机研究与发展 ，2010 ，47(5) ：762-771． [11] 刘德喜 ，万常选，刘喜平．不确定数据库 中基于 x-tuple 的 高效 TO p—k 查询处理 算法[C ]∥第 26 届中国数据库学术 会议论文集(A 辑 )．[出版地不详] ：[出版者不详 ]，2009 ： 1 5 — 1 8 ． [12 ] 吴义虎 ，武志平．基于平均车速 和车速标准差 的路段安全 方法[J]．公路交通科技 ，2008 ，25(3) ：139 —142．