基于信息熵改進(jìn)的K-means動(dòng)態(tài)聚類(lèi)算法

楊玉梅

(川北醫(yī)學(xué)院 圖書(shū)館,四川 南充 637000)

?

基于信息熵改進(jìn)的K-means動(dòng)態(tài)聚類(lèi)算法

楊玉梅

(川北醫(yī)學(xué)院 圖書(shū)館,四川 南充 637000)

摘要：初始聚類(lèi)中心及聚類(lèi)過(guò)程產(chǎn)生的冗余信息是影響K-means算法聚類(lèi)性能的主要因素，也是阻礙該算法性能提升的主要問(wèn)題。因此，提出一個(gè)改進(jìn)的K-means算法。改進(jìn)算法通過(guò)采用信息熵對(duì)聚類(lèi)對(duì)象進(jìn)行賦權(quán)來(lái)修正聚類(lèi)對(duì)象間的距離函數(shù)，并利用初始聚類(lèi)的賦權(quán)函數(shù)選出質(zhì)量較高的初始聚類(lèi)中心點(diǎn)；然后，為算法的終止條件設(shè)定標(biāo)準(zhǔn)閾值來(lái)減少算法迭代次數(shù)，從而減少學(xué)習(xí)時(shí)間；最后，通過(guò)刪除由信息動(dòng)態(tài)變化而產(chǎn)生的冗余信息來(lái)減少動(dòng)態(tài)聚類(lèi)過(guò)程中的干擾，以使算法達(dá)到更準(zhǔn)確更高效的聚類(lèi)效果。實(shí)驗(yàn)結(jié)果表明，當(dāng)數(shù)據(jù)樣本數(shù)量較多時(shí)，相比于傳統(tǒng)的K-means算法和其他改進(jìn)的K-means算法，提出的算法在準(zhǔn)確率和執(zhí)行效率上都有較大提升。

關(guān)鍵詞：K-means算法；信息熵；數(shù)據(jù)挖掘；動(dòng)態(tài)聚類(lèi)

0引言

聚類(lèi)分析作為數(shù)據(jù)挖掘的重要分支，在信息化時(shí)代起著舉足輕重的作用。聚類(lèi)分析的目標(biāo)在于將數(shù)據(jù)集分成若干個(gè)簇，并保證同一簇內(nèi)的數(shù)據(jù)點(diǎn)相似度盡可能的大，簇與簇之間的數(shù)據(jù)點(diǎn)的相似度盡可能的小[1]。聚類(lèi)操作是對(duì)事先未知的數(shù)據(jù)對(duì)象進(jìn)行類(lèi)的劃分，而類(lèi)的形成是由數(shù)據(jù)驅(qū)動(dòng)來(lái)完成。在數(shù)據(jù)挖掘領(lǐng)域中，聚類(lèi)分析既可以作為數(shù)據(jù)挖掘過(guò)程中的一個(gè)環(huán)節(jié)，又可以作為獲取數(shù)據(jù)分布情況的工具。聚類(lèi)分析的應(yīng)用前景較為廣泛，比如：生物種群的劃分、目標(biāo)客戶(hù)的定位、市場(chǎng)趨勢(shì)分析、模式識(shí)別及圖像處理等[2]。

