基于特征映射的微博用戶標簽興趣聚類方法*

秦 雨 余正濤 王炎冰 石林賓 潘華山

(1.昆明理工大學信息工程與自動化學院，昆明,650500； 2.昆明理工大學智能信息處理重點實驗室,昆明,650500)

?

基于特征映射的微博用戶標簽興趣聚類方法*

秦 雨1,2余正濤1,2王炎冰1,2石林賓1,2潘華山1,2

(1.昆明理工大學信息工程與自動化學院，昆明,650500； 2.昆明理工大學智能信息處理重點實驗室,昆明,650500)

針對現(xiàn)有的用戶興趣聚類方法沒有考慮用戶標簽之間存在的語義相關性問題，提出了一種基于特征映射的微博用戶標簽興趣聚類方法。首先，獲取待分析用戶及其所關注用戶的用戶標簽，選取出現(xiàn)頻數(shù)高于設定閾值的標簽構建模糊矩陣的特征維；然后，考慮標簽之間的語義相關性，利用特征映射的思想將用戶標簽根據(jù)其與特征維標簽之間的語義相似度映射到每個特征維下，計算每個特征維所對應的特征值；最后，利用模糊聚類得到了不同閾值下的用戶興趣聚類結果。實驗結果表明，本文提出的基于特征映射的微博用戶標簽興趣聚類方法有效地改善了用戶興趣聚類效果。

微博；特征映射；模糊聚類；語義相似度

引 言

隨著社交網絡的不斷發(fā)展，社交網絡的參與者越來越多，面對如此龐大的用戶群體，如何準確地把握用戶興趣，自動為用戶找到與之興趣相近的用戶，成為許多專家和學者研究的熱點問題。在用戶興趣挖掘領域，國內外專家學者已經開展了大量的研究工作。Huang等[1]提出一種通過形式概念分析技術從正例文檔中建立用戶興趣模型的方法。Pazzani等[2]通過分析用戶對頁面的收藏行為和添加書簽的行為構建用戶興趣模型。Shen等[3-4]綜合考慮用戶的查詢軌跡、用戶瀏覽過的網頁信息以及用戶在各網站上的點擊次數(shù)構建用戶興趣模型。Zhou等[5]利用認知情感理論，以用戶瀏覽軌跡作為數(shù)據(jù)來源，通過計算用戶之間的相關程度構建用戶興趣模型。Teevan等[6]通過收集用戶的查詢和瀏覽歷史對用戶興趣進行建模等。以上方法借助分析用戶的行為歷史記錄、瀏覽記錄或從網頁文本角度出發(fā)挖掘用戶興趣，都取得了較好的效果。對于微博用戶興趣挖掘任務，Shu等[7]提出了一種基于Twitter-Rank的微博用戶興趣模型構建方法。Liu等[8]通過提取微博中的關鍵詞挖掘用戶興趣。Chen[9]分別利用用戶本身微博和用戶的粉絲微博進行了用戶興趣發(fā)現(xiàn)。對于微博用戶興趣挖掘，采用微博用戶標簽進行用戶興趣提取是較為直觀的方法，現(xiàn)有的方法主要是基于統(tǒng)計學習思想對標簽信息進行分析從而獲取用戶興趣。閻春霖等[10]綜合考慮標簽的使用頻率和稀疏度,通過構造鄰接矩陣挖掘用戶興趣?？岛t[11]利用微博標簽表示用戶興趣,使用加權二分圖算法提高用戶興趣發(fā)現(xiàn)效果。以上利用統(tǒng)計學習挖掘用戶興趣的方法沒有考慮用戶標簽之間存在的語義相關性,學習過程中選取的表征用戶興趣的特征維由于維數(shù)的限制不可能覆蓋所有的標簽詞,從而導致一些標簽詞不能有效表征到用戶興趣的特征向量上。基于以上分析，本文探討通過結合詞語相似度計算和特征映射的思想來實現(xiàn)用戶興趣聚類。

