基于特征分析的微博用戶興趣發現算法*

趙巖露, 王晶, 沈奇威

（1 北京郵電大學網絡與交換技術國家重點實驗室, 北京 100876；2 東信北郵信息技術有限公司, 北京 100191）

1 引言

個性化推薦是一種廣泛使用的Web個性化服務應用程序，它根據用戶的興趣和特點，對信息資源進行收集、整理和分類，向用戶提供和推薦符合其興趣偏好或需求的信息[1]。而個性化推薦的本質是如何描述和發現用戶的興趣[2]。

社交網絡服務作為社會化媒體的出現，已經在用戶的日常生活中占據很大的地位。騰訊微博，作為中國最大的微博網站之一，擁有超過2億注冊用戶，每天產生超過4000萬條消息。由于社交網絡中用戶的入度和出度的分布也是滿足長尾分布的[3]，并且對于使用者來說用戶比消息本身重要的多，因此如何給用戶推薦其感興趣的用戶，并減少信息超載的風險就成了亟待解決的問題，也提供了尋求新的數據挖掘解決方案的機會[4]。

本文在騰訊微博的開放數據集基礎上，分析用戶的特征信息(包括用戶的個人基本信息、用戶的微博信息、用戶的行為信息和用戶的關注信息)，建立用戶興趣模型，發掘用戶的相關用戶列表，采用協同過濾的方法為用戶推薦其可能感興趣的明星用戶，達到個性化推薦的效果。

2 興趣模型研究現狀綜述

用戶興趣模型適用的場合很廣泛，無論是電子商務、社交網絡還是搜索引擎。

如何規劃系統的動作, 也是構建用戶模型過程中的一大難點[5,6]。

衡量一個用戶興趣模型好壞的主要因素是其表示用戶興趣的能力[7]。用戶興趣模型的計算方法主要采用協同過濾算法。學術界對協同過濾算法進行了深入研究，提出了很多方法，比如基于領域的方法、隱語義模型、基于圖的隨機游走算法等[3]。現有的協同過濾算法在計算推薦過程中將用戶訪問過的每個資源同等對待，這顯然是不合理的。在微博數據中，要結合用戶對每個用戶的實際交互行為，考慮為用戶間分配不同的權重。

在微博系統中，由于微博信息的不斷更新增多，所以信息的數量級比用戶的數量級大，考慮到計算時間和復雜度，就需要采用基于用戶的協同過濾推薦算法[8]。

3 微博數據集描述

微博數據集描述如表1所示。

本文認為一個微博數據集的特征應包括用戶的個人信息，微博信息，社交關系信息和行為信息這4個維度。其中個人信息反映用戶的基本社會屬性，微博信息反映用戶微博的的內容，社交關系信息反映用戶的社交圈，行為信息反映用戶的互動情況。這4個維度能很好的反映微博用戶的興趣，本文的興趣模型都是圍繞這些特征而進行分析計算。

4 算法描述

4.1 核心算法

將用戶的特征劃分為相互獨立的3個模型計算與其可能相關的用戶：

(1) 個人信息相關度模型：定義根據用戶的個人信息計算與其相關的用戶的方法為calcUserProfile。

(2) 微博信息相關度模型：定義根據用戶的微博內容信息計算與其相關的用戶的方法為calcUserKey Word。

(3) 社交信息相關度模型：定義根據用戶社交關系信息和行為信息計算與其相關的用戶的方法為calcUser SNS。

圖1 核心算法圖

表1 微博數據集

采用這3個模型分別計算用戶的相關用戶列表，結合模型融合的技術和TOP-N算法得到最終的推薦明星列表。

核心算法思路如圖1所示。

4.1.1 個人信息相關度模型

calcUserProfile采用統計的方法計算，計算方法如表2所示。系統中采用0.3作為閾值，與當前用戶相關度權值超過0.3的用戶按序組成與當前用戶的相關用戶列表，個人信息相關度如表2所示。

表2 個人信息相關度表

