社會化標(biāo)簽語義相似度的協(xié)同過濾算法

諶頏

(廣東技術(shù)師范學(xué)院天河學(xué)院 信息與傳媒學(xué)院， 廣東 廣州 510540)

?

社會化標(biāo)簽語義相似度的協(xié)同過濾算法

諶頏

(廣東技術(shù)師范學(xué)院天河學(xué)院 信息與傳媒學(xué)院， 廣東 廣州 510540)

摘要：為解決傳統(tǒng)的協(xié)同過濾算法不能準(zhǔn)確理解用戶的喜好，影響推薦準(zhǔn)確率和推薦效果，提出基于社會化標(biāo)簽語義相似度的協(xié)同過濾算法.算法以標(biāo)簽語義相似度為基礎(chǔ)，將項(xiàng)目資源和相關(guān)標(biāo)簽的語義信息納入，顯著提高了推薦系統(tǒng)的預(yù)測性能.研究結(jié)果表明：與以具體評分?jǐn)?shù)據(jù)為基礎(chǔ)的算法相比，該算法較好地解決了詞相似度和句子相似度計(jì)算問題，推薦準(zhǔn)確度和性能較以往的協(xié)同過濾算法有明顯提高，改善了推薦效果.

關(guān)鍵詞：協(xié)同過濾； 推薦系統(tǒng)； 社會化標(biāo)簽； 語義相似度； 預(yù)測性能

網(wǎng)絡(luò)信息迅猛增長帶來了日益嚴(yán)重的信息過載問題[1]，個性化推薦系統(tǒng)可幫助用戶在海量信息中有效搜索關(guān)心的資源.這些系統(tǒng)一般采用了基于內(nèi)容、協(xié)同過濾或兩種方法混合的技術(shù)[1-2].雖然這些傳統(tǒng)的推薦技術(shù)應(yīng)用廣泛，但是它們在理解用戶喜好方面存在不足，因此推薦精確度和效果有較大的影響.標(biāo)簽系統(tǒng)為用戶提供了另一種實(shí)現(xiàn)資源推薦的新方法，它是一種提供基于Web的服務(wù)，用戶能使用簡短的語言描述對網(wǎng)頁信息資源進(jìn)行分類的標(biāo)簽技術(shù)[2].此外，標(biāo)簽還為內(nèi)容相似性的比較提供了方法.考慮標(biāo)簽和項(xiàng)目資源的語義差別，本文提出了一種基于社會化標(biāo)簽語義相似度的協(xié)同過濾算法.

1標(biāo)簽的概念模型

標(biāo)簽(tag)是用戶為項(xiàng)目資源自由、隨意添加的一組標(biāo)記或注解，用戶的這種自主行為具有重要的社會意義，它可以更好地幫助用戶組織資源、瀏覽資源和推薦資源[3].為了便于基于經(jīng)驗(yàn)數(shù)據(jù)和模型的標(biāo)簽系統(tǒng)實(shí)現(xiàn)推薦行為，首先要建立一個通用可行的概念模型.考慮到通用性和有效性，研究選擇采用三元組模型，包含用戶集合(users)、標(biāo)簽集合(tags)和項(xiàng)目資源集合(items)等3個實(shí)體集合.

標(biāo)簽系統(tǒng)建立起了用戶、標(biāo)簽和資源三者間的動態(tài)關(guān)系，如圖1所示.用戶集合區(qū)域是用戶空間，包含了該系統(tǒng)中所有用戶集合，每個元素代表一個用戶；標(biāo)簽集合區(qū)域是標(biāo)簽空間，包含了該系統(tǒng)中全部標(biāo)簽集合，每個標(biāo)簽對應(yīng)一個詞(如“Avatar”)或一個短語(如“Forrest Gump”)；項(xiàng)目資源集合區(qū)域則為項(xiàng)目資源空間，包括所有的項(xiàng)目集合，每個項(xiàng)目通常由一個唯一的編號標(biāo)記.

圖1　標(biāo)簽系統(tǒng)的動態(tài)關(guān)系Fig.1　Dynamic relationship of tag system

2標(biāo)簽喜好預(yù)測

2.1　項(xiàng)目交互的預(yù)測方法

一種基于用戶與具有相關(guān)標(biāo)簽的項(xiàng)目交互的預(yù)測方法，如圖2所示.用戶在訪問資源時往往有兩類行為：一是新增、查找、關(guān)注標(biāo)簽的行為；二是用戶瀏覽項(xiàng)目資源時的交互行為，如點(diǎn)擊、瀏覽、評分、收藏等[4].通過對兩類行為的分析可知用戶感興趣的內(nèi)容.研究發(fā)現(xiàn)，如果將項(xiàng)目與標(biāo)簽之間的相關(guān)性作為預(yù)測算法的一個權(quán)重值，則該算法能夠獲得更好的用戶喜好預(yù)測結(jié)果.

