優化的初始中心點選取的K-means聚類算法

王金金，王未央

（上海海事大學信息工程學院，上海 201306）

優化的初始中心點選取的K-means聚類算法

王金金，王未央

（上海海事大學信息工程學院，上海 201306）

0　引言

數據挖掘中的一個重要研究方向就是聚類，它的思想是將數據集中的數據對象分為多個類或簇，在同一個簇或者類中的各個數據對象的相似程度盡可能做到最大，而不同簇或類之間的數據對象的相似程度盡可能的最小。為了將數據集群中的數據對象進行聚類，Han等人總結出了以劃分、層次、密度、網絡和模型為基礎的五大類經典聚類算法。

K-means算法是一種簡單、快速的基于劃分的聚類算法，在實際應用中最為廣泛，它能夠在一些具有數值屬性的數據的聚類中體現出聚類算法對幾何和統計學上的重大影響。然而，傳統的K-means算法具有憑借著具體的實際經驗制定k值、對初始的聚類中心異常敏感、會隨聚類中心的不同而得到不同的聚類結果等弊端，使得它很少會得到整個數據集的最佳聚類結果，并且隨機的選定初始聚類中心導致其結果經常局限于局部的最優解，從而使得到的結果非常不精確。所以為了獲得更好的聚類效果，找到一組較優的初始中心點和去除聚類結果的波動性對K-means算法具有重大的意義。

研究者們從聚類收斂條件、k值的選取、初始聚類中心的選擇和處理分類屬性數據四個方面進行改進。本文主要從初始聚類中心選擇這一方面對該算法做出改進，使得算法的精確度和效率都有所提高。

1　K-means算法的基本思想

K-means均值算法的基本思想是：從數據集中任意選取k個數據作為k個聚類的初始中心點，數據集中其余的數據依據距離最小的原則，劃分到離它最近的初始中心點這一組中，對于初始劃分的每一組，計算出組中所有數據對該數組中心距離的平均值來當作新的聚類中心點，重復執行上述步驟，直到使得平方誤差準則函數收斂為止。其中平方誤差準則函數如（1）：

在公式（1）中，E是整個分組得到的樣本空間中所有數據對象的到中心點的距離與平均距離的差的平方的和，xi是需要聚類的數據集中屬于類Ci的數據樣本，ai是類Ci中所有樣本的平均值［3］。K-means算法的具體步驟如下：

（1）從包含n個數據的數據集U中任意挑選出k個樣本數據作為k個類的初始中心，記為a1（0），a2（0），a3（0），…，ak（0）。

（2）將整個數據集U中的數據對象xi依次依據距離最小的原則分配給隨機選取的k個類中的某一類Ci（t），i∈｛1，2，3，…，k｝，t代表迭代計算的次數，即如果Di（t）=min｛||x-aj（t）||，j=1，2，3，…，k｝，則x分類到類Ci（t+1）中，i∈｛1，2，3，…，k｝。

（3）計算出再分類的聚類中心，具體計算公式如下：

在公式（2）中，類Ci（t+1）中樣本的數據個數是，新得的聚類中心就是類數據對象距離的平均值，從而使公式（1）達到最小。

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

2.1改進的算法思想

一般情況下，處于數據集的低密度區域的數據對象被稱為孤立點或者噪聲點［6］。為了避免噪聲數據的干擾，我們首先要對這些噪聲點或者孤立點進行刪除；而對于其余的數據點，我們將數據對象之間的歐氏距離當作判定數據對象相似度的一個衡量準則，因此，我們就得計算出相鄰數據對象之間的歐氏距離，然后我們將處于高密度區域中的數據對象來作為初始的聚類中心點。

我們選取的初始聚類中心點都位于整個數據集中的高密度區域范圍內，它能很好地說明整個數據集中的數據分布情況，從而消除了傳統的K-means算法依賴于聚類中心的缺陷，并提高K-means聚類結果的精度。

另外，在高密度區域中選擇數據對象當作初始聚類中心點，我們必須計算出數據對象之間的距離。對于多維屬性的數據對象，計算它們之間的距離，我們需要耗費大量的時間，尤其是那些高維屬性的對象，距離的計算就必將耗費更多的時間。所以，在本文中提出了建立一個二維數組來存儲數據對象之間的距離，對初始聚類中心選擇的衡量標準中密度大小是一方面，另一方面，為下一個K-means聚類提供直接的距離值，從而減少時間并更能提高運行效率。

