《推薦系統實踐》樣章：如何利用用戶標簽數據

推薦系統的目的是聯系用戶的興趣和物品，這種聯系需要依賴于不同的媒介。GroupLens在文章1中認為目前流行的推薦系統基本上通過三種方式來聯系用戶興趣和物品。如圖1所示，第一種方式是通過用戶喜歡過的物品：可以給用戶推薦與他喜歡過的物品相似的物品，這就是前面提到的基于物品的算法（item-based）。第二種方式是通過和用戶興趣相似的其他用戶：可以給用戶推薦那些和他們興趣愛好相似的其他用戶喜歡的物品，這也是前面提到的基于用戶的算法（user-based）。除了這兩種方法，第三個也是最重要的方式是通過一些特征（feature）來聯系用戶和物品，可以給用戶推薦那些具有用戶喜歡的特征的物品。這里的特征有不同的表現方式，比如可以表現為物品的屬性集合（比如對于圖書，屬性集合就包括了作者、出版社、主題和關鍵詞等），也可以表現為隱語義向量（latent
factor vector），這可以通過前面提出的隱語義模型（Latent Factor
Model）學習得到。在本章中，我們將討論一種重要的特征表現方式：標簽。

圖1 推薦系統聯系用戶和物品的幾種途徑

根據維基百科的定義2，標簽是一種無層次化結構的、用來描述信息的關鍵詞。因此，標簽可以用來準確地描述物品的語義。根據給物品打標簽的人的不同，標簽應用一般分為兩種。第一種是讓作者或者編輯給物品打標簽，而另一種是讓普通用戶給物品打標簽，也就是UGC的標簽應用。表1列出了這兩種不同的標簽系統的代表網站。在本章中，我們主要討論UGC的標簽應用，研究用戶給物品打標簽的行為，以及如何通過分析這種行為給用戶進行個性化推薦。

表1 兩種不同的標簽系統的代表網站

UGC的標簽系統是一種很重要的表示用戶興趣和物品語義的方式。當一個用戶對一個物品打上一個標簽后，這個標簽一方面描述了用戶的興趣，另一方面也表示了物品的語義，從而將用戶和物品聯系了起來。

UGC標簽系統的代表應用

---

UGC標簽系統是很多Web 2.0網站的必要組成部分，本節將討論使用UGC標簽系統的代表網站：UGC標簽系統的鼻祖美味書簽（Delicious）、論文書簽網站CiteULike、音樂網站Lastfm、視頻網站Hulu、書和電影評論網站豆瓣等。下面將分別介紹這些應用。

Delicious

美味書簽（Delicous）是標簽系統里的開山鼻祖了，它允許用戶給互聯網上的每個網頁打上標簽，從而通過標簽的方式重新組織整個互聯網。圖2是Delicious中被用戶打上recommender
system標簽最多的網頁，這些網頁反應了用戶心目中和推薦系統最相關的網頁。圖3是Delicious中“豆瓣電臺”這個網頁被用戶打的最多的標簽，可以看到這些標簽確實準確地描述了豆瓣電臺。

圖2 Delicious中被打上recommender system標簽的網頁

圖3 Delicious中“豆瓣電臺”網頁被用戶打的最多的標簽

CiteULike

CiteULike是一個著名的論文書簽網站，它允許研究人員提交或者收藏他們感興趣的論文，給論文打標簽，從而幫助用戶更好地發現和自己研究領域相關的優秀論文。我們知道，研究人員搜索自己研究領域值得參考的論文是很費時費力的工作，而CiteULike通過群體智能，讓每個研究人員對自己了解的論文進行標記，從而幫助用戶更好更快地發現自己感興趣的論文。圖4展示了CiteULike中一篇被用戶打的標簽最多的有關推薦系統評測的文章，可以發現，最多的兩個標簽是collaborative-filtering（協同過濾）和evaluate（評測），確實比較準確地反應了這篇論文的主要內容。

圖4 CiteULike中一篇論文的標簽

Lastfm

