一種基于密度的文本聚類挖掘算法

(1.江蘇科技大學(xué) 電子信息學(xué)院， 江蘇 鎮(zhèn)江 212003; 2.東南大學(xué) 計算機(jī)科學(xué)與工程學(xué)院， 南京 210096)



摘 要：針對DBSCAN算法需用戶設(shè)置參數(shù)值、易產(chǎn)生挖掘結(jié)果偏差等不足，提出改進(jìn)算法DBTC(densitybased text clustering)，該算法不僅能夠發(fā)現(xiàn)任意形狀的簇，還有效地解決了基于密度的DBSCAN聚類算法在文本挖掘中參數(shù)設(shè)置困難和高密度的簇被相連的低密度簇包含的問題。理論分析和實(shí)驗(yàn)結(jié)果表明，算法是有效可行的。

關(guān)鍵詞：分詞； 文本聚類； 向量空間模型； 核心對象

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2009)01012403



Text cluster mining algorithm based on density

ZHAO Kang1， LU Jieping1， NI Weiwei2， WANG Guiping1



(1.School of Electronics Information， Jiangsu University of Science Technology， Zhenjiang Jiangsu 212003， China; 2. College of Computer Science Engineering， Southeast University， Nanjing 210096， China)



Abstract:Focusing on the problem that the DBSCAN algorithm needs to set parameters by users and tends to warp the mining result， proposed an improved text clustering algorithms DBTC (densitybased text clustering). The algorithm not only could find arbitrary shaped clusters， but also efficiently solved these problems which were it was too difficult for users to determine the parameters and the highdensity cluster was completely contained to the linked lowdensity cluster. Theoretic analysis and experimental results indicate that the algorithm is effective and efficient.

Key words：words segmentation; text clustering; vector space model; coreobject;



隨著網(wǎng)絡(luò)數(shù)據(jù)的不斷膨脹，信息過載和資源迷向的問題日益突出，大量的非結(jié)構(gòu)化數(shù)據(jù)迫切需要一種有效的分析處理技術(shù)，使人們能夠在這些數(shù)據(jù)中找到所需要的信息。數(shù)據(jù)挖掘技術(shù)可用于在海量的數(shù)據(jù)中發(fā)現(xiàn)所需知識。

數(shù)據(jù)挖掘的大部分研究主要是針對結(jié)構(gòu)化數(shù)據(jù)，而事實(shí)上，可獲取的大部分信息都存儲在文本數(shù)據(jù)庫中。文本挖掘作為數(shù)據(jù)挖掘的一個分支，它把文本型的信息源作為分析的對象，利用定量計算和定性分析的方法從中尋找信息的結(jié)構(gòu)、模式等各種隱含的知識。

文本聚類是文本挖掘中的一項重要技術(shù)，可以將文本數(shù)據(jù)按相似性聚成簇，以供進(jìn)一步挖掘和分析。密度聚類DBSCAN方法具有能夠發(fā)現(xiàn)任意形狀簇的優(yōu)點(diǎn)，在聚類分析中被廣泛應(yīng)用[1，2]。但是將該算法直接用于文本聚類時，需要用戶輸入?yún)?shù)，將選擇能產(chǎn)生可接受的聚類結(jié)果的參數(shù)值的責(zé)任留給用戶。算法對這些參數(shù)值非常敏感，設(shè)置的細(xì)微差別可能導(dǎo)致差別很大的數(shù)據(jù)聚類；另外，真實(shí)的文本數(shù)據(jù)的維度非常高而且可能具有傾斜的分布，全局的密度參數(shù)很難符合內(nèi)在的聚類結(jié)構(gòu)，使得高密度的簇包含在低密度的簇中。針對這些問題和不足，本文對DBSCAN算法進(jìn)行改進(jìn)，提出DBTC文本聚類算法，并進(jìn)行了算法性能分析和實(shí)驗(yàn)驗(yàn)證。

1 文本數(shù)據(jù)的預(yù)處理

