秦福高 王文琴 孫悅娟 蔡志玲

(1.常州工學(xué)院計(jì)算機(jī)信息工程學(xué)院，江蘇 常州 213002;2.常州工學(xué)院教務(wù)處，江蘇 常州 213002;3.河海大學(xué)計(jì)算機(jī)及信息工程學(xué)院，江蘇 南京 210098)

基于SA算法的k-means聚類(lèi)算法的改進(jìn)

秦福高1王文琴1孫悅娟2蔡志玲3

(1.常州工學(xué)院計(jì)算機(jī)信息工程學(xué)院，江蘇 常州 213002;2.常州工學(xué)院教務(wù)處，江蘇 常州 213002;3.河海大學(xué)計(jì)算機(jī)及信息工程學(xué)院，江蘇 南京 210098)

傳統(tǒng)的k-means聚類(lèi)算法常陷入局部最優(yōu)，需要事先輸入聚類(lèi)數(shù)，這樣會(huì)造成原有算法失效或聚類(lèi)結(jié)果不準(zhǔn)確。在研究現(xiàn)有聚類(lèi)算法的基礎(chǔ)上，使用ε-最近鄰法剔除孤立點(diǎn)，提出一種改進(jìn)的基于模擬退火算法的、具有自適應(yīng)功能的k-means聚類(lèi)算法。實(shí)驗(yàn)結(jié)果證明，提出的算法是可行的、有效的。

聚類(lèi);k-means算法;模擬退火算法;自適應(yīng)性

0 引言

聚類(lèi)分析是數(shù)據(jù)挖掘中常用的重要技術(shù)，其目的是把數(shù)據(jù)集中的對(duì)象劃分成數(shù)個(gè)有意義的簇，通過(guò)分析各個(gè)簇的結(jié)果，獲得數(shù)據(jù)中所隱藏的、未知的、令人感興趣的信息。目前，聚類(lèi)分析被廣泛應(yīng)用于市場(chǎng)研究、模式識(shí)別等多個(gè)領(lǐng)域。

傳統(tǒng)的k-means聚類(lèi)算法在收斂速度、全局優(yōu)化以及自適應(yīng)等方面都存在著局限性，現(xiàn)在許多研究人員嘗試將啟發(fā)式算法引入聚類(lèi)分析，借助隨機(jī)搜索算法找到全局最優(yōu)解。通過(guò)研究發(fā)現(xiàn)，將啟發(fā)式算法中的SA(Simulated Annealing，模擬退火)算法和k-means算法結(jié)合，可以改進(jìn)聚類(lèi)算法陷入局部最優(yōu)的問(wèn)題，但隨著信息量和數(shù)據(jù)復(fù)雜程度的增加，算法本身能否做到自適應(yīng)，也成為考慮的重點(diǎn)。如果算法在聚類(lèi)過(guò)程中能夠增加自學(xué)習(xí)能力，自動(dòng)實(shí)現(xiàn)分組，則容易得到全局優(yōu)化和算法準(zhǔn)確度的均衡點(diǎn)，于是提出了改進(jìn)的基于SA算法的k-means聚類(lèi)算法。

1 傳統(tǒng)的k-means算法及其缺點(diǎn)

1.1 k-means算法的思想

1.2 k-means算法的步驟

Step1 輸入簇的數(shù)目k、包含n個(gè)數(shù)據(jù)的數(shù)據(jù)集D以及迭代終止條件ε。

Step2 從數(shù)據(jù)集D中任意選擇k個(gè)對(duì)象作為初始中心點(diǎn)。

Step3 根據(jù)剩余對(duì)象到中心點(diǎn)的距離，將其分配到最近的簇，計(jì)算平方誤差值E1。

Step4 重新計(jì)算聚類(lèi)中心點(diǎn)，根據(jù)對(duì)象到各個(gè)中心點(diǎn)的距離，將其分配到最近的簇，計(jì)算平方誤差值E2。

Step5 如果|E1-E2|≤ε，則迭代結(jié)束，輸出k個(gè)簇，否則，E2值賦予E1，轉(zhuǎn)入Step4。

1.3 k-means算法的缺點(diǎn)

