K-Means 聚類中心最近鄰?fù)扑]算法

郝雅嫻

山西師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西臨汾041000

0 引言

協(xié)同過濾算法技術(shù)［1］已經(jīng)被成功的運用到推薦系統(tǒng)中，基于協(xié)同過濾推薦算法的假設(shè)是:如果用戶對相同項目評分相似，那么這些用戶的興趣也是相似的.協(xié)同過濾算法通過分析不同用戶對不同項目的評分，對用戶的興趣進行建模，并為用戶提供推薦服務(wù).基于協(xié)同過濾算法的推薦一般有三步:即用戶數(shù)據(jù)收集，數(shù)據(jù)預(yù)處理以及做出推薦［2］.

基于最近鄰的推薦算法是計算每個用戶或者項目的最近鄰，通過最近鄰進行評分預(yù)測［3］，因為初始數(shù)據(jù)數(shù)據(jù)量與稀疏性非常大，因此會導(dǎo)致KNN 運算時間較長，從而導(dǎo)致推薦結(jié)果不理想［4，5］.目前一個較為成功的方法就是利用聚類算法減少推薦算法的計算復(fù)雜度.聚類算法可以將對象劃分為若干個類別，類別中任意兩個對象的相似度高于不同類別的相似度，在聚類算法的基礎(chǔ)上，推薦算法可以向用戶推薦受用戶歡迎的項目，并且降低算法的計算復(fù)雜度［6，7］. Shinde 等人利用聚類算法處理推薦算法中的冷啟動問題［8］，Ghazanfar 等人利用聚類算法鑒別并處理推薦算法中的gray-sheep 用戶問題［9］，文獻［10］中首先對項目進行聚類分析，然后將聚類后的聚類中心結(jié)果結(jié)合已評分的數(shù)據(jù)來計算用戶相似性.

本文將KNN 算法與Kmeans 算法相結(jié)合，利用目標用戶所屬的聚類中心代替目標用戶尋找其最近鄰，降低了KNN 算法單獨運算時的計算復(fù)雜度.本文提出的算法總體可以分為3 步:

首先對初始數(shù)據(jù)集進行聚類運算，然后找出數(shù)據(jù)集的聚類中心;

其次尋找每個用戶所屬的聚類中心，將聚類中心代替目標用戶放入KNN 算法中尋找用戶的最近鄰;

最后做出評分預(yù)測.同時又考慮到目標用戶與聚類中心對預(yù)測評分值的影響，于是在本文算法的基礎(chǔ)上提出了加權(quán)的思想.如果目標用戶已經(jīng)在聚類中心的最近鄰用戶集合中就不去計算其對評分值得影響，如果不在近鄰集合中，就添加目標用戶與聚類中心的評分值對預(yù)測評分值的影響.算法在Movielens 數(shù)據(jù)集上進行實驗，實驗結(jié)果表明，推薦算法評分預(yù)測的精確度得到顯著提高，而且加權(quán)之后的改進算法精確度也明顯提高.

1 預(yù)備知識

1.1 K-Means 算法

K-Means 算法是無監(jiān)督的聚類分析算法，其本質(zhì)是通過計算不同樣本間的距離來判斷他們的相近關(guān)系，相近的就會放到同一個類別中.

首先隨機選擇一個k 值，也就是將數(shù)據(jù)分為幾類.k 值就是最初選擇的聚類點，又稱質(zhì)心;其次計算數(shù)據(jù)集中每一個樣本點距離質(zhì)心的距離，分別將這些樣本分配到離其質(zhì)心最近的那一類中;再次計算每個類中樣本的平均值，將這個平均值作為新的質(zhì)心，然后重復(fù)第二步;最后不斷重復(fù)得到收斂質(zhì)心.下面給出的是K-Means 算法的偽代碼:

K-Means 算法:

1.2 基于用戶的最近鄰算法

基于用戶的最近鄰算法(K-Nearest Neighbor algorithm，KNN)是最早的協(xié)同過濾算法.其基本思想是利用目標用戶近鄰用戶的評分值去估計目標用戶對項目的評分預(yù)測值.隨后基于項目u 的最近鄰算法被提出.在這里只介紹基于用戶的最近鄰算法的基本思想，對于目標u 項目的最近鄰尋找，首先定義最近鄰個數(shù)k，將計算所得的相似度按從大到小的順序排列，選取前k 個作為目標項目u 的k 個最近鄰用戶.尋找項目最近鄰算法的關(guān)鍵問題是通過計算相似度來尋找最近鄰，計算相似度的方法常用的有歐氏距離、余弦相似度以及皮爾遜相似度，本文采用歐氏距離方法計算相似度，計算公式如下:

