K－means聚類中心的魯棒優(yōu)化算法

羅 倩

（北京信息科技大學(xué) 信息與通信工程學(xué)院，北京100192）

0 引 言

由于K－means方法［1］的初始聚類中心是隨機(jī)選擇的，不同的初始聚類中心可能會(huì)得到不同的聚類結(jié)果，因此不能獲得最佳聚類效果。為了克服K－means算法的局限性，不少學(xué)者研究了優(yōu)化算法，如通過中值預(yù)測［2］、KD樹［3，4］、線性判別分析［5］、變異精密搜索的蜂群算法［6］以及其它改進(jìn)算法［7－9］對聚類簇中心進(jìn)行優(yōu)化并改善K－means算法分類結(jié)果，取得了一定的效果，但是算法的魯棒性有待進(jìn)一步提高。研究聚類中心的優(yōu)化問題、獲得有效、準(zhǔn)確和 穩(wěn) 定 的 聚 類 結(jié) 果 具 有 重 要 意 義［10－15］。

本文提出基于鄰域數(shù)據(jù)距離加權(quán)的聚類中心優(yōu)化方法，提高了算法的準(zhǔn)確性和魯棒性，且不需要大量計(jì)算。

1 K－means算法的基本思想

K－means分析方法是廣泛使用的聚類算法。算法需要事先依據(jù)某種評(píng)價(jià)函數(shù)確定最優(yōu)類別數(shù)K，確保每一類中數(shù)據(jù)的相似度較高，而各類之間數(shù)據(jù)的相似度較低。Kmeans分類算法要解決的問題是將N 個(gè)數(shù)據(jù)樣本｛yi｝Ni＝1（每個(gè)數(shù)據(jù)樣本的維數(shù)是n維）分類到K 個(gè)聚類之中，算法主要包括兩個(gè)過程：一是根據(jù)某種準(zhǔn)則把每個(gè)樣本分配給最近的聚類中心；二是更新各個(gè)聚類中心，使其最佳地適應(yīng)樣本。K－means算法的具體步驟是：①采用某種評(píng)價(jià)函數(shù)確定分類數(shù)K，并隨機(jī)初始化K 個(gè)聚類中心。②計(jì)算每個(gè)數(shù)據(jù)樣本與每一個(gè)聚類中心的距離，距離采用2－范數(shù)距離計(jì)算，把與類中心距離最小的樣本劃分到該類中。③對上述每類樣本計(jì)算平均值，采用平均值更新聚類中心。④判斷迭代是否終止，否則返回第②步繼續(xù)執(zhí)行。

K－means算法結(jié)果對初始聚類中心具有依賴性，導(dǎo)致聚類結(jié)果不穩(wěn)定，按照距離量度可能會(huì)將兩類的中心處收斂為同一個(gè)聚類中心，造成分類錯(cuò)誤，且算法本身在收斂時(shí)無法更正，如圖1所示。圖1 （a）用3種不同符號(hào)表示3個(gè)不同的樣本數(shù)據(jù)類，采用K－means算法進(jìn)行數(shù)據(jù)聚類時(shí)，可能會(huì)產(chǎn)生如圖1 （b）的聚類結(jié)果，圖中米字符號(hào)表示各類的聚類中心。圖1 （b）中，上方的數(shù)據(jù)簇應(yīng)屬于同一個(gè)數(shù)據(jù)類，但是K－means算法卻將其分為兩類，分別用不同符號(hào)表示；圖1 （b）的下方，原始數(shù)據(jù)應(yīng)該是兩個(gè)數(shù)據(jù)類，卻聚類為同一類。因此K－means算法聚類結(jié)果不穩(wěn)定，可能會(huì)造成分類錯(cuò)誤。

圖1 原始數(shù)據(jù)分類情況和K－means算法聚類結(jié)果

聚類是實(shí)現(xiàn)數(shù)據(jù)稀疏表示、數(shù)據(jù)分類、信息抽取、信號(hào)壓縮和數(shù)據(jù)挖掘等應(yīng)用的基礎(chǔ)，因此準(zhǔn)確、可靠和穩(wěn)定的聚類方法對這些應(yīng)用具有現(xiàn)實(shí)意義。本文從樣本的各維數(shù)據(jù)分析出發(fā)，提出了基于鄰域數(shù)據(jù)距離加權(quán)、采用數(shù)據(jù)密度約束值進(jìn)行聚類更新的優(yōu)化算法。

