喻新潮，曾圣超，溫柳英 ，羅朝廣

(西南石油大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，成都 610500)

1 引 言

協(xié)同過濾[1]是推薦系統(tǒng)中廣泛使用的技術(shù)之一，其主要的特點(diǎn)在于不依賴商品的內(nèi)容，而是完全依賴于一組用戶表示的偏好[2].協(xié)同過濾可分為兩大類：基于內(nèi)存[3]和基于模型[4].前者使用整個(gè)用戶商品數(shù)據(jù)庫進(jìn)行預(yù)測(cè)，如slope one[5]，矩陣分解[6]等.后者通過學(xué)習(xí)用戶偏好的描述性模型，然后將其運(yùn)用于預(yù)測(cè)評(píng)分，如神經(jīng)網(wǎng)絡(luò)分類[7]，貝葉斯網(wǎng)絡(luò)[8]等.

傳統(tǒng)的kNN[9]推薦算法是使用所有鄰居進(jìn)行商品之間的相似度計(jì)算.這不僅導(dǎo)致其時(shí)間復(fù)雜度較高，且由于只是用單個(gè)距離度量參與相似度的計(jì)算，還會(huì)使推薦精度不理想，如Jaccard[10]，Manhattan[11]等.

本文通過結(jié)合聚類與kNN算法，提出了一種更加高效的協(xié)同過濾算法(C-kNN).首先，我們使用M-distance聚類方法[12]對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，旨在把具有相似性的商品歸為一簇.M-distance是一種基于平均評(píng)分的聚類算法，相比k-means[13]，它具有更優(yōu)的時(shí)間復(fù)雜度，且聚類的結(jié)果是確定的.然后，我們針對(duì)同一簇中的商品進(jìn)行預(yù)測(cè)，其中預(yù)測(cè)評(píng)分為鄰居評(píng)分的期望.C-kNN不僅通過聚類顯著地縮小了鄰居的搜索范圍，進(jìn)而有效地提高運(yùn)行速度，還考慮了商品之間的強(qiáng)關(guān)聯(lián)性，因此能夠更加準(zhǔn)確的預(yù)測(cè)出用戶對(duì)商品的評(píng)分.其中，相似度的計(jì)算采用的是Manhattan距離.它把兩個(gè)商品之間的評(píng)分差的絕對(duì)值作為度量衡，且距離越小越相似.

實(shí)驗(yàn)采用留一法(leave-one-out)[14]作為交叉驗(yàn)證的方法，即每次都只將單個(gè)評(píng)分作為測(cè)試集，而其余的數(shù)據(jù)用作訓(xùn)練集.實(shí)驗(yàn)數(shù)據(jù)集包括MovieLens100K，MovieLens1M，Epinions以及Netflix.對(duì)于MAE而言，C-kNN比傳統(tǒng)的基于kNN的推薦算法在MovieLens100K上大約有4%到5%的提升，在MovieLens1M上大約有7%到10%的提升，在Epinions上大約有1%到2%的提升，在Netflix上大約有2%到16%的提升.對(duì)于RMSE而言，C-kNN比傳統(tǒng)的基于kNN的推薦算法在MovieLens100K上大約有6%到7%的提升，在MovieLens1M上大約有7%到9%的提升，在Epinions上大約有3%到4%的提升，在Netflix上大約有1%到17%的提升.

2 相關(guān)工作

全球信息量的增長(zhǎng)速度遠(yuǎn)超過我們可以處理的速度.每年都有很多尚未被探索的信息需要我們?nèi)ヌ幚?在如此龐大的信息量中找出我們所需要的信息是非常困難的.但是，有些技術(shù)可以幫助我們過濾沒有用的信息并找到有價(jià)值的信息.其中推薦系統(tǒng)中的協(xié)同過濾算法是應(yīng)用最成功，也是最廣泛的技術(shù)之一.

協(xié)同過濾推薦是通過探索用戶對(duì)商品或者信息的偏好來提取可能對(duì)該用戶有用的信息.偏好的提取可以是基于用戶的相似性也可以是基于商品的相似性.基于用戶的相似性算法首先根據(jù)新用戶的歷史數(shù)據(jù)，找到與其具有相似興趣的用戶，我們稱之為鄰居，然后將鄰居喜歡的物品推薦給新用戶.基于商品的相似性算法試圖找到與被推薦商品相似的一類商品，然后把它推薦給用戶.然而不管是基于用戶還是基于商品的推薦，都需要在全局尋找和其具有相似性的鄰居，這不僅會(huì)導(dǎo)致時(shí)間復(fù)雜度較高，而且也會(huì)降低最終推薦的精確度.

