基于加權(quán)信息熵相似性的協(xié)同過濾算法

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

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

0 引言

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

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

式中：Ru，i，Ru，j分別為用戶u 對(duì)項(xiàng)目i和j的評(píng)

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

1.1 算法的提出

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

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

1.2 NN WD算法設(shè)計(jì)

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

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

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

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

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

式中：n為項(xiàng)目I1和I2的共同評(píng)分集合大小；di為第i項(xiàng)評(píng)分的差值；Ni為di在評(píng)分差異度集合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，值越大，項(xiàng)目間的相似度越高.

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

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

2.1 實(shí)驗(yàn)數(shù)據(jù)集

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

2.2 預(yù)測(cè)評(píng)分和度量方法

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

式中：Ru，I為用戶u對(duì)I的評(píng)分；和RI為Ia和I的平均評(píng)分；sim（Ia，I）為Ia和I的相似度.

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

2.3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

3 結(jié)論

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

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

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

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

［4］ 羅辛，歐陽(yáng)元新，熊璋，等.通過相似度支持度優(yōu)化基于K近鄰的協(xié)同過濾算法［J］.計(jì)算機(jī)學(xué)報(bào)，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］ 夏培勇.個(gè)性化推薦技術(shù)中的協(xié)同過濾算法研究［D］.青島：中國(guó)海洋大學(xué)，2011.

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

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

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

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