2 基于鄰域數(shù)據(jù)距離加權(quán)的K－means聚類算法優(yōu)化設(shè)計(jì)

圖1 （b）的下方，K－means算法把兩個(gè)數(shù)據(jù)類聚類為同一類，其聚類中心不處于數(shù)據(jù)密集處。圖2 示出了圖1所用數(shù)據(jù)樣本各維直方圖與上述K－means算法收斂聚類中心之間關(guān)系的分析結(jié)果。

圖2 樣本中各維數(shù)據(jù)的直方圖與聚類中心的關(guān)系

對樣本的各維數(shù)據(jù)進(jìn)行分析，可以看到，這種Kmeans聚類結(jié)果的出現(xiàn)是由于其收斂的聚類中心并不位于數(shù)據(jù)密集之處，而是位于兩個(gè)數(shù)據(jù)簇之間，導(dǎo)致分類錯(cuò)誤。因此，本文提出采用數(shù)據(jù)鄰域距離加權(quán)的數(shù)據(jù)樣本密度約束值法優(yōu)化聚類效果的算法，確定聚類中心是否處于數(shù)據(jù)密集處，這樣可以很好地解決K－means算法的問題，使分類結(jié)果更準(zhǔn)確。

2.1 采用鄰域數(shù)據(jù)距離加權(quán)的密度約束值判斷聚類效果

本算法采用K－means方法對數(shù)據(jù)進(jìn)行聚類分析，并計(jì)算數(shù)據(jù)各維的直方圖，采用鄰域數(shù)據(jù)距離加權(quán)的密度約束值判斷聚類結(jié)果，即對直方圖計(jì)算每一分析點(diǎn)的相鄰點(diǎn)距離加權(quán)和，獲得該點(diǎn)的密度約束值，建立適當(dāng)?shù)拈T限，只要任意一個(gè)收斂的聚類中心的任一維低于密度約束值門限，就判斷聚類結(jié)果為非最優(yōu)，并重新進(jìn)行分類迭代。

對數(shù)據(jù)進(jìn)行直方圖分析后，用直方圖數(shù)據(jù)進(jìn)行密度約束值的計(jì)算相比采用全部數(shù)據(jù)計(jì)算可以更節(jié)省計(jì)算時(shí)間，并能提高準(zhǔn)確率，但在做直方圖運(yùn)算時(shí)，應(yīng)根據(jù)數(shù)據(jù)范圍選擇合適的組距。

本文提出算法的具體計(jì)算過程為：

（1）給定合適的組距，計(jì)算數(shù)據(jù)每一維的直方圖。

（2）確定數(shù)據(jù)分布范圍，計(jì)算每一值點(diǎn)的鄰域數(shù)據(jù)距離加權(quán)值，得到數(shù)據(jù)點(diǎn)的密度約束值

式中：j——數(shù)據(jù)維數(shù)的標(biāo)號(hào)，qj（i）——第j維第i 個(gè)直方圖統(tǒng)計(jì)點(diǎn)的鄰域距離加權(quán)值，αl，j——距離加權(quán)系數(shù)，l——鄰域距離標(biāo)號(hào)，由m 確定所選取的鄰域的大小，hj（l）——鄰域中各點(diǎn)的直方圖統(tǒng)計(jì)值。

（3）當(dāng)收斂的聚類中心的某一維位置ck，j所對應(yīng)的密度約束值小于某個(gè)給定的閾值Tj時(shí)，即當(dāng)

則判定為本次聚類不準(zhǔn)確，并用2.2 節(jié)方法重新確定聚類中心，并重新分類。

式 （2）中，k為數(shù)據(jù)的類號(hào)，閾值Tj取

式中：β——閾值系數(shù)。這里，只要任意一個(gè)j （j＝1，…，n）或k（k＝1，…，K）滿足式 （2），則重新迭代。

圖3示出了圖1中的數(shù)據(jù)及前述收斂聚類中心的鄰域數(shù)據(jù)距離加權(quán)分析結(jié)果。可以看出，此結(jié)果滿足式 （2），造成這種K－means聚類結(jié)果不準(zhǔn)確。

圖3 鄰域數(shù)據(jù)距離加權(quán)的密度約束值分析結(jié)果

2.2 聚類中心的優(yōu)化方法

