基于Weighted-slope One的用戶聚類(lèi)推薦算法研究

鄭 丹，王名揚(yáng)，陳廣勝

(東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，黑龍江 哈爾濱 150040)

基于Weighted-slope One的用戶聚類(lèi)推薦算法研究

鄭 丹，王名揚(yáng)，陳廣勝

(東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，黑龍江 哈爾濱 150040)

針對(duì)傳統(tǒng)協(xié)同過(guò)濾推薦算法存在的數(shù)據(jù)稀疏性以及實(shí)時(shí)性差的問(wèn)題，提出一種基于Weighted-slope One的用戶聚類(lèi)推薦算法。該算法首先利用Weighted-slope One算法的思想對(duì)初始的用戶-評(píng)分矩陣進(jìn)行有效填充，降低數(shù)據(jù)的稀疏性；然后，結(jié)合初始聚類(lèi)中心優(yōu)化改進(jìn)的K-means方法對(duì)用戶進(jìn)行聚類(lèi)，生成相似用戶集合，以縮小目標(biāo)用戶搜索最近鄰的范圍；最后，結(jié)合目標(biāo)用戶所屬的聚類(lèi)，利用基于用戶的協(xié)同過(guò)濾算法搜索最近鄰居，為目標(biāo)用戶推薦對(duì)應(yīng)的產(chǎn)品。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法可以顯著降低數(shù)據(jù)的稀疏度，同時(shí)提升推薦的準(zhǔn)確性和實(shí)時(shí)性。

協(xié)同過(guò)濾；高維稀疏矩陣；Weighted-slopeOne；K-means；聚類(lèi)中心

1 概 述

隨著信息網(wǎng)絡(luò)的不斷發(fā)展，令人眼花繚亂的商品、繁雜且真假難辨的信息都在急劇增長(zhǎng)。對(duì)于用戶來(lái)說(shuō)，想要在這些信息中快速發(fā)現(xiàn)、收集和維護(hù)自己所需的信息記錄需要花費(fèi)大量的時(shí)間和精力，這就是“信息超載”現(xiàn)象。在電子商務(wù)領(lǐng)域，通過(guò)合理地整合信息對(duì)用戶實(shí)現(xiàn)個(gè)性化推薦是解決信息超載問(wèn)題的一種有效方案。個(gè)性化推薦作為一種依靠用戶購(gòu)買(mǎi)記錄、用戶偏好等為基礎(chǔ)來(lái)實(shí)現(xiàn)推薦目標(biāo)產(chǎn)品推薦的算法，在電子商務(wù)領(lǐng)域有著廣泛的應(yīng)用。在目前的電子商務(wù)推薦系統(tǒng)中，協(xié)同過(guò)濾是使用最廣泛、最成功的推薦算法。它通過(guò)構(gòu)建用戶-項(xiàng)目的評(píng)分矩陣，搜索與目標(biāo)用戶具有相似偏好的鄰居用戶，根據(jù)鄰居用戶對(duì)某項(xiàng)目的評(píng)分值來(lái)預(yù)測(cè)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分值，從而產(chǎn)生推薦結(jié)果[1]。

盡管協(xié)同過(guò)濾算法在商品的個(gè)性化推薦當(dāng)中取得了巨大的成功，但是，近年來(lái)隨著電子商務(wù)平臺(tái)上用戶以及產(chǎn)品數(shù)量的不斷增長(zhǎng)，數(shù)據(jù)稀疏性成為限制傳統(tǒng)協(xié)同過(guò)濾算法應(yīng)用的瓶頸，并由此帶來(lái)了推薦精度低、實(shí)時(shí)性差和冷啟動(dòng)等問(wèn)題[2]。由于用戶評(píng)分的項(xiàng)目相對(duì)于所有項(xiàng)目來(lái)說(shuō)只占到很小的一部分，所以當(dāng)用戶的評(píng)分項(xiàng)目之間沒(méi)有交集的時(shí)候，很難判斷兩個(gè)用戶之間是否具有相似偏好，從而導(dǎo)致推薦精度的下降。同時(shí)，用戶、產(chǎn)品數(shù)量的激增是用戶-項(xiàng)目評(píng)分矩陣過(guò)大，使搜索目標(biāo)用戶的最近鄰居范圍變大，推薦實(shí)時(shí)性受到嚴(yán)重影響。冷啟動(dòng)問(wèn)題是針對(duì)“小白”用戶來(lái)說(shuō)的?！靶“住庇脩糁傅氖莿傔M(jìn)入電子商務(wù)平臺(tái)的用戶，沒(méi)有任何的評(píng)價(jià)和購(gòu)買(mǎi)記錄，無(wú)法去度量他與其他用戶的相似度。冷啟動(dòng)問(wèn)題實(shí)際上是數(shù)據(jù)稀疏性的一個(gè)極端表現(xiàn)[3]。究其本質(zhì)，形成這兩個(gè)問(wèn)題的主要原因還是數(shù)據(jù)稀疏性問(wèn)題，因此，有必要對(duì)數(shù)據(jù)稀疏性進(jìn)行深入研究。

