摘  要： 針對私人微博內(nèi)容進行聚類研究，結(jié)合私人微博的內(nèi)容和結(jié)構(gòu)特點提出了基于K-means的改進聚類算法。通過添加引用和評論內(nèi)容豐富了文本內(nèi)容，降低了短文本矩陣向量嚴重稀疏性帶來的聚類算法準確性降低的影響；通過甄別“微話題”內(nèi)容和改進相似度的計算，找到初始化類別并進行初步計算得到合適的類別數(shù)目和初始中心點，解決了K-means算法中聚類數(shù)目K需人工指定和初始中心點選取隨機性的問題。實驗結(jié)果表明，改進后的算法不僅可以自適應(yīng)地得到K值，較普通的K-means算法在聚類的準確率上有所提高。

　　關(guān)鍵詞： K-means算法；私人微博；初始中心點；自適應(yīng)

　　作為Web2.0時代新興起的一類開放式互聯(lián)網(wǎng)應(yīng)用，微博是一種非正式的迷你型博客。據(jù)CNNIC（中國互聯(lián)網(wǎng)信息中心）發(fā)布的數(shù)據(jù)顯示，截至2013年6月底，我國的微博用戶已達3.31億，網(wǎng)民的微博用戶比例達到了56.0%，用戶每日發(fā)布的博文數(shù)多達1億條。與傳統(tǒng)社會媒體相比，微博的發(fā)展態(tài)勢強勁，已成為人們生活中不可或缺的一部分[1]。針對微博的研究是目前的一大熱點，微博不完全同于已有的短文本，它具有簡短、實時性及社會性等特征。目前國內(nèi)大量關(guān)于微博的研究都著眼于公共微博，如從公共微博中挖掘熱點事件發(fā)現(xiàn)[2]、意見領(lǐng)袖識別、網(wǎng)絡(luò)內(nèi)容檢測、網(wǎng)絡(luò)輿情檢測等[3]。本文針對私人微博，通過改進文本信息處理中使用到的聚類方法，對私人微博的內(nèi)容進行整理和挖掘。對本人微博來說，可以對自己的微博歷史內(nèi)容整理歸類，使得歷史數(shù)據(jù)清晰可用；對他人而言，可以更清楚快速地了解他人微博的整體內(nèi)容，挑選出自己感興趣的信息；同時，也為公共微博的研究提供了支持,可以進一步應(yīng)用于內(nèi)容特征、用戶興趣分析和新興話題檢測等。這些功能對于數(shù)據(jù)量龐大的微博應(yīng)用是很有實際意義的。聚類是一種無指導(dǎo)的機器學(xué)習(xí)方法，在數(shù)據(jù)挖掘領(lǐng)域中非常活躍，應(yīng)用非常廣泛。它基于“物以類聚”的原理，按照相似性把個體歸為若干類別，使得同一類別差異盡可能小，不同類別差異盡可能大。其中K-means算法是目前應(yīng)用最廣泛的基于劃分的聚類方法。本文的主要工作就是對常用的K-means算法進行改進，使之適應(yīng)于私人微博文本。

　　1 私人微博文本特性分析及相關(guān)工作

　　1.1 私人微博文本特性分析

　　微博是一種半結(jié)構(gòu)化的數(shù)據(jù)，不同于其他形式的短文本，微博文本本身就隱含了大量有價值的信息。例如采用新浪微博開放平臺API，除了能夠獲取一條微博文本內(nèi)容之外，同時還可以得到21條相關(guān)的其他信息。通過對大量個人微博縱向觀察，總結(jié)出私人微博的鮮明特性：(1)文本長度短小，限定在140字內(nèi)，信息量較少；(2)微博文本具有較強的時效性，內(nèi)容與時間聯(lián)系緊密；(3)一個人對某事件的態(tài)度和觀點基本是一貫而連續(xù)的，但是興趣點的轉(zhuǎn)移卻是很快的，這使得文本聚類分析變得復(fù)雜；(4)微博數(shù)據(jù)分布不平衡，符合相關(guān)研究人員提出的文本“長尾現(xiàn)象”；(5)微博結(jié)構(gòu)中含有一些對內(nèi)容非常重要的補充和提示，例如微博文本內(nèi)容中兩個“#”之間代表的是“微話題”，表示當(dāng)前討論的主題；微博文本內(nèi)容中“@”符號后面的稱謂表示了當(dāng)前對話的微博賬號；某條微博與其轉(zhuǎn)發(fā)或者評論的微博內(nèi)容上有著緊密的聯(lián)系；微博轉(zhuǎn)發(fā)量、評論量、點贊量這些量化了的數(shù)字提示了微博內(nèi)容的流行程度及重要程度。