在重新聚類時(shí)，仍采用K－means聚類算法，但是不再隨機(jī)選取聚類中心，而是對于上述聚類中心中某一維低于閾值的中心，用與錯(cuò)誤聚類中心距離最近的、達(dá)到最大密度約束值的數(shù)據(jù)位置更新這個(gè)類中心，作為這個(gè)類的初始化中心，其它類的聚類中心仍采用已收斂的聚類中心。這里的距離采用2－范數(shù)距離。

再次迭代收斂條件為兩次迭代后的聚類中心沒有顯著變化。具體為：當(dāng)滿足式 （4）時(shí)，則迭代終止

這里x2表示x的2－范數(shù)，ε為一個(gè)很小的正數(shù)，E 為兩次相鄰迭代間聚類中心誤差矩陣

式中：Cn（m）——第m 次迭代歸一化的聚類中心矩陣

式中：m——迭代次數(shù)，C（m）——第m 次迭代所得到的各類聚類中心構(gòu)成的K ×n 維矩陣，ck，n（m）——該矩陣中的各元素。

3 實(shí)驗(yàn)與分析

3.1 仿真實(shí)驗(yàn)

首先采用仿真實(shí)驗(yàn)。隨機(jī)產(chǎn)生具有不同均值、方差的3類高斯分布數(shù)據(jù)，數(shù)據(jù)樣本維數(shù)為三維，并隨機(jī)產(chǎn)生初始聚類中心，圖4 （a）給出了3類仿真數(shù)據(jù)的情況。

采用本文的算法得到的聚類結(jié)果在圖4 （b）和圖5中顯示?？梢钥吹奖疚乃惴軌驕?zhǔn)確確定各聚類中心，并獲得準(zhǔn)確的聚類結(jié)果。圖5顯示出收斂的聚類中心的各維都是分布在數(shù)據(jù)密度約束值相對較大的地方。

圖4 原始分類數(shù)據(jù)情況和本文算法聚類結(jié)果

3.2 標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)

本部分采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集 （ftp：／／ftp.ics.uci.edu／pub／machine－learning－databases／）中的Iris、Wine和Abalone＿Data這3種數(shù)據(jù)集，將本文算法與K－means算法進(jìn)行比較實(shí)驗(yàn)。

Iris數(shù)據(jù)包含3類，每類有50個(gè)樣本，每個(gè)樣本有4個(gè)屬性，共150 個(gè)數(shù)據(jù)；Wine數(shù)據(jù)集是13 維數(shù)據(jù)集，共178個(gè)樣本數(shù)據(jù)，分為3類；Abalone＿Data數(shù)據(jù)集上含有4177個(gè)數(shù)據(jù)，每個(gè)樣本維數(shù)是8維，分為3類。

3種數(shù)據(jù)集的特征見表1。

圖5 仿真數(shù)據(jù)的密度約束值與各聚類中心關(guān)系

表1 Iris、Wine和Abalone＿Data數(shù)據(jù)集特征

下面分別用K－means算法和本文算法對3種標(biāo)準(zhǔn)數(shù)據(jù)運(yùn)行100次，K－means算法中每次運(yùn)行均采用隨機(jī)的初始聚類中心，分析兩種算法的聚類樣本個(gè)數(shù)、聚類中心、平均準(zhǔn)確率、平均代價(jià)函數(shù)和附加迭代次數(shù)等。

首先使用K－means算法和本文算法在Iris數(shù)據(jù)集上進(jìn)行測試，聚類結(jié)果見表2。

其中，平均準(zhǔn)確率為每次收斂的準(zhǔn)確率與該種收斂出現(xiàn)頻次的加權(quán)和，即第i種聚類結(jié)果的準(zhǔn)確率 （7）

表2 采用Iris數(shù)據(jù)集算法結(jié)果對比

這里，fi為在100 次運(yùn)行中，第i種聚類結(jié)果出現(xiàn)的頻次。

各個(gè)聚類的代價(jià)函數(shù)為所有樣本到各自聚類中心的2－范數(shù)距離的平均值，即

式中：Objk——第k類聚類的代價(jià)函數(shù)，Ck——第k類的聚類中心，datak，s——第k類、第s類樣本，Nk——第k類的樣本數(shù)。各聚類總的代價(jià)函數(shù)為

由于K－means方法收斂后聚類結(jié)果不是唯一的，所以定義平均代價(jià)函數(shù)為

式中：Obj（i）——第i種聚類結(jié)果的代價(jià)函數(shù)。