k-means算法是基于距離的經(jīng)典的聚類(lèi)算法，其優(yōu)點(diǎn)是簡(jiǎn)單、快速、易懂，對(duì)于密集型數(shù)據(jù)，聚類(lèi)效果好，處理大數(shù)據(jù)集時(shí)，具有相對(duì)可伸縮性和高效性，但是該算法也存在許多缺點(diǎn):

①對(duì)于“噪音”和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類(lèi)數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。

②不適于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇，因?yàn)榇夭捎脤?duì)象的均值作為中心點(diǎn)。

③初始中心點(diǎn)選擇不當(dāng)，容易使算法陷入局部最優(yōu)狀態(tài)。不同的初始值，可能會(huì)導(dǎo)致不同的聚類(lèi)結(jié)果。

④要求用戶(hù)必須事先輸入要生成的簇的數(shù)目k。很多情況下，k值只能靠人為經(jīng)驗(yàn)進(jìn)行設(shè)定，使聚類(lèi)結(jié)果過(guò)于主觀。

2 一種基于SA算法的k-means聚類(lèi)算法

2.1 SA算法

SA算法[2]是基于 Monte Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性，物理退火過(guò)程主要包括加溫過(guò)程、等溫過(guò)程和冷卻過(guò)程。

SA算法類(lèi)似于物理退火過(guò)程，對(duì)給定的初始解S和初始溫度T，從其鄰域中隨機(jī)產(chǎn)生另一個(gè)解S1，計(jì)算△J=J(S1)- J(S)，若△J＜0或者概率P在指定范圍內(nèi)，則接受新解。對(duì)于溫度T的每一個(gè)取值，算法持續(xù)進(jìn)行“產(chǎn)生新解→判斷→接受或舍棄”的迭代過(guò)程，迭代次數(shù)由控制參數(shù)L決定，整個(gè)過(guò)程對(duì)應(yīng)著固體在某一恒定溫度下趨于熱平衡的過(guò)程，最終溫度趨向于穩(wěn)定值，對(duì)應(yīng)著問(wèn)題的最終解。

2.2 SA算法與k-means算法的結(jié)合

傳統(tǒng)k-means算法的終止條件是目標(biāo)函數(shù)值不再改變，如果初始中心點(diǎn)選在局部最小值周?chē)?，就可能陷入局部最?yōu)。SA算法的終止條件是聚類(lèi)中心點(diǎn)不再變化，算法與初始中心點(diǎn)的選擇關(guān)系不大，同時(shí)算法能以概率P進(jìn)行隨機(jī)搜索，避免局部最優(yōu)，最終能以概率1收斂到全局最優(yōu)值。Selim等人[3]首先將模擬退火的全局尋優(yōu)思想應(yīng)用到聚類(lèi)領(lǐng)域，于是后人常常將模擬退火機(jī)制引入聚類(lèi)分析，將其與k-means算法結(jié)合，利用SA算法的全局尋優(yōu)能力來(lái)彌補(bǔ)k-means算法容易陷入局部最優(yōu)的不足。

基于SA算法的k-means聚類(lèi)算法的處理過(guò)程:將k-means算法聚類(lèi)結(jié)果作為初始解，初始目標(biāo)函數(shù)值作為初始溫度T，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄新解”的迭代過(guò)程，并逐步降低T值，算法終止時(shí)當(dāng)前解為近似最優(yōu)解。這種算法開(kāi)始時(shí)以最快的速度找到相對(duì)較優(yōu)的區(qū)域，然后進(jìn)行更精確的搜索，最終找到全局最優(yōu)解。

將SA算法與k-means算法進(jìn)行結(jié)合，確實(shí)可以改進(jìn)聚類(lèi)算法陷入局部最優(yōu)的問(wèn)題，但是隨著信息量和數(shù)據(jù)復(fù)雜程度的增加，算法能否做到自適應(yīng)，也成為評(píng)判算法優(yōu)劣的標(biāo)準(zhǔn)。如果算法在聚類(lèi)過(guò)程中能夠進(jìn)行孤立點(diǎn)檢測(cè)、初始聚類(lèi)個(gè)數(shù)及中心點(diǎn)確定，那么在實(shí)現(xiàn)全局優(yōu)化聚類(lèi)的同時(shí)，可以一并提高算法的自適應(yīng)性，所以此算法有待進(jìn)一步改進(jìn)。