1 基本思想

利用統(tǒng)計學習挖掘用戶興趣的方法在學習過程中，選取的表征用戶興趣的特征維由于維數(shù)的限制不可能覆蓋所有的標簽詞,從而丟失一些對用戶興趣聚類有指導意義的信息。比如：通過統(tǒng)計獲取的特征空間中存在“旅行”特征維，而對于某用戶，表征其興趣的標簽集合當中沒有“旅行”標簽，如果按照詞頻統(tǒng)計特征進行處理，該用戶在“旅行”特征維上的特征值為0。但在特征分析時發(fā)現(xiàn)，該用戶的標簽集合中可能存在與“旅行”語義很相近的標簽，如有“旅游”標簽，可以考慮計算“旅游”和“旅行”的詞語相似度，通過映射的方式將“旅游”標簽的信息映射到“旅行”特征維標簽上，這樣可以更加逼近用戶的真實興趣。

基于特征映射的微博用戶標簽興趣聚類方法的主要思想是：某個待分析用戶的用戶興趣可以通過用戶本人的標簽和其所關注用戶的標簽構成的標簽集合進行表征，所有待分析用戶的標簽集合可以構成一個用戶標簽庫，然后對該標簽庫中存在的大量用戶標簽做詞頻統(tǒng)計獲取用戶興趣特征維，再結合詞語相似度計算和特征映射思想確定每一特征維上的特征值，最后通過模糊聚類實現(xiàn)用戶興趣聚類。

2 基于特征映射的微博用戶標簽興趣聚類過程

2.1 特征選取

通過新浪微博應用程序編程接口(Application programming interface,API)獲取每個用戶和其所關注用戶的標簽，由于用戶標簽的建立是半指導方式，用戶自己填寫的個性化標簽存在標簽隨意性強的特點，對該類標簽的分析處理有一定困難。因此，本文的處理方式是去除所有帶有特殊符號和包含英文單詞的個性化標簽。通過以上處理，可以得到所有滿足要求的用戶標簽構成的標簽集合。利用實驗室自主開發(fā)的新浪微博標簽詞頻統(tǒng)計工具統(tǒng)計所有標簽的出現(xiàn)次數(shù)，對標簽出現(xiàn)次數(shù)從大到小排序，通過設定閾值選取排序靠前的標簽作為用戶向量的特征維。

2.2 基于特征映射的用戶特征向量表征

為了更好地表征用戶特征向量，考慮標簽之間的語義相關性，引入特征映射的思想將用戶標簽根據(jù)其與特征維標簽之間的語義相似度映射到每個特征維上，從而計算每個特征維所對應的特征值。在特征映射過程中，針對某些長標簽無法直接計算詞語相似度的問題，首先利用中國科學院的ICTCLAS分詞系統(tǒng)對長標簽進行分詞，將其表示成一個詞的集合，再計算用戶標簽與特征維標簽之間的平均語義相似度。具體做法如下：為了方便標簽的統(tǒng)一處理，對所有標簽使用統(tǒng)一的定義，不論長標簽還是正常標簽都可以統(tǒng)一表征為一個詞集合lu={wu1,wu2,…,wum}，其中m表示該標簽當中所包含的詞數(shù)目，每個特征維標簽也同樣可以表征為一個詞集合ld={wd1,wd2,…,wdn}，其中n表示該特征維標簽中所包含的詞數(shù)目。設表征每個用戶的所有標簽數(shù)目為X，其中每個標簽出現(xiàn)的次數(shù)為x，則對于每個標簽來說，其初始特征值ful計算公式為

(1)

用戶標簽與特征維標簽之間的語義相似度用Sl(lu,ld)表示，其中l(wèi)u表示用戶標簽，ld表示特征維標簽，其計算公式為

(2)

