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

吳錫坤 劉洋

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

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

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

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

1 非平衡文本聚類的研究方法

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

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

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

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

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

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

2 文本表示

2.1 文本表示模型

文本作為信息的載體，將原始文本信息表示成計算機形式信息的過程稱為文本表示的過程。

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

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

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

IF權(quán)值反應(yīng)的是特征值在原文本中的重要程度，出現(xiàn)頻數(shù)越多說明比重越大，反之越小。IDF反映的是特征值承載的信息度，如果一個特征值只出現(xiàn)在一個或少量幾個文本中很可能說明該特征值能更好地代表該文本，因為特征值的相異程度越高往往代表的意義更鮮明，此時根據(jù)公式IDF值相應(yīng)的更大，突出文本特征性。TF-IDF是基于統(tǒng)計的權(quán)重計算方式，所以采集樣本數(shù)量越多則最終結(jié)果越精確。

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

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

3 K-Means聚類分析

K-Means聚類算法是數(shù)據(jù)挖掘領(lǐng)域中常用的基于劃分的聚類算法?；趧澐值木垲愃惴ǖ幕驹瓌t是：（1）假定數(shù)據(jù)集中的每個元素都只屬于某一個類別；（2）每個類別中都至少包含一個元素。K-Means算法是典型的基于劃分的聚類算法。算法思想如下。

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

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

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

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

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

4 實驗分析

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

經(jīng)過實驗分析可以看到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]周昭濤.文本聚類分析效果評價及文本表示研究[D].中國科學(xué)院技術(shù)研究所，2005.