近年來(lái)，針對(duì)數(shù)據(jù)稀疏性帶來(lái)的問(wèn)題，為了提升推薦效果，學(xué)者們將主成分分析、聚類(lèi)分析、奇異值分解等算法引入到傳統(tǒng)的協(xié)同過(guò)濾推薦算法中，通過(guò)降維，縮小目標(biāo)用戶搜索最近鄰居的范圍，使得推薦的精度和實(shí)時(shí)性有了明顯提升。文獻(xiàn)[4]提出使用主成分分析對(duì)維數(shù)進(jìn)行約減，然后使用傳統(tǒng)的K-means聚類(lèi)技術(shù)對(duì)用戶進(jìn)行聚類(lèi)，生成用戶簇類(lèi)，以縮小目標(biāo)用戶搜索最近鄰居的范圍，有效緩解了數(shù)據(jù)稀疏性，提升了推薦質(zhì)量。文獻(xiàn)[5]提出使用奇異值分解算法對(duì)用戶-項(xiàng)目的評(píng)分矩陣進(jìn)行處理，然后使用協(xié)同過(guò)濾算法對(duì)目標(biāo)用戶產(chǎn)生推薦，有效緩解了數(shù)據(jù)稀疏性的問(wèn)題，同時(shí)推薦精度也得到了提升。文獻(xiàn)[6]提出了一種基于項(xiàng)目聚類(lèi)的協(xié)同過(guò)濾算法，通過(guò)對(duì)各項(xiàng)目進(jìn)行聚類(lèi)，在與目標(biāo)項(xiàng)目最相似的若干個(gè)類(lèi)中搜索最近鄰居產(chǎn)生推薦列表。但是，直接使用主成分分析、SVD奇異值分解、聚類(lèi)分析等來(lái)對(duì)原始的用戶-評(píng)分矩陣進(jìn)行處理的能力是有限的。因?yàn)?，?dāng)用戶-評(píng)分矩陣數(shù)據(jù)的稀疏程度很大時(shí)，這些方法在第一步進(jìn)行處理時(shí)的效果就不太理想。

基于以上啟發(fā)，文中提出一種基于Weighted-slopeOne的用戶聚類(lèi)推薦算法。首先借鑒Weighted-slopeOne算法的思想對(duì)初始的用戶-項(xiàng)目評(píng)分矩陣進(jìn)行填充，使初始的用戶-評(píng)分矩陣的稀疏性大大降低。其次，對(duì)于已經(jīng)填充的用戶-評(píng)分矩陣使用一種初始聚類(lèi)中心優(yōu)化改進(jìn)的K-means算法對(duì)用戶進(jìn)行聚類(lèi)，生成相似用戶集合。最后，使用協(xié)同過(guò)濾算法實(shí)現(xiàn)對(duì)目標(biāo)用戶的推薦。具體推薦過(guò)程為：首先判斷目標(biāo)用戶所屬的簇類(lèi)，在目標(biāo)用戶所屬的相似用戶集合內(nèi)實(shí)現(xiàn)推薦。實(shí)驗(yàn)仿真結(jié)果表明，文中所提出的方法不但有效降低了數(shù)據(jù)的稀疏性，同時(shí)由于是在目標(biāo)用戶所屬簇類(lèi)內(nèi)為其實(shí)現(xiàn)系統(tǒng)過(guò)濾推薦，因此可以有效地降低協(xié)同過(guò)濾搜索目標(biāo)用戶最近鄰居的范圍；并且由于都是目標(biāo)用戶的相似用戶，因此文中提出的算法在降低計(jì)算復(fù)雜度的同時(shí)，還能有效提升推薦系統(tǒng)的實(shí)時(shí)響應(yīng)速度。

