協(xié)同標(biāo)簽系統(tǒng)中基于標(biāo)簽組合效應(yīng)的推薦算法*

蔡毅 劉宇 張廣怡 陳俊挺 閔華清

(華南理工大學(xué)軟件學(xué)院，廣東廣州510006)

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，推薦系統(tǒng)已廣泛應(yīng)用于電子商務(wù)與社交網(wǎng)絡(luò)平臺［1］．在這些電子商務(wù)平臺中存在著大量的用戶個性化信息．對這些信息進行分析并將結(jié)果運用到這些平臺中無疑會給用戶帶來更好的個性化服務(wù)．

協(xié)同標(biāo)簽系統(tǒng)允許用戶使用標(biāo)簽來描述自己評價過的資源(如電影、網(wǎng)頁、書籍、音樂等)．采用標(biāo)簽來標(biāo)注資源有助于資源的組織、檢索和共享．當(dāng)前很多用于協(xié)同標(biāo)簽系統(tǒng)的推薦方法通過分析用戶過去的行為來對用戶進行建模，以分析用戶的喜好．這些方法主要采用向量空間模型對用戶進行建模，即一個用戶由一個包含該用戶標(biāo)注過的所有標(biāo)簽的向量來表示．在這種用戶模型中，用戶對一個資源的喜好程度正比于其對該資源任意一個特征的喜好程度，故忽略了特征間的組合效應(yīng)．但特征間的組合有可能會改變特征原有的屬性，即用戶的喜好程度．

為此，文中提出了一種基于標(biāo)簽組合效應(yīng)的推薦算法(TGER)，并將其應(yīng)用于協(xié)同標(biāo)簽系統(tǒng)中的資源推薦．首先，在原有的向量空間模型的基礎(chǔ)上，通過分析用戶對商品的評分與對該商品標(biāo)注的標(biāo)簽的關(guān)系獲取那些造成用戶對資源評分具有穩(wěn)定影響的標(biāo)簽集合，計算標(biāo)簽組合聚集強度，即標(biāo)簽組合影響該用戶對資源評分的穩(wěn)定程度．由于標(biāo)簽組合可能含有多個標(biāo)簽(稱為多維標(biāo)簽組合)，因此需要通過對較低維標(biāo)簽組合的聚集強度進行過濾以得到較高維的標(biāo)簽組合，即穩(wěn)定影響用戶對資源喜好程度的標(biāo)簽組合，并建立一個標(biāo)簽組合效應(yīng)矩陣．然后計算待推薦商品在矩陣中的最高維標(biāo)簽組合對用戶評分產(chǎn)生影響的權(quán)值，最后整合這些權(quán)值可得出用戶對目標(biāo)商品的最終預(yù)測評分．

1 背景與相關(guān)工作

1．1 推薦方法

當(dāng)前的推薦方法主要有基于內(nèi)容的推薦方法、協(xié)同過濾推薦方法及混合推薦方法．基于內(nèi)容的推薦方法通過將目標(biāo)商品與活躍用戶曾經(jīng)評價過的商品進行相似度比較，將與活躍用戶喜歡的商品類似的目標(biāo)商品推薦給用戶［2］．協(xié)同過濾推薦方法分為基于項目的和基于用戶的兩類［3］．基于項目的協(xié)同過濾推薦方法與基于內(nèi)容的推薦方法的最大區(qū)別在于相似度的計算策略，前者通過商品或用戶的社會關(guān)系來計算二者的相似度，而后者則通過比較商品間“內(nèi)容”的相似程度得出．為避免這兩種方法的缺點，一些學(xué)者將這兩種方法結(jié)合起來，提出了混合推薦方法．文獻(xiàn)［4］中對混合推薦方法做了詳細(xì)的分類．文獻(xiàn)［5-7］中探討了一些混合推薦方法及其實現(xiàn)．