式中：Sim(wui,wdj)代表包含m個詞的用戶標簽wui(i=1,2,3,…,m)與包含n個詞的特征維標簽wdj(j=1,2,3,…,n)之間的平均語義相似度，詞語相似度計算方法參考文獻[12]的基于知網的詞語相似度計算方法。通過依次計算某個用戶的所有標簽與待確定特征值的特征維標簽之間的語義相似度，選取出與該特征維標簽相似度最大的用戶標簽，將該標簽本身的特征值與該最大相似度相乘，計算結果作為該特征維的特征值，這樣就完成了特征維中一維的確定。重復上述工作，即可確定出特征維中每一維的特征值，從而完成用戶標簽到特征維標簽的特征映射，特征映射過程中每一特征維的特征值的公式為

(3)

式中：max{Sl((lu)a,ld)}表示一個用戶的X個用戶標簽分別與特征維ld計算相似度之后得到的相似度最大值，ful((lu)a)表示當(lu)a與ld計算取得相似度最大值時該用戶標簽本身的特征值，T(ld)表示特征維ld的特征值。通過以上計算，可以為每個用戶構建出表征用戶興趣的特征向量。為了驗證該模型的構建效果，使用模糊聚類方法對模型效果進行驗證。

2.3 基于模糊聚類的用戶興趣聚類

桃花島小地主家的女兒黃蓉，算是標準的江南小家碧玉。從小不能說是嘗遍人間美味吧，但糊弄叫花子洪七公和蒙古土鱉郭靖還是綽綽有余的。

2.3.1 數(shù)據(jù)標準化

由于不同的數(shù)據(jù)通常有不同的量綱，為了能夠比較不同量綱的量，本文采用標準差規(guī)格化方法對數(shù)據(jù)進行適當變換，其計算公式為

(4)

2.3.2 模糊相似矩陣

(5)

2.3.3 最佳聚類閾值

(6)

3 實驗與結果分析

3.1 實驗數(shù)據(jù)集

為了驗證本文提出的基于特征映射的微博用戶標簽興趣聚類方法的有效性，在實驗數(shù)據(jù)集的準備方面，利用新浪微博API在旅游、環(huán)保、科技、自然語言處理等15個領域隨機收集了3 000位用戶，為每位用戶獲取了其所關注的50位用戶。對于每個用戶，將用戶本人及其所關注用戶的用戶標簽構成標簽集合，去除掉其中帶有特殊符號和包含英文單詞的標簽，以備為每個用戶建立用戶興趣特征向量。將所有用戶的標簽集合組合成用戶標簽庫，以備統(tǒng)計詞頻確定特征空間。

3.2 不同聚類算法下的用戶興趣聚類結果對比實驗

為了驗證本文選取的模糊聚類算法在用戶興趣聚類任務上會有更好的效果，本實驗對模糊聚類和K-means算法的用戶興趣聚類結果進行了對比。首先，兩種不同算法在用戶特征向量的構建方面，都考慮標簽之間的語義相關性，引入特征映射構建用戶特征向量。其次，對于模糊聚類，將這些特征向量組成原始數(shù)據(jù)矩陣，利用模糊聚類算法得到用戶興趣聚類結果。對于K-means方法，依次選取2，4，6，8作為聚類數(shù)目，選取關注用戶數(shù)較多的K位用戶作為初始聚類中心，通過K-means算法得到聚類結果。選取平均聚類準確度p作為評價標準，其計算公式為

(7)

式中：n為聚類數(shù)，pi為各類的準確度，即類中具有相同興趣的最大用戶數(shù)與類中用戶總數(shù)之比，平均聚類準確度越高，代表聚類效果越好。模糊聚類算法和K-means算法的實驗結果對比如表1所示。

表1 不同聚類算法下用戶興趣聚類結果對比

根據(jù)模糊聚類的思想，不再將每個用戶的興趣以硬劃分的形式劃分到某個類別當中，使用模糊聚類實現(xiàn)用戶興趣聚類任務更能反映用戶興趣多類屬的模糊特性。從表1的實驗結果中不難看出，在同樣引入特征映射構建用戶特征向量的情況下，模糊聚類方法相比于K-means算法在用戶興趣聚類任務中的平均聚類準確度更優(yōu)。