4.1.2 微博信息相關度模型

calcUserKeyWord采用向量空間模型計算。

當需要對未知用戶和用戶興趣模型進行比較時，就通過計算未知用戶的關鍵詞權重向量V(v1，v2，…，vn)和用戶興趣度向量W(w1，w2，…，wn)之間的余弦相似度公式(1)來度量， Sim(V，W)越大，說明兩個向量的匹配程度越高。

在微博信息相關度模型中，文本是用戶，詞組是用戶的關鍵詞信息。系統中采用0.05作為閾值，與當前用戶相似度權值超過0.05的用戶按序組成與當前用戶的相關用戶列表。

4.1.3 社交信息相關度模型

calcUserSNS采用圖的模型計算。

如圖2所示，令G(V，E)表示用戶與用戶間關系的無向圖，其中V是所有用戶頂點的集合，E是用戶與用戶之間的邊，代表用戶之間的相關程度。

圖2 用戶關系圖模型

本文采用基于隨機游走的PersonalRank算法來計算圖中頂點之間的相關性。

假設要對用戶A進行用戶推薦，可以從用戶A對應的節點VA開始在圖上進行隨機游走，游走到任何一個節點時，首先按照概率α決定是繼續游走，還是停止這次游走并從VA節點開始重新游走。如果決定繼續游走，那么就從當前節點指向的節點中按照均勻分布隨機選擇一個節點作為游走下次經過的節點。這樣，經過很多次隨機游走后，每個物品節點被訪問到的概率會收斂到一個數。最終的推薦列表中用戶的權重就是用戶節點的訪問概率。

上面的描述可以用公式(2)表示：

在社交信息相關度模型中， 系統采用系數α為0.8。對收斂后的用戶節點的訪問概率進行排序，即得到與當前用戶相關的用戶列表。

4.1.4 模型融合

單獨采用以上的某個模型都不能很好的解決推薦問題，所以需要采用模型融合的技術，將各個模型的結果進行融合，從而得到最終的推薦結果。

在本文中，采用加權融合的方法，優先級為社交信息模型>微博信息模型>個人信息模型。為了避免過擬合的問題，利用最小二乘法[9]，計算出3個模型的線性加權系數依次為0.8、0.5、0.3。將各個模型的預測結果值乘以線性加權系數并排序即得到最終的相關用戶列表。

4.1.5 產生推薦結果

對當前用戶的相關用戶列表，采用TOP-N算法進行明星用戶推薦。Top-N推薦是針對單個用戶產生的，它對每個人是不一樣的：通過對你的相關用戶列表進行統計，選擇累積出現權值最高的且不在你的關注列表中的N個明星用戶作為推薦結果。

4.2 冷啟動問題

在推薦系統中，必須考慮系統冷啟動的問題[10]，也就是用戶的行為數據不足的情況下系統推薦的問題。聚類算法作為無意識的自動發現算法，能很好的解決系統的冷啟動問題。本文采用改進的K-means算法，聚合出系統中明星的類別，為用戶推薦主流類別的用戶。

5 實驗結果

5.1 評測指標

主要依據信息檢索的常用指標，召回率、正確率和F-Measure[11]。正確率(Precision)定義為系統的推薦列表中用戶喜歡的產品和所有被推薦產品的比率。召回率(Recall)定義為推薦列表中用戶喜歡的產品與系統中用戶喜歡的所有產品的比率。

為了同時考察正確率和召回率，Pazzani等把二者綜合考慮提出了F指標[12]。F指標定義為：

其中，P為正確率，R為召回率。由于F指標把正確率和召回率統一到一個指標，因此得到了廣泛的應用。

測試采用的方法為K重交叉驗證法。該方法是最為普遍的計算推廣誤差的方法之一。

5.2 結果分析

實驗結果如圖3～5所示。

