王 越，王 泉，呂奇峰，曾 晶

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

K-means算法是最常用的聚類算法之一，是一種基于劃分的聚類算法，具有聚類速度快、易實(shí)現(xiàn)、對(duì)大型數(shù)據(jù)集能進(jìn)行高效分類的特點(diǎn)。但是K-means算法也有其不足，例如傳統(tǒng)K-means算法的初始聚類中心點(diǎn)選擇是隨機(jī)的，不同的初始聚類中點(diǎn)心會(huì)使得到的聚類結(jié)果不同，甚至可能無(wú)法得到有效的聚類結(jié)果［1-2］。所以如何選擇合理的初始聚類中心點(diǎn)，使得聚類的結(jié)果準(zhǔn)確、穩(wěn)定、有效，是一個(gè)重要的研究方向［3］。目前，已有大量的文獻(xiàn)針對(duì)K-means算法的初始聚類中心點(diǎn)的選取進(jìn)行了研究，例如:基于樣本點(diǎn)之間最大最小距離的選擇方法［4］;將隨機(jī)選擇初始聚類中心點(diǎn)的過(guò)程重復(fù)多次，然后取最優(yōu)結(jié)果的擇優(yōu)法［5］;基于簇密度的密度法［6］;基于遺傳算法尋找初始聚類中心點(diǎn)的遺傳法［7-8］;遞歸法［9］;基于種群的啟發(fā)式搜索算法［10］等。這些算法都能有效提高 K-means算法聚類的準(zhǔn)確性，但是卻需要反復(fù)進(jìn)行大量的計(jì)算，增加了算法的時(shí)間復(fù)雜度。

本文提出一種新的基于樣本點(diǎn)之間距離的初始聚類中心選擇算法，不需要進(jìn)行大量的計(jì)算便能得到合理的初始聚類中心點(diǎn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法比傳統(tǒng)的K-means算法有更高的準(zhǔn)確性與穩(wěn)定性。

1 改進(jìn)的K-means算法的基本思想

1.1 初始聚類中心點(diǎn)選取的算法

令樣本數(shù)據(jù)集合 S={x1，x2，…，xn}，傳統(tǒng)的K-means算法是從S中隨機(jī)選擇k個(gè)樣本點(diǎn)，每一個(gè)樣本點(diǎn)代表一個(gè)聚類的質(zhì)心。這樣導(dǎo)致了聚類結(jié)果的波動(dòng)性，使得聚類結(jié)果不穩(wěn)定且平均準(zhǔn)確率不高。

改進(jìn)初始聚類中心點(diǎn)選取的思路:

1)計(jì)算數(shù)據(jù)集所有樣本點(diǎn)兩兩之間的距離。K-means算法用2個(gè)樣本點(diǎn)之間的歐式距離代表2點(diǎn)的相似程度，距離越小說(shuō)明樣本點(diǎn)之間的相似度越高。2點(diǎn)間的歐式距離可定義為

其中:xin為樣本點(diǎn)xi第n維的數(shù)據(jù)對(duì)象;xjn為樣本點(diǎn)xj第n維的數(shù)據(jù)對(duì)象。

2)計(jì)算所有樣本點(diǎn)之間的平均距離，可定義為

3)將與樣本點(diǎn)xi(其中1≤i≤n)的距離小于平均距離 mDis的樣本點(diǎn) xj(1≤j≤n，j≠i)記錄下來(lái)，稱其為鄰近點(diǎn)，并計(jì)算出xi的鄰近點(diǎn)數(shù)量。當(dāng)所有樣本點(diǎn)的鄰近點(diǎn)統(tǒng)計(jì)結(jié)束后，將它們按鄰近點(diǎn)的數(shù)量從高到低排序。鄰近點(diǎn)數(shù)量最多的樣本點(diǎn)作為第1個(gè)聚類中心點(diǎn)。然后繼續(xù)往下查找。若鄰近點(diǎn)數(shù)量第2的點(diǎn)是已有初始聚類中心的鄰近點(diǎn)則忽略，繼續(xù)往下查找，直到找到第m個(gè)點(diǎn)不是已有聚類中心點(diǎn)的鄰近點(diǎn)，則將它作為聚類中心點(diǎn)。反復(fù)進(jìn)行這個(gè)過(guò)程，直到找到k個(gè)初始聚類中心點(diǎn)。這樣找到的初始聚類中心點(diǎn)能較好地反映出數(shù)據(jù)對(duì)象的分布，并且能保證找出的k個(gè)初始聚類中心點(diǎn)不會(huì)過(guò)于相近而導(dǎo)致聚類效果不佳。

1.2 樣本點(diǎn)維間加權(quán)