K-means算法是聚類(lèi)分析常用的方法之一，該算法的特點(diǎn)在于簡(jiǎn)單、效率高且宜于處理大規(guī)模的數(shù)據(jù)，已經(jīng)被應(yīng)用到眾多領(lǐng)域，如自然語(yǔ)言處理、天文、海洋、土壤數(shù)據(jù)處理等[3]。自K-means算法提出以來(lái)，大量有關(guān)K-means算法的研究如雨后春筍般涌現(xiàn)，同時(shí)該算法的弊端也紛紛暴露出來(lái)，主要包括以下4點(diǎn)：①必須事先確定K值。②聚類(lèi)結(jié)果會(huì)受到初始聚類(lèi)中心影響。③處理分類(lèi)屬性數(shù)據(jù)較為困難且易產(chǎn)生局部最優(yōu)解[4]。④當(dāng)數(shù)據(jù)樣本數(shù)量較大時(shí)，不僅使算法的時(shí)間開(kāi)銷(xiāo)非常大，且由聚類(lèi)的動(dòng)態(tài)變化導(dǎo)致的冗余信息也將對(duì)算法產(chǎn)生影響。由于上述K-means算法的第1和第3個(gè)缺點(diǎn)是算法本質(zhì)所致，幾乎是無(wú)法改變的，為此，國(guó)內(nèi)外諸多專(zhuān)家學(xué)者針對(duì)其余不足提出了眾多解決方法。文獻(xiàn)[2]提出基于密度的改進(jìn)K均值算法，該算法針對(duì)由初始中心點(diǎn)的隨機(jī)產(chǎn)生導(dǎo)致的聚類(lèi)結(jié)果的不穩(wěn)定提出了改進(jìn)算法；文獻(xiàn)[3] 提出基于密度和最鄰近的K-means文本聚類(lèi)算法；文獻(xiàn)[4]提出聚類(lèi)模式下一種優(yōu)化的K-means文本特征選擇算法，文獻(xiàn)[5]提出基于信息熵的精確屬性賦權(quán)K-means聚類(lèi)算法,文獻(xiàn)[6]提出一種基于余弦值和K-means的植物葉片識(shí)別方法等。然而，國(guó)內(nèi)外諸多專(zhuān)家學(xué)者在一定程度上都是對(duì)K-means算法的初始聚類(lèi)中心進(jìn)行優(yōu)化，并沒(méi)有考慮數(shù)據(jù)樣本數(shù)量較多的情況。

在上述情況下，論文針對(duì)K-means算法的第2點(diǎn)和第4點(diǎn)不足，提出基于信息熵的K-means動(dòng)態(tài)聚類(lèi)方法，該算法首先通過(guò)熵值法對(duì)聚類(lèi)對(duì)象賦權(quán)的方式來(lái)修正對(duì)象間的距離函數(shù)，利用初始聚類(lèi)的賦權(quán)函數(shù)值選出質(zhì)量較高的初始聚類(lèi)中心點(diǎn)。其次通過(guò)為算法的終止條件設(shè)定標(biāo)準(zhǔn)值，減少算法迭代次數(shù)，減少學(xué)習(xí)時(shí)間；通過(guò)刪除由信息動(dòng)態(tài)變化而產(chǎn)生的冗余信息，減少動(dòng)態(tài)聚類(lèi)過(guò)程中的干擾，使算法達(dá)到更準(zhǔn)確更高效的聚類(lèi)效果。

1相關(guān)基本定義

假設(shè)Α={ai|ai∈Rm,i=1,2,…,n}為給定的數(shù)據(jù)集，Ti(i=1,2,…,k)代表第i個(gè)類(lèi)別，c(T1),c(T2),…,c(Tk)分別是k個(gè)聚類(lèi)中心。有如下定義。

定義1設(shè)向量ai=(ai1,ai2,…,aim)和向量aj=(aj1,aj2,…,ajm)分別代表2個(gè)數(shù)據(jù)對(duì)象，那么它們之間的歐式距離定義為

(1)

定義2同一類(lèi)別的數(shù)據(jù)對(duì)象的質(zhì)心點(diǎn)定義為

(2)

(2)式中，|Ti|是Ti中數(shù)據(jù)對(duì)象的個(gè)數(shù)。

定義3同屬于Tj組的ni個(gè)數(shù)據(jù)對(duì)象ai(i=1,2,…,n1)的標(biāo)準(zhǔn)差[5]σ定義為

(3)

2優(yōu)化K-means算法的初始聚類(lèi)中心點(diǎn)

