基于均值密度中心估計(jì)的k-means 聚類文本挖掘方法

符保龍，張愛(ài)科

(柳州職業(yè)技術(shù)學(xué)院，廣西柳州， 545006)

0 引言

隨著計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)、信息技術(shù)的迅猛發(fā)展，人類獲取信息的渠道更加豐富而方式更加簡(jiǎn)單。這也使得每個(gè)人一天被大量的各色信息所包圍，而每天所做的重要工作，就是如何從海量信息中遴選出真正需要的信息，這就需要用到數(shù)據(jù)挖掘技術(shù)［1］。文本挖掘是數(shù)據(jù)挖掘的一個(gè)重要分支，專門(mén)以分析搜索文本類型的數(shù)據(jù)為核心目標(biāo)，綜合了數(shù)據(jù)庫(kù)、統(tǒng)計(jì)分析、機(jī)器學(xué)習(xí)、模式識(shí)別等眾多學(xué)科領(lǐng)域的知識(shí)和技術(shù)［2］。從文本挖掘的實(shí)現(xiàn)方法來(lái)看，形成了分析預(yù)測(cè)法、描述統(tǒng)計(jì)法兩大類。其中，分析預(yù)測(cè)法又包含決策樹(shù)法、神經(jīng)網(wǎng)絡(luò)法、支持向量機(jī)法等;描述統(tǒng)計(jì)法又分為關(guān)聯(lián)分析法、聚類分析法等［3］。

決策樹(shù)法根據(jù)文本信息的屬性特征對(duì)原始集合進(jìn)行逐級(jí)劃分，直到分離每一個(gè)屬性特征為止，并生成相應(yīng)的決策樹(shù)，最終的挖掘過(guò)程體現(xiàn)為沿著決策樹(shù)的逆向回溯。此方法的主要優(yōu)點(diǎn)是原理簡(jiǎn)單，但復(fù)雜度受控于決策樹(shù)的維度［4］。神經(jīng)網(wǎng)絡(luò)法將搜索特征和搜索策略，映射為神經(jīng)元和神經(jīng)網(wǎng)絡(luò)，其挖掘能力的準(zhǔn)確度高，但計(jì)算時(shí)間長(zhǎng)［5］。支持向量機(jī)法是非常常用的分類方法，用于數(shù)據(jù)挖掘和文本挖掘具有理論上的優(yōu)勢(shì)，但其挖掘過(guò)程受控于核函數(shù)的選擇［6］。關(guān)聯(lián)分析是數(shù)據(jù)統(tǒng)計(jì)的常見(jiàn)方法，通過(guò)置信度、支持率2個(gè)重要參數(shù)實(shí)現(xiàn)對(duì)關(guān)聯(lián)規(guī)則的解讀。其中，支持率可以支撐不同屬性特征的劃分比例，置信度則表明了這種劃分比例的可信程度。這種方法會(huì)受到關(guān)聯(lián)規(guī)則制定者的主觀影響，不同的領(lǐng)域知識(shí)、個(gè)人價(jià)值取向都會(huì)造成關(guān)聯(lián)規(guī)則制定的差異性［7］。聚類分析致力于基于知識(shí)的自動(dòng)挖掘，是非常高效的無(wú)監(jiān)督學(xué)習(xí)方法。它通過(guò)對(duì)初始集合的特征聚類，最大程度地使用文本信息的內(nèi)在相似性，使得具有相近屬性的文本信息聚集于一個(gè)空間上高度致密的區(qū)域［8］。從實(shí)現(xiàn)上來(lái)看，K－means聚類就是非常典型的一種。但是K－means聚類受到聚類中心可變性［9］、奇異點(diǎn)［10］等問(wèn)題的影響，有時(shí)無(wú)法達(dá)到預(yù)期的挖掘性能。本文對(duì)于文本挖掘技術(shù)的研究，就是針對(duì)K－means聚類方法展開(kāi)的，尤其是針對(duì)一般K－means聚類方法的聚類中心可變性、奇異點(diǎn)等問(wèn)題進(jìn)行處理，使其能達(dá)到更高的挖掘性能。

1 K-means聚類方法

設(shè)K－means聚類方法是聚類分析中的代表性方法，也是數(shù)據(jù)挖掘和文本挖掘中的常用技術(shù)。其基本的數(shù)學(xué)處理過(guò)程如下:假設(shè)用于執(zhí)行聚類分析的初始數(shù)據(jù)集合中有m個(gè)樣本數(shù)據(jù)，其特征屬性總共有K個(gè)，這里K是一個(gè)大于0的整數(shù)。整個(gè)K－means聚類的過(guò)程，實(shí)質(zhì)上就是使得這m個(gè)樣本數(shù)據(jù)形成的特征聚類中心距離平方和最小，即滿足(1)式。

