基于NKL和K-means聚類的協(xié)同過(guò)濾推薦算法

李順勇， 張鈺嘉， 張海玉

（1.山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院，太原 030006； 2.山西大學(xué)新聞學(xué)院，太原 030006）

協(xié)同過(guò)濾（Collaborative Filtering）是一種有效的推薦技術(shù)，該技術(shù)通過(guò)找出與被推薦用戶喜好相近的一組用戶，然后把該組用戶喜好的項(xiàng)目推薦給被推薦用戶. 協(xié)同過(guò)濾技術(shù)由于其推薦資源廣、算法較為簡(jiǎn)單、易于實(shí)現(xiàn)等優(yōu)勢(shì)，在電子商務(wù)、客戶研究、廣告投遞等方面有著較為廣泛的應(yīng)用［1-2］.

1 NKL-KM算法

基于上述分析，本文提出了一種基于NKL 和K-means 聚類的協(xié)同過(guò)濾推薦算法（NKL-KM），該算法分為三個(gè)步驟：首先，基于NKL度量法計(jì)算item之間的相似性；其次，根據(jù)K-means算法將item分成k個(gè)類；最后，得到Top-n列表.

1.1 NKL相似性度量法

③KLSim(i,j)沒(méi)有考慮到具體評(píng)分值對(duì)計(jì)算相似性度量時(shí)的影響，評(píng)1分和5分用戶所表達(dá)的感情是截然不同的. 因此，本文在式（1）的基礎(chǔ)上，引入?yún)?shù)λ、α、β 得到式（2），計(jì)算式為

式（2）有以下屬性：

1.2 K-means算法［15］

為提高推薦算法精度，本文將K-means算法與CF算法相結(jié)合，基于1.1提出的NKL相似性度量法，提出了一種基于NKL和K-means聚類的協(xié)同過(guò)濾推薦算法.

定義1［15］數(shù)據(jù)的分類標(biāo)準(zhǔn)為：

K-means算法具體過(guò)程見(jiàn)算法1.

算法1［15］K-means算法

Step4 重復(fù)Step2～Step3至簇中心不再變化為止.

得到C={ }C1,C2,C3,…,Ck后，就可以對(duì)目標(biāo)項(xiàng)目進(jìn)行項(xiàng)目評(píng)分預(yù)測(cè)，預(yù)測(cè)具體步驟如1.3所示.

1.3 項(xiàng)目評(píng)分預(yù)測(cè)

綜上，一種基于NKL和K-means聚類的協(xié)同過(guò)濾推薦算法具體步驟如算法2所示.

算法2 NKL-KM算法

輸出：Top-n推薦列表.

Step4 重復(fù)Step2～Step3至簇中心不再變化為止；

Step6 根據(jù)式（5）計(jì)算用戶u對(duì)i的評(píng)分，挑選出預(yù)測(cè)分?jǐn)?shù)最高的n個(gè)項(xiàng)目組成Top-n推薦列表.

2 仿真實(shí)驗(yàn)

2.1 數(shù)據(jù)集的選擇

本文選取MovieLens［16］和Netflix數(shù)據(jù)集［17］中的部分?jǐn)?shù)據(jù)，構(gòu)成了NewML以及NewNet，數(shù)據(jù)集的具體信息如表1所示. 從表1可以看出，NewML數(shù)據(jù)集的稀疏度較低，處理難度較大. 在本文中，隨機(jī)選取NewML以及NewNet中80%的數(shù)據(jù)作為訓(xùn)練集，剩余的作為測(cè)試集.

表1 數(shù)據(jù)集信息Tab.1 Data set information

2.2 評(píng)價(jià)標(biāo)準(zhǔn)

在推薦系統(tǒng)中，最常用的檢驗(yàn)推薦算法性能的指標(biāo)是Mean Absolute Error（MAE）以及Root Mean Squared Error（RMSE）. MAE和RMSE的值越小，說(shuō)明預(yù)測(cè)準(zhǔn)確率越高. MAE和RMSE計(jì)算公式如下所示：

