基于標簽的評分信息熵推薦算法①

葉 婷

(南京財經(jīng)大學(xué) 信息工程學(xué)院,南京 210046)

基于標簽的評分信息熵推薦算法①

葉 婷

(南京財經(jīng)大學(xué) 信息工程學(xué)院,南京 210046)

由于標簽是由用戶根據(jù)自己的理解和喜好隨意進行標注的因此存在大量的噪聲標簽,導(dǎo)致基于標簽的推薦系統(tǒng)準確率不高.針對這種情況,提出了結(jié)合評分信息熵的標簽推薦算法.算法通過判斷用戶在標注標簽的評分穩(wěn)定程度來確定該標簽對于用戶的重要性從而過濾掉噪聲標簽將重要標簽賦予較高權(quán)重,并構(gòu)建用戶的興趣模型,最后應(yīng)用到協(xié)同過濾算法中產(chǎn)生推薦.該算法能有效地利用評分權(quán)重并結(jié)合信息熵來增強推薦準確率,與以往的基于標簽的推薦算法進行對比,能獲得滿意的推薦效果.

標簽; 評分信息熵; 興趣模型; 協(xié)同過濾; 推薦算法

隨著Internet的迅猛發(fā)展,人們的衣食住行交流溝通方面也漸漸離不開互聯(lián)網(wǎng)技術(shù).然而,互聯(lián)網(wǎng)中充斥著復(fù)雜多樣的信息,網(wǎng)絡(luò)信息過載的問題也日益嚴重.不可否認,搜索引擎的出現(xiàn)和使用在很大程度上給用戶帶來了便利.它可以根據(jù)用戶設(shè)置的檢索條件進行信息匹配,從而推送出相關(guān)信息返回給用戶.這種檢索過程要求用戶能夠明確地表達自己的信息需求,然而并不是所有的需求和偏好都能通過關(guān)鍵字來描述.傳統(tǒng)的搜索引擎技術(shù)已經(jīng)不能滿足用戶的搜索需要,因此個性化推薦技術(shù)孕育而生,且很好的緩解了信息過載問題[1].

由社會化標簽是用戶為方便自己使用對資源的概要描述,它不僅反映了用戶的喜好興趣,還可以反映被標注的資源的特性,因此得到了學(xué)術(shù)界和產(chǎn)業(yè)界的重視.目前已有不少學(xué)者將社會化標簽應(yīng)用到推薦系統(tǒng)中.Marimho等人[2]提出了基于用戶、資源、標簽三元關(guān)分離三個二維二維矩陣,計算向量矩陣的相似度來求得與目標用戶有相似興趣的其他用戶從而進行推薦.Symeonidis[3]根據(jù)社會標簽系統(tǒng)的用戶、項目、標簽數(shù)據(jù)構(gòu)建三階張量模型,并結(jié)合聚類方法以減小張量維度從而簡化推薦運算.Jiang和Zhou等[4]為了提高基于標簽的推薦性能,考慮結(jié)合時間因素以及社會關(guān)系信息從而優(yōu)化推薦結(jié)果.Cao J等[5]提出了一種新的半監(jiān)督學(xué)習(xí)算法,該算法先在少量標注標簽的用戶集中訓(xùn)練得到一個貝葉斯分類器,并融合混合型協(xié)同過濾算法提出Web服務(wù)的雙向推薦機制.以上研究多采用機器學(xué)習(xí)的相關(guān)算法,由于標簽自身的語義模糊等特征且社會化系統(tǒng)中有大量的噪聲標簽存在,導(dǎo)致最終的推薦結(jié)果不是很令人滿意.

盡管目前在社會化標簽的推薦算法上已經(jīng)有很多研究,但大部分的研究多是考慮標簽復(fù)雜的語義信息或是對標簽進行“一視同仁”的處理.然而,由于用戶的認知水平、教育背景存在差異,對事物的理解也會有所差別,因此標簽質(zhì)量的優(yōu)劣也不確定.由此可知,相同的標簽對于不同的用戶來說其重要程度也會有所不同.通常,如果一個標簽多次被一個用戶用來標記資源,則可認為這個標簽對這個用戶的重要程度很高.常用的計算標簽權(quán)重的TF-IDF[6,7]方法就是利用特性將標簽與其他用戶的標簽區(qū)分開來,如果該標簽較少被其他用戶使用,那么該標簽對于該用戶的意義就較大.然而,用戶對于標簽的使用只是出于自身對于資源的理解,并不代表其對于該標簽的喜愛,并且根據(jù)用戶對于標簽標注的資源打分不同,對于同一標簽的喜愛程度也是不同的.