3 改進(jìn)的基于SA算法的k-means聚類(lèi)算法

3.1 ε-最近鄰法剔除孤立點(diǎn)

自適應(yīng)算法在聚類(lèi)前并不知道初始中心點(diǎn)，因此無(wú)法用基于距離的方法檢測(cè)孤立點(diǎn)，必須用基于密度的方法檢測(cè)孤立點(diǎn)。結(jié)合k-最近鄰算法和基于密度的聚類(lèi)算法，提出ε-最近鄰法。

ε-最近鄰法，就是檢查給定對(duì)象的半徑領(lǐng)域中的近鄰數(shù)目，若近鄰數(shù)大于給定閾值，則該對(duì)象稱(chēng)為核心對(duì)象，否則稱(chēng)為孤立點(diǎn)。處理時(shí)將核心對(duì)象標(biāo)志為正常數(shù)據(jù)，孤立點(diǎn)標(biāo)志為異常點(diǎn)，異常點(diǎn)不再對(duì)其進(jìn)行聚類(lèi)。

3.2 自適應(yīng)思想

基于SA算法的k-means聚類(lèi)方法在聚類(lèi)分析時(shí)需要用戶(hù)輸入聚類(lèi)的數(shù)目，主觀性太強(qiáng)，且聚類(lèi)結(jié)果對(duì)輸入的參數(shù)敏感，這使得聚類(lèi)的質(zhì)量難以保證。為了提高算法的自適應(yīng)性，自動(dòng)對(duì)相似的數(shù)據(jù)進(jìn)行聚類(lèi)，確定聚類(lèi)數(shù)目，引入蟻群算法。

將待聚類(lèi)的n個(gè)數(shù)據(jù)隨機(jī)地散布到空間中，然后將m個(gè)螞蟻分布到這個(gè)空間內(nèi)，并以概率P隨機(jī)移動(dòng)，當(dāng)一只螞蟻遇到一個(gè)待聚類(lèi)數(shù)據(jù)xi時(shí)便將其拾起并繼續(xù)隨機(jī)運(yùn)動(dòng)，若運(yùn)動(dòng)路徑附近的數(shù)據(jù)xj與背負(fù)的數(shù)據(jù)的相似性d(xi，xj)高于設(shè)定的閾值ε，則將其放置在該位置，然后繼續(xù)移動(dòng)，重復(fù)上述數(shù)據(jù)搬運(yùn)過(guò)程。

3.3 數(shù)據(jù)二元化

對(duì)于正常數(shù)據(jù) xi和xj，若兩者之間的距離d(xi，xj)大于給定閾值 L，則 d(xi，xj)標(biāo)為0，否則標(biāo)為1，建立對(duì)象間的二元矩陣。

3.4 算法的步驟

Step1 設(shè)定閾值ε，L，N和概率P。

Step2 用ε-最近鄰法剔除異常點(diǎn)，若對(duì)象的近鄰數(shù)大于給定閾值N，則標(biāo)為正常數(shù)據(jù)，若小于N，則標(biāo)為異常點(diǎn)。

Step3 對(duì)數(shù)據(jù)進(jìn)行二元化處理，若正常數(shù)據(jù)xi和xj之間的距離d(xi，xj)大于給定閾值L，則標(biāo)為0，否則標(biāo)為1，建立對(duì)象間的二元矩陣。

Step4 預(yù)聚類(lèi)，任選一個(gè)對(duì)象xi，考察二元化矩陣，將標(biāo)為1的對(duì)象和xi歸為一類(lèi)，依次進(jìn)行直到遇到0為止，最終確定聚類(lèi)個(gè)數(shù)k。

Step5 對(duì)劃分的初始類(lèi)，計(jì)算每個(gè)類(lèi)中對(duì)象的均值作為初始中心點(diǎn)。

Step6 對(duì)類(lèi)中的非中心點(diǎn)，基于模擬退火依概率P搜索法，用k-means算法將其賦給距離最近的類(lèi)，并更新中心點(diǎn)。

Step7 比較2次聚類(lèi)中心有無(wú)變化，若無(wú)變化，轉(zhuǎn)Step8，否則轉(zhuǎn)Step6。

