基于標(biāo)簽與協(xié)同過(guò)濾算法的淘書(shū)吧應(yīng)用

徐 彬，張建明

（江蘇大學(xué) 江蘇 鎮(zhèn)江 212013）

協(xié)同過(guò)濾（Collaborative Filtering，CF）由 Goldberg 等人[1]在1992年提出并首次應(yīng)用在研究郵件推薦模型Tapestry中。協(xié)同過(guò)濾推薦算法的核心思想是利用用戶(hù)的歷史信息，計(jì)算用戶(hù)之間的相似性；利用與目標(biāo)用戶(hù)相似性較高的用戶(hù)對(duì)其他產(chǎn)品的評(píng)價(jià)來(lái)預(yù)測(cè)目標(biāo)用戶(hù)對(duì)特定產(chǎn)品的喜好程度；根據(jù)喜好程度來(lái)對(duì)目標(biāo)用戶(hù)進(jìn)行推薦。協(xié)同過(guò)濾又可分為兩種：基于用戶(hù)的協(xié)同過(guò)濾和基于商品的協(xié)同過(guò)濾。協(xié)同過(guò)濾算法的基本思想是找到與該用戶(hù)行為最相似的其他用戶(hù)，通過(guò)其他用戶(hù)的行為來(lái)預(yù)測(cè)該用戶(hù)的行為，并提出了k最近鄰的思想[2]。本文還將標(biāo)簽屬性加入到推薦算法中，將具有相同標(biāo)簽的書(shū)籍進(jìn)行分類(lèi)，使得內(nèi)容之間的相關(guān)性和用戶(hù)之間的交互性大大增強(qiáng)[3]。協(xié)同過(guò)濾方法已成為電子商務(wù)中非常重要的一種推薦方法。國(guó)外用到協(xié)同過(guò)濾方法比較著名的網(wǎng)站有亞馬遜的網(wǎng)絡(luò)書(shū)店，通過(guò)記錄購(gòu)買(mǎi)的商品以及對(duì)商品的評(píng)分還有瀏覽過(guò)的商品來(lái)判斷您的興趣，然后與其他用戶(hù)的購(gòu)買(mǎi)行為進(jìn)行比較，從而進(jìn)行相似度的分析，最后推薦商品。而國(guó)內(nèi)比較著名的有淘寶，當(dāng)當(dāng)，京東商城。他們利用改良后的協(xié)同過(guò)濾算法，將一系列可能滿足要求的商品推薦給用戶(hù)，以便用戶(hù)的篩選，將用戶(hù)體驗(yàn)做到極致，為網(wǎng)站帶來(lái)了大量的流量。原有的協(xié)同過(guò)濾只依賴(lài)于用戶(hù)對(duì)項(xiàng)目的評(píng)分矩陣，對(duì)于各種特定的應(yīng)用都有較好的適用性，但它也存在一些難以完全解決的問(wèn)題，如新用戶(hù)問(wèn)題、數(shù)據(jù)稀疏性問(wèn)題及可信問(wèn)題等[4]。

文中提出了一種將標(biāo)簽集成到推薦系統(tǒng)的方法，首先對(duì)標(biāo)簽進(jìn)行預(yù)處理，然后構(gòu)建用戶(hù)-商品評(píng)分矩陣，最后將標(biāo)簽混合至用戶(hù)-商品評(píng)分矩陣的協(xié)同過(guò)濾推薦算法中。本文的貢獻(xiàn)如下:1）提出了通用的標(biāo)簽預(yù)處理方法；2）通過(guò)標(biāo)簽預(yù)處理減少推薦過(guò)程中同義標(biāo)簽的計(jì)算，從而提高了推薦算法的性能；3）提出了一種改良后的協(xié)同過(guò)濾方法，該方法可以利用用戶(hù)、產(chǎn)品和標(biāo)簽之間的三維關(guān)系，提高推薦系統(tǒng)的準(zhǔn)確性。

1 基于標(biāo)簽的協(xié)同過(guò)濾推薦算法

1.1 算法描述

1）根據(jù)用戶(hù)對(duì)商品的評(píng)分，建立用戶(hù)-商品評(píng)分矩陣。

2）對(duì)標(biāo)簽進(jìn)行預(yù)處理，整理商品與標(biāo)簽之間的關(guān)系。

3）根據(jù)商品-標(biāo)簽的評(píng)分矩陣來(lái)計(jì)算商品之間的相似度，確定商品的最近鄰，建立物品的協(xié)同過(guò)濾評(píng)分矩陣。

4）綜合商品-標(biāo)簽評(píng)分矩陣和協(xié)同過(guò)濾方法來(lái)計(jì)算預(yù)測(cè)評(píng)分值。

5）按照排名先后將評(píng)分值最高的N個(gè)商品推薦給用戶(hù)。

1.2 用戶(hù)-商品評(píng)分矩陣C（m，n）

