謝娟英，王艷娥

(陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，西安 710062)

1 概述

聚類分析是數(shù)據(jù)挖掘研究的一項(xiàng)重要技術(shù)［1］，屬于無(wú)監(jiān)督機(jī)器學(xué)習(xí)方法，它基于物以類聚原理，分析和探索事物的內(nèi)在聯(lián)系和本質(zhì)。在聚類分析過(guò)程中，以相似度為基礎(chǔ)，使得同一類簇中的模式具有較高的相似度，而不同類簇的模式具有很低的相似度。聚類分析廣泛應(yīng)用于模式識(shí)別、數(shù)據(jù)分析、圖像處理等領(lǐng)域［2］。常用的聚類分析方法包括基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法和基于變換的聚類算法［1-2］。

K-means 算法是一種典型的基于劃分的聚類算法，該算法將一個(gè)含有n 個(gè)樣本的集合劃分為K 個(gè)子集合，其中每個(gè)子集合代表一個(gè)類簇，同一類簇中的樣本具有高度的相似性，不同類簇中的樣本相似度較低。K-means 算法以其思路簡(jiǎn)潔、收斂速度快成為應(yīng)用最廣泛的聚類算法。但傳統(tǒng)K-means 算法需要預(yù)先提供確定的類簇?cái)?shù)K，在K 值給定的前提下，隨機(jī)產(chǎn)生初始聚類中心進(jìn)行聚類，聚類結(jié)果的隨機(jī)性很大，嚴(yán)重依賴于初始聚類中心，經(jīng)常收斂于局部最優(yōu)解。關(guān)于K-means 算法的研究形成2 個(gè)分支，一是如何確定好的初始聚類中心;二是如何確定合適的K 值。

本文在分析關(guān)于K-means 優(yōu)化初始聚類中心研究的基礎(chǔ)上，提出一種基于樣本空間分布的最小方差優(yōu)化K-means 初始聚類中心的聚類算法，以克服現(xiàn)有優(yōu)化K-means 初始聚類中心的算法需要人為選擇一定參數(shù)，聚類結(jié)果嚴(yán)重依賴于參數(shù)選擇的缺點(diǎn)。根據(jù)樣本的分布特征，計(jì)算樣本的相似度、平均距離及方差;選擇方差最小，且相距較遠(yuǎn)(不小于樣本間平均距離)的K 個(gè)樣本作為K-means 算法的初始聚類中心，避免傳統(tǒng)K-means 算法隨機(jī)選取初始聚類中心所導(dǎo)致的聚類結(jié)果不穩(wěn)定和不可靠現(xiàn)象，以及現(xiàn)有優(yōu)化初始聚類中心的K-means 算法過(guò)多依賴于參數(shù)選擇的問(wèn)題。

2 K-means 算法介紹及研究現(xiàn)狀

K-means 算法以類簇?cái)?shù)K 為參數(shù)，將n 個(gè)樣本劃分為互不相交的K 個(gè)類簇，同一類簇中的樣本相似度較高，而不同類簇的樣本相似度較低。常用的相似度判斷是計(jì)算樣本間的歐氏距離。K-means算法的基本思想是:首先從n 個(gè)樣本集中隨機(jī)選擇K 個(gè)樣本作為初始聚類中心，根據(jù)每個(gè)樣本與各個(gè)聚類中心的相似度，將其分配給最相似的聚類中心，得到K 個(gè)互不相交的類簇集合;然后重新計(jì)算每個(gè)類簇的新中心，再將每個(gè)樣本根據(jù)相似性原理分配給最近的簇中心重新計(jì)算每個(gè)類簇的新中心，分配每個(gè)樣本到距離最近的類簇。這個(gè)過(guò)程不斷重復(fù)，直到各個(gè)類簇的中心不再變化，得到原始樣本集合的K 個(gè)互不相交的穩(wěn)定的類簇。

