基于內容和標簽權重的混合推薦算法*

劉 宇朱文浩

（1.武漢郵電科學研究院 武漢 430070）（2.南京烽火星空通信發展有限公司 南京 210019）

1 引言

信息和互聯網技術發展至今，人們逐漸從找不到自己所需信息的信息匱乏時代發展到現在的信息過載的時代，因此從大量的信息中找到自己感興趣的信息就變成了一件非常困難的事。推薦系統正是為了解決這一問題而出現的，它是可以主動從大量的信息中獲取用戶感興趣的信息，進而推薦給用戶的系統，一方面幫助用戶發現對自己有價值的信息，另一方面讓信息能夠展示在對它感興趣的用戶面前［1］。近年來，推薦系統已經被廣泛的運用到電子商務、電影和視頻網站、個性化音樂網絡電臺、社交網絡、個性化閱讀和個性化郵件等各個領域［2］，分別將這些不同物品的信息根據用戶的興趣推薦給用戶。

2 推薦算法及研究現狀

目前基本的推薦算法主要包括基于協同過濾的算法、基于內容的推薦算法和基于標簽的推薦算法［3］。

基于協同過濾的推薦算法又可以分為基于用戶的協同過濾算法和基于內容的協同過濾算法。基于用戶的協同過濾利用和用戶興趣相似的其他用戶，給用戶推薦那些和他們興趣愛好相似的用戶喜歡的物品；基于物品的協同過濾即利用用戶喜歡過的物品，給用戶推薦與他喜歡的物品相似的物品［4］。協同過濾可以增加推薦的新穎性，但是當用戶對物品的評價信息較少時，推薦效果則不是很好，即協同過濾算法存在冷啟動問題［5］。此外，協同過濾推薦算法由于是利用的歷史行為和喜好，在給用戶推薦物品時就無法給出令人信服的理由，因此在可解釋性問題上也存在缺陷。

基于內容的推薦算法與協同過濾算法不同，它利用的是物品的內容信息，通過抽取物品的內容信息來描述物品來形成物品的特征屬性，從而得到物品之間的相似度，進而根據用戶過去對物品的喜好，給用戶推薦與其喜好相似的物品［6］。而目前，在音樂、電影等物品的推薦系統中，由于其內容抽取比較困難，所以基于內容的推薦算法不能得到有效的利用，因而通常被用于基于文本的物品，此時，物品的內容可以通過向量空間模型表示，將物品表示成一個關鍵詞向量，而文本形式的內容則需要經過分詞、提取和內容特征的處理等過程［7］，從而生成關鍵詞向量，過程也極為復雜。所以基于內容的推薦算法沒有得到廣泛的應用。

標簽是用戶用來描述物品信息的關鍵詞，是用戶對物品信息的高度概括。在基于標簽的推薦系統中，標簽是聯系用戶和物品之間的紐帶。帶有用戶的主觀性，因此通過標簽得到的物品之間的相似度比基于分詞和內容抽取的物品信息更能代表用戶的興趣。基于標簽的推薦系統通過分析物品的標簽信息和用戶對標簽的使用偏好之間的相似行形成三元組（用戶、物品、標簽）［8］。基于標簽的推薦系系統同樣依賴用戶的歷史行為，因此也存在冷啟動的問題。

上述的三種推薦算法雖然在推薦系統中應用得較多，但是它們各自都缺點，如基于內容的推薦算法無法處理音頻、視頻等多媒體非結構化數據［9］；協同過濾和基于標簽的推薦算法則分別存在可解釋性問題和冷啟動問題。結合基于標簽的推薦算法和基于內容的推薦算法二者的優點，同時引入標簽權重來提高推薦系統的準確率，本文提出了一種基于標簽權重的內容推薦算法（TW-ContentItem）。

3 標簽權重

3.1 標簽權重的描述

在第二節中提到基于內容的推薦算法大多用于文本的推薦，而從文本中得到到關鍵詞向量需要經過分詞、實體檢測、關鍵詞排名等一系列階段，使用起來較為復雜，而且在非文本的推薦系統中，物品的關鍵詞信息提取很難提取［10］。因此可以結合標簽，以用戶給物品打的標簽作為電影、音樂等的關鍵詞，形成關鍵詞向量，從而可以更方便地計算物品之間的相似度，而不需要經歷上述復雜的提取和內容特征的處理過程。

傳統的標簽系統在描述物品時給出標簽特征，而對不同物品的描述，不同標簽對物品特征體現的程度可能不同，所以標簽權重在這個基礎上做出了擴展，在給出標簽特征的同時還會給出該標簽在描述物品時對應的權重。