由于文本數(shù)據(jù)是半結(jié)構(gòu)化的數(shù)據(jù)，在進(jìn)行文本的聚類分析之前，需要對文本集進(jìn)行預(yù)處理，將文本格式轉(zhuǎn)換為聚類算法能夠處理的數(shù)據(jù)格式。

1.1 文本的分詞

文本挖掘時，以向量表示文本，一般可以選擇字、詞和詞組。現(xiàn)有的研究結(jié)果表明[3]，選取詞作為特征項要優(yōu)于字和詞組。因此，文本預(yù)處理的第一步就是文本分詞。為了將一篇文檔切分成一個個獨(dú)立的中文單詞，本文采用基于統(tǒng)計的方法對文本進(jìn)行切分。算法的基本思想是：為了把句子切分成詞序列，也就是把字符序列重新組合成詞。分詞的過程可以看做是在給定輸入字符串S=c1c2…cn(S代表句子，c1、c2、cn代表漢字字符)的條件下輸出為S=(C1C2CX1)(CX1+1CX2)…(CXm-1Cm)=w1w2…wm的過程，而合理的概率分詞結(jié)果應(yīng)為條件P(w1w2…wm｜S)取得最大值時所對應(yīng)的詞串。

分詞中需要注意的是，為了更好地體現(xiàn)出文本的語義內(nèi)容，需要在分詞過程中去除停用詞(不宜作為文本特征的詞，如介詞、嘆詞等)和合并同義詞(將意思相近的詞用一個詞替代，如電腦可用計算機(jī)替換)。停用詞典和同義詞典需要事先定義。對于之后的文本表示來說，這實(shí)際上是一個特征值約簡的降維過程。

1.2 文本表示

文本表示采用空間向量模型(VSM)。空間向量模型的基本思想是以一個規(guī)范化的特征向量來表示文本： V(d)=(〈t1，w1(d)〉，…，〈t1，wi(d)〉，…，〈tn，wn(d)〉)。其中：ti為特征詞條項；wi(d)為ti在文本d中的權(quán)值，一般被定義為ti在d出現(xiàn)的頻率tfi(d)[3]的函數(shù)，即wi(d)=φ(tfi(d))。對于φ，采用TF×IDF函數(shù)，即