然而，K-means 算法是一個(gè)局部搜索過(guò)程，其聚類結(jié)果依賴于初始聚類中心以及初始劃分［3］，并且K-means 算法的最終結(jié)果只是相對(duì)于初始劃分更好，未必是全局最優(yōu)的劃分［4］。但是，如果初始聚類中心選擇得好，初始劃分按照Forgy 方法產(chǎn)生，即按照最近鄰方法將樣本分配到各個(gè)初始聚類中心產(chǎn)生初始聚類，聚類結(jié)果將會(huì)達(dá)到全局最優(yōu)［5］。為此，諸多學(xué)者致力于K-means 算法的最佳初始聚類中心選擇研究。文獻(xiàn)［6］提出確定性的初始聚類中心選擇方法，根據(jù)樣本的局部密度選擇Kmeans 算法的K 個(gè)初始聚類中心;為提高聚類性能，文獻(xiàn)［7］在K-means 算法的迭代過(guò)程中對(duì)每個(gè)類簇的新中心重新進(jìn)行計(jì)算;文獻(xiàn)［8-9］研究了Kmeans 算法的初始化問(wèn)題;文獻(xiàn)［10］等利用譜方法估計(jì)特征中心得到K-means 算法的初始聚類中心;文獻(xiàn)［11-14］分別采用不同的樣本密度計(jì)算方法估計(jì)樣本點(diǎn)的密度，選擇相互距離最遠(yuǎn)的K 個(gè)處于高密度區(qū)域的樣本作為K-means 算法的初始聚類中心;文獻(xiàn)［15］采用密度敏感度量樣本的相似性，計(jì)算樣本密度，啟發(fā)式地生成K-means 算法的初始聚類中心;文獻(xiàn)［16-17］根據(jù)樣本的空間分布信息以及密度RPCL 算法確定K-means 的初始聚類中心;文獻(xiàn)［18］利用密度網(wǎng)格優(yōu)化K-means 聚類。以上這些優(yōu)化K-mean 算法一定程度上改善了K-mean的聚類性能，但因需要主觀選擇一些參數(shù)，在一定程度上缺少了客觀性。因此，本文基于每個(gè)類簇中心的樣本方差最小原理，提出基于樣本分布緊密度的最小方差優(yōu)化初始聚類中心的K-means 聚類算法。

3 本文算法

傳統(tǒng)K-means 算法隨機(jī)選取的初始聚類中心有可能是一些孤立點(diǎn)或噪聲點(diǎn)，或者不同類簇的初始聚類中心位于同一個(gè)類簇，導(dǎo)致聚類結(jié)果可能偏離數(shù)據(jù)集樣本的真實(shí)分布，得到錯(cuò)誤的聚類結(jié)果，或者使聚類的收斂速度緩慢甚至很難收斂。選取相互距離較遠(yuǎn)的樣本作為初始聚類中心，可避免初始聚類中心可能位于同一類簇的缺陷，但對(duì)噪聲點(diǎn)非常敏感，可能導(dǎo)致聚類結(jié)果的偏差。文獻(xiàn)［6，11-17］分別研究了基于密度優(yōu)化初始聚類中心的K-means 算法，以解決K-means 算法選擇相互距離較遠(yuǎn)的樣本為初始聚類中心時(shí)，可能選擇到噪音點(diǎn)的問(wèn)題。然而，盡管這些研究使得這一問(wèn)題得到一定程度的改善，提高了聚類結(jié)果的準(zhǔn)確性，但是這些文獻(xiàn)中涉及到了密度調(diào)節(jié)系數(shù)或噪聲調(diào)節(jié)系數(shù)，聚類結(jié)果直接依賴于這些參數(shù)的選擇，參數(shù)選擇不好，聚類結(jié)果會(huì)變得非常差。因此，這些研究帶有很大程度上的主觀性，需要對(duì)原始數(shù)據(jù)集有一定的先驗(yàn)知識(shí)和經(jīng)驗(yàn)值，且有些算法的執(zhí)行時(shí)間過(guò)長(zhǎng)，不能處理較大數(shù)據(jù)集。

本文以樣本的方差作為選取K-means 初始聚類中心的啟發(fā)信息，以樣本間的平均距離為半徑，選擇K 個(gè)位于不同區(qū)域且在該區(qū)域方差最小的樣本作為初始聚類中心，不需要其他參數(shù)選擇，提出基于樣本分布緊密度的最小方差優(yōu)化初始聚類中心的Kmeans 聚類算法。根據(jù)方差的定義可知，本文的優(yōu)化K-means 算法選擇的初始聚類中心為緊密度較高，即周圍樣本分布比較密集的樣本，從而保證K-means算法快速地收斂到全局最優(yōu)解或近似全局最優(yōu)解，而且初始聚類中心的選擇無(wú)需人工干預(yù)，不需要輸入任何參數(shù)，保證了K-means 算法聚類結(jié)果的客觀性和穩(wěn)定性。