傳統(tǒng)的K-means算法是隨機(jī)選擇初始聚類(lèi)中心點(diǎn)，可能造成在同一類(lèi)別的樣本被強(qiáng)行當(dāng)做2個(gè)類(lèi)別的初始聚類(lèi)中心點(diǎn)，使結(jié)果簇只能收斂于局部最優(yōu)解，因此，為了選出更為合理的初始聚類(lèi)中心，需要對(duì)初始聚類(lèi)中心進(jìn)行預(yù)處理，基本思想[6]為：首先把數(shù)據(jù)集平均分成k1(k1>k)個(gè)子集，在每個(gè)子集中隨機(jī)選出某一數(shù)據(jù)對(duì)象，然后把這k1個(gè)數(shù)據(jù)對(duì)象當(dāng)做聚類(lèi)種子中心進(jìn)行初聚類(lèi)，計(jì)算每個(gè)類(lèi)別的賦權(quán)類(lèi)別價(jià)值函數(shù)σi，按照從小到大的順序進(jìn)行排列，最后把前k個(gè)類(lèi)對(duì)應(yīng)的質(zhì)心作為初始聚類(lèi)的中心點(diǎn)。

(4)

使用熵值法[7]確定屬性權(quán)重值的步驟如下：

Step 1構(gòu)造屬性值矩陣

其中，n表示樣本數(shù)據(jù)個(gè)數(shù)，m為每個(gè)數(shù)據(jù)對(duì)象的維數(shù)。

Step 2計(jì)算第j維屬性對(duì)應(yīng)的第i個(gè)數(shù)據(jù)對(duì)象的屬性值比重。需要對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，即將數(shù)據(jù)壓縮到區(qū)間[0,1]，其過(guò)程如(5)式所示

(5)

(5)式中：Mij表示屬性值比重，xij代表屬性值，i=1,2,…,n，j=1,2,…,m。

Step 3計(jì)算第j維屬性的熵值

(6)

Step 4計(jì)算第j維屬性的差異性系數(shù)為

(7)

對(duì)于給定的j，當(dāng)Hj越小時(shí)，qj越大，屬性越重要。

Step 5第j維的屬性權(quán)值的計(jì)算

(8)

Step 6使用歐式距離計(jì)算數(shù)據(jù)對(duì)象之間的相似性，根據(jù)定義1可得賦權(quán)后的歐式距離[8]為

(9)

(9)式中，ωj是第j維屬性的權(quán)值。相當(dāng)于使權(quán)值對(duì)應(yīng)的屬性值進(jìn)行了適當(dāng)?shù)姆糯蠡蚩s小，使權(quán)值大的屬性聚類(lèi)作用更大，權(quán)值小的屬性聚類(lèi)作用更小。

Step 7采用標(biāo)準(zhǔn)差作為標(biāo)準(zhǔn)測(cè)度函數(shù)，由定義3求得賦權(quán)類(lèi)別目標(biāo)價(jià)值函數(shù)[9]為

(10)

(10)式中：σi表示第i類(lèi)的賦權(quán)標(biāo)準(zhǔn)差；|Tj|是Tj所含數(shù)據(jù)對(duì)象的個(gè)數(shù)。由(10)式可知，σi的值越小，類(lèi)內(nèi)數(shù)據(jù)對(duì)象相似度越大，數(shù)據(jù)對(duì)象越密集，其所在類(lèi)的質(zhì)心越能夠體現(xiàn)分類(lèi)決策面。

3本文改進(jìn)算法

3.1K-means算法改進(jìn)思想