在應用標簽權重時，首先假設用戶在為相似的物品打標時會用相同的標簽［11］，則根據用戶與標簽的關系及物品和標簽的關系可以分別利用兩種標簽權重：物品標簽權重和用戶標簽權重。對于不同的物品，標簽可以看成是物品的內容屬性，那么可以理解為標簽對物品的重要性與物品打上標簽的次數有關，同一標簽打得越多，對物品來說越是重要，這就是物品標簽權重；用戶標簽權重則與用戶使用某一標簽的頻率有關，標簽使用越頻繁則權重越大［12］。

3.2 標簽權重的計算

為了用實現用標簽表示物品的內容屬性得到物品的標簽權重，對于物品d，其內容表示成一個關鍵詞向量為

其中t為標簽，w為標簽對應的權重。

物品標簽權重可以用TF-IDF公式來計算得到：

在計算物品權重時，可以將每一個物品視為一個文檔ti，令D=｛d1，d2，d3，…，dj，…｝表示一個文檔的集合，而T=｛t1，t2，t3，…，tj，…｝表示詞典，即物品被打上的所有標簽的集合，也就是視為在文檔集里面的標簽集合［10］。由此便可以利用式（2）計算出標簽的權重。

與物品標簽權重類似，用戶標簽權重也可以用式（2）計算，這時詞典T表示的是用戶使用的所有標簽的集合。由于本文主要用到物品標簽權重，這里不再贅述。

3.3 標簽權重的作用

在基于內容的推薦算法中，由于部分標簽的流行的較高，所以被使用的頻率較高，因此次標簽對物品來說區分度較低，因此該標簽的權重較低［13］，為了減少這類標簽的影響，引入標簽權重，在生成關鍵詞向量時加入標簽的權重，另外，即使同一個標簽，對不同的物品的重要性也可能并不相同［14］，因此引入不同物品的標簽權重從很大程度上能夠提高推薦系統的準確率。

引入標簽權重的另一個優點是對冷啟動問題不敏感，因為當一個新的物品加入時，會有帶有一些有關物品基本信息的標簽，總會有其他的物品包含這些標簽，那么該物品就能夠在更多人的推薦列表中出現，從而使物品能夠擴散開來。也正是標簽帶有物品的基本信息［15］。

在可解釋性方面，基于內容的推薦算法本身就有很好的可解釋性，因為就是根據物品的內容屬性來推薦的，同樣的引入的標簽，讓用戶根據他自己的興趣選擇相關的標簽，得到推薦結果，使用戶更容易覺得系統的推薦有道理。

4 算法實現

4.1 相似度

在第二章通過標簽權重得到物品的標簽權重向量之后，就可以通過向量之間的余弦相似度公式得到物品之間兩兩的相似度。

計算物品di和dj之間的相似度公式為

即向量之間的余弦相似度，式中wti和wtj為標簽t的權值，T為兩個物品之間共有標簽的集合。在推薦系統中計算物品之間的相似度矩陣最簡單的方法是對任意兩兩物品都用上述的公式計算相似度［16］。

4.2 倒排表

雖然運用式（3）來計算物品兩兩之間的相似度實現起來較為簡單，但是可以看到當有N個物品，每個物品平均由m個標簽表示，那么用上面簡單方法的復雜度為O（N2m），這個時間復雜度是非常高的。不僅如此，實際上很多物品相互之間并沒有被打上相同的標簽。而系統中若兩兩之間計算相似度會將很多時間浪費在計算這種沒有共同標簽的物品的相似度上［4］。

因此在實際應用中為了減少時間復雜度，可以利用物品-標簽倒排表如圖1、圖2所示，對于每個標簽都保存使用過該標簽的物品列表。建立標簽-物品倒排表之后，建立一個相似度矩陣W［18］，如圖3所示。當兩個物品同時打上一個標簽時W［u］［v］的值加1，如A、C同時打上了標簽a、b則W［A］［C］=2。依此類推，掃描完所有標簽之后，就可以得到最終的物品相似度矩陣W，矩陣中的w是余弦相似度中的分子部分，將其除以分母就可以得到最終的余弦相似度。

圖1 物品-標簽

圖2 標簽-物品倒排

圖3 相似度矩陣分子

