基于二分Kmeans的協(xié)同過(guò)濾推薦算法

吳金李+張建明

摘要摘要：針對(duì)傳統(tǒng)協(xié)同過(guò)濾推薦算法中存在的數(shù)據(jù)稀疏性問(wèn)題，提出了一種基于二分Kmeans的協(xié)同過(guò)濾推薦算法。該算法在Kmeans算法的基礎(chǔ)上，為了降低初始質(zhì)點(diǎn)選擇對(duì)聚類結(jié)果的影響，在運(yùn)行中逐個(gè)添加質(zhì)點(diǎn)。首先初始化評(píng)分?jǐn)?shù)據(jù)并將其作為初始簇，然后選擇合適的簇隨機(jī)產(chǎn)生兩個(gè)質(zhì)點(diǎn)將簇分裂為兩個(gè)簇，重復(fù)上述步驟，直到聚類完成。最后為了降低不同用戶評(píng)分標(biāo)準(zhǔn)差異，將用戶評(píng)分的平均值和用戶同簇內(nèi)相互間的相似度相結(jié)合，計(jì)算預(yù)測(cè)評(píng)分矩陣，生成推薦結(jié)果。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法較好地解決了數(shù)據(jù)稀疏問(wèn)題，提高了推薦質(zhì)量。

關(guān)鍵詞關(guān)鍵詞：Kmeans算法；二分Kmeans；協(xié)同過(guò)濾；推薦算法

DOIDOI：10.11907/rjdk.162275

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）001002603

引言

隨著網(wǎng)絡(luò)的發(fā)展，互聯(lián)網(wǎng)上的信息量飛速增長(zhǎng)，推薦系統(tǒng)根據(jù)這些用戶行為信息，挖掘?qū)τ脩粲杏玫男畔?duì)用戶進(jìn)行個(gè)性化推薦。隨著個(gè)性化推薦系統(tǒng)的發(fā)展，協(xié)同過(guò)濾算法成為目前使用最廣泛的推薦系統(tǒng)基礎(chǔ)算法[12]。其基本思想是找到與目標(biāo)對(duì)象最相似的對(duì)象生成推薦結(jié)果[34]。

Goldberg等[5]最早提出協(xié)同過(guò)濾思想，后來(lái)明尼蘇達(dá)大學(xué)在實(shí)際網(wǎng)站建設(shè)時(shí)又提出基于用戶和基于項(xiàng)目的協(xié)同過(guò)濾推薦系統(tǒng)，形成傳統(tǒng)的協(xié)同過(guò)濾推薦算法。在實(shí)際應(yīng)用中隨著用戶數(shù)和項(xiàng)目數(shù)的增加，系統(tǒng)需要計(jì)算的數(shù)據(jù)量也相應(yīng)增加，同時(shí)用于計(jì)算的用戶項(xiàng)目評(píng)分矩陣數(shù)據(jù)變得更稀疏，這些都對(duì)推薦系統(tǒng)的性能產(chǎn)生影響。因此Sarwar等[6]利用Kmeans算法對(duì)用戶進(jìn)行聚類，縮小最近鄰的搜索范圍，改善可擴(kuò)展性問(wèn)題。Herlocker J等[7]對(duì)項(xiàng)目進(jìn)行聚類，縮小了目標(biāo)項(xiàng)目的最近鄰搜索范圍，有效減少了運(yùn)算數(shù)據(jù)量。Tsai CF等[8]在理論和實(shí)驗(yàn)上闡明，基于SOM和Kmeans聚類方法可以作為協(xié)同過(guò)濾算法的基準(zhǔn)，提高了推薦系統(tǒng)的精度。

針對(duì)網(wǎng)絡(luò)數(shù)據(jù)量大、信息種類復(fù)雜等問(wèn)題，在協(xié)同過(guò)濾推薦算法的基礎(chǔ)上采用大數(shù)據(jù)處理中的Kmeans算法，可以有效地將數(shù)據(jù)進(jìn)行分類，但初始質(zhì)點(diǎn)的選擇對(duì)Kmeans算法聚類的結(jié)果影響較大。為解決初始質(zhì)點(diǎn)選擇問(wèn)題，本文提出改進(jìn)二分Kmeans方法，動(dòng)態(tài)地為數(shù)據(jù)集添加質(zhì)點(diǎn)，經(jīng)迭代計(jì)算出所有質(zhì)點(diǎn)，降低初始質(zhì)點(diǎn)選擇帶來(lái)的誤差，并且添加邊界值處理。計(jì)算預(yù)測(cè)評(píng)分時(shí)針對(duì)用戶的評(píng)分標(biāo)準(zhǔn)不同，采用平均值法降低其所帶來(lái)的影響，結(jié)合對(duì)象之間的相似度對(duì)預(yù)測(cè)評(píng)分方法加以改進(jìn)。實(shí)驗(yàn)結(jié)果表明，本實(shí)驗(yàn)方案效果更好。

