張世堯，張順香

（安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001）

基于用戶聚類的微博話題推薦算法

張世堯，張順香

（安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001）

微博話題推薦算法的作用是當(dāng)用戶面臨微博信息過載時(shí)，結(jié)合用戶的基本信息，幫助用戶找到對(duì)自己有價(jià)值的微博話題。微博推薦算法的核心任務(wù)是以用戶信息為基礎(chǔ)，分析用戶的偏好，并推薦給其他信息相似的用戶。本文提出的基于用戶聚類的微博推薦算法包括三個(gè)層次，即用戶微博話題特征提取、用戶聚類、微博話題推薦。實(shí)驗(yàn)表明該系統(tǒng)的準(zhǔn)確率達(dá)到50.2%，可準(zhǔn)確地為用戶進(jìn)行微博話題推薦，并提高了用戶瀏覽微博的效率。

微博話題；用戶聚類；推薦

推薦系統(tǒng)的作用是當(dāng)用戶面臨信息過載時(shí)，結(jié)合用戶的基本信息，幫助用戶找到對(duì)自己有價(jià)值的信息［1］。近年來，微博飛速發(fā)展，據(jù)最新統(tǒng)計(jì)，僅新浪微博的注冊(cè)用戶人數(shù)就已達(dá)到5億，日活躍用戶達(dá)到4 700萬，據(jù)文獻(xiàn)［2］統(tǒng)計(jì)，118萬用戶的平均關(guān)注數(shù)為469個(gè)，這些用戶每天會(huì)產(chǎn)生大量的微博信息。這些微博信息是否每一條都對(duì)用戶有價(jià)值？用戶對(duì)于微博構(gòu)成的數(shù)據(jù)集是否能有效的判別［2］？也就是說，用戶面臨著非常嚴(yán)重的信息過載。

為解決這一問題，本文提出了基于用戶聚類的微博話題推薦算法。推薦算法的核心任務(wù)是以用戶信息為基礎(chǔ)，分析用戶的偏好話題，并推薦給其他信息相似的用戶。目的是幫助用戶在浩如煙海的微博話題中快速、有效的找出自己感興趣的微博話題。

本文提出的基于用戶聚類的微博話題推薦算法包括三個(gè)層次：

(ⅰ) 用戶話題特征提取，將用戶過往微博進(jìn)行分詞，特征詞提取，獲取用戶興趣話題特征矩陣。

(ⅱ)結(jié)合(ⅰ)利用凝聚層次聚類算法對(duì)用戶進(jìn)行聚類。

(ⅲ)結(jié)合(ⅱ)，對(duì)聚類簇中的每個(gè)用戶，推薦給同一聚類簇內(nèi)，當(dāng)前用戶關(guān)注而其他用戶沒有關(guān)注的話題，具有一定的準(zhǔn)確性。

1　相關(guān)工作

關(guān)于微博話題推薦算法，國(guó)內(nèi)外已有大量學(xué)者對(duì)其進(jìn)行研究，大多都是根據(jù)用戶的行為（評(píng)論，過往微博，關(guān)注）建立用戶模型，并根據(jù)模型通過聚類或者計(jì)算相似度等方法，對(duì)用戶進(jìn)行微博推薦。文獻(xiàn)［3］利用概率主題模型挖掘用戶潛在的主題信息，根據(jù)用戶之間的轉(zhuǎn)發(fā)、評(píng)論情況，計(jì)算用戶的互動(dòng)系數(shù)，過濾信息熵低的微博，通過微博的評(píng)分公式，給每條待推薦微博打分，并將分?jǐn)?shù)高的微博推薦給用戶，從而實(shí)現(xiàn)微博的推薦功能。文獻(xiàn)［4］通過用戶過往微博為用戶建立興趣模型，在此基礎(chǔ)上聚類，并將同一類中與用戶過往微博相似度高的微博推薦給用戶。文獻(xiàn)［5］利用自然語(yǔ)言處理工具建立一個(gè)以命名實(shí)體和核心項(xiàng)的形式自動(dòng)提取用戶興趣的系統(tǒng)，從而根據(jù)用戶興趣推薦給有相似興趣的朋友。文獻(xiàn)［6］通過深入研究用戶的互聯(lián)網(wǎng)行為，如轉(zhuǎn)發(fā)，評(píng)論，并通過研究用戶行為和用戶興趣，根據(jù)電容放電原理，提出了一種基于興趣流的動(dòng)態(tài)模型。文獻(xiàn)［7］提出了Twittomender系統(tǒng)，根據(jù)用戶及其粉絲和好友發(fā)布的tweet、用戶在twitter上的關(guān)系網(wǎng)絡(luò)，對(duì)用戶進(jìn)行建模，同時(shí)利用Lucene的TF-IDF衡量關(guān)鍵詞的權(quán)重。文獻(xiàn)［8］提出了一種結(jié)合用戶評(píng)論的內(nèi)容推薦算法，通過LDA對(duì)用戶評(píng)論內(nèi)容特征項(xiàng)進(jìn)行降維，計(jì)算產(chǎn)品之間的相似度，然后結(jié)合用戶的打分權(quán)重得到綜合相似度，最后為其推薦可能感興趣的產(chǎn)品。文獻(xiàn)［9］提出了一種預(yù)測(cè)算法來推算概率模型的參數(shù)，并且使用MapReduce來處理大規(guī)模數(shù)據(jù)。文獻(xiàn)［10］提出一種基于兩階段聚類的推薦算法GCCR，將圖摘要方法和基于內(nèi)容相似度的算法結(jié)合，實(shí)現(xiàn)基于用戶興趣的主題推薦。