3.1 算法原理

方差是數(shù)據(jù)集中各數(shù)據(jù)與其平均數(shù)之差的平方和的期望，樣本方差的算術(shù)平方根為樣本標(biāo)準(zhǔn)差［19］。樣本方差與樣本標(biāo)準(zhǔn)差都是衡量一個(gè)樣本波動(dòng)大小的量，樣本方差或樣本標(biāo)準(zhǔn)差越大，樣本數(shù)據(jù)的波動(dòng)就越大。在概率論與數(shù)理統(tǒng)計(jì)中，方差用來(lái)度量隨機(jī)變量與其數(shù)學(xué)期望(即均值)之間的偏離程度。方差和標(biāo)準(zhǔn)差是測(cè)算樣本離散趨勢(shì)最重要和最常用的指標(biāo)。方差是測(cè)算數(shù)值型數(shù)據(jù)離散程度的最重要方法。

K-means 算法的初始聚類中心如果選擇到每一個(gè)類簇的中心，其方差將最小。基于此原理，本文通過(guò)計(jì)算數(shù)據(jù)集所有樣本的方差，以及所有樣本間的距離均值R，啟發(fā)式地選擇位于樣本分布密集區(qū)域，且相距較遠(yuǎn)的樣本為K-means 的初始聚類中心。啟發(fā)式選擇過(guò)程為:首先選擇方差最小的那個(gè)樣本為第一個(gè)類簇的初始中心，以R 為半徑做圓;然后，在圓之外的樣本中，尋找方差最小的樣本作為第二個(gè)類簇的初始中心，以R 為半徑做圓;重復(fù)在剩余樣本中選擇下一個(gè)類簇的初始聚類中心，直到第K 個(gè)類簇的初始中心選擇到。此時(shí)，便得到了K-means 算法的初始聚類中心向量。

3.2 基本概念

假設(shè)待聚類的數(shù)據(jù)集為:

K 個(gè)初始聚類中心分別為C1，C2，…，Ck，用W1，W2，…，Wk表示K 個(gè)類簇所包含的樣本集合，所有樣本的集合為W。

定義1 樣本xi，xj之間的歐氏距離:

定義2 樣本xi到所有樣本距離的平均值:

定義3 樣本xi的方差:

定義4 數(shù)據(jù)集樣本的平均距離:

定義5 聚類誤差平方和:

3.3 算法步驟

算法步驟描述如下:

(1)確定初始聚類中心

1)根據(jù)定義1～定義3 計(jì)算數(shù)據(jù)集中每一個(gè)樣本的方差，在數(shù)據(jù)集W 中尋找方差最小的樣本將其作為第一個(gè)類簇的初始聚類中心C1;根據(jù)定義4計(jì)算數(shù)據(jù)集樣本的平均距離cmean，令:

2)如果c?K，則令c=c +1，在數(shù)據(jù)集W 中尋找方差最小的樣本將其作為第c 個(gè)類簇的初始聚類中心Cc，并令:

否則，找到K 個(gè)初始聚類中心C1，C2，…，Ck，轉(zhuǎn)步驟(2)。

3)轉(zhuǎn)步驟2)。

(2)構(gòu)造初始劃分

1)根據(jù)定義1 計(jì)算數(shù)據(jù)集中每個(gè)樣本到各個(gè)初始聚類中心的距離，根據(jù)相似性原理將樣本分配到距離最近，即最相似的類簇中，得到初始劃分。

2)計(jì)算每一個(gè)類簇中所有樣本的均值，作為該類簇的新中心。

3)根據(jù)定義5 計(jì)算當(dāng)前聚類結(jié)果的聚類誤差平方和E。

(3)重新分配樣本并更新聚類中心

1)根據(jù)定義1 計(jì)算數(shù)據(jù)集中每個(gè)樣本到各個(gè)類簇中心的距離，根據(jù)相似性原理將樣本分配到距離最近的類簇中。

2)計(jì)算每一個(gè)類簇中所有樣本的均值，作為該類簇的新中心。

