基于社交網(wǎng)絡(luò)中非平衡文本聚類(lèi)方法的研究

吳錫坤 劉洋

摘 要：社交網(wǎng)絡(luò)中的文本種類(lèi)數(shù)量存在極大的差異，不同領(lǐng)域的話(huà)題分布極不平衡，而在社交網(wǎng)絡(luò)文本數(shù)據(jù)中進(jìn)行文本聚類(lèi)對(duì)經(jīng)濟(jì)生活具有重要意義。該文針對(duì)文本聚類(lèi)展開(kāi)研究，結(jié)合非平衡文本的特點(diǎn)、文本特征的提取、聚類(lèi)常用的算法進(jìn)行實(shí)驗(yàn)。

關(guān)鍵詞：社交網(wǎng)絡(luò) 非平衡文本 聚類(lèi)方法

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2016）05（a）-0090-02

隨著信息技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)已經(jīng)廣泛深入現(xiàn)代社會(huì)的工作和生活之中，據(jù)第36次《中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示，截至2015年6月，我國(guó)網(wǎng)民規(guī)模達(dá)6.68億，互聯(lián)網(wǎng)普及率為48.8%；社交網(wǎng)絡(luò)作為互聯(lián)網(wǎng)中最活躍的角色之一每天產(chǎn)生數(shù)以?xún)|計(jì)的數(shù)據(jù)，主要是文本數(shù)據(jù)。社交網(wǎng)絡(luò)中的話(huà)題有的可能在短時(shí)間里積攢成千萬(wàn)甚至億級(jí)別的熱度，而同時(shí)同一類(lèi)別的某個(gè)話(huà)題可能只有不到10萬(wàn)的熱度，針對(duì)社交網(wǎng)絡(luò)中話(huà)題體現(xiàn)出的非平衡性進(jìn)行聚類(lèi)研究具有很重要的意義，有助于提供更接近真實(shí)的匯總信息，更便捷地使用網(wǎng)絡(luò)資源。

1 非平衡文本聚類(lèi)的研究方法

文本聚類(lèi)是自然語(yǔ)言處理的一個(gè)重要領(lǐng)域，聚類(lèi)分析原來(lái)是統(tǒng)計(jì)學(xué)機(jī)器學(xué)習(xí)領(lǐng)域研究的課題，近幾年隨著數(shù)據(jù)挖掘的興起，將文本挖掘引入數(shù)據(jù)挖掘的概念中。文本分析主要分為聚類(lèi)和分類(lèi)兩種分析方法。文本聚類(lèi)是根據(jù)文本數(shù)據(jù)的不同特征，按照事物間的相似性，將其劃分為不同數(shù)據(jù)類(lèi)的過(guò)程。聚類(lèi)和分類(lèi)是人類(lèi)認(rèn)識(shí)自然的基本方法，人類(lèi)經(jīng)過(guò)生活經(jīng)驗(yàn)和社會(huì)活動(dòng)形成對(duì)大千世界的認(rèn)識(shí)觀，比方說(shuō)我們將很自然地將天空中的鳥(niǎo)分為鴿子、燕子、老鷹等，這是對(duì)生活經(jīng)驗(yàn)的總結(jié)是典型的分類(lèi)行為。至于為什么將一種鳥(niǎo)稱(chēng)為鴿子、燕子或者老鷹，是從它們的體型、顏色、喙長(zhǎng)、食物鏈等級(jí)等特征總結(jié)出來(lái)的，這個(gè)總結(jié)特征的過(guò)程就屬于聚類(lèi)分析過(guò)程中的特征值提取的研究?jī)?nèi)容，根據(jù)這些鳥(niǎo)特征的不同劃分為不同的種類(lèi)便是一個(gè)聚類(lèi)過(guò)程。

文本聚類(lèi)的基本流程是經(jīng)典的三步走流程：文本表示、聚類(lèi)算法、聚類(lèi)結(jié)果分析。文本表示過(guò)程報(bào)過(guò)文本特征提取、機(jī)器語(yǔ)言表示，經(jīng)過(guò)文本表示過(guò)程將試驗(yàn)樣本表示成計(jì)算機(jī)可以識(shí)別的數(shù)據(jù)，作為聚類(lèi)算法的輸入數(shù)據(jù)。聚類(lèi)算法是聚類(lèi)分析的主體工作部分，經(jīng)過(guò)聚類(lèi)算法處理將起初離散的文本數(shù)據(jù)聚沙成塔，形成各個(gè)文本簇，或者叫作類(lèi)的集合；聚類(lèi)結(jié)果分析是對(duì)聚類(lèi)結(jié)果進(jìn)行綜合評(píng)價(jià)，評(píng)價(jià)的規(guī)則主要有兩個(gè)：（1）簇（類(lèi)）內(nèi)元素差距越小、簇（類(lèi)）與簇（類(lèi)）之間差距越大越好；（2）聚類(lèi)結(jié)果與人工判斷的結(jié)果差距越小越好。