在樣本數(shù)據(jù)聚類(lèi)的過(guò)程中，不僅需要計(jì)算每個(gè)聚類(lèi)對(duì)象與他們中心對(duì)象的距離，還需要重新計(jì)算中心對(duì)象發(fā)生變化的聚類(lèi)的均值，且計(jì)算是在一次次迭代中重復(fù)完成，當(dāng)數(shù)據(jù)樣本較多時(shí)，過(guò)大的計(jì)算量會(huì)嚴(yán)重影響算法的性能。其次，由于K-means聚類(lèi)是個(gè)動(dòng)態(tài)變化的過(guò)程，聚類(lèi)過(guò)程中將產(chǎn)生一些冗余信息，會(huì)對(duì)聚類(lèi)產(chǎn)生一些不必要的干擾。針對(duì)K-means算法的以上缺陷，提出2點(diǎn)優(yōu)化原則。①減少聚類(lèi)過(guò)程中的迭代次數(shù)；②減少聚類(lèi)過(guò)程中的數(shù)據(jù)量。K-means動(dòng)態(tài)聚類(lèi)算法的基本思想：由于K-means算法是通過(guò)迭代的過(guò)程把數(shù)據(jù)集劃分為不同的類(lèi)別，首先為中心點(diǎn)的該變量設(shè)定一個(gè)值，在迭代的過(guò)程中，當(dāng)中心點(diǎn)的該變量小于某個(gè)設(shè)定值時(shí)，將整個(gè)簇加入到已選數(shù)據(jù)集，同時(shí)將它從樣本集中刪除，使得原始樣本數(shù)據(jù)集中只保留未被正確識(shí)別的樣本。然后算法進(jìn)入下一輪循環(huán)，對(duì)其他樣本進(jìn)行篩選，直到所有樣本數(shù)據(jù)都被正確識(shí)別。

3.2本文改進(jìn)算法描述

結(jié)合基于信息熵的賦權(quán)方法與K-means的動(dòng)態(tài)聚類(lèi)對(duì)數(shù)據(jù)集合進(jìn)行聚類(lèi)處理，算法流程如圖1所示。

算法步驟描述如下

輸入：數(shù)據(jù)對(duì)象集A，聚類(lèi)種子初始中心點(diǎn)個(gè)數(shù)k1。

輸出：k個(gè)結(jié)果簇，使每個(gè)聚類(lèi)中心點(diǎn)的改變量小于設(shè)定的值，直至數(shù)據(jù)對(duì)象集合為?。

Step 2使用熵值法計(jì)算數(shù)據(jù)對(duì)象各個(gè)屬性的權(quán)值。

Step 3將數(shù)據(jù)集平均分成k1(k1>k)個(gè)子集，從各個(gè)子集中隨機(jī)選出一個(gè)數(shù)據(jù)對(duì)象，并將其作為聚類(lèi)種子中心。

Step 4掃描數(shù)據(jù)集合，根據(jù)其與各聚類(lèi)種子中心的相似度(賦權(quán)后的歐式距離)，將其歸于與其最相似的簇中。

Step 5計(jì)算k1個(gè)聚類(lèi)的σi(i=1,2,…,k1)，并按照σi值遞增順序排序，選前k個(gè)σi值對(duì)對(duì)應(yīng)的質(zhì)心作為初始聚類(lèi)中心。

Step 6將樣本集中的樣本按照歐式距離最短原則分配到最鄰近的簇中。

Step 7計(jì)算每個(gè)類(lèi)的質(zhì)心點(diǎn)。

Step 8判斷聚類(lèi)中心點(diǎn)的改變量是否滿(mǎn)足設(shè)定的條件，如果滿(mǎn)足，將其加入到已選特征集，同時(shí)將它從數(shù)據(jù)樣本集中刪除。

圖1　本文改進(jìn)算法流程圖Fig.1　Flow chart of the proposed improved algorithm

Step 9判斷數(shù)據(jù)樣本集是否為空，如果為空，結(jié)束算法。如果不為空，遍歷中心點(diǎn)個(gè)數(shù)N，當(dāng)N

Step 10更新中心點(diǎn)。計(jì)算每個(gè)聚類(lèi)中心點(diǎn)的改變量大于設(shè)定值的簇的質(zhì)心，并將其作為新的聚類(lèi)中心，然后轉(zhuǎn)向Step 6。

Step 11結(jié)束，數(shù)據(jù)樣本為空集，得到k個(gè)結(jié)果簇。

算法優(yōu)點(diǎn)：該算法不但利用熵值法提升了所選初始中心的質(zhì)量，而且還通過(guò)為算法終止條件設(shè)定標(biāo)準(zhǔn)值以及刪除由信息動(dòng)態(tài)變化而產(chǎn)生的冗余信息的策略，減少了算法學(xué)習(xí)時(shí)間及干擾，從而使算法較高效地獲得高質(zhì)量的聚類(lèi)效果。