與基于內(nèi)容的推薦方法相比，協(xié)同過濾推薦方法在很大程度上因不需要依賴于商品的內(nèi)容數(shù)據(jù)而被更為廣泛地運用到社交網(wǎng)絡(luò)與電子商務(wù)等領(lǐng)域的推薦系統(tǒng)中．學(xué)術(shù)界對協(xié)同過濾推薦方法進行了廣泛而深入的研究，許多改進的協(xié)同過濾推薦方法也迅速發(fā)展起來．文獻(xiàn)［8］中探討了協(xié)同過濾推薦方法的性能與效率．在眾多的協(xié)同過濾推薦方法中，基于矩陣分解的協(xié)同過濾推薦方法［9］較為流行．

1．2 協(xié)同標(biāo)簽系統(tǒng)中的用戶模型

在協(xié)同標(biāo)簽系統(tǒng)中，許多推薦方法通過用戶歷史行為和信息對用戶進行建模，其中向量空間模型是一種比較常見的用戶模型．

在向量空間模型中，用戶被映射到標(biāo)簽向量的一個空間．這個向量空間中每個標(biāo)簽的權(quán)重反映了用戶對該標(biāo)簽感興趣的程度，權(quán)重值在［0，1］區(qū)間上．如果權(quán)重值越接近1，意味著用戶對此標(biāo)簽表現(xiàn)出越多的興趣．向量空間模型中標(biāo)簽權(quán)重的計算方法有詞頻(TF)及詞頻-逆用戶頻率(TF-IUF)［10］．通常采用TF和詞頻-逆資源頻率(TF-IRF)方法來計算每個標(biāo)簽在資源向量中的權(quán)值．

文獻(xiàn)［11］中提出的標(biāo)簽權(quán)值計算指標(biāo)歸一化詞頻(NTF)反映了用戶使用該標(biāo)簽的可能性或概率，故可以更恰當(dāng)?shù)胤从秤脩魧?biāo)簽的感興趣程度．

由于標(biāo)簽是一種文本數(shù)據(jù)，故其包含了特定的用戶語義．在向量空間模型中，如果將向量中的元素視為商品或用戶的特征，則可以得到特征向量模型．文獻(xiàn)［12-15］中探討了這一模型的幾種實現(xiàn)方式．

然而，目前所使用的協(xié)同標(biāo)簽系統(tǒng)的用戶建模方法大都只分別存儲單個標(biāo)簽的權(quán)值，因而無法體現(xiàn)標(biāo)簽組合對原來標(biāo)簽權(quán)值可能造成的改變，但此改變可以使用戶更喜歡或不喜歡某個資源．例如，艾米是美國人，她喜愛包含“辣”或“雞”元素的菜(如麻婆豆腐、白切雞)，但不喜歡“辣子雞”．另一方面，艾米討厭大蒜和菠菜，但對蒜蓉菠菜情有獨鐘．

針對上述問題，文獻(xiàn)［16］中采用標(biāo)簽協(xié)同效應(yīng)矩陣來儲存每個用戶使用過的任意兩個標(biāo)簽間的組合效應(yīng)特征值．受其啟發(fā)，文中對二維標(biāo)簽協(xié)同效應(yīng)矩陣進行擴展，使該矩陣儲存的不僅僅是兩個標(biāo)簽間的效應(yīng)特征值，還包括任意多個標(biāo)簽間的效應(yīng)特征值，以使推薦結(jié)果更為準(zhǔn)確．

2 TGER算法的建立

2．1 標(biāo)簽組合效應(yīng)

標(biāo)簽組合效應(yīng)是指不同的標(biāo)簽組合對用戶喜好有不同程度的影響．而用戶喜好可以理解為用戶對商品的感興趣程度，具體可以表現(xiàn)為對商品的評分．

標(biāo)簽組合是一個或多個標(biāo)簽的集合，即fk={t1，t2，…，tk}，k 為 f的維度．

為了量化標(biāo)簽組合效應(yīng)，需要賦予其兩個特征屬性:標(biāo)簽聚集強度和標(biāo)簽組合權(quán)值．

