陳伶紅，徐華中，李 鮑，吳友宇

(1.武漢理工大學(xué) 自動化學(xué)院，湖北 武漢 430070；2.武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢 430070)

?

一種基于用戶對項目屬性偏好的推薦算法

陳伶紅1，徐華中1，李 鮑1，吳友宇2

(1.武漢理工大學(xué) 自動化學(xué)院，湖北 武漢 430070；2.武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢 430070)

針對協(xié)同過濾推薦算法中存在的數(shù)據(jù)稀疏性問題，提出了一種基于用戶偏好模型的混合聚類推薦算法。利用用戶-項目評分矩陣參考TF-IDF和信息熵的原理得到了用戶對項目屬性的偏好模型，并以此為基礎(chǔ)數(shù)據(jù)進(jìn)行用戶聚類、相似度計算和最近鄰查詢，然后對用戶未評分的項目進(jìn)行評分預(yù)測，進(jìn)而產(chǎn)生推薦。實(shí)驗(yàn)表明，基于用戶對項目屬性偏好的混合聚類推薦算法與傳統(tǒng)的協(xié)同過濾和基于用戶-項目評分矩陣的聚類算法相比，在推薦精度上表現(xiàn)出一定的優(yōu)越性。

推薦算法；協(xié)同過濾；用戶偏好；SOM；K-means

隨著信息技術(shù)和互聯(lián)網(wǎng)的發(fā)展，人們逐漸從信息匱乏的時代走入了信息過載的時代。推薦系統(tǒng)能夠有效地解決信息過載問題，在電子商務(wù)領(lǐng)域得到了廣泛的應(yīng)用，其中推薦算法則是最核心的技術(shù)點(diǎn)。協(xié)同過濾推薦算法是目前最為成熟的一種推薦算法[1]，可分為基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾。基于用戶的協(xié)同過濾推薦算法主要是依據(jù)用戶的歷史評分?jǐn)?shù)據(jù)計算用戶間的相似度，找到目標(biāo)用戶的最近鄰居，目標(biāo)用戶對未評分項目的評分可以通過其近鄰對該項目的評分進(jìn)行預(yù)測，將評分最高的前N個項目推薦給目標(biāo)用戶。但是隨著電子商務(wù)系統(tǒng)規(guī)模的擴(kuò)大，用戶數(shù)量和項目數(shù)量的增加，導(dǎo)致用戶-項目評分?jǐn)?shù)據(jù)出現(xiàn)嚴(yán)重的稀疏性，用戶相似度計算十分耗時，并且很難找到相似的用戶集，使得推薦質(zhì)量下降。為此，許多學(xué)者將數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的方法與協(xié)同過濾相結(jié)合。如曹渝昆提出了一種基于Web挖掘和Fuzzy Art神經(jīng)網(wǎng)絡(luò)的電子商務(wù)顧客分類方法，可以縮小目標(biāo)顧客的鄰居用戶搜索范圍，縮短推薦時間[2]，但是此方法主要挖掘的是隱式數(shù)據(jù)，對數(shù)據(jù)處理技術(shù)要求較高；成桂蘭等提出一種基于SOM和K-means混合聚類的推薦算法[3]，該方法在一定程度上縮短了最近鄰查詢時間，提高了推薦效率和推薦質(zhì)量，但是稀疏的用戶-項目評分?jǐn)?shù)據(jù)使得某些可能相似的用戶因缺少共同評分項目而導(dǎo)致相似度較低；胡新明提出了一種引用文本分類中的TF-IDF算法將用戶對商品的評分矩陣轉(zhuǎn)化為用戶對商品屬性評分矩陣的推薦算法，在較少數(shù)據(jù)量的情況下得到與基于用戶商品評分矩陣推薦算法同質(zhì)量甚至更高質(zhì)量的推薦結(jié)果[4]，但是該方法忽略了商品屬性在不同商品集合間以及商品集合內(nèi)的分布情況；袁漢寧等提出了基于MI聚類的協(xié)同推薦算法[5]，通過多示例聚類計算用戶的最近鄰居集，但是在計算用戶間相似度時仍然使用用戶-項目評分?jǐn)?shù)據(jù)，稀疏的用戶-項目評分?jǐn)?shù)據(jù)使得某些可能相似的用戶因缺少共同評分項目而導(dǎo)致相似度較低。