本文考慮引入標簽信息熵的特征實現(xiàn)對標簽區(qū)別對待,之前也有一些應(yīng)用信息熵的信息到推薦系統(tǒng)當(dāng)中.如Saneeha等[8]通過將用戶的興趣特征進行層次聚類,通過計算用戶興趣特征對應(yīng)到各個類簇的比例從而確定各興趣項的熵權(quán)重.Harita等[9]通過用戶對電影數(shù)據(jù)是否感興趣程度分為1、0兩個類別繼而訓(xùn)練最大熵模型和標簽特征并應(yīng)用到推薦系統(tǒng)中.Javier等[10]考慮結(jié)合標簽的評分數(shù)據(jù)來計算用戶興趣項的權(quán)重從而產(chǎn)生推薦.以上研究方法多是通過數(shù)據(jù)挖掘算法和大量的數(shù)據(jù)模型訓(xùn)練計算信息熵,或簡單的結(jié)合評分數(shù)據(jù)計算用戶的興趣項權(quán)重,多是要求用戶主觀上將興趣項分類而不能通過算法自適應(yīng)地修正用戶的興趣項權(quán)重,最終推薦效果一般且耗費大量時間.

因此本文提出了基于評分信息熵的用戶標簽權(quán)重計算方法,通過衡量用戶對標注標簽的資源的打分不確定程度并結(jié)合歸一化的評分數(shù)據(jù)綜合評價用戶標簽權(quán)重,從而構(gòu)建用戶的基于標簽的興趣模型,并應(yīng)用到推薦算法中.

1 基于評分信息熵的用戶標簽權(quán)重計算

在本文中,用戶的興趣模型是通過用戶的標簽數(shù)據(jù)進行構(gòu)建,并融合了用戶的評分、標簽頻數(shù)、標簽信息熵等特征計算興趣項的權(quán)重.其中,U=u1,u2,,u|U|定義為一組用戶,I= i1,i2,,i|I|定義為一組項目,T=t1,t2,,t|T|定義為標注在項目的標簽.總的來說,用戶對項目的評分可以體現(xiàn)用戶對其興趣度,用戶給項目打的標簽體現(xiàn)了用戶對項目的理解,本文聯(lián)系用戶的評分數(shù)據(jù)以及標簽數(shù)據(jù)來計算興趣項權(quán)重從而協(xié)同過濾推薦.

定義1.(用戶—資源評分矩陣)定義為U*I矩陣R(U*I)=(Ri,j),其中U表示用戶集合,I表示資源集合,Ri,j為用戶u對資源i的評分.計算用戶標簽權(quán)重前,先將每個用戶的評分歸一化即用戶u在資源i上標簽t的評分權(quán)重表示為:

定義2.(信息熵)由于同一個標簽可能會被標注在不同的資源中,因此用戶對于同一個標簽可能打分多次.因此給標簽定義信息熵如下:

其中,Tu為用戶u使用的標簽集合,wru,i(t)表示用戶u在標注標簽t上的資源打分,fu(t)表示用戶使用標簽t標注資源的頻數(shù).

2 算法流程

由于標簽和評分數(shù)據(jù)都是用戶根據(jù)自己的理解喜好標注的,所以可以很好的表達用戶的興趣.考慮社會化標簽系統(tǒng)中存在一定的噪聲標簽,因此通過計算標簽的評分信息熵來修正標簽的不確定表達從而增強準確性.本文采用用戶的標簽數(shù)據(jù)表示用戶興趣模型的興趣項,并通分析用戶對于同一個標簽的打分不確定程度確定標簽的信息熵并結(jié)合評分從而計算標簽興趣項的興趣權(quán)重,考慮將用戶對于標注在同個資源的標簽的打分穩(wěn)定性區(qū)別對待,從而能更加精確的表示用戶的興趣.最后將其興趣模型應(yīng)用到協(xié)同過濾算法當(dāng)中.