4對(duì)比實(shí)驗(yàn)

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

為了分析本文改進(jìn)算法的聚類(lèi)性能，使用5種不同的公用數(shù)據(jù)集合進(jìn)行模擬實(shí)驗(yàn)。數(shù)據(jù)樣本集合均來(lái)自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)，UCI數(shù)據(jù)庫(kù)是一個(gè)專(zhuān)門(mén)用于數(shù)據(jù)挖掘算法和測(cè)試機(jī)器學(xué)習(xí)的公用數(shù)據(jù)庫(kù)。庫(kù)中的數(shù)據(jù)均有確定的屬性類(lèi)別，因此，可以用準(zhǔn)確率和時(shí)間效率來(lái)衡量聚類(lèi)性能的優(yōu)劣。為驗(yàn)證傳統(tǒng)K-means算法和本文改進(jìn)算法的準(zhǔn)確率和時(shí)間效率，不對(duì)測(cè)試數(shù)據(jù)集的數(shù)據(jù)分布做任何人為處理。表1描述了5組數(shù)據(jù)的概要信息，如名稱(chēng)，樣本數(shù)和類(lèi)別數(shù)等。

表1　實(shí)驗(yàn)數(shù)據(jù)集

從表1可以看出，5組數(shù)據(jù)分別由不同的數(shù)量樣本數(shù)和類(lèi)別數(shù)組成，數(shù)據(jù)集的多元性在一定程度上驗(yàn)證了它們?cè)诓煌瑮l件下的性能，保證了實(shí)驗(yàn)結(jié)果具有普遍性。

4.2實(shí)驗(yàn)結(jié)果對(duì)比

1)計(jì)算得到Lung-cancer數(shù)據(jù)集各屬性對(duì)應(yīng)的權(quán)值如圖2所示，Promoter數(shù)據(jù)集各屬性對(duì)應(yīng)的權(quán)值如圖3所示。

圖2　Lung-cancer屬性熵權(quán)值Fig.2　Lung-cancer entropy property values

由圖2和圖3中的屬性熵權(quán)重?cái)?shù)據(jù)得知，每個(gè)屬性的聚類(lèi)作用不同，應(yīng)該對(duì)其加以區(qū)分，傳統(tǒng)的K-means算法忽略了屬性對(duì)聚類(lèi)作用的差異度，致使數(shù)據(jù)對(duì)象的誤判情況頻繁出現(xiàn)，真實(shí)聚類(lèi)結(jié)果與算法的聚類(lèi)結(jié)果之間有一定的差距。

圖3　Promoter屬性熵權(quán)值Fig.3　Promoter entropy property values

2)為了盡可能地避免K-means算法本身固有的缺陷對(duì)實(shí)驗(yàn)結(jié)果造成影響，現(xiàn)對(duì)實(shí)驗(yàn)數(shù)據(jù)做如下預(yù)處理：

由圖4可見(jiàn)，本文改進(jìn)算法對(duì)數(shù)據(jù)樣本數(shù)量較多的Coil2000和Isolet數(shù)據(jù)集取得了較高的聚類(lèi)精度，說(shuō)明改進(jìn)后的算法對(duì)Coil2000和Isolet數(shù)據(jù)集有較好的聚類(lèi)效果。對(duì)數(shù)據(jù)樣本數(shù)量較小的Lung-cancer和Promoter數(shù)據(jù)集，本文改進(jìn)算法精度低于傳統(tǒng)K-means算法和文獻(xiàn)[12]的K-means算法，說(shuō)明當(dāng)數(shù)據(jù)樣本數(shù)量較小時(shí)，改進(jìn)后的算法并不可取。由圖5可見(jiàn)，傳統(tǒng)的K-means算法和文獻(xiàn)[12]的K-means算法較改進(jìn)后的算法在執(zhí)行時(shí)消耗的時(shí)間要多，改進(jìn)后的算法在執(zhí)行效率上較傳統(tǒng)算法有較大的提升，并且數(shù)據(jù)樣本數(shù)量越大，算法執(zhí)行效率就越高。