式(1)中的u 與v 分別表示原始評分矩陣中的任意兩個項目，ru，rv分別表示用戶u 與v 對應(yīng)的評分向量，sim(u，v)表示項目u 與v 之間的相似度大小.將計算所得的相似度大小保存到相似度向量矩陣中，預(yù)測評分值由評分值與相似度的加權(quán)平均值得到，即

當(dāng)原始評分矩陣具有極大的稀疏性時，利用相似度計算目標項目的最近鄰會出現(xiàn)誤差.因此許多學(xué)者在KNN 算法執(zhí)行之前會首先對原始評分矩陣進行預(yù)處理，從而使算法的準確性提高.下面給出基于用戶最近鄰算法的偽代碼:

KNN 算法

2 算法實現(xiàn)

2.1 算法步驟

第1 步～第4 步是尋找聚類中心的過程，首先針對數(shù)據(jù)集進行聚類，初始化聚類中心，計算每個樣本到聚類中心的距離，第三步重新計算聚類中心，直到收斂，第4 步輸出整個樣本的聚類中心.

第5 行～第8 行是進行最近鄰計算的過程，如果計算樣本x 對商品p 的評分，首先找到樣本x 所屬的聚類中心.第6 行用聚類中心代替樣本x 去計算最近鄰，得到聚類中心的最近鄰之后，通過預(yù)測評分公式計算評分值，最后輸出評分值.下面給出本文算法的偽代碼:

2.2 算法實例分析

下面給出實例模擬本算法的實驗，首先對表1 中的數(shù)據(jù)進行聚類分析.

表1 原始評分表Tab.1 Original Rating

表2 聚類中心Tab.2 Cluster centroids

表3 聚類類別Tab.3 Clustering Categories

隨機選取2 個聚類中心:Id =1，2，選擇用戶1與用戶2 作為聚類中心;

計算樣本與聚類中心間的距離，這里采用歐式距離，經(jīng)過計算S(1，3)= 4.58，S(1，4)= 7，S(1，

5)= 3.16，S(2，3)= 4.47，S(2，4)= 6.48，S(2，5)

= 5.19;因為S(1，3)＞S(2，3)，所以用戶3 選擇用戶2 作為聚類中心;

依據(jù)此規(guī)則，第一次的選擇結(jié)果，組1 成員:1與5，組2 成員:2，3，4.

第二次選擇聚類中心取樣本平均值，不斷重復(fù)以上步驟，分別得到聚類中心與樣本所屬的聚類類別表(表2).

根據(jù)表3 數(shù)據(jù)可知，只有用戶4 屬于第2 類，其余用戶屬于第一類，那么，接下來進行最近鄰計算，如果求用戶1 對M_3 的評分，則將用戶1 所屬聚類類別0 的聚類中心代替用戶1 尋找最近鄰，同樣進行相似度計算.

比較相似度并找出前2 個近鄰，最后根據(jù)評分預(yù)測公式進行評分估計，可得用戶1 對M_3 的評分值為1.364 4，不斷重復(fù)這個過程，最后可以的到完整的用戶評分預(yù)測值.

3 實驗結(jié)果分析

3.1 Movielens 數(shù)據(jù)集與評價指標

針對推薦算法，只有通過評測才可以了解其推薦質(zhì)量.推薦系統(tǒng)的評測指標問題同樣也是近幾年來諸多學(xué)者研究的課題重點.

本算法利用均方根誤差(RMSE)驗證實驗結(jié)果的準確性，以RMSE 值作為實驗準確性的評價指標，RMSE 的值越小算法實驗結(jié)果越優(yōu).計算公式如下:其中TestSet 表示測試集

MovieLens 數(shù)據(jù)集包括三個數(shù)據(jù)集.其一是一個小型的數(shù)據(jù)集，該數(shù)據(jù)集是943 個用戶對1 682 部電影的評分數(shù)據(jù)信息:其二是一個中型數(shù)據(jù)集，該數(shù)據(jù)集是6 040 個用戶對3 952 部電影的評分數(shù)據(jù)信息;最后是一個大型數(shù)據(jù)集，該數(shù)據(jù)集是71 567 個用戶對10 681 部電影的大約有一千萬條評分的數(shù)據(jù)信息.