Lastfm是一家著名的音樂網站，它通過分析用戶的聽歌行為來預測用戶對音樂的興趣，從而給用戶推薦個性化的音樂。作為多媒體，音樂不像文本那樣可以很容易地分析它的內容信息。為了在不進行復雜的音頻分析的情況下獲得音樂的內容信息，Lastfm引用了標簽系統，讓用戶用標簽標記音樂和歌手。圖5展示了披頭士樂隊在Lastfm中的標簽云（tag
cloud）。從這個標簽云可以看到，披頭士應該是一個英國的傳統搖滾樂隊，流行于上世紀60年代。

圖5 Lastfm中披頭士樂隊的標簽云

豆瓣

豆瓣是中國著名的評論和社交網站，同時也是中國個性化推薦鄰域的領軍企業之一。豆瓣在個性化推薦領域進行了廣泛的嘗試，標簽系統也是他們嘗試的領域之一。他們允許用戶對圖書和電影進行標簽，從而獲得圖書和電影的內容信息，并用這種信息來改善他們的推薦效果。圖7展示了《數據挖掘導論》在豆瓣被用戶標記的情況。如圖7所示，最多的幾個標簽分別是：數據挖掘、計算機、計算機科學、數據分析、IT數據分析。這些標簽準確地反應了這本書的內容信息。

圖6 豆瓣讀書中《數據挖掘導論》一書的常用標簽

Hulu

Hulu是美國著名的視頻網站。視頻作為一種最為復雜的多媒體，獲取它的內容信息是最困難的，因此，Hulu也引入了用戶標簽系統來讓用戶對電視劇和電影進行標記。圖7展示了美劇《豪斯醫生》的常用標簽，可以看到，Hulu對標簽做了分類，并展示了每一類最熱門的標簽。從類型（genre）看，豪斯醫生是一部醫學片（medical
drama）；從時間看，這部劇開始于2004年；從人物看，這部美劇的主演是hugh laurie，他在劇中飾演的人物是greg house。

圖7 Hulu中《豪斯醫生》的常用標簽

從前面的各種應用可以看到，標簽系統在各種各樣的網站中（音樂、視頻和社交等）都得到了廣泛的應用。標簽系統的最大優勢在于可以發揮群體的智能，獲得物品內容信息的比較準確的關鍵詞描述，而準確的內容信息是提升個性化推薦系統的重要資源。

標簽系統中的推薦問題

---

標簽行為作為一種重要的用戶行為，蘊含了很多反映用戶興趣的信息，因此深入研究用戶的標簽行為可以很好地指導個性化推薦系統提升自己的推薦質量。同時，標簽作為一種重要的內容表示方式，比傳統的內容屬性表示更能反應用戶對物品的看法，并且表示形式非常簡單，便于很多算法處理。

標簽系統中的推薦問題主要有以下兩個。

• 如何利用用戶的標簽行為給用戶推薦物品（tag-based recommendation）？

• 如何在用戶給物品打標簽時給用戶推薦適合于該物品的標簽（tag recommendation）？

為了研究上面的兩個問題，我們首先需要解答下面三個問題。

• 用戶為什么要打標簽（Why）？

• 用戶怎么打標簽（How）？

• 用戶打什么樣的標簽（What）？

用戶為什么要標注

在設計基于Tag的個性化推薦系統之前，我們需要深入了解用戶的標注行為，知道用戶為什么要標注，用戶怎么標注，只有深刻地了解用戶的行為，我們才能基于這個行為給用戶設計出令他們滿意的個性化推薦系統。

Morgan
Ames研究圖片分享網站中用戶標注的動機問題3，他將用戶標注的動機分解成兩個維度。首先是社會維度，有些用戶標注是為了給內容的上傳者使用的，而有些用戶標注是為了給廣大用戶使用的。令一個維度是功能維度，有些標注是為了更好地組織內容，方便用戶將來的查找，而另一些標注是為了傳達某種信息，比如照片的拍攝時間和地點等。

用戶如何打標簽

在互聯網中，盡管每個用戶的行為看起來是隨機的，但其實這些表面隨機的行為的背后蘊含著很多規律。在這一節中，我們通過研究美味書簽的數據集，來發現用戶標注行為中的一些統計規律。

德國的研究人員公布過一個很龐大的美味書簽的數據集4，該數據集包含了2003年9月到2007年12月美味書簽用戶4.2億條標簽行為記錄。本節選用該數據集2007年一整年的數據進行分析，對該數據集的統計特性進行研究。

本節將統計數據集的以下信息。

