基于改進(jìn)的K-means算法在文本挖掘中的應(yīng)用

楊 丹，朱世玲，卞正宇

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

0 引 言

K-means算法作為一種無監(jiān)督的機(jī)器學(xué)習(xí)算法[1]，具有簡單易理解、聚類速度快等特點(diǎn)。目前聚類算法大致可以分為基于劃分的、密度的、分層的、網(wǎng)格的、模型的等類型[2-6]。雖然K-means算法在眾多領(lǐng)域應(yīng)用廣泛，但是其聚類質(zhì)量的優(yōu)劣則取決于多個(gè)因素。針對K-means算法對于初始聚類中心選擇的敏感性，文獻(xiàn)[7-8]提出了一種基于最大最小距離法選取初始聚類中心的方法，該算法基于距離最遠(yuǎn)的數(shù)據(jù)對象最不可能分到一個(gè)簇的事實(shí)，獲取若干個(gè)距離彼此相隔較遠(yuǎn)的點(diǎn)作為初始中心[9]。雖然該算法的聚類效果相對于傳統(tǒng)算法有了一定的提高，但是并沒有考慮到距離較遠(yuǎn)的數(shù)據(jù)對象可能是離群點(diǎn)的情況，離群點(diǎn)作為初始聚類中心會影響到聚類的最終結(jié)果[10]并且也會增加迭代的次數(shù)。

在上述算法的基礎(chǔ)上，文中依據(jù)稀疏度能夠度量點(diǎn)周圍緊湊程度的特點(diǎn)[11-12]，結(jié)合最大最小距離法的原理，提出了一種新的結(jié)合稀疏度和距離的方式來選擇初始聚類中心，并通過實(shí)驗(yàn)對該算法進(jìn)行驗(yàn)證。

1 稀疏度

在數(shù)據(jù)集D{x1,x2,…,xn}中,對象F的稀疏度定義為：

(1)

其中，Ni表示xi的K個(gè)近鄰對象組成的對象集合；d(xi,xj)表示xi,xj之間的距離。

2 K-means算法

2.1 基本思想

給定一個(gè)數(shù)據(jù)集D{x1,x2,…,xn},每一個(gè)數(shù)據(jù)對象都是m維的，將數(shù)據(jù)集D劃分為K個(gè)簇{S1,S2,…,SK}，使用K-means算法過程需要使用的定義如下：

定義1:兩個(gè)數(shù)據(jù)對象之間的距離(歐氏距離)。

(2)

其中,xi,xj為數(shù)據(jù)集中的兩個(gè)數(shù)據(jù)對象。

定義2:聚類中心。

(3)

其中，nc表示簇C包含數(shù)據(jù)對象的個(gè)數(shù)；xi表示簇C的第i個(gè)數(shù)據(jù)對象。

定義3:聚類的終止條件。

(4)

其中,K表示簇的個(gè)數(shù);Zj表示第j個(gè)簇的中心;nj表示第j個(gè)簇包含的數(shù)據(jù)對象的個(gè)數(shù)。

定義4:Minps值。

(5)

(6)

上述公式都是一種經(jīng)驗(yàn)的規(guī)則，xi鄰近的Minpts個(gè)點(diǎn)組成Ni，Kmax表示最大的聚類簇?cái)?shù)，beta為用戶自定義的參數(shù)。

算法1：K-means算法。

輸入：數(shù)據(jù)集D，簇的個(gè)數(shù)K，聚類終止條件E，迭代次數(shù)T

輸出：K個(gè)滿足終止條件和迭代次數(shù)的簇

Step1：在數(shù)據(jù)集D中任選K個(gè)初始聚類中心；

Step2：循環(huán)Step3～Step5，判斷是否滿足終止條件E和迭代次數(shù)；

Step3：按照定義1計(jì)算剩余的數(shù)據(jù)對象到每個(gè)聚類中心的距離，將其歸并到距離最小的簇中；

Step4：按照定義2，重新計(jì)算每個(gè)簇的聚類中心；

Step5：按照定義3，計(jì)算聚類結(jié)果E。

2.2 改進(jìn)的K-means算法描述