(1)式中:S表示距離平方和的目標(biāo)函數(shù);Pj為第j個(gè)樣本數(shù)據(jù);Oi為第i個(gè)特征聚類中心;?ji為第j個(gè)樣本數(shù)據(jù)與第i個(gè)特征聚類中心距離的權(quán)重系數(shù)。K－means聚類的實(shí)現(xiàn)過(guò)程，實(shí)際上就是求取距離平方和的目標(biāo)函數(shù)的極值過(guò)程。當(dāng)K－means聚類應(yīng)用于文本挖掘時(shí)，實(shí)現(xiàn)流程如圖1所示。

圖1 K－means聚類的實(shí)現(xiàn)流程Fig.1 K－means clustering implementation process

根據(jù)圖1所示的K－means聚類實(shí)現(xiàn)流程，首先確定執(zhí)行文本挖掘的原始文本數(shù)據(jù)集合。然后，為原始集合的K個(gè)特征隨機(jī)選定聚類中心。接下來(lái)開(kāi)始執(zhí)行K－means迭代算法，求取最佳的距離平方和目標(biāo)函數(shù)。迭代過(guò)程中，只要距離平方和目標(biāo)函數(shù)的數(shù)值還在變化，就說(shuō)明其尚未達(dá)到最優(yōu)。這時(shí)，就需要更新各個(gè)特征聚類中心，重新執(zhí)行迭代過(guò)程。當(dāng)距離平方和目標(biāo)函數(shù)的數(shù)值不再發(fā)生變化時(shí)，結(jié)束迭代過(guò)程，此時(shí)的聚類中心就是我們所需要的聚類中心。樣本數(shù)據(jù)與各個(gè)特征聚類中心的計(jì)算公式為(2)式中;sji表示第j個(gè)樣本數(shù)據(jù)pj與第i個(gè)特征聚類中心Oi間的距離;t表示迭代次數(shù)。

距離平方和目標(biāo)函數(shù)是否發(fā)生變化的判斷依據(jù)如(3)式所示。

K－means聚類的優(yōu)點(diǎn)是，原理簡(jiǎn)單、便于數(shù)學(xué)實(shí)現(xiàn)、收斂速度快、聚類能力強(qiáng)，對(duì)于大數(shù)據(jù)量的文本操作非常適用。K－means聚類的缺點(diǎn)是，聚類中心對(duì)于迭代結(jié)果影響較大，而對(duì)于一般使用者而言，聚類中心的數(shù)目和初值往往很難設(shè)置得非常理想。另外，因?yàn)榫嚯x平方和的目標(biāo)函數(shù)形式，只能形成規(guī)則球形聚類區(qū)域，使得K－means聚類對(duì)于一些非規(guī)則聚類特征效果不理想。再有，奇異點(diǎn)對(duì)于K－means聚類的迭代過(guò)程也有較大影響。

2 改進(jìn)的K-means聚類方法

從K－means聚類方法的缺點(diǎn)可以看出，對(duì)其影響較大的主要有3個(gè)因素:①聚類中心如何妥善選擇;②如何根據(jù)聚類情況選擇有針對(duì)性的聚類區(qū)域;③如何對(duì)奇異點(diǎn)進(jìn)行處理。為此對(duì)K－means聚類方法提出3點(diǎn)改進(jìn)措施，以全面提高其聚類效果。

首先，對(duì)于要執(zhí)行聚類分析的文本數(shù)據(jù)而言，不再隨機(jī)選取聚類中心，而是采取基于均值密度的中心估計(jì)方法來(lái)估算聚類中心，避免隨機(jī)選取聚類中心導(dǎo)致的偶然性和錯(cuò)誤。仍然用pi表示初始集合的一個(gè)文本數(shù)據(jù)點(diǎn)，現(xiàn)在以pi為中心、以E為邊長(zhǎng)，構(gòu)建一個(gè)立方體，在這個(gè)立方體內(nèi)的文本數(shù)據(jù)點(diǎn)的總數(shù)稱之為pi的密度，記為d(pi)。遍歷初始集合中的所有數(shù)據(jù)點(diǎn)，我們就可以得到以所有數(shù)據(jù)點(diǎn)為中心的密度集合D為

