基于K-means的改進協同過濾算法

吳婷婷，李孝忠，劉徐洲

(天津科技大學人工智能學院，天津 300457)

互聯網上信息資源的爆炸式增長給用戶帶來了信息過載問題，不明確的用戶需求更是對搜索引擎提出了更大的挑戰[1–2]．針對這一問題，推薦系統作為一種高效便捷的自動化篩選信息工具受到廣泛關 注[3]．已有的推薦系統可分為基于內容的推薦、基于關聯規則的推薦、協同過濾推薦、混合推薦[4]．在目前的推薦系統中，基于協同過濾的推薦算法使用范圍最廣[5]，具有較高的研究和發展價值．常用的協同過濾推薦算法主要有兩類[6-7]：(1)基于用戶的協同過濾(user-based collaborative filtering，User-based CF)算法，通過用戶的歷史行為判斷用戶對項目的喜愛程度，根據不同的用戶對同一項目的偏好計算用戶之間的關系，并在具有相同偏好的用戶之間進行項目的推薦；(2)基于物品的協同過濾(item-based collaborative filtering，Item-based CF)算法，根據計算不同用戶對不同項目的喜愛獲得項目之間的關系．但是在使用協同過濾推薦算法中存在著數據稀疏、用戶相似度不高等問題，導致推薦結果的準確度較低. Kanimozhi[8]通過對商品進行聚類，較大程度上縮小了商品的最近鄰居搜索范圍，提高了算法的運行效率．但是，該算法并沒有利用用戶對商品的評級信息，忽視了用戶的歷史行為記錄，從而導致了推薦結果準確性的提高存在一定程度的限制．Tsaic等[9]將協同過濾算法與聚類算法相結合，有效地提高了推薦系統的準確度，但是在計算用戶的相似度時僅使用了皮爾森相似度公式，存在著用戶相似度可能不高的問題．李順勇等[10]將K-means聚類算法運用到協同過濾算法中，并利用改進的相似度公式尋找用戶的鄰居集合，在一定程度上提高了推薦結果的準確性，但是在運用相似度公式時未考慮用戶共同評級的影響．岳希等[11]先用基于用戶的協同過濾算法對用戶未評價的項目進行預測，然后將預測分數對原始用戶-項目評分矩陣進行填充，從而緩解了數據的稀疏性．但是第一次運用協同過濾算法時采用皮爾森相似度進行計算，導致預測評分存在一定的偏差，影響原數據的準確性以及后續的推薦結果．Feng等[12]在計算用戶相似度時考慮多種因素的影響，提高了用戶之間相似度性．但是計算較為復雜，計算量較大，影響算法的整體效率. Koohi等[13]將模糊聚類融合到協同過濾算法中，得到最 佳的推薦結果，但是在數據量較大時，要獲得確定 的聚類結論可能有一定的困難，影響用戶之間的相 似度．

本文主要針對基于用戶的協同過濾算法中的用戶相似度計算部分以及K-means聚類算法進行改進．相似度公式主要考慮用戶之間共同評分的項目的數量以及不同用戶針對同一項目評分標準之間的差異這兩個影響因素，進而提高用戶之間的相似度；聚類過程中主要在K-means聚類算法的基礎上引入了二分K-means聚類算法，從而提高聚類結果以及推薦結果的準確性．

1 基礎工作

1.1 基于用戶的協同過濾算法

基于用戶的協同過濾(User-based CF)算法于1992年提出并在郵件過濾系統中應用成功，1994年被研究機構GroupLens在新聞過濾中成功使用，直到2000年成為了推薦系統領域中應用最廣泛的算法之一．該算法收集用戶偏好的數據后，使用KNN算法計算用戶的最近聚類，從而得出用戶的共同偏好，最終根據共同偏好程度向用戶推薦共同偏好．

在User-based CF算法中，對目標用戶進行推薦需要利用用戶-項目評分矩陣搜索與目標用戶相似的鄰居用戶，利用鄰居用戶產生預測評分．算法主要有3個步驟：相似度計算、鄰居用戶的選擇和評分預 測[14]．User-based CF算法的流程圖如圖1所示．

圖1 User-based CF算法的流程圖 Fig. 1 Flowchart of the User-based CF algorithm

相似度計算過程是算法的核心部分，常見的相似度計算方法公式有皮爾森(Pearson)相似度、杰卡德(Jaccard)相似度等，這些相似度計算方法是將一個用戶對所評價項目的分值作為一個向量計算用戶之間的相似度．隨著數據信息的快速增長，用戶和項目數量都在急劇增加，這種情況導致了用戶-項目評分矩陣非常稀疏，上述傳統相似度計算方法的效果并不理想．因此，近幾年來有很多針對相似度計算的研究．

1.2 K-means算法