基于協(xié)同過濾的推薦算法需要得到與目標用戶興趣相似的用戶集合,從而挖掘出這個集合中用戶喜歡的且沒有標注過的資源.為了找到k近鄰相似用戶,我們定義用戶的相似度如下:

對于給定的用戶u∈U,與其相似度較大的k近鄰用戶定義如下:

對于給定用戶的k近鄰用戶,得出用戶u對于未標注的資源i的預(yù)測興趣度定義如下:

則基于標簽的評分信息熵推薦算法表述如下:

第 1步.結(jié)合用戶-評分-資源記錄,根據(jù)公式(1)計算用戶對于標簽的評分權(quán)重并進行歸一化處理.

第2步.結(jié)合用戶在標簽上的不同打分數(shù)據(jù)并計算其對應(yīng)的概率,根據(jù)公式(2)計算不同標簽的信息熵值.

第3步.結(jié)合標簽的信息熵值,根據(jù)公式(3)結(jié)合用戶的評分數(shù)據(jù)修正用戶對于其標簽的興趣度權(quán)重.

第4步.構(gòu)建用戶基于標簽以及評分信息熵權(quán)重的興趣模型{(T1,W1),(T2,W2),…,(Tn,Wn)},其中 T1表示用戶的標簽興趣項,W1表示用戶對應(yīng)的評分信息熵權(quán)重.根據(jù)公式(4)計算用戶相似度,并構(gòu)造用戶的相似度矩陣SN*N.

第5步.基于用戶對資源的歷史記錄,根據(jù)用戶的相似度矩陣SN*N查詢用戶與其他用戶的相似度,并用公式(5)得到用戶的k近鄰用戶,依據(jù)公式(6)依次計算用戶與這些資源的預(yù)測興趣度.

第6步.按預(yù)測興趣度從大到小排序,取前N個資源組成 Top-N 推薦集合并輸出.其中算法的偽代碼如下.

表1 基于標簽的評分信息熵推薦算法

3 實驗

3.1 實驗數(shù)據(jù)

本部分采用MovieLens和Delicious兩組數(shù)據(jù)集來測試算法的效率,具體數(shù)據(jù)集合見表2,數(shù)據(jù)集中的評分數(shù)據(jù)大小在 0.5-5 之間,間隔 0.5,共 10 個分值.為了驗證本文算法的有效性,將本文算法SE-CF與兩個較新的算法tensor-u[11]采用張量分解模型并考慮用戶標簽的語義信息進行推薦與colla-tv[12]結(jié)合TF-IDF算法以及用戶的評分矩陣進行推薦和一個經(jīng)典的基于標簽的推薦算法T-CF[13]進行對比驗證.

表2 數(shù)據(jù)集結(jié)構(gòu)

3.2 度量標準

推薦算法實驗中的重要組成部分之一就是推薦質(zhì)量的評價指標計算,不同推薦算法的評價方法也會有所差別.在本文中,實驗采取的評價指標如下:

(1)準確率(Precision)表示在用戶產(chǎn)生的推薦列表中,有多大比例的資源是用戶真正喜歡的,設(shè)R(u)指用戶在訓(xùn)練集上依據(jù)用戶的行為作出的推薦列表,T(u)表示用戶在測試集中的行為列表.則推薦結(jié)果的準確率定義如下:

(2)召回率(Recall)表示用戶真正喜歡的商品中,有多大比例的商品進入了推薦列表,其計算公式如下:

(3)F-measure,因為準確率和召回率在一定程度上是相互矛盾的,如果推薦的準確率高可能意味著它的召回率會比較低,因此現(xiàn)在實驗中多使用一個平衡以上兩種指標的綜合評價方法即F-measure,其計算公式如下:

3.3 實驗結(jié)果分析

(1)確定鄰居數(shù)k的影響

本部分測試鄰居數(shù)k的值對協(xié)同過濾推薦結(jié)果的影響,其中設(shè)置k的值的變化從10到100,值變化間隔為10,將本文算法SE-CF與算法T-CF在度量標準Recall上進行對比驗證.在協(xié)同過濾算法中,鄰居用戶的數(shù)量k一定程度上影響著推薦精度,k如果太小將無法獲取足夠的候選資源集合,k如果太大也將增加計算成本以及時間消耗.設(shè)置不同的k值,實驗結(jié)果的召回率也會隨之改變,其結(jié)果如圖1所示.