2 基于Weighted-slope One算法降低用戶-評(píng)分矩陣的稀疏性

Slope One算法是于2005年由Daniel Lemire教授提出的一個(gè)基于項(xiàng)目的推薦算法[7]。算法以f(x)=x+b作為預(yù)測(cè)器，使用線性回歸預(yù)測(cè)用戶對(duì)未評(píng)分項(xiàng)目的打分，參數(shù)b為用戶對(duì)兩個(gè)項(xiàng)目評(píng)分的平均偏差[8]。Weighted-slopeOne是SlopeOne的一個(gè)遞進(jìn)算法，它均衡了每個(gè)評(píng)分項(xiàng)目對(duì)于目標(biāo)項(xiàng)目的影響。由于Weighted-slopeOne在預(yù)測(cè)用戶對(duì)項(xiàng)目的打分值時(shí)充分考慮了用戶共同評(píng)分的差異度以及不同項(xiàng)目被用戶同時(shí)評(píng)論的次數(shù)，因此，所得預(yù)測(cè)的評(píng)分與真實(shí)的用戶評(píng)分是比較相近的。但是，文獻(xiàn)[9]研究表明SlopeOne在用戶-項(xiàng)目評(píng)分矩陣比較密集的時(shí)候推薦的效果較好，當(dāng)數(shù)據(jù)比較稀疏時(shí)，其推薦的效果并不好。鑒于此，文中并不直接使用Weighted-slopeOne算法進(jìn)行推薦，而是借鑒Weighted-slopeOne算法的這種對(duì)目標(biāo)用戶打分思想來(lái)對(duì)初始高維的用戶-評(píng)分矩陣進(jìn)行填充，對(duì)填充后的矩陣使用初始聚類(lèi)中心優(yōu)化的K-means算法進(jìn)行聚類(lèi)，生成相似用戶集合。當(dāng)對(duì)目標(biāo)用戶進(jìn)行推薦時(shí)，首先確定目標(biāo)用戶所屬的簇類(lèi)，然后在該簇類(lèi)內(nèi)搜索目標(biāo)用戶的最近鄰居，產(chǎn)生推薦。

使用Weighted-slopeOne對(duì)用戶u的未評(píng)分項(xiàng)目進(jìn)行填充降低用戶-評(píng)分矩陣的稀疏性的過(guò)程為：首先，尋找用戶u和用戶v評(píng)分過(guò)的項(xiàng)目集合Iuv=Iu∩Iv，利用式(1)計(jì)算用戶u的未評(píng)分項(xiàng)目j對(duì)于項(xiàng)目i的偏移量devji，根據(jù)式(2)得到目標(biāo)用戶對(duì)于項(xiàng)目j的評(píng)分值。

這是經(jīng)典的SlopeOne算法計(jì)算目標(biāo)用戶對(duì)項(xiàng)目評(píng)分的方法，但是對(duì)項(xiàng)目進(jìn)行評(píng)分的用戶數(shù)量在最終的預(yù)測(cè)評(píng)分時(shí)顯然也有影響。因此，使用Weighted-slopeOne算法修正最終目標(biāo)用戶u對(duì)于項(xiàng)目的預(yù)測(cè)評(píng)分，即根據(jù)式(3)得出目標(biāo)用戶對(duì)項(xiàng)目j的最終評(píng)分。

(1)

(2)

(3)

其中：ui，uj分別表示用戶u對(duì)項(xiàng)目i和項(xiàng)目j的評(píng)分值；card(i∩j)表示項(xiàng)目i和項(xiàng)目j同時(shí)被評(píng)分過(guò)的用戶數(shù)目；R(u)表示目標(biāo)用戶u已經(jīng)評(píng)價(jià)過(guò)的項(xiàng)目的集合；D(j)表示與目標(biāo)項(xiàng)目j計(jì)算得到的平均偏移量devji的集合。

通過(guò)使用Weighted-slopeOne算法對(duì)初始的用戶-評(píng)分矩陣進(jìn)行處理，矩陣中的大部分零元素就會(huì)被填充，從而有效降低了整個(gè)矩陣的稀疏程度。

3 初始聚類(lèi)中心優(yōu)化的K-means算法