對于初始聚類中心的選擇，不僅要考慮到初始聚類中心周圍的緊密程度，而且還要保證初始聚類中心盡量的離散。因此文中在采用稀疏度評判數(shù)據(jù)對象周圍稀疏度的同時(shí)，為了保證聚類中心點(diǎn)盡量離散，采用了一種新的結(jié)合稀疏度和距離的度量方式。首先通過稀疏度來判斷數(shù)據(jù)周圍的緊密程度，然后結(jié)合最大最小距離的原則構(gòu)建一個(gè)新的評價(jià)函數(shù)。該評價(jià)函數(shù)可以有效避免文獻(xiàn)[10]必須人為確定參數(shù)的缺點(diǎn)，使得初始聚類中心的選擇更加穩(wěn)定。評價(jià)函數(shù)如下：

(7)

其中，S(xi)表示數(shù)據(jù)對象xi的稀疏度；D(xi)表示數(shù)據(jù)對象xi與其他已選初始聚類中心距離的最小值；Si的值是介于-1和1之間。Si接近1時(shí)，表示數(shù)據(jù)對象xi的周圍是緊湊的，且遠(yuǎn)離其他的聚類中心。

改進(jìn)的算法流程如下：

輸入：簇的數(shù)目K，數(shù)據(jù)集D，最大迭代次數(shù)T及終止條件E

輸出：K個(gè)滿足終止條件和迭代次數(shù)的簇

Step1：按照式1～5，計(jì)算每個(gè)數(shù)據(jù)對象由Minpts個(gè)點(diǎn)組成的對象集合的稀疏度，選擇稀疏度最小點(diǎn)作為第一個(gè)初始聚類中心；

Step2：按照式7計(jì)算剩余的數(shù)據(jù)對象與已選取的初始聚類中心值，選取值最大的點(diǎn)作為剩余初始聚類中心，依次循環(huán)下去，直到滿足K個(gè)初始聚類中心；

Step3：利用K個(gè)初始聚類中心進(jìn)行聚類。

3 文本聚類

3.1 TF-IDF算法

文本表示常用的模型有布爾邏輯模型(BM)、向量空間模型(VSM)[13-15]、潛在語義索引(LSI)[16]和概率模型(PM)等。文中采用的是向量空間模型，對于文檔D，采用(TF-IDF1,TF-IDF2,…,TF-IDFn)來表示[17-19]。IF-IDF算法公式如下：

TF-IDF(ti,d)=

(8)

其中，ni為含詞條ti的文檔數(shù)；N為文檔總數(shù)。

3.2 改進(jìn)的文本距離計(jì)算

K-means算法通常是根據(jù)兩個(gè)數(shù)據(jù)對象之間的距離來歸類的[20-22]。但在對文本進(jìn)行聚類之前，通常采用余弦公式來計(jì)算兩個(gè)文本間的相似度。文中根據(jù)相似度值總是處于0和1之間的特點(diǎn)，采取一種簡單的數(shù)學(xué)變化將文本相似度轉(zhuǎn)化為文本距離，避免文獻(xiàn)[8]采用lg方法需設(shè)計(jì)參數(shù)的問題，距離公式如下：

余弦計(jì)算公式：

(9)

距離計(jì)算公式：

Distancei,j=1-cosθ

(10)

其中，vi和vj分別表示兩個(gè)文本特征向量，在距離公式中，當(dāng)兩個(gè)文本的相似度為1時(shí)，距離為0；當(dāng)兩個(gè)文本之間相似度為0時(shí)，兩者之間的距離最大為1。

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

4.1 實(shí)驗(yàn)一

4.1.1 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(huán)境：Window7操作系統(tǒng)，1T硬盤，MyEclipse軟件，Java編程軟件。

實(shí)驗(yàn)數(shù)據(jù)：為了驗(yàn)證改進(jìn)后的算法優(yōu)于傳統(tǒng)算法和文獻(xiàn)[4]算法，采用了UCI數(shù)據(jù)庫中的3個(gè)數(shù)據(jù)集：Iris、Wine及Balance-Scale。其中Iris數(shù)據(jù)集包含4個(gè)屬性，150個(gè)數(shù)據(jù)對象，分為3類；Wine數(shù)據(jù)集包含13個(gè)屬性，178個(gè)數(shù)據(jù)對象，分為3類；Balance數(shù)據(jù)集包含4個(gè)屬性，625個(gè)數(shù)據(jù)對象，分為3類。

實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)通過準(zhǔn)確率、召回率及F度量值對傳統(tǒng)算法、最大最小距離法及改進(jìn)后的算法進(jìn)行了比較，結(jié)果見表1。

表1 算法比較(1)

%

4.1.2 實(shí)驗(yàn)分析