1基于Kmeans的協(xié)同過(guò)濾推薦算法

1.1傳統(tǒng)協(xié)同過(guò)濾推薦算法

協(xié)同過(guò)濾算法包括兩種思想，基于用戶協(xié)同過(guò)濾和基于項(xiàng)目的推薦算法?；谟脩魠f(xié)同過(guò)濾算法的基本思想：①找到和目標(biāo)用戶興趣相似的用戶集合；②找到該集合中用戶喜歡的，且目標(biāo)用戶沒(méi)有聽(tīng)說(shuō)過(guò)的物品推薦給目標(biāo)用戶[8]，如圖1所示。

圖1基于用戶推薦

首先收集并處理所有用戶信息，然后將目標(biāo)用戶的信息與用戶信息集合中的信息作相似計(jì)算得出相似用戶集合。其中關(guān)鍵是計(jì)算用戶間的相似度，通過(guò)第一步數(shù)據(jù)的處理，用戶信息已經(jīng)轉(zhuǎn)化為空間向量信息，計(jì)算空間向量的相似性有效方法，即皮爾森相關(guān)系數(shù)（PCC）[9]相對(duì)于其它方法而言較為準(zhǔn)確，例如相對(duì)于余弦相似性計(jì)算，PCC對(duì)向量作去中心和歸一化處理，降低了不同用戶評(píng)分標(biāo)準(zhǔn)不同所產(chǎn)生的影響，皮爾森相關(guān)系數(shù)如式（1）所示。最后根據(jù)用戶相似矩陣計(jì)算目標(biāo)用戶未接觸的商品的預(yù)測(cè)評(píng)分產(chǎn)生推薦結(jié)果，對(duì)用戶進(jìn)行推薦。

其中Ri、Rj表示用戶評(píng)分均值，Rik、Rjk表示用戶對(duì)k項(xiàng)目的評(píng)分。

基于物品協(xié)同過(guò)濾算法基本思想：①計(jì)算物品之間的相似度；②根據(jù)物品的相似度和用戶的歷史行為生成推薦列表[10]，如圖2所示。與基于用戶協(xié)同過(guò)濾類似，基于物品協(xié)同過(guò)濾算法首先計(jì)算出物品之前的相似度，再根據(jù)目標(biāo)用戶的歷史信息，計(jì)算預(yù)測(cè)與之相似的物品，最后對(duì)目標(biāo)用戶形成推薦。

圖2基于物品推薦

隨著網(wǎng)絡(luò)用戶數(shù)目的增加，計(jì)算用戶相似性的難度加大，運(yùn)算時(shí)間復(fù)雜度和空間復(fù)雜度的增長(zhǎng)和用戶數(shù)的增長(zhǎng)近似于平方關(guān)系。因此，著名的電子商務(wù)公司亞馬遜提出了基于物品的協(xié)同過(guò)濾算法[11]。由此可以看出，基于用戶推薦算法注重找到與用戶相似的用戶集合中的熱點(diǎn)，而基于物品推薦算法則注重用戶的歷史信息，更傾向于個(gè)性化推薦。1.2基于Kmeans的協(xié)同過(guò)濾推薦算法

在計(jì)算對(duì)象間的相似度時(shí)，傳統(tǒng)推薦算法首先計(jì)算出每?jī)晌挥脩舻南嗨贫?，?dāng)對(duì)象的數(shù)據(jù)量達(dá)到一定程度時(shí)，相似度計(jì)算量將會(huì)非常大。因此，為了降低數(shù)據(jù)計(jì)算量，采用大數(shù)據(jù)中用于數(shù)據(jù)分類的Kmeans聚類方法。算法首先根據(jù)數(shù)據(jù)大小確定k個(gè)質(zhì)點(diǎn)做初始質(zhì)心，計(jì)算數(shù)據(jù)集中所有數(shù)據(jù)距離最近的質(zhì)點(diǎn)，將數(shù)據(jù)指派到該質(zhì)點(diǎn)所在的簇中。然后根據(jù)指派到簇的點(diǎn)，更新每個(gè)質(zhì)心。重復(fù)以上步驟，直到質(zhì)心不再變化，數(shù)據(jù)被指派到不同的簇[1013]。

