王興茂,張興明,吳毅濤,潘俊池
(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南鄭州 450002)
基于啟發(fā)式聚類模型和類別相似度的協(xié)同過濾推薦算法
王興茂,張興明,吳毅濤,潘俊池
(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南鄭州 450002)
基于k-近鄰的協(xié)同過濾推薦算法對于鄰居數(shù)量k的確定過于主觀,并且推薦時以k-近鄰均值加權(quán)推薦不夠準確.針對這兩個問題,本文首先引入并改進最大最小距離聚類算法,進而設(shè)計啟發(fā)式聚類模型將用戶進行不規(guī)定類別數(shù)的自由聚類劃分,目標用戶所在類的用戶為鄰居用戶,客觀確定鄰居數(shù)量;然后在推薦時定義類別相似度,針對性地建立目標用戶未評分和評分項目的潛在類別關(guān)系,改進k-近鄰均值加權(quán)算法.實驗結(jié)果表明,該算法提高了推薦準確度(約0.035MAE).
協(xié)同過濾;推薦算法;聚類算法;啟發(fā)式聚類模型;類別相似度
協(xié)同過濾是推薦系統(tǒng)中應(yīng)用最廣泛、最成功的推薦算法[1].它能根據(jù)用戶的歷史行為來預(yù)測用戶的偏好,進而為用戶進行個性化的推薦,已成為學(xué)術(shù)界研究的熱點[2~4].但隨著互聯(lián)網(wǎng)的爆炸式擴張,數(shù)據(jù)稀疏性成為推薦系統(tǒng)最突出的問題[5],導(dǎo)致目標用戶選擇出的鄰居不合理,進而導(dǎo)致推薦結(jié)果準確度降低.很多學(xué)者采用聚類算法來提高推薦的效果[6],G Adomavicius 和 Tuzhilin根據(jù)用戶評分的相似性對用戶進行聚類,離線時處理數(shù)據(jù),在線時尋找最近鄰居[7].Truong等對項目進行k-均值聚類,計算了目標項目與聚類中心的相似性,然后在項目聚類中尋找目標項目最近鄰居并產(chǎn)生推薦列表[8].張莉等綜合用戶和項目特征,采用k-均值對相似用戶聚類,然后結(jié)合用戶興趣類別活躍度進行推薦[9].Rashid等在用戶聚類基礎(chǔ)上生成每個聚類的代理用戶,然后基于目標用戶的最相似代理用戶進行最近鄰協(xié)同過濾推薦[10].George等提出對用戶和項目同時進行聚類的協(xié)同過濾方法[11].以上的研究緩解了數(shù)據(jù)稀疏度對推薦系統(tǒng)的影響,但存在兩個基本問題,一是算法主觀地選擇了聚類時的類別數(shù)量和鄰居的數(shù)量;二是在推薦時采用k-近鄰均值加權(quán)的算法以評分項目均值加權(quán)的方式太過一般性,沒有考慮被預(yù)測的項目與目標用戶所評價項目的潛在關(guān)系,即本文引入的類別相似度.
針對這兩個問題,本文首先以用戶之間歐氏距離為標準,在推薦系統(tǒng)中引入并改進最大最小距離聚類算法進而設(shè)計啟發(fā)式聚類模型對用戶進行客觀的類別劃分,以目標用戶所在類的集合為鄰居集合,不主觀規(guī)定類別的數(shù)量和鄰居的數(shù)量k;然后在預(yù)測評分時引入項目之間的類別相似度,對傳統(tǒng)的k-近鄰均值加權(quán)公式進行根本的改進,使預(yù)測評分更加合理.
2.1啟發(fā)式聚類模型的提出
最大最小距離聚類算法[12]的最大優(yōu)勢就是復(fù)雜度較低,但它存在第一個聚類中心隨機選取帶來的聚類不準確而且參數(shù)α的選取主觀問題.本文以最大最小聚類算法為基礎(chǔ)設(shè)計啟發(fā)式聚類模型來客觀地對用戶的類別進行劃分,如圖1所示,該模型采用啟發(fā)式的思想來確定第一個聚類中心.為了更好地對模型進行說明以及方便后文的計算,先介紹相關(guān)定義:
定義1用戶Ui點密度:以用戶i為中心,d為半徑,歐式距離為衡量標準,這個球狀簇內(nèi)所有用戶的數(shù)量為用戶Ui的點密度,設(shè)為mi.
定義2歐式距離矩陣:存儲各個用戶之間歐氏距離的矩陣,設(shè)為D(m×m).
該模型核心思想分為三步:
step1通過用戶之間的歐式距離計算建立歐式距離矩陣;
step2采用啟發(fā)式的思想來確定第一個聚類中心,即一個用戶周圍的用戶數(shù)越多,就越適合作為聚類中心,本模型通過點密度的計算(見2.2.2小節(jié))挑選出適合作第一個聚類中心的用戶;
2.2算法的相關(guān)計算
2.2.1歐式相似度
設(shè)用戶的評分向量為(ri1,ri2,ri3,…,rim),則兩個用戶Ui和Uj之間的歐式距離[13]如式(1):
(1)
歐式相似度與歐式距離成反相關(guān)的關(guān)系,Ui和Uj的歐式相似度如式(2):
(2)
設(shè)用戶項目評分矩陣為R(m×n)如式(3),這是m個用戶對n個項目的評分矩陣,rij為用戶i對項目j的評分.
(3)
通過矩陣R(m×n)和式(1),計算系統(tǒng)中任意兩個用戶ui與uj之間的歐式距離di,j.構(gòu)成系統(tǒng)中用戶的歐式距離矩陣D(m×m)如式(4):
(4)
進而利用矩陣D(m×m)和式(2)計算這兩個用戶之間的歐式相似度simij,構(gòu)成歐式相似度矩陣OS(m×m)如式(5):
(5)
2.2.2點密度和參數(shù)α的計算
模型中采用啟發(fā)式的思想通過點密度的計算來確定第一個聚類中心,計算如下:
首先需要找合適的d,本文令它為系統(tǒng)中所有用戶之間距離之和的均值.通過2.2.1小節(jié)的計算,知道D(m×m)是一個角對稱矩陣,只需要計算上三角,即d的計算如式(6):
(6)
點密度計算:
設(shè)Li(di,1,di,2,di,3,…,di,m)為矩陣D(m×m)的第i行的行向量,它為用戶Ui與系統(tǒng)中其它用戶的距離向量.引入?yún)?shù)mi,j,對任意j∈{1,2,3,…,m},如果di,j≥d,則mi,j=1,否則mi,j=0,則用戶Ui的點密度mi如式(7):
(7)
從mi(1≤i≤m,且i∈N)中找出mk,滿足對于任意的整數(shù)i∈[1,m],有mk≥mi.這樣就找出具有最大用戶點密度的用戶Uk,我們把用戶Uk設(shè)為第一個中心點z1.
α的計算:
α的確定關(guān)系著聚類的效果,它應(yīng)該與數(shù)據(jù)集中用戶點之間距離大小有關(guān),本文給出通用計算如下:遍歷歐式距離矩陣D(m×m),找出dmax,即對于任意di,j(1≤i,j≤m)有dmax≥di,j.α的計算如式(8),關(guān)于d的計算見式(6).
α=d/dmax
(8)
2.2.3項目類別相似度計算
定義3項目類別相似度兩個項目Ii和Ij的類別接近程度,設(shè)為Isim(i,j).
我們將系統(tǒng)中項目的用戶評分向量(r1,r2,r3,…,rm)進行二元化,即如果ri>0,則ri=1,否則ri=0.然后引入Tanimoto系數(shù)計算兩個項目Ix和Iy之間的類別相似度,如式(9):
(9)
x和y為項目Ix和Iy經(jīng)過二元化的評分向量,x·y是兩個項目共同被評價的用戶數(shù),x·x+y·y-x·y為兩個項目所有屬性的個數(shù).
2.2.4引入類別相似度的預(yù)測評分計算
傳統(tǒng)的預(yù)測目標用戶對未知項目評分公式[14]如式(10),式中采用k-近鄰平均加權(quán)的方式進行目標用戶對未知項目分數(shù)的預(yù)測.
(10)
本文把該公式分兩部分組成,我們將其分別定義:
(1)目標用戶對目標項目的基本評分值Rb如式(11):
(11)
(2)其它用戶對目標用戶的推薦貢獻值Rc如式(12):
(12)
(13)
式(13)中Isim(i,j)為用戶評價過的項目與目標項目之間的類別相似度,a為目標用戶ua評價過的項目數(shù),Ra(j)為目標用戶ua對項目ij(1≤j≤a)的評分.該式通過Isim(i,j)與Ra(j)加權(quán)來計算目標用戶對目標項目的評分,然后引入權(quán)重1/2來計算目標用戶對目標項目的均值.新的預(yù)測評分公式如式(14):
(14)
算法流程的設(shè)計
基于2.2小節(jié)的主要步驟的相關(guān)計算,本節(jié)直接給出本文算法的流程.
輸入:用戶項目評分矩陣R(m×n),目標用戶Ua
輸出:為用戶Ua提供的推薦列表
step1根據(jù)式(1)、(2)和用戶評分矩陣R(m×n)計算用戶之間的歐幾里得距離矩陣D(m×m)和歐式相似度矩陣OS(m×m)分別如式(4)和(5);
step2利用式(6)、(7)和矩陣D(m×m),計算系統(tǒng)中用戶的樣本點密度mi,并挑選出具有最大點密度的用戶Uk;
step3將Uk設(shè)為第一個聚類中心點z1,按照2.1小節(jié)的模型對系統(tǒng)中用戶按照歐幾里得距離進行不規(guī)定類別數(shù)k的聚類,聚類完成,分別G1,G2,G3,…Gk;
step4如果Ua∈Gg,則類Gg為Ua的鄰居集;
step5根據(jù)式(13)和Gg為目標用戶預(yù)測未評分的項目Ii的評分Pa,i,(1≤i≤n);
step6根據(jù)評分Pa,i大小排序,為目標用戶Ua提供推薦列表.
準確度分析前文已經(jīng)說明,這里不再贅述,所以本節(jié)主要對時間復(fù)雜度進行分析和比較.本文的時間開銷主要是歐式相似度矩陣計算、第一個樣本點的確定、聚類劃分、預(yù)測評分計算.
(1)歐式相似度矩陣
(2)第一個樣本點的確定
mi:用戶點密度計算//執(zhí)行m(m+1)次
(3)聚類劃分
z2:第2個樣本點的確定//執(zhí)行(m-1)次
z3:第3個樣本點的確定//執(zhí)行2(m-2)次
z4:第4個樣本點的確定//執(zhí)行3(m-3)次
…
zk:第k個樣本點的確定//執(zhí)行(k-1)(m-k+1)次
(4)預(yù)測評分計算//執(zhí)行小于m/2次(由于鄰居數(shù)不定)
算法執(zhí)行總次數(shù):
根據(jù)復(fù)雜度計算規(guī)則計算得出時間復(fù)雜度為:
T(n)=O(m2)
本文算法復(fù)雜度為O(m2),經(jīng)典的最基本協(xié)同過濾推薦算法的復(fù)雜度也為O(m2),說明本文算法在提高了準確度的同時并不會付出相當大的額外時間開銷,即本文算法是可行的.
仿真實驗首先在MovieLens-100k、Netflix-3m1k和Netflix-5m3k三種數(shù)據(jù)集下驗證本文算法CluC-CF的推薦性能,然后人為對數(shù)據(jù)集MovieLens-100k進行處理,進而驗證稀疏度和用戶數(shù)對本文算法CluC-CF性能的影響,仿真實驗比較以下三種推薦算法:
(1)傳統(tǒng)基于用戶的協(xié)同過濾推薦算法(相似度計算采用pearson相關(guān)系數(shù))(CF);
(2)基于傳統(tǒng)聚類的協(xié)同過濾推薦算法(Ck-CF);
(3)基于聚類和類別相似度的協(xié)同過濾推薦算法(CluC-CF).
4.1數(shù)據(jù)集
本實驗是在基于java的Eclipse開發(fā)環(huán)境下進行的.為了驗證本文算法的有效性,實驗中采用Grouplens提供的MovieLens-100k和電影租賃網(wǎng)站Netflix提供的Netflix-3m1k和Netflix-5m3k數(shù)據(jù)集,三種數(shù)據(jù)集的數(shù)據(jù)情況如表1所示,隨機2-8分割,80%為訓(xùn)練數(shù)據(jù),20%為測試數(shù)據(jù),進行本文算法的仿真實驗.
表1MovieLens-100k、Netflix-3m1k和Netflix-5m3k三種數(shù)據(jù)集數(shù)據(jù)表
名稱用戶數(shù)項目數(shù)評分總數(shù)稀疏度MovieLens-100k94316829040994.3%Netflix-3m1k442710005613698.7%Netflix-5m3k8662300029329998.9%
用MovieLens-100k來進行評分密度及稀疏度計算說明,評分密度P如式(15):
(15)
稀疏度X如式(16):
X=1-P=0.943
(16)
4.2評價指標
本文平均絕對偏差MAE(Mean Absolute Error)來衡量算法的準確度[15],MAE可以直觀地對推薦質(zhì)量進行度量,是最常用的一種推薦質(zhì)量度量方法,時間指標主要考慮訓(xùn)練時間的長短.
(1)準確度指標MAE:
平均絕對偏差MAE通過計算預(yù)測的用戶評分與實際的用戶評分之間的偏差度量預(yù)測的準確性,MAE越小,推薦質(zhì)量越高.設(shè)預(yù)測的用戶評分集合表示為{p1,p2,p3,…,pN},對應(yīng)的實際用戶評分集合為{r1,r2,r3,…,rN},則平均絕對偏差MAE如式(17):
(17)
(2)時間指標:
主要考慮算法的訓(xùn)練時間,因為推薦過程中訓(xùn)練占主導(dǎo)地位.
4.3實驗結(jié)果和分析
4.3.1近鄰數(shù)對算法精度的影響
當近鄰數(shù)k為5、30、50、70時,在MovieLens-100k、Netflix-3m1k和Netflix-5m3k三個不同數(shù)據(jù)集下比較Per-CF、Ck-CF和CluC-CF三種算法的MAE大小.實驗結(jié)果如圖2所示.
本文算法通過數(shù)據(jù)集的特性分析,自動選擇鄰居數(shù),并不需要人為主觀的進行選擇,所以推薦準確度與鄰居數(shù)無關(guān),而Per-CF和CK-CF都會受鄰居數(shù)的影響,Per-CF受近鄰數(shù)影響較大.在Netflix-3m1k和Netflix-5m3k這種高稀疏度的數(shù)據(jù)集下本文算法CluC-CF的性能優(yōu)勢更加明顯,因為CluC-CF能夠根據(jù)數(shù)據(jù)集特性客觀調(diào)整聚類數(shù)量和鄰居數(shù)量,并且通過類別相似度更能較深地挖掘潛在的關(guān)聯(lián)因素,在數(shù)據(jù)更稀疏情況下較其它兩種算法效果更佳.而基于共同評價項目評分的Per-CF推薦性能惡化的很快,Ck-CF通過主觀聚類分析能一定程度緩解推薦性能的惡化,同時可以看到CluC-CF在數(shù)據(jù)集Netflix-5m3k下的推薦準確度要比在Netflix-3m1k下高,這因為Netflix-5m3k數(shù)據(jù)集的用戶數(shù)更多,即用戶更加稠密,每一類都不乏相似性高的鄰居,根據(jù)類內(nèi)鄰居進行推薦會使推薦性能更優(yōu).下面針對稀疏度和用戶數(shù)對本文算法的影響進一步驗證.
4.3.2稀疏度對算法精度的影響
為了進一步驗證稀疏度對本文算法CluC-CF推薦精度的影響,本小節(jié)在MovieLens-100k數(shù)據(jù)集中,保證用戶數(shù)和項目數(shù)不變,隨機減少評分矩陣的評分,增加稀疏度,當鄰居數(shù)k=40(此時Per-CF和CK-CF性能最優(yōu)),比較三種算法的精度,實驗結(jié)果如圖3.
當稀疏度變大時,相似性計算精度會變低,會導(dǎo)致主觀規(guī)定鄰居數(shù)進而硬性選擇鄰居更加不準確,而本文算法CK-CF會根據(jù)數(shù)據(jù)集特性自動選取鄰居,并引入項目類別相似度提高推薦精度,所以表現(xiàn)會優(yōu)于Per-CF和CK-CF,也就是更適用于稀疏度高的數(shù)據(jù)集.
4.3.3用戶數(shù)對算法精度的影響
本小節(jié)將驗證推薦系統(tǒng)中的用戶數(shù)對本文算法的影響,本實驗在數(shù)據(jù)集MovieLens-100k中,k=40,保證項目和稀疏度不變,將用戶數(shù)逐漸增加,比較三種算法的精度,實驗結(jié)果如圖4.
隨著鄰居數(shù)的繼續(xù)增加,本文算法的性能逐漸變優(yōu).分析這一原因是,當用戶數(shù)很少時,CluC-CF聚類產(chǎn)生的每一類中用戶數(shù)變少,即導(dǎo)致鄰居缺乏,甚至可能出現(xiàn)“孤苦伶仃無鄰居”的現(xiàn)象,所以準確度低的可憐.而當用戶數(shù)很多時,每一類都不乏相似性高的鄰居,會使推薦性能更優(yōu).而實際推薦系統(tǒng)中往往用戶數(shù)都至少是數(shù)以萬計,所以本文算法的實用性更強.
4.3.4算法運行時間
為佐證3.2小節(jié)分析的CluC-CF時間復(fù)雜度,本實驗來比較三種算法的運行時間,實驗結(jié)果如圖5所示.
可以看出CluC-CF的運行時間接近傳統(tǒng)的推薦算法Per-CF,而小于CK-CF.這是因為CK-CF采用k-均值聚類后又要重新選擇鄰居,而本文算法不需要,所以時間要小于CK-CF.然而CluC-CF要通過聚類來客觀選擇鄰居,所以時間大于Per-CF.
本文針對傳統(tǒng)k-近鄰協(xié)同過濾推薦算法存在鄰居數(shù)的確定過于主觀和鄰居推薦時的平均加權(quán)算法不具有針對性的問題,首先在推薦系統(tǒng)中設(shè)計了啟發(fā)式聚類模型,根據(jù)數(shù)據(jù)集的特性客觀的為目標用戶劃分鄰居.然后提出項目類別相似度的概念,對傳統(tǒng)推薦時的平均加權(quán)算法進行根本改進,使目標用戶對未知項目的基本評分更具有針對性,提高推薦性能.基于這兩個針對鄰居選擇和推薦的創(chuàng)新點,提出基于啟發(fā)式聚類模型和類別相似度的協(xié)同過濾推薦算法,仿真實驗佐證了這一算法的可行性,并且CluC-CF確實提高了推薦準確度(較Per-CF提升約約0.035MAE).然而數(shù)據(jù)集特性很差時,會存在孤立點自成一類的問題,本文下一步主要工作將進行這方面的研究.
[1]張鋒,等.兩方參與的隱私保護協(xié)同過濾推薦研究[J].電子學(xué)報,2009,37(1):84-89.
Zhang Feng,et al.Research on privacy-preserving two-party collaborative filtering recommendation[J].Acta Electronica Sinica,2009,37(1):84-89.(in Chinese)
[2]黃世平,黃晉,陳健,等.自動建立信任的防攻擊推薦算法研究[J].電子學(xué)報,2013,41(2):84-89.
Huang Shi-ping,Huang Jin,Chen Jian,et al.Anti-attack recommender algorithm based on automatic trust establishment[J].Acta Electronica Sinica,2013,41(2):84-89.(in Chinese)
[3]吳永輝,等.基于主題的自適應(yīng)、在線網(wǎng)絡(luò)熱點發(fā)現(xiàn)方法及新聞推薦系統(tǒng)[J].電子學(xué)報,2010,38(11):2620-2624.
Wu Yong-hui,et al.Adaptive on-line web topic detection method for web news recommendation system[J].Acta Electronica Sinica,2010,38(11):2620-2624.(in Chinese)
[4]韓立新.對搜索引擎中評分方法的研究[J].電子學(xué)報,2005,33(11):2094-2096.
Han Li-xin.A study on the ranking method of search engines[J].Acta Electronica Sinica,2005,33(11):2094-2096.(in Chinese)
[5]Song Y,Zhang L,et al.Automatic tag recommendation algorithm for social recommender systems[J].ACM Transactions on the Web,2011,5(1):4-39.
[6]李聰.電子商務(wù)協(xié)同過濾可擴展性研究綜述[J].現(xiàn)代圖書情報技術(shù),2010,(11):37-44.
Li Cong.Review of scalability problem in ecommerce collaborative filtering[J].Modern Library and Information Technology,2010,(11):37-44.(in Chinese)
[7]Adomavicius G,Tuzhilin A.Toward the next generation of recommender systems:A survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(6):734-749.
[8]Truong K,Ishikawa F,Honiden S.Improving accuracy of recommender system by item clustering[J].IEICE-Trans Inf Syst,2007,E90-D(9):1363-1373.
[9]張莉,秦桃,滕丕強.一種改進的基于用戶聚類的協(xié)同過濾算法[J].情報科學(xué),2014,32(10):24-28.
Zhang Li,Qin Tao,Teng Pi-qiang.An improved collabrative filtering algorithm based on user clustering[J].Information Science,2014,32(10):24-28.(in Chinese)
[10]Rashid A M,Lam S K,et al.ClustKNN:A highly scalable hybrid model & memory-based CF algorithm[A].Proceedings of the KDD Workshop on Web Mining and Web Usage Analysis[C].Philadelphia,Pennsylvania:ACM,2006.1-59593-444-8.
[11]George T,Merugu S.A scalable collaborative filtering framework based on co-clustering[A].Proceedings of the Fifth IEEE International Conference on Data Mining[C].Washington DC:IEEE Computer Society,2005.625-628.
[12]李弼程,邵美珍,黃杰.模式識別原理與應(yīng)用[M].西安電子科技大學(xué)出版社,2008.2.
Li Bi-cheng,Shao Mei-zhen,Huang Jie.Principle and Application of Pattern Recognition[M].Xidian University Publisher,2008.2.(in Chinese)
[13]Haralambos,Marmanis,Dmitry.智能Web算法[M].電子工業(yè)出版社,2011.7.
[14]KRZYWICKI A,WOBCKE W,CAI X.Interaction-based collaborative filtering methods for recommendation in online dating[A].Web Information Systems Engineering-WISE 2010[C].Berlin Heidelberg:Springer,2010.342-356.
[15]ZHANG J Y,PEARL P.A recursive prediction algorithm for collaborative filtering recommender systems[A].Proceedings of the 2007 ACM Conference on Recommender Systems[C].ACM,2007.57-64.
王興茂男,1989年生于遼寧營口,國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士生,主要研究方向為數(shù)據(jù)挖掘、用戶行為分析、推薦算法.
E-mail:wxmcat@163.com
張興明男,1963年生于河南新鄉(xiāng),國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心教授,主要研究方向為通信與信息系統(tǒng)、寬帶信息網(wǎng)絡(luò)等.
A Collaborative Recommendation Algorithm Based on Heuristic Clustering Model and Category Similarity
WANG Xing-mao,ZHANG Xing-ming,WU Yi-tao,PAN Jun-chi
(National Digital Switching System Engineering and Technological R&D Center,Zhengzhou,Henan 450002,China)
The collaborative recommendation algorithm based on kNN confirms the number of neighbours subjectively,and is not accurate enough to predict by kNN mean weighting calculating.To address these two problems,the maximum and minimum distance clustering algorithm was introduced and improved to design the heuristic clustering model,the model divided the users allodially without the determination of the category numbers,the neighbours of the target users were the users who were in the same category with the target users;then the category similarity was defined to build the category relation between the unscore and score items of the target user in prediction,and the kNN mean weighting calculating was advanced based on the category similarity.The experiments show that this algorithm improves the degree of accuracy(reducing about 0.035 MAE).
collaborative;recommendation algorithm;clustering algorithm;heuristic clustering model;category similarity
2014-12-12;
2015-10-15;責(zé)任編輯:李勇鋒
國家973重點基礎(chǔ)研究發(fā)展計劃(No.2012CB315901);國家863高技術(shù)研究發(fā)展計劃(No.2011AA01A103)
TP393
A
0372-2112 (2016)07-1708-06
??學(xué)報URL:http://www.ejournal.org.cn
10.3969/j.issn.0372-2112.2016.07.027