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

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

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

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

　　1.1 私人微博文本特性分析

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

　　在文本挖掘領(lǐng)域中,，與傳統(tǒng)文本相比，短文本具有信息量小的缺點(diǎn),，這使得在數(shù)學(xué)化表示文本內(nèi)容時(shí),，短文本會產(chǎn)生矩陣向量嚴(yá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)過幾個(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)容往往與所評論和引用的微博緊密相關(guān),，所以把評論內(nèi)容和引用內(nèi)容歸并到正文內(nèi)容中,，形成偽文檔，這樣部分解決了矩陣向量嚴(yán)重稀疏性的問題。如對某用戶新浪微博2013年2月14日～2013年6月7日內(nèi)共492條微博內(nèi)容進(jìn)行整理,，如表1所示,。

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

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

　　ency)方法[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)性，對式(1)進(jìn)行改進(jìn),，添加了時(shí)間上的考量,。時(shí)間相似度的計(jì)算公式如下：

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

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

　　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]。它的基本思想是初始隨機(jī)給定K個(gè)簇中心,，按照最鄰近原則把待分類樣本點(diǎn)分到各個(gè)簇,，然后按平均法重新計(jì)算各個(gè)簇的質(zhì)心，從而確定新的簇心。一直迭代,，直到簇心的移動(dòng)距離小于某個(gè)給定的值,。K-means算法的具體過程如下：

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

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

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

　　K-means具有算法流程簡單,、復(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)的選擇對算法的準(zhǔn)確性有較大影響,，往往希望中心點(diǎn)具有一定的代表性，即具有較高的密度,。

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

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

　　2.1 聚類初始化

　　偽文檔經(jīng)過分詞和預(yù)處理形成了語料庫M,。鑒于之前所述的私人微博特性,，在文檔M中，首先選取出文本內(nèi)容含"#"符號的文本,，且"#"話題一致的直接歸為一類,，不相同的另成一類。這樣充分利用了微博文本內(nèi)容特點(diǎn),，同一個(gè)微話題下討論的必然是相同主題的內(nèi)容,，不需要機(jī)器識別,。選取完成后，假設(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表示評論數(shù),，cAg表示點(diǎn)贊的個(gè)數(shù),，這些參數(shù)都可以直接獲得。通過流行度能夠近似獲得文本的重要程度,，進(jìn)一步獲得文本密度較大的中心點(diǎn),。在某一聚類簇中只含一個(gè)數(shù)據(jù)的特殊情況下，它的中心點(diǎn)就是數(shù)據(jù)向量本身,。

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

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

　　u1和u2初始化完成后,，通過相似度計(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)證明,，通過該方法選取的P值對結(jié)果的影響是較準(zhǔn)確的。

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

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

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

　　私人微博上有許多信息都是屬于個(gè)人的信息，如個(gè)人的想法,、遇到的事情,、心情等。這些信息一般都是孤立出現(xiàn),，缺乏聚類的意義,。有關(guān)研究人員提出了短文本的“長尾現(xiàn)象”[9]。根據(jù)“長尾現(xiàn)象”的理論,，最后得出的類別數(shù)目有很大部分會是小的類別,，把這些小類別視作孤立點(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所示。

　　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ù)通過新浪開放平臺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)行說明,，分詞采用中科院的漢語詞法分析系統(tǒng)（ICTCLAS）。

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

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

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

　　由表2可知,，對應(yīng)于傳統(tǒng)聚類算法的聚類簇?cái)?shù)目K值為17。采用傳統(tǒng)K-means算法再次處理,，進(jìn)行對比實(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),。

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

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

　　參考文獻(xiàn)

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

　　[2] 童薇，陳威,，孟小峰.EDM：高效的微博事件檢測算法[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 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é)報(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 Proba-bility,，1967(1)：281-297.

　　[8] 萬小軍，楊建武,，陳曉鷗.文檔聚類中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 usinglinear-time document clustering[C].Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM,，1999：16-22.