聚類的思想對(duì)于找出商品之間的相似關(guān)系非常有用.聚類的問題可以定義為：給定d維空間中的n個(gè)數(shù)據(jù)點(diǎn)并將它們劃分為k個(gè)簇，簇內(nèi)的數(shù)據(jù)點(diǎn)比簇外的數(shù)據(jù)點(diǎn)更加相似.

基于聚類思想的推薦，丁小煥等人提出了一種基于平行因子分解的協(xié)同過濾推薦算法[15].該算法所提出的三種不同方案的推薦模型對(duì)于精確度和召回率有較高的提升.楊大鑫等人提出的基于最小方差的k-means用戶聚類推薦算法[16]在緩解數(shù)據(jù)稀疏性方面具有顯著的效果，且在推薦準(zhǔn)確率上，比傳統(tǒng)的協(xié)同過濾算法有較大的提升.

kNN是由Cover和Hart于1968年提出的一個(gè)理論上比較成熟的方法.它的基本思想是：給定新的商品后，計(jì)算新商品與所有的鄰居之間的相似度，并找出k個(gè)最相似的樣本.kNN算法的優(yōu)點(diǎn)在于穩(wěn)定性較好且簡(jiǎn)單易用.但由于僅使用了單一的距離度量來計(jì)算相似度，這會(huì)降低推薦的精確度.

3 問題描述

本節(jié)首先提出了商品聚類信息系統(tǒng).然后，給出了評(píng)分預(yù)測(cè)問題和商品聚類信息系統(tǒng)問題的形式化表達(dá).

3.1 商品聚類信息系統(tǒng)

定義1.一個(gè)商品聚類信息系統(tǒng)是一個(gè)6元組：

S=(U，T，r，R，q，W)

(1)

其中U={u0，u1，…，un-1}表示為用戶的有限集合且|U|=n，T={t0，t1，…，tm-1}是商品的有限集合且|T|=m，r:U×T→R，是用戶對(duì)商品的評(píng)分函數(shù)，且ri，j表示用戶ui對(duì)商品tj的評(píng)分，i∈[0，n-1]，如表1所示n=5，j∈[0，m-1]，如表1所示m=5.q:T→Q是商品所屬簇的映射，qj表示商品tj所屬簇.

如表1所示，E=2用戶u0對(duì)商品t0的評(píng)分為1，且沒有評(píng)價(jià)過商品t2.

表1 商品聚類信息系統(tǒng)Table 1 Item clustering information system

通常，評(píng)分?jǐn)?shù)據(jù)通常為5個(gè)評(píng)級(jí)，即R={ 1，2，3，4，5}.注：rij=0表示用戶ui沒有評(píng)價(jià)過商品tj，W={0，1，…，E-1}表示所有商品被劃分為E個(gè)簇.因此，以下性質(zhì)成立.

性質(zhì)1.兩個(gè)商品tj與tj，屬于同一個(gè)簇，當(dāng)且僅當(dāng)

qj=qj

(2)

如表1所示：q0=q4，q1=q2=q3.其中Q所對(duì)應(yīng)的集合為Q0={t0，t4}，Q1={t1，t2，t3}，Q={Q0，Q1}.

3.2 問題描述

問題1.預(yù)測(cè)評(píng)分.

1)輸入：S=(U，T，r，R，q，W)；

2)輸出：預(yù)測(cè)評(píng)分；

3)約束條件：當(dāng)兩個(gè)商品屬于同一簇時(shí)，才計(jì)算它們之間的相似度；

4)優(yōu)化目標(biāo)：使預(yù)測(cè)的評(píng)分更加接近真實(shí)的評(píng)分.

問題2.商品聚類.

1)輸入：U，T，r，R，E；

2)輸出：Q；

3)約束條件：設(shè)置閾值，同屬于一個(gè)閾值區(qū)間的商品被分為一簇；

4)優(yōu)化目標(biāo)：盡可能把相似性較強(qiáng)的商品劃分到同一簇中.

4 C-kNN算法

本章首先描述了預(yù)處理技術(shù)，即獲得聚類信息系統(tǒng).其次，詳細(xì)介紹本文提出的C-kNN算法.最后，用一個(gè)運(yùn)行實(shí)例來提高算法的可讀性.

4.1 C-kNN算法

首先我們給出C-kNN算法的框架圖，如圖1所示.

圖1 算法框架Fig.1 Algorithm framework diagram

算法1描述了C-kNN的實(shí)現(xiàn)過程.

