宋添樹 李江宇 張沁哲

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

1 引言

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

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

例如馮小剛微博:

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

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

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

2 相關(guān)工作

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

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

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

3 微博聚類

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

3.1 預處理

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

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

圖1 個人微博聚類示意圖

3.2 機器學習

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

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

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

3.3 個人微博句子向量

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

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

圖2 句子向量

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

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

3.4 聚類

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

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

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

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

clarans（A Clustering Algorithm based on Randomized Search,基于隨機選擇的聚類算法）,中心思想是隨機選擇一定數(shù)量的聚類中心,然后不停地移動聚類中心使得每個簇的成員到聚類中心的距離最小。每次計算兩個點的距離時,使用公式（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←{}設置第n個簇為空集

7 for n←1 to N

8 計算空間點到中心距離

9 if(veci

10 歸于此類

11 返回結(jié)果

4 實驗

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

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

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

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

圖3 對比實驗

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

5 結(jié)束語

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

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

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

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

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

[4]王小林,王東,楊思春,等.基于《知網(wǎng)》的詞語語義相似度算法[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.