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

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，昆明,650500； 2.昆明理工大學(xué)智能信息處理重點(diǎn)實(shí)驗(yàn)室,昆明,650500)

?

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

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

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，昆明,650500； 2.昆明理工大學(xué)智能信息處理重點(diǎn)實(shí)驗(yàn)室,昆明,650500)

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

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

引 言

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

1 基本思想

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

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

2 基于特征映射的微博用戶標(biāo)簽興趣聚類過(guò)程

2.1 特征選取

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

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

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

(1)

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

(2)

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

(3)

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

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

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

2.3.1 數(shù)據(jù)標(biāo)準(zhǔn)化

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

(4)

2.3.2 模糊相似矩陣

(5)

2.3.3 最佳聚類閾值

(6)

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 不同聚類算法下的用戶興趣聚類結(jié)果對(duì)比實(shí)驗(yàn)

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

(7)

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

表1 不同聚類算法下用戶興趣聚類結(jié)果對(duì)比

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

3.3 用戶興趣聚類在是否引入特征映射條件下的對(duì)比實(shí)驗(yàn)

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

圖1 引入特征映射和不引入特征映射的平均聚類準(zhǔn)確度對(duì)比實(shí)驗(yàn)Fig．1 Comparison of average clustering accuracy between considering feature mapping and without considering feature mapping

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

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

表2 用戶及用戶興趣

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

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

4 結(jié)束語(yǔ)

本文針對(duì)微博用戶標(biāo)簽之間存在一定的語(yǔ)義相關(guān)性問(wèn)題提出了基于特征映射的微博用戶標(biāo)簽興趣聚類方法?？紤]用戶標(biāo)簽的語(yǔ)義相關(guān)性并引入特征映射的思想能夠有效地提高用戶興趣聚類效果，同時(shí)驗(yàn)證了本文選取的模糊聚類方法相比于K-means算法在用戶興趣聚類任務(wù)中更具優(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]閻春霖，張延園．基于用戶標(biāo)簽的社區(qū)發(fā)現(xiàn)方法研究[J]．科學(xué)技術(shù)與工程, 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]康海瀟．基于標(biāo)簽的微博用戶興趣發(fā)現(xiàn)算法研究及應(yīng)用[D]．杭州：浙江大學(xué)，2013.

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

[12]劉群，李素建．基于《知網(wǎng)》的詞匯語(yǔ)義相似度計(jì)算[J].中文計(jì)算語(yǔ)言學(xué)，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

國(guó)家自然科學(xué)基金(61175068)資助項(xiàng)目。

2014-06-05；

2014-06-30

TP391

A

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

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

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

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

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