對(duì)(5)式中的集合數(shù)據(jù)求取均值，即可以得到原始數(shù)據(jù)集合的平均密度為

從(8)式可以看出，OK實(shí)際上是剩余數(shù)據(jù)中前(K－1)個(gè)聚類中心距離最小數(shù)據(jù)的最大者。至此，所有的聚類中心就選取完畢了。這樣選擇的聚類中心顯然比隨機(jī)選取的聚類中心具有更高的合理性和可信度。

確定了聚類中心，再來(lái)解決聚類情況與原始數(shù)據(jù)分布不符的問(wèn)題。這里，我們采用一個(gè)相對(duì)更加靈活的方式。如前所述，我們對(duì)原始數(shù)據(jù)集合和候選密度數(shù)據(jù)集合中的數(shù)據(jù)鄰域一直使用一個(gè)邊長(zhǎng)為E的立方體，實(shí)際上這個(gè)可以根據(jù)經(jīng)驗(yàn)事先確定鄰域?yàn)槠渌问健１热缜蛐?、棱錐、長(zhǎng)方體等，如圖2所示。

圖2 數(shù)據(jù)鄰域的其他形式Fig.2 Other forms of data neighborhood

當(dāng)然，實(shí)際上事先往往很難決定最適合聚類數(shù)據(jù)的鄰域形式，可以分別選用不同的鄰域形式，對(duì)比后續(xù)的處理結(jié)果哪個(gè)更加可靠。

最后，對(duì)奇異點(diǎn)的處理問(wèn)題。所謂奇異點(diǎn)，就是原始數(shù)據(jù)集合中，存在一些遠(yuǎn)離聚類中心，其周?chē)鷶?shù)據(jù)稀疏甚至沒(méi)有數(shù)據(jù)的點(diǎn)。在隨機(jī)選取聚類中心的情況下，一旦選取到奇異點(diǎn)，往往會(huì)導(dǎo)致聚類不準(zhǔn)確甚至迭代過(guò)程無(wú)法進(jìn)行的情況。因此，對(duì)于奇異點(diǎn)的去除會(huì)大大提高聚類的準(zhǔn)確性和可靠程度。對(duì)于本文的改進(jìn)方法而言，奇異點(diǎn)的去除仍然可以依據(jù)(5)式進(jìn)行。(5)式中那些密度最小的點(diǎn)，就可以被作為奇異點(diǎn)刪除掉。也可以根據(jù)事先設(shè)定的域值進(jìn)行篩選，如(9)式所示。

(9)式中:Q為事先設(shè)定的閾值;η為調(diào)整閾值的權(quán)重系數(shù)。

我們可以通過(guò)控制η的大小，來(lái)調(diào)整奇異點(diǎn)的判據(jù)。至此，對(duì)K－means聚類方法的3點(diǎn)改進(jìn)就全部實(shí)現(xiàn)，其他聚類分析的執(zhí)行過(guò)程仍然采用一般的聚類分析的執(zhí)行方法。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文方法的有效性，我們對(duì)基于均值密度中心估計(jì)的K－means聚類文本挖掘方法進(jìn)行了性能測(cè)試性實(shí)驗(yàn)。實(shí)驗(yàn)選用的計(jì)算機(jī)硬件配置為CPU雙核、主頻 2.6 GHz，內(nèi)存 4 GByte、硬盤(pán)300 GByte。軟件開(kāi)發(fā)工具選擇了XP操作系統(tǒng)、C++程序設(shè)計(jì)語(yǔ)言。文本挖掘?qū)嶒?yàn)流程如圖3所示。

圖3 文本挖掘?qū)嶒?yàn)流程Fig.3 Process of textmining experiment

圖3中，實(shí)際中分詞處理、去詞過(guò)濾、詞頻統(tǒng)計(jì)、特征信息選擇、特征向量等環(huán)節(jié)屬于文檔的預(yù)處理階段，因?yàn)椴皇潜疚牡暮诵难芯抗ぷ?，因此加以?jiǎn)要介紹。分詞處理、去詞過(guò)濾處理我們直接使用了中科院發(fā)布的文檔詞法分析系統(tǒng)。特征信息選擇和特征向量構(gòu)建，我們采用了基于文檔詞頻的方法。經(jīng)過(guò)這些預(yù)處理工作，才可以執(zhí)行后續(xù)的K－means聚類分析。實(shí)驗(yàn)所用的文本數(shù)據(jù)為120篇科技類文獻(xiàn)，其內(nèi)容主體涉及了生物、醫(yī)學(xué)、機(jī)械、通信、建筑、農(nóng)業(yè)六大方面，每個(gè)領(lǐng)域的文獻(xiàn)共有20篇，合計(jì)120篇。這120篇文獻(xiàn)的分布情況如表1所示。

