一種改進(jìn)的K-means聚類(lèi)算法*

周愛(ài)武，崔丹丹，肖 云

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039)

聚類(lèi)分析[1](clustering)是數(shù)據(jù)挖掘研究的重要領(lǐng)域，借助聚類(lèi)分析將大量的數(shù)據(jù)對(duì)象聚成不同的類(lèi)簇，使不同簇之間的相似度低，簇內(nèi)的相似度高，它是一種無(wú)監(jiān)督的學(xué)習(xí)算法。為了實(shí)現(xiàn)對(duì)數(shù)據(jù)對(duì)象的聚類(lèi)，人們提出了不同的聚類(lèi)算法。聚類(lèi)算法主要分成基于劃分、基于密度、基于分層、基于網(wǎng)格和基于模型的五大類(lèi)[2]。K-means(均值)聚類(lèi)算法是典型的基于劃分的聚類(lèi)算法，同時(shí)也是應(yīng)用最廣泛的一種聚類(lèi)算法。K-means聚類(lèi)算法[3]主要針對(duì)處理大數(shù)據(jù)集，不但處理快速簡(jiǎn)單，而且算法具有高效性以及可伸縮性。但是K-means聚類(lèi)算法存在K值需要事先指定、隨機(jī)選擇初始聚類(lèi)中心等的局限性。人們針對(duì)K-means聚類(lèi)算法的這些局限性提出了不同的改進(jìn)算法。劉濤等人[4]提出了基于半監(jiān)督學(xué)習(xí)的K-means聚類(lèi)算法的研究，用粒子群算法以及迭代搜索的思想找到優(yōu)質(zhì)的聚類(lèi)中心進(jìn)行聚類(lèi)；李飛等人[5]提出了基于遺傳算法的全局搜索能力來(lái)解決初始聚類(lèi)中心選擇的敏感性問(wèn)題。

K-means聚類(lèi)算法由于初始聚類(lèi)中心是隨機(jī)選擇的，容易造成算法會(huì)陷入局部最優(yōu)解甚至是無(wú)解的情況，而聚類(lèi)結(jié)果的好壞直接取決于初始聚類(lèi)中心的選擇。因此初始聚類(lèi)中心的選擇十分重要。本文主要針對(duì)隨機(jī)選擇初始聚類(lèi)中心這一缺點(diǎn)，提出了一種新的改進(jìn)的K-means聚類(lèi)算法。

1 傳統(tǒng)的K-means聚類(lèi)算法

K-means聚類(lèi)算法是解決聚類(lèi)問(wèn)題的一種經(jīng)典算法，該算法具有簡(jiǎn)單、快速并且能夠有效處理大數(shù)據(jù)集的特點(diǎn)。K-means聚類(lèi)算法首先從n個(gè)數(shù)據(jù)對(duì)象中任意選取k個(gè)對(duì)象作為初始聚類(lèi)中心；而對(duì)于所剩下的其他對(duì)象，則根據(jù)它們與這些聚類(lèi)中心的相似度(距離)，分別將它們分配給與其最相似的類(lèi)簇；然后計(jì)算該類(lèi)簇中所有對(duì)象的均值；不斷重復(fù)這一過(guò)程直到標(biāo)準(zhǔn)準(zhǔn)則函數(shù)開(kāi)始收斂為止。具體步驟如下[6]：

輸入：k，data[n]；輸出：k個(gè)簇的集合，滿足聚類(lèi)準(zhǔn)則函數(shù)收斂。

(1)任意選擇k個(gè)對(duì)象作為初始中心點(diǎn)，例如c[0]=data[0]，…c[k-1]=data[k-1]；

(2)根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象指派給最相似的簇；

(3)更新簇均值，即計(jì)算每個(gè)簇中對(duì)象的均值；

(4)重復(fù)步驟(2)和步驟(3)，直到準(zhǔn)則函數(shù)不再發(fā)生變化。

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

2.1 相關(guān)定義

定義1 數(shù)據(jù)對(duì)象 xi(xi1，xi2，…，xip)T、xj(xj1，xj2，… ，xjp)T之間的距離用歐氏距離d(xi，xj)表示如下：

定義2 二維數(shù)據(jù)樣本點(diǎn)中心 center(xi，xj)：

2.2 改進(jìn)算法的思想及基本步驟

影響K-means聚類(lèi)算法性能的主要原因有：樣本集中孤立點(diǎn)以及隨機(jī)選擇初始聚類(lèi)中心而造成聚類(lèi)結(jié)果的不穩(wěn)定以及不準(zhǔn)確。針對(duì)K-means的這種不足，本文提出了一種新的思想：首先將樣本點(diǎn)中影響聚類(lèi)結(jié)果的孤立點(diǎn)去除，然后利用坐標(biāo)平移的思想來(lái)確定初始聚類(lèi)中心，利用K-means算法進(jìn)行聚類(lèi)，最終得到可以滿足平方誤差準(zhǔn)則函數(shù)收斂的聚類(lèi)結(jié)果。