本文實驗所采用的數(shù)據(jù)集為MovieLens 數(shù)據(jù)集中的小型數(shù)據(jù)集.圖1 展示了部分初始數(shù)據(jù)集，從圖中可知，MovieLens 數(shù)據(jù)集是非常稀疏的.

圖1 MovieLens Fig.1 MovieLens

3.2 實驗結(jié)果

根據(jù)算法步驟，首先對數(shù)據(jù)進行聚類分析通過對數(shù)據(jù)集進行聚類算法實驗，得到以下結(jié)果:圖2 列出的是經(jīng)過聚類為3 的聚類運算后，每個樣本所屬的聚類類別情況，圖2 中為部分原始數(shù)據(jù)集所對應(yīng)的聚類類別，最后一列表示的是每一行樣本所屬類別，類別類型用0，1，2 代替.圖3 為經(jīng)過聚類運算之后的聚類中心.

圖2 聚類類別Fig.2 Clustering categories

圖3 聚類中心Fig.3 Cluster centroids

圖4 聚類結(jié)果Fig.4 Clustering Results

確定聚類中心后，本文分別計算了KNN，K-Means 聚類中心算法與K-Means_w 算法下的RMSE 值，圖中藍色曲線是基于KNN 計算得到的RMSE 值，由圖中可知，隨著KNN 中k 值得變大，RMSE 值不斷增大，這是因為原數(shù)據(jù)集有很強的稀疏性，KNN 的計算速度雖然很快，但是在樣本數(shù)量很大的情況下，計算速度相對變慢，KNN 對于大多數(shù)特征下取值都為0 的數(shù)據(jù)集(稀疏數(shù)據(jù)集)來說，KNN 算法的效果并不好，所以隨著KNN 中k 值得增大，RMSE 值反而增大.

圖中黃色曲線是利用K-Means 聚類中心算法計算得到的RMSE 值，由圖可知，確定聚類中心為2 的情況下，隨著最近鄰個數(shù)的增加，RMSE 值減少，隨著k 值得增大，曲線將逐漸達到收斂，因為K-Means 選取的聚類中心解決了KNN 所面對的數(shù)據(jù)稀疏性問題，聚類中心是經(jīng)過不斷迭代之后所產(chǎn)生的，利用中心代替目標用戶取計算最近鄰，有效地解決了數(shù)據(jù)稀疏性所造成的問題.

圖中紅色曲線是加權(quán)后的K-Means 聚類中心算法RMSE 值，從圖中可以明確地看到加權(quán)之后的算法有效地提高了算法的效率，降低了RMSE 值，加權(quán)之后的K-Means 算法考慮到的是目標用戶如果是聚類中心的最近鄰，就不需要重復(fù)計算目標用戶對評分值得影響，如果目標用戶不在聚類中心的最近鄰用戶集合中，應(yīng)該添加目標用戶與聚類中心的評分值對預(yù)測評分值得影響.

通過圖中的對比，可知改進后的算法RMSE 值是最好的.表4 中給出了三個算法下不同K 值所對應(yīng)的RMSE 值，用這個數(shù)據(jù)可以模擬上圖，從表中也可以直觀的對比得出，RMSE 在K-Means_w 算法下的結(jié)果是非?？捎^的.

圖5 RMSE 值對比圖Fig.5 RMSE comparison

表4 算法實驗結(jié)果(RMSE)Tab.4 Experimental Results(RMSE)

4 結(jié)論

本文提出的K-Means 聚類中心最近鄰?fù)扑]算法，通過將KNN 算法與K-Means 算法相結(jié)合，在對未知評分項預(yù)測時，同時考慮被預(yù)測的目標用戶與其聚類中心對評分預(yù)測值的影響，降低了稀疏性問題對KNN 算法的影響，同時提高了算法精確度，使得推薦結(jié)果合理性更高.實驗結(jié)果證明，本文提出的算法對比KNN 算法得到更準確的推薦結(jié)果.在以后的工作中，會繼續(xù)針對稀疏性問題進行深入研究.