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

(安徽大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601)

基于特征空間的文本聚類

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

(安徽大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601)

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

知網(wǎng)；領(lǐng)域詞典；主題；義原；聚類；K值優(yōu)化

0 引 言

文本聚類是聚類算法的一種具體應(yīng)用。隨著互聯(lián)網(wǎng)的發(fā)展，文本聚類應(yīng)用越來越廣泛，如在信息檢索、智能搜索引擎等方面都有廣泛的應(yīng)用。文本聚類是一種沒有監(jiān)督的機(jī)器學(xué)習(xí)方法，不需要訓(xùn)練過程，也不需要預(yù)先對文檔手工標(biāo)注類別，而是按照一定的相似度對大量文本進(jìn)行歸類。與結(jié)構(gòu)化的數(shù)據(jù)挖掘?qū)ο蟛煌谋揪垲愄幚淼氖亲匀徽Z言類文本，傳統(tǒng)的文本聚類算法首先將文本進(jìn)行分詞處理，接著刪去代詞、停用詞和嘆詞等不影響文本類別的詞，然后再計算每個詞的TF-IDF值(其中TF表示特征詞在某文本中的出現(xiàn)頻率，IDF表示特征詞在整個文本集中的出現(xiàn)頻率)，根據(jù)TF-IDF值選取每篇文檔的特征詞。但是這種方法沒有考慮詞與詞的相關(guān)性(詞與詞反映同一個主題)，很有可能將相關(guān)的兩個詞當(dāng)成無關(guān)詞，若是不考慮詞之間的相關(guān)性，則可能將兩篇相關(guān)度較高的文本看作互相沒有關(guān)聯(lián)的文本。

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

1 相關(guān)介紹

1.1知識背景

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

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

在VSM中，每一篇文本在特征空間中都表示為一個向量，文本中的一個詞條對應(yīng)向量中的一個參數(shù)，由這樣的d個參數(shù)構(gòu)成一個特征向量，而每一個特征向量等于該向量的d個參數(shù)所對應(yīng)的特征在文本集中的權(quán)值。數(shù)學(xué)描述如下：

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

(2)領(lǐng)域詞典。

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

(3)HowNet。

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

1.2相關(guān)原理

(1)語義相似性。

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

(2)詞匯的相關(guān)度。

對于兩個詞f1和f2,f1有n個義原：s11,s12,…,s1n,f2有m個義原:s21,s22,…,s2m?，F(xiàn)規(guī)定w1與w2是取各個義原相似度的最大值:

(1)

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

(3)構(gòu)建替代詞庫。

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

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

輸入：M個詞及每個詞對應(yīng)的義原集；

輸出：N行相關(guān)詞集合。

①從1到M：獲取對應(yīng)的詞以及它的義原集。

②從2到M：獲取對應(yīng)的詞以及它的義原集。

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

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

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

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

(4)選擇領(lǐng)域詞典。

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

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

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

②對數(shù)據(jù)集進(jìn)行聚類，得到聚類結(jié)果。

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

④求得與簇M距離較近的一個簇N，依據(jù)聚類的評價標(biāo)準(zhǔn)高內(nèi)聚低耦合的原則，研究這兩簇，設(shè)定Discc為簇自身到自身簇均值的距離，Discd為一個簇的數(shù)據(jù)到另一個簇均值的距離。

(2)

(3)

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

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

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

針對傳統(tǒng)文本聚類算法的不足，進(jìn)行如下改進(jìn)：

輸入:M篇文本文檔，設(shè)定聚類簇數(shù)N。

輸出:N個集合。

算法描述：

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

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

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

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

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

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

(7)將替換后的詞文檔進(jìn)行數(shù)值化；

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

(9)對數(shù)據(jù)進(jìn)行聚類處理。

3 實驗分析

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

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

圖1 精確度對比圖

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

4 結(jié)束語

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

[1] 林 利.基于本體的文本聚類的應(yīng)用研究[D].天津：天津大學(xué)，2012.

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

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

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

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

[6] 吳國進(jìn).基于支持向量機(jī)的文本分類研究[D].合肥:安徽大學(xué),2011.

[7] 劉 群,李素建.基于知網(wǎng)的詞匯語義相似度的計算[C]//第三屆漢語詞匯語義學(xué)研討會.出版地不詳:出版者不詳,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].軟件學(xué)報，2008，19(1)：48-61.

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

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

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

[15] 周昭濤.文本聚類分析效果評價及文本表示研究[D].北京:中國科學(xué)院計算技術(shù)研究所,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">網(wǎng)絡(luò)出版時間

時間：2017-07-05

安徽大學(xué)大學(xué)生科研訓(xùn)練計劃項目(J18520148)

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

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