2.2相關參數的定義

（1）點密度：對于數據集U中的樣本點x，以x為球心，以某一正數r為半徑的球形區域中所包含的樣本點的個數，稱之為點密度，記作Dens（x）［3］。

在公式（3）中，Dist（x，p）表示相鄰數據對象的歐氏距離。

（2）孤立點（噪聲點）：數據集U中的數據對象xi，計算xi到其相鄰點的距離的平均值，計算公式如（4）：

把所有點按從小到大序列排序，當相鄰兩點之間的平均值大于某一閾值，則判斷此點為孤立點并去除孤立點。

2.3算法的一般描述

輸入：聚類數k和含有n個數據對象的數據集；

輸出：達到目標函數值中最小的k個聚類結果。

具體的實現步驟如下：

（1）計算出相鄰的兩個數據對象的距離d（xi，yj）；

（2）按照公式（5）將每一個數據對象到其相鄰數據對象的距離的平均值計算出來，并將判定為是孤立點的數據對象刪掉，從而得到高密度區域的數據對象的集合D；

（3）將具有最大密度的數據樣本當作第一個中心a1加入到集合A中，同時將其從D中刪除；

（4）在數據對象集合D中找到離集合A最遠的點，加入到集合A中，同時將其從集合D中刪除；

（5）重復步驟（4），直到A中的數據對象的個數達到k個；

（6）按照選出來的k個聚類中心，運用 K-means聚類算法得到最終的聚類結果。

3　實驗分析

3.1實驗一

有一個專門用于測試數據挖掘算法和機器學習的UCI［4］數據庫，在這個數據庫中有專門為測試聚類算法性能而存在的的數據集，所以我們可以用精確度來直接表示聚類的質量。在實驗中的實驗數據集是UCI數據庫中的常用的Iris數據集和Wine數據集，使用它們來證明優化的初始中心選取的K-means算法的效果，各數據集的概況在表1中體現：

表1　UCI數據集

在實驗時，本文中分別用隨機選擇初始聚類中心的傳統K-means聚類算法、文獻中的改進算法以及本文提出的優化的初始聚類中心選擇的聚類算法對上述兩個數據集進行了5次聚類實驗。通過對實驗結果的分析和計算得到如下兩個實驗結果表格，具體如表2、表3所示：

表2　三種算法對Iris數據集的測試結果表

表3　三種算法對wine數據集的測試結果表

其他文獻中的算法與傳統的K-means聚類算法相比，使得對初始聚類中心的敏感性得到消除，算法相對比較穩定并且使得精確度有所提高，但是與文本提出的新算法相比較，本文提出的新算法不僅對初始聚類中心的依賴消除而且使得聚類結果的精確度更加準確，同時提高了聚類的運算效率。針對擁有250個數據Iris數據集分成四類，用傳統的隨機選取初始中心的K-means算法，實驗5次，得到的最高準確率能夠達到83.33%，最低準確率僅僅才57.33%，雖然其他文獻中的算法精確度可以穩定在83.33%的較高水平上，但是本文提出的新算法在保證計算結果穩定的同時，達到了更高的精確度，為89.33%；再通過三種算法的迭代次數可以看出，本文提出的優化的初始中心點選取的K-means聚類算法相對于傳統的K-means算法，以及其他文獻中提出的算法大大地提高了運算的效率和聚

3.2實驗二

下面這個實驗是選取了UCI數據庫中的含有150個數據對象的Iris數據集，其中每個數據對象有4個屬性，我們通過實驗是將數據集分成3類，根據Iris數據集中間的二維數據進行聚類，分別用傳統K-means算法隨機選取聚類中心的聚類算法和本文提出的優化的初始中心點選取的K-means聚類算法進行聚類。通過實驗我們得到了如下的聚類結果圖，在實驗結果圖中，圓圈、三角形、五角星分別代表一類數據。具體的實驗結果如圖1所示。

圖1　傳統K-means隨機選取聚類中心的聚類算法