Step8 終止算法，計(jì)算最終類(lèi)的相似度與相異度比值，即算法緊致度，輸出聚類(lèi)數(shù)目、聚類(lèi)中心點(diǎn)、算法緊致度。

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

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

實(shí)驗(yàn)使用的數(shù)據(jù)分析平臺(tái)是SAS系統(tǒng)，編程環(huán)境是VS6.0，通過(guò)同一個(gè)有50個(gè)對(duì)象的測(cè)試數(shù)據(jù)集分別對(duì)傳統(tǒng)的k-means算法、基于SA算法的k-means算法、基于蟻群算法的k-means算法以及本文提出的改進(jìn)的基于SA算法的k-means算法進(jìn)行實(shí)驗(yàn)，共采集10組數(shù)據(jù)，如表1所示。

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

根據(jù)表1的實(shí)驗(yàn)數(shù)據(jù)，在測(cè)試數(shù)據(jù)集相同的情況下，與其他3種算法相比，綜合來(lái)看，本文提出的算法迭代次數(shù)較少，有明顯的優(yōu)勢(shì)，說(shuō)明收斂速度快，算法性能好;新算法的緊致度較好，算法整體上穩(wěn)定而準(zhǔn)確;新算法產(chǎn)生的類(lèi)數(shù)目與基于蟻群算法的k-means算法基本一致，與另外2種算法相比，聚類(lèi)的數(shù)目相差不大，自適應(yīng)效果較好。

第3組中新算法的緊致度出現(xiàn)了意外，通過(guò)分析發(fā)現(xiàn)測(cè)試的數(shù)據(jù)對(duì)象空間分布極不規(guī)律，有的類(lèi)呈非球狀簇，這也證明了基于距離的聚類(lèi)算法在處理非球狀簇時(shí)確實(shí)存在困難。

表1 4種算法實(shí)驗(yàn)數(shù)據(jù)

5 結(jié)語(yǔ)

從實(shí)驗(yàn)結(jié)果看，改進(jìn)的基于SA算法的 kmeans算法與傳統(tǒng)的k-means聚類(lèi)算法相比，改變了傳統(tǒng)的k-means聚類(lèi)算法在收斂速度、全局優(yōu)化以及自適應(yīng)等方面存在的不足。該算法在實(shí)現(xiàn)全局優(yōu)化聚類(lèi)的同時(shí)，較好地解決了孤立點(diǎn)檢測(cè)、初始聚類(lèi)個(gè)數(shù)及中心點(diǎn)確定的問(wèn)題，提高了算法的自適應(yīng)性。

[1]Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京:機(jī)械工業(yè)出版社，2007:203-204.

[2]Metropolis N，Rosenbluth A，Rosenbluth M，et al.Equation of State Calculations by Fast Computing Machines[J].Journal of Chemical Physics，1953，21(6):1087 -1092.

[3]Selim S Z，Alsultan K.A Simulated Annealing Algorithm for the Clustering Problem[J].Patterm Recognition，1991，24(10):1003-1008.

Improvement of k-means Clustering Algorithm Based on Simulated Annealing Algorithm

QIN Fu-gao1WANG Wen-qin1SUN Yue-juan2CAI Zhi-ling3

(1.School of Computer＆ Information Engineering，Changzhou Institute of Technology，Changzhou 213002;
2.Teaching Affairs Office，Changzhou Institute of Technology，Changzhou 213002;
3.College of Computer and Information Engineering，Hohai University，Nanjing 210098)

The problem of traditional k-means clustering algorithm is that it often falls into local optimum，and needs to input clustering parameters ahead of time，which causes some disabled or inaccurate clustering results.On the basis of current clustering algorithm research，this paper proposes a kind of improved k-means clustering algorithm based on simulated annealing.The algorithm is adaptive and may remove the outliers by ε-nearest neighbor method.And its feasibility and effectiveness are proved by the experiment results.

clustering;k-means algorithm;simulated annealing algorithm;adaptability

TP311.13

A

1671-0436(2011)03/04-0021-04

2011-05-27

秦福高(1973— )，男，碩士，講師。

責(zé)任編輯:唐海燕