• 用戶活躍度的分布。

• 物品流行度的分布。

• 標簽熱門度的分布。

• 用戶標簽行為隨時間演化的曲線。

• 用戶相隔一段時間興趣變化的情況。

• 物品的生命周期。

[*具體統計結果待書正式出版時公布*]**

用戶打什么樣的標簽

用戶在看到一個物品時，我們最希望他打的標簽是能夠準確描述物品內容屬性的關鍵詞。但用戶往往不是按照我們的想法去操作，而是可能會給物品打上各種各樣奇怪的標簽。

Scott A. Golder 總結了美味書簽上的標簽，將它們分為如下的幾類。

• 表明物品是什么：比如是一只鳥，就會有“鳥”這個詞的標簽；是豆瓣的首頁，就有一個標簽叫“豆瓣”；是喬布斯的首頁，就會有個標簽叫“喬布斯”。

• 表明物品的種類：比如在美味書簽中，表示一個網頁的類別的標簽包括 article（文章）、 blog（博客）、 book（圖書）等。

• 表明誰擁有物品 ：比如很多博客的標簽中會包括博客的作者等信息。

• 表達用戶的觀點：比如用戶認為網頁很有趣，就會有funny（有趣）的標簽，認為很無聊，就會打上boring（無聊）的標簽。

• 用戶相關的標簽：有些標簽，比如 my favorite（我最喜歡的）、my comment（我的評論）等。

• 用戶的任務：比如 to read（即將閱讀）、 job search（找工作）等。

很多不同的網站也設計了自己的標簽分類系統，比如Hulu對視頻的標簽就做了分類。

圖8是著名的美劇《豪斯醫生》的標簽。可以看到，Hulu將電視劇的標簽分成了幾類。

• 類型（Genre）：主要表示這個電視劇的類別，比如《豪斯醫生》是屬于醫學劇情片（medical
  drama），同時有喜劇（comedy）、懸疑（mystery）的成分。

• 時間（Time）：主要包括電視劇發布的時間，有時也包括電視劇中事件發生的時間，比如是二戰期間，或者是上世紀90年代。

• 人物（People）：主要包括電視劇的導演、演員和劇中重要人物等。

• 地點（Place）：劇情發生的地點，或者是視頻拍攝的地點等。

• 語言（Language）：這部電視劇使用的語言。

• 獎項（Awards）：這部電視劇獲得的相關獎項。

• 其他（Details）：包含了不能歸類到上面各類的其他所有標簽。

圖8 著名美劇《豪斯醫生》在視頻網站Hulu上的標簽分類

---

1?文章名是Tagsplanations : Explaining Recommendations
using Tags。

2
具體見http://en.wikipedia.org/wiki/Tag_(metadata)。

3?具體見?Why We Tag: Motivations for Annotation in
Mobile and Online
Media。

4?數據集見
http://www.dai-labor.de/en/competence_centers/irml/datasets/。

?

===============================================

用戶用標簽來描述自己對物品的看法，因此，標簽成為了聯系用戶和物品的紐帶。因此，標簽數據是反應用戶興趣的重要數據源，而如何利用用戶的標簽數據來提高用戶個性化推薦結果的質量，是推薦系統研究的重要問題。

在如何利用標簽數據的問題上，豆瓣無疑是這方面的代表。豆瓣將標簽系統融入到他們的整個產品線中。下面以豆瓣讀書為例進行介紹。首先，在每本書的頁面上，都提供了一個叫做“豆瓣成員常用標簽”的應用，它給出了這本書上用戶最常打的標簽。同時，在用戶希望給書做評價時，豆瓣也會讓用戶給圖書打標簽。最后，在最終的個性化推薦結果里，豆瓣利用標簽將用戶的推薦結果做了聚類，顯示了不同標簽下用戶的推薦結果，從而增加了推薦的多樣性和可解釋性。

一個用戶標簽行為的數據集一般由一個三元組的集合表示，其中記錄(u, i, b) 表示用戶u給物品i打上了標簽b。當然，用戶的真實的標簽行為數據遠遠比三元組表示的要復雜，比如用戶標簽的時間、用戶的屬性數據、物品的屬性數據等。但是，在本章中，為了集中討論標簽數據，我們只考慮上面定義的三元組形式的數據，即用戶的每一次標簽行為都用一個三元組(用戶,物品,標簽)來表示。