圖2　標(biāo)簽的喜好推導(dǎo)Fig.2　Inferring a user′s preference for a tag

2.2　標(biāo)簽與項(xiàng)目的相關(guān)權(quán)重計(jì)算

通過Sigmoid函數(shù)計(jì)算出標(biāo)簽質(zhì)量,相關(guān)權(quán)重值可用標(biāo)簽質(zhì)量計(jì)算.設(shè)標(biāo)簽t與項(xiàng)目i的相關(guān)權(quán)重為w(i，t)，則有

式(1)中：m為標(biāo)簽質(zhì)量,m=TF×IDF,其中，設(shè)某項(xiàng)目所有的標(biāo)簽相關(guān)權(quán)重之和為1.0，TF表示詞頻，指詞條t在文檔d中出現(xiàn)的頻率，IDF表示逆文檔頻率指數(shù)，指詞條t出現(xiàn)的文檔頻率(DF)的反比[5].

2.3　標(biāo)簽喜好推導(dǎo)算法

根據(jù)用戶-系統(tǒng)的交互行為，有多種方法可預(yù)測推導(dǎo)出用戶的標(biāo)簽喜好.用戶對項(xiàng)目的評分能更準(zhǔn)確地表達(dá)用戶的喜好.因此,文中選擇用戶對項(xiàng)目的數(shù)字評分方法，即用項(xiàng)目評級(item-ratings,IR)算法推導(dǎo)用戶的標(biāo)簽喜好.此算法考慮了標(biāo)簽的相關(guān)權(quán)重，即有

式(2)中:u表示用戶；w(i，t)表示項(xiàng)目i和標(biāo)簽t之間的相關(guān)權(quán)重；ru，i表示用戶u對項(xiàng)目i的評分；Mt是所有包含了標(biāo)簽t的項(xiàng)目的集合.然而，該算法的分子和分母的總和都沒有考慮用戶未評價(jià)的項(xiàng)目.在一些網(wǎng)站(如Del.icio.us)可能無法得到精確推導(dǎo)值，但是如果用戶將一個項(xiàng)目添加為其最喜愛，那么就可以認(rèn)為這個用戶是喜歡這些項(xiàng)目的.

2.4　基于標(biāo)簽的推薦算法

預(yù)測出用戶感興趣的標(biāo)簽后，下一步將通過隱式標(biāo)簽(implicit-tag，IT)算法預(yù)測用戶對項(xiàng)目資源的評分.具體方法：預(yù)測項(xiàng)目i的用戶評分，先要計(jì)算出該用戶對項(xiàng)目i之標(biāo)簽的興趣程度，以及標(biāo)簽-項(xiàng)目的相關(guān)權(quán)重w(i，t).用戶對標(biāo)簽的興趣程度用NTP(u，t)表示，Ti表示項(xiàng)目i的所有標(biāo)簽的集合，則預(yù)測用戶u對項(xiàng)目i的評分計(jì)算式為

3基于WordNet的語義相似度算法

通過對MovieLens數(shù)據(jù)分析發(fā)現(xiàn)，標(biāo)簽是一個單詞的情況約占39%，說明大多數(shù)標(biāo)簽是由多個單詞構(gòu)成的短語或句子.因此，計(jì)算標(biāo)簽之間的語義相似度需要分別計(jì)算詞的相似度和句子的相似度.

3.1　詞的相似度算法

詞的相似度是取兩個詞所有概念相似度的最大值[6].計(jì)算兩個同義詞集的語義相似度的方法很多，如Wu & Palmer，Leacock & Chodorow和R. Resnik算法等.兩個詞的相似度(sim-words，SW)的表達(dá)式為

式(4)中:Cl,C2分別表示第一個詞W1和第二個詞W2的所有概念;SIM(Cl,i，C2,j)表示第一個詞的第i個概念和第二個詞的第j個概念的語義相似度.

3.2　句子的相似度算法

假定兩個句子X和Y，其中X的長度為m，Y的長度為n.算法的主要步驟:1) 分詞;2) 提取詞干;3) 詞性標(biāo)注;4) 詞義消歧;5) 將分詞結(jié)果組成詞語義相似度矩陣S[m，n]，若是縮寫詞，如SCI(science citation index)，先查縮寫詞典，再計(jì)算相似度值;6) 采用Hungarian方法將句子語義相似度計(jì)算問題轉(zhuǎn)化成兩個圖的最大匹配權(quán)重計(jì)算問題，取句子X和Y中的詞分別為兩個圖中的定點(diǎn)[7];7) 把前面的計(jì)算步驟合并計(jì)算，得到句子的相似度.