為了計(jì)算目標(biāo)用戶的相似用戶，首先計(jì)算目標(biāo)用戶和每個(gè)簇內(nèi)質(zhì)心的相似性，計(jì)算出目標(biāo)用戶所屬簇。再計(jì)算出目標(biāo)用戶和簇內(nèi)用戶的相似性，得出目標(biāo)用戶相似用戶集合。最后對(duì)目標(biāo)用戶未接觸的物品預(yù)測(cè)評(píng)分后生成推薦。

2基于二分Kmeans的協(xié)同過(guò)濾推薦算法

Kmeans算法最重要的是質(zhì)心的選擇，質(zhì)心的選擇可以根據(jù)數(shù)據(jù)集中數(shù)據(jù)的范圍，隨機(jī)生成指定個(gè)數(shù)的質(zhì)心。當(dāng)簇的數(shù)量比較大時(shí)，比較容易出現(xiàn)質(zhì)點(diǎn)在簇中分布不均，即可能出現(xiàn)有些簇中質(zhì)點(diǎn)個(gè)數(shù)相當(dāng)少的情況，此時(shí)這些初始質(zhì)心到其它質(zhì)心的距離較大[12]。當(dāng)質(zhì)心相對(duì)距離較遠(yuǎn)時(shí)，Kmeans算法不能很好地在簇與簇之間重新計(jì)算分布質(zhì)點(diǎn)，因而聚類結(jié)果不佳。為了改善Kmeans聚類方法初始質(zhì)心選擇所帶來(lái)的影響，采用二分Kmeans算法。二分Kmeans算法思想是為了得到k個(gè)簇，將所有點(diǎn)的集合分裂成兩個(gè)簇，再根據(jù)SSE值從這些簇中選取一個(gè)最大的繼續(xù)分裂，直到產(chǎn)生k個(gè)簇。其中SSE表示javascript：；用數(shù)據(jù)集中每個(gè)數(shù)據(jù)和其質(zhì)心的歐幾里得距離計(jì)算誤差平方，然后求得所有誤差和。SSE公式如式（2）所示[13]。

其中，ci表示質(zhì)心坐標(biāo)，x表示質(zhì)心為ci的數(shù)據(jù)。dist表示空間兩個(gè)向量的歐幾里得距離。每次選定最小的SSE后，重新計(jì)算每個(gè)簇的質(zhì)心，采用均值法來(lái)計(jì)算。第i個(gè)簇的質(zhì)心由式（3）定義。

ci=1mi∑x∈Cix（3）

一般二分Kmeans算法在選取對(duì)哪一簇分類有多種方法時(shí)，可以選擇SSE結(jié)果最大簇或者基于一個(gè)標(biāo)準(zhǔn)SSE值來(lái)選擇，并且不考慮邊界情況。本文在選取分類簇上按照簇的編號(hào)，依次選取。如果在已有的簇中找不到分類后更小的SSE值，并且質(zhì)心個(gè)數(shù)小于k，則停止循環(huán)，輸出現(xiàn)有質(zhì)心坐標(biāo)和分類結(jié)果。具體流程如圖3所示。首先初始化數(shù)據(jù)，然后判斷質(zhì)心個(gè)數(shù)是否小于k值，若成立則循環(huán)計(jì)算分類前SSE1值和分類后SSE2值直到SSE2

對(duì)每個(gè)簇中所有用戶的數(shù)據(jù)根據(jù)皮爾森相關(guān)系數(shù)[14]計(jì)算同一簇內(nèi)每?jī)蓚€(gè)用戶間的相似性，然后對(duì)用戶未評(píng)分的部分預(yù)測(cè)評(píng)分。根據(jù)相似性，由于每個(gè)用戶評(píng)分標(biāo)準(zhǔn)不同，在計(jì)算評(píng)分時(shí)消除個(gè)人評(píng)分對(duì)目標(biāo)評(píng)分結(jié)果的影響。具體實(shí)現(xiàn)如式（4）所示。

pu，i=Ru+∑j∈Misim（u，j）×（Rj，i-Rj）∑j∈Mi（|sim（u，j）|）（4）

其中，Pu，i表示用戶u對(duì)項(xiàng)目i的評(píng)分，Ru表示用戶評(píng)分均值，Rj，i表示j用戶對(duì)i項(xiàng)目的評(píng)分，Rj表示j用戶評(píng)分均值。

