一種優化初始聚類中心的K-means聚類算法＊

周愛武，崔丹丹，潘 勇

(安徽大學 計算機科學與技術學院，安徽 合肥 230039)

數據挖掘技術研究不斷深入與發展，作為數據挖掘技術中的聚類分析，也越來越被人們關注與研究。聚類分析是數據挖掘中一個非常活躍的研究領域，并且具有廣泛的應用。聚類就是將數據集劃分成若干簇或者類的一個過程[1]。經過聚類之后，使得同一簇中的數據對象相似度最大，而不同簇之間的相似度最小。

聚類是一種無監督的學習算法，即把數據對象聚成不同的類簇，從而使不同類之間的數據相似度低，而同一個類中的相似度高，并且將要劃分的類是之前不知道的，其形成由數據驅動。聚類算法[1]分成基于劃分的、密度的、分層的、網格的、模型的。其中基于劃分的聚類算法中的K-均值算法(K-means算法)是最常用的一種聚類算法，同時也是應用最廣泛的一種算法。K-means聚類算法主要針對處理大數據集時[2]，處理快速簡單，并且算法具有高效性和可伸縮性。但是K-means算法也有一定的局限性[3]，如K值必須事先給定，只能處理數值型數據，初始聚類的中心是隨機選擇的，而其聚類結果的好壞直接取決于初始聚類中心的選擇。并且由于初始聚類中心隨機選擇，容易造成算法陷入局部最優解。因此初始聚類中心的選擇十分重要。

本文針對隨機選擇初始聚類中心的缺點，提出了一種新的改進的K-means聚類算法。該算法產生的初始聚類中心不是隨機的，能夠很好地體現數據的分布情況，使得初始中心盡可能地趨向于比較密集的范圍內，從而進行更好的聚類，最終消除了傳統K-means算法中由于初始聚類中心選擇是隨機的而產生的缺點。最后實驗證明了這種算法的有效性與可行性。

1 傳統K-means算法

1.1 傳統K-means算法的思想

傳統的K-means算法具體描述如下[5]：

輸入：k，data[n]；

輸出：K個簇的集合。

(1)任意選擇k個對象作為初始中心點，例如c[0]=data[0]，…c[k-1]=data[k-1]。

(2)根據簇中對象的均值，將每個對象指派給最相似的簇。

(3)更新簇均值，即計算每個簇中對象的均值。(4)重復步驟(2)、(3)，直到不再發生變化。

1.2 傳統K-means算法的局限性

傳統的K-means算法中對于K個中心點的選取是隨機的[3]，而初始點選取的不同會導致不同的聚類結果。為了減少這種隨機選取初始聚類中心而導致的聚類結果的不穩定性，本文提出了一種關于初始聚類中心選取的方法，用來改變這種不穩定性。

2 優化初始聚類中心的改進K-means算法

2.1 基本定義

設需要聚類的數據集：X={xi|xi∈R P，i=1，2，…，n)，k個聚類中心分別用 z1，z2，z3，…zk表示。 有如下定義：

定義 1 2 個 p 維向 量 xi=(xi1，xi2，…，xip)T和 xj=(xj1，xj2，…，xjp)T數據對象間的距離用歐氏距離[6]表示：

定義 2 二維數據樣本點中心 center(xi，xj)[6]：

定義3 樣本點之間的平均距離Meandist：

即所有樣本點的兩兩之間的距離之和除以樣本點n的組合數。

2.2 改進算法流程

本算法的改進建立在沒有離群點的數據集上，針對沒有離群點的數據進行分析。

輸入：樣本點，初值 k。

輸出：k個簇的聚類結果，使平方誤差準則最小。

步驟：

(1)求出兩兩樣本點之間的距離存入矩陣D中。

(2)初始化集合A以及中心點集合 Center，最小距離的樣本點放入集合A中，并求出其中心最為第一個初始的聚類中心z1。

(3)求出次小距離的樣本點的中心，然后求出此中心與z1之間的距離，與Meandist進行判斷。如果小于Meandist，則將此樣本點加入A中，再求第三距離小的樣本點，重復步驟(3)；如果大于Meandist，則求出此中心存入Center。

(4)Until集合 Center中的個數等于 k，初始聚類中心全部找到。