表1 120篇科技文本的序號(hào)排布Tab.1 Serial number arrangement of 120 text of science and technology

我們選擇聚類項(xiàng)數(shù)K=6，分別執(zhí)行一般的K－means聚類挖掘方法和本文改進(jìn)后的方法，聚類結(jié)果如表2所示。

從表2的數(shù)據(jù)可以看出，使用一般的K－means聚類挖掘方法得到的結(jié)果是生物科技文獻(xiàn)查找正確的有第1－8篇、第11－14篇;醫(yī)學(xué)科技文獻(xiàn)查找正確的有第22－29篇、第33－40篇;機(jī)械類科技文獻(xiàn)查找正確的有第42－48篇、第50－58篇;通信類科技文獻(xiàn)查找正確的有第61－65篇、第72－79篇;建筑類科技文獻(xiàn)查找正確的有第82－88篇、第92－98篇;農(nóng)業(yè)類科技文獻(xiàn)查找正確的有第101－106篇、第114－120篇。而采用改進(jìn)K－means聚類挖掘方法得到的結(jié)果是生物科技文獻(xiàn)查找正確的有第1－10篇、第14篇、第16－18篇、第20篇;醫(yī)學(xué)科技文獻(xiàn)查找正確的有第21－28篇、第30篇、第32－37篇、第39－40篇;機(jī)械類科技文獻(xiàn)查找正確的有第42－52篇、第55－60篇;通信類科技文獻(xiàn)查找正確的有第61－70篇、72－76篇;建筑類科技文獻(xiàn)查找正確的有第81－88篇、第92－98篇;農(nóng)業(yè)類科技文獻(xiàn)查找正確的有第101－106篇、第111－120篇。

表2 本文實(shí)驗(yàn)的聚類結(jié)果Tab.2 Clustering results of the experiment

依據(jù)表2中的聚類結(jié)果，對(duì)一般的K－means聚類挖掘方法和改進(jìn)后的K－means聚類挖掘方法的查準(zhǔn)率進(jìn)行比較，其結(jié)果如表3所示。

表3 改進(jìn)前后K－means聚類挖掘方法的查準(zhǔn)率Tab.3 Before and after improvement of K means clusteringminingmethod precision

表3中數(shù)據(jù)用柱狀圖形式表達(dá)如圖4所示。

圖4 表3數(shù)據(jù)的柱狀圖分析結(jié)果Fig.4 Histogram analysis of the data in Tab.3

從表3中的數(shù)據(jù)和圖4的圖形可以看出，經(jīng)過(guò)本文方法，改進(jìn)后的K－means聚類挖掘方法對(duì)于六大類科技文獻(xiàn)的查準(zhǔn)率，有5類高于改進(jìn)前的K－means聚類挖掘方法，從而證實(shí)了本文方法改進(jìn)措施的有效性。

為了進(jìn)一步比對(duì)本文改進(jìn)方法與其他原理實(shí)現(xiàn)文本挖掘方法的性能，本文選取文獻(xiàn)［11］中的自組織神經(jīng)網(wǎng)絡(luò)聚類方法(self－organizing map feature neural network，SOM)進(jìn)行橫向比對(duì)，仍然采用表2所述的數(shù)據(jù)，比較結(jié)果如表4和圖5所示。

表4 改進(jìn)前后K－means聚類挖掘方法的查準(zhǔn)率Tab.4 Before and after improvement of K means clusteringminingmethod precision

圖5 表4數(shù)據(jù)的柱狀圖分析結(jié)果Fig.5 histogram analysis of the data in Tab.4

從表4中的數(shù)據(jù)和圖5的圖形可以看出，SOM比一般的K－means均值聚類方法要優(yōu)秀，但和本文改進(jìn)的K－means均值聚類方法相比要稍差一些。綜合這2次比較的結(jié)果可以看出，本文的改進(jìn)方法在文本挖掘查準(zhǔn)率方面不僅強(qiáng)于一般K－means均值聚類的方法，且與新近流行的自組織神經(jīng)網(wǎng)絡(luò)聚類方法相比也具有一定的優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