針對上述問題，筆者提出了一種基于用戶對項目屬性偏好模型的混合聚類推薦算法，考慮到項目屬性在用戶喜歡和不喜歡的集合間以及集合內(nèi)的分布情況，借鑒文本分類中TF-IDF算法并引進(jìn)信息熵建立用戶對項目屬性的偏好模型，然后用SOM算法對該模型中的用戶進(jìn)行粗聚類，將其聚類中心和聚類簇數(shù)目作為K-means聚類算法的初始聚類質(zhì)心和聚類簇數(shù)目，在目標(biāo)用戶所在的聚類簇中計算用戶相似度并尋找近鄰，對未評分的項目進(jìn)行預(yù)測。

1 用戶偏好模型

用戶對項目屬性的偏好模型是進(jìn)行用戶聚類和相似度計算的基礎(chǔ)，通過分析用戶-項目評分矩陣和項目-屬性矩陣，建立用戶對項目中出現(xiàn)的所有屬性的偏好權(quán)重矩陣。

考慮包含m個用戶和n個項目的系統(tǒng)，令用戶集合U={U1,U2,…,Um}(i=1,2,…,m)，項目集合I={I1,I2,…,In}(j=1,2,…,n)，用戶-項目評分矩陣如表1所示，其中元素rij表示第i個用戶對第j個項目的評分值。

表1 用戶-項目評分矩陣

項目屬性集合表示為F={f1,f2,…,fs}(k=1,2,…,s)，項目-屬性矩陣如表2所示，其中元素ajk表示項目Ij的特征屬性：

(1)

參考TF-IDF算法的原理，如果屬性fj在集合Li中出現(xiàn)的次數(shù)越多，說明用戶越偏好具有該屬性的項目，則屬性fj應(yīng)該賦予較大的權(quán)重。根據(jù)以上論述得到偏好權(quán)重wik為：

(2)

但由式(2)得出的用戶對項目屬性的偏好權(quán)重存在如下問題：①沒有考慮到屬性fj在集合Li和集合Qi之間的分布情況。如果屬性fj在集合Li中出現(xiàn)較多，而在集合Qi中出現(xiàn)較少，則說明用戶比較偏好具有該屬性的項目，該屬性應(yīng)該賦予較高的權(quán)重。如果屬性fj比較均勻地分布在集合Li和Qi中，說明用戶對具有該屬性的項目沒有特別偏好，該屬性值應(yīng)該賦予較低的權(quán)重。②沒有考慮到屬性fj在集合Li中的分布情況。在集合Li中出現(xiàn)頻率較高的屬性的權(quán)重應(yīng)該比出現(xiàn)頻率較低的屬性要高。如果屬性fj在集合Li中出現(xiàn)的頻率較低，則該屬性應(yīng)該被賦予較小的權(quán)重?？紤]到以上兩種情況，參考文獻(xiàn)[6]在文本分類中引入信息熵來改善TF-IDF算法，引進(jìn)信息熵來計算用戶對項目屬性偏好的模型。

若給定的概率分布為P=(p1,p2,…,pn)，則由該分布傳遞的信息量稱為P的熵，即：

(3)

屬性fj在集合Li和Qi中的概率分布為Poc=(NLik/NRik,NQik/NRik)(其中NQik表示集合Qi中具有屬性fj的項目個數(shù))，記Hoc(Poc)為屬性fj的類間信息分布熵。屬性fj在集合Li中的概率分布為Pic=NLik/NLi，記Hic(Pic)為屬性fj的類內(nèi)信息分布熵。

由以上分析可知，Hoc(Poc)越大則屬性fj的權(quán)重越小，Hic(Pic)越大則屬性fj的權(quán)重越大。得到改進(jìn)后的用戶Ui對屬性fj的偏好權(quán)重為：

(4)

其中對Hoc做了一定的修改，常數(shù)1是為了防止Hoc(Poc)=0，使得1/(Hoc+1)分布在[0，1]區(qū)間。根據(jù)式(4)建立用戶-項目屬性偏好矩陣如表3所示。