圖1 不同鄰居數(shù) k 值對 Recall變化情況

從圖1可以看出,當(dāng)鄰居數(shù)k的值約為35時,本算法SE-CF和T-CF算法的召回率基本相同,當(dāng)k>35時,本算法SE-CF的召回率才高于T-CF算法.實驗過程分析可得,經(jīng)典T-CF算法是基于用戶共同標注的資源數(shù)目來確定用戶之間的相似度,而SE-CF算法是通過計算用戶標簽的評分信息熵構(gòu)建用戶的標簽興趣模型再計算兩用戶之間的相似程度,相似度的值與用戶共同標注的資源數(shù)目沒有直接關(guān)聯(lián),因此可能存在兩個用戶相似度較大但共同標注的資源很少的現(xiàn)象.如圖1所示,隨著鄰居用戶數(shù)目k的增大,SE-CF算法的召回率的上升速率要明顯高于經(jīng)典T-CF算法.另外,從圖中可以看出兩個算法的召回率在k=70左右趨于穩(wěn)定,k>70時,二者的召回率上升速度都很緩慢,因此在后面的協(xié)同過濾算法比較中設(shè)置鄰居數(shù)k=70.

(2)實驗對比驗證

為了更好的驗證實驗,本文采用五折交叉驗證,每次隨機選取80%的實驗數(shù)據(jù)集作為訓(xùn)練集,剩余20%數(shù)據(jù)為測試集,對五次結(jié)果取平均作為最終結(jié)果,同時考慮在Precision、Recall、F-measure三個度量標準進行比實驗驗證.在本文算法中訓(xùn)練集用于計算用戶標簽的評分信息熵以確定用戶標簽的興趣權(quán)重,并構(gòu)建用戶興趣模型應(yīng)用到協(xié)同過濾推薦算法當(dāng)中,然后測試集中利用訓(xùn)練集得到的推薦結(jié)果進行比較計算.根據(jù)前面的實驗所知,設(shè)k=70,隨著推薦列表的數(shù)量N值的變化,三個度量標準的值也會不同,并將N設(shè)置從5到25變化,值變化間隔為5,實驗數(shù)據(jù)結(jié)果如表3、表4所示.

對比圖示結(jié)果如圖2、圖3所示.

通過上圖的對比可以看出無論推薦列表數(shù)量N取任何值,基于標簽的評分信息算法在準確率、召回率、F-measure三個度量標準都明顯好于其他基于標簽的推薦算法,同時也可以看出基于標簽的評分信息熵推薦算法在N=10時推薦效果最好且比其他幾個推薦算法準確度平均提高了6.7%左右.筆者分析認為,本文算法之所以能優(yōu)于其他三個算法在于:一是考慮將豐富信息量的標簽信息構(gòu)成用戶的興趣模型能較好的表達用戶的興趣; 二是考慮有一定的噪聲標簽的存在因此提出通過計算標簽的打分不確定程度來計算標簽的興趣權(quán)重從而將標簽對用戶的重要性區(qū)別對待,對于打分不穩(wěn)定不能精準表現(xiàn)用戶興趣的標簽可以通過計算其信息熵來修正降低其重要性.

表3 MovieLens實驗數(shù)據(jù)對比

表4 Delicious實驗數(shù)據(jù)對比

圖2 Movielens數(shù)據(jù)集結(jié)果對比

圖3 Delicious 數(shù)據(jù)集結(jié)果對比

4 結(jié)語

本章基于標簽構(gòu)建用戶的興趣模型,并提出了一種用戶標簽評分信息熵的興趣度計算方法,對于用戶重要性高的標簽予以較高的權(quán)重.通過在MovieLens數(shù)據(jù)集和Delicious數(shù)據(jù)集上將本文算法與其他三個算法進行實驗對比,驗證了本文算法要明顯好于其他三個基于標簽的推薦算法.由于用戶的評分信息局限于幾個離散的數(shù)值,因此基于社會化標簽的信息熵計算還不夠準確.目前,將信息熵應(yīng)用于標簽的推薦算法研究還比較新穎,因為信息熵本身有很豐富的解釋信息以及物理背景,因此其應(yīng)用前景還是十分可觀的.