非平衡文本的本質(zhì)是在一個(gè)文本數(shù)據(jù)集中一種或多種領(lǐng)域的文本數(shù)據(jù)在數(shù)量上的不平衡，例如在社交網(wǎng)絡(luò)中獲取20 000個(gè)話(huà)題作為實(shí)驗(yàn)樣本，其中包含16 000個(gè)屬于娛樂(lè)領(lǐng)域，2 000個(gè)屬于科技領(lǐng)域，1 000個(gè)屬于經(jīng)濟(jì)領(lǐng)域，1 000個(gè)屬于文學(xué)領(lǐng)域。對(duì)此數(shù)據(jù)集進(jìn)行聚類(lèi)分析，由于樣本數(shù)量的不平衡，在聚類(lèi)分析中提取的文本特征值數(shù)量也不確定。文本特征值數(shù)量的不平衡直接影響到聚類(lèi)分析結(jié)果的精確度。因此，基于非平衡文本的聚類(lèi)方法的研究力圖更準(zhǔn)確地對(duì)社交網(wǎng)絡(luò)中的文本數(shù)據(jù)進(jìn)行聚類(lèi)研究。實(shí)際上，在社交網(wǎng)絡(luò)中話(huà)題的分布十分不均衡，同一時(shí)間內(nèi)話(huà)題熱度從十萬(wàn)到千萬(wàn)甚至到數(shù)十億，因此將該時(shí)間段中的話(huà)題進(jìn)行聚類(lèi)遠(yuǎn)比例子中提出的問(wèn)題復(fù)雜得多。除此之外，話(huà)題在產(chǎn)生和傳播過(guò)程中的特定時(shí)間段各個(gè)話(huà)題的數(shù)量同樣是動(dòng)態(tài)的、不平衡的，因此基于非平衡文本聚類(lèi)的算法要具備的特征有以下幾方面。

（1）動(dòng)態(tài)性，可以容納新出現(xiàn)的文本數(shù)據(jù)而不會(huì)劇烈影響聚類(lèi)的結(jié)果。

（2）穩(wěn)定性，對(duì)文本的描述錯(cuò)誤不會(huì)帶來(lái)嚴(yán)重的影響。

（3）時(shí)間無(wú)關(guān)性，文本輸入的順序與最后的聚類(lèi)結(jié)果無(wú)關(guān)。

2 文本表示

2.1 文本表示模型

文本作為信息的載體，將原始文本信息表示成計(jì)算機(jī)形式信息的過(guò)程稱(chēng)為文本表示的過(guò)程。

現(xiàn)有的文本表示模型有布爾模型、向量空間模型、概率模型、n-Gram模型。根據(jù)話(huà)題文本的特征，我們選擇向量空間模型。向量控件模型是有G.Salton等人于20世紀(jì)60年代末提出，并成功應(yīng)用于SMART系統(tǒng)，是目前最為成熟和應(yīng)用最為廣泛的文本表示模型之一。向量空間模型以及相關(guān)的技術(shù)，包括特征項(xiàng)的選擇、加權(quán)策略，以及采用相關(guān)反饋進(jìn)行查詢(xún)優(yōu)化等技術(shù)，在文本分類(lèi)、自動(dòng)索引、特征檢索等許多領(lǐng)域得到了廣泛應(yīng)用。

向量空間模型的基本思想是：前提假設(shè)文本所表達(dá)內(nèi)容的特征和構(gòu)成文本的某些特征項(xiàng)的出現(xiàn)頻率有關(guān)，與這些特征項(xiàng)的順序或位置無(wú)關(guān)。也就是說(shuō)可以通過(guò)選取文本的特征值，計(jì)算特征值在文本中的出現(xiàn)頻數(shù)和在整個(gè)文檔集合中出現(xiàn)的頻數(shù)來(lái)表示文本承載的內(nèi)容。

特征項(xiàng)是文本中含有的具有領(lǐng)域特征性的基本單位（字、詞、詞組或短語(yǔ)），文本特征值的提取是文本聚類(lèi)的重要環(huán)節(jié)，主要方法根據(jù)方式主要分為基于統(tǒng)計(jì)和基于語(yǔ)義兩類(lèi)，經(jīng)典的基于統(tǒng)計(jì)的方式是特征項(xiàng)權(quán)重計(jì)算公式：