由于Iris數(shù)據(jù)集是4維數(shù)據(jù)，不易顯示，本文選取其第2－4維數(shù)據(jù)進(jìn)行顯示。圖6 （a）用不同符號(hào)給出了Iris數(shù)據(jù)的分類情況。圖6 （b）給出了本文算法對Iris標(biāo)準(zhǔn)數(shù)據(jù)集的聚類中心和聚類結(jié)果。圖7是聚類中心各維的數(shù)據(jù)密度約束值情況。

圖6 本文算法應(yīng)用于Iris標(biāo)準(zhǔn)數(shù)據(jù)集聚類結(jié)果

從表2和圖6～圖7中可以看出，對于Iris標(biāo)準(zhǔn)數(shù)據(jù)集，K－means算法聚類收斂結(jié)果不是唯一的，平均準(zhǔn)確率較低，代價(jià)函數(shù)較高；本文算法聚類結(jié)果唯一，并與Iris數(shù)據(jù)的實(shí)際中心非常接近，且平均準(zhǔn)確率較高，代價(jià)函數(shù)較低。此外，采用本文的收斂準(zhǔn)則，附加迭代次數(shù)大大減少。

以上實(shí)驗(yàn)說明，本文算法對Iris數(shù)據(jù)是有效的和具有魯棒性的，算法運(yùn)算量較小。

對Wine和Abalone＿Data數(shù)據(jù)集的分析分別見表3和表4?？梢钥闯?，對于這兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集本文算法相比于K－means分析方法同樣獲得了較好的平均準(zhǔn)確率和代價(jià)函數(shù)，聚類效果具有較高的魯棒性。

圖7 本文算法對Iris數(shù)據(jù)集各聚類中心各維的數(shù)據(jù)數(shù)據(jù)密度約束值

本節(jié)的仿真實(shí)驗(yàn)和對各標(biāo)準(zhǔn)數(shù)據(jù)集的分析結(jié)果說明Kmeans算法由于其初始聚類中心是隨機(jī)選取的，算法穩(wěn)定性差，聚類質(zhì)量差；本文提出的算法由于采用數(shù)據(jù)鄰域距離加權(quán)約束分類判決和聚類中心的更新，可以有效地將聚類中心控制在數(shù)據(jù)密度較高的地方，所以算法可以得到準(zhǔn)確和魯棒的聚類效果，而且，按照本文算法的收斂準(zhǔn)則，算法額外迭代次數(shù)較低，不影響聚類分析的運(yùn)算時(shí)間，本文算法對K－means算法獲得了較有效、魯棒的優(yōu)化性能。

表3 采用Wine標(biāo)準(zhǔn)數(shù)據(jù)集的算法結(jié)果對比

表4 采用Abalone＿Data數(shù)據(jù)集的算法對比

4 結(jié)束語

K－means算法作為如圖像分割、信號(hào)的稀疏表示等諸多應(yīng)用的預(yù)處理算法，對其準(zhǔn)確性和魯棒性的要求較高。但是由于K－means分析方法對初始聚類中心的選擇非常敏感，造成分類結(jié)果的不穩(wěn)定，錯(cuò)誤分類會(huì)造成以此算法為基礎(chǔ)的后續(xù)處理的錯(cuò)誤，因此建立高可靠性和魯棒性聚類算法非常重要。本文提出了基于鄰域數(shù)據(jù)距離加權(quán)、依據(jù)數(shù)據(jù)密度約束聚類中心更新的魯棒算法，在仿真數(shù)據(jù)以及Iris、Wine和Abalone＿Data標(biāo)準(zhǔn)數(shù)據(jù)集上對K－means算法和本文算法進(jìn)行了對比分析。實(shí)驗(yàn)結(jié)果表明，該算法優(yōu)于K－means聚類方法，具有魯棒聚類效果，可以提高聚類質(zhì)量，可以為后續(xù)的數(shù)據(jù)挖掘、模式識(shí)別、信息檢索和信號(hào)的稀疏表示等處理奠定良好的基礎(chǔ)。

［1］SU Qinghua，HU Zhongbo.K－means clustering algorithm based on differential evolution ［J］.Journal of Wuhan University of Technology，2010，32 （1）：187－191 （in Chinese）.［蘇清華，胡中波.基于差分演化的K－均值聚類算法 ［J］.武漢理工大學(xué)學(xué)報(bào)，2010，32 （1）：187－191.］

［2］Suresh L，Jay B Simha，Rajappa Velur.Seeding cluster centers of K－means clustering through median projection ［C］／／International Conference on Complex，Intelligent and Software Intensive Systems，IEEE，2010：15－18.