2　用戶話題特征提取

2.1基本概念

定義1用戶話題特征向量（Topic Feature Vector）。

用戶微博中有很多出現(xiàn)頻次較高，但是對(duì)話題提取無意義的詞，比如“的”，“很”，如果都記為話題會(huì)造成很大的冗余信息，同時(shí)使推薦算法難以準(zhǔn)確工作。本文依照文獻(xiàn)［11-12］對(duì)用戶過往微博分詞，特征詞提取，去除多余詞，并根據(jù)詞的權(quán)重，找出每一個(gè)用戶的興趣的話題列表，這些話題列表可以用向量表示，本文把這種向量記為用戶話題特征向量TFV，TFV描述如下：

其中，ti為話題關(guān)注表示符號(hào)，當(dāng)用戶關(guān)注話題時(shí)，ti的值為1，如果不關(guān)注，則值為0，m為所有用戶關(guān)注話題的總個(gè)數(shù)。

定義2用戶話題特征矩陣（Topic Feature Matrix）。

根據(jù)定義1，我們得到了用戶話題特征向量TFV，假設(shè)用戶的數(shù)量為n，則n個(gè)話題特征向量就構(gòu)成了一個(gè)用戶話題特征向量矩陣TFM。單個(gè)用戶的話題特征向量的長(zhǎng)度為m，則用戶話題特征向量矩陣TFM的大小就為n*m，用戶話題特征向量可描述為如下形式：

其中t在定義一里已經(jīng)說明，為話題特征表示符號(hào)，n為用戶數(shù)量，m為話題的總個(gè)數(shù)。表1給出了話題矩陣的一些實(shí)例。

表1　用戶話題特征矩陣矩陣實(shí)例圖

定義3用戶微博話題集合T（Topic Grounp）。

對(duì)于所有微博用戶關(guān)注的話題，我們定義一個(gè)用戶話題集合T，用來保存用戶關(guān)注的所有話題，用戶微博話題集合T的定義描述如下：

T=｛tpi|i=1，…，m｝（3）

tp為單個(gè)微博話題，m為所有用戶關(guān)注的微博話題的總個(gè)數(shù)。

2.2用戶微博話題特征數(shù)據(jù)結(jié)構(gòu)

獲得用戶話題列表后，需要一種數(shù)據(jù)結(jié)構(gòu)對(duì)用戶話題列表進(jìn)行保存，本文選擇用鏈表保存單個(gè)用戶的話題列表，用鏈表表示的好處是，因?yàn)槊總€(gè)用戶的話題列表的長(zhǎng)度是不固定的，用鏈表大大節(jié)省了所需空間，而且鏈表長(zhǎng)度可以隨著用戶話題列表的長(zhǎng)度變化而變化。鏈表的數(shù)據(jù)結(jié)構(gòu)如下所示。

表頭：

ID為用戶的id，name為用戶昵稱，address為用戶地址，sex用戶性別，age為用戶年齡，node為話題指針域。

話題結(jié)點(diǎn)：

user-ID為此話題的用戶ID，content為內(nèi)容，time為發(fā)表時(shí)間，topic-hot為話題熱度，node為話題指針域。

2.3獲得用戶話題特征矩陣TFM

根據(jù)用戶的話題鏈表集合，可以生成用戶話題特征向量TFV和用戶話題特征矩陣TFM，方面下一步在用戶聚類中計(jì)算用戶鄰近度dist。

算法1：用戶話題特征矩陣生成算法