由于數(shù)據(jù)集中的不同類的樣本點(diǎn)可能因?yàn)榫嚯x比較近而出現(xiàn)部分樣本點(diǎn)有交疊的現(xiàn)象，這樣由傳統(tǒng)的K-means算法進(jìn)行聚類時(shí)效果會(huì)不理想。由于K-means算法采用歐氏距離來(lái)表示樣本點(diǎn)之間的相似程度，研究式(1)可以發(fā)現(xiàn)，如果放大樣本點(diǎn)之間差異最大的維度，其他維度保持不變，那么計(jì)算出的結(jié)果中不同類的樣本點(diǎn)之間的距離變大的幅度會(huì)比相同類的樣本點(diǎn)之間的距離變大的幅度要大一些。因此，對(duì)差異最大的維進(jìn)行加權(quán)以后，不同類樣本點(diǎn)之間的距離便會(huì)比相同類樣本點(diǎn)之間的距離拉得更開(kāi)，從而使聚類的準(zhǔn)確度提高。

可通過(guò)下述方法找到樣本點(diǎn)之間差異最大的維。

用DIM(i)avg表示第i維的平均值，即

其中:j表示第幾個(gè)樣本;DIM(i，j)表示第j個(gè)樣本點(diǎn)的第i維的值。然后計(jì)算第i維上各樣本點(diǎn)的值與該維平均值的差，再求和?？杀硎緸?/p>

通過(guò)對(duì)比各維經(jīng)過(guò)上述操作后得到的結(jié)果，最大的維便是差異最大的維。

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

令樣本數(shù)據(jù)集 S={x1，x2，…，xn}，需要將該樣本集聚為K類。

改進(jìn)后的K-means算法流程:

輸入:樣本數(shù)據(jù)集S，聚類個(gè)數(shù)K。

輸出:K個(gè)聚類。

1)獲取樣本數(shù)據(jù)集S，找到樣本點(diǎn)之間差異最大的維，并進(jìn)行加權(quán)操作。

2)根據(jù)式(1)計(jì)算出數(shù)據(jù)集中樣本點(diǎn)兩兩之間的距離dis(xi，xj)，并保存在n×n的表中。

3)根據(jù)式(2)計(jì)算出樣本點(diǎn)之間的平均距離mDis。

4)將與樣本點(diǎn)xi(其中1≤xi≤n)的距離小于mDis的樣本點(diǎn) xj(其中1≤j≤n，j≠i)記錄下來(lái)，令它們?yōu)閤i的鄰近點(diǎn)，并計(jì)算出每個(gè)樣本點(diǎn)的鄰近點(diǎn)的數(shù)量，保存在鄰近點(diǎn)表中。

5)將樣本點(diǎn)x1，x2，…，xn按鄰近點(diǎn)數(shù)從高到低排列，鄰近點(diǎn)最多的樣本點(diǎn)作為第1個(gè)聚類中心點(diǎn)。

6)依次往下查找鄰近點(diǎn)表，若該點(diǎn)是已有初始聚類中心的鄰近點(diǎn)則忽略，繼續(xù)查找鄰近點(diǎn)表，直到找到一個(gè)樣本點(diǎn)不為已有聚類中心點(diǎn)的鄰近點(diǎn)，則將它作為另一個(gè)聚類中心點(diǎn)。

7)重復(fù)步驟6)直到找到第k個(gè)聚類中心點(diǎn)。

8)進(jìn)行聚類運(yùn)算后，將樣本點(diǎn)加權(quán)的維還原，并輸出實(shí)驗(yàn)結(jié)果。

3 改進(jìn)的K-means算法的實(shí)驗(yàn)結(jié)果與分析

為了考察改進(jìn)K-means算法的有效性，本文選擇用于測(cè)試算法性能的UCI數(shù)據(jù)庫(kù)中的Iris數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

Iris數(shù)據(jù)集是被公認(rèn)為用于數(shù)據(jù)挖掘的最著名的數(shù)據(jù)集，它包含3種植物種類，即setosa、versicolor、virginica，每種各有50個(gè)樣本。它有4個(gè)屬性:花萼長(zhǎng)、花萼寬、花瓣長(zhǎng)、花瓣寬。該數(shù)據(jù)集的數(shù)據(jù)特點(diǎn)是:第1類樣本點(diǎn)與其他樣本點(diǎn)離得較遠(yuǎn);第2類樣本點(diǎn)和第3類樣本點(diǎn)離得很近，并且有一些交疊。

使用經(jīng)典的K-means算法在Iris數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，得到實(shí)驗(yàn)結(jié)果如表1所示。

