基于初始聚類中心優(yōu)化和維間加權(quán)的改進K-means算法

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

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

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

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

1 改進的K-means算法的基本思想

1.1 初始聚類中心點選取的算法

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

改進初始聚類中心點選取的思路:

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

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

2)計算所有樣本點之間的平均距離，可定義為

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

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

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

可通過下述方法找到樣本點之間差異最大的維。

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

其中:j表示第幾個樣本;DIM(i，j)表示第j個樣本點的第i維的值。然后計算第i維上各樣本點的值與該維平均值的差，再求和。可表示為

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

2 改進K-means算法的流程描述

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

改進后的K-means算法流程:

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

輸出:K個聚類。

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

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

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

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

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

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

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

8)進行聚類運算后，將樣本點加權(quán)的維還原，并輸出實驗結(jié)果。

3 改進的K-means算法的實驗結(jié)果與分析

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

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

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

表1 經(jīng)典算法的實驗結(jié)果

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

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

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

表2 改進后算法的實驗結(jié)果

4 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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