在矩陣C（m，n）中，其中m行代表m個(gè)用戶(hù)，n列代表n個(gè)評(píng)分商品，元素Cij表示用戶(hù)i對(duì)商品j的評(píng)分。該方法中用1，2，3，4，5離散值表示對(duì)該商品的偏愛(ài)度。值越大表示用戶(hù)喜愛(ài)程度越高。

表1 用戶(hù)評(píng)分矩陣Tab.1 User rating matrix

1.3 商品-標(biāo)簽評(píng)分矩陣

1.3.1 標(biāo)簽處理

不同類(lèi)型的商品通過(guò)分類(lèi)將其區(qū)別。相同分類(lèi)下的商品，我們通過(guò)設(shè)定不同的標(biāo)簽，將有聯(lián)系的主從關(guān)系的商品聯(lián)系在一起。同一種商品可以使用多個(gè)標(biāo)簽，同一個(gè)標(biāo)簽也可以使用多個(gè)商品。商品和標(biāo)簽之間是多對(duì)多的關(guān)系。我們通過(guò)這種復(fù)雜的關(guān)系，再結(jié)合用戶(hù)瀏覽和購(gòu)買(mǎi)過(guò)的商品所屬的標(biāo)簽。這很少一部分的標(biāo)簽是頻繁用到的，而這些少量頻繁標(biāo)簽集合也是穩(wěn)定的[5]。根據(jù)用戶(hù)與標(biāo)簽的關(guān)系，將用戶(hù)—標(biāo)簽構(gòu)成一個(gè)二部圖，如圖1所示。本系統(tǒng)使用SimRank算法計(jì)算商品之間的相似度。

圖1 用戶(hù)標(biāo)簽二部圖Fig.1 User tags bipartite graph

SimRank算法是在2002年提出的，為了衡量結(jié)構(gòu)性上下文（structural-context）的相似性[6]。SimRank算法的根本就是:相似與同一個(gè)物品的兩個(gè)或兩個(gè)以上物品之間也存在相似性。

基于SimRank算法，我們假定：如果相同或相似的標(biāo)簽都適用于兩個(gè)用戶(hù)，則這兩個(gè)用戶(hù)就存在相似性。構(gòu)造如圖1，標(biāo)簽集合NT和用戶(hù)集合NU，如果用戶(hù)甲和標(biāo)簽A之間存在聯(lián)系，則用有向線段連接用戶(hù)甲與標(biāo)簽A。它們之間的相似性按如下公式計(jì)算:

公式中:u′∈Ut，trust（u，u′）表示用戶(hù) u 與 u′的信任度；O（u）表示用戶(hù)u的出鄰居集合，即由u出發(fā)所指向的標(biāo)簽集合；n 是迭代的次數(shù)；|O（u）|表示用戶(hù) u 的出鄰居數(shù)；A1，A2為常數(shù)，在0～1之間。

1.3.2 綜合相似度計(jì)算

基于傳統(tǒng)的協(xié)同過(guò)濾方法，要求每個(gè)商品的詳細(xì)評(píng)分?jǐn)?shù)據(jù)。但客觀條件決定了用戶(hù)不可能對(duì)每個(gè)商品都進(jìn)行評(píng)分。這就造成了商品的評(píng)分信息不夠全面，導(dǎo)致了評(píng)分矩陣稀疏，在該矩陣上產(chǎn)生的推薦，會(huì)有較大的誤差，對(duì)推薦的準(zhǔn)確度也會(huì)產(chǎn)生比較大的影響。而基于商品標(biāo)簽的協(xié)同過(guò)濾方法，彌補(bǔ)了單一評(píng)分矩陣稀疏的問(wèn)題。常用的用戶(hù)相似度計(jì)算方法有余弦相似性、修正余弦相似性、皮爾森相似性。本文采用皮爾森相似性作為相似度度量標(biāo)準(zhǔn)，將商品的評(píng)分相似度和標(biāo)簽相似度加權(quán)得到綜合相似度：

根據(jù)公式計(jì)算預(yù)測(cè)評(píng)分，將評(píng)分最高的Ns個(gè)項(xiàng)目生成推薦集Cs。對(duì)目標(biāo)用戶(hù)u進(jìn)行預(yù)測(cè)評(píng)分，simsu，v是社交網(wǎng)絡(luò)下經(jīng)過(guò)SimRank算法迭代得到的用戶(hù)u和v的相似性Sn（u，v）。將得到預(yù)測(cè)評(píng)分記為sim（u，p），并將評(píng)分最高的Cs作為推薦結(jié)果。

其中，neighbors（u）是評(píng)價(jià)過(guò)的商品i，且與用戶(hù)u最相似的n個(gè)用戶(hù)的集合。

此方法預(yù)測(cè)用戶(hù)u對(duì)于所有未評(píng)分商品的評(píng)分值，取預(yù)測(cè)評(píng)分值最高的N個(gè)商品推薦給用戶(hù)u。

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

