基于特征空間的文本聚類

黃建宇，周愛武，肖 云，譚天誠

(安徽大學 計算機科學與技術學院，安徽 合肥 230601)

基于特征空間的文本聚類

黃建宇，周愛武，肖 云，譚天誠

(安徽大學 計算機科學與技術學院，安徽 合肥 230601)

文本聚類是聚類算法的一種具體應用，隨著互聯網的發展，文本聚類應用越來越廣泛，譬如在信息檢索、智能搜索引擎等方面都有較為廣泛的應用。文本聚類算法主要涉及文本預處理和文本聚類算法，故對文本聚類進行改進可以從這兩方面入手。傳統文本聚類的文本預處理采用VSM模型，該模型不考慮詞與詞的語義相似度和詞與詞的相關性，導致文本聚類精確度非常低。針對該問題，提出了基于特征空間文本聚類的方法。該方法根據文檔集合的特征空間構造一個替代詞庫，并根據這個替代詞庫得到文檔的主題，依據主題配合其對應的領域詞典對文檔詞進行相應的替換。傳統的文本聚類使用K-means算法，但該算法需要人工指定K值。為此，提出了基于K值優化的K-means改進算法。實驗結果表明，所提出的文本聚類方法和K-means改進算法顯著提高了文本聚類的智能性和精確性。

知網；領域詞典；主題；義原；聚類；K值優化

0 引 言

文本聚類是聚類算法的一種具體應用。隨著互聯網的發展，文本聚類應用越來越廣泛，如在信息檢索、智能搜索引擎等方面都有廣泛的應用。文本聚類是一種沒有監督的機器學習方法，不需要訓練過程，也不需要預先對文檔手工標注類別，而是按照一定的相似度對大量文本進行歸類。與結構化的數據挖掘對象不同，文本聚類處理的是自然語言類文本，傳統的文本聚類算法首先將文本進行分詞處理，接著刪去代詞、停用詞和嘆詞等不影響文本類別的詞，然后再計算每個詞的TF-IDF值(其中TF表示特征詞在某文本中的出現頻率，IDF表示特征詞在整個文本集中的出現頻率)，根據TF-IDF值選取每篇文檔的特征詞。但是這種方法沒有考慮詞與詞的相關性(詞與詞反映同一個主題)，很有可能將相關的兩個詞當成無關詞，若是不考慮詞之間的相關性，則可能將兩篇相關度較高的文本看作互相沒有關聯的文本。

針對上述問題,提出了基于特征空間的文本聚類方法。該方法考慮了詞之間的相關性，提出了替代詞庫的概念，對要進行聚類的文檔構造替代詞庫，替代詞庫中的每一行是由相關度很大的一組詞構成的。通過替代詞庫得到文檔集合大致主題，并選取對應的領域詞典，根據領域詞典，將經過文本預處理后的文檔進行相應詞的替換[1-5]。

1 相關介紹

1.1知識背景

(1)向量空間模型(VSM)。

VSM(Vector Space Model)是當前自然語言處理中常用的模型，該模型是對文檔表示常用的方法。

在VSM中，每一篇文本在特征空間中都表示為一個向量，文本中的一個詞條對應向量中的一個參數，由這樣的d個參數構成一個特征向量，而每一個特征向量等于該向量的d個參數所對應的特征在文本集中的權值。數學描述如下：

特征詞集合X=(x1,x2,…)，文本集合D=(d1,d2,…)，特征詞權重集合W=(w1,w2,…),則文本di=(wi1,wi2,…)[6]。

(2)領域詞典。