算法具體步驟：

首先排除樣本點(diǎn)中的孤立點(diǎn)：

(1)輸入樣本點(diǎn)，利用unique函數(shù)排除樣本點(diǎn)中重復(fù)的數(shù)據(jù)；

(2)計(jì)算每個(gè)樣本點(diǎn)與其余樣本點(diǎn)之間的距離存入矩陣cid中；

(3)指定孤立點(diǎn)的個(gè)數(shù)acnodenum，執(zhí)行孤立點(diǎn)查找程序，即計(jì)算每個(gè)點(diǎn)與其余點(diǎn)的距離之和，找出距離最大的前acnodenum個(gè)點(diǎn)，即為孤立點(diǎn)；排除孤立點(diǎn)，將孤立點(diǎn)存入集合acnode中，并將這些點(diǎn)從原始數(shù)據(jù)集中刪除得到新的數(shù)據(jù)集datanew，即為本文算法第一次去除孤立點(diǎn)之后的樣本點(diǎn)集合。在第一次去除了孤立點(diǎn)之后，可以得到新的樣本點(diǎn)集合datanew。

其次對(duì)datanew樣本進(jìn)行處理，從中找出k個(gè)初始聚類(lèi)中心：

(4)求出樣本點(diǎn)集合datanew中的兩兩之間的距離存入矩陣D中；

(5)從矩陣D中找出距離最大的兩個(gè)點(diǎn)A和B，其最大距離記為maxinD，根據(jù)式(2)計(jì)算其中心 center和半徑(r=maxinD/2)；

(6)第二次去除孤立點(diǎn)：求datanew中的每個(gè)樣本點(diǎn)與center的距離，將大于r的樣本點(diǎn)加入到集合acnode中并將其從datanew中去除得到第二次去除孤立點(diǎn)之后的樣本點(diǎn)datanewsec；

(7)利用坐標(biāo)平移的思想求解初始聚類(lèi)中心：

①將步驟(5)中求出的A、B中的任一點(diǎn)加入初始聚類(lèi)中心集合nc中作為第一個(gè)初始聚類(lèi)中心；

②循環(huán)k-1次實(shí)現(xiàn)以center為參照點(diǎn)，將A坐標(biāo)順時(shí)針移動(dòng)圓心角等于2×pi/k的度數(shù)；

利用T-text分析是否已經(jīng)發(fā)表A類(lèi)文章的研究生對(duì)于初級(jí)知識(shí)、中級(jí)知識(shí)、高級(jí)知識(shí)、初級(jí)技能、中級(jí)技能、高級(jí)技能、態(tài)度的差異情況，經(jīng)過(guò)分析，是否已經(jīng)發(fā)表A類(lèi)文章的研究生在初級(jí)知識(shí)、中級(jí)知識(shí)、高級(jí)知識(shí)、初級(jí)技能、中級(jí)技能、高級(jí)技能、態(tài)度因素的P值均大于0.05，沒(méi)有顯著性差異。

③最終得到包含A在內(nèi)的k個(gè)點(diǎn)，將這個(gè)k個(gè)點(diǎn)作為初始的聚類(lèi)中心存入矩陣nc中；

(8)利用步驟(7)中求得的初始的聚類(lèi)中心nc，用K-means算法進(jìn)行聚類(lèi)得出滿足聚類(lèi)準(zhǔn)則函數(shù)收斂的聚類(lèi)結(jié)果。

(9)計(jì)算acnode中的每個(gè)點(diǎn)與每個(gè)初始聚類(lèi)中心的距離，將acnode中的點(diǎn)加入到距離初始聚類(lèi)中心最近的簇中。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)及實(shí)驗(yàn)環(huán)境

為了便于對(duì)比分析與計(jì)算，本實(shí)驗(yàn)采用的是二維數(shù)據(jù)，并且數(shù)據(jù)類(lèi)型是數(shù)值型的。實(shí)驗(yàn)采用了兩組測(cè)試數(shù)據(jù)：一組是隨機(jī)數(shù)據(jù)，一組是UCI數(shù)據(jù)庫(kù)中的標(biāo)準(zhǔn)數(shù)據(jù)集Iris數(shù)據(jù)集。實(shí)驗(yàn)工具采用MATLAB環(huán)境編程實(shí)現(xiàn)。

3.2 實(shí)驗(yàn)方案