φ=(tfi(d) log (N/ni+0.01)/∑ni=1tfi(d)2 log2 (N/ni+0.01)

其中：N為總文檔數(shù)；ni為含有詞條ti的文檔數(shù)；n為特征向量的維數(shù)。wi(d)反映了詞條ti區(qū)分文檔屬性的能力，一個詞語在文檔集中出現(xiàn)的范圍越廣，說明它區(qū)分文檔的能力越低；另一方面，如果它在某一個特定的文檔中出現(xiàn)的次數(shù)越高，說明V(d)=(〈t1，w1(d)〉，…，〈ti，wi(d)〉，…，〈tn，wn(d)〉)在區(qū)分該文檔內(nèi)容屬性方面的能力越強(qiáng)。這樣，利用TF×IDF進(jìn)行計算就可以得到全部特征詞的權(quán)值，從而完成文檔的特征表示。

1.3 文本相似度

兩個文本D1和D2之間的距離常用它們之間的相似度sim(D1，D2)來衡量。當(dāng)文本被表示成空間向量模型時，可以借助向量之間的距離來表示文本之間的相似程度。相似度大，說明文本匹配程度高，反之匹配程度就低。可采用余弦計算法來計算兩個文本之間的相似度。余弦相似度定義為

sim(D1，D2)=v1#8226;v2/（｜v1｜×｜v2｜）

其中：v1、v2為兩個文檔的向量，內(nèi)積v1#8226;v2為標(biāo)準(zhǔn)向量點(diǎn)積，定義為∑ti=1v1iv2i，分母中的范數(shù)｜v1｜定義為v1#8226;v2。

2 文本的聚類

經(jīng)過了文本的預(yù)處理，獲得了可供文本聚類算法直接處理的標(biāo)準(zhǔn)數(shù)據(jù)集。如何選擇一種能夠有效處理現(xiàn)有數(shù)據(jù)集的聚類算法是本文討論的重點(diǎn)。

2.1 傳統(tǒng)的聚類算法及其局限性

目前的文本聚類方法大致可以分為層次凝聚法、平面劃分法、基于密度的方法等類型。層次聚類比平面劃分法容易獲得較高的精度[4];但是在每次合并時，需要比較所有簇之間的相似度并選擇出最佳的兩個簇，效率較低，不適用于大量文檔的集合。平面劃分法與層次凝聚法的區(qū)別在于，它將文檔集合水平地分割為若干個簇，而不是生成層次化的嵌套簇。平面劃分方法可以取得較好的效率，但在事先不知道類別的情況下對文本進(jìn)行自動的匹配和歸類，具有一定的盲目性。因此，需要在初始時對一些對聚類效果有決定性作用的參數(shù)進(jìn)行設(shè)置。基于密度的DBSCAN算法[5]因其抗噪聲能力強(qiáng)、能發(fā)現(xiàn)任意形狀的聚簇等優(yōu)點(diǎn)，在文本聚類中被廣泛地采用；但是算法依賴于兩個參數(shù)：鄰域半徑ε和鄰域內(nèi)的最少對象閾值minPts。算法對這兩個參數(shù)非常敏感，細(xì)微的差別即可能導(dǎo)致較大的聚類差異。同時，分析DBSCAN算法可以發(fā)現(xiàn)，全局恒定的鄰域半徑ε和最少對象數(shù)minPts可能導(dǎo)致高密度的聚類結(jié)果被完全包含在相連的低密度的聚類結(jié)果中。正是由于這些不足，使得DBSCAN算法難以在實(shí)際應(yīng)用中發(fā)揮作用。

2.2 相關(guān)的定義和性質(zhì)

為了說明問題并在DBSCAN基礎(chǔ)上對算法進(jìn)行改進(jìn)，首先引入一些相關(guān)的概念[6]。

定義 1 對于任何正整數(shù)k和集合D，對象p的k近鄰距離定義為p到它的第k個最近鄰居o的距離。其中p，o∈D。對象p的k近鄰距離用kdistance(p)表示。

定義2 給定集合D，p∈D，o∈Nkdistance(p)[1]。p的近鄰密度(near neighbors density)記為nndkdistance(p)，定義如下：

nndkdistance(p)(p)=1/[(∑o∈Nkdistance(p)(p) distkdistance(o)(p，o)[1]/｜Nkdistance(p)(p)｜

]

對象p的近鄰密度是關(guān)于p的k的近鄰鄰居[1]Nkdistance(p)(p)平均近鄰距離的倒數(shù)。

定義3 給定集合D， p∈D， p關(guān)于其鄰居Nkdistance(p)[1]的相對密度(relative density)記為rdkdistance(p)(p) ，定義如下：

rdkdistance(p)(p)=∑O∈Nkdistance(p)(p)[nndkdistance(o)(o)/

nndkdistance(p)(p)]/｜Nkdistance(p)(p)｜

其中：rdkdis tance(p)(p))反映了對象p的近鄰密度與其鄰居的近鄰密度之間的差別， 當(dāng)rdkdistance(p)(p)接近1時，說明對象p與其鄰居能很好地融為一體，在數(shù)據(jù)分布上密度十分接近。

定義4 給定閾值δ>0和集合D，p∈D，若｜rdkdistance(p)(p)-1｜<δ，則稱該對象p為核心對象。

定義5 核心對象p的k近鄰鄰居中，由所有核心對象加p本身構(gòu)成的子集稱為核心對象p的核心集合，記為corekdistance(p)(p)。若p非核心對象，則其核心集合無定義。

定義6 p，q∈D，對象p為核心對象q∈Nkdistance(p)(p)，則稱對象p關(guān)于核心對象q密度可達(dá)。

定義7 設(shè)D是數(shù)據(jù)集，p∈D，且p為核心對象，p的初始類C是滿足下列條件的數(shù)據(jù)集D的一個非空子集:q∈D，若o∈corekdistance(p)(p)，使得q關(guān)于核心對象o密度可達(dá)，那么q∈C。顯然，核心對象p的初始類C非空，且有Nkdistance(p)(p)C。

定義8 給定集合D，CD， p∈D， p關(guān)于類C的相對密度記為rdc(p)。定義如下：

rdc(p)=∑O∈C(nndkdistance(o)(o)/nndkdistance(p)(p))/｜C｜

其中：rdc(p)反映了對象p的近鄰密度與類C中成員對象的平均近鄰密度之間的差別。

定理 設(shè)C是一個對象集，用dismin表示C中對象的最小k近鄰距離，即dismin=min{diskdistance(o)(p，o)｜p，o∈C，o∈Nkdistance(p)(p)}。相似地，設(shè)dismax表示C中對象的最大k近鄰距離，即dismax=max{distkdistance(o)(p，o)｜p，o∈C，o∈Nkdistance(p)(p)}。令ε=(dismax/dismin)-1，對于C中的所有對象p，若Nkdistance(p)(p)C，而q∈Nkdistance(p)(p)，也都有Nkdistance(p)(p)∈C，則1/(1+ε)≤rdkdistance(p)(p)≤(1+ε)。

證明 對所有o∈Nkdistance(p)(p)，distkdistance(o)(p，o)≥dismin。那么依定義2可知對象p的近鄰密度nndkdistance(p)(p)≤1/dismin；另一方面， distkdistance(o)(p，o)≤distmax，因此，nndkdistance(p)(p)≥1/dismax。設(shè)q∈Nkdistance(p)(p)，根據(jù)以上討論可知，q的近鄰密度nndkdistance(p)(p)也在1/dismax和1/dismin之間。根據(jù)定義3可知對象p的相對密度rdkdistance(p)(p)滿足distmin/dismax≤rdkdistance(p)(p)≤dismax/dismin，即1/(1+ε)≤rdkdistance(p)(p)≤(1+ε)。

類C的核心對象p的rdkdistance(p)(p)值接近于1。定理為算法參數(shù)δ的選擇限定了取值范圍，從而不像DBSCAN算法中參數(shù)Eps那樣取值具有太多的盲目性和試探性。

2.3 算法思想

文本聚類是從給定的文檔本身出發(fā)，根據(jù)文檔特征詞矢量將相關(guān)者聚成一類。對于給定的文檔集合D={d1，…，di，…，dn}，在數(shù)據(jù)集D中找到一個核心對象p，求出p的核心集合，得到初始類C；然后由初始類C進(jìn)行擴(kuò)展，直到?jīng)]有任何核心對象可以歸入該類；重新在D中尋找任意一個未歸類的核心對象q。重復(fù)上述過程，直到?jīng)]有任何對象可以歸入任何類。