式（6）、（7）中：q表示測(cè)試集數(shù)據(jù)數(shù)；ri表示用戶的實(shí)際評(píng)分；pi表示根據(jù)式（5）得到的預(yù)測(cè)評(píng)分.

2.3 算法比較

2.3.1 NewML數(shù)據(jù)集算法對(duì)比 本節(jié)在NewML上對(duì)NKL-KM算法性能進(jìn)行測(cè)試，首先確定合適的聚類簇?cái)?shù)，確定好合適的cluster 數(shù)后，再將本文算法與NHSM（new heuristic similarity model）、JMSD（combining Jaccard and MSD）、BCF（Bhattacharyya Coefficient based CF）算法進(jìn)行對(duì)比. 不同聚類簇?cái)?shù)對(duì)比結(jié)果如圖1所示.

圖1 NewML數(shù)據(jù)集上不同聚類簇?cái)?shù)對(duì)比Fig.1 Comparison of the number of different cluster clusters on NewML dataset

從圖1可以看出，根據(jù)本文算法得到的MAE值和RMSE值在cluster數(shù)為8時(shí)達(dá)到了最小值，故在NewML數(shù)據(jù)集上將聚類簇?cái)?shù)定為8.

確定好cluster 后，在NewML 數(shù)據(jù)集上將NKL-KM 算法與NHSM（new heuristic similarity model）、JMSD（combining Jaccard and MSD）、BCF（Bhattacharyya Coefficient based CF）算法在不同最近鄰數(shù)下進(jìn)行對(duì)比，對(duì)比結(jié)果如圖2所示.

圖2 NewML數(shù)據(jù)集上不同算法對(duì)比Fig.2 Comparison of different algorithms on NewML dataset

從圖2可知，在不同最近鄰數(shù)下本文提出的NKL-KM 算法性能優(yōu)于JMSD、BCF 以及NHSM 算法. 除此之外，BCF 算法在NewML 上性能優(yōu)于JMSD、NHSM 算法，而NHSM 算法性能又優(yōu)于JMSD. 與此同時(shí)，由于NKL-KM算法在進(jìn)行距離度量時(shí)考慮到項(xiàng)目之間評(píng)分的概率分布以及分值差異，所以圖中NKL-KM算法的MAE和RMSE的折線最為平緩，算法性能也最為穩(wěn)定.

2.3.2 NewNet數(shù)據(jù)集算法對(duì)比 本節(jié)在NewNet上對(duì)NKL-KM算法性能進(jìn)行測(cè)試，確定NKL-KM算法合適的cluster數(shù)，并將本文提出的NKL-KM算法與NHSM（new heuristic similarity model）、JMSD（combining Jaccard and MSD）、BCF（Bhattacharyya Coefficient based CF）算法進(jìn)行對(duì)比. NKL-KM算法在不同簇?cái)?shù)時(shí)的對(duì)比結(jié)果如圖3所示.

圖3 NewNet數(shù)據(jù)集上不同聚類簇?cái)?shù)對(duì)比Fig.3 Comparison of the number of different clusters on NewNet dataset

由圖3可知，根據(jù)NKL-KM得到的MAE值和RMSE值在cluster數(shù)為17時(shí)達(dá)到了最小值，故在NewNet數(shù)據(jù)集上將cluster定為17.

令cluster=17，在NewNet 數(shù)據(jù)集上將NKL-KM 算法與NHSM、JMSD、BCF算法在不同最近鄰數(shù)下進(jìn)行對(duì)比，對(duì)比結(jié)果如圖4所示.

圖4 NewNet數(shù)據(jù)集上不同算法對(duì)比Fig.4 Comparison of different algorithms on NewNet dataset

由圖4可知，不同最近鄰數(shù)下，NKL-KM算法的MAE值和RMSE值均是最低，JMSD算法性能最差. 除此之外，由于NKL-KM算法在進(jìn)行距離度量時(shí)考慮到項(xiàng)目之間評(píng)分的概率分布以及分值差異，故NKL-KM算法較為穩(wěn)定.

3 結(jié)語(yǔ)