宋添樹 李江宇 張沁哲

（內(nèi)蒙古科技大學(xué) 信息工程學(xué)院,內(nèi)蒙古自治區(qū) 包頭 014010）

1 引言

微博是一種以140個字符為上限的新興的網(wǎng)絡(luò)社交平臺,根據(jù)應(yīng)用目的分為官方微博和個人微博兩種。其中官方微博主要發(fā)表與其所在單位相關(guān)的廣告、通告以及其領(lǐng)域內(nèi)事件等等,官方微博的內(nèi)容隨時間順序排列整齊、不容易混亂。近年來,隨著個人電腦、智能手機(jī)的普及,人們逐漸將社交眼光放在了微博平臺上。由于微博平臺的便利性和計算機(jī)網(wǎng)絡(luò)的發(fā)展,個人微博的數(shù)量和事件的復(fù)雜度逐年增加,如果用戶想了解一個人的專業(yè)領(lǐng)域、興趣愛好以及表達(dá)方式方法等內(nèi)容需要逐條瀏覽每條微博,不易查詢,費(fèi)時費(fèi)力,如果將相似事件的微博聚類在一起可以極大地解放勞動力,快速地對博主形成認(rèn)知,還可以為其他應(yīng)用軟件提供數(shù)據(jù)便利。當(dāng)前國內(nèi)外的聚類算法大都基于字?jǐn)?shù)較長的文檔類型,主要方法有詞共現(xiàn)法、詞頻-文檔頻率法等刻畫空間點(diǎn)的分布再根據(jù)各類聚類算法對距離的不同應(yīng)用進(jìn)行聚類,此類方法聚類精確度較低,只能應(yīng)用于粗放型的分類,對于個人微博字?jǐn)?shù)較少的特殊情況來看,矩陣和二維表中出現(xiàn)0的情況十分普遍,因此并不十分適用個人微博中語義復(fù)雜、事件多變的情況。

因此本文依上述問題提出了基于語義相似度的個人微博聚類算法,將語義相似度大的微博聚類在一起。首先將個人微博進(jìn)行分詞并去除停用詞；其次使用機(jī)器學(xué)習(xí)CBOW模型訓(xùn)練詞語向量；再次使用改進(jìn)的曼哈頓距離法計算相似度；最后使用clarans法進(jìn)行聚類。

例如馮小剛微博:

(1)“《芳華》是一封情書,寫給青春的,寫給軍隊(duì)的,寫給那些女兵的大熒幕作品。”

(2)“青春不老,佳音終傳,誰的等待都不愿辜負(fù)。12月15日,電影全國及北美地區(qū)同步上映?！?/p>

按照詞頻-文檔頻率以及詞共現(xiàn)法分析,這兩條微博并不相關(guān),但是在語義層面上來看這兩句話都與“電影”相關(guān),因此本文的研究目的就是將語義層面上相似度大的微博聚類在一起,使用戶可以分類查看自己感興趣的內(nèi)容。綜合考慮了個人微博特點(diǎn),采用python語言爬取個人微博；使用jieba分詞工具進(jìn)行精細(xì)分詞并去除停用詞；形成0、1組成的向量空間；使用CBOW模型訓(xùn)練詞語向量,縮短訓(xùn)練窗口,降低維度；根據(jù)較低維度的向量距離計算文本相似度；最后進(jìn)行聚類。

2 相關(guān)工作

文本聚類工作應(yīng)用十分廣泛,主要針對論文一類的文檔歸類；將混雜在一起不同領(lǐng)域的文章有效地分開,根據(jù)用戶設(shè)定的聚類粒度大小將文檔聚類。有相同屬性的文章聚類在一起,不同屬性的文檔則不屬于一類。