在下面的各節中，我們將利用Delicious的數據集，討論如何利用用戶標簽數據進行個性化推薦的各種算法。

實驗設置

---

我們將Delicious的數據集按照9：1隨機分成訓練集R和測試集T。這里分割的鍵值是用戶和物品，不包括標簽，也就是說，用戶對物品的多個標簽記錄要么都被分進訓練集，要么都被分進測試集。

在分完數據集后，我們將通過學習訓練集中的用戶標簽數據，來預測測試集上用戶會給什么物品打標簽。對于用戶u，令R(u)是給用戶u的長度為N的推薦列表，里面包含著我們認為用戶會打標簽的物品。而另T(u)是測試集中用戶u實際上打過標簽的物品集合。然后，我們利用準確率/召回率（Precision/Recall）來評測個性化推薦算法的準確率：

如果用Python實現上面的兩個指標，我們可以通過如下的代碼：

defPrecisionRecall(test_data, recommendations, N):hit =0n_recall =0n_precision =0for user,ru in recommendations.items():tu = test_data[user]for item in sorted(ru.items(), key=itemgetter(1), reverse=True)[0:N]:if item in tu:hit +=1n_precision +=1n_recall += len(tu)recall = hit /(n_recall *1.0)precision = hit /(n_precision *1.0)return list(recall, precision)

同時，為了全面評測個性化推薦的性能，我們同時評測了推薦結果的覆蓋度（Coverage）、多樣性（Diversity）和新穎度。

覆蓋度我們通過如下的公式和代碼計算：

defCoverage(train_data, test_data, recommendations, N):total_items =set()recommend_items =set()for user, items in train_data.items():for item in items:total_items.add(item)for user, ru in recommendations.items():for item, weight in sorted(ru.items(), key=itemgetter(1), reverse=True)[0:N]:recommend_items.add(item)return(len(recommend_items)*1.0)/(len(total_items)*1.0);

關于多樣性，我們在第1章中討論過，多樣性的定義取決于相似度的定義。在本章中，我們用物品的標簽向量的余弦相似度來度量物品之間的相似度。對于每個物品i，itemtags[i]存儲了物品i的標簽向量，其中itemtags[i][b]是物品i上標簽b被打的次數，那么物品i和j的余弦相似度可以通過如下的程序計算：

defCosineSim(item_tags, i, j):ret =0for b,wib in item_tags[i].items():if b in item_tags[j]:ret += wib * item_tags[j][b]ni =0nj =0for b, w in item_tags[i].items():ni += w * wfor b, w in item_tags[j].items():nj += w * wif ret ==0:return0return ret / math.sqrt(ni * nj)

在得到物品之間的相似度度量后，我們通過如下的公式來計算一個推薦列表的多樣性：

如果用程序實現，代碼如下：

defDiversity(item_tags, recommend_items):ret =0n =0for i in recommend_items.keys():for j in recommend_items.keys():if i == j:continueret +=CosineSim(item_tags, i, j)n +=1return ret /(n *1.0)

而推薦系統的多樣性定義為所有用戶的推薦列表的多樣性的平均值。

至于推薦結果的新穎性，這里我們簡單地用推薦結果的平均熱門程度（AveragePopularity）來度量。對于物品i，定義它的熱門度item_pop(i)為給這個物品打過標簽的用戶數。而對推薦系統，我們定義它的新穎度如下：

如果用程序實現，代碼如下：

defAveragePopularity(item_pop, recommend_results):ret =0n =0for u, recommend_items in recommend_results.items():for item in recommend_items.keys():ret += math.log(1+ item_pop [item])n +=1return ret /(n *1.0)

一個最簡單的算法

---

當拿到了用戶標簽行為數據時，大家都可以想到一個最簡單的算法來給用戶推薦個性化的物品。這個算法的描述如下所示。

• 統計每個用戶最常用的標簽。

• 對于每個標簽，統計被打過這個標簽的次數最多的物品。

• 對于一個用戶，首先找到他常用的標簽，然后對于這些常用標簽，找到具有這些標簽的最熱門的物品，推薦給這個用戶。

如果用公式描述上面的算法，那么用戶u對物品i的興趣可以用如下的公式度量：