實際中由于添加了標簽權重，需要對倒排進行改進，即W［u］［v］的值應該是u、v兩個物品共同標簽對應的權重的乘積之和。令wui和wvi分別為標簽i在物品u和物品v標簽列表中對應的權重，T為u、v物品所共有標簽的集合，du、dv分別為u、v的相似度向量。則用倒排序的方法得出物品u、v之間的相似度為

通過這種方法來計算相似度能夠很大程度上減少計算量，并且改進之后加入標簽權重的影響，使其準確率有很大的提高。

4.3 Top-N推薦列表

得到物品的推薦列表主要有以下兩個步驟：

1）計算物品之間的相似度；

2）根據物品相似度和用戶歷史行為及給用戶生成推薦列表。

在4.2節中已經可以得到物品之間的相似度列表，下面是得到用戶對物品的興趣度及推薦列表的具體方法。

計算用戶u對物品j的興趣公式：

這里的N（u）是用戶喜歡物品的集合（在本寫系統中指的是用戶打過標簽的物品），S（j，k）是和物品j最相似的k個物品的集合（與j之間兩兩相似度最高的k個物品），wij是物品j和i的相似度，rui（對于隱反饋數據集，如果用戶u對物品i有過行為，即可令rui=1［4］）是用戶u對物品i的興趣，則當rui=1時用戶u對物品j的興趣就是對i、j之間的相似度wji。對求得的興趣進行排序取前N個物品就是所求的Top-N排序。

式（5）在理論上是可行的，但是數據量過大時，要得到用戶u對所有物品的興趣并排序，其時間復雜度極高，且用戶對大部分的物品的興趣度可能接近0。為此在使用式（5）之前，可以先對數據進行預處理，即確定鄰近值k后，先根據用戶u的興趣列表J（u）（假設列表個數為m），分別找到與列表中物品相似的k個物品，然后對這m*k個物品使用式（5）得到推薦列表可以減小時間復雜度。

5 結果分析

5.1 數據集的選擇

Delilious是最早應用標簽系統的，它允許用戶給互聯網上的每個網頁打標簽，從而能夠從各個方面準確的描述網頁這個“物品”［19］，而本文需要的也是用標簽來描述物品的內容屬性，所以該數據集滿足算法的需求。在本文中運用了該數據集的兩組數據：

1）bookmark_tags.dat：｛用戶id，標簽id，標簽權重｝；

2）user_taggedbookmarks-timestamps.dat：｛用戶id，物品id，標簽id｝。

從數據集的上述兩個文件中可以得到計算用戶偏好的四元組：

M=｛用戶id，物品id，標簽id，標簽權重｝

5.2 評測指標

推薦的目的就是給用戶推薦其最感興趣的物品，因此本文得到物品的相似度之后采用的是topN推薦，而測評指標則是準確率（Precision），通過選取不同長度N的推薦列表可以全面測評實驗算法的準確率［20］。

對用戶u推薦的N個物品（記為R（u）），令用戶u在測試集上喜歡的物品集合為T（u），則準確率可以表示為

5.3 結果分析

對比的另外兩種算法為基于內容的推薦算法和基于標簽的推薦算法。

本文將標簽與基于內容的推薦算法相結合，并利用標簽權重來提高推薦算法的準確率，利用倒排及預處理來降低算法的時間復雜度。

基于內容的推薦算法中，選取的鄰近值k是一個很關鍵的參數。表1為不同k值下得到的推薦系統的準確率。

表1 TW-ContentItem推薦算法在不同k值下的準確率

從表1可以發現當k=10時系統的準確率明顯高于其他的值。

選取基于物品的協同過濾算法（ItemCF）和基于標簽的推薦算法（ItemTags）來進行對照。以準確率為測評指標，取k=10，通過選取不同長度N的推薦列表，與本文的推薦算法（TW-ContentItem）進行對比，實驗結果如圖4所示。

圖4 不同算法準確率比較

從圖4中可以看到，在選取的物品鄰近數k都取相同的值時，本文提出的算法在選取不同的N值時的準確率明顯高于其他兩種。

6 結語

本文結合傳統的基于內容的推薦算法和基于標簽的推薦算法，并引入標簽權重，提出了一種基于內容和標簽權重的混合推薦算法。提高了推薦系統的準確率，并且省去了基于內容的推薦算法在音樂、電影等推薦系統中應用時繁雜的內容提取過程。同時，由于基于內容的推薦算法是基于物品自身的內容屬性推薦的，結合標簽權重之后，對冷啟動問題也不會很敏感，此外，基于內容和標簽的推薦算法二者分別利用了物品的內容屬性和特征，在可解釋性方面也優與其他的推薦算法。