首先作如下假設(shè):若用戶i對包含標(biāo)簽組合的商品的評分波動很大，則該標(biāo)簽組合對用戶i的喜好的影響不明顯;否則，其對用戶i的喜好有較為強烈的影響．

用標(biāo)簽聚集強度Ifki表示標(biāo)簽組合fk影響用戶i喜好的穩(wěn)定程度，其值域為［0，1］．當(dāng) Ifki趨于1時，表明fk越穩(wěn)定地反映用戶的特定喜好;當(dāng)Ifki趨于0時，表明fk對用戶喜好的影響越不穩(wěn)定．

標(biāo)簽聚集強度并不能直接體現(xiàn)用戶對一組標(biāo)簽的喜惡程度，其反映的是這組標(biāo)簽體現(xiàn)用戶喜好的能力，并作為篩選更高維(指標(biāo)簽組合包含的標(biāo)簽數(shù)目)標(biāo)簽組合的依據(jù)．例如，李四觀看了五部電影并作如表1所示的評價．

表1 李四的電影評價記錄Table 1 Movie evaluation records for Li Si

從表1可知:擁有“科幻”標(biāo)簽的電影并沒有獲得李四穩(wěn)定的評分，即“科幻”并不能很好地體現(xiàn)李四的喜好;在李四對“源代碼”的評價中，原本出現(xiàn)在5．0評分的電影“2012”中的標(biāo)簽組合{科幻，災(zāi)難}卻因多了新的標(biāo)簽“驚悚”而得到1．0的差評;李四對使用{科幻，動作}標(biāo)簽組合進行描述的電影的評分均為3．0左右，故該標(biāo)簽組合很有可能體現(xiàn)李四對電影的“一般”喜好程度．

2．2 基于標(biāo)簽聚集強度的用戶模型

為克服傳統(tǒng)用戶模型無法準(zhǔn)確體現(xiàn)用戶對某標(biāo)簽組合的喜好程度的問題，理論上新的用戶模型必須存儲每一個能獨立對用戶喜好造成影響的標(biāo)簽組合的權(quán)值．然而，試圖直接窮舉所有可能的標(biāo)簽組合是不實際的．可取的方法就是存儲一些標(biāo)簽組合的聚集強度，以實現(xiàn)低維過濾的效果，即對較低維的標(biāo)簽組合進行篩選，以過濾掉不符合條件的較高維的標(biāo)簽組合．

基于標(biāo)簽聚集強度的用戶模型表示為一個n維標(biāo)簽組合矩陣Mi，n，矩陣中的每個單元存儲用戶i所使用過的標(biāo)簽組合對的標(biāo)簽聚集強度，其中fnm的上標(biāo)n為f包含的標(biāo)簽數(shù)，下標(biāo)m為索引．

文中基于標(biāo)簽聚集強度的用戶模型的構(gòu)建是通過過濾較低維的標(biāo)簽組合尋找較高維的標(biāo)簽組合，并以此迭代更新整個標(biāo)簽組合效應(yīng)矩陣．為此，首先建立一維標(biāo)簽組合效應(yīng)矩陣Mi，1，每個單元存儲兩個標(biāo)簽間的聚集強度．

提取矩陣Mi，1中聚集強度大于或等于α的二維標(biāo)簽組合(其中α為標(biāo)簽聚集強度閾值，只有當(dāng)標(biāo)簽組合的聚集強度大于或等于α?xí)r，其組合效應(yīng)才不可忽略)，然后構(gòu)建 Mi，2，Mi，2增加的行和列是從Mi，1中提取出來的二維標(biāo)簽組合．同理，通過 Mi，2可以迭代構(gòu)建Mi，4，依此類推，直到新矩陣與其前一矩陣擴展出來的部分相比沒有任何單元的值大于或等于α?xí)r，迭代停止．最后獲得一個矩陣Mi，n，該矩陣單元存儲所有不可忽略組合效應(yīng)的標(biāo)簽組合的聚集強度，這些標(biāo)簽組合包含的標(biāo)簽數(shù)目范圍為［2，n2］．