［3］Siti Noraini Sulaiman，Khairul Azman Ahmad，Nor Ashidi Mat Isa，et al.Performance of hybrid radial basis function network：Adaptive fuzzy K－means versus moving K－means clustering as centre positioning algorithms on cervical cell pre－cancerous stage classification ［C］／／IEEE International Conference on Control System，Computing and Engineering，IEEE，2012：607－611.

［4］Pahala Sirait，Aniati Murni Arymurthy.Cluster centres determination based on KD tree in K－means clustering for area change detection［C］／／International Conference on Distributed Frameworks for Multimedia Applications，IEEE，2010：1－7.

［5］Zhang Yuhua，Wang Kun，Lu Heng，et al.An improved Kmeans clustering algorithm over data accumulation in delay tolerant mobile sensor network ［C］／／8th International Conference on Communications and Networking in China，IEEE，2013：34－39.

［6］LUO Ke，LI Lian，ZHOU Boxiang.Artificial bee colony rough clustering algorithm based on mutative precision search［J］.Control and Decision，2014，29 （5）：838－842 （in Chinese）.［羅可，李蓮，周博翔.基于變異精密搜索的蜂群聚類算法 ［J］.控制與決策，2014，29 （5）：838－842.］

［7］WANG Zhong，LIU Guiquan，CHEN Enhong.A K－means algorithm based on optimized initial center points ［J］.Pattern Recognition and Artificial Intelligence，2009，22 （2）：299－304 （in Chinese）. ［汪中，劉貴全，陳恩紅.一種優(yōu)化初始中心點(diǎn)的K－means算法 ［J］.模式識(shí)別與人工智能，2009，22 （2）：299－304.］

［8］Jiang Dongyang，Zheng Wei，Lin Xiaoqing.Research on selection of initial center points based on improved K－means algorithm ［C］／／2nd International Conference on Computer Science and Network Technology，IEEE，2012：1146－1149.

［9］Liao Qing，Yang Fan，Zhao Jingming.An improved parallel K－means clustering algorithm with map reduce ［C］／／Proceedings of 15th IEEE International Conference on Communication Technology，IEEE，2013：764－768.

［10］Xie Juanying，Jiang Shuai.A simple and fast algorithm for global K－means clustering ［C］／／2nd International Workshop on Education Technology and Computer Science，IEEE，2010：36－40.

［11］JI Suqin，SHI Hongbo.Optimized K－means clustering algorithm for massive data［J］.Computer Engineering and Applications，2014，50 （14）：143－147 （in Chinese）. ［冀素琴，石洪波.面向海量數(shù)據(jù)的K－means聚類優(yōu)化算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50 （14）：143－147.］

［12］YU Haitao，LI Zi，YAO Nianmin.Research on optimization method for K－means clustering algorithm ［J］.Journal of Chinese Computer Systems，2012，33 （10）：2273－2277 （in Chinese）.［于海濤，李梓，姚念民.K－means聚類算法優(yōu)化方法的研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2012，33 （10）：2273－2277.］

［13］FENG Bo，HAO Wenning，CHEN Gang，et al.Optimization to K－means initial cluster centers ［J］.Computer Engineering and Applications，2013，49 （14）：182－185 （in Chinese）. ［馮波，郝文寧，陳剛，等.K－means算法初始聚類中心選擇的優(yōu)化 ［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49 （14）：182－185.］

［14］YANG Mingchuan，LV Xuebin，ZHOU Qunbiao.Image segmentation algorithm based on incomplete K－means clustering and category optimization ［J］.Journal of Computer Applications，2012，32 （1）：248－251 （in Chinese）. ［楊明川，呂學(xué)斌，周群彪.不完全K－means聚類與分類優(yōu)化結(jié)合的圖像分割算法 ［J］.計(jì)算機(jī)應(yīng)用，2012，32 （1）：248－251.］

［15］SHI Yabing，HUANG Yu，QIN Xiao，et al.K－means clustering algorithm based on a novel approach for improved initial seeds［J］.Journal of Guangxi Normal University （Natural Science Edition），2013，31 （4）：33－40 （in Chinese）.［石亞冰，黃予，覃曉，等.基于優(yōu)化初始種子新策略的K－Means聚類算法 ［J］.廣西師范大學(xué)學(xué)報(bào) （自然科學(xué)版），2013，31（4）：33－40.］