楊玉梅

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

?

基于信息熵改進的K-means動態(tài)聚類算法

楊玉梅

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

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

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

0引言

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

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

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

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

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

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

(1)

定義2同一類別的數(shù)據(jù)對象的質(zhì)心點定義為

(2)

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

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

(3)

2優(yōu)化K-means算法的初始聚類中心點

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

(4)

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

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

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

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

(5)

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

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

(6)

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

(7)

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

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

(8)

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

(9)

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

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

(10)

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

3本文改進算法

3.1K-means算法改進思想

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

3.2本文改進算法描述

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

算法步驟描述如下

輸入：數(shù)據(jù)對象集A，聚類種子初始中心點個數(shù)k1。

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

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

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

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

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

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

Step 7計算每個類的質(zhì)心點。

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

圖1　本文改進算法流程圖Fig.1　Flow chart of the proposed improved algorithm

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

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

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

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

4對比實驗

4.1實驗數(shù)據(jù)集

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

表1　實驗數(shù)據(jù)集

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

4.2實驗結(jié)果對比

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

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

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

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

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

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

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

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

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

5結(jié)束語

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

參考文獻：

[1]袁利永,王基一. 一種改進的半監(jiān)督K-Means聚類算法[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]傅德勝,周辰.基于密度的改進K均值算法及實現(xiàn)[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文本聚類算法[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é)仁.聚類模式下一種優(yōu)化的K-means文本特征選擇[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的植物葉片識別方法[J].華中師范大學(xué)學(xué)報(自然科學(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聚類算法[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] 吳志媛,錢雪忠.基于PLSI的標(biāo)簽聚類研究[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

中圖分類號：TP301

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

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

作者簡介：

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

(編輯：張誠)