表3 用戶-項目屬性偏好矩陣

2 推薦過程

推薦算法主要分為5個過程：生成用戶-項目屬性偏好模型、用戶聚類、用戶相似度計算和最近鄰居查詢、評分預(yù)測、生成推薦。

(1)生成用戶-項目屬性偏好模型。通過式(4)生成用戶-項目屬性偏好模型，作為用戶聚類和相似度計算的數(shù)據(jù)基礎(chǔ)。

(2)用戶聚類。為了縮短用戶相似度計算的時間、縮小用戶最近鄰居查詢范圍，需要對用戶進(jìn)行聚類，將用戶-項目屬性偏好矩陣中項目屬性偏好比較相似的用戶分配到同一聚類簇中，使同一聚類簇中的用戶相似度盡可能高，不同聚類簇中的用戶相似度盡可能低。常用的聚類算法有SOM神經(jīng)網(wǎng)絡(luò)、K-means聚類算法、層次聚類算法、FCM聚類算法等[7]。SOM算法進(jìn)行聚類時，網(wǎng)絡(luò)收斂時間過長，通常網(wǎng)絡(luò)需要訓(xùn)練上萬次才能收斂。K-means算法的初始聚類質(zhì)心選擇不當(dāng)，很難得到較好的聚類效果，在大規(guī)模數(shù)據(jù)集上收斂較慢。因此采用SOM與K-means聚類相結(jié)合的混合聚類模型對用戶進(jìn)行聚類，聚類流程為：①將步驟(1)中得到的用戶-項目屬性偏好矩陣作為聚類的輸入數(shù)據(jù)，通過SOM對輸入訓(xùn)練較少的次數(shù)進(jìn)行粗聚類，輸出聚類簇ClusterSOM、神經(jīng)元的權(quán)值ωSOM、聚類簇數(shù)目K；②將ωSOM作為原始質(zhì)心Ooriginal，對于每一個簇內(nèi)元素不為0的聚類簇，尋找與Ooriginal距離最近的元素作為該簇最終的質(zhì)心OSOM；③以K、OSOM作為K-means聚類的聚類簇數(shù)目和初始聚類質(zhì)心，對用戶進(jìn)一步聚類，輸出用戶聚類結(jié)果ClusterResult。

(3)用戶相似度計算和最近鄰居查詢。計算目標(biāo)用戶Ui與所在聚類簇cindex中其他用戶的相似度。用戶相似性的度量標(biāo)準(zhǔn)主要有余弦法、修正余弦法和基于相關(guān)性的相似性度量等[8]，筆者選用余弦法來計算用戶間的相似度：

(5)

其中，ωu和ωv分別為用戶u和用戶v的項目屬性偏好向量。

(6)

(4)評分預(yù)測。找到目標(biāo)用戶Ui針對目標(biāo)項目Iij的最近鄰用戶集合MKnear后，通過集合MKnear中的用戶對目標(biāo)項目Iij評分的加權(quán)平均值來描述目標(biāo)用戶Ui對目標(biāo)項目Iij的評分。評分預(yù)測公式為：

(5)生成推薦。重復(fù)步驟(3)和步驟(4)，預(yù)測目標(biāo)用戶Ui對所有未評分項目的評分，選擇預(yù)測評分最高的N個項目推薦給目標(biāo)用戶Ui。

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

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

實(shí)驗(yàn)采用MovieLens(ml-100K)數(shù)據(jù)集，該數(shù)據(jù)集包含了943個用戶對1 682部電影的10萬個評分。實(shí)驗(yàn)采用五折交叉驗(yàn)證法，將實(shí)驗(yàn)數(shù)據(jù)平分成5個互不相交的數(shù)據(jù)子集，每次選擇其中一個數(shù)據(jù)子集作為測試集，其余4個子集作為訓(xùn)練集，如此循環(huán)5次，取每次實(shí)驗(yàn)結(jié)果的平均值作為最終結(jié)果。當(dāng)用戶對項目的評分過少時，難以發(fā)現(xiàn)用戶對項目屬性的偏好，因此在每次實(shí)驗(yàn)中，找出測試集中評分項目少于20個的用戶，從測試集和測試集中剔除這些用戶的評分?jǐn)?shù)據(jù)。MovieLens數(shù)據(jù)集中的項目是電影，根據(jù)電影類別，將電影劃分為19個類別，0～18分別代表19個項目類別屬性，如表4所示。電影類別屬性為Unknown的電影不能表示出用戶對某一具體屬性的偏好程度，因此將電影類別屬性為Unknown的項目從訓(xùn)練集和測試集中剔除。