這里，B(u)是用戶u打過的標簽集合，B(i)是物品i被打過的標簽集合,?是用戶u打過標簽b的次數，?是物品i被打過標簽b的次數。本章用SimpleTagBased來標記這個算法。

在Python中，我們用 records 來存儲標簽數據的三元組，其中

records[i]=[user, item, tag]

用 usertags 來存儲?，其中usertags[u][b] =??。

用 tagitems來存儲，其中tagitems[b][i] =?。

如下的程序可以從records統計出usertags和tagitems:

defInitStat(records):user_tags = dict()tag_items = dict()for user, item, tag in records.items():if user notin user_tags:user_tags[user]= dict()if tag notin user_tags[user]:user_tags[user][tag]=1else:user_tags[user][tag]+=1if tag notin tag_items:tag_items[tag]= dict()if item notin tag_items[tag]:tag_items[tag][item]=1else:tag_items[tag][item]+=1

統計出usertags和tagitems之后，可以通過如下程序對用戶進行個性化推薦：

defRecommend(user):recommend_items = dict()for tag, wut in user_tags[user].items():for item, wti in tag_items[tag].items():if item notin recommend_items:recommend_items[item]= wut * wtielse:recommend_items[item]+= wut * wtireturn recommend_items

我們在Delicious數據集上對上面的算法進行評測，結果如表2所示。

表2 簡單的基于標簽的推薦算法在Delicious數據集上的評測結果

算法的改進

---

我們再來回顧一下上面提出的簡單算法，該算法通過如下公式預測用戶u對物品i的興趣：

仔細研究上面的公式，可以發現上面的公式有很多缺點。下面我們將逐條分析該算法的缺點，并提出改進意見。

歸一化

如果我們從概率論的角度出發，認為用戶u喜歡物品i的概率取決于u曾經打過的標簽，那么我們會得到如下的概率公式：

這個公式和SimpleTagBased算法的公式相比，對參數做了歸一化，而且他的解釋也是從概率的角度出發，更加明確，本章用NormTagBased來代表這個算法。表3給出了SimpleTagBased算法和NormTagBased算法在各種指標上的實驗結果的比較。

表3 SimpleTagBased算法和NormTagBased算法的比較

如表3所示，經過歸一化之后的NormTagBased算法無論在召回率/準確率，還是在覆蓋度、多樣性和熱門程度等指標上，均優于SimpleTagBased算法。因此，NormTagBased算法是對SimpleTagBased的算法的一個有效的改進。

數據稀疏性

在前面的算法中，用戶興趣和物品的聯系是通過B(u)∩B(i)中的標簽建立的。但是，如果這個用戶是新用戶，或者物品是新物品，那么這個集合（B(u)∩B(i)）中的標簽數量會很少。為了提高推薦的準確率，我們可能要對標簽集合做擴展，比如用戶曾經用過“推薦系統”這個標簽，我們可以將這個標簽的相似標簽也加入到用戶標簽集合中，比如“個性化”，“協同過濾”等標簽。

為了說明數據稀疏性對性能的影響，我們將用戶按照打過的標簽數分成兩組。第一組用戶打過10次以下的標簽，而第二組用戶打過超過10次標簽，我們分別統計這兩組用戶的推薦結果的準確率和召回率，結果如表4所示。

表4 不同活躍度的用戶的召回率/準確率對比

[具體實驗結果待正式發表時公布]

進行標簽擴展有很多方法，其中著名的有話題模型（Topic Model）。不過這里我們遵循簡單的原則，只介紹一種基于鄰域的方法。

標簽擴展的本質是對每個標簽找到和它相似的標簽，也就是計算標簽之間的相似度。最簡單的相似度可以是同義詞。如果我們有一個同義詞詞典，就可以根據這個詞典來進行標簽擴展。如果沒有這個詞典，我們還是可以從數據中統計出標簽的相似度。

如果認為同一個物品上的不同標簽具有某種相似度的話，那么如果兩個標簽同時出現在很多物品的標簽集合中，就可以認為這兩個標簽具有較大的相似度。對于標簽b，令N(b)為有標簽b的物品的集合，n_(b,i)為給物品i打上標簽b的用戶數，可以通過如下的余弦相似度公式計算標簽b和標簽b'的相似度：

