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

郝雅嫻

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

0 引言

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

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

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

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

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

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

1 預(yù)備知識

1.1 K-Means 算法

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

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

K-Means 算法:

1.2 基于用戶的最近鄰算法

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

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

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

KNN 算法

2 算法實(shí)現(xiàn)

2.1 算法步驟

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

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

2.2 算法實(shí)例分析

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

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

表2 聚類中心Tab.2 Cluster centroids

表3 聚類類別Tab.3 Clustering Categories

隨機(jī)選取2 個(gè)聚類中心:Id =1，2，選擇用戶1與用戶2 作為聚類中心;

計(jì)算樣本與聚類中心間的距離，這里采用歐式距離，經(jīng)過計(jì)算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;因?yàn)镾(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 類，其余用戶屬于第一類，那么，接下來進(jìn)行最近鄰計(jì)算，如果求用戶1 對M_3 的評分，則將用戶1 所屬聚類類別0 的聚類中心代替用戶1 尋找最近鄰，同樣進(jìn)行相似度計(jì)算.

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

3 實(shí)驗(yàn)結(jié)果分析

3.1 Movielens 數(shù)據(jù)集與評價(jià)指標(biāo)

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

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

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

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

圖1 MovieLens Fig.1 MovieLens

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

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

圖2 聚類類別Fig.2 Clustering categories

圖3 聚類中心Fig.3 Cluster centroids

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

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

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

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

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

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

表4 算法實(shí)驗(yàn)結(jié)果(RMSE)Tab.4 Experimental Results(RMSE)

4 結(jié)論

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