表1 經(jīng)典算法的實(shí)驗(yàn)結(jié)果

使用改進(jìn)后的K-means算法在Iris數(shù)據(jù)集上再次進(jìn)行實(shí)驗(yàn)，得到實(shí)驗(yàn)結(jié)果如表2所示。

實(shí)驗(yàn)結(jié)果表明:經(jīng)典的K-means算法受初始中心點(diǎn)的影響較大，經(jīng)過(guò)5次實(shí)驗(yàn)最好的情況下正確率為87.3%，最差的情況下正確率僅為69.3%。

改進(jìn)后的算法當(dāng)樣本點(diǎn)差異最大的維加權(quán)的系數(shù)ω=1，即保持原樣本點(diǎn)各維的值不變的時(shí)候進(jìn)行2次實(shí)驗(yàn)，雖然準(zhǔn)確率相對(duì)傳統(tǒng)的K-means算法最好的情況沒(méi)有提高，但是改進(jìn)后算法的結(jié)果穩(wěn)定，且與傳統(tǒng)算法中最好的情況下得準(zhǔn)確率相同。當(dāng)加權(quán)系數(shù)ω=2時(shí)，即放大了樣本點(diǎn)之間差異最大的維，發(fā)現(xiàn)得到的結(jié)果的準(zhǔn)確率與不進(jìn)行加權(quán)之前相比有所提高。當(dāng)加權(quán)系數(shù)ω=5時(shí)，聚類結(jié)果的準(zhǔn)確率比ω=2時(shí)又有所提高，說(shuō)明對(duì)樣本點(diǎn)間差異最大維進(jìn)行加權(quán)再進(jìn)行聚類的方法是可行的，而且ω=2時(shí)沒(méi)有達(dá)到改進(jìn)算法的最大正確率。當(dāng)加權(quán)系數(shù)ω=10時(shí)，實(shí)驗(yàn)的結(jié)果和ω=5時(shí)一樣，準(zhǔn)確率不再提高，說(shuō)明已達(dá)到改進(jìn)后算法的最大正確率92%。

表2 改進(jìn)后算法的實(shí)驗(yàn)結(jié)果

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

K-means算法計(jì)算速度快、資源消耗小，是一種應(yīng)用廣泛的聚類算法。傳統(tǒng)的K-means算法由于初始聚類中心點(diǎn)的選取是隨機(jī)的，造成了聚類結(jié)果的不穩(wěn)定。改進(jìn)的算法改進(jìn)了初始中心點(diǎn)的選擇方法，并且對(duì)樣本點(diǎn)之間差異最大的維進(jìn)行加權(quán)操作。實(shí)驗(yàn)證明改進(jìn)后的算法能找到合適的初始聚類中心點(diǎn)，并且有效提高了算法聚類的準(zhǔn)確率。不足之處是需要人工進(jìn)行多次實(shí)驗(yàn)才能確定權(quán)值何時(shí)才是最優(yōu)，如何自動(dòng)獲得最優(yōu)的權(quán)值將是下一步的研究方向。

［1］HAN Jia wei，KAMBER M.Data Mining Concepts and Techniques［M］.［S.l］：Morgan Kaufman Publishers，2001.

［2］韓存鴿.聚類挖掘在高校圖書(shū)館管理系統(tǒng)中的應(yīng)用［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012(11)：83-87.

［3］顧洪博，張繼懷.聚類算法初始聚類中心的優(yōu)化［J］.西安工程大學(xué)學(xué)報(bào)，2010，24(2)：222-226.

［4］連鳳娜，吳錦林，唐琦.一種改進(jìn)的K-means聚類算法［J］.電腦與信息技術(shù)，2008，16(1)：38-40.

［5］曹文平.一種有效K-均值聚類中心的選取方法［J］.計(jì)算機(jī)與現(xiàn)代化，2008(3)：95-97.

［6］袁方，周志勇，宋鑫.初始聚類中心優(yōu)化的K-means算法［J］.計(jì)算機(jī)工程，2007，33(3)：65-66.

［7］賴玉霞，劉建平，楊國(guó)興.基于遺傳算法的K均值聚類分析［J］.計(jì)算機(jī)工程，2008，34(20)：200-202.

［8］路彬彬，賈振紅，何迪，等.基于新的遺傳算法的模糊C均值聚類用于遙感圖像分割［J］.激光雜志，2010(6)：15-17.

［9］李業(yè)麗，秦臻.一種改進(jìn)的K-means算法［J］.北京印刷學(xué)院學(xué)報(bào)，2007，15(2)：63-65.

［10］孟巖，劉希玉，劉艷麗.一種基于蟻群算法的K-means算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44(1)：179-182.