本文建立了一種基于均值密度的聚類中心迭代初值求取方法;根據(jù)文本數(shù)據(jù)集合的特征選擇性地使用針對(duì)性更強(qiáng)的鄰域形狀;利用均值密度配合閾值策略消除奇異點(diǎn)的影響。實(shí)驗(yàn)結(jié)果表明，經(jīng)過(guò)本文方法的改進(jìn)，K－means聚類挖掘方法可以獲得更高的文本挖掘查準(zhǔn)率。

［1］CHEN Chunling，TSENG F SC，LIANG Tyne.Hierarchical document clustering using fuzzy association rule mining［C］//In proc of the 3rd International Conference on Innovative Computing Information and Control.Dalian Liaoning:Conference Publications，2008:326－329.

［2］趙康，陸介平，倪巍偉.一種基于密度的文本聚類挖掘算法［J］.計(jì)算機(jī)應(yīng)用研究，2009，26(1):124－126.

ZHAO Kang，LIU Jieping，NIWewei.A kind of text clustering mining algorithm based on density［J］.Computer application research，2009，26(1):124－126.

［3］梁文婷，何中市，龍華，等.改進(jìn)傳統(tǒng)文本結(jié)構(gòu)關(guān)系圖的文本分析［J］.微計(jì)算機(jī)信息，2009，3:213－215.

LIANGWenting，HE Zhongshi，LONG Hua，et al.Improve the traditional text structure diagram textanalysis［J］.Microcomputer information，2009，3:213－215.

［4］徐麗，伏玉琛，李斯.一種改進(jìn)的SVM決策樹(shù)Web文本分類算法［J］.蘇州大學(xué)學(xué)報(bào):工學(xué)版，2011，31(5):7－11.

XU Li，F(xiàn)U Yuchen，LISi.An improved SVM decision tree Web text categorization algorithm［J］.Journal of suzhou university:engineering science，2011，31(5):7－11.

［5］朱云霞.結(jié)合聚類思想神經(jīng)網(wǎng)絡(luò)文本分類技術(shù)研究［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(1):155－157.

ZHU Yunxia.Combined with neural network clustering thought text classification technology research［J］.Computer application research，2012，29(1):155－157.

［6］趙知偉，顧靜航，胡亞楠，等.基于支持向量機(jī)分類和語(yǔ)義信息的中文跨文本指代消解［J］.計(jì)算機(jī)應(yīng)用，2013，33(4):984－987.

ZHAO Zhiwei，GU Jinghang HU Yanan，et al.Based on support vector machine(SVM)classification and semantic information across in Chinese text to refer to eliminate［J］.Journal of computer applications，2013，33(4):984－987.

［7］陶余會(huì)，周水庚，關(guān)佶紅.一種基于文本單元關(guān)聯(lián)網(wǎng)絡(luò)的自動(dòng)文摘方法［J］.模式識(shí)別與人工智能，2008，22(3):440－444.

TAO Yuhui，ZHOU Shuikan，GUAN Jiehong.A kind of automatic summarizationmethod based on textunitassociated network［J］.Journal of pattern recognition and artificial intelligence，2008，22(3):440－444.

［8］彭京，楊冬青，唐世渭，等.一種基于語(yǔ)義內(nèi)積空間模型的文本聚類算法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(8):1354－1363.

PENG jing，YANG Dongqin，TANG Shiwei，et al.A model based on semantic inner product space text clustering algorithm［J］.Journal of computers，2007，30(8):1354－1363.

［9］李霞，蔣盛益，張倩生，等.適用于大規(guī)模文本處理的動(dòng)態(tài)密度聚類算法［J］.北京大學(xué)學(xué)報(bào):自然科學(xué)版，2013，49(1):133－139.

LIXia，JIANG Shenyi，ZHANG Qiansheng，et al.Suitable for large－scale text processing dynamic density clustering algorithm［J］.Journal of Beijing university:natural science edition，2013，49(1):133－139.

［10］馮汝偉，謝強(qiáng)，丁秋林.基于文本聚類與分布式Lucene的知識(shí)檢驗(yàn)［J］.計(jì)算機(jī)應(yīng)用，2013，33(1):186－188.

FENG Ruwei，XIE Jiang，DING Qiulin.Based on text clustering and distributed Lucene knowledge test［J］.Journal of computer applications，2013，33(1):186－188.

［11］蔡麗宏.SOM聚類算法的改進(jìn)及其在文本挖掘中的應(yīng)用研究［D］.南京:南京航空航天大學(xué)，2011.

CAILihong.SOM clustering algorithm is improved and its application in textmining research［D］.Nanjing:Nanjing university of aeronautics and astronautics，2011.

(編輯:魏琴芳)