根據(jù)表1的實(shí)驗(yàn)結(jié)果可以看出，傳統(tǒng)算法在Iris數(shù)據(jù)集的10組實(shí)驗(yàn)結(jié)果中，準(zhǔn)確率、召回率及F度量值中最高值與最低值都相差30個(gè)百分點(diǎn)以上，在Wine數(shù)據(jù)集上，三個(gè)度量值中最高值與最低值相差也在15個(gè)百分點(diǎn)以上。在相差值較小的Balance-Scale數(shù)據(jù)集中三個(gè)度量值的最高值與最低值相差也達(dá)到了10個(gè)百分點(diǎn)左右。因此傳統(tǒng)算法的聚類結(jié)果的隨機(jī)性很大，很不穩(wěn)定。

最大最小距離法相對于傳統(tǒng)算法在Iris數(shù)據(jù)集上的準(zhǔn)確率、召回率及F度量值都優(yōu)于傳統(tǒng)算法,但是在Wine、Balance-Scale數(shù)據(jù)集上聚類效果略低于傳統(tǒng)算法。首先對Wine數(shù)據(jù)集進(jìn)行分析，可以發(fā)現(xiàn)該數(shù)據(jù)集的最后一個(gè)屬性值的范圍跨度較大，最大值為1 680，最小值為278，采用最大最小距離法選取初始聚類中心會受到最后一條屬性的影響，因此所選取的聚類中心不能很好地代表數(shù)據(jù)的實(shí)際分布。其次再對Balance-Scale數(shù)據(jù)集進(jìn)行分析，可以發(fā)現(xiàn)它的分布極度不均勻，最大的簇包含288個(gè)數(shù)據(jù)對象，而最小的簇僅僅包含49個(gè)數(shù)據(jù)對象，如果僅僅采用最大最小距離法選取初始聚類中心，可能會導(dǎo)致所選取的中心來源于某一個(gè)或其中的某幾個(gè)簇。

文中改進(jìn)算法是在最大最小距離乘積法的基礎(chǔ)上，采用稀疏度來評判所選取的聚類中心，既考慮到了數(shù)據(jù)的分布情況，又使所選取的聚類中心較遠(yuǎn)。從實(shí)驗(yàn)結(jié)果來看，該算法無論是在分布均勻的數(shù)據(jù)集中，還是在分布不均勻的數(shù)據(jù)集中，聚類的準(zhǔn)確率、召回率以及F度量值都優(yōu)于傳統(tǒng)算法和最大最小距離算法。

4.2 實(shí)驗(yàn)二

4.2.1 實(shí)驗(yàn)數(shù)據(jù)

為了證明改進(jìn)后的算法聚類結(jié)果的優(yōu)越性，實(shí)驗(yàn)數(shù)據(jù)采用了搜狗語料庫中的財(cái)經(jīng)文檔150篇，教育文檔500篇和軍事文檔350篇。通過準(zhǔn)確率、召回率及F值對實(shí)驗(yàn)結(jié)果進(jìn)行分析，比較算法的聚類效果。其中傳統(tǒng)算法的值為5次實(shí)驗(yàn)結(jié)果的平均值。實(shí)驗(yàn)結(jié)果見表2。

4.2.2 實(shí)驗(yàn)分析

由于文本具有高維稀疏的特點(diǎn)，所以文本聚類的效果并不像普通數(shù)據(jù)集那樣產(chǎn)生較好的結(jié)果。針對文本聚類過程中不可以采用簇的均值替代新的聚類中心的原理，采用K-中心算法中計(jì)算新的中心點(diǎn)的方法來獲取迭代中的中心點(diǎn)。通過表2可以看出，改進(jìn)算法相較于傳統(tǒng)算法和最大最小距離法在聚類質(zhì)量上都有了一定的提高，因此，該算法相較于傳統(tǒng)算法和最大最小距離法較適合用于進(jìn)行文本聚類。

表2 算法比較(2)

5 結(jié)束語

針對K-means算法相較于其他聚類算法具有對初始中心敏感的特點(diǎn)，結(jié)合最大最小距離的方法提出了一種基于稀疏度選取初始聚類中心的算法。實(shí)驗(yàn)結(jié)果表明，該算法優(yōu)于傳統(tǒng)的K-means算法和最大最小距離算法，并得到較好的聚類效果。最后將該算法應(yīng)用于文本的聚類處理中，在聚類的過程中通過一個(gè)簡單的變換將相似度轉(zhuǎn)化為對象之間的距離值。實(shí)驗(yàn)表明該算法相較于傳統(tǒng)算法和最大最小距離法更加適用于文本聚類處理，準(zhǔn)確率和召回率和F度量值都有了一定的提高。