(5)用找到的初始聚類中心進行K-means聚類。

算法舉例：

如圖1所示，假設有20個點數據集，并且已經將孤立點排除，需要將其聚成k=3類。首先計算兩兩之間的距離，利用定義 2求出 Meandist，并找出最小的距離(如圖中的x1、x2)；然后求出其中心，用紅色表示；找出距離次小的距離(如圖中的 x3、x4)，計算出 x3、x4的中心，并加一步判斷。如果這個中心與前面求出的一個聚類中心之間的距離小于Meandist，那么就排除這個聚類中心，接著執行找第三小的距離，并求其中心，直到找到K個初始聚類中心為止；反之，則求下一個初始聚類中心，直到找到k個初始聚類中心為止。

圖1 改進算法聚類舉例

3 實驗分析

為了便于分析與計算，本文采用的是二維數據，并且數據類型是實型的，實驗環境為MATLAB。為了進行對比，分別采用了傳統的K-means算法與本文改進的K-means算法進行比較。

本文實驗采用了兩組實驗進行驗證，一組是隨機數據，一組是標準數據庫集。

(1)采用隨機數據

本文用隨機產生的80個樣本分別采用傳統的K-means算法進行聚類與本文的改進算法進行聚類，比較其聚類結果圖。

傳統算法采用隨機選取初始聚類中心有 (0.950 1，0.794 8)、(0.231 1，0.956 8)、(0.606 8，0.522 6)， 其聚類結果如圖2所示。

采用改進算法的初始聚類中心有 (0.339 9、0.028 4)，(0.2007，0.5914)、(0.7248，0.3819)，其聚類結果如圖 3 所示。

圖2 針對隨機數據的傳統的K-means聚類結果

圖3 針對隨機數據的改進算法聚類結果

圖4 Iris數據集傳統K-means算法聚類結果

圖5 Iris數據集改進算法聚類結果

表1 兩種算法不同數據集的執行時間比較

(2)采用標準數據集：Iris數據集

本文采用了Iris數據集，它是UCI數據庫中的一個標準數據集。Iris數據集包含有4個屬性，150個數據對象，可分為三類。選用Iris數據集前二維的數據進行聚類。分別用傳統算法和改進算法進行聚類，其中分別用實心點、圈實心點以及五角星表示這三類。

傳統算法采用隨機選取初始聚類中心有 (0.950 1，0.582 8)，(0.231 1，0.423 5)、(0.606 8，0.515 5)， 其聚類結果如圖4所示。

采用改進算法的初始聚類中心有(0.009 9，0.015 0)、(0.294 2，0.639 2)、(0.651 2，0.190 5)，其聚類結果如圖 5所示。

對比這兩幅圖的聚類結果可以看出，采用改進算法產生聚類結果比較穩定準確。

運用K-means算法和本文改進算法針對隨機數據和Iris數據分別實驗得出的時間如表1所示。

K-means算法是應用最為廣泛的一種基于劃分的算法，但是由于其初始中心的選擇是隨機的，從而影響了聚類結果，使得聚類結果不穩定。本文主要是針對傳統K-means算法的這一缺點，提出了一種新的改進算法，即基于平均距離的思想，進行初始聚類中心的選擇。實驗證明，該算法是切實可行的，與傳統的K-means算法比較，有較好的聚類結果以及較短的運行時間。但本文算法是基于先將噪聲點排除掉之后應用此改進算法進行聚類、且是在點的分布比較均勻的前提下應用，才有良好的效果。如果對于具有噪聲點的數據集有一定的局限性、而且是比較密集的點的情況下，這將在以后的學習研究中進行探討。

[1]HAN J，KAMBER M.數據挖掘概念與技術[M].范明，盂小峰，等譯.北京：機械工業出版社，2006.

[2]孟海東，張玉英，宋飛燕.一種基于加權歐氏距離聚類方法的研究[J].計算機應用，2006，26(22)：152-153.

[3]包穎.基于劃分的聚類算法研究與應用[D].大連：大連理工大學，2008：18-20.

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

[5]張玉芳，毛嘉莉，熊忠陽.一種改進的K-means算法[J].計算機應用，2003，23(8)：31-33.

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