圖2　優化的初始中心點選取的K-means聚類算法

從上述的兩個實驗的實驗結果可以看出，本文中所提出的優化的初始中心點選取的K-means聚類算法，既可保證計算結果的穩定性，更進一步提高了算法的精確度。同時在計算過程中，本文算法的計算時間少于傳統算法平均時間，迭代次數也遠遠小于傳統算法，類的精確度。我們將含有278條數據的Wine數據集分成4類，經過5次傳統K-means聚類算法的實驗能夠達到的最高準確率是96.07%，而最低準確率僅僅是59.55%，通過其他文獻中提出的算法進行的實驗，其準確率能夠穩定的達到96.63%，但是還是沒有超過本文提出的優化的初始中心點選取的K-means聚類算法所達到97.19%的準確率。很好地提高了算法的運算效率。

4　結語

隨著互聯網用戶的增加和數據庫的龐大發展，聚類人物所設計的數據量越來越龐大，傳統的K-means聚類算法的應用相當廣范，但其聚類效率和聚類結果會隨著初始聚類中心以及數據量的改變而改變，嚴重影響了這種算法聚類的精確度；對于這個問題很多研究專家分別從各個不同的角度對K-means算法作出了改進。在本文中提出了一種優化的初始中心點選取的K-means聚類算法，并通過實驗結果的對比得出，利用該算法能夠更好地提高聚類的精確度，并且利用計算過程中通過數組來存儲對象的方法，很大地提高了算法的運算效率。

［1］周愛武，于亞飛.K-means聚類算法的研究［J］.計算機技術與發展，2011.02：2.

［2］王賽芳，戴芳，王萬斌，張曉宇.基于初始聚類中心優化的K-均值的算法［J］.計算機工程與科學，2010，32（10）.

［3］汪中，劉貴全，陳恩紅.一種優化初始中心點的K-means算法［J］.模式識別與人工智能，2009，22（2）.

［4］韓凌波，王強，蔣正鋒等.一種改進的K-means初始聚類中心選取算法［J］.計算機工程，2010，46（17）.

［5］孟子健，馬江洪.一種可選初始聚類中心的改進K均值算法［J］.理論新探，2014，12（3）.

［6］顧洪博，張繼懷.改進的k-均值算法在聚類分析中的應用［J］-西安科技大學學報2010，30（4）.

［7］曹志宇，張忠林，李元韜.快速查找初始聚類中心的K-means算法［J］.蘭州交通大學學報，2009，28（6）：15-18.

［8］ESTER M，KRIEGEL H P，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise［J］. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining.Portland：AAAI，1996：226-231.

［9］Gan W Y.Li D E.Hierarchical clustering based on kernel density estimation［J］-Journal of System Simulation，2004（02）.

Clustering；K-means Algorithm；Clustering；Outlier；Density

K-means Clustering Algorithm to Optimize the Initial Center Point

WANG Jin-jin，WANG Wei-yang
（Colleg of Information Engineering，Shanghai Maritime University，Shanghai 201306）

1007-1423（2015）20-0006-04

10.3969/j.issn.1007-1423.2015.20.002

王金金（1988-），女，山東濰坊人，在讀碩士研究生，研究方向為港航物流管理

2015－05－13

2015－07－13

介紹一種可以對初始聚類中心進行優化的算法，改進之處是對孤立點進行特殊處理，降低孤立點敏感的問題，把距離與密度結合，選取最優的初始中心點，從而使聚類的精確度得到提高，并且該算法通過在計算的過程中存儲數據對象之間的距離來提高算法的效率。通過對實驗結果的分析，得到改進后的聚類算法可以有更好的精確度和更高的算法效率。

K-means算法；聚類中心；孤立點

王未央（1963-），女，江蘇常熟人，副教授，研究方向為數據處理與挖掘

Describes an algorithm which initial cluster centers can be optimized.The improvement is to isolate point for special treatment，reduce outlier sensitive issue，combines the distance and density to select the appropriate initial focal point，so that improves the clustering accuracy，in order to improve the efficiency of the algorithm，the algorithm in the process of calculating the distance between the stored data objects.The experimental results prove that the improved clustering algorithm can achieve better results and higher efficiency of the algorithm.