表4 電影類別屬性

3.2 性能評價

實(shí)驗(yàn)采用平均絕對誤差MAE[9]來度量推薦的準(zhǔn)確性，MAE值越低推薦結(jié)果越準(zhǔn)確，其計算公式為：

(8)

式中：pi為預(yù)測評分；qi為實(shí)際評分。

3.3 結(jié)果分析

根據(jù)HERLOCKER等[10]的研究結(jié)果，在真實(shí)環(huán)境中最近鄰用戶數(shù)量設(shè)置為20～50比較合理，筆者采用的MovieLens數(shù)據(jù)集共有943個用戶，設(shè)置SOM的輸出神經(jīng)元數(shù)目為6×6，鄰居查詢個數(shù)Knear=[5 10 15 20 25 30 35 40 45 50 55 60 65 70]來進(jìn)行對比實(shí)驗(yàn)，以驗(yàn)證筆者提出算法的優(yōu)越性。

將筆者提出的利用TF-IDF和信息熵挖掘用戶偏好模型，進(jìn)行SOM+K-means聚類和用戶相似度計算的推薦算法稱為算法1；將利用TF-IDF挖掘用戶偏好模型，進(jìn)行SOM+K-means聚類和用戶相似度計算的推薦算法稱為算法2；將利用用戶-項目評分矩陣，進(jìn)行SOM+K-means聚類和用戶相似度計算的推薦算法稱為算法3；將傳統(tǒng)的基于用戶的協(xié)同過濾推薦算法稱為算法4；將基于MI聚類的協(xié)同推薦算法稱為算法5(根據(jù)文獻(xiàn)[5]中的描述，選擇聚類個數(shù)K=20時推薦效果最好，選擇表4中1～18的電影屬性類別作為實(shí)例的內(nèi)容特征)。

圖1 算法1～算法5的對比實(shí)驗(yàn)結(jié)果

圖1所示為算法1～算法5的對比實(shí)驗(yàn)結(jié)果，可以看出基于SOM+K-means聚類的推薦算法比傳統(tǒng)的協(xié)同過濾推薦算法效果更好；使用用戶偏好模型進(jìn)行聚類和相似度計算的推薦效果比使用用戶-項目評分矩陣的推薦效果更好；使用TF-IDF和信息熵相結(jié)合挖掘的用戶偏好模型比使用TF-IDF挖掘的用戶偏好模型的推薦效果更好。算法1、算法2比算法5的效果好，算法5比算法3、算法4的效果更好，說明算法5通過多示例聚類得到的最近鄰集合，比以用戶-項目評分矩陣為數(shù)據(jù)基礎(chǔ)進(jìn)行聚類得到的最近鄰居集合更為準(zhǔn)確。由于算法5計算用戶相似度時使用的是用戶-項目評分矩陣，不能更好地挖掘用戶間的相似性，使得推薦結(jié)果不如算法1準(zhǔn)確。

圖2所示為算法1、算法2、算法4的用戶相似度計算、最近鄰查詢及評分預(yù)測的時間，可以看出當(dāng)15

圖2 不同算法的相似度計算、最近鄰查詢及評分預(yù)測的時間

圖3 不同SOM聚類中心下推薦算法的實(shí)驗(yàn)結(jié)果