　　在文本挖掘領(lǐng)域中，與傳統(tǒng)文本相比，短文本具有信息量小的缺點，這使得在數(shù)學(xué)化表示文本內(nèi)容時，短文本會產(chǎn)生矩陣向量嚴重稀疏的問題。但是，微博與其他傳統(tǒng)媒體的短文本相比隱含了大量有用的信息，為進行聚類研究提供了可以利用的條件，使得更有利于進行處理。正是在微博內(nèi)容和結(jié)構(gòu)上的特點的基礎(chǔ)上，本文提出了基于K-means的改進聚類算法。

　　1.2 相關(guān)工作

　　通常進行文本聚類算法之前，需要經(jīng)過幾個典型步驟：文本表示、特征選擇、相似度計算等。文本聚類需要建立文本模型，將文本轉(zhuǎn)化成數(shù)據(jù)格式。文本模型反映了數(shù)據(jù)的關(guān)系，并在此基礎(chǔ)上采用文本相似度的計算方法，最后采用聚類算法形成聚簇。

　　1.2.1 文本表示和特征選擇

　　本文在文本表示上采用了典型的向量空間模型VSM(Vector Space Model)[4]，并結(jié)合私人微博特點，采取形成偽文檔的方法。微博內(nèi)容往往與所評論和引用的微博緊密相關(guān)，所以把評論內(nèi)容和引用內(nèi)容歸并到正文內(nèi)容中，形成偽文檔，這樣部分解決了矩陣向量嚴重稀疏性的問題。如對某用戶新浪微博2013年2月14日～2013年6月7日內(nèi)共492條微博內(nèi)容進行整理，如表1所示。

　　可以看到，微博內(nèi)容增加了一倍多，字數(shù)特別少影響到語義的文本數(shù)目大大減少。

　　然后進行分詞預(yù)處理，本文采用中科院的漢語詞法分析系統(tǒng)ICTCLAS(Institute of Computing Technology，Chinese Lexical Analysis System)進行分詞。特征選擇上采用應(yīng)用最為廣泛的TFIDF(Term FreqencyInverse Document Frequ-

　　ency)方法[5]。

　　1.2.2 相似度計算

　　在相似度計算上采用的是改進的歐式距離[6]。設(shè)兩個微博文本轉(zhuǎn)化為兩個p緯向量xi=(xi1，xi2，…，xip)和xj=(xj1，xj2，…，xjp)，則它們的歐式距離為：

　　鑒于微博內(nèi)容與時間的相關(guān)性，對式(1)進行改進，添加了時間上的考量。時間相似度的計算公式如下：

　　simtime(xi，xj)=e-|ti-tj|(2)

　　其中，ti和tj分別表示編號為xi和xj的微博發(fā)布時間，該公式的計算結(jié)果在0和1之間。改進后的歐式距離既考慮了語義相似度又考慮到了時間相似度，如下：

　　simCom(xi，xj)=×d(xi，xj)+×simtime(xi，xj)(3)

　　其中，?琢和?茁為相似度的可調(diào)節(jié)參數(shù)，simCom(xi，xj)為文本向量的綜合相似度。

　　1.3 K-means聚類算法思想

　　聚類算法基于著名的假設(shè)：同一類別相似性大，不同類別相似性小。K-means算法屬于聚類方法中一種典型的劃分方法[7-8]。它的基本思想是初始隨機給定K個簇中心，按照最鄰近原則把待分類樣本點分到各個簇，然后按平均法重新計算各個簇的質(zhì)心，從而確定新的簇心。一直迭代，直到簇心的移動距離小于某個給定的值。K-means算法的具體過程如下：

　　輸入條件：聚類簇的個數(shù)k，以及包含n個數(shù)據(jù)對象的樣本集。

　　輸出條件：滿足方差最小標準的k個聚類。

　　(1)選取k個對象作為初始聚類中心；(2)根據(jù)聚類中心的值，將每個對象（重新）賦給最相似的簇；(3)重新計算每個簇匯中對象的平均值，用此平均值作為新的聚類中心；(4)重復(fù)執(zhí)行步驟(2)、(3)，直到評價函數(shù)收斂或聚類的中心不再發(fā)生變化為止。

　　K-means具有算法流程簡單、復(fù)雜度低易于實現(xiàn)、效率高易于并行等優(yōu)點，但是也存在著一些缺陷：(1)需要指定聚類數(shù)目K，K的指定往往需要大量的經(jīng)驗并且使得算法準確性不穩(wěn)定；(2)初始的K個中心點的選取是隨機的，但是中心點的選擇對算法的準確性有較大影響，往往希望中心點具有一定的代表性，即具有較高的密度。

　　2 改進的K-means聚類算法

