優(yōu)化的初始中心點(diǎn)選取的K-means聚類算法

王金金，王未央

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

優(yōu)化的初始中心點(diǎn)選取的K-means聚類算法

王金金，王未央

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0　引言

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

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

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

1　K-means算法的基本思想

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

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

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

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

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

在公式（2）中，類Ci（t+1）中樣本的數(shù)據(jù)個(gè)數(shù)是，新得的聚類中心就是類數(shù)據(jù)對(duì)象距離的平均值，從而使公式（1）達(dá)到最小。

2　初始聚類中心優(yōu)化的K-means算法

2.1改進(jìn)的算法思想

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

我們選取的初始聚類中心點(diǎn)都位于整個(gè)數(shù)據(jù)集中的高密度區(qū)域范圍內(nèi)，它能很好地說明整個(gè)數(shù)據(jù)集中的數(shù)據(jù)分布情況，從而消除了傳統(tǒng)的K-means算法依賴于聚類中心的缺陷，并提高K-means聚類結(jié)果的精度。

另外，在高密度區(qū)域中選擇數(shù)據(jù)對(duì)象當(dāng)作初始聚類中心點(diǎn)，我們必須計(jì)算出數(shù)據(jù)對(duì)象之間的距離。對(duì)于多維屬性的數(shù)據(jù)對(duì)象，計(jì)算它們之間的距離，我們需要耗費(fèi)大量的時(shí)間，尤其是那些高維屬性的對(duì)象，距離的計(jì)算就必將耗費(fèi)更多的時(shí)間。所以，在本文中提出了建立一個(gè)二維數(shù)組來存儲(chǔ)數(shù)據(jù)對(duì)象之間的距離，對(duì)初始聚類中心選擇的衡量標(biāo)準(zhǔn)中密度大小是一方面，另一方面，為下一個(gè)K-means聚類提供直接的距離值，從而減少時(shí)間并更能提高運(yùn)行效率。

2.2相關(guān)參數(shù)的定義

（1）點(diǎn)密度：對(duì)于數(shù)據(jù)集U中的樣本點(diǎn)x，以x為球心，以某一正數(shù)r為半徑的球形區(qū)域中所包含的樣本點(diǎn)的個(gè)數(shù)，稱之為點(diǎn)密度，記作Dens（x）［3］。

在公式（3）中，Dist（x，p）表示相鄰數(shù)據(jù)對(duì)象的歐氏距離。

（2）孤立點(diǎn)（噪聲點(diǎn)）：數(shù)據(jù)集U中的數(shù)據(jù)對(duì)象xi，計(jì)算xi到其相鄰點(diǎn)的距離的平均值，計(jì)算公式如（4）：

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

2.3算法的一般描述

輸入：聚類數(shù)k和含有n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集；

輸出：達(dá)到目標(biāo)函數(shù)值中最小的k個(gè)聚類結(jié)果。

具體的實(shí)現(xiàn)步驟如下：

（1）計(jì)算出相鄰的兩個(gè)數(shù)據(jù)對(duì)象的距離d（xi，yj）；

（2）按照公式（5）將每一個(gè)數(shù)據(jù)對(duì)象到其相鄰數(shù)據(jù)對(duì)象的距離的平均值計(jì)算出來，并將判定為是孤立點(diǎn)的數(shù)據(jù)對(duì)象刪掉，從而得到高密度區(qū)域的數(shù)據(jù)對(duì)象的集合D；

（3）將具有最大密度的數(shù)據(jù)樣本當(dāng)作第一個(gè)中心a1加入到集合A中，同時(shí)將其從D中刪除；

（4）在數(shù)據(jù)對(duì)象集合D中找到離集合A最遠(yuǎn)的點(diǎn)，加入到集合A中，同時(shí)將其從集合D中刪除；

（5）重復(fù)步驟（4），直到A中的數(shù)據(jù)對(duì)象的個(gè)數(shù)達(dá)到k個(gè)；

（6）按照選出來的k個(gè)聚類中心，運(yùn)用 K-means聚類算法得到最終的聚類結(jié)果。

3　實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)一

有一個(gè)專門用于測(cè)試數(shù)據(jù)挖掘算法和機(jī)器學(xué)習(xí)的UCI［4］數(shù)據(jù)庫，在這個(gè)數(shù)據(jù)庫中有專門為測(cè)試聚類算法性能而存在的的數(shù)據(jù)集，所以我們可以用精確度來直接表示聚類的質(zhì)量。在實(shí)驗(yàn)中的實(shí)驗(yàn)數(shù)據(jù)集是UCI數(shù)據(jù)庫中的常用的Iris數(shù)據(jù)集和Wine數(shù)據(jù)集，使用它們來證明優(yōu)化的初始中心選取的K-means算法的效果，各數(shù)據(jù)集的概況在表1中體現(xiàn)：

表1　UCI數(shù)據(jù)集