K-means算法是一種基于劃分的聚類(lèi)分析方法，由于其理理論可靠、算法實(shí)現(xiàn)簡(jiǎn)單、收斂速度快，并且又容易實(shí)現(xiàn)對(duì)大規(guī)模數(shù)據(jù)的處理，因此是應(yīng)用最廣泛的聚類(lèi)算法之一。但是由于傳統(tǒng)的聚類(lèi)算法對(duì)聚類(lèi)中心敏感，隨機(jī)地選取任意k個(gè)點(diǎn)作為初始聚類(lèi)中心，并迭代地改變中心使聚類(lèi)準(zhǔn)則收斂，經(jīng)常會(huì)導(dǎo)致算法陷入局部最優(yōu)，產(chǎn)生完全不同的聚類(lèi)結(jié)果。為了避免這種初始聚類(lèi)中心隨機(jī)選取帶來(lái)的聚類(lèi)結(jié)果不穩(wěn)定性，學(xué)者們將數(shù)據(jù)分布的稠密程度作為指標(biāo)引入到初始聚類(lèi)中心的選取上，希望所選取的初始聚類(lèi)中心能夠在一定程度上代表數(shù)據(jù)本身的分布情況。

文獻(xiàn)[10]通過(guò)劃分高、低密度區(qū)域選擇高密度區(qū)域中具有代表性的數(shù)據(jù)對(duì)象作為初始的聚類(lèi)中心。文獻(xiàn)[11]通過(guò)建立數(shù)據(jù)對(duì)象分布的密度集合，計(jì)算最近兩點(diǎn)的垂直中點(diǎn)方法來(lái)確定初始聚類(lèi)中心，迭代形成最終簇類(lèi)。通過(guò)考察密度特性，這些算法都有效地改善了K-means的穩(wěn)定性。但算法中還存在著參數(shù)選擇較為主觀的現(xiàn)象，比如對(duì)于密度參數(shù)θ選得過(guò)大，可導(dǎo)致本不屬于同一類(lèi)的樣本點(diǎn)被劃分到同一類(lèi)的情況；如果過(guò)小，會(huì)導(dǎo)致相反的情形，導(dǎo)致噪聲數(shù)據(jù)也被列入候選聚類(lèi)中心的情況，由此導(dǎo)致聚類(lèi)性能的下降。

基于此，文中提出一種基于距離-期望密度參數(shù)的聚類(lèi)中心選擇方法。該方法結(jié)合每個(gè)聚類(lèi)簇大致期望的樣本平均個(gè)數(shù)來(lái)確定密度θ的大小。同時(shí)，在滿足期望密度的前提下，計(jì)算每個(gè)密度區(qū)域的半徑，作為期望密度參數(shù)，結(jié)合數(shù)據(jù)樣本間的距離，尋找初始的聚類(lèi)中心。由于對(duì)用戶聚類(lèi)依靠的是用戶對(duì)產(chǎn)品的評(píng)分相似性，與密度類(lèi)似，偏好同一類(lèi)產(chǎn)品的用戶一般會(huì)具有相同的喜好，所以將改進(jìn)的K-means聚類(lèi)算法直接應(yīng)用于用戶聚類(lèi)產(chǎn)生相似用戶是十分有意義的。

(1)相關(guān)定義。

定義1：密度參數(shù)。

取空間中的任一數(shù)據(jù)樣本xi，以其為中心，尋找距離xi最近的θ個(gè)數(shù)據(jù)樣本，把xi與個(gè)樣本之間的最大距離稱(chēng)之為樣本xi的密度參數(shù)，用ε表示。

定義2：期望密度。

Eθ=a*n/k

(4)

其中：n為數(shù)據(jù)集的樣本總數(shù)；k為設(shè)定的聚類(lèi)個(gè)數(shù)；a為期望密度比例系數(shù)。

a可以根據(jù)經(jīng)驗(yàn)選取，文中取a=0.6。即，如果某個(gè)數(shù)據(jù)樣本被選作聚類(lèi)中心，則離該對(duì)象最近的θ個(gè)樣本應(yīng)該占到以該對(duì)象為中心所形成的聚類(lèi)簇覆蓋樣本的60%。

定義3：平均相異度。

數(shù)據(jù)樣本之間的平均相異度定義為：

(5)

其中：xi、xj為數(shù)據(jù)集中兩個(gè)數(shù)據(jù)樣本；t為數(shù)據(jù)對(duì)象xj的個(gè)數(shù)；d(xi,xj)為數(shù)據(jù)樣本xi與xj間的距離，文中用歐幾里得距離公式進(jìn)行計(jì)算：