2．3 標(biāo)簽聚集強度計算方法

標(biāo)簽聚集強度作為反映標(biāo)簽組合影響用戶喜好的穩(wěn)定程度的特征量，理論上應(yīng)當(dāng)滿足如下約束條件:如果一個標(biāo)簽組合的所有子標(biāo)簽組合的聚集強度均大于常數(shù)α，則該標(biāo)簽組合的聚集強度也大于α，即

該約束可以確保不可忽略組合效應(yīng)的較高維標(biāo)簽組合不會因為其不滿足條件的較低維子標(biāo)簽組合被過濾而被過濾，另一方面，對于所有可以忽略組合效應(yīng)的高維標(biāo)簽組合在其低維子標(biāo)簽組合被過濾后隨即被過濾．滿足此約束條件的計算方法不僅可以明顯地提高基于標(biāo)簽組合效應(yīng)的推薦算法的推薦性能，而且使得高維標(biāo)簽組合效應(yīng)矩陣的建立成為可能．

考慮到算法時間復(fù)雜度的因素，文中給出一種樸素的標(biāo)簽聚集強度計算方法，即

該方法采用方差特征值的倒數(shù)，將其映射到［0，1］．基于式(1)，文中提出了一種標(biāo)簽組合效應(yīng)矩陣生成算法，具體的算法描述如下:

由式(1)可知，遍歷一次用戶i標(biāo)注過的標(biāo)簽組合f的商品列表，即可求出Ifi，通常這個列表的長度不大于10．因此，該算法的運行時間主要消耗在while循環(huán)中．假設(shè)標(biāo)簽組合效應(yīng)矩陣包含所有可能的標(biāo)簽組合，即α=0，那么采用該算法構(gòu)建n維標(biāo)簽組合效應(yīng)矩陣的時間復(fù)雜度上界為O(qn)，其中q為用戶i使用過的標(biāo)簽數(shù)目．在實際情況中，通過調(diào)節(jié)閾值α可以過濾掉大量的標(biāo)簽組合，因此時間復(fù)雜度遠(yuǎn)小于O(qn)．標(biāo)簽組合效應(yīng)矩陣生成算法的空間消耗主要在于存儲標(biāo)簽組合效應(yīng)矩陣，其空間復(fù)雜度上界為O((ls)n)，其中l(wèi)為最大標(biāo)簽組合的長度，s為矩陣中標(biāo)簽組合的數(shù)目．

2．4 TGER 算法描述

標(biāo)簽組合權(quán)值體現(xiàn)用戶對該標(biāo)簽組合的喜好程度，其主要應(yīng)用于基于標(biāo)簽組合效應(yīng)的推薦過程．

用戶對標(biāo)簽組合的喜好程度由其組合權(quán)值體現(xiàn)，權(quán)值越大表示用戶對出現(xiàn)該標(biāo)簽組合的商品越感興趣．標(biāo)簽組合權(quán)值的計算方法如下:

式中，^ri，j為TGER算法預(yù)測用戶i對商品j的評分，F(xiàn)(i，j)為用戶i標(biāo)簽組合容器與商品j均包含的標(biāo)簽組合集合，為F(i，j)的長度，為標(biāo)簽組合f的權(quán)值．該方法屬于高維標(biāo)簽組合優(yōu)先匹配計算方法，即一旦找到更高維度的標(biāo)簽組合，就以該維度的標(biāo)簽組合權(quán)值作為推薦的依據(jù)，而不再考慮較低維度的標(biāo)簽組合權(quán)值對推薦的影響．

(1)組合效應(yīng)傳遞法．此方法最初是為了解決數(shù)據(jù)集的稀疏問題而提出的，其基本思想是:{t1，t2}、{t1，t3}和{t2，t3}均出現(xiàn)過，但{t1，t2，t3}沒有．然而，因為每兩個標(biāo)簽組合的交集都非空，所以先假定{t1，t2，t3}很可能會出現(xiàn)，并且根據(jù){t1，t2}、{t1，t3}和{t2，t3}的聚集強度去計算{t1，t2，t3}的加權(quán)出現(xiàn)次數(shù)，其中最簡潔的一種方法是取其平均數(shù)．