初始類C的擴(kuò)展過程分為兩步：a)對p的核心集合進(jìn)行擴(kuò)展，得到類C的核心集合；b)根據(jù)關(guān)于擴(kuò)展的核心集合中的核心對象的密度可達(dá)這一條件，對類C進(jìn)行擴(kuò)展。

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

3.1 聚類的準(zhǔn)確率

一般來說，將查全率和查準(zhǔn)率結(jié)合起來才能正確地評價一個文本聚類算法。但是在文本聚類過程中，并不存在手工的分類類別和自動聚類的簇一一對應(yīng)的關(guān)系，因此以查全率和查準(zhǔn)率作為評價標(biāo)準(zhǔn)并不合適，本文采用加權(quán)平均準(zhǔn)確率[7]作為衡量聚類效果的標(biāo)準(zhǔn)。由于聚類所得到的類簇中包含的文本往往來自于不同的標(biāo)準(zhǔn)類，這個標(biāo)準(zhǔn)就假設(shè)類簇的標(biāo)準(zhǔn)類標(biāo)志等于這個類簇中最大的那個標(biāo)準(zhǔn)類的類標(biāo)志，而該類簇的準(zhǔn)確率就等于這個類簇中最大的那個標(biāo)準(zhǔn)類所占的比率，其計算式為

