劉文龍，張桂蕓，陳 喆，朱薔薔

（1.天津師范大學(xué) 計算機(jī)與信息工程學(xué)院，天津300387；2.天津師范大學(xué) 城市與環(huán)境科學(xué)學(xué)院，天津300387）

0 引言

互聯(lián)網(wǎng)技術(shù)的快速發(fā)展使我們進(jìn)入了信息爆炸的時代［1］，用戶需要處理大量毫無意義的信息和垃圾數(shù)據(jù).個性化推薦系統(tǒng)是一種解決信息過載問題的工具，而協(xié)同過濾技術(shù)是推薦系統(tǒng)中最為成功的技術(shù)之一，尤其是在電子商務(wù)領(lǐng)域里的應(yīng)用［2］.它是基于這樣一種假設(shè)：興趣愛好相似的用戶對相同項目的評價相似.實現(xiàn)協(xié)同過濾技術(shù)時，依據(jù)所建立模型的種類，可以分為基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾［3］.由于在實際應(yīng)用中，項目數(shù)量更加穩(wěn)定，并往往遠(yuǎn)低于用戶數(shù)量，因此，基于項目的協(xié)同過濾方法更為常用［4］.它的大體步驟如下：①收集項目信息，如用戶的瀏覽購買和評價記錄；②根據(jù)收集的信息計算項目的K鄰近集合；③通過K鄰近集合進(jìn)行分析計算產(chǎn)生對目標(biāo)用戶的推薦.作者選擇基于項目的協(xié)同過濾算法對實驗結(jié)果進(jìn)行分析驗證.

由上面介紹的協(xié)同過濾技術(shù)步驟可以看出，相似性計算是協(xié)同過濾技術(shù)的核心.傳統(tǒng)的相似度計算方法有余弦相似性（Cosine）［5］、Pearson相似相關(guān) 系 數(shù)［5］、修 正 的 余 弦 相 似 性［5］、Spear man相似性.其中，Pearson相似相關(guān)系數(shù)是最為常用的相似度計算方法，Pearson相關(guān)系數(shù)用于衡量兩個向量之間的線性關(guān)系.設(shè)項目i和項目j共同評分的用戶集合為Uij，利用Pearson相關(guān)系數(shù)得到兩者相似性為Si m（i，j）

式中：Ru，i，Ru，j分別為用戶u 對項目i和j的評

1 基于加權(quán)信息熵的相似度計算方法NNWD

1.1 算法的提出

傳統(tǒng)的相似度計算方法在協(xié)同過濾技術(shù)中存在一定弊端，如：①在數(shù)據(jù)高維稀疏的情況下，用戶之間關(guān)注圈交集（共同評分項目）的規(guī)模大多偏小且不一致，傳統(tǒng)的相似性度量方法容易過分地夸大或者縮小用戶間的真實相似性［6］；②受數(shù)據(jù)稀疏等影響，推薦精度較低［6］；③Pearson相關(guān)系數(shù)必須滿足數(shù)據(jù)之間的線性關(guān)系以及殘差相互獨立且均值為0等假設(shè)［6］.當(dāng)這些條件不滿足時，其計算準(zhǔn)確度將會降低.

例如對于項目I1和I2，首先找出I1和I2共同評分的用戶評分，I1（2，1，2，1）和I2（5，4，5，4），用Pearson相關(guān)系數(shù)計算I1與I2的相似性Si m（I1，I2）＝1，完全正相關(guān)，相似度最高，而實際上I1的評分普遍偏低，I2的評分普遍偏高，他們的相似度沒有那么高.對于I3（4，5，4，5）和I2（5，4，5，4），Si m（I2，I3）＝－1，完全負(fù)相關(guān)，相似度最低，而I3與I2的普遍評分都比較高，他們的相似度沒有那么低.對于判斷I1（2，1，2，1）與I4（2，1，2，2），I1（2，1，2，1）與I5（2）誰更相似時，由于I1與I5只有一個項目評分一樣，用Pearson相關(guān)系數(shù)計算Si m（I1，I5）＝1，Si m（I1，I4）＝0.5774，而I1與I4有3個項目評分一致，它們相似度應(yīng)該更高.對于某些項目的評分，像I（1，1，1，1）和I（5，5，5，5），用傳統(tǒng)的相似度計算方法無法準(zhǔn)確計算它們之間的相似度.

1.2 NN WD算法設(shè)計

信息熵是信息論中用于度量信息混亂程度的一個概念.信息越混亂，信息熵越大.對于給定的樣本集X，它的信息熵公式為

式中：N為X 中分類的數(shù)量；p（xi）為X中第i類元素出現(xiàn)的概率.將信息熵用于項目之間相似度的計算，兩個項目之間評分差異的信息熵越大，表示兩個項目差異越混亂，相似度也就越低.基于信息熵的相似度計算步驟如下：

（1）假設(shè)項目I1和I2共同評分的用戶集合為U＝｛u1，u2，…，un｝，I1和I2的共同評分為I1＝（Ru1，I1，Ru2，I1，Ru3，I1，…，Run，I1）和 I2＝ （Ru1，I2，Ru2，I2，Ru3，I2，…，Run，I2），I1和 I2的 評 分 差 異 度D（I1，I2）定義為

（2）根據(jù)公式（2），計算差異度的信息熵為

這里N表示di的種類數(shù)，極端情況下若di全都相同，則N＝1.考慮到評分差異對相似度的影響，越大，相似度越低.所以計算信息熵時，加入權(quán)重更加合理.同時兩個項目擁有的共同評價數(shù)n也會對相似度產(chǎn)生影響，n越大，相似度越大，所以加入1／n作為權(quán)重.新的加權(quán)差異信息熵的計算公式為