在實(shí)驗(yàn)時(shí)，本文中分別用隨機(jī)選擇初始聚類中心的傳統(tǒng)K-means聚類算法、文獻(xiàn)中的改進(jìn)算法以及本文提出的優(yōu)化的初始聚類中心選擇的聚類算法對(duì)上述兩個(gè)數(shù)據(jù)集進(jìn)行了5次聚類實(shí)驗(yàn)。通過對(duì)實(shí)驗(yàn)結(jié)果的分析和計(jì)算得到如下兩個(gè)實(shí)驗(yàn)結(jié)果表格，具體如表2、表3所示：

表2　三種算法對(duì)Iris數(shù)據(jù)集的測(cè)試結(jié)果表

表3　三種算法對(duì)wine數(shù)據(jù)集的測(cè)試結(jié)果表

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

3.2實(shí)驗(yàn)二

下面這個(gè)實(shí)驗(yàn)是選取了UCI數(shù)據(jù)庫中的含有150個(gè)數(shù)據(jù)對(duì)象的Iris數(shù)據(jù)集，其中每個(gè)數(shù)據(jù)對(duì)象有4個(gè)屬性，我們通過實(shí)驗(yàn)是將數(shù)據(jù)集分成3類，根據(jù)Iris數(shù)據(jù)集中間的二維數(shù)據(jù)進(jìn)行聚類，分別用傳統(tǒng)K-means算法隨機(jī)選取聚類中心的聚類算法和本文提出的優(yōu)化的初始中心點(diǎn)選取的K-means聚類算法進(jìn)行聚類。通過實(shí)驗(yàn)我們得到了如下的聚類結(jié)果圖，在實(shí)驗(yàn)結(jié)果圖中，圓圈、三角形、五角星分別代表一類數(shù)據(jù)。具體的實(shí)驗(yàn)結(jié)果如圖1所示。

圖1　傳統(tǒng)K-means隨機(jī)選取聚類中心的聚類算法

圖2　優(yōu)化的初始中心點(diǎn)選取的K-means聚類算法

從上述的兩個(gè)實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果可以看出，本文中所提出的優(yōu)化的初始中心點(diǎn)選取的K-means聚類算法，既可保證計(jì)算結(jié)果的穩(wěn)定性，更進(jìn)一步提高了算法的精確度。同時(shí)在計(jì)算過程中，本文算法的計(jì)算時(shí)間少于傳統(tǒng)算法平均時(shí)間，迭代次數(shù)也遠(yuǎn)遠(yuǎn)小于傳統(tǒng)算法，類的精確度。我們將含有278條數(shù)據(jù)的Wine數(shù)據(jù)集分成4類，經(jīng)過5次傳統(tǒng)K-means聚類算法的實(shí)驗(yàn)?zāi)軌蜻_(dá)到的最高準(zhǔn)確率是96.07%，而最低準(zhǔn)確率僅僅是59.55%，通過其他文獻(xiàn)中提出的算法進(jìn)行的實(shí)驗(yàn)，其準(zhǔn)確率能夠穩(wěn)定的達(dá)到96.63%，但是還是沒有超過本文提出的優(yōu)化的初始中心點(diǎn)選取的K-means聚類算法所達(dá)到97.19%的準(zhǔn)確率。很好地提高了算法的運(yùn)算效率。

4　結(jié)語

隨著互聯(lián)網(wǎng)用戶的增加和數(shù)據(jù)庫的龐大發(fā)展，聚類人物所設(shè)計(jì)的數(shù)據(jù)量越來越龐大，傳統(tǒng)的K-means聚類算法的應(yīng)用相當(dāng)廣范，但其聚類效率和聚類結(jié)果會(huì)隨著初始聚類中心以及數(shù)據(jù)量的改變而改變，嚴(yán)重影響了這種算法聚類的精確度；對(duì)于這個(gè)問題很多研究專家分別從各個(gè)不同的角度對(duì)K-means算法作出了改進(jìn)。在本文中提出了一種優(yōu)化的初始中心點(diǎn)選取的K-means聚類算法，并通過實(shí)驗(yàn)結(jié)果的對(duì)比得出，利用該算法能夠更好地提高聚類的精確度，并且利用計(jì)算過程中通過數(shù)組來存儲(chǔ)對(duì)象的方法，很大地提高了算法的運(yùn)算效率。

［1］周愛武，于亞飛.K-means聚類算法的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011.02：2.

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

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

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

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

［6］顧洪博，張繼懷.改進(jìn)的k-均值算法在聚類分析中的應(yīng)用［J］-西安科技大學(xué)學(xué)報(bào)2010，30（4）.

［7］曹志宇，張忠林，李元韜.快速查找初始聚類中心的K-means算法［J］.蘭州交通大學(xué)學(xué)報(bào)，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-），女，山東濰坊人，在讀碩士研究生，研究方向?yàn)楦酆轿锪鞴芾?/p>

2015－05－13

2015－07－13

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

K-means算法；聚類中心；孤立點(diǎn)

王未央（1963-），女，江蘇常熟人，副教授，研究方向?yàn)閿?shù)據(jù)處理與挖掘

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.