(6)

(2)改進(jìn)算法的思想。

聚類(lèi)中心優(yōu)化的K-means算法中，選取具有較低期望密度參數(shù)且彼此相距最遠(yuǎn)的k個(gè)對(duì)象作為初始的聚類(lèi)中心，這些中心點(diǎn)能夠很好地反映數(shù)據(jù)對(duì)象的空間分布特性，同時(shí)能保證選出的聚類(lèi)中心所覆蓋的區(qū)域樣本密度較高。這些都使得算法具有較高的穩(wěn)定性，同時(shí)使得算法能夠獲得全局最優(yōu)的聚類(lèi)效果。

4 基于用戶的協(xié)同過(guò)濾推薦

協(xié)同過(guò)濾算法是于1992年由Goldberg等學(xué)者提出的，該算法是以項(xiàng)目屬性或者用戶評(píng)分相似性作為個(gè)性化推薦的基礎(chǔ)。協(xié)同過(guò)濾算法可以分為基于用戶的協(xié)同過(guò)濾和基于項(xiàng)目的協(xié)同過(guò)濾[12]?；谟脩舻膮f(xié)同過(guò)濾算法實(shí)現(xiàn)推薦時(shí)基于如下事實(shí)：如果用戶對(duì)一些項(xiàng)目的評(píng)分比較相似，就認(rèn)為他們?cè)谄渌?xiàng)目的評(píng)分上具有相似關(guān)系[13]。

算法的執(zhí)行流程為：首先，計(jì)算目標(biāo)用戶與推薦系統(tǒng)中所有用戶的相似性，找到與目標(biāo)用戶最相似的鄰居用戶集合；其次，根據(jù)最近鄰居集合中用戶對(duì)項(xiàng)目的評(píng)分去預(yù)測(cè)目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目的打分；最后，根據(jù)預(yù)測(cè)的打分情況為目標(biāo)用戶推薦打分值最高的topM個(gè)項(xiàng)目[14-15]。

算法執(zhí)行過(guò)程中先明確的幾個(gè)計(jì)算單元如下：

(1)用戶相似度計(jì)算。

用戶之間的相似度是通過(guò)用戶對(duì)項(xiàng)目的歷史評(píng)分來(lái)進(jìn)行度量的[16]。文中使用余弦相似性來(lái)產(chǎn)生用戶最近鄰居，其公式如下：

(7)

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

在預(yù)測(cè)項(xiàng)目評(píng)分時(shí)，經(jīng)常選取前N個(gè)與目標(biāo)用戶相似性最大的用戶作為目標(biāo)用戶的最近鄰居，根據(jù)這些鄰居用戶對(duì)目標(biāo)用戶未評(píng)分項(xiàng)目的評(píng)分情況來(lái)預(yù)測(cè)產(chǎn)生目標(biāo)用戶對(duì)其的評(píng)分值。假設(shè)Nu表示鄰居用戶的集合，根據(jù)式(8)可以計(jì)算目標(biāo)用戶對(duì)于某項(xiàng)目的預(yù)測(cè)評(píng)分。

(8)

針對(duì)預(yù)測(cè)評(píng)分的值給出目標(biāo)用戶的推薦列表。

5 基于Weighted-slope One的用戶聚類(lèi)推薦算法

設(shè)用戶集合為U={u1,u2,…,um}，使用改進(jìn)的K-means算法生成的用戶集合表示為U'={C1,C2,…,Ck}。其中，k表示生成簇類(lèi)的個(gè)數(shù)，Ck表示第k個(gè)簇類(lèi)?；赪eighted-slopeOne的用戶聚類(lèi)推薦算法的具體執(zhí)行步驟如下：

輸入：用戶-評(píng)分矩陣D，聚類(lèi)個(gè)數(shù)k，最近鄰居及大小N，推薦列表的個(gè)數(shù)M；

輸出：目標(biāo)用戶的推薦列表以及對(duì)應(yīng)的評(píng)分。

Step1：根據(jù)Weighted-slopeOne算法利用式(3)對(duì)初始的用戶-評(píng)分矩陣D中的0元素進(jìn)行填充，生成填充矩陣Dζ；