式中：n為項目I1和I2的共同評分集合大小；di為第i項評分的差值；Ni為di在評分差異度集合D中出現(xiàn)的次數(shù).由公式可知，NWD（I1，I2）取值范圍為0到＋∞，NWD（I1，I2）越大相似度越低.

（3）將NWD（I1，I2）歸一化到 0，［］1由于NWD（I1，I2）越大相似度越低，所以采用如下歸一化方法［6］

其中 Max（NWDIa）表示NN WDIa集合中最大值；Min（NWDIa）表示NN WDIa集合中最小值；NN WDIa就是歸一化之后的相似度，取值范圍為0到1，值越大，項目間的相似度越高.

NNWD（Nor malized New Weighted Differences）算法是利用兩個項目之間的差異，將項目間共同評分的交集大小和差異大小作為權(quán)值加入到差異信息熵公式去，最后進(jìn)行歸一化處理，形成了歸一化的新加權(quán)差異信息熵（NN WD）算法.

2 數(shù)據(jù)實驗及結(jié)果分析

2.1 實驗數(shù)據(jù)集

實 驗 采 用 Movie Lens 站 點 （http：／／movielens.u mn.edu）的實驗數(shù)據(jù)，共匯總了用戶943個，項目（影片）1 682個，以及用戶對影片產(chǎn)生的100 000條評分記錄，數(shù)據(jù)集稀疏度為1－100 000／（943×1 682）≈0.93 695［7］，非常稀疏.用戶評分從1到5五個等級.數(shù)據(jù)集按80%和20%劃分成訓(xùn)練集和測試集.

2.2 預(yù)測評分和度量方法

將相似性最高的若干項目作為目標(biāo)項目Ia的鄰居集合M＝｛I1，I2，…，Ik｝，其中Ia?M，集合M中的項目按照與Ia相似度從高到低排列.根據(jù)K個最相似鄰居預(yù)測目標(biāo)用戶u對項目Ia的評分，公式為［8］：

式中：Ru，I為用戶u對I的評分；和RI為Ia和I的平均評分；sim（Ia，I）為Ia和I的相似度.

平均絕對誤差（MAE）是最常用的用于統(tǒng)計測試集精準(zhǔn)度的度量方法［9］.設(shè)用戶u對項目的預(yù)測值集合為｛p1，p2，…，pn｝，用戶u的實際評分集合為｛q1，q2，…，qn｝，平均絕對誤差 MAE 定義為［10］

2.3 實驗結(jié)果及分析

取測試集中10個項目來預(yù)測目標(biāo)用戶對它們的評分.分別取最鄰近集合大小K為10到60，步長為10，在同一數(shù)據(jù)環(huán)境下，與基于余弦相似性的協(xié)同過濾、基于Pearson相似性的協(xié)同過濾、基于Spear man相似性的協(xié)同過濾進(jìn)行比較.最終結(jié)果如圖1所示，可以看出基于信息熵的相似度計算方法一定程度上優(yōu)于其它方法.

圖1 不同的相似度計算方法產(chǎn)生的結(jié)果Fig.1 The result of different similarity calculation methods

進(jìn)而計算當(dāng)K＝70，80，90時，用NN WD方法的 MAE值分別為0.5741，0.5712和0.5665.

3 結(jié)論

作者將信息論中的信息熵理論應(yīng)用到協(xié)同過濾算法的相似度計算當(dāng)中，又考慮到不同的差異度對相似性的影響，對信息熵計算方法進(jìn)行相應(yīng)的加權(quán).運用基于項目相似性的協(xié)同過濾算法進(jìn)行試驗比較，相對于傳統(tǒng)的方法提高了預(yù)測精度.

［1］ 劉建國，周濤，王秉宏.個性化推薦系統(tǒng)的研究進(jìn)［J］.自然科學(xué)進(jìn)展，2009，19（1）：1－14.

［2］ 許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究［J］.軟件學(xué)報，2009，20（2）：350－362.

［3］ 李濤.推薦系統(tǒng)中若干關(guān)鍵問題研究［D］.南京：南京航空航天大學(xué)，2009.

［4］ 羅辛，歐陽元新，熊璋，等.通過相似度支持度優(yōu)化基于K近鄰的協(xié)同過濾算法［J］.計算機(jī)學(xué)報，2010，33（8）：1437－1445.

［5］ PANG Huan－li，ZHOU Lian－zhe，LIU Hai－mei.Personalization Portal System Based on Collaborative Filtering Algorith m［A］.Inter national Conference on Co mputer，Mechatronics，Contr ol and Electronic Engineering（CMCE）［C］.Changchun，JL，China：IEEE Industrial Electronics Society，2010：383－386.

［6］ 夏培勇.個性化推薦技術(shù)中的協(xié)同過濾算法研究［D］.青島：中國海洋大學(xué)，2011.

［7］ 鄧愛林，朱揚勇，施伯樂.基于項目評分預(yù)測的協(xié)同過濾推薦算法［J］.軟件學(xué)報，2003，14（9）：1621－1628.

［8］ 吳月萍，鄭建國.協(xié)同過濾推薦算法［J］.計算機(jī)工程與設(shè)計，2011，32（09）：3019－3021.

［9］ 黃國言，李有超，高建培，等.基于項目屬性的用戶聚類協(xié)同過濾推薦算法［J］.計算機(jī)工程與設(shè)計，2010，31（5）：1038－1041.

［10］孫小華.協(xié)同過濾系統(tǒng)的稀疏性與冷啟動問題研究［D］.浙江：浙江大學(xué)，2005.