[具體實驗結果待正式發表時公布]

標簽清理

不是所有的標簽都能反應用戶的興趣。比如，在一個視頻網站中，用戶可能對一個視頻賦予了一個表示情緒的標簽，比如“不好笑”（no funny）。但我們不能因此認為用戶對“不好笑”有興趣，并且給用戶推薦其他具有“不好笑”這個標簽的視頻。相反，如果用戶對視頻打過“成龍”這個標簽，我們可以據此認為用戶對成龍的電影感興趣，從而給用戶推薦成龍其他的電影。同時，標簽系統里經常出現詞形不同、詞義相同的標簽，比如recommender system和recommendation engine就是兩個同義詞。

標簽清理的另一個重要意義在于用標簽作為推薦解釋。如果我們要把標簽呈現給用戶，作為給用戶推薦某一個物品的解釋時，對標簽的質量要求就很高。首先，這些標簽不能包含沒有意義的停止詞或者表示情緒的詞，其次這些推薦解釋里不能包含很多相同意義的詞語。

本章我們使用的標簽清理的方法有以下幾種。

• 去除詞頻很高的停止詞。

• 去除因詞根不同造成的同義詞，比如 recommender system和recommendation system。

• 去除因分隔符造成的同義詞，比如 collaborative_filtering和collaborative-filtering。

[具體實驗結果待正式發表時公布]

為了控制標簽的質量，很多網站也采用了讓用戶反饋的思想，即讓用戶來告訴系統某個標簽是否合適。MovieLens在他們的實驗系統中就采用了這種方法，關于這方面的研究可以參考GroupLens的Shilad同學的博士論文 。此外，電影推薦網站Jinni也采用了這種方式（如圖9所示）。當然，Jinni不屬于UGC的標簽系統，它給電影的標簽是專家賦予的，因此它讓用戶對標簽反饋其實是想融合專家和廣大用戶的知識。

圖9 Jinni允許用戶對編輯給的標簽進行反饋

基于圖的推薦算法

---

前面討論的簡單算法很容易懂，也容易實現，但缺點是不夠系統化和理論化。因此，在這一節中，我們主要討論如何利用圖模型來做基于標簽數據的個性化推薦。

首先，我們需要將用戶的標簽行為表示到一個圖上。我們知道，圖是由頂點、邊和邊上的權重組成的。而在用戶標簽數據集上，有三種不同的元素：用戶、物品和標簽。因此，我們需要定義三種不同的頂點：用戶頂點、物品頂點和標簽頂點。然后，如果我們得到一個表示用戶u給物品i打了標簽b的用戶標簽行為(u,i,b)，那么，最自然的想法就是在圖中增加三條邊，首先在用戶u對應的頂點v(u)和物品i對應的頂點v(i)之間需要增加一條邊（如果這兩個頂點已經有邊相連，那么就應該將邊的權重加1），同理，在v(u)和v(b)之間需要增加一條邊， v(i)和v(b)之間也需要邊相連接。

圖10是一個簡單的用戶-物品-標簽圖的例子。

圖10 一個簡單的用戶-物品-標簽圖的例子

通過用戶標簽行為構造出圖之后，為用戶u推薦物品的問題就轉化為計算圖上所有物品節點相對于用戶節點v(u)的相關度排名的問題。圖上的排名算法很多，其中最著名的就是PageRank算法。

PageRank算法最初是用來對互聯網上的網頁進行排名的算法。網頁通過超級鏈接形成了圖。PageRank假設用戶從所有網頁里隨機挑出一個網頁，然后開始通過超級鏈接進行網上沖浪。到達每個網頁后，用戶首先會以d的概率繼續沖浪，而在沖浪時，用戶會以同等的概率在當前網頁的所有超級鏈接中隨機挑選一個進入下一個網頁。那么，在這種模擬下，最終每個網頁都會有一個被用戶訪問到的穩定概率，而這個概率就是網頁的排名。

PageRank算法通過如下的迭代關系式來計算網頁的權重：

其中PR(i)是網頁i的排名，d是用戶每次繼續沖浪的概率，N是所有網頁的總數。in(i)是指向網頁i的所有網頁的集合，out(j)是網頁j鏈向的網頁的集合。