他人的相關(guān)研究對本文起了重要的作用。在中文語義相似度計算方面,趙世奇等人提出了LFIC(Linguistic Features Indexing Clustering)方法進(jìn)行文本聚類,提取了文本的主題,同時基于漢語語言學(xué)將語義層面的相似度考慮進(jìn)去[1]。劉群、李素建等人創(chuàng)建了How Net詞匯庫將詞語之間的關(guān)系用樹狀關(guān)系或網(wǎng)狀關(guān)系表示,根據(jù)從屬關(guān)系和并列關(guān)系計算詞語之間的相似度。這種體系對語義相似度的影響十分深遠(yuǎn)[2]。王小林等人根據(jù)How Net體系結(jié)構(gòu)運(yùn)算量較大的弊端改進(jìn)了語義相似度的計算公式,使相似度更加精確[3-4]。

在文檔聚類方面,Vesanto J等人提出了一種自組織映射數(shù)據(jù)挖掘（SOM）算法,該算法可以有效利用數(shù)據(jù)原型來可視化和探索數(shù)據(jù)的屬性,與傳統(tǒng)k-means算法相比有了明顯的提高[5]。Ding C H等人主要針對k-means聚類算法中高維災(zāi)難問題提出了優(yōu)化算法PCA（Principal Component Analysis）,通過降維降噪算法優(yōu)化聚類結(jié)構(gòu),實(shí)驗(yàn)數(shù)據(jù)使用DNA和互聯(lián)網(wǎng)新聞數(shù)據(jù)證明了PCA算法比傳統(tǒng)k-means算法有更快的聚類速度和準(zhǔn)確程度[6]。Elhamifar E等人針對現(xiàn)如今高維數(shù)據(jù)集合,如圖像、視頻、文本和網(wǎng)頁文檔,以及DNA微陣列數(shù)據(jù)等等,這些高維數(shù)據(jù)大多是多個低維數(shù)據(jù)的子集組成的集合,提出了一種稀疏子空間聚類的算法對位于低維子空間聯(lián)合中的數(shù)據(jù)點(diǎn)進(jìn)行聚類[7]。Vimalarani C等人和Zhang D等人采用支持向量機(jī)SVM無監(jiān)督學(xué)習(xí)結(jié)合一般聚類算法應(yīng)用于文本聚類運(yùn)算中,并取得了良好的效果[8-9]。

3 微博聚類

聚類過程主要分為五個部分:（1）預(yù)處理階段分詞并去除停用詞,漢語語言處理主要基于詞語來進(jìn)行,將微博語句分詞將很大程度上方便計算過程。本文采用python語言調(diào)用jieba分詞詞庫將微博句子分詞；（2）將分詞結(jié)束后的微博文本形成一個詞匯-文檔0,1分布的二維表格,將這個二維表格作為機(jī)器學(xué)習(xí)的輸入端；使用CBOW機(jī)器學(xué)習(xí)方法訓(xùn)練詞匯向量,縮短微博所代表的向量維度；（3）由詞匯向量可以算得微博語句向量；（4）句子向量代表了空間中的一個一個的點(diǎn),采用本文改進(jìn)的曼哈頓距離計算微博之間的相似程度；（5）根據(jù)所計算的相似程度最后采用clarans方法聚類。示意圖如圖1所示。

3.1 預(yù)處理

個人微博的聚類算法首先要獲取數(shù)據(jù)集合,本文主要基于用戶數(shù)量最多的新浪微博獲取個人微博數(shù)據(jù)。首先將個人微博數(shù)據(jù)集合按照時間順序排列形成最初的數(shù)據(jù)集合。最初的數(shù)據(jù)集合中含有無法處理的雜質(zhì)內(nèi)容,例如表情、圖片、視頻、音頻等。預(yù)處理的過程就是將這些無法通過正常自然語言處理進(jìn)行計算的部分去除,過濾掉微博中的雜質(zhì)之后形成個人微博集合T={t1,t2,...,tn}。此時個人微博集合中僅含有漢字部分。

將個人微博集合進(jìn)行分詞、去除停用詞處理,將處理之后的集合表示為Tr={tr1,tr2,...,trn}。

圖1 個人微博聚類示意圖

