李順勇, 張鈺嘉, 張海玉
(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].
基于上述分析,本文提出了一種基于NKL 和K-means 聚類的協(xié)同過(guò)濾推薦算法(NKL-KM),該算法分為三個(gè)步驟:首先,基于NKL度量法計(jì)算item之間的相似性;其次,根據(jù)K-means算法將item分成k個(gè)類;最后,得到Top-n列表.
③KLSim(i,j)沒(méi)有考慮到具體評(píng)分值對(duì)計(jì)算相似性度量時(shí)的影響,評(píng)1分和5分用戶所表達(dá)的感情是截然不同的. 因此,本文在式(1)的基礎(chǔ)上,引入?yún)?shù)λ、α、β 得到式(2),計(jì)算式為
式(2)有以下屬性:
為提高推薦算法精度,本文將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所示.
綜上,一種基于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推薦列表.
本文選取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
在推薦系統(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.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)定.