　　許多研究都證明，不像傳統(tǒng)的普通文檔（如新聞文章和學(xué)術(shù)論文），直接對微博內(nèi)容進行聚類效果不好；也不像一些其他的短文本，微博本身就隱含了許多可以加以利用的信息。在此基礎(chǔ)上，針對私人微博使用了經(jīng)過改進的K-means聚類算法。主要目的在于解決微博文本信息量小導(dǎo)致向量矩陣稀疏和K的取值需要人工指定及K個中心隨機指定的問題。

　　2.1 聚類初始化

　　偽文檔經(jīng)過分詞和預(yù)處理形成了語料庫M。鑒于之前所述的私人微博特性，在文檔M中，首先選取出文本內(nèi)容含"#"符號的文本，且"#"話題一致的直接歸為一類，不相同的另成一類。這樣充分利用了微博文本內(nèi)容特點，同一個微話題下討論的必然是相同主題的內(nèi)容，不需要機器識別。選取完成后，假設(shè)從中共挑出了m1，m2，…，mn個類別，每個類別中含有c1，c2，…，cn條文本。

　　此時，文檔分成了兩類，一類是已挑出并進行歸類的文檔（設(shè)為集合u1），另一類是待處理的文檔(設(shè)為集合u2)。在u1中指定中心點為每個類別m中流行度最高的微博文本,其流行度由下式確定：

　　pop=cRe+cCo+cAg(4)

　　其中，pop表示流行度，cRe表示轉(zhuǎn)發(fā)數(shù)，cCo表示評論數(shù)，cAg表示點贊的個數(shù)，這些參數(shù)都可以直接獲得。通過流行度能夠近似獲得文本的重要程度，進一步獲得文本密度較大的中心點。在某一聚類簇中只含一個數(shù)據(jù)的特殊情況下，它的中心點就是數(shù)據(jù)向量本身。

　　2.2 初始類別的選取和中心點的確定

　　2.2.1 K值和中心點的形成過程

　　u1和u2初始化完成后，通過相似度計算求得u2中每個向量與u1中所有中心點的距離。其中u2到u1中各個類中心點的所有距離中最近距離設(shè)為dmin。當(dāng)dmin大于某一閾值P時，u1中添加一個新類，把此條數(shù)據(jù)向量歸入該新類中，再重新計算u2中每個向量與u1中所有中心點的距離；當(dāng)dmin小于該閾值P時，把此條數(shù)據(jù)向量歸到u1中離中心最近的那個類，重新計算u1的中心點，此時的中心點計算采取求向量數(shù)值平均值的計算方法。u2中所有數(shù)據(jù)都添加到u1時(即u1=M時)停止。初步分類完成。

　　至此，得到聚類簇個數(shù)K的值，也得到每個類別的中心點。

　　2.2.2 相似度的計算

　　相似度的計算采用了改進后的歐式距離公式，該公式添加了時間相似度進行考量。微博內(nèi)容的相似度與時間上的間隔有一定關(guān)系，把微博在時間上越相近、內(nèi)容上相似的概率越大的因素也考慮進去。

　　2.2.3 閾值P的選定

　　閾值P的選取除了可以使用固定經(jīng)驗值外，也可以采用更為靈活的自適應(yīng)選取的方法。計算u2中每個向量與u1中所有中心點的距離，選取其平均值為P。雖然增加了計算量，但是使得算法更穩(wěn)定。實驗證明，通過該方法選取的P值對結(jié)果的影響是較準確的。

　　2.3 采用K-means算法進行迭代

　　根據(jù)聚類中心的值，將每個對象（重新）賦給最相似的簇；重新計算每個聚類簇中所有對象的平均值，用此平均值作為新的聚類中心；比較每個數(shù)據(jù)向量離它最近的聚類中心是否就是其所屬的聚類的中心；迭代，直到評價函數(shù)收斂或聚類的中心不再發(fā)生變化為止。最終得出聚類結(jié)果。

　　2.4 聚類結(jié)果的整理

　　私人微博上有許多信息都是屬于個人的信息，如個人的想法、遇到的事情、心情等。這些信息一般都是孤立出現(xiàn)，缺乏聚類的意義。有關(guān)研究人員提出了短文本的“長尾現(xiàn)象”[9]。根據(jù)“長尾現(xiàn)象”的理論，最后得出的類別數(shù)目有很大部分會是小的類別，把這些小類別視作孤立點，將不太具有聚類效果和意義的進行舍棄。實驗得出當(dāng)某類文檔個數(shù)只含有1或2個文檔時進行舍棄效果較好。

　　2.5 改進后的K-means算法流程圖

　　改進后的K-means算法流程如圖1所示。

　　3 實驗及結(jié)果分析