precision(C)=(1/｜C｜) max(｜{di｜label(di)=cj}｜)

整個聚類結(jié)果的準(zhǔn)確率表達(dá)式為precision=∑G′k=1(｜Ck｜/N) precision(Ck)。其中：Ck代表聚類結(jié)果簇；G′為類簇的個數(shù)。

實(shí)驗(yàn)從百度上采集5 000篇文檔作為訓(xùn)練集，將基于DBSCAN的聚類算法與基于DBTC的聚類算法進(jìn)行比較，對一個對象鄰域內(nèi)所包含的最小數(shù)目的minPts，先后取2、4、6、8，其聚類準(zhǔn)確率如表1所示，在DBSCAN中ε為一定值。實(shí)驗(yàn)結(jié)果表明，較之基于DBSCAN的文本聚類算法，DBTC算法的準(zhǔn)確率有明顯的提高。

表1 兩種文本聚類算法的聚類準(zhǔn)確率的比較

KDBSCAN算法DBTC算法KDBSCAN算法DBTC算法

468.4%71.8%873.1%75.9%

672.8%76.2%1071.5%73.2%

3.2 聚類的質(zhì)量

本文所改進(jìn)的基于密度的文本聚類算法DBTC可以在有噪聲的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的簇，并且有效地解決了DBSCAN算法所存在的高密度簇可能包含在相連的低密度簇間的問題。聚類質(zhì)量如圖1、2所示。

圖1、2為兩種聚類算法的結(jié)果，可見，DBTC算法相對于DBSCAN算法，能夠把類分得更細(xì)，而且也更為準(zhǔn)確。

4 結(jié)束語

本文通過對已有的基于DBSCAN的文本聚類算法的研究提出了一種改進(jìn)的文本聚類算法DBTC。該算法有效地解決了DBSCAN算法用于文本聚類時參數(shù)設(shè)置困難以及可能出現(xiàn)高密度聚類結(jié)果包含在低密度簇中的問題。實(shí)驗(yàn)和算法分析表明，DBTC算法是有效的。

參考文獻(xiàn)：

［1］CHEN Mingshan， HAN Jiawei， PHILP S Y. Datamining: an overview from a database perceptive[J].IEEE Trans on Knowledge and Data Engineering，1996，8(6):866882.

[2]HAN Jiawei， KAMBER M. 數(shù)據(jù)挖掘:概念與技術(shù)[M].范明，孟小峰，等譯. 北京：機(jī)械工業(yè)出版社.2004.

[3]YANG Yiming， PEDERSON J O. A comparative study on feature selection in text categorization[C]//Proc ofthe 14th International Conference on Machine Learning. San Francisco: Morgan Kaufmann Publishers， 1997:412420.

[4]易高翔，程耕國.Web文本挖掘研究[J].武漢科技大學(xué)學(xué)報:自然科學(xué)版，2005，28(1):7274.

[5]ESTER M， KRIEGEL H P， SANDER J， et al. A densitybased algorithm for discovering clusters in large spatial databases with noise[C]//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining.[S.l.]:AAAI Press， 1996:226231.

[6]劉青寶，鄧蘇，張維明.基于相對密度的聚類算法[J].計算機(jī)科學(xué) 2007，34(2):192195.

[7]HOTHO A， STAAB S， STUMME G. Wordnet improves text document clustering[C]//Proc of SIGIR Semantic Web Workshop. 2003:541544.

[8]石陸魁，何丕康.一種基于密度高效聚類算法[J].計算機(jī)應(yīng)用，2005，25(8):18241826，1839.

[9]魯松，李曉黎，白碩，等.文檔中詞語權(quán)重計算方法的改進(jìn)[J].中文信息學(xué)報，2001，14(6):813.

[10]楊炳儒.知識工程與知識發(fā)現(xiàn)[M].北京:冶金工業(yè)出版社，2000:520.