基于K-means的改進(jìn)協(xié)同過濾算法

吳婷婷，李孝忠，劉徐洲

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

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

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

1 基礎(chǔ)工作

1.1 基于用戶的協(xié)同過濾算法

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

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

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

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

1.2 K-means算法

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

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

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

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

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

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

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

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

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

1.3 二分K-means算法

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

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

(1)將所有數(shù)據(jù)點當(dāng)成一個簇．

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

其中：ic表示質(zhì)心，x表示以ic為質(zhì)心的簇內(nèi)的數(shù)據(jù)，dist表示兩個向量的歐幾里得距離．

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

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

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

2 本文改進(jìn)的協(xié)同過濾算法

2.1 相似度的改進(jìn)

傳統(tǒng)的相似度計算方法在計算用戶之間的相似度時都存在著各自的缺陷．比如，Jaccard相似度在計算時僅考慮了用戶之間共同的評分項目的數(shù)量，Pearson相似度在計算過程中僅考慮了用戶之間不同評分標(biāo)準(zhǔn)的差異性．針對傳統(tǒng)的相似度計算方法存在的缺陷進(jìn)行如下改進(jìn)：

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

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

在計算相似度時，將Jaccard相似度和Pearson相似度進(jìn)行結(jié)合，同時考慮了用戶共同評分項目的數(shù)量和不同用戶評分標(biāo)準(zhǔn)的差異性對相似度的影響，最終的相似度公式為

2.2 本文算法

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

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

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

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

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

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

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

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

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

(5)根據(jù)鄰居用戶集合，利用式(6)對目標(biāo)用戶未評分的項目進(jìn)行預(yù)測評分．

3 實 驗

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

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

3.2 評價標(biāo)準(zhǔn)

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

3.3 實驗結(jié)果與分析

為了得到聚類效果最好的簇數(shù)，使用輪廓系數(shù)作為評價聚類效果的標(biāo)準(zhǔn)．不同聚類數(shù)目K下的輪廓系數(shù)值見表1．

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

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

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

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

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

4 結(jié)語

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