Step2：利用改進(jìn)的K-means算法基本思想對(duì)Dζ進(jìn)行處理，生成k個(gè)聚類(lèi)輸出，各聚類(lèi)的中心為ci,i=1,2,…,k；

Step3：通過(guò)式(6)計(jì)算目標(biāo)用戶與聚類(lèi)中心ci的距離，將目標(biāo)用戶分配到距離最小的聚類(lèi)Ci(i=1,2,…,k)中；

Step4：在目標(biāo)用戶所屬的簇類(lèi)中，根據(jù)式(7)計(jì)算目標(biāo)用戶與其他用戶的相似性，搜索出相似性最大的前N個(gè)用戶作為目標(biāo)用戶的最近鄰居集合，記為Nu；

Step5：利用式(8)計(jì)算各個(gè)項(xiàng)目的預(yù)測(cè)評(píng)分，列出topM個(gè)預(yù)測(cè)得分最大的項(xiàng)目推薦給目標(biāo)用戶。

6 仿真實(shí)驗(yàn)與結(jié)果分析

6.1 數(shù)據(jù)集

仿真實(shí)驗(yàn)中，選取了MovieLens站點(diǎn)的電影數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)。數(shù)據(jù)集中包含了943個(gè)用戶1 682部電影共10 000條評(píng)價(jià)得分，其中每個(gè)用戶至少對(duì)20部電影進(jìn)行了評(píng)分，評(píng)分值為1～5之間的整數(shù)。評(píng)分值越大說(shuō)明用戶對(duì)該項(xiàng)目的偏好性越強(qiáng)，0值表示用戶未對(duì)該電影進(jìn)行評(píng)分。

6.2 評(píng)測(cè)指標(biāo)

在推薦算法中經(jīng)常使用平均絕對(duì)誤差(MAE)來(lái)衡量推薦結(jié)果的好壞。MAE是通過(guò)計(jì)算預(yù)測(cè)的用戶評(píng)分與實(shí)際的用戶評(píng)分之間的偏差來(lái)度量預(yù)測(cè)的準(zhǔn)確性[12]。假設(shè)目標(biāo)用戶對(duì)項(xiàng)目的實(shí)際評(píng)分為{pi|i=1,2,…,n},其中n表示項(xiàng)目的總個(gè)數(shù)，使用推薦算法預(yù)測(cè)得到的目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分為 {qi|i=1,2,…,n},那么MAE的計(jì)算公式為：

(9)

從式(9)可以看出，MAE值越小說(shuō)明推薦結(jié)果的準(zhǔn)確性越高。

6.3 仿真結(jié)果分析

為保證所選取的相似用戶集合最為合理，首先針對(duì)用戶簇類(lèi)個(gè)數(shù)進(jìn)行系統(tǒng)過(guò)濾算法的實(shí)現(xiàn)，計(jì)算其對(duì)應(yīng)的MAE值，以選擇最合理的用戶簇類(lèi)個(gè)數(shù)來(lái)對(duì)目標(biāo)用戶產(chǎn)生最終的推薦結(jié)果。

圖1就是在不同的聚類(lèi)個(gè)數(shù)下MAE的變化情況。

圖1 不同聚類(lèi)數(shù)目下的MAE值

由圖1可以看出，隨著聚類(lèi)個(gè)數(shù)的增加，MAE的值先降后升，這說(shuō)明在用戶數(shù)固定的情況下，需要找到一個(gè)最優(yōu)的聚類(lèi)數(shù)目能夠使推薦的MAE值達(dá)到最小。從圖1中觀察可知，當(dāng)聚類(lèi)個(gè)數(shù)為11時(shí)，MAE的值最低，顯然對(duì)于文中所選取的數(shù)據(jù)集而言，令k=11是最合理的聚類(lèi)個(gè)數(shù)。

在確定了最優(yōu)的聚類(lèi)個(gè)數(shù)后，將文中所提出的基于Weighted-slopeOne算法與傳統(tǒng)的協(xié)同過(guò)濾算法、基于K-means用戶聚類(lèi)的協(xié)同過(guò)濾算法進(jìn)行了比較。最近鄰居的個(gè)數(shù)從5增至50，間隔為5。實(shí)驗(yàn)對(duì)比結(jié)果如圖2所示。

圖2 推薦結(jié)果的MAE值比較

