基于初始聚類中心優化和維間加權的改進K-means算法

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

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

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

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

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

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

令樣本數據集合 S={x1，x2，…，xn}，傳統的K-means算法是從S中隨機選擇k個樣本點，每一個樣本點代表一個聚類的質心。這樣導致了聚類結果的波動性，使得聚類結果不穩定且平均準確率不高。

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

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

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

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

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

1.2 樣本點維間加權

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

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

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

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

通過對比各維經過上述操作后得到的結果，最大的維便是差異最大的維。

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

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

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

輸入:樣本數據集S，聚類個數K。

輸出:K個聚類。

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

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

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

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

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

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

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

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

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

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

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

使用經典的K-means算法在Iris數據集上進行實驗，得到實驗結果如表1所示。

表1 經典算法的實驗結果

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

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

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

表2 改進后算法的實驗結果

4 結束語

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

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

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

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

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

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

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

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

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

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

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