下面我們舉一個簡單的例子來說明PageRank算法，我們用圖11所示的例子來演示一下PageRank的迭代過程。

圖11 說明PageRank算法的圖例

(1)一開始，每個頂點的排名都是一樣的，PR(A) = PR(B) = PR(C) = PR(D) = PR(E) = 1 / 5，令d = 0.85。

(2)根據前面的迭代關系式有

PR(A)=(1–0.85)/5+0.85*(PR(B)/2)=0.115
PR(B)=(1–0.85)/5+0.85*(PR(C)/1)=0.2
PR(C)=(1–0.85)/5+0.85*(PR(A)/2+ PR(D)/2+ PR(E)/2)=0.285
PR(D)=(1–0.85)/5+0.85*(PR(E)/2)=0.115
PR(E)=(1–0.85)/5+0.85*(PR(A)/2+ PR(B)/2+ PR(D)/2)=0.285

(3)繼續按照前面的迭代關系式，有

PR(A)=(1–0.85)/5+0.85*(PR(B)/2)=0.115
PR(B)=(1–0.85)/5+0.85*(PR(C)/1)=0.27225
PR(C)=(1–0.85)/5+0.85*(PR(A)/2+ PR(D)/2+ PR(E)/2)=0.248875
PR(D)=(1–0.85)/5+0.85*(PR(E)/2)=0.151125
PR(E)=(1–0.85)/5+0.85*(PR(A)/2+ PR(B)/2+ PR(D)/2)=0.21275

我們可以按照上面的步驟一步步迭代下去，最終得到所有頂點的PageRank排名。

但是，從上面的描述可以看到，PageRank只是計算了所有頂點的全局排名，并不能用來計算一個頂點相對于另一個頂點的相關度排名。因此，很多研究人員對PageRank做出了修改，其中一個著名的修改就是TopicRank算法。

PageRank算法認為，用戶每次都是從所有頂點中以相同的概率隨機挑選一個頂點，然后開始隨機游走，而且在每次隨機游走經過每個頂點時，都會有1 - d的概率停止游走。那么，如果我們要計算所有點相對于某一個頂點的相關度排名，我們可以假設用戶每次都從某一個頂點v出發，然后在每次隨機游走經過每個頂點時都以1-d的概率停止游走，從v重新開始。 那么，最終每個頂點被訪問的概率就是這些頂點和v的相關度排名。

PageRank可以用來給圖中的頂點進行全局的排名，但它無法用來給每個用戶個性化的對所有物品排序。為了解決個性化排名的問題，斯坦福大學的Haveliwala提出了TopicRank的算法 ，這個算法可以用來做個性化排序，因此本文將其稱為PersonalRank。PersonalRank的迭代公式如下：

可以看到，PersonalRank和PageRank的區別在于用ri代替了1/N，也就是說，從不同的點重新開始的概率不同了。那么，假設如果我們要計算所有頂點和頂點k的相關度排名，我們可以定義如下：

然后利用上面的迭代公式，就可以計算出所有頂點相對于k的相關度排名。我們將這里的稱為頂點i的啟動概率。

回到給用戶推薦物品這個問題上來，在我們構造出用戶-物品-標簽的圖之后，如果我們要給用戶u做推薦，我們可以令頂點v(u)的啟動概率為1，而其他頂點的啟動概率為0。然后用上面的迭代公式來計算所有物品對應的頂點相對于v(u)的排名。

下面兩段Python代碼給出了如何從用戶行為記錄集合tagging_records中構建圖，以及如何在圖上給用戶進行推薦。

defBuildGraph(tagging_records):graph = dict()for user, item, tag in tagging_records:addToMat(graph,‘u:’+user,‘i:’+item,1)addToMat(graph,‘i:’+item,‘u:’+user,1)addToMat(graph,‘u:’+user,‘t:’+tag,1)addToMat(graph,‘t:’+tag,‘u:’+user,1)addToMat(graph,‘t:’+tag,‘i:’+item,1)addToMat(graph,‘i:’+item,‘t:’+tag,1)defRecommend(user, d, K):rank = dict()rank[‘u:’+user]=1for step in range(0:K):for i, ri in rank.items():for j, wij in graph[i]:tmp_rank[j]+= d * ri * wijtmp_rank[‘u:’+ user]=(1– d)sum_weight = sum(tmp_rank.values())rank = dict()for i, ri in tmp_rank.items():rank[i]= ri / sum_weighttmp_rank = dict()return rank