圖4　3種K-means算法精度對(duì)比結(jié)果Fig.4　Accuracy comparison results of threeK-means algorithms

圖5　3種K-means算法執(zhí)行時(shí)間對(duì)比結(jié)果Fig.5　Execution time comparison results of three K-means algorithms

經(jīng)分析可知，造成上述實(shí)驗(yàn)結(jié)果的原因如下：本文改進(jìn)算法不僅優(yōu)化了初始聚類(lèi)中心，而且還對(duì)學(xué)習(xí)迭代條件進(jìn)行優(yōu)化，同時(shí)還刪除了由信息動(dòng)態(tài)變化而產(chǎn)生的冗余信息從而減少動(dòng)態(tài)聚類(lèi)過(guò)程中的干擾；文獻(xiàn)[12]中的K-means算法僅對(duì)初始聚類(lèi)中心進(jìn)行了優(yōu)化，傳統(tǒng)經(jīng)典K-means算法并沒(méi)做任何改變。這使得本文改進(jìn)算法在聚類(lèi)耗時(shí)上優(yōu)于其余2種作對(duì)比的K-means算法。然而，由于本文改進(jìn)算法在聚類(lèi)過(guò)程中刪除了一些動(dòng)態(tài)信息，這在樣本數(shù)量較少的情況下將損失占比較大的有用信息，聚類(lèi)精度也就較低，甚至低于傳統(tǒng)K-means算法。但是，在樣本數(shù)量較多的情況下?lián)p失的一些有用信息占的比例就十分小， 甚至損失可以忽略不計(jì)，此時(shí)本文改進(jìn)算法優(yōu)勢(shì)就顯現(xiàn)出來(lái)了，聚類(lèi)精度超過(guò)了文獻(xiàn)[12]的K-means算法。

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

K-means算法是一種應(yīng)用廣泛的聚類(lèi)算法，在眾多領(lǐng)域都取得了較好的聚類(lèi)效果，本文針對(duì)初始中心點(diǎn)的問(wèn)題和聚類(lèi)過(guò)程中產(chǎn)生冗余信息的問(wèn)題，提出了一種基于信息熵改進(jìn)的K-means動(dòng)態(tài)聚類(lèi)算法，新算法不僅在選取初始中心點(diǎn)方面有明顯的優(yōu)勢(shì)，而且簡(jiǎn)化了算法的復(fù)雜度，提高了聚類(lèi)的精度。雖然如此，算法固有的缺陷依然對(duì)聚類(lèi)的性能造成了一定的影響，如K-means算法需要事先確定k的個(gè)數(shù)；對(duì)孤立點(diǎn)數(shù)據(jù)很敏感等[11]；目前已有不少學(xué)者針對(duì)這些問(wèn)題進(jìn)行研究。這也是作者下一步要研究的問(wèn)題。

參考文獻(xiàn)：

[1]袁利永,王基一. 一種改進(jìn)的半監(jiān)督K-Means聚類(lèi)算法[J].計(jì)算機(jī)工程與科學(xué),2011,33(6):138-143.

YUAN Liyong,WANG Jiyi. An Improved Semi-Supervised K-Means Clustering Algorithm[J]. Computer Engineering and Science, 2011,33(6):138-143.

[2]傅德勝,周辰.基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用,2011,31(2):432-434.

FU Desheng,ZHOU Chen. Improved K-means algorithm and its implementation based on density[J]. Journal of Computer Applications, 2011,31(2):432-434.

[3]張文明,吳江,袁小蛟.基于密度和最鄰近的K—means文本聚類(lèi)算法[J].計(jì)算機(jī)應(yīng)用,2010,30(7):1933-1935.

ZHANG Wenming,WU Jiang,YUAN Xiaojiao. K-means text clustering algorithm based on density and nearest neighbor[J]. Journal of Computer Applications, 2010,30(7):1933-1935.