3.3 用戶興趣聚類在是否引入特征映射條件下的對比實驗

為了驗證本文提出的特征映射思想對用戶興趣聚類效果的提升，該實驗分別采用兩種方式構造用戶的特征向量：(1)考慮用戶標簽之間的語義相關性，利用特征映射構建用戶特征向量；(2)不考慮標簽語義相關性而僅僅通過硬匹配構建用戶特征向量。分別將兩種方式下構造的用戶特征向量組成原始數(shù)據(jù)矩陣，并利用模糊聚類算法對用戶興趣進行聚類，評價標準也選用平均聚類準確度，實驗結果如圖1所示。通過分析圖1中實驗結果可以發(fā)現(xiàn)，考慮用戶標簽之間的語義相關性并引入特征映射的思想構建用戶特征向量，相比使用硬匹配構建用戶特征向量在用戶興趣聚類的平均聚類準確度上有了較大改善。實驗結果驗證了本文提出的基于特征映射的微博用戶標簽興趣聚類方法的有效性。

圖1 引入特征映射和不引入特征映射的平均聚類準確度對比實驗Fig．1 Comparison of average clustering accuracy between considering feature mapping and without considering feature mapping

3.4 基于模糊聚類方法的用戶興趣聚類在不同閾值下的聚類結果分析

由于3 000位用戶的聚類結果不便在本文中全部展示，因此本實驗選取其中15位用戶的聚類結果進行分析，這15位用戶的用戶興趣如表2所示。使用本文提出的基于特征映射的用戶標簽興趣聚類方法對以上15位用戶進行興趣聚類，在不同閾值下的聚類結果如圖2所示。

表2 用戶及用戶興趣

圖2 不同閾值下的用戶興趣聚類結果Fig．2 Clustering result of user interest with different threshold

通過觀察圖2所反映的不同閾值下的用戶興趣聚類結果，并結合表2中展示的15位用戶各自的用戶興趣，可以比較直觀地看到本文提出的用戶興趣聚類方法在用戶興趣聚類任務上取得了較好效果。比如當閾值取0.630 8時，興趣為自然語言處理的用戶1和興趣為機器學習的用戶4自動被聚為一類；再比如當閾值為0.518 2時，除了興趣為自然語言處理的用戶1和興趣為機器學習的用戶4聚為一類之外，興趣為數(shù)據(jù)挖掘的用戶12也被加入到該類當中，此外，興趣為旅游的用戶2、興趣為攝影的用戶3和興趣為美食的用戶5被自動聚為一類，興趣為電子商務的用戶14和興趣為互聯(lián)網的用戶15自動聚為一類。

4 結束語

本文針對微博用戶標簽之間存在一定的語義相關性問題提出了基于特征映射的微博用戶標簽興趣聚類方法。考慮用戶標簽的語義相關性并引入特征映射的思想能夠有效地提高用戶興趣聚類效果，同時驗證了本文選取的模糊聚類方法相比于K-means算法在用戶興趣聚類任務中更具優(yōu)越性。

[1] Huang He, Huang Hai, Wang Rujing. FCA-Based web user profile ming for topics of interest[C]∥ Proceedings of the 2007 IEEE International Conference on Integration Technology.Shenzhen, China:IEEE,2007:20-24.

[2] Pazzani M, Billsus D. Learning and revising user profiles: The identification of interesting web sites[J]. Machine Learning27, 1997,27(3):313-331.

[3] Tan Bin, Shen Xuehua, Zhai Chengxiang. Mining long-term search history to improve search accuracy[C]∥ Conference on Knowledge Discovery in Data. Philadelphia, PA,USA:[s.n.], 2006: 718-719.

[4] Shen X, Tan B, Zhai C. Context-sensitive information retrieval using implicit feedback[C]∥Proceedings of the 28th Annual International ACM SIGIR Conference. Salvador, Brazil:ACM, 2005: 41-45.

