基于K-means的私人微博聚類算法改進(jìn)

高永兵，郭文彥，周環(huán)宇，聶知秘

（內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭014010）

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

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

1.1 私人微博文本特性分析

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

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

1.2 相關(guān)工作

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

1.2.1文本表示和特征選擇

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

表1 偽文檔整理對(duì)比表

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

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

1.2.2相似度計(jì)算

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

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

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

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

1.3 K-means聚類算法思想

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

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

輸出條件：滿足方差最小標(biāo)準(zhǔn)的k個(gè)聚類。

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

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

2 改進(jìn)的K-means聚類算法

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

2.1 聚類初始化

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

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

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

2.2 初始類別的選取和中心點(diǎn)的確定

2.2.1 K值和中心點(diǎn)的形成過(guò)程

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

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

2.2.2 相似度的計(jì)算

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

2.2.3 閾值P的選定

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

2.3 采用K-means算法進(jìn)行迭代

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

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

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

2.5 改進(jìn)后的K-means算法流程圖

改進(jìn)后的K-means算法流程如圖1所示。

圖1 算法流程圖

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

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

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

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

圖2 部分實(shí)驗(yàn)結(jié)果圖

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

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

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

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

表2 聚類簇?cái)?shù)目

表3 對(duì)照實(shí)驗(yàn)比較

表4 平均正確率比較

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

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

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

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

[3]蔣盛益，麥智凱，龐觀松，等.微博信息挖掘技術(shù)研究綜述[J].圖書情報(bào)工作，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 nodules[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é)報(bào)(工學(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 Probability，1967(1)：281-297.

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

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

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