基于社交網絡中非平衡文本聚類方法的研究

吳錫坤 劉洋

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

關鍵詞：社交網絡 非平衡文本 聚類方法

中圖分類號：TP393 文獻標識碼：A 文章編號：1674-098X（2016）05（a）-0090-02

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

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

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

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

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

（1）動態性，可以容納新出現的文本數據而不會劇烈影響聚類的結果。

（2）穩定性，對文本的描述錯誤不會帶來嚴重的影響。

（3）時間無關性，文本輸入的順序與最后的聚類結果無關。

2 文本表示

2.1 文本表示模型

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

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

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

特征項是文本中含有的具有領域特征性的基本單位（字、詞、詞組或短語），文本特征值的提取是文本聚類的重要環節，主要方法根據方式主要分為基于統計和基于語義兩類，經典的基于統計的方式是特征項權重計算公式：

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

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

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

3 K-Means聚類分析

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

（1）選取K的值（k的值的選取是關鍵）。

（2）隨機在數據集中選取類簇的初始中心

（4）再一次統計K的值，類簇中全部數據對象的算數平均值即為K。

（5）判斷是否結束，否者繼續（3）（4）步驟。

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

4 實驗分析

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

經過實驗分析可以看到ITF可以較好地提高小文本集的權重進而提高準確率。

參考文獻

[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，Fujita 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]何金鳳.基于中文信息檢索的文本預處理[D].電子科技大學，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].中國科學院技術研究所，2005.