3)根據(jù)定義5 計(jì)算當(dāng)前聚類結(jié)果的聚類誤差平方和E'。

4)如果E' -E?10-10，即聚類中心不再變化，則算法結(jié)束，輸出聚類結(jié)果;否則，令E=E'，轉(zhuǎn)向步驟3)。

4 仿真實(shí)驗(yàn)

為驗(yàn)證本文算法的聚類效果及其穩(wěn)定性，分別在UCI 數(shù)據(jù)集和隨機(jī)生成的人工模擬數(shù)據(jù)集兩大類數(shù)據(jù)集上進(jìn)行測(cè)試，并與文獻(xiàn)［11，13，15，16］以及傳統(tǒng)K-means 算法的聚類結(jié)果進(jìn)行比較，其中傳統(tǒng)Kmeans 算法的聚類結(jié)果是執(zhí)行100 次的平均值，文獻(xiàn)［11，13，15］的實(shí)驗(yàn)結(jié)果是調(diào)整參數(shù)所取得的最好結(jié)果。各算法聚類結(jié)果的評(píng)價(jià)除采用聚類誤差平方和、聚類時(shí)間、聚類準(zhǔn)確率這些常用評(píng)價(jià)方法外，還采用了外部評(píng)價(jià)法的Rand 指數(shù)、Jaccard 系數(shù)和Adjusted Rand Index 參數(shù)。其中外部評(píng)價(jià)方法是一種基于預(yù)先給定的分布結(jié)構(gòu)，即在數(shù)據(jù)集樣本類標(biāo)已知情況下對(duì)待測(cè)試的聚類算法的聚類性能進(jìn)行評(píng)價(jià)的有效指標(biāo)［16，20-23］，Adjusted Rand Index 參數(shù)是其中最好的聚類有效性評(píng)價(jià)準(zhǔn)則［24］。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)使用的UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)［25］的10 個(gè)測(cè)試聚類算法的常用數(shù)據(jù)集的描述如表1 所示。

表1 實(shí)驗(yàn)所用的UCI 數(shù)據(jù)集描述

測(cè)試本文算法聚類效果的人工模擬數(shù)據(jù)集包含11 組，其中1 組不含噪音，其他10 組分別含有5%，10%，15%，20%，25%，30%，35%，40%，45% 和50%不同比例的噪音。這些人工模擬數(shù)據(jù)集每組都含有3 類分別符合不同正態(tài)分布的600 個(gè)樣本，每類200 個(gè)。第i 類的橫坐標(biāo)x 的均值為縱坐標(biāo)y的均值為，第i類的標(biāo)準(zhǔn)差為σi。噪音樣本分布在第3 類，其標(biāo)準(zhǔn)差為σl。隨機(jī)生成的人工模擬數(shù)據(jù)集的生成參數(shù)如表2 所示。

表2 隨機(jī)生成的人工模擬數(shù)據(jù)集的各項(xiàng)參數(shù)

4.2 實(shí)驗(yàn)結(jié)果與分析

下面分別是本文算法在UCI 數(shù)據(jù)集和人工模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果與分析。需要說(shuō)明的是用于實(shí)驗(yàn)對(duì)比的優(yōu)化初始聚類中心K-means 算法是在最佳參數(shù)設(shè)置下的運(yùn)行結(jié)果。對(duì)比算法嚴(yán)重依賴于參數(shù)調(diào)整，本文采用其他算法的最好實(shí)驗(yàn)結(jié)果與本文算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，以說(shuō)明本文算法的優(yōu)越性。

4.2.1 UCI 數(shù)據(jù)集的聚類結(jié)果與分析

表3 為各算法在10 組UCI 數(shù)據(jù)集上的聚類誤差平方和比較;表4 是各算法在這10 組UCI 數(shù)據(jù)集的聚類時(shí)間比較。表3～表4 中加粗的數(shù)據(jù)表示最佳的聚類結(jié)果，下同。

表3 各算法在UCI 數(shù)據(jù)集的聚類誤差平方和比較

表4 各算法在UCI 數(shù)據(jù)集的聚類時(shí)間比較 s

