吳金李+張建明

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

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

DOIDOI：10.11907/rjdk.162275

中圖分類號：TP312文獻標識碼：A文章編號文章編號：16727800（2017）001002603

引言

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

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

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

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

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

協(xié)同過濾算法包括兩種思想，基于用戶協(xié)同過濾和基于項目的推薦算法。基于用戶協(xié)同過濾算法的基本思想：①找到和目標用戶興趣相似的用戶集合；②找到該集合中用戶喜歡的，且目標用戶沒有聽說過的物品推薦給目標用戶[8]，如圖1所示。

圖1基于用戶推薦

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

其中Ri、Rj表示用戶評分均值，Rik、Rjk表示用戶對k項目的評分。

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

圖2基于物品推薦

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

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

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

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

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

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

ci=1mi∑x∈Cix（3）

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

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

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

其中，Pu，i表示用戶u對項目i的評分，Ru表示用戶評分均值，Rj，i表示j用戶對i項目的評分，Rj表示j用戶評分均值。

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

Step1：將用戶評分數(shù)據(jù)分為訓練集和測試集，將兩類數(shù)據(jù)分別存入二維數(shù)組中。

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

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

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

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

3實驗結(jié)果及分析

實驗數(shù)據(jù)是MovieLens數(shù)據(jù)集中小規(guī)模的庫，包括943位獨立用戶對1 682部電影的100 000次評分數(shù)據(jù)。用戶對已看過的電影評分，評分范圍為1～5。實驗采用Java開發(fā)平臺，根據(jù)用戶評分生預測評分矩陣從而形成推薦。

評價推薦系統(tǒng)推薦質(zhì)量的度量標準采用平均絕對誤差MAE進行度量。通過計算預測評分和實際評分的MAE值來判斷推薦效果。當MAE值越小時，推薦的質(zhì)量越高，反之推薦的質(zhì)量越低。MAE公式如式（5）所示，其中pi表示系統(tǒng)對用戶的預測評分，qi表示用戶的實際評分。

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

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

4結(jié)語

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

參考文獻：

[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.