輸入：用戶話題鏈表集合U=｛U1，U2，…，Uk｝，話題數(shù)目m，用戶數(shù)目n，話題列表集合T=｛tp1，tp2，…，tpm｝

輸出：用戶話題特征矩陣TFM

算法說明：

(ⅰ)步驟1新建了用戶話題特征矩陣TFM；

(ⅱ)步驟3到步驟9將用戶話題特征矩陣TFM初始化；

(ⅲ)步驟14找到話題t在話題列表里的位置，并將用戶話題關(guān)注表示符號(hào)置1；

(ⅵ)步驟12到18對(duì)每個(gè)用戶關(guān)注的話題戶話題關(guān)注表示符號(hào)置1。

該算法主要的時(shí)間復(fù)雜度在于兩個(gè)雙重循環(huán)，第一個(gè)循環(huán)（步驟3到9）的時(shí)間復(fù)雜度為O （n*m），第二個(gè)循環(huán)（步驟12到18）的時(shí)間復(fù)雜度為 O（n*m2），所以該算法的時(shí)間復(fù)雜度為 O （n*m2）。該算法的主要用到n*m的二維矩陣存儲(chǔ)TFM，所以算法的空間復(fù)雜度為O（n*m）。

3　用戶聚類

根據(jù)上文得到的用戶話題特征矩陣TFM，我們可以對(duì)話題興趣相似的用戶進(jìn)行聚類，得到話題興趣相似的用戶聚類簇。同一個(gè)聚類簇內(nèi)的用戶關(guān)注的話題相似，從而可以為下一步對(duì)用戶進(jìn)行微博話題推薦做好鋪墊。

凝聚層次聚類是一種自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，根據(jù)鄰近度和并這些簇，直至滿足條件或者只剩下一個(gè)簇為止，根據(jù)鄰近度選擇的不同可以把凝聚層次聚類劃分為單鏈，全鏈和組平均，本文使用全鏈計(jì)算鄰近度。使用用戶話題特征矩陣TFM作為聚類的輸入。

兩個(gè)A，B用戶之間的距離dist為兩個(gè)用戶之間的余弦距離，

則用戶聚類算法如下。

算法2：用戶聚類算法

輸入：用戶話題特征矩陣TFM

輸出：用戶聚類簇集合C

9： 計(jì)算出C中每個(gè)聚類簇之間的鄰近度，

則鄰近度可以構(gòu)成一個(gè)矩陣M

10：else

11：repeat

12：選取max（dist（Ui，Uj）），使Ui=Ui∪Uj，

則C=｛C1，…，Cn-1｝

13：更新鄰近度矩陣M

14：until達(dá)到聚類數(shù)目

15：end

算法說明：

(ⅰ)將每個(gè)用戶看成是一個(gè)簇（步驟1到8）；

(ⅱ )計(jì)算每對(duì)用戶之間的相似度dist（A，B），計(jì)算出初始相似度矩陣；（步驟9）

(ⅲ)選取具有最大相似度的簇對(duì)max（dist（Ui，Uj）），并將Ui和Uj合并為一個(gè)新的簇類Uk=Ui∪Uj，從而構(gòu)成U的一個(gè)新的簇類C=｛C1，…，Cn-1｝；

(ⅳ )更新相似矩陣；（步驟13）

(ⅴ)到聚類數(shù)目達(dá)到為止。（步驟14）

該算法使用了鄰近度矩陣，假設(shè)鄰近度矩陣是對(duì)稱的，且有m個(gè)用戶，則需要存儲(chǔ)m2/2個(gè)鄰近度，因此總的空間復(fù)雜度為O（m2）。步驟4的時(shí)間復(fù)雜度為當(dāng)前簇個(gè)數(shù)的平方O（m2），步驟5同樣復(fù)雜度為O（m）則總共需要O（m3）的復(fù)雜度，如果使用有序表存儲(chǔ)聚類簇，則時(shí)間復(fù)雜度可以降為O（m2log m）

4　微博話題推薦算法

結(jié)合用戶話題特征矩陣TFM，用戶聚類的結(jié)果集，我們可以設(shè)計(jì)微博話題推薦算法，算法的大概思想是，推薦給同一聚類簇內(nèi)，當(dāng)前用戶關(guān)注而其他用戶沒有關(guān)注的話題，具有一定的準(zhǔn)確性。

4.1微博話題推薦算法

微博話題推薦算法的思想是，當(dāng)用戶A和B都同屬于一個(gè)聚類簇時(shí)，推薦給用戶B用戶A關(guān)注，而用戶B沒有關(guān)注的話題。推薦算法如下：