這里，d是前面提到的繼續隨機游走的概率，K是迭代的次數。在上面從某一個用戶節點開始隨機游走時，迭代K步最多可以走到離該用戶節點距離為K之內的所有頂點，而其他頂點的權重為0。

在傳統的PersonalRank中，我們需要迭代很多次，直到所有頂點的權重都穩定了為止。但是，如果我們為每個用戶做推薦，都需要在全圖上進行迭代，直到全圖的所有頂點的權重都收斂，這樣的時間復雜度太大了。因此，我們在實際的應用中一般只迭代比較少的次數。

用圖模型解釋前面的簡單算法

在介紹了圖模型后，我們可以用圖模型來重新看待前面提到的簡單的算法。在那個算法中，用戶對物品的興趣通過如下的公式計算：

這個公式認為用戶對物品的興趣通過標簽來傳遞，因此這個公式可以通過一個比前面簡單的圖來建模（記為SimpleTagGraph）。給定用戶標簽行為記錄(u,i,b)，SimpleTagGraph會增加兩條有向邊，一條由用戶節點v(u)指向標簽節點v(b)，另一條由標簽節點v(b)指向物品節點v(i)。

圖12就是一個簡單的SimpleGraph的例子。在構建了SimpleGraph后，利用前面的PersonalRank算法，令K = 1，就是我們前面提出的簡單推薦算法。

圖12 SimpleGraph的例子

[相關實驗：發表時公布

A. 迭代次數K對精度的影響

B. 邊權重的定義對精度的影響

]

基于標簽的推薦解釋

---

基于標簽的推薦的最大好處是可以利用標簽來做推薦解釋，這方面的代表性應用是豆瓣的個性化推薦系統。圖13展示了豆瓣讀書的個性化推薦界面。

圖13 豆瓣讀書的個性化推薦應用“豆瓣猜”的界面

如圖13所示，豆瓣讀書推薦結果包括兩個部分。上面是一個標簽云，表示用戶的興趣分布，標簽的尺寸越大，表示用戶對這個標簽相關的圖書越感興趣。比如圖13顯示了我在豆瓣的閱讀興趣，從上方的標簽云可以看到，豆瓣認為我對“編程”、“機器學習”、“軟件開發”感興趣，這是因為我看了很多IT技術方面的圖書，豆瓣認為我對“東野圭吾”感興趣，是因為我看了好幾本他的偵探小說，同時因為我對人文學科比較感興趣，所以豆瓣認為我對“傳記”、“文化”比較感興趣。單擊每一個標簽云中的標簽，都可以在標簽云下方得到和這個標簽相關的圖書推薦，比如圖13就是機器學習相關的圖書推薦。

豆瓣這樣組織推薦結果頁面有很多好處。首先這樣提高了推薦結果的多樣性。我們知道，一個用戶的興趣在長時間內是很廣泛的，但在某一天又比較具體。因此，我們如果想在某一天擊中用戶當天的興趣，是非常困難的。而豆瓣通過標簽云，展示了用戶的所有興趣，然后讓用戶自己根據他今天的興趣選擇相關的標簽，得到推薦結果，從而極大地提高了推薦結果的多樣性，使得推薦結果更容易滿足用戶多樣的興趣。

同時，標簽云也提供了推薦解釋的作用。用戶通過這個界面可以知道豆瓣給自己推薦的每一本書都是基于它認為自己對某個標簽感興趣。而對于每個標簽，用戶總能通過回憶自己之前的行為來知道自己是否真的對這個標簽感興趣。

我們知道，要讓用戶直接覺得推薦結果是有道理的，是很困難的。而豆瓣將推薦結果的可解釋性拆分成了兩個部分，首先讓用戶覺得標簽云是有道理的，然后讓用戶覺得從某個標簽推薦出某本書也是有道理的。因為生成讓用戶覺得有道理的標簽云比生成讓用戶覺得有道理的推薦圖書更加簡單，標簽和書的關系就更容易讓用戶覺得有道理，從而讓用戶最終覺得推薦出來的書也是很有道理的。