由表3 聚類誤差平方和比較可見(jiàn)，傳統(tǒng)K-means算法運(yùn)行100 次的平均聚類誤差平方和在Ionosphere 數(shù)據(jù)集最優(yōu)，本文算法在不需要任何初始參數(shù)調(diào)整條件下在該數(shù)據(jù)集上的聚類誤差平方和明顯優(yōu)于文獻(xiàn)［16］的結(jié)果，且不差于文獻(xiàn)［11，13，15］的聚類誤差平方和。表3 的實(shí)驗(yàn)結(jié)果還顯示，本文算法在Iris，Haberman，Balance-scale 3 個(gè)數(shù)據(jù)集上的聚類誤差平方和略高于在文獻(xiàn)［16］的算法，但在其他數(shù)據(jù)集上都取得了很好的聚類效果，特別是在Soybean-small 和new-thyroid 數(shù)據(jù)集上，本文算法的聚類誤差平方和絕對(duì)地優(yōu)于其他優(yōu)化初始聚類中心的K-means 算法的最好聚類誤差平方和，以及傳統(tǒng)K-means 算法的平均實(shí)驗(yàn)結(jié)果。以上聚類誤差平方和的分析可見(jiàn)，本文算法在不需要任何參數(shù)調(diào)整的條件下，得到了很好的初始聚類中心，是一種不依賴任何參數(shù)調(diào)整的優(yōu)化初始聚類中心的K-means 聚類算法。

表4 關(guān)于各算法聚類時(shí)間的比較揭示，傳統(tǒng)Kmeans 聚類算法的運(yùn)行時(shí)間最快;本文算法的運(yùn)行時(shí)間優(yōu)于文獻(xiàn)［11，13，15］優(yōu)化初始聚類中心的Kmeans 算法;與本文在文獻(xiàn)［16］的優(yōu)化初始聚類中心的K-means 聚類算法相比，本文算法只在Pima Indians Diabetes 和Haberman 這2 個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間較快，但是本文算法不需要選擇任何參數(shù)?？傮w時(shí)間分析顯示，本文算法和文獻(xiàn)［16］算法的時(shí)間性能差別不大，不如傳統(tǒng)K-means 快速，但優(yōu)于文獻(xiàn)［11，13，15］的算法。

圖1(a)～圖1(d)分別是各算法的聚類準(zhǔn)確率、聚類結(jié)果的Rand Index 參數(shù)、Jaccard 系數(shù)以及Adjusted Rand Index 參數(shù)的比較。

圖1 UCI 數(shù)據(jù)集的聚類結(jié)果

由圖1(a)關(guān)于聚類準(zhǔn)確率的比較可見(jiàn)，本文算法的聚類準(zhǔn)確率在各個(gè)數(shù)據(jù)集上都最優(yōu)，特別是Iris和Soybean-small 2 個(gè)數(shù)據(jù)集上，本文算法的聚類準(zhǔn)確率接近90%。圖1(b)關(guān)于各算法在10 個(gè)UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)數(shù)據(jù)集上的Rand 指數(shù)可見(jiàn)，本文采用樣本空間分布緊密度啟發(fā)的優(yōu)初始聚類中心Kmeans 算法在9 個(gè)數(shù)據(jù)上取得了最好的實(shí)驗(yàn)結(jié)果;在Iris 數(shù)據(jù)集上，本文算法的性能位居第二，不如文獻(xiàn)［16］優(yōu)化初始聚類中心的K-means 算法的Rand指數(shù)，但優(yōu)于其他優(yōu)化初始聚類中心K-means 算法。圖1(c)關(guān)于各算法聚類結(jié)果的Jaccard 系數(shù)比較可見(jiàn)，本文算法在各個(gè)數(shù)據(jù)集上都最優(yōu)。圖1(d)關(guān)于最有效的聚類結(jié)果評(píng)價(jià)指標(biāo)Adjusted Rand Index 的比較顯示，本文算法具有最好的聚類效果。

以上結(jié)果表明，相比于其他優(yōu)化初始聚類中心的K-means 算法的聚類結(jié)果嚴(yán)重依賴參數(shù)選擇的缺陷，本文算法在不依賴于任何參數(shù)調(diào)整的條件下，可取得較好的聚類效果，并且聚類結(jié)果比較穩(wěn)定。

4.2.2 人工模擬數(shù)據(jù)集的聚類結(jié)果分析