　　運行環(huán)境為Windows 7操作系統(tǒng)，3.20 GHz CPU，8.0 GB內(nèi)存，編程工具是Microsoft Visual Studio 2012。數(shù)據(jù)通過新浪開放平臺API獲取，從名人影響力榜上隨機抽取了50位認證用戶的微博進行實驗，其中每位用戶的微博數(shù)量不少于100條，時間跨度不小于一個月。以下采用某名人用戶新浪微博2013年2月14日～2013年3月11日內(nèi)共100條微博內(nèi)容做舉例進行說明，分詞采用中科院的漢語詞法分析系統(tǒng)（ICTCLAS）。

　　鑒于微博內(nèi)容聚類結(jié)果評價標準難度較大，本文對聚類質(zhì)量的評價標準參考了一種常用的基于人工標注的評價指標F-measure[10]的思想并進行了簡化，主要以人工判別為主，對聚類產(chǎn)生的結(jié)果直接進行人工判別。當(dāng)結(jié)果簇中超過半數(shù)的文檔可以被看做一類時，認為該聚類是正確的。通過結(jié)果簇的正確率的比較，衡量算法的準確性。

　　實驗過程中，首先使用改進的算法進行實驗(其中相似度計算時，α和β都取為0.5)，然后再使用傳統(tǒng)的K-means算法進行對照實驗。傳統(tǒng)K-means算法的K值根據(jù)改進算法的聚類簇個數(shù)給出。部分實驗結(jié)果如圖2所示。

　　統(tǒng)計算法執(zhí)行過程中的聚類個數(shù)，結(jié)果如表2所示。

　　由表2可知，對應(yīng)于傳統(tǒng)聚類算法的聚類簇數(shù)目K值為17。采用傳統(tǒng)K-means算法再次處理，進行對比實驗，實驗結(jié)果如表3所示。

　　統(tǒng)計所有50人的微博文本聚類實驗的正確率，結(jié)果如表4所示。

　　由實驗結(jié)果可知，改進后的算法克服了K-means算法K和中心點需要指定的缺點，充分利用了微博內(nèi)容和結(jié)構(gòu)上的特點，且準確率較原算法也有提高，基本實現(xiàn)了設(shè)想的目標。

　　國內(nèi)關(guān)于微博的研究主要都著眼于公共微博，本文從私人微博入手，以用戶為單位對微博內(nèi)容進行處理挖掘。由于微博文本不同于其他形式的短文本，其本身就隱含了大量有價值的信息，這些微博文本結(jié)構(gòu)上和內(nèi)容上的特點為研究提供了思路。針對私人微博的特殊性和傳統(tǒng)K-means聚類算法的不足，本文提出了一種聚類簇數(shù)目和初始中心點自適應(yīng)生成的改進算法，有效克服了傳統(tǒng)算法準確性不穩(wěn)定的缺陷。其應(yīng)用在私人微博的聚類過程中，具有一定的使用價值。

　　由于只對文本內(nèi)容進行了研究，而微博現(xiàn)在使用了大量的富媒體技術(shù)，下一步的工作需要針對如何結(jié)合富媒體對微博內(nèi)容整體有一個更全面的研究。

　　參考文獻

　　[1] 王連喜，蔣盛益，龐觀松，等．微博用戶關(guān)系挖掘研究綜述[J]．情報雜志，2012，31(12)：91－97．

　　[2] 童薇，陳威，孟小峰.EDM：高效的微博事件檢測算法[J].計算機科學(xué)與探索，2012，6(12)：1076-1086.

　　[3] 蔣盛益，麥智凱，龐觀松，等．微博信息挖掘技術(shù)研究綜述[J]．圖書情報工作，2012，56(17)：136－142．

　　[4] BUGIS S P，YOUNG J E M，ARCHIBALD S D，et al.Diagnostic accuracy of fine-needle aspiration biopsy versus frozen section in solitary thyroid nod-ules[J].The American Journal of Surgery，1986，152(4)：411-416.

　　[5] AIZAWA A.An information-theoretic perspective of tf-idf measures[J].Information Processing & Management，2003，39(1)：45-65.

　　[6] 張忠林，曹志字，李元韜.基于加權(quán)歐式距離的K-means算法研究[J].鄭州大學(xué)學(xué)報(工學(xué)版)，2010，31(1)：89-92.

　　[7] MACQUEEN J.Some methods for classification and analysis of multivariate observations[C].Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Proba-bility，1967(1)：281-297.

　　[8] 萬小軍，楊建武，陳曉鷗.文檔聚類中K-means算法的一種改進算法[J].計算機工程，2003，29(2)：102-157.

　　[9] 彭澤映，俞曉明，許洪波，等.大規(guī)模短文本的不完全聚類[J].中文信息學(xué)報，2011，25(1)：54-59.

　　[10] LARSEN B，AONE C.Fast and effective text mining usinglinear-time document clustering[C].Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，1999：16-22.