第1行，通過M-distance算法把商品劃分到不同的簇中.

第2行，初始化鄰居商品集合.

第3-11行，這是本文算法的核心.在滿足兩個(gè)商品同時(shí)屬于一個(gè)簇(第3行)且用戶ui對(duì)商品tj和tj，的評(píng)分都不為0時(shí)，通過Manhattan距離計(jì)算它們之間的相似度，公式如下：

(3)

第7，8行，每計(jì)算一個(gè)相似度就和該數(shù)組中的元素進(jìn)行比較，確保NeighborDistances[.]是一個(gè)從小到大有序的數(shù)組，數(shù)組是由k個(gè)最相似的元素組成.

第12行，取相似度最高的k個(gè)商品的平均分，即用戶ui對(duì)商品tj的預(yù)測(cè)評(píng)分值.

下面給出算法1的偽代碼.

算法2描述了算法1(第1行)中商品聚類的具體實(shí)現(xiàn)過程.

第1-6行，找出評(píng)分矩陣中每個(gè)商品的平均分，其公式為：

(4)

表2 C-kNN算法Table 2 C-kNN algorithm

第7-11行，計(jì)算每個(gè)商品所屬的簇的下標(biāo)索引，其計(jì)算公式為：

(5)

第12-14行，把每個(gè)商品分配到它所屬的簇中并得到簇的集合Q.對(duì)于1≤q≤E，其所屬的簇為：

(6)

下面給出算法2的偽代碼.

4.2 運(yùn)行實(shí)例

表3 聚類算法Table 3 Clustering algorithm

5 實(shí)驗(yàn)分析

本節(jié)首先介紹并分析實(shí)驗(yàn)所用的數(shù)據(jù)集，其次介紹所使用的評(píng)價(jià)指標(biāo)，接著描述總體的實(shí)驗(yàn)設(shè)計(jì)，最后分析實(shí)驗(yàn)結(jié)果.

5.1 數(shù)據(jù)集

實(shí)驗(yàn)采用4個(gè)真實(shí)數(shù)據(jù)集，分別是Epinion、MovieLens1M(ML1M)、MovieLens100K(ML100K) 、Netflix.通過對(duì)數(shù)據(jù)集的分析可以得出，4個(gè)數(shù)據(jù)集的平均分分別是3.75，3.53，3.51和3.6.最流行的電影分別被評(píng)價(jià)2314，7359，7372和32944次.如表4所示.

表4 數(shù)據(jù)集信息Table 4 Statistic information of dataset

5.2 評(píng)價(jià)指標(biāo)

本文所采用的推薦質(zhì)量評(píng)價(jià)指標(biāo)是均方根誤差RMSE和平均絕對(duì)誤差MAE.這二個(gè)指標(biāo)廣泛用于評(píng)估推薦系統(tǒng)的性能.

RMSE是指參數(shù)估計(jì)值與參數(shù)真值之差平方的期望值的算術(shù)平方根，值越小說明預(yù)測(cè)模型描述實(shí)驗(yàn)數(shù)據(jù)具有更好的精確度.公式如下：

(7)

其中pi，j表示用戶ui對(duì)商品tj的預(yù)測(cè)評(píng)分，ri，j表示用戶ui對(duì)商品tj的實(shí)際評(píng)分.

MAE則能更好地反映預(yù)測(cè)值誤差的實(shí)際情況，值越低說明誤差越小.其定義為：

(8)

其中pi，j，ri，j表示與公式(7)相同.

5.3 實(shí)驗(yàn)設(shè)計(jì)

在本節(jié)中，我們旨在討論以下兩方面：

1)不同的聚類結(jié)果對(duì)推薦準(zhǔn)確性的影響.

2)算法C-kNN與經(jīng)典kNN的性能對(duì)比.

針對(duì)第1)方面，對(duì)用戶進(jìn)行聚類時(shí)，我們嘗試使用多種進(jìn)行聚類以找出不同的聚類結(jié)果對(duì)實(shí)驗(yàn)結(jié)果的影響.

針對(duì)第2)方面，我們?cè)O(shè)置k的值為5.根據(jù)找出的合適大小的平均分聚類在5.2所提出的二個(gè)指標(biāo)上來進(jìn)行實(shí)驗(yàn)，隨后分析結(jié)果并比較算法的差別.