3.2.1 采用隨機(jī)數(shù)據(jù)

采用傳統(tǒng)的隨機(jī)選擇初始聚類(lèi)中心的K-means算法將本文的改進(jìn)算法對(duì)隨機(jī)產(chǎn)生的80個(gè)樣本進(jìn)行聚類(lèi)，聚類(lèi)的簇?cái)?shù)設(shè)為k=4，比較其聚類(lèi)結(jié)果圖。

第 1 組 ： (0.660 2，0.207 1)、(0.342 0，0.607 2)、(0.289 7， 0.629 9)、(0.341 2，0.370 5)。

第 2 組 ： (0.767 6，0.274 6)、 (0.261 0，0.193 1)、(0.719 7，0.827 6)、(0.315 8，0.620 6)。

第 3 組 ： (0.580 8，0.104 6)、 (0.815 8，0.400 6)、(0.211 4，0.445 7)、(0.623 2，0.807 5)。

第 4 組 ： (0.568 1，0.846 9)、 (0.781 2，0.575 2)、(0.211 4，0.445 7)、(0.628 6，0.122 5)。

圖1 針對(duì)隨機(jī)數(shù)據(jù)的選取四種初始聚類(lèi)中心的結(jié)果圖

采用改進(jìn)算法選出的初始聚類(lèi)中心為(0.231 1，0.956 8)、 (0.999 6，0.795 7)、(0.8385，0.0272)和(0.0700，0.188 3)，其聚類(lèi)結(jié)果如圖2所示。

由圖 1、圖 2可以看出，利用本文改進(jìn)算法選出的初始聚類(lèi)中心進(jìn)行聚類(lèi)，其聚類(lèi)結(jié)果比較接近數(shù)據(jù)分布。

圖2 針對(duì)隨機(jī)數(shù)據(jù)的改進(jìn)算法聚類(lèi)結(jié)果

3.2.2 采用Iris數(shù)據(jù)集

Iris數(shù)據(jù)集是UCI數(shù)據(jù)庫(kù)中的一個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集，包含有4個(gè)屬性，150個(gè)數(shù)據(jù)對(duì)象，可分為3類(lèi)。選用Iris數(shù)據(jù)集中間二維的數(shù)據(jù)進(jìn)行聚類(lèi)，分別用原算法和改進(jìn)算法進(jìn)行實(shí)驗(yàn)。對(duì)實(shí)驗(yàn)結(jié)果從運(yùn)行時(shí)間以及準(zhǔn)確度上進(jìn)行分析，實(shí)驗(yàn)結(jié)果匯總以及分析如表1所示。

從表1可以看出，改進(jìn)算法的運(yùn)行時(shí)間比傳統(tǒng)K-means算法的運(yùn)行時(shí)間要小，尤其當(dāng)數(shù)據(jù)集比較大時(shí)，其運(yùn)行時(shí)間小得多。從圖3中可以看出，采用改進(jìn)算法其準(zhǔn)確度明顯提高。

本文提出的改進(jìn)算法雖然在查找孤立點(diǎn)以及計(jì)算樣本點(diǎn)之間的距離方面，會(huì)增加時(shí)間消耗，但是改進(jìn)算法準(zhǔn)確度較高，聚類(lèi)效果較好。實(shí)驗(yàn)證明該算法是切實(shí)可行的，與傳統(tǒng)的K-means算法相比較，有較好的聚類(lèi)結(jié)果。

表1 K-means算法與本文改進(jìn)算法準(zhǔn)確率與運(yùn)行時(shí)間比較

圖3 兩種算法的準(zhǔn)確率以及運(yùn)行時(shí)間的比較

[1]Han Jiawei，KAMBER M.Dataminingconceptsand techniques， second edition[M].Elsevier(Singapore)Pte Ltd，2006：251-263.

[2]張建輝.K-means聚類(lèi)算法的研究與應(yīng)用 [D].武漢：武漢理工大學(xué)，2007：10-14.

[3]馮超.K-means聚類(lèi)算法的研究[D].大連：大連理工大學(xué)，2007：15-19.

[4]劉濤，尹紅健.基于半監(jiān)督學(xué)習(xí)的K-均值聚類(lèi)算法的研究[J].計(jì)算機(jī)應(yīng)用研究，2010，27(3)：913-917.

[5]李飛，薛彬，黃亞樓.初始中心優(yōu)化的 K-Means聚類(lèi)算法[J].計(jì)算機(jī)科學(xué)，2002，29(7)：94-96.

[6]Shi Na， Liu Xumin， Guan Yong.Research on k-means clustering algorithm[C].Third International Symposium on Intelligent Information Technology and Security Informatics，2010：63-67.