根據(jù)圖2，隨著目標(biāo)用戶最近鄰居個(gè)數(shù)的不斷增加，三種算法的MAE值呈明顯的下降趨勢(shì)。這說(shuō)明隨著最近鄰居個(gè)數(shù)的不斷增加，可以有效提升推薦結(jié)果的準(zhǔn)確率。但從MAE下降的速率來(lái)看，當(dāng)最近鄰居的個(gè)數(shù)上升到某個(gè)個(gè)數(shù)之后，MAE下降的速率越來(lái)越慢，最后趨近于平滑。這說(shuō)明最近鄰居的個(gè)數(shù)并不是越多越好，而是隨著最近鄰居數(shù)目的增多，其為MAE減小所做的貢獻(xiàn)越來(lái)越小。在實(shí)際應(yīng)用中，當(dāng)考慮推薦系統(tǒng)實(shí)時(shí)性、存儲(chǔ)、計(jì)算的復(fù)雜度時(shí)，合理選擇最近鄰居的個(gè)數(shù)對(duì)于推薦精度和維護(hù)成本都至關(guān)重要。

除此之外，在不同的最近鄰居數(shù)目下對(duì)比三種算法可得，文中提出的算法較其他算法均有最小的MAE值，傳統(tǒng)的協(xié)同過(guò)濾算法的推薦效果最不理想，添加了用戶聚類(lèi)的推薦效果次之。但是由于數(shù)據(jù)稀疏性和初始聚類(lèi)中心隨機(jī)選取可能帶來(lái)的不穩(wěn)定聚類(lèi)結(jié)果，基于K-means的協(xié)同過(guò)濾推薦的精度也不高。而文中提出的算法無(wú)論是對(duì)數(shù)據(jù)稀疏性還是聚類(lèi)結(jié)果都進(jìn)行了對(duì)應(yīng)的處理，可以確保在數(shù)據(jù)稀疏性降低的同時(shí)有穩(wěn)定的聚類(lèi)結(jié)果。顯然，通過(guò)文中填充高維稀疏矩陣，實(shí)現(xiàn)用戶聚類(lèi)，為目標(biāo)用戶在聚類(lèi)內(nèi)給出推薦結(jié)果的方法不但有效降低了數(shù)據(jù)的稀疏性，同時(shí)在聚類(lèi)內(nèi)搜索目標(biāo)用戶的最近鄰居縮小了搜索范圍，加快了推薦算法的響應(yīng)速度，推薦MAE值得到了提升。

7 結(jié)束語(yǔ)

文中分析陳述了協(xié)同過(guò)濾推薦算法所存在的問(wèn)題以及學(xué)者為提升推薦準(zhǔn)確率所做的研究工作。在此基礎(chǔ)上提出了一種基于Weighted-slopeOne的用戶聚類(lèi)推薦算法。通過(guò)借鑒Weighted-slopeOne進(jìn)行評(píng)分預(yù)測(cè)的思想對(duì)初始的用戶-項(xiàng)目矩陣中的0元素進(jìn)行填充，降低數(shù)據(jù)稀疏性，使用改進(jìn)的K-means聚類(lèi)算法對(duì)用戶進(jìn)行聚類(lèi)，在簇類(lèi)內(nèi)查找目標(biāo)用戶的最近鄰居最終給出預(yù)測(cè)評(píng)分以及推薦結(jié)果。仿真實(shí)驗(yàn)證明，文中提出的算法可以有效地提升推薦的準(zhǔn)確性，同時(shí)由于其縮小了搜索最近鄰居的空間，推薦算法的實(shí)時(shí)性也得到了提升。

[1] 王桂芬.電子商務(wù)個(gè)性化推薦系統(tǒng)中協(xié)同過(guò)濾算法的研究與應(yīng)用[D].南昌:南昌大學(xué),2012.

[2] 李 華,張 宇,孫俊華.基于用戶模糊聚類(lèi)的協(xié)同過(guò)濾推薦研究[J].計(jì)算機(jī)科學(xué),2012,39(12):83-86.

[3] 孫小華.協(xié)同過(guò)濾系統(tǒng)的稀疏性與冷啟動(dòng)問(wèn)題的研究[D].杭州:浙江大學(xué),2005.

[4] 郁 雪,李敏強(qiáng).一種結(jié)合有效降維和K-means聚類(lèi)的協(xié)同過(guò)濾推薦模型[J].計(jì)算機(jī)應(yīng)用研究,2009,26(10):3718-3720.