方法1：按照用戶微博中提取出的關鍵字和明星的關鍵字直接進行相似度計算。由于本方法依賴用戶和明星標簽的規模，故隨著樣本用戶集增大，召回率和正確率逐步增高，但是正確率仍舊在一個較低的范圍之內。值得注意的是，其召回率在正常的范圍內不斷穩定增長。

方法2：采用分析提取用戶好友列表的方法，將好友列表中用戶關注的明星做統計計算。本方法受用戶集增大而較大的影響，但是用戶集規模到達一定地步之后，用戶的關系網趨于穩定，影響幅度變得很小。同時，可以看出本方法的正確率始終保持在很高的規模，這樣從側面驗證了微博中用戶關注的重要意義。

方法3：采用本文提出的基于特征分析的興趣發現方法。 兼顧了方法1和方法2的優點，結果顯示其召回率不斷提升，正確率也維持在一個滿意的規模內。各項指標較前兩種方法都有一定的提升。

方法4：采用聚類的方法解決冷啟動問題。主要解決了召回率較低的問題，從系統內明星中進行聚類發掘，并根據用戶反饋修正更新推薦結果，可以看到在保證正確率維持在原有規模的基礎上，召回率較之前的3種方法有較大程度的提升。

總的來看，由3個圖比較可見，改進后的算法(即方法4)能得到最大且穩定的召回率和正確率。

圖3 推薦結果召回率曲線

6 結語

微博中的關系，只是整個社會科學中社會關系、人際關系的一部分，值得更深一步研究。

圖4 推薦結果正確率曲線

圖5 推薦結果F-Measure曲線

本文的創新之處在于對微博的數據特征進行了深入的分析，詮釋了微博用戶興趣在微博系統中的表達形式。在實際系統中，采用提取用戶的關注用戶列表作為推薦新用戶的主要依據，其優點是快速簡單，但是缺點是沒有充分考慮社交網絡中用戶的特征，而且在覆蓋率和新穎度上都無法保證。在分析和采用實際推薦系統方法的基礎上，圍繞微博系統特征進行推理分析和計算，比較多種方法的優劣，提出改進后的算法。實驗結果驗證表明改進后的算法較之前的算法在各個指標上有顯著提升。

[1] 林霜梅，汪更生，陳弈秋. 個性化推薦系統中的用戶建模及特征選擇[J]. 計算機工程，2007，33(17)：202-204+236.

[2] Jie Y. A short-term user Interest model for personalized recommendation[A]. Information Management and Engineering (ICIME)[C]. 2010 The 2nd IEEE International Conference.

[3] 項亮. 推薦系統實踐[M]. 北京：人民郵電出版社，2012.

[4] KDD Cup 2012，ACM SIGKDD，knowledge discovery and data mining conference, August 12-16，Beijing，China[EB/OL]. http://www.kddcup2012.org/c/kddcup2012-track1.

[5] 周繼恩，劉貴全，張春陽. 基于內部信念狀態POMDP模型在用戶興趣獲取中的應用[J]. 小型微型計算機系統，2004,25(11):91-95.

[6] Xu Z H，Lu R，Xiang L，Yang Q. Discovering user interest on Twitter with a modified author-Topic model[A]. 2011 IEEE/WIC/ACM International Conference[C].

[7] 郭新明，弋改珍. 基于向量空間模型的用戶興趣模型研究[J].咸陽師范學院學報. 2009，24(6)：53-55.

[8] 萬里，廖建新，王純. 基于社會網絡信息流模型的協同過濾算法[J]. 吉林大學學報(工學版), 2011，41(1)：275-280.

[9] http://zh.wikipedia.org/wiki/最小二乘法.

[10] 佐凱. 基于云計算的微博推薦系統[D]. 南京：南京理工大學, 2012.

[11] 劉建國，周濤, 郭強. 個性化推薦系統評價方法綜述[J]. 復雜系統與復雜性科學. 2009,6(3)：5-14.

[12] Pazzani M，Billsus D. Learning and revising user profiles：the identification of interesting web sites[J]．Machine Learning，1997，27：313-331.