3.2 機(jī)器學(xué)習(xí)

CBOW模型（Continuous Bag-of-Words）是一種用于神經(jīng)網(wǎng)絡(luò)的語言模型。CBOW模型的訓(xùn)練輸入是某一個特征詞的上下文相關(guān)的詞對應(yīng)的詞向量,而輸出就是特定的一個詞的詞向量。其中,輸入詞向量為詞袋模型刻畫的詞向量,輸出為Softmax函數(shù)的浮點(diǎn)數(shù)降維的詞語向量。若給出訓(xùn)練詞序列w1,w2,...,wn,CBOW的訓(xùn)練目的是使每個詞語的平均對數(shù)概率最大化。

C(wn)為模型輸出詞語向量結(jié)果,N為訓(xùn)練詞語的個數(shù),k為訓(xùn)練窗口的大小。給出詞語wn從訓(xùn)練窗口-k到k之間計算正確預(yù)測詞語wn+j的對數(shù)概率。概率函數(shù)p通過Softmax函數(shù)刻畫。

使用CBOW模型,給出大量語料庫訓(xùn)練詞語向量,獲得個人微博語句中每一個詞的詞語向量的值。本文實(shí)驗(yàn)綜合考慮計算機(jī)性能以及算法優(yōu)化這兩方面內(nèi)容給定訓(xùn)練窗口為50維度。

3.3 個人微博句子向量

通過3.2節(jié)中利用CBOW模型訓(xùn)練得出詞語向量。每一個詞語都有一個特定的向量表示,每個個人微博語句都有一個或多個詞語組成,下面的過程就是將詞語向量合理地表示為句子向量。

詞語向量的本質(zhì)是預(yù)測這個詞語上下文出現(xiàn)其他詞語的可能性,因此將句子向量看作是詞語向量的平均值能夠有效地表達(dá)出這種關(guān)系。

圖2 句子向量

其中vec(sentence)是句子向量,vec(wsi)是一個句子中的詞語向量。

每個個人微博語句向量表示完成之后,每個向量可以視作一個n維空間中的一個點(diǎn)。因此多個個人微博相當(dāng)于在同一個n維空間中點(diǎn)的集合。將這些點(diǎn)合理地劃分粒度大小以及根據(jù)粒度大小合理地聚類。

3.4 聚類

獲得個人微博所代表的點(diǎn)之后進(jìn)行個人微博之間相似度計算,句子之間的相似度歸結(jié)為兩個點(diǎn)之間的距離大小,普通的距離算法例如歐幾里得距離會產(chǎn)生大量的浮點(diǎn)數(shù)運(yùn)算,在空間維度較高的條件之下會消耗大量的時間,因此優(yōu)化距離算法是個人微博這類短文本聚類的首要工作。

曼哈頓距離（Manhattan distance）又稱為出租車距離,描述的是兩個點(diǎn)之間橫縱坐標(biāo)之間距離而并非兩個點(diǎn)之間直線距離。利用曼哈頓距離計算兩點(diǎn)距離可以節(jié)省大量的計算機(jī)浮點(diǎn)運(yùn)算。

其中Dis(p1,p2)為兩個個人微博所代表的點(diǎn)之間的曼哈頓距離。D1至Dn為n維向量空間,1到n維之間距離之差求和就是兩個點(diǎn)之間的具體距離,即個人微博之間的相似度。

得出兩個微博相似度之后采用clarans算法對個人微博進(jìn)行聚類工作。

clarans（A Clustering Algorithm based on Randomized Search,基于隨機(jī)選擇的聚類算法）,中心思想是隨機(jī)選擇一定數(shù)量的聚類中心,然后不停地移動聚類中心使得每個簇的成員到聚類中心的距離最小。每次計算兩個點(diǎn)的距離時,使用公式（4）計算。

算法1 clarans聚類

輸入:聚類中心的個數(shù)n,每個中心最大半徑maxneighbor

輸出:聚類結(jié)果

1 獲得聚類中心{vec1,...,vecn}