選用Dice相關(guān)系數(shù)計(jì)算句子的相似度(sim-sentences,SS),即

首先，設(shè)一個參照值；然后，依次對所有數(shù)據(jù)對進(jìn)行匹配，若匹配分值超過參照值，說明這兩個詞的語義相似，予以保留[7]；最終，通過式(5)可得匹配關(guān)系值即句子相似度值.例如，給定兩個句子S和T，其長度分別為5和3.根據(jù)圖的匹配算法得到S[1]與T[1]進(jìn)行匹配，其匹配分值是0.8，S[2]與T[2]的匹配分值為0.7，S[3]與T[3]的匹配分值為0.75.使用Dice相關(guān)系數(shù)，設(shè)參照值為0.5，可以看出，3個分值都大于參照值，因此，選擇這3個匹配對.由式(5)計(jì)算可得比值，即句子的相似度為2×(1+1+1)/(5+3) =0.75.

4用戶評分預(yù)測和資源推薦列表的計(jì)算

預(yù)測用戶u對他未曾購買過的項(xiàng)目資源i的評分.一方面,從式(3)可推導(dǎo)出用戶u對標(biāo)簽的喜好NTP(u，t)，從而得到其感興趣的upre標(biāo)簽集合.即設(shè)參照值θ，用戶u添加標(biāo)簽t，如存在NTP(u，t)>θ，則說明用戶對它感興趣，就將它加入到upre標(biāo)簽集合中.另一方面，還要得到與項(xiàng)目相關(guān)度最高的irel標(biāo)簽集合.即設(shè)參照值ω，如果有w(i，t)>ω，則說明此標(biāo)簽與項(xiàng)目相關(guān)度高，就將它加入到irel標(biāo)簽集合中.然后，計(jì)算出upre，irel兩個標(biāo)簽集合的相似度值(SR)，即SR(u，i)=SS(upre，irel).此值就是用戶u對未購買項(xiàng)目i的預(yù)測評分.

需要說明一下，如果把兩個集合中的所有標(biāo)簽(單詞、短語或句子)分別串起來就可以看成是兩個“句子”[8]，那么，采用以上句子相似度算法計(jì)算兩組標(biāo)簽集合的相似度是合理的[9-10].

重復(fù)對用戶u所有未購買過的項(xiàng)目進(jìn)行SR(u，i)的計(jì)算，并將全部預(yù)測評分結(jié)果從大到小排序，取前N個項(xiàng)目資源，即是N推薦列表.

5實(shí)驗(yàn)與分析

實(shí)驗(yàn)選擇MovieLens(http:∥www.grouplens.org)第三組數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，該數(shù)據(jù)集含有71 567名用戶對10 681部電影的10 000 054條評分?jǐn)?shù)據(jù)及95 580個標(biāo)簽.

通過Ntop方法計(jì)算出項(xiàng)目預(yù)測準(zhǔn)確度.首先，將推薦產(chǎn)生的N個資源置于訓(xùn)練集中;然后,檢測N個資源有多少存在于測試集中，量越多算法的準(zhǔn)確度就越高，反之,就越低.

用戶集中全部用戶重復(fù)以上實(shí)驗(yàn)后，計(jì)算得出全體用戶興趣度的平均值.平均Ntop準(zhǔn)確度計(jì)算式為

式(6)中：Iu為設(shè)用戶Ui已標(biāo)注過標(biāo)簽的電影集；U為用戶集合；Rui是訓(xùn)練集中用戶Ui的推薦列表；Iui是用戶Ui測試集中的電影集.如果Npre的值越高，則說明對應(yīng)推薦算法的推薦準(zhǔn)確度越高.

表1　不同算法的預(yù)測準(zhǔn)確度比較

基于CFBTSS算法做了5和10兩組實(shí)驗(yàn)，其中，推薦列表長度分別取5和10，并且分別用Cosine-tag和Implicit-item算法做了同樣的實(shí)驗(yàn)，然后對三者進(jìn)行比較，結(jié)果如表1所示.從表1可以看出：無論推薦列表長度是5還是10，CFBTSS算法結(jié)果皆優(yōu)于另兩種，其推薦準(zhǔn)確度更高.