基于二分Kmeans推薦算法首先對(duì)初始數(shù)據(jù)聚類，然后計(jì)算每個(gè)簇中用戶相似性，最后對(duì)用戶評(píng)分矩陣進(jìn)行評(píng)分預(yù)測(cè)后，找出預(yù)測(cè)評(píng)分最高的前N個(gè)物品形成推薦[15]。具體實(shí)現(xiàn)步驟如圖4所示。

Step1：將用戶評(píng)分?jǐn)?shù)據(jù)分為訓(xùn)練集和測(cè)試集，將兩類數(shù)據(jù)分別存入二維數(shù)組中。

Step2：設(shè)置分類數(shù)量k。

Step3：將訓(xùn)練集數(shù)據(jù)帶入圖3流程圖進(jìn)行計(jì)算，得到k個(gè)質(zhì)心坐標(biāo)，并為數(shù)組存放每位用戶所屬的簇。

Step4：根據(jù)式（1）計(jì)算k個(gè)簇內(nèi)每位用戶在其對(duì)應(yīng)的簇內(nèi)與同簇內(nèi)每位用戶的相似性，求出k個(gè)相似矩陣表。

Step5：將相似矩陣表和初始數(shù)據(jù)表中數(shù)據(jù)帶入式（4）得到預(yù)測(cè)評(píng)分，根據(jù)topN得到推薦。

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

實(shí)驗(yàn)數(shù)據(jù)是MovieLens數(shù)據(jù)集中小規(guī)模的庫(kù)，包括943位獨(dú)立用戶對(duì)1 682部電影的100 000次評(píng)分?jǐn)?shù)據(jù)。用戶對(duì)已看過(guò)的電影評(píng)分，評(píng)分范圍為1～5。實(shí)驗(yàn)采用Java開(kāi)發(fā)平臺(tái)，根據(jù)用戶評(píng)分生預(yù)測(cè)評(píng)分矩陣從而形成推薦。

評(píng)價(jià)推薦系統(tǒng)推薦質(zhì)量的度量標(biāo)準(zhǔn)采用平均絕對(duì)誤差MAE進(jìn)行度量。通過(guò)計(jì)算預(yù)測(cè)評(píng)分和實(shí)際評(píng)分的MAE值來(lái)判斷推薦效果。當(dāng)MAE值越小時(shí)，推薦的質(zhì)量越高，反之推薦的質(zhì)量越低。MAE公式如式（5）所示，其中pi表示系統(tǒng)對(duì)用戶的預(yù)測(cè)評(píng)分，qi表示用戶的實(shí)際評(píng)分。

MAE=∑Ni=1|pi-qi|N（5）

本文對(duì)Kmeans協(xié)同過(guò)濾和二分Kmeans協(xié)同過(guò)濾算法在相同數(shù)據(jù)集中進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖5所示，最近鄰個(gè)數(shù)增加時(shí)MAE值減小，表示預(yù)測(cè)結(jié)果越好，基于二分Kmeans的協(xié)同過(guò)濾推薦效果優(yōu)于基于Kmeans協(xié)同過(guò)濾的推薦效果。

4結(jié)語(yǔ)

隨著互聯(lián)網(wǎng)科技的發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)蘊(yùn)含的信息將逐漸被人挖掘，推薦系統(tǒng)可以有效地處理數(shù)據(jù)，但由于網(wǎng)絡(luò)數(shù)據(jù)存在數(shù)據(jù)稀疏、數(shù)據(jù)量大等問(wèn)題，因而本文采用基于二分Kmeans的協(xié)同過(guò)濾推薦算法。該算法將相同類別的數(shù)據(jù)聚集在一起，將不同類別的數(shù)據(jù)加以分離，降低運(yùn)算量。對(duì)數(shù)據(jù)動(dòng)態(tài)地添加質(zhì)點(diǎn)，再更新數(shù)據(jù)類別，可提高數(shù)據(jù)分類效果，使得每個(gè)類別內(nèi)的數(shù)據(jù)結(jié)合更緊密，類之間的差距也相應(yīng)增加。實(shí)驗(yàn)結(jié)果表明，本文采用基于二分Kmeans的協(xié)同過(guò)濾推薦算法能夠有效提高算法性能。

參考文獻(xiàn)：

[1]LINDEN G，SMITH B，YORK J.Amazon.com recommendations：itemtoitem collaborative filtering[J].IEEE Internet Computing，2003，7（1）：7680.

[2]CHUNG K Y，LEE D，KIM K J.Categorization for grouping associative items using data mining in itembased collaborative filtering[J]. Multimedia Tools & Applications，2014，71（2）：889904.