1Verma C,Hart M,Bhatkar S,et al.Improving scalability of personalized recommendation systems for enterprise knowledge workers.IEEE Access,2016,4:204–215.[doi:10.1109/ACCESS.2015.2513000]

2Marinho LB,Schmidt-Thieme L.Collaborative tag recommendations.In:Preisach C,Burkhardt H,Schmidt-Thieme L,et al.eds.Data Analysis,Machine Learning and Applications.Berlin,Heidelberg,Germany.2008.553–540.

3Symeonidis P.ClustHOSVD:Item recommendation by combining semantically enhanced tag clustering with tensor hosvd.IEEE Trans.on Systems,Man,and Cybernetics:Systems,2016,46(9):1240–1251.[doi:10.1109/TSMC.2015.248 2458]

4Jiang ZG,Zhou A,Wang SG,et al.Personalized service recommendation for collaborative tagging systems with social relations and temporal influences.Proc.of the 2016 IEEE International Conference on Services Computing(SCC).San Francisco,CA,USA.2016.786–789.

5Cao J,Wu ZA,Wang YQ,et al.Hybrid collaborative filtering algorithm for bidirectional web service recommendation.Knowledge and Information Systems,2013,36(3):607–627.[doi:10.1007/s10115-012-0562-1]

6Buck C,Koehn P.Quick and reliable document alignment via TF/IDF-weighted cosine distance.Proc.of the 1st Conference on Machine Translation,Volume 2:Shared Task Papers.Berlin,Germany.2016.672–678.

7Chen KW,Zhang ZP,Long J,et al.Turning from TF-IDF to TF-IGM for term weighting in text classification.Expert Systems with Applications:An International Journal,2016,66:245–260.[doi:10.1016/j.eswa.2016.09.009]

8Ahmed S,Tepe K.Entropy-based recommendation trust model for machine to machine communications.Proc.of the 8th International Conference Ad Hoc Networks.Ottawa,Canada.2016.297–305.

9Mehta H,Dixit VS,Bedi P.Weighted difference entropy based similarity measure at two levels in a recommendation framework.Proc.of the 2013 International Conference on Advances in Computing,Communications and Informatics(ICACCI).Mysore,India.2013.2076–2083.

10Parra-Arnau J,Rebollo-Monedero D,Forné J.Optimal forgery and suppression of ratings for privacy enhancement in recommendation systems.Entropy,2014,16(3):1586–1631.[doi:10.3390/e16031586]

11Zhang SW,Ge YY.Personalized tag recommendation based on transfer matrix and collaborative filtering.Journal of Computer and Communications,2015,3(9):9–17.[doi:10.4236/jcc.2015.39002]

12Peng J,Zeng DD,Zhao HM,et al.Collaborative filtering in social tagging systems based on joint item-tag recommendations.Proc.of the 19th ACM International Conference on Information and Knowledge Management.Toronto,ON,Canada.2010.809–818.

13Tso-Sutter KHL,Marinho LB,Schmidt-Thieme L.Tagaware recommender systems by fusion of collaborative filtering algorithms.Proc.of the 2008 ACM Symposium on Applied Computing.New York,USA.2008.1995–1999.

Label-Based Score Information Entropy Recommendation Algorithm

YE Ting
(College of Information and Engineering,Nanjing University of Finance and Economics,Nanjing 210046,China)

As the label is marked by the user according to their own understanding and preferences,the expression of the concept is fuzzy and there are a large number of noise tags,resulting in the low efficiency of the traditional label-based recommendation algorithm recommended.casein view of this problem,a tag recommendation algorithm combining the score information entropy is proposed.The algorithm determines the importance of the tag for the user in order to build the user’s interest model for the rating of the label.The algorithm can effectively use the score weight and combine the information entropy to enhance the recommendation accuracy,and compared with the previous label-based recommendation algorithm,it can get a satisfactory recommendation effect.

tag; score information entropy; interest model; collaborative filtering; recommendation system

葉婷.基于標簽的評分信息熵推薦算法.計算機系統(tǒng)應(yīng)用,2017,26(10):190–195.http://www.c-s-a.org.cn/1003-3254/6003.html

科技部科技支撐項目(BAH29F01); 江蘇省重點研發(fā)計劃(BE2016178)

2017-01-17; 采用時間:2017-02-20