在人工模擬數(shù)據(jù)集上分別運(yùn)行傳統(tǒng)K-means 算法、文獻(xiàn)［11，13，15，16］算法和本文算法，所得聚類誤差平方和如表5 所示;各算法的聚類時(shí)間如表6所示。表5 的聚類誤差平方和比較可見(jiàn)，文獻(xiàn)［13］算法的聚類誤差平方和最小(優(yōu))，本文算法與文獻(xiàn)［15，16］的聚類誤差平方和相同，優(yōu)于傳統(tǒng)Kmeans 算法的聚類誤差平方和，以及文獻(xiàn)［11］的聚類誤差平方和。表6 各算法聚類時(shí)間的比較顯示，K-means 算法運(yùn)行速度最快，文獻(xiàn)［15］算法需要的聚類時(shí)間最長(zhǎng)，本文算法的聚類時(shí)間和文獻(xiàn)［13，16］的聚類時(shí)間基本持平，都優(yōu)于文獻(xiàn)［11］的優(yōu)化Kmeans 聚類算法。從聚類時(shí)間比較可見(jiàn)，本文算法是一種快速的K-means 聚類算法。

表5 人工模擬數(shù)據(jù)集的聚類誤差平方和比較

表6 人工模擬數(shù)據(jù)集的聚類時(shí)間比較 s

圖2(a)～圖2(d)分別展示了各聚類算法的聚類準(zhǔn)確率、聚類結(jié)果的Rand Index 參數(shù)、Jaccard 系數(shù)以及Adjusted Rand Index 參數(shù)。

圖2(a)關(guān)于各算法聚類準(zhǔn)確率的比較顯示，本文算法和文獻(xiàn)［15-16］算法的聚類準(zhǔn)確率相同，都高于文獻(xiàn)［11，13］的優(yōu)化K-means 聚類算法，以及傳統(tǒng)K-means 算法;另外，圖2(a)的實(shí)驗(yàn)結(jié)果顯示Kmeans 算法的聚類準(zhǔn)確率最差。圖2(b)～圖2(d)關(guān)于聚類結(jié)果的外部評(píng)價(jià)參數(shù)Rand 參數(shù)、Jaccard 系數(shù)、Adjusted Rand Index 參數(shù)的比較顯示，本文算法和文獻(xiàn)［15-16］達(dá)到了同樣好的聚類效果，都優(yōu)于文獻(xiàn)［11，13］的算法和傳統(tǒng)K-means 算法;另外，圖2的結(jié)果比較還揭示傳統(tǒng)K-means 算法的聚類效果最差。

圖2 人工模擬數(shù)據(jù)集的聚類結(jié)果

以上關(guān)于人工模擬數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析表明，本文基于樣本分布緊密度的最小方差優(yōu)化初始聚類中心的K-means 算法在含有不同比例噪聲的人工模擬數(shù)據(jù)集上都取得了很好的聚類效果，聚類準(zhǔn)確率高且聚類結(jié)果穩(wěn)定。另外，本文算法的聚類結(jié)果不依賴于任何參數(shù)調(diào)整，而文獻(xiàn)［11，13，15］的聚類算法如果參數(shù)選擇不合適，聚類結(jié)果會(huì)變得非常差。

5 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)K-means 算法初始聚類中心隨機(jī)選取帶來(lái)的聚類結(jié)果不穩(wěn)定，以及現(xiàn)有優(yōu)化初始聚類中心的K-means 算法的參數(shù)選取較多，聚類結(jié)果嚴(yán)重依賴于參數(shù)選擇的問(wèn)題，本文利用類簇中心的樣本方差最小、具有最高緊密度原理，提出了最小方差優(yōu)化初始聚類中心的K-means 聚類算法。UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)數(shù)據(jù)集以及帶有同比例噪音的人工模擬數(shù)據(jù)集的仿真實(shí)驗(yàn)表明，本文算法與傳統(tǒng)K-means 算法以及現(xiàn)有優(yōu)化初始聚類中心的K-means 算法相比，不僅提高了聚類準(zhǔn)確率、聚類結(jié)果穩(wěn)定，而且對(duì)噪音數(shù)據(jù)有較好的免疫性，能客觀地呈現(xiàn)出原始樣本的分布狀況。

［1］Han Jiawei，Kamber M.Data Mining:Concepts and Techniques［M］.2nd ed.Beijing，China:China Machine Press，2011.