IF權(quán)值反應(yīng)的是特征值在原文本中的重要程度，出現(xiàn)頻數(shù)越多說(shuō)明比重越大，反之越小。IDF反映的是特征值承載的信息度，如果一個(gè)特征值只出現(xiàn)在一個(gè)或少量幾個(gè)文本中很可能說(shuō)明該特征值能更好地代表該文本，因?yàn)樘卣髦档南喈惓潭仍礁咄淼囊饬x更鮮明，此時(shí)根據(jù)公式IDF值相應(yīng)的更大，突出文本特征性。TF-IDF是基于統(tǒng)計(jì)的權(quán)重計(jì)算方式，所以采集樣本數(shù)量越多則最終結(jié)果越精確。

2.2 非平衡文本樣本的平衡化

非平衡文本數(shù)據(jù)集由于樣本數(shù)量的差距，根據(jù)文本特征的提取規(guī)則，在文本特征提取過(guò)程中同一個(gè)特征值在文檔中出現(xiàn)的頻數(shù)會(huì)差異很大。即IF值增益效果會(huì)比IDF值的削弱效果大得多。根據(jù)數(shù)據(jù)集數(shù)量的不同有研究者改進(jìn)了TF-IDF方法稱(chēng)之為ITC方法。ITF方法綜合文本長(zhǎng)短和文本數(shù)量的差距將特征值權(quán)重進(jìn)行同一化，特征值的權(quán)值取值范圍規(guī)定在[0，1]之間。公式表示如下：

3 K-Means聚類(lèi)分析

K-Means聚類(lèi)算法是數(shù)據(jù)挖掘領(lǐng)域中常用的基于劃分的聚類(lèi)算法。基于劃分的聚類(lèi)算法的基本原則是：（1）假定數(shù)據(jù)集中的每個(gè)元素都只屬于某一個(gè)類(lèi)別；（2）每個(gè)類(lèi)別中都至少包含一個(gè)元素。K-Means算法是典型的基于劃分的聚類(lèi)算法。算法思想如下。

（1）選取K的值（k的值的選取是關(guān)鍵）。

（2）隨機(jī)在數(shù)據(jù)集中選取類(lèi)簇的初始中心

（4）再一次統(tǒng)計(jì)K的值，類(lèi)簇中全部數(shù)據(jù)對(duì)象的算數(shù)平均值即為K。

（5）判斷是否結(jié)束，否者繼續(xù)（3）（4）步驟。

根據(jù)算法思想可以看出K-Means算法是基于貪心算法，可以保證局部最優(yōu)（每個(gè)點(diǎn)都?xì)w并在相似度最高的中心處），但并不是局部最優(yōu)，這是因?yàn)橹行狞c(diǎn)選取時(shí)造成的誤差是后面算法無(wú)法改變的。K–Means算法的優(yōu)點(diǎn)很明顯：（1）不受范圍影響；（2）受順序影響較小；（3）凸型聚類(lèi)效果好。

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

此次實(shí)驗(yàn)對(duì)1000個(gè)原始文本進(jìn)行聚類(lèi)，其中600個(gè)來(lái)自科技領(lǐng)域，200個(gè)來(lái)自?shī)蕵?lè)領(lǐng)域，100個(gè)來(lái)自體育領(lǐng)域，100個(gè)來(lái)自經(jīng)濟(jì)領(lǐng)域。實(shí)驗(yàn)環(huán)境采用OSX Yosemite10.10.5、i7CPU2.2 GHz、Memory16GB頻率1 600 MHz，編程語(yǔ)言為Python，使用傳統(tǒng)TF-IDF和改進(jìn)后的ITF建立的向量進(jìn)行K-Means聚類(lèi)算法分析結(jié)果對(duì)比（見(jiàn)表1）。

經(jīng)過(guò)實(shí)驗(yàn)分析可以看到ITF可以較好地提高小文本集的權(quán)重進(jìn)而提高準(zhǔn)確率。

參考文獻(xiàn)

[1]He Haibo，Garcia E A.Learning from imbalanced Data[J].IEEE Transactions on Knowledge and Data Enginering，2009， 21（9）：1263-1284.

[2]Kawai Y，F(xiàn)ujita Y，Kumamoto T.Using a Sentiment Map for Visualizing Credibility of News Sites on the Web[C]//Proceedings of WICOW 2008.California：ACM，2008：53-58.

[3]何金鳳.基于中文信息檢索的文本預(yù)處理[D].電子科技大學(xué)，2008.

[4]Ming Zhao，Jianli Wang，Guanjun Fan.Research on Application of Improved Text Cluster Algorithm in intelligent QA system[C]//Genetin and Evolutionary Computing，2008.WGEC 08.Second International Conference on 2008 IEEE，2008：463-466.

[5]Z.Huang.Extensions to the k-means algorithm for clustering large date sets with categorical values[J].Data Mining and Knowledge Discovery，1998（2）：283-304.

[6]周昭濤.文本聚類(lèi)分析效果評(píng)價(jià)及文本表示研究[D].中國(guó)科學(xué)院技術(shù)研究所，2005.