為驗(yàn)證基于標(biāo)簽協(xié)同過(guò)濾算法的有效性，取豆瓣站點(diǎn)（www.douban.com）的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，該站點(diǎn)用戶(hù)可以自由發(fā)表有關(guān)書(shū)籍、電影、音樂(lè)的評(píng)論，可以自動(dòng)進(jìn)行推薦。展現(xiàn)在用戶(hù)面前的大部分內(nèi)容，都是基于每個(gè)用戶(hù)的特點(diǎn)自動(dòng)生成的。我們從該站點(diǎn)得到實(shí)驗(yàn)數(shù)據(jù)集（包括65171個(gè)用戶(hù)和其標(biāo)簽過(guò)的圖書(shū)）。實(shí)驗(yàn)數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集占90%，測(cè)試集占10%。

2.1 結(jié)果評(píng)價(jià)

本文使用平均絕對(duì)誤差 （Mean Absolute Error，MAE）來(lái)評(píng)價(jià)推薦系統(tǒng)的精確性。MAE通過(guò)計(jì)算項(xiàng)目的實(shí)際評(píng)分與預(yù)測(cè)評(píng)分之間的偏差來(lái)計(jì)算預(yù)測(cè)的準(zhǔn)確性。MAE越小，推薦系統(tǒng)的準(zhǔn)確度越高[7]。MAE公式如下：

其中，ruj為用戶(hù)的實(shí)際評(píng)分；puj為用戶(hù)的預(yù)測(cè)評(píng)分；N為預(yù)測(cè)的項(xiàng)目個(gè)數(shù)。

2.2 實(shí)驗(yàn)結(jié)果

為檢驗(yàn)本文提出的基于標(biāo)簽-協(xié)同過(guò)濾方法的有效性，本文參照傳統(tǒng)的協(xié)同過(guò)濾方法，在最近鄰居個(gè)數(shù)取值不同的時(shí)候，對(duì)比2種方法MAE的變化情況。實(shí)驗(yàn)數(shù)據(jù)以下表所示，分別計(jì)算平均絕對(duì)誤差，結(jié)果如圖2所示。

圖2 絕對(duì)評(píng)價(jià)誤差Fig.2 Absolute evaluation errors

由圖2可知，對(duì)比傳統(tǒng)的協(xié)同過(guò)濾方法，本文提出的標(biāo)簽-協(xié)同過(guò)濾方法在同等條件下的MAE值更小，精確度更高。因此，將標(biāo)簽信息和協(xié)同過(guò)濾方法相結(jié)合，可提高推薦系統(tǒng)的準(zhǔn)確度。

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

本文使用的協(xié)同過(guò)濾推薦算法加入了標(biāo)簽屬性。在原有的協(xié)同過(guò)濾算法的基礎(chǔ)上，通過(guò)標(biāo)簽更加精確了算法的推薦程度。并通過(guò)實(shí)驗(yàn)數(shù)據(jù)，客觀的證明了該方法能夠在一定程度上提高了推薦質(zhì)量。

在以后的研究中，我們還要加強(qiáng)對(duì)近義詞，反義詞標(biāo)簽的處理。并且結(jié)合用戶(hù)的檢索，用戶(hù)的購(gòu)買(mǎi)時(shí)間，進(jìn)一步提高相似度的計(jì)算，為用戶(hù)推薦更加精準(zhǔn)的產(chǎn)品。

[1]Goldberg D，Nichols D，Oki B M，et al.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM，1992，35（12）:61－70.

[2]Herlocker J L，Konstan J A，Borchers A，et al.An algorithmic framework for performing collaborative filtering.Proc of the 22nd Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval[M].New York:ACM，1999:230－237.

[3]踏莎而行.小Tag有大智慧[J].電子商務(wù)世界，2006（5）:84-85.Lufthansa riding the line.Small Tag with great wisdom[J].Ecommerce World，2006（5）:84-85.

[4]Chetto H，Chetto M．Some result of the earliest deadline scheduling algorithm [J]．IEEE Trans on Parallel and Distributed Systems，1989，15（10）:1261-1269．

[5]徐雁斐，張亮，劉煒.基于協(xié)同標(biāo)記的個(gè)性化推薦[J].計(jì)算機(jī)應(yīng)用與軟件，2008，25（1）:9-13.XU Yan-fei，ZHANG Liang，LIU Wei.Recommended based on collaborative personalized tag[J].Computer Applications and Software，2008，25（1）:9-13.

[6]Jeh G，Widom J.SimRank:a measure of structural context similarity ［C］//Proc of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining．New York:ACM Press，2002:538-543．

[7]陳志敏，沈潔，趙耀.基于相關(guān)均值的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)工程，2009，35（22）:53-55.CHEN Zhi-min，SHEN Jie，ZHAO Yao.Related to the meanbased collaborative filtering recommendation algorithm[J].Computer Engineering，2009，35（22）:53-55.