聚類是以相似性為基礎的，也就是將相似的東西劃分為一組，在聚類的過程中并不知道某一類是什么，而最終的目標僅僅是把相似的東西聚到一起．聚類一般為數值聚類，對數據提取M種特征并組成一個M維向量，進而得到一個從原始數據到M維向量空間的映射，然后基于某種方法或者規則進行劃分，使得同組的數據具有最大的相似性．其中，K-means算法是聚類算法中應用最廣泛、最簡潔的一種算法．

K-means算法是基于距離的聚類算法中的一 種[15]．該算法的目標是根據輸入的參數K(聚類目標數)，將所有的數據劃分為K個類．基本思想是將每個數據點歸為距離它最近的聚類中心點所在的簇類．其具體步驟如下：

(1)隨機在數據點中選取K個數據點作為初始聚類中心點．

(2)對于每一個數據點，利用歐幾里得公式計算該點到每一個聚類中心的距離并將其劃分到最近的類．其中，歐幾里得公式為

其中：x、y為用戶u、v評價項目的分值；iur、ivr表示用戶u、v對項目i的評分；n為項目個數．

(3)利用公式(2)重新計算每一個類別中數據點的平均值，并將得到的平均值點作為新的聚類中心點．若沒有數據點和平均值點相同，利用公式(1)計算數據點到平均值點的距離，將距離平均值點最近的數據點作為新的聚類中心點．

其中：Ci表示第i個類別，ci代表第i類數據的平均值點，x是第i個類別中的數據點，im為第i個類別中數據點的個數．

(4)如果聚類中心的變化沒有超出預設的閾值，則收斂；否則轉到步驟(2)．

K-means聚類算法簡單，計算速度快，同時在處理大量數據時具有相對可伸縮性．

1.3 二分K-means算法

當質心相對較遠時，K-means聚類算法不能很好地在簇與簇之間重新計算分布質點，因而聚類結果不佳[16]．為了改善這一問題，采用二分K-means算法，該算法屬于分層聚類的一種．通常分層聚類有兩種策略：聚合，一種自底向上的辦法，將每一個觀察者初始化本身為一類，然后進行兩兩相結合；分裂，一種自頂向下，將所有的觀察者都初始化為一類，然后進行遞歸分裂．

二分K-means算法為了得到K個簇，將所有數據作為一個簇集合并分裂成兩個簇，直到劃分為K個簇．該算法的具體步驟如下：

(1)將所有數據點當成一個簇．

(2)對每一個簇計算簇內誤差平方和(sum of squared error，SSE)．SSE表示某一簇內其他數據點到聚類中心的距離總和，該值越小，說明該簇越緊湊，聚類效果最好．在給定的簇上進行K-means聚類(K＝2)，并計算將該簇分裂后的總SSE．其中，SSE的計算公式為

其中：ic表示質心，x表示以ic為質心的簇內的數據，dist表示兩個向量的歐幾里得距離．

(3)選擇可以最大程度降低SSE值的簇進行 劃分．

(4)重復步驟(2)和(3)，直到達到指定的簇數時停止．

因為二分K-means算法在計算相似度的數量少，所以該算法可以加速K-means算法的執行速 度，同時能夠克服K-means算法收斂于局部最小的缺點．

2 本文改進的協同過濾算法

2.1 相似度的改進

傳統的相似度計算方法在計算用戶之間的相似度時都存在著各自的缺陷．比如，Jaccard相似度在計算時僅考慮了用戶之間共同的評分項目的數量，Pearson相似度在計算過程中僅考慮了用戶之間不同評分標準的差異性．針對傳統的相似度計算方法存在的缺陷進行如下改進：

(1)考慮用戶共同評分項目的數量對相似度的影響．在計算相似度過程時，會發現兩個用戶共同評分項目的數量越多，兩者相似度就會越高．

(2)考慮用戶評分標準的差異對相似度的影響．用戶對同一個項目的評分標準又是不同的．比如，用戶1不喜歡項目1，對其評為3分；用戶2同樣不喜歡項目1，對其評為1分；而用戶3喜歡項目1，對其評為3分．

在計算相似度時，將Jaccard相似度和Pearson相似度進行結合，同時考慮了用戶共同評分項目的數量和不同用戶評分標準的差異性對相似度的影響，最終的相似度公式為

2.2 本文算法

K-means算法與協同過濾算法相組合的算法對傳統的協同過濾算法做出了進一步的改進，使得傳統推薦算法的準確率有了一定程度的提高．比如，文獻[7]將層次聚類算法與協同過濾算法進行融合，減少了用戶搜索鄰居的范圍，提高推薦速度，有效地提高了推薦結果的準確性，但該方法計算的復雜度較高．文獻[17]將密度聚類算法與協同過濾算法進行結合，進一步提高推薦結果的準確性，但是該方法對于圈的半徑以及閾值這兩個參數的設置較為敏感．