2 for n←1 to n

3Do←n

4 直到每個簇的成員到聚類中心距離最小時停止循環(huán)

5 do for n←1 to n

6 do ωk←{}設(shè)置第n個簇為空集

7 for n←1 to N

8 計算空間點(diǎn)到中心距離

9 if(veci

10 歸于此類

11 返回結(jié)果

4 實(shí)驗(yàn)

新浪微博是近幾年來新興的即時網(wǎng)絡(luò)分享平臺,其用戶數(shù)量龐大、內(nèi)容復(fù)雜多樣為本文提供了良好的數(shù)據(jù)來源。因此使用新浪微博作為測試數(shù)據(jù)很具有代表性。

本文采用python語言編寫爬取程序,再根據(jù)微博爬取結(jié)果進(jìn)行聚類。

實(shí)驗(yàn)節(jié)選自吳京,于謙,樊振東,李開復(fù)4人總計5000條左右的微博作為實(shí)驗(yàn)數(shù)據(jù)。本文采用對比實(shí)驗(yàn)來分析研究結(jié)果,分別采用BIRCH算法、DBSCAN算法進(jìn)行對照。

實(shí)驗(yàn)使用F值度量,F值為準(zhǔn)確率與召回率的調(diào)和平均值。

圖3 對比實(shí)驗(yàn)

如圖3所示,本文方法相比BIRCH聚類算法以及DBSCAN聚類算法有較為明顯的提高,其中樊振東的個人微博信息按時間順序排列較為整齊,因此三種聚類算法區(qū)別不明顯。因此本文方法在個人微博時間線較為混亂時更加有效。

5 結(jié)束語

本文采用CBOW模型訓(xùn)練個人微博文本取得詞語向量,句子由詞語組成,將詞語向量計算獲得個人微博句子向量。個人微博向量可以視作空間中的一個點(diǎn)。根據(jù)曼哈頓距離計算個人微博相似度以此簡化算法,計算完相似度之后,根據(jù)clarans聚類算法將個人微博聚類。實(shí)驗(yàn)結(jié)果表明,本文方法比傳統(tǒng)聚類算法BIRCH聚類算法以及DBSCAN聚類算法有較為明顯的提高。

研究工作的數(shù)據(jù)來源相對較少,聚類結(jié)果準(zhǔn)確度依然有待提高；聚類數(shù)據(jù)量大時,會造成時間消耗量大的問題。因此找到精度以及時間消耗平衡是下一步研究的工作。

[1]趙世奇,劉挺,李生.一種基于主題的文本聚類方法[J].中文信息學(xué)報,2007,21(2):58-62.

[2]劉群,李素建.基于《知網(wǎng)》的詞匯語義相似度計算[C].第三屆漢語詞匯語義學(xué)研討會.臺北,2002:59-79.

[3]王小林,王義.改進(jìn)的基于知網(wǎng)的詞語相似度算法[J].計算機(jī)應(yīng)用,2011,31(11):3075-3077.

[4]王小林,王東,楊思春,等.基于《知網(wǎng)》的詞語語義相似度算法[J].計算機(jī)工程,2014,40(12):177-181.

[5]Vesanto J,Alhoniemi E.Clustering of the self-orga-nizing map[J].IEEE Transactions on Neural Networks,2000,11(3):586-600.

[6]Ding C H,He X.K-means clustering via principal component analysis[C].International conference on machine learning,2004.

[7]Elhamifar E,Vidal R .Sparse Subspace Clustering:Algorithm,Theory,and Applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(11):2765-2781.

[8]Vimalarani C,Subramanian R ,Sivanandam S N,et al.An Enhanced PSO-Based Clustering Energy Optimization Algorithm for Wireless Sensor Network[J].The Scientific World Journal,2016.

[9]Zhang D,Chen S.Clustering Incomplete Data Using Kernel-Based Fuzzy C-means Algorithm[J].Neural Process-ing Letters,2003,18(3):155-162.