一種聚類與kNN結合的協同過濾算法

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

(西南石油大學 計算機科學學院，成都 610500)

1 引 言

協同過濾[1]是推薦系統中廣泛使用的技術之一，其主要的特點在于不依賴商品的內容，而是完全依賴于一組用戶表示的偏好[2].協同過濾可分為兩大類：基于內存[3]和基于模型[4].前者使用整個用戶商品數據庫進行預測，如slope one[5]，矩陣分解[6]等.后者通過學習用戶偏好的描述性模型，然后將其運用于預測評分，如神經網絡分類[7]，貝葉斯網絡[8]等.

傳統的kNN[9]推薦算法是使用所有鄰居進行商品之間的相似度計算.這不僅導致其時間復雜度較高，且由于只是用單個距離度量參與相似度的計算，還會使推薦精度不理想，如Jaccard[10]，Manhattan[11]等.

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

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

2 相關工作

全球信息量的增長速度遠超過我們可以處理的速度.每年都有很多尚未被探索的信息需要我們去處理.在如此龐大的信息量中找出我們所需要的信息是非常困難的.但是，有些技術可以幫助我們過濾沒有用的信息并找到有價值的信息.其中推薦系統中的協同過濾算法是應用最成功，也是最廣泛的技術之一.

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

聚類的思想對于找出商品之間的相似關系非常有用.聚類的問題可以定義為：給定d維空間中的n個數據點并將它們劃分為k個簇，簇內的數據點比簇外的數據點更加相似.

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

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

3 問題描述

本節首先提出了商品聚類信息系統.然后，給出了評分預測問題和商品聚類信息系統問題的形式化表達.

3.1 商品聚類信息系統

定義1.一個商品聚類信息系統是一個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，是用戶對商品的評分函數，且ri，j表示用戶ui對商品tj的評分，i∈[0，n-1]，如表1所示n=5，j∈[0，m-1]，如表1所示m=5.q:T→Q是商品所屬簇的映射，qj表示商品tj所屬簇.

如表1所示，E=2用戶u0對商品t0的評分為1，且沒有評價過商品t2.

表1 商品聚類信息系統Table 1 Item clustering information system

通常，評分數據通常為5個評級，即R={ 1，2，3，4，5}.注：rij=0表示用戶ui沒有評價過商品tj，W={0，1，…，E-1}表示所有商品被劃分為E個簇.因此，以下性質成立.

性質1.兩個商品tj與tj，屬于同一個簇，當且僅當

qj=qj

(2)

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

3.2 問題描述

問題1.預測評分.

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

2)輸出：預測評分；

3)約束條件：當兩個商品屬于同一簇時，才計算它們之間的相似度；

4)優化目標：使預測的評分更加接近真實的評分.

問題2.商品聚類.

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

2)輸出：Q；

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

4)優化目標：盡可能把相似性較強的商品劃分到同一簇中.

4 C-kNN算法

本章首先描述了預處理技術，即獲得聚類信息系統.其次，詳細介紹本文提出的C-kNN算法.最后，用一個運行實例來提高算法的可讀性.

4.1 C-kNN算法

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

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

算法1描述了C-kNN的實現過程.

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

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

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

(3)

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

第12行，取相似度最高的k個商品的平均分，即用戶ui對商品tj的預測評分值.

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

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

第1-6行，找出評分矩陣中每個商品的平均分，其公式為：

(4)

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

第7-11行，計算每個商品所屬的簇的下標索引，其計算公式為：

(5)

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

(6)

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

4.2 運行實例

表3 聚類算法Table 3 Clustering algorithm

5 實驗分析

本節首先介紹并分析實驗所用的數據集，其次介紹所使用的評價指標，接著描述總體的實驗設計，最后分析實驗結果.

5.1 數據集

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

表4 數據集信息Table 4 Statistic information of dataset

5.2 評價指標

本文所采用的推薦質量評價指標是均方根誤差RMSE和平均絕對誤差MAE.這二個指標廣泛用于評估推薦系統的性能.

RMSE是指參數估計值與參數真值之差平方的期望值的算術平方根，值越小說明預測模型描述實驗數據具有更好的精確度.公式如下：

(7)

其中pi，j表示用戶ui對商品tj的預測評分，ri，j表示用戶ui對商品tj的實際評分.

MAE則能更好地反映預測值誤差的實際情況，值越低說明誤差越小.其定義為：

(8)

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

5.3 實驗設計

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

1)不同的聚類結果對推薦準確性的影響.

2)算法C-kNN與經典kNN的性能對比.

針對第1)方面，對用戶進行聚類時，我們嘗試使用多種進行聚類以找出不同的聚類結果對實驗結果的影響.

針對第2)方面，我們設置k的值為5.根據找出的合適大小的平均分聚類在5.2所提出的二個指標上來進行實驗，隨后分析結果并比較算法的差別.

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

表5 數據集信息Table 5 Statistic information of dataset

由于Netflix數據集比較大，我們取其中的五部分進行實驗，分別為：用戶評分次數大于35，并小于40 (NF_1)； 用戶評分次數大于31，并小于34 (NF_2)； 用戶評分次數大于395，并小于400 (NF_3) ；用戶評分次數大于2300，并小于2350 (NF_4)； 用戶評分次數大于3500，并小于4000(NF_5).數據詳細信息如表6所示.

表6 數據集信息 Table 6 Statistic information of dataset

5.4 實驗結果

按照4.3節的實驗設計，分別在三個真實的數據集上進行實驗.

方面1，在MovieLens100K上進行實驗，找出不同的聚類對實驗結果的影響.根據聚類閾值的大小，我們將商品分為2到10組.結果如下：

由圖2和圖3可以得出，不同的閾值會影響實驗結果.因為根據不同的，可能導致有些較為相似的鄰居沒有被聚到同一簇中.

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

方面2，分別測試了RMSE，MAE兩種評價指標.結果如下：

表7 MovieLens100K實驗結果(MAE)Table 7 MovieLens100K experimental results (MAE)

通過實驗可以知道，C-kNN比經典的kNN推薦算法在MovieLens100K上，性能大約有4%到5%的提升，在Epinions上大約有1%到2%的提升.

表8 MovieLens100K實驗結果(RMSE)Table 8 MovieLens100K experimental results(RMSE)

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

表9 ML1M實驗結果(MAE)Table 9 ML1M experimental results(MAE)

由表9得到的信息，在ML1M上劃分成的三個子數據集分別做了實驗.結果表明，相較于經典的kNN協同過濾算法，預測值誤差降低了7%到10%.

表10 ML1M實驗結果(RMSE) Table 10 ML1M experimental results(RMSE)

根據表10結果表明，C-kNN與經典的kNN推薦算法對比，在ML1M所劃分的三個子數據集中在RMSE上提升了7%到9%.

表11 Netflix實驗結果(MAE) Table 11 Netflix experimental results(MAE)

根據表11實驗結果表明，在不同的稀疏度下，C-kNN比經典的kNN推薦算法在MAE上都有較大的提升.

表12 Netflix實驗結果(RMSE) Table 12 Netflix experimental results(RMSE)

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

6 結 語

本文提出了一種聚類與kNN結合的協同過濾算法，并在4個真實數據集上進行了實驗.其性能相比于傳統的kNN推薦算法，在MAE和RMSE上都有較大的提升.表明在使用kNN算法進行評分預測前，利用M-distance聚類算法對所有商品進行劃分，最終可以有效的提高推薦精度.