[4]劉海峰,劉守生,張學(xué)仁.聚類(lèi)模式下一種優(yōu)化的K-means文本特征選擇[J].計(jì)算機(jī)科學(xué),2011,38(1):195-197.

LIU Haifeng,LIU Shousheng,ZHANG Xueren.Clustering-based Improved K-means Text Feature Selection[J]. Computer Science, 2011,38(1):195-197.

[5]朱顥東,申圳.基于余弦值和K-means的植物葉片識(shí)別方法[J].華中師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,48(5):650-655.

ZHU Haodong,SHEN Zhen. Plant Leaf Identification Method Based on Cosine Theorem and K-means[J].

Journal of central China normal university (natural science edition), 2014,48(5):650-655.

[6]LEE S S, LIN Jachen.An accelerated K-means clustering algorithm selction and erasure rules[J]. Zhejiang University-SCIENCE C(Computers Electronics), 2012,13(10): 761-768.

[7]原福永,張小彩,羅思標(biāo).基于信息熵的精確屬性賦權(quán)K-means聚類(lèi)算法[J].計(jì)算機(jī)應(yīng)用,2011,31(6)1675-1677.

YUAN Fuyong.,ZHANG Xiaocai,LUO Sibiao. Accurate property weighted K-means clustering algorithm based oninformation entropy[J]. Journal of Computer Applications, 2011,31(6)1675-1677.

[8]ORAKOGLU F E, Cevdet Emin Ekinci. Optimization of constitutive parameters of foundation soils K-means clustering analysis[J]. Sciences in Cold and Arid Regions, 2013, 5(5) :0626-0636.

[9]TABAKHI S. An unsupervised feature selection algorithm based on ant colony optimization[J].Engineering Applications of Artificial intelligence, 2014,32: 112-123.

[10] DERNONCOURT, DAVID. Analysis of feature selection stability on high dimension and small sample data[J].Computational Statistics and Data Analysis, 2014,71:681-693.

[11] 吳志媛,錢(qián)雪忠.基于PLSI的標(biāo)簽聚類(lèi)研究[J].計(jì)算機(jī)應(yīng)用研究,2013,30(5):1316-1319.

WU Zhiyuan,QIAN Xuezhong. Tag clustering research based on PLSI[J]. Application Research of Computers, 2013,30(5):1316-1319.

[12] REHAB D, MOHAMMED A R. A novel approach for initializing the spherical K-means clustering algorithm [J]. Simulation Modeling Practice and Theory,2015, 54(5):49-63.

Improved K-means dynamic clustering algorithm based on information entropy

YANG Yumei

(Library of North Sichuan Medical College, Nanchong 637000, P.R. China)

Abstract:Initial cluster centers and redundant information which is generated in clustering process will affect the clustering performance of K-means algorithm. In order to overcome the above mentioned shortcomings, a modified K-means algorithm is proposed. Firstly, it uses information entropy empowering the clustering objects to correct the distance function, and then employs empowerment function to select the optimal initial cluster centers. Subsequently, it decreases algorithm iterations to reduce learning time by setting the threshold value for termination condition of the algorithm.Finally,it reduces interference of dynamic clustering by removing redundant information from clustering process to make the proposed algorithm achieve more accurate and efficient clustering effect. The experimental results show that, when the data sample is larger, compared with the traditional K-means algorithm and other improved K-means algorithm, this improved K-means algorithm has large improvement in accuracy and efficiency.

Keywords：K-means algorithm; information entropy; data mining; dynamic clustering

DOI：10.3979/j.issn.1673-825X.2016.02.018

收稿日期：2015-04-11

修訂日期：2015-12-10通訊作者：楊玉梅yangyumei7810@163.com

中圖分類(lèi)號(hào)：TP301

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-825X(2016)02-0254-06

作者簡(jiǎn)介：

楊玉梅(1978-),女, 四川南充人,碩士,副研究員,主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)、智能信息處理。E-mail: yangyumei7810@163.com。

(編輯：張誠(chéng))