考慮上述單一的聚類算法與協同過濾算法進行結合時出現的問題，將K-means算法和二分K-means算法進行結合對協同過濾算法進行改進．首先將數據集轉為用戶-項目評分矩陣(缺失值用0補充)；然后在通過K-means聚類算法進行第一次聚類，根據輪廓系數得到聚類效果最好的K值；接著將K值作為二分K-means聚類算法的輸入，再根據二分Kmeans算法進行第二次聚類，得到最終的聚類結果；最后根據目標用戶的相似鄰居已評分而目標用戶未評分的項目進行預測評分．輪廓系數(S(i))、預測評分按照式(5)和式(6)計算．

其中：b(i)表示樣本點i距離下一個最近簇中所有點的平均距離，a(i)表示樣本點i與同一簇內其他點的平均距離．S(i)值越大，聚類效果越好．

改進之后的算法流程如圖2所示，具體步驟 如下：

圖2 本文算法的流程圖 Fig. 2 Flowchart of the algorithm in this article

(1)將數據進行處理并轉為用戶-項目評分矩陣，缺失值用0填充．

(2)將用戶-項目評分矩陣作為K-means聚類算法的輸入，根據式(5)得到聚類效果最好的分類數目K．其中，利用式(1)計算樣本點與中心點的距離．

(3)將用戶-項目評分矩陣和聚類數目K輸入到二分K-means算法中，得到每位用戶所屬的簇．

(4)計算目標用戶所屬的簇以及該簇內最為相似的前m個相似用戶，利用式(4)作為相似度計算公式.

(5)根據鄰居用戶集合，利用式(6)對目標用戶未評分的項目進行預測評分．

3 實 驗

3.1 數據集

采用豆瓣電影數據集，該數據集包含了947位用戶對1494部電影的91319次評分，評分范圍為1～5，每一位用戶評價至少10部電影．數據集按照70%、30%的比例劃分為訓練集和測試集．數據集屬性包括用戶ID、產品ID以及相應的評分．

3.2 評價標準

采用平均絕對誤差(MAE)、準確率(Precision)、召回率(Recall)以及F1指標檢測算法的推薦結果，公式為

3.3 實驗結果與分析

為了得到聚類效果最好的簇數，使用輪廓系數作為評價聚類效果的標準．不同聚類數目K下的輪廓系數值見表1．

表1 不同聚類數目下的輪廓系數 Tab. 1 Contour coefficients under different clustering numbers

由表1可知：當聚類數目K為10時，K-means聚類算法的輪廓系數最高，即聚類效果最佳．

為了驗證本文所提的算法能夠有效地提高推薦結果的準確性，本文選取傳統的基于用戶的協同過濾算法，僅改進相似度的協同過濾算法，基于K-means的協同過濾算法作為本文的對比算法．對比結果如圖3—圖6所示．

圖3 不同算法的平均絕對誤差對比 Fig. 3 MAE comparison of different algorithms

圖4 不同算法的準確率對比 Fig. 4 Precision comparison of different algorithms

圖5 不同算法的召回率對比 Fig. 5 Recall comparison of different algorithms

圖6 不同算法的F1值對比 Fig. 6 Comparison of F1 values of different algorithms

由圖3可以看出，僅改變相似度計算方法或僅基于K-means的協同過濾算法的MAE值均比傳統協同過濾算法的MAE值低，但本文算法的MAE值是最低的，這也進一步說明本文算法預測的分值與實際的分值更接近．通過圖4—圖6可以看出，上述算法的準確率、召回率以及F1值均隨著目標用戶的最近鄰居數的增加而增加．首先，通過觀察發現僅改變相似度計算方法或者僅基于K-means的協同過濾算法均能使傳統的協同過濾算法的推薦效果提高，但推薦效果都不如本文的算法．其次，通過實驗結果發現尋找目標用戶的鄰居時，僅改變相似度的計算方法和僅基于K-means的協同過濾算法都在一定程度上使得用戶間的相似度得到提高，但是本文將兩者進行結合使得用戶之間的相識度更加準確，進一步驗證了相似度的計算是推薦算法的核心部分．

4 結語

本文將聚類算法和協同過濾算法進行結合，并對聚類算法和相似度計算進行相應的改進，提出了基于K-means的改進協同過濾算法．該算法在聚類過程中既考慮了K值選取的影響又考慮了隨機質心選取的影響，使得在尋找最近鄰居時的相似度更加準確．采用豆瓣電影數據集進行對比實驗，實驗結果表明本文算法進一步提高了推薦的效果．但是，面對數據集極度稀疏以及用戶冷啟動的問題還是無法解決，后續工作應該對算法進行相應的改進，以求進一步提高算法的準確度．