圖3所示為不同SOM聚類中心下推薦算法的實(shí)驗(yàn)結(jié)果。SOM聚類結(jié)束時，外星權(quán)向量位于輸入向量聚類的中心，該實(shí)驗(yàn)中SOM訓(xùn)練次數(shù)較少并未完全收斂，因此選擇各聚類簇中離外星權(quán)向量最近的一點(diǎn)作為SOM的聚類中心(Center1),文獻(xiàn)[3]將SOM聚類結(jié)束時各聚類簇中元素的平均值作為SOM的聚類中心(Center2)，Center1的推薦效果較Center2要好，即SOM聚類中心的選取比文獻(xiàn)[3]更合理。

4 結(jié)論

筆者為了解決評分矩陣稀疏性問題，通過TF-IDF算法和信息熵生成用戶對項目屬性偏好的模型，然后以此為數(shù)據(jù)基礎(chǔ)進(jìn)行用戶聚類和相似度計算，使得相似用戶之間的相關(guān)性增強(qiáng)，縮短了最近鄰用戶的查詢時間，通過五折交叉對比實(shí)驗(yàn)得出，筆者提出的算法具有更高的推薦質(zhì)量和效率。但筆者研究的前提是假設(shè)用戶興趣不會發(fā)生變化，然而在實(shí)際研究中，用戶的興趣是會隨時間發(fā)生變化的，因此需要將時間因素同項目屬性等結(jié)合起來，以提高推薦系統(tǒng)的準(zhǔn)確性，這將是下一步研究的重點(diǎn)。

[1] 劉魯,任曉麗.推薦系統(tǒng)研究進(jìn)展及展望[J].信息系統(tǒng)學(xué)報,2008 (1): 82-90.

[2] 曹渝昆.基于神經(jīng)網(wǎng)絡(luò)和模糊邏輯的智能推薦系統(tǒng)研究[D].重慶：重慶大學(xué)，2006.

[3] 成桂蘭，劉旭東，陳德人.基于混合聚類的個性化推薦算法[J].武漢理工大學(xué)學(xué)報(信息與管理工程版)，2011，33(3)：379-381.

[4] 胡新明.基于商品屬性的電子商務(wù)推薦系統(tǒng)研究[D].武漢：華中科技大學(xué)，2012.

[5] 袁漢寧，周彤，韓言妮.基于MI聚類的協(xié)同過濾推薦算法[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，2015，40(2)：253-257.

[6] 李原.中文文本分類中分詞和特征選擇方法研究[D].長春：吉林大學(xué)，2011.

[7] 馮曉蒲，張鐵峰.四種聚類方法之比較[J].微型機(jī)與應(yīng)用，2010，29(16)：1-3.

[8] SARWAR B, KARYPIS G, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms[C]∥Proceedings of the 10th International Conference on World Wide Web. [S.l.]:[s.n.], 2001: 285-295.

[9] KARYPIS G. Evaluation of item-based top-n recommendation algorithms[C]∥Proceedings of the Tenth International Conference on Information and Knowledge Management. [S.l.]:[s.n.], 2001: 247-254.

[10] HERLOCKER J L, KONSTAN J A, BORCHERS A, et al. An algorithmic framework for performing collaborative filtering[C]∥Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.[S.l.]:[s.n.], 1999:230-237.

CHEN Linghong:Postgraduate; School of Automation, WUT, Wuhan 430070, China.

A Recommendation Algorithm Based on Users’ Preference of Item Features

CHENLinghong,XUHuazhong,LIBao,WUYouyu

Considering the problem of data sparsity in traditional collaborative filtering recommendation algorithm, a hybrid clustering recommendation algorithm based on users’ preference is proposed. The users’ preference model is obtained by using user-item rating matrix and referring to the principle of TF-IDF and information entropy, which is the basic data of users clustering, similarity calculation and nearest neighbor query. Item recommendation is accomplished after predicting the rates for the no-rated items. Experiment shows that the hybrid clustering recommendation algorithm based on user p

for project attributes has some advantages over the traditional collaborative filtering and clustering algorithm based on user-item scoring matrix.

recommendation algorithm; collaborative filtering; users’ preference; SOM; K-means

2095-3852(2016)05-0616-05

A

2016-05-25.

陳伶紅(1991-)，女，湖北武漢人，武漢理工大學(xué)自動化學(xué)院碩士研究生.

TP301.6 DOI：10.3963/j.issn.2095-3852.2016.05.021