算法3：微博話題推薦算法

輸入：用戶簇集合C=｛C1，C2，…，Cm｝

輸出：用戶微博話題推薦

1：for用戶簇c in C

2： for用戶u in c

3：for話題t in u

4：if t=1

5：判斷t可在當(dāng)前c中的其他用戶u中，如果不存在，則推薦給當(dāng)前c中其他用戶u。

6：endif；

7：endfor；

8： endfor

9：endfor

10：end

算法說明：

用戶簇集合中的每一個(gè)用戶簇（對(duì)應(yīng)步驟1 到9），每一個(gè)用戶簇中的用戶（對(duì)應(yīng)步驟2到8），每一個(gè)用戶關(guān)注的話題（對(duì)應(yīng)步驟3到7），用戶關(guān)注值t為1時(shí)（步驟4），判斷用戶簇中的其他用戶是否關(guān)注該話題（步驟5），對(duì)沒關(guān)注該話題的同一用戶簇中的用戶推薦當(dāng)前話題。

該假設(shè)用戶簇集合中的用戶簇?cái)?shù)目為m，單個(gè)用戶簇中的用戶數(shù)目為n，單個(gè)用戶關(guān)注的話題數(shù)目為p，則該算法需要的空間復(fù)雜度為O （m*n*p），時(shí)間復(fù)雜度也為O（m*n*p）。

5　實(shí)驗(yàn)分析

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

本文使用信息檢索系統(tǒng)常用的準(zhǔn)確度率（精度）來評(píng)價(jià)系統(tǒng)的效果。準(zhǔn)確率計(jì)算方法為：P=|C?R|/|R|，其中R為系統(tǒng)推薦給用戶的條目，C為用戶感興趣的條目。簡(jiǎn)單來說，就是用戶感興趣的條目數(shù)與總的推薦的條目數(shù)的比率［13］。

微博話題推薦算法和其他算法不同，必須要獲得用戶反饋才能評(píng)判算法推薦的準(zhǔn)確度，實(shí)驗(yàn)分為以下幾個(gè)步驟：

(ⅰ)搭建實(shí)驗(yàn)環(huán)境；

本次推薦算法實(shí)驗(yàn)的環(huán)境為dell xps 13筆記本電腦，MySql 5.0和Python 2.7，以及另外10臺(tái)個(gè)人筆記本電腦用來查閱推薦結(jié)果。

(ⅱ)準(zhǔn)備基本數(shù)據(jù)；

選取10名用戶微博作為實(shí)驗(yàn)數(shù)據(jù)，分別用爬蟲獲取他們的歷史微博，并分別用user表保存用戶數(shù)據(jù)，weibo表保存微博歷史數(shù)據(jù)。

(ⅲ)算法實(shí)際運(yùn)行；

通過每名用戶的歷史微博，提取出用戶興趣話題，并建立用戶話題特征矩陣TFM，對(duì)用戶進(jìn)行聚類，分別獲得對(duì)10名用戶推薦的話題。

(ⅳ)收集統(tǒng)計(jì)結(jié)果。

微博話題推薦算法經(jīng)過運(yùn)行，得出推薦結(jié)果，然后通過微博私信的方式由程序自動(dòng)推薦給10名用戶，10名用戶的反饋如表2所示

表2　用戶反饋表

由表2可知，用戶被推薦的話題數(shù)目數(shù)量不同，被推薦話題數(shù)目和感興趣的話題數(shù)目也不相同，但是準(zhǔn)確率一直穩(wěn)定50.2%附近，取得了不錯(cuò)的推薦效果。

5.2實(shí)驗(yàn)對(duì)比

將本文提出的推薦算法與基于協(xié)同過濾的推薦［14］、基于內(nèi)容的推薦［15］進(jìn)行對(duì)比，在試驗(yàn)中，三個(gè)推薦系統(tǒng)（算法）均使用相同的用戶數(shù)據(jù)，得出的對(duì)比情況如表3所示。

表3　算法比較表

從表3可以看出，三種推薦系統(tǒng)（算法）都能實(shí)現(xiàn)對(duì)用戶進(jìn)行微博（話題）推薦，后兩種推薦系統(tǒng)（算法）的最高準(zhǔn)確率較高，但是平均準(zhǔn)確率低于本文提出的推薦算法，說明本文提出的算法比較穩(wěn)定，在最好和最壞的情況都能穩(wěn)定的為用戶推薦微博話題。

6總結(jié)