所用的領域詞典是由東北大學自然語言處理開發的，用來存儲于指定領域有關的領域關聯詞的詞典，一行由兩個字段組成，分別是漢字對應的專業術語和拼音對應的專業術語[7-8],以軍事為例(阿哥斯波塔米戰役a'ge'si'bo'ta'mi'zhan'yi)。

(3)HowNet。

HowNet是一個較為詳細的語義知識詞典，但是HowNet通過一種多維的方式表示一個詞的語義，這在計算詞與詞之間的相似度時造成了一定的困難。在HowNet中，詞的語義是由多個義原組成的，因此計算詞的語義相似性是相當麻煩的[3,7,9]。

1.2相關原理

(1)語義相似性。

義原是最基本的、不易于再分割意義的最小單位。每個詞的詞義都是由多個不同的義原組成的，必須綜合每個詞的義原集合來考慮詞與詞之間的語義相似性，而不是單純地看某幾個常用義原，被所謂的經驗誤導。并且，每個詞的義原集中第一義原所占的比重較大，需要加以考慮。

(2)詞匯的相關度。

對于兩個詞f1和f2,f1有n個義原：s11,s12,…,s1n,f2有m個義原:s21,s22,…,s2m。現規定w1與w2是取各個義原相似度的最大值:

(1)

該式僅從義原方面考慮詞匯的相似性，不考慮第一義原的重要位置[7,10]。

(3)構建替代詞庫。

由于每一個詞的詞義都是由義原集合組成的，對于任意兩個詞，若只從語義方面考慮，它們的語義相似度有可能非常低，但是它們又可能實際上是關于同一主題的。所以文中要從詞的語義和相關性兩個方面進行考慮。假定給定一組詞的具體步驟：

首先，取得這組詞中每個詞的義原集合，再從第一個詞開始循環遍歷每個詞及其義原集。假定一組詞及其義原集為：fi(y1,y2,y3),fj(y3),fk(y3,y6),fm(y3,y10),fn(y1)。若兩個詞不相同,則把它們義原的交集提取出來，并將這兩個詞分別放在它們共有的義原后面，得到y1[fi,fn],y3[fi,fk,fm]。具體描述如下:

輸入：M個詞及每個詞對應的義原集；

輸出：N行相關詞集合。

①從1到M：獲取對應的詞以及它的義原集。

②從2到M：獲取對應的詞以及它的義原集。

③比較這兩個義原集是否有交集，若是交集不為空，則先判斷有沒有已建立的相關詞，若是交集為空，則建立一組相關詞。相關詞的第一項由它們共有的義原組成，接著在它的后面加上相應的兩個詞。若是相關詞已經存在，則轉下一步。

④判斷已經存在的相關詞中的共有的義原和步驟③中兩個詞的共有義原是否相同，若相同，則直接把兩個詞添加在已有相關詞的后面，若不同，則依照步驟③新建一組相關詞。

通過上述步驟就可以得到一個初步的替代詞庫。

然后，循環遍歷步驟創建的替代詞庫，計算每組相關詞的第一個項的語義相似度。設定閾值α=0.5,如果計算的語義相似度大于0.5，就將這兩組相關詞進行合并，否則不合并，從而得到替代詞庫。

(4)選擇領域詞典。

刪除構建的替代詞庫中的一些與主題無關的相關詞組(例如表示屬性的一些詞)，然后循環遍歷替代詞庫，計算每組相關詞的數目。依據聚類簇數K，選擇數目排在前面的K組相關詞，這K組相關詞就是文檔集合的主題，根據K組相關詞選擇與其對應的K組領域詞典。

(5)K-means算法中的K值優化。

K-means算法在聚類前必須要知道它需要聚類成幾個簇，但是對于陌生的數據集并不知道K值的大小，所以在完成聚類操作前需人為指定K值，因此該方法相對不智能。于是提出了一種改進的思路對K值進行優化，其優化流程如下:

②對數據集進行聚類，得到聚類結果。

③根據步驟②得到的簇集合，求得每個簇均值到其他簇均值的距離和，選擇其中距離和最小的簇，記為M。

④求得與簇M距離較近的一個簇N，依據聚類的評價標準高內聚低耦合的原則，研究這兩簇，設定Discc為簇自身到自身簇均值的距離，Discd為一個簇的數據到另一個簇均值的距離。

(2)

(3)

其中，cx為自身簇的均值；dx為另一個簇的均值。

計算Discc/Discd的值，如果該值越接近于0，說明效果越好，也越能體現聚類高內聚、低耦合的標準。按照這種思路分別計算選定兩個簇的比值，選擇其中最大的比值作為結果[11-16]。

2 聚類算法的改進

針對傳統文本聚類算法的不足，進行如下改進：

輸入:M篇文本文檔，設定聚類簇數N。

輸出:N個集合。

算法描述：

(1)對文檔進行分詞和去停用詞的處理；

(2)使用TF-IDF方法計算文檔中所有詞的TF-IDF值，然后根據對應的值篩選出文檔的特征詞；

(3)通過由特征詞構成的特征向量來構建這些文檔的特征空間；

(4)構建一個替代詞庫(使用1.2的方法)；

(5)選擇領域詞典(使用1.2的方法)；

(6)對分詞、除停用詞后的詞進行遍歷，看其是否在領域詞典中，如果在就用對應的領域詞典第一項進行替換；

(7)將替換后的詞文檔進行數值化；

(8)使用上面K值優化，確定K值；

(9)對數據進行聚類處理。

3 實驗分析

為了檢測和驗證算法的性能，實驗中使用一般的文本聚類語料庫，此語料庫中包含軍事、經濟、藝術、醫藥、政治、體育六個類別。

領域詞典采用的是東北大學自然語言處理開發的領域詞典。使用Java編寫文本預處理的部分，使用Matlab編寫文本聚類的部分。在Intel Core i5,2.6 GHz，4 GB內存的計算機上，以MyEclipse8.0 Matlab R2012(a)為運行環境。實驗在語料庫中通過隨機選取的方式獲取部分文本，總共進行了五次實驗，實驗效果如圖1所示。

圖1 精確度對比圖

由圖1可知，改進算法相比傳統算法在精確度上提升明顯，但是由于受到分詞工具和HowNet出現的一些未登陸詞的影響，導致聚類的精確度并不是很完美。

4 結束語

文中提出了一種基于特征空間文本聚類的方法。依據文檔集合的特征空間中的特征詞義原集合構建一個替代詞庫,根據這個替代詞庫得到大致文檔主題，再由這些主題配合相應的領域詞典使得聚類精確度得到了很大提升；同時對K-means算法進行改進，使K值不再依靠人為指定，而是根據文中算法進行計算，選出最佳值，提高了文本聚類算法的可靠性和精確性。但是由于分詞工具和HowNet出現的未登錄詞導致精確度不是特別完美，需要進一步進行研究。

[1] 林 利.基于本體的文本聚類的應用研究[D].天津：天津大學，2012.

[2] 龐觀松,蔣盛益.文本自動分類技術研究綜述[J].情報理論與實踐,2012,35(2):123-128.

[3] 曾淑琴,吳揚揚.基于HowNet的詞語相關度計算模型[J].微型機與應用,2012,31(8):77-80.

[4] 諶志群,張國煊.文本挖掘研究進展[J].模式識別與人工智能,2005,18(1)：65-74.

[5] 路永和,李焰鋒.改進TE-IDF算法的文本特征項權值計算方法[J].圖書情報工作,2013,57(3):90-95.

[6] 吳國進.基于支持向量機的文本分類研究[D].合肥:安徽大學,2011.

[7] 劉 群,李素建.基于知網的詞匯語義相似度的計算[C]//第三屆漢語詞匯語義學研討會.出版地不詳:出版者不詳,2002:59-76.

[8] Zhu Jingbo,Yao Tianshun.FIFA-based text classification[J].

Journal of Chinese Information Processing,2002,16(3):20-26.

[9] Budanitsky A，Hirst G．Evaluating word-net-based measures of lexical semantic relatedness[J].Computational Linguistics,2006,2(1):13-47.

[10] Dai L,Liu B,Xia Y,et al.Measuring semantic similarity between words using HowNet[C]//International conference on computer science and information technology.[s.l.]:IEEE,2008:601-605.

[11] 孫吉貴,劉 杰,趙連宇.聚類算法研究[J].軟件學報，2008，19(1)：48-61.

[12] 鐘 勇,趙向輝.一種優化初始中心點的k-means文本聚類算法[J].鄭州大學學報：理學版,2009,41(2):29-32.

[13] 田 萱,杜小勇，李海華．語義查詢擴展中詞語-概念相關度的計算[J].軟件學報，2008，19(8):2043-2053.

[14] 汪 中,劉貴全,陳恩紅.一種優化初始中心點的K-means算法[J].模式識別與人工智能,2009,22(2):299-304.

[15] 周昭濤.文本聚類分析效果評價及文本表示研究[D].北京:中國科學院計算技術研究所,2005.

[16] Hartigan J A,Wong M A.Algorithm AS 136:a k-means clustering algorithm[J].Journal of the Royal Statistical Society Series C (Applied Statistics),1979,28(1):100-108.

Text Clustering Based on Feature Space

HUANG Jian-yu，ZHOU Ai-wu，XIAO Yun，TAN Tian-cheng

(College of Computer Science and Technology,Anhui University,Hefei 230601,China)

Text clustering is a specific application of the clustering algorithm.With the development of Internet,the text clustering has gotten an increasingly wide utilization in many fields,such as information retrieval and intelligent search engine.Text clustering algorithm involves text preprocessing and text clustering primarily,so some improvements on text clustering from these two aspects have been conducted.The traditional text clustering adopts the VSM without considering the semantic similarity and correlation between words,which leads to low accuracy.In view of it,the text clustering method based on feature space is proposed which constructs an alternative word library through the feature space of document collection and gets the document theme according to the alternative word library,and then replaces the words in document based on the themes and its corresponding domain dictionary.However the traditional text clustering algorithm must need artificialKvalue.Therefore,K-means algorithm is presented based on theKvalue optimization.The experimental results show that the two improvements above mentioned have made text clustering more intelligent and more precise.

HowNet;domain dictionary;theme;sememes;clustering;optimizedKvalue

2016-05-07

：2016-08-12 < class="emphasis_bold">網絡出版時間

時間：2017-07-05

安徽大學大學生科研訓練計劃項目(J18520148)

黃建宇(1993-),男,研究方向為大數據與數據挖掘；周愛武,副教授,碩士生導師,研究方向為數據挖掘、數據庫與Web技術。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1649.004.html

TP301.6

:A

:1673-629X(2017)09-0075-03

10.3969/j.issn.1673-629X.2017.09.016