比較推薦列表的平均評分評價(jià)算法的有效性，分?jǐn)?shù)越高，用戶對推薦結(jié)果就越滿意，算法也越有效.同樣做了推薦列表長度分別為5和10的兩組實(shí)驗(yàn).當(dāng)推薦列表長度為5時，CFBTSS算法的平均分和準(zhǔn)確度為4.3,0.72；當(dāng)推薦列表長度為10時，其平均分和準(zhǔn)確度分別為3.6,0.68.由此可知，推薦列表5的用戶評分平均達(dá)到了4.3顆星，表明用戶比較喜歡這些電影.從實(shí)驗(yàn)結(jié)果看，提出的CFBTSS算法能夠推薦更符合用戶喜好的電影，表示這樣的推薦更有意義.

以上兩個實(shí)驗(yàn)結(jié)果表明：CFBTSS算法的推薦精確度和性能與傳統(tǒng)個性化推薦算法相比有了較大地改善.

6結(jié)束語

文中算法以標(biāo)簽語義相似度為基礎(chǔ)，與以具體評分?jǐn)?shù)據(jù)為基礎(chǔ)的算法相比，具有更好的理解意義和準(zhǔn)確度，對改進(jìn)個性化推薦系統(tǒng)具有重要意義.下一步工作是研究改進(jìn)語義差別計(jì)算的方法及如何更加科學(xué)地描述項(xiàng)目資源的屬性.

參考文獻(xiàn)：

[1]王國霞，劉賀平.個性化推薦系統(tǒng)綜述[J].計(jì)算機(jī)工程與應(yīng)用，2012，48(7):66-74.

[2]BEGELMAN G，KELLER P，SMADJA F.Automated tag clustering: Improving search and exploration in the tag space[C]∥Proceedings of the 15th International Conference on World Wide Web.Edinburgh:ACM Press,2006:1-5.

[3]諶頏.使用分類改進(jìn)標(biāo)簽推薦系統(tǒng)準(zhǔn)確度的研究[J].微電子學(xué)與計(jì)算機(jī)，2011，28(5):96-93.

[4]陳葉旺，李海波，余金山.一種基于農(nóng)業(yè)領(lǐng)域本體的語義檢索模型[J].華僑大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012,33(1):27-32.

[5]楊現(xiàn)民，余勝泉.學(xué)習(xí)資源語義特征自動提取研究[J].中國電化教育，2013(11):74-80.

[6]符征.語義引擎的形成及其應(yīng)用[J].自然辯證法研究,2013(11):21-25.

[7]鄧雙義.基于語義的標(biāo)簽推薦系統(tǒng)關(guān)鍵問題研究[D].上海：華東師范大學(xué)，2009:37-41.

[8]許棣華,王志堅(jiān),林巧民,等.一種基于偏好的個性化標(biāo)簽推薦系統(tǒng)[J].計(jì)算機(jī)應(yīng)用研究,2011(7):2573-2579

[9]崔林,宋瀚濤,陸玉昌.基于語義相似性的資源協(xié)同過濾技術(shù)研究[J].北京理工大學(xué)學(xué)報(bào),2005,25(5):402-405.

[10]荀恩東,顏偉.基于語義網(wǎng)計(jì)算英語詞語相似度[J].情報(bào)學(xué)報(bào),2006,25(1):43-48.

(責(zé)任編輯： 黃曉楠英文審校： 吳逢鐵)

Collaborative Filtering Algorithm Based on

Social Tags Semantic Similarity

CHEN Hang

(Information and Communication College, Tianhe College of

Guangdong Polytechnic Normal University， Guangzhou 510540， China)

Abstract：In order to solve the traditional collaborative filtering algorithm can not accurately understand the user′s preferences, affect the recommendation accuracy and recommendation effect, a collaborative filtering algorithm based on social tags semantic similarity is proposed. Based on the semantic similarity of tags, the semantic information of project resources and related tags is included, and the prediction performance of the recommendation system is significantly improved. Research results show that: compared with the algorithm based on the user rating, the proposed algorithm can solve the problem of word similarity and sentence similarity computation, and the recommendation accuracy and recommendation effect, as well as the performance of the proposed algorithm is significantly improved compared with the previous collaborative filtering algorithm.

Keywords：collaborative filtering； recommendation system； social tags； semantic similarity； prediction performance

基金項(xiàng)目：廣東省高等學(xué)校學(xué)科與專業(yè)建設(shè)專項(xiàng)(2013LYM0110)； 廣東省教育科學(xué)規(guī)劃專項(xiàng)(14JXN060)

通信作者：諶頏(1980-)，男，高級工程師，主要從事網(wǎng)絡(luò)信息系統(tǒng)、數(shù)據(jù)挖掘和個性化推薦技術(shù)的研究.E-mail:toboby@126.com.

收稿日期：2015-11-13

中圖分類號：TP 301.6

文獻(xiàn)標(biāo)志碼：A

doi:10.11830/ISSN.1000-5013.2016.01.0084

文章編號：1000-5013(2016)01-0084-04