[5] Zhou Xiaoming, Conati C. Inferring user goals from personality and behavior in a causal model of user affect[C]∥ Proceedings of the 8th International Conference on Intelligent User Interfaces. Miami, Florida, USA:[s.n.], 2003: 211-214.

[6] Teevan J, Dumais S T, Horvitz E. Personalizing search via automated analysis of interests and activities[C]∥ Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Salvador, Brazil:ACM, 2005: 449-451.

[7] Shu Wengjian, Lim E P, Jiang Jing, et al.Twitterrank：Finding topic-sensitive influential twitterers[C]∥ Proceedings of the 3th ACM International Conference on Web Search and Data Mining．New York City, NY, USA:ACM, 2010: 261-270.

[8] Liu Z, Chen X, Sun M. Mining the interests of Chinese microbloggers via keyword extraction[J]. Frontiers of Computer Science in China, 2012, 1(6):76-87.

[9] Chen J, Nairn R, Nelson L, et al. Short and tweet: Experiments on recommending content from information streams[C]∥ Proceedings of the 28th International Conference on Human Factors in Computing Systems. New York, USA: ACM,2010:1185-1194.

[10]閻春霖，張延園．基于用戶標簽的社區(qū)發(fā)現(xiàn)方法研究[J]．科學技術與工程, 2011,11(6): 1237-1240.

Yan Chunlin, Zhang Yanyuan. Research of community dicovery algorithm based on user tags[J]. Science Technology and Engineering, 2011,11(6):1237-1240.

[11]康海瀟．基于標簽的微博用戶興趣發(fā)現(xiàn)算法研究及應用[D]．杭州：浙江大學，2013.

Kang Haixiao. Algorithm research of tag-based user interest discovery in Weibo and application[D]. Hangzhou:Zhejiang University, 2013.

[12]劉群，李素建．基于《知網》的詞匯語義相似度計算[J].中文計算語言學，2002，7(2): 59-76.

Liu Qun, Li Sujian. Word similarity computing based on How-net[J]. Computational Linguistics and Chinese Language Processing, 2002,7(2):59-76.

Micro-blog User Label Interest Clustering Method Based on Feature Mapping

Qin Yu1,2, Yu Zhengtao1,2, Wang Yanbin1,2, Shi Linbin1,2, Pan Huashan1,2

(1. Institute of Information Engineering and Automation, Kunming University of Science and Technology, Kunming, 650500, China; 2. Key Laboratory of Intelligent Information Processing, Kunming University of Science and Technology, Kunming, 650500, China)

Since many methods for cluster user interest does not consider the semantic similarity of the user labels, a micro-blog user label interest clustering method is introduced based on feature mapping. Firstly, the user labels of the target users and their focus users are obtained, then the labels with the higher frequency than the threshold value is chosen. Therefore, a feature space is created. Secondly, the user labels are mapped to the feature space by calculating the semantic similarity based on the feature mapping. Finally, the fuzzy clustering is utilized to obtain the clustering result of different threshold value. Experimental results show that the method greatly improves the clustering accuracy rate for user interest clustering.

micro-blog; feature mapping; fuzzy clustering; semantic similarity

國家自然科學基金(61175068)資助項目。

2014-06-05；

2014-06-30

TP391

A

秦雨(1989-)，男，碩士研究生，研究方向：信息檢索、數(shù)據(jù)挖掘，E-mail：iamno1_2009@163.com。

石林賓(1989-)，男，碩士研究生，研究方向：信息檢索和數(shù)據(jù)挖掘。

余正濤(1970-)，男，博士，教授，研究方向：自然語言處理、信息檢索和信息抽取。

潘華山(1989-)，男，碩士研究生，研究方向：自然語言處理和數(shù)據(jù)挖掘。

王炎冰(1988-)，男，碩士研究生，研究方向：社交網絡分析、信息檢索。