由于算法的運(yùn)行時(shí)間較長(zhǎng)，我們把ML1M的數(shù)據(jù)集取其中的3部分分別進(jìn)行實(shí)驗(yàn)，分別為：用戶評(píng)分次數(shù)大于500，并小于600(ML1M_1)；用戶評(píng)分次數(shù)大于500，并小于700(ML1M_2)； 用戶評(píng)分次數(shù)大于300，并小于400(ML1M_3).數(shù)據(jù)詳細(xì)信息如表5所示.

表5 數(shù)據(jù)集信息Table 5 Statistic information of dataset

由于Netflix數(shù)據(jù)集比較大，我們?nèi)∑渲械奈宀糠诌M(jìn)行實(shí)驗(yàn)，分別為：用戶評(píng)分次數(shù)大于35，并小于40 (NF_1)； 用戶評(píng)分次數(shù)大于31，并小于34 (NF_2)； 用戶評(píng)分次數(shù)大于395，并小于400 (NF_3) ；用戶評(píng)分次數(shù)大于2300，并小于2350 (NF_4)； 用戶評(píng)分次數(shù)大于3500，并小于4000(NF_5).數(shù)據(jù)詳細(xì)信息如表6所示.

表6 數(shù)據(jù)集信息 Table 6 Statistic information of dataset

5.4 實(shí)驗(yàn)結(jié)果

按照4.3節(jié)的實(shí)驗(yàn)設(shè)計(jì)，分別在三個(gè)真實(shí)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).

方面1，在MovieLens100K上進(jìn)行實(shí)驗(yàn)，找出不同的聚類對(duì)實(shí)驗(yàn)結(jié)果的影響.根據(jù)聚類閾值的大小，我們將商品分為2到10組.結(jié)果如下：

由圖2和圖3可以得出，不同的閾值會(huì)影響實(shí)驗(yàn)結(jié)果.因?yàn)楦鶕?jù)不同的，可能導(dǎo)致有些較為相似的鄰居沒有被聚到同一簇中.

圖2 E的選擇對(duì)MAE的影響Fig.2 Influence of E′s choice on MAE圖3 E°的選擇對(duì)RMSE的影響Fig.3 Influence of E′s choice on RMSE

方面2，分別測(cè)試了RMSE，MAE兩種評(píng)價(jià)指標(biāo).結(jié)果如下：

表7 MovieLens100K實(shí)驗(yàn)結(jié)果(MAE)Table 7 MovieLens100K experimental results (MAE)

通過實(shí)驗(yàn)可以知道，C-kNN比經(jīng)典的kNN推薦算法在MovieLens100K上，性能大約有4%到5%的提升，在Epinions上大約有1%到2%的提升.

表8 MovieLens100K實(shí)驗(yàn)結(jié)果(RMSE)Table 8 MovieLens100K experimental results(RMSE)

由表8可知在MovieLens100K、Epinions上，C-kNN比經(jīng)典的kNN推薦算法在RMSE上分別提升了6.34%、3.55%.

表9 ML1M實(shí)驗(yàn)結(jié)果(MAE)Table 9 ML1M experimental results(MAE)

由表9得到的信息，在ML1M上劃分成的三個(gè)子數(shù)據(jù)集分別做了實(shí)驗(yàn).結(jié)果表明，相較于經(jīng)典的kNN協(xié)同過濾算法，預(yù)測(cè)值誤差降低了7%到10%.

表10 ML1M實(shí)驗(yàn)結(jié)果(RMSE) Table 10 ML1M experimental results(RMSE)

根據(jù)表10結(jié)果表明，C-kNN與經(jīng)典的kNN推薦算法對(duì)比，在ML1M所劃分的三個(gè)子數(shù)據(jù)集中在RMSE上提升了7%到9%.

表11 Netflix實(shí)驗(yàn)結(jié)果(MAE) Table 11 Netflix experimental results(MAE)

根據(jù)表11實(shí)驗(yàn)結(jié)果表明，在不同的稀疏度下，C-kNN比經(jīng)典的kNN推薦算法在MAE上都有較大的提升.

表12 Netflix實(shí)驗(yàn)結(jié)果(RMSE) Table 12 Netflix experimental results(RMSE)

如表12所示，C-kNN協(xié)同過濾算法在不同稀疏度的下都要比經(jīng)典的kNN算法在RMSE上均有較大的提升.

6 結(jié) 語

本文提出了一種聚類與kNN結(jié)合的協(xié)同過濾算法，并在4個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn).其性能相比于傳統(tǒng)的kNN推薦算法，在MAE和RMSE上都有較大的提升.表明在使用kNN算法進(jìn)行評(píng)分預(yù)測(cè)前，利用M-distance聚類算法對(duì)所有商品進(jìn)行劃分，最終可以有效的提高推薦精度.