本文針對(duì)用戶面臨微博信息過載的問題，為了讓用戶能省時(shí)省力的獲取到自己感興趣的微博話題，設(shè)計(jì)了基于用戶聚類的微博話題推薦算法。本文首先將用戶過往微博進(jìn)行分詞，特征詞提取，確定用戶興趣話題，建立用戶話題特征矩陣，然后對(duì)用戶進(jìn)行聚類，接著對(duì)聚類簇內(nèi)的每個(gè)用戶，推薦給同一用戶聚類簇內(nèi)當(dāng)前用戶關(guān)注，而簇內(nèi)其他用戶沒有關(guān)注的話題，最后給出微博話題推薦算法的試驗(yàn)效果分析，證明本文提出的算法是有效可行的。

［1］ 項(xiàng)亮.推薦系統(tǒng)實(shí)踐［M］.北京：人民郵電出版社，2012.

［2］ 慕福楠.面向微博用戶的推薦多樣性研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2013.

［3］ 謝昊.基于主題模型的微博話題推薦算法研究［J］.華東師范大學(xué)，2013.

［4］ 蔣超.基于用戶聚類和語(yǔ)義詞典的微博推薦系統(tǒng)［D］.杭州：浙江大學(xué)，2013.

［5］ Piao S，Whittle J A feasibility study on extracting twitter users'interests using NLP tools for serendipitous connections［C］//Proceedings of the 3rd IEEE International Conference on Social Computing，2011：910-915.

［6］ 趙釹森.基于用戶行為的動(dòng)態(tài)推薦系統(tǒng)算法研究及實(shí)現(xiàn)［D］.成都：電子科技大學(xué)，2013.

［7］ Hannon J，Bennett M，Smyth B.Recommending twitter users to follow using content and collaborative filtering approaches.［J］.In NIPS*17，2010：199-206.

［8］ 劉英.基于用戶評(píng)論的個(gè)性化產(chǎn)品推薦系統(tǒng)［D］.北京：北京郵電大學(xué)，2015.

［9］ Kim Y，Twitobi S K.A recommendation system for twitter using probabilistic modeling［C］//IEEE 13th International Conference on Data Mining，2011：340-349.

［10］ 陳克寒，韓盼盼，吳健.基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法［J］.計(jì)算機(jī)學(xué)報(bào)，2013，36（2）：349-359.

［11］Luo X F，F(xiàn)ang N，Hu B，et al.Semantic representation of scientific documents for the e-science Knowledge Grid［J］.Concurrency and Computation-Practice&Experience，2008，20（7）：839-862.

［12］Liang Z，Jing H N，Zhi A S.Algorithm design for personalization recommendation systems［J］.Journal of Computer Research&Development，2002，39（8）：986-991.

［13］Sakaguchi T，Akaho Y，Takagi T，et al.Recommendations in Twitter using conceptual fuzzy sets［C］.IEEE，F(xiàn)uzzyInformationProcessingSociety（NAFIPS），2010 Annual Meeting of the North American.2010：1-6.

［14］Sebastiani F.Machine learning in automated text categorization［J］.ACM Computing Surveys，2002，34（1）：1-47.

［15］Miyahara K，Michael J P.Collaborative filtering with the simple bayesian classifier［Z］，2000：679-689.

A recommendation algorithm of Micro-blog topic based on user clustering

ZHANG Shi-yao，ZHANG Shun-xiang

（School of Computer Science and Engineering，Anhui University of Science and Technology，Huainan Anhui 232001，China）

The recommendation algorithm of micro-blog topic aims to help users find valuable micro-blog topic based on the users'basic information when overload information of micro-blog has occurred.The main tasks of the micro-blog recommendation algorithm are analyzing the users'p

and recommending a special micro-blog topic to other users with similar information.This paper proposes a user clustering-based micro-blog topic recommendation algorithm which includes three levels，namely the users micro-blog topic features extraction，users clustering，and users recommendation.Experimental results show that the accuracy of the proposed system is up to 50.2%.It can accurately recommend micro-blog topic for users.Thus，the efficiency of browsing the micro-blog can be improved greatly.

Micro-blog topic；user clustering；recommendation

TP391，TP393

A

1004-4329（2016）02-074-06

10.14096/j.cnki.cn34-1069/n/1004-4329（2016）02-074-06

2016-03-10

安徽省教育廳自然科學(xué)基金重點(diǎn)項(xiàng)目（KJ2015A111）；上海市信息安全綜合管理技術(shù)研究重點(diǎn)實(shí)驗(yàn)室（上海交通大學(xué)）開放課題（AGK2013002）資助。

張世堯（1991－），男，碩士研究生，研究方向：信息提取與推薦系統(tǒng)。