［2］孫吉貴，劉 杰，趙連宇.聚類算法研究［J］.軟件學(xué)報(bào)，2008，19(1):48-61.

［3］Pena J M，Lozano J A，Larranaga P.An Empirical Comparison of Four Initialization Methods for the KMeans Algorithm［J］.Pattern Recognition Letters，1999，20(10):1027-1040.

［4］Vance F.Clustering and the Continuous K-Means Algorithm［J］.Los Alamos Science，1994，22:138-134.

［5］Jain A K，Murty M N，F(xiàn)lynn P J.Data Clustering:A Review［J］.ACM Computing Survey，1999，31 (3):264-323.

［6］Kaufman L，Rousseeuw P J.Finding Groups in Data:An Introduction to Cluster Analysis［M］.New York，USA:John Wiley ＆ Sons，Inc.，1990.

［7］Dhillon I S，Guan Yuqiang，Kogan J.Refining Clusters in High Dimensional Text Data［C］//Proceedings of the 2nd SIAM Workshop on Clustering High Dimensional Data.Arlington，USA:［s.n.］，2002:59-66.

［8］Khan S S，Ahmad A.Cluster Center Initialization for Kmeans Clustering［J］.Pattern Recognition Letters，2004，25(11):1293-1302.

［9］Deelers S，Auwatanamongkol S.Enhancing K-means Algorithm with Initial Cluster Centers Derived from Data Partitioning Along the Data Axis with the Highest Variance［J］.Proceedings of World Academy of Science，Engineering and Technology，2007，26:323-328.

［10］錢 線，黃萱菁，吳立德.初始化K-means 的譜方法［J］.自動(dòng)化學(xué)報(bào)，2007，33(4):342-346.

［11］袁 方，周志勇，宋 鑫.初始聚類中心優(yōu)化的Kmeans 算法［J］.計(jì)算機(jī)工程，2007，33(3):65-66.

［12］賴玉霞，劉建平.K-means 算法的初始聚類中心的優(yōu)化［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44(10):147-149.

［13］王塞芳，戴 芳，王萬(wàn)斌，等.基于初始聚類中心優(yōu)化的K-均值算法［J］.計(jì)算機(jī)工程與科學(xué)，2010，32(10):105-107.

［14］韓凌波，王 強(qiáng)，蔣正峰，等.一種改進(jìn)的K-means 初始聚類中心選取算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(17):150-152.

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

［16］謝娟英，郭文娟，謝維信，等.基于樣本空間分布密度的初始聚類中心優(yōu)化K-均值算法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(3):888-892.

［17］謝娟英，郭文娟，謝維信，等.基于密度RPCL 的Kmeans 算法［J］.西北大學(xué)學(xué)報(bào)，2012，32(3):646-650.

［18］米 源，楊 燕，李天瑞.基于密度網(wǎng)格的數(shù)據(jù)流聚類算法［J］.計(jì)算機(jī)科學(xué)，2011，38(12):178-181.

［19］盛 驟，謝式千，潘承毅，等.概率論與數(shù)理統(tǒng)計(jì)［M］.2 版.北京:高等教育出版社，1997.

［20］張惟皎，劉春煌，李芳玉.聚類質(zhì)量的評(píng)價(jià)方法［J］.計(jì)算機(jī)工程，2005，31(20):10-12.

［21］于 劍，程乾生.模糊聚類方法中的最佳聚類數(shù)的搜索范圍［J］.中國(guó)科學(xué):E 輯，2002，32(2):274-280.

［22］楊 燕，靳 蕃，Kamel M.聚類有效性評(píng)價(jià)綜述［J］.計(jì)算機(jī)應(yīng)用研究，2008，41(6):1631-1632.

［23］Hubert L，Arabie P.Comparing Partitions［J］.Journal of Classification，1985，2:193-218.

［24］Vinh N X，Epps J，Nailey J.Information Theoretic Measures for Clustering Comparison:Is a Correction for Chance Necessary?［C］//Proceedings of the 26th International Conference on Machine Learning.Montreal，Canada:［s.n.］，2009:1073-1080.

［25］Frank A，Asuncion A.UCI Machine Learning Repository［D］.Irvine，USA:School of Information and Computer Science，University of California，2010.