(2)組合效應(yīng)加權(quán)法．此方法只在{t1，t2，t3}共同出現(xiàn)時才去計算其組合權(quán)值的增量，其中一種計算方法為

式中，c為用戶i標(biāo)注商品所使用的標(biāo)簽總數(shù)．注意到用戶使用c個標(biāo)簽去描述一個商品時，其評分取決于這些標(biāo)簽的整體影響，此時標(biāo)簽組合的任意一個子集對最終評分均只能起到部分的影響，故加上作為部分匹配的罰項．采用式(3)的基于標(biāo)簽組合效應(yīng)的推薦算法描述如下:

該算法的運行時間主要消耗在構(gòu)建臨時標(biāo)簽組合容器T中，維護一張全局的標(biāo)簽索引的時間復(fù)雜度為O(k)，因此該算法的時間復(fù)雜度上界為O(gl)，其中g(shù)為i的長度．

3 實驗與結(jié)果分析

為檢測文中所提算法的效率，采用MovieLens數(shù)據(jù)集(該數(shù)據(jù)集已被廣泛應(yīng)用于推薦系統(tǒng)的相關(guān)實驗中)進行實驗，抽取了其中同時包含評分和標(biāo)簽的數(shù)據(jù)項組成一個新的數(shù)據(jù)集，該數(shù)據(jù)集包含44805條記錄，每條記錄為一個四元組〈用戶ID，電影ID，標(biāo)簽，評分〉，由2025個用戶對4796部電影的評價構(gòu)成．每個用戶至少評價了一部電影，每部電影至少使用一個標(biāo)簽，每個標(biāo)簽是一個英文單詞或一句簡短的話．分?jǐn)?shù)的域值為［0．5，5．0］，間隔為0．5．將每個用戶評價過的電影的80%作為訓(xùn)練集，剩下的20%作為測試集，用以測試基于標(biāo)簽組合效應(yīng)的推薦算法的效率．

實驗采用絕對平均誤差(MAE)來評估目標(biāo)算法的效率，其定義如下:

式中，N為被預(yù)測的商品總數(shù)．

本實驗采用經(jīng)典的CB算法和MovieLens數(shù)據(jù)集上廣泛使用的MF算法作為基準(zhǔn)參照算法．由于數(shù)據(jù)集自身的稀疏性，當(dāng)標(biāo)簽組合過濾到三維以后，四維標(biāo)簽集合極為稀少，其對推薦效果的提高極為微弱，因而本次實驗只對一維、二維和三維的TGER算法進行測試．

為探討基于標(biāo)簽聚集強度的用戶模型的性能，以及驗證TGER算法的效率，文中的實驗步驟如下:①對不同維度的標(biāo)簽聚集強度過濾方法進行對比，以探討用戶模型的性能隨存儲的標(biāo)簽組合維度的增加而變化的趨勢;②將TGER算法與參照算法進行對比，考察基于標(biāo)簽聚集強度的用戶模型應(yīng)用在推薦系統(tǒng)中的效率．

實驗觀察到數(shù)據(jù)集中的標(biāo)簽組合的聚集強度主要分布在［0．80，0．99］，由于篇幅有限，文中只給出標(biāo)簽聚集強度閾值α取0．85、0．94和0．97時的實驗結(jié)果．

為考察TGER算法對小規(guī)模及不同區(qū)域的測試對象的MAE性能，將整個測試集包含的2025個用戶隨機地劃分成5個測試組，分別使用一、二、三維TGER算法對這5個測試組進行測試，結(jié)果如圖1所示．可以看出，當(dāng)過濾維數(shù)逐漸提高時，TGER算法的MAE性能越來越好．