[5]VozalisMG,MargaritisKG.ApplyingSVDonitem-basedfiltering[C]//Procof5thinternationalconferenceonintelligentsystemsdesignandapplications.[s.l.]:IEEE,2005:464-469.

[6] 鄧愛(ài)林,左子葉,朱揚(yáng)勇.基于項(xiàng)目聚類(lèi)的協(xié)同過(guò)濾推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng),2004,25(9):1665-1670.

[7] 李朝陽(yáng).基于SlopeOne算法的協(xié)作過(guò)濾個(gè)性化推薦系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].武漢:華中科技大學(xué),2010.

[8] 王 毅.基于Hadoop的SlopeOne及其改進(jìn)算法實(shí)現(xiàn)[D].成都:西南交通大學(xué),2011.

[9] 董 麗,邢春曉,王克宏.基于不同數(shù)據(jù)集的協(xié)作過(guò)濾算法評(píng)測(cè)[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版,2009,49(4):590-594.

[10] 袁 方,周志勇,宋 鑫.初始聚類(lèi)中心優(yōu)化的k-means算法[J].計(jì)算機(jī)工程,2007,33(3):65-66.

[11] 周煒奔,石躍祥.基于密度的K-means聚類(lèi)中心選取的優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(5):1726-1728.

[12] 馬宏偉,張光衛(wèi),李 鵬.協(xié)同過(guò)濾推薦算法綜述[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30(7):1282-1288.

[13] 李 濤,王建東,葉飛躍,等.一種基于用戶聚類(lèi)的協(xié)同過(guò)濾推薦算法[J].系統(tǒng)工程與電子技術(shù),2007,29(7):1178-1182.

[14] 李曉艷,張子剛,張逸石.集成k-means聚類(lèi)和有監(jiān)督特征選擇的混合式協(xié)同過(guò)濾推薦[J].管理學(xué)報(bào),2013,10(9):1362-1367.

[15] 張海燕,丁 峰,姜麗紅.基于模糊聚類(lèi)的協(xié)同過(guò)濾推薦方法[J].計(jì)算機(jī)仿真,2005,22(8):144-147.

[16] 賀銀慧,陳端兵,陳 勇,等.一種結(jié)合共同鄰居和用戶評(píng)分信息的相似度算法[J].計(jì)算機(jī)科學(xué),2010,37(9):184-186.

Research on User Clustering Recommendation Algorithm Based on Weighted-slope One

ZHENG Dan,WANG Ming-yang,CHEN Guang-sheng

(College of Information and Computer Engineering,Northeast Forestry University,Harbin 150040,China)

Aiming at the problems of data sparseness and the poor real-time performance of traditional collaborative filtering recommendation algorithm,a new user clustering recommendation algorithm based on Weighted-slope One algorithm is proposed.Firstly,the zero items in user-item matrix are filled by Weighted-slope One algorithm.This operation can effectively reduce the data sparseness.Secondly,the users are clustered by the optimizedK-meansalgorithm.Thisoperationcaneffectivelyfindthenearestneighborofthetargetuser.Finally,thecorrespondingproductsarerecommendedtothetargetusersaccordingtotheirnearestneighborswhicharefoundbytheusers’collaborativefilteringrecommendationalgorithm.Experimentalresultsshowthattheimprovedalgorithmcansignificantlyreducethedatasparseness,andimprovetherealtimeperformanceandtheaccuracyofrecommendation.

collaborative filtering;high-dimensional sparse matrix;Weighted-slope One；K-means;clusteringcenter

2015-07-14

2015-10-20

時(shí)間：2016-03-22

中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金項(xiàng)目(2572014DB05)；中國(guó)博士后科學(xué)基金面上基金(2012M520711)；國(guó)家自然科學(xué)基金資助項(xiàng)目(71473034)

鄭 丹(1991-)，女，碩士，研究方向?yàn)閿?shù)據(jù)挖掘；王名揚(yáng)，博士，副教授，研究方向?yàn)閿?shù)據(jù)挖掘、社交網(wǎng)絡(luò)挖掘；陳廣勝，教授，研究方向?yàn)樯镔|(zhì)材料材質(zhì)預(yù)測(cè)、新型復(fù)合材料智能化檢測(cè)、技術(shù)創(chuàng)新方法推廣應(yīng)用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1521.068.html

TP

A

1673-629X(2016)04-0051-05

10.3969/j.issn.1673-629X.2016.04.011