從圖1還可以發(fā)現(xiàn)，針對實驗所用數(shù)據(jù)集，標(biāo)簽聚集強度閾值對TGER算法性能的影響并不明顯．理想的情況應(yīng)當(dāng)是:在不降低TGER算法性能的前提下，最大程度地過濾掉標(biāo)簽組合．

在整個測試集范圍內(nèi)進行測試并對TGER與MF、CB算法的MAE性能進行對比，當(dāng)α=0．97時，一維TGER、二維TGER、三維TGER、MF和CB算法的 MAE 分別為0．56、0．52、0．50、0．62 和0．89．三維TGER算法的MAE性能相對于MF與CB算法分別提高了19%和44%．

圖1 一維、二維和三維TGER算法的MAE對比Fig．1 Comparison of MAE among one-，two-and threedimension TGER algorithm

4 結(jié)語

在分析現(xiàn)有推薦方法忽略標(biāo)簽組合效應(yīng)所帶來的局限性后，文中探討并定義了標(biāo)簽組合效應(yīng)，提出了一種新的基于標(biāo)簽組合效應(yīng)矩陣和用戶對資源評分的用戶建模方法，并基于該用戶建模方法提出了一種新的推薦算法，最后采用MovieLens數(shù)據(jù)集對其進行實驗評估，結(jié)果表明，文中提出的推薦算法能夠明顯地提高推薦的質(zhì)量．今后擬將該用戶建模方法應(yīng)用到個性化搜索中．

［1］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．

［2］Lops P，de Gemmis M，Semeraro G．Content-based recommender systems:state of the art and trends［M］．Recommender Systems Handbook．New York:Springer-Verlag，2011:73-105．

［3］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．Hong Kong:ACM，2001:285-295．

［4］Burke R．Hybrid recommender systems:survey and experiments［J］．User Modeling and User-Adapted Interaction，2002，12(4):331-370．

［5］Melville P，Mooney R J，Nagarajan R．Content-boosted collaborative filtering for improved recommendations［C］∥Proceedings of the Eighteenth National Conference on Artificial Intelligence．Menlo Park:ACM，2002:187-192．

［6］Ma H，King I，Lyu M R．Effective missing data prediction for collaborative filtering［C］∥Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval．Amsterdam:ACM，2007:39-46．

［7］Gunawardana A，Meek C．A unified approach to building hybrid recommender systems［C］∥Proceedings of the Third ACM Conference on Recommender Systems．New York:ACM，2009:117-124．

［8］Symeonidis P，Nanopoulos A，Papadopoulos A N，et al．Collaborative recommender systems:combining effectiveness and efficiency［J］．Expert Systems with Applications，2008，34(4):2995-3013．

［9］Koren Y，Bell R，Volinsky C．Matrix factorization techniques for recommender systems［J］．Computer，2009，42(8):30-37．

［10］Noll M G，Meinel C．Web search personalization via social bookmarking and tagging［M］．The Semantic Web．Berlin/Heidelberg:Springer-Verlag，2007:367-380．

［11］Cai Y，Li Q，Xie H，et al．Personalized resource search by tag-based user profile and resource profile［M］．Web Information Systems Engineering．Berlin/Heidelberg:Springer-Verlag，2010:510-523．

［12］Hofmann T．Probabilistic latent semantic indexing［C］∥Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval．Berkeley:ACM，1999:50-57．

［13］Agarwal D，Merugu S．Predictive discrete latent factor models for large scale dyadic data［C］∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining．San Jose:ACM，2007:26-35．

［14］Agarwal D，Chen B C．Regression-based latent factor models［C］∥Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining．Paris:ACM，2009:19-28．

［15］Deerwester S，Dumais S T，F(xiàn)urnas G W，et al．Indexing by latent semantic analysis［J］．Journal of the American Society for Information Science，1990，41(6):391-407．

［16］Han H，Cai Y，Shao Y，et al．Improving recommendation based on features’co-occurrence effects in collaborative tagging systems［M］．Web Technologies and Applications．Berlin/Heidelberg:Springer-Verlag，2012:652-659．