摘  要： 針對初始聚類中心對傳統(tǒng)K-means算法的聚類結(jié)果有較大影響的問題,，提出一種依據(jù)樣本點類內(nèi)距離動態(tài)調(diào)整中心點類間距離的初始聚類中心選取方法,，由此得到的初始聚類中心點盡可能分散且具代表性，能有效避免K-means算法陷入局部最優(yōu),。通過UCI數(shù)據(jù)集上的數(shù)據(jù)對改進(jìn)算法進(jìn)行實驗,，結(jié)果表明改進(jìn)的算法提高了聚類的準(zhǔn)確性。
關(guān)鍵詞： K-means,；聚類算法,；初始聚類中心；動態(tài)聚類

    聚類分析[1]是基于數(shù)據(jù)集客觀存在著若干個自然類,，每個自然類中的數(shù)據(jù)的某些屬性都具有較強的相似性而建立的一種數(shù)據(jù)描述方法,。因而可以講，聚類分析是將給定的一些模式分成若干組,，對于多選定的屬性或者特征,，每組內(nèi)的各樣本模式是相似的，而與其他組的樣本模式差別較大,。聚類分析有許多具體的算法,，從算法策略上看，可以分為如下幾種典型方法：(1)根據(jù)相似性閾值和最小距離原則的簡單聚類方法,；(2)譜系聚類算法,；(3)近鄰函數(shù)法；(4)動態(tài)聚類法,。其他方法基本是由這四種派生而來,。
    在眾多的聚類方法中，動態(tài)聚類法中的K-means算法因其方法簡單,、效率高,、結(jié)果尚令人滿意，因此得到了廣泛的應(yīng)用,。但是K-means算法本身存在缺陷和不足,，如K值的選取、初始聚類中心的選取以及對噪聲敏感等問題,。學(xué)術(shù)界對初始聚類中心的選取提出了多種改進(jìn)算法,，如參考文獻(xiàn)[2]提出利用數(shù)據(jù)樣本的近鄰點信息確定初始聚類中心的方法；參考文獻(xiàn)[3]采用基于密度的思想,，將不重復(fù)的核心點作為初始聚類中心,；參考文獻(xiàn)[4]選擇包含數(shù)據(jù)樣本最多的K個類中心作為初始聚類中心；黃韜等[5]通過對數(shù)據(jù)集的多次采樣,，選取最終較優(yōu)的初始聚類中心,。這些算法提高了聚類準(zhǔn)確性,，但初始中心點的選取未能同時兼顧代表性和分散性的特性。
    針對樣本點之間的近類內(nèi),、遠(yuǎn)類間的分布特性,，本文提出一種依據(jù)類內(nèi)距離動態(tài)調(diào)整中心點類間距離的初始聚類中心選取方法，得到的初始聚類中心能盡量分散,，很好地代表K個簇,，并且，掃描一遍數(shù)據(jù)集即可完成初始聚類中心的選取,。實驗表明,，與隨機選取初始聚類中心的傳統(tǒng)K-means算法相比，該方法提高了聚類的準(zhǔn)確率,，使得聚類結(jié)果更穩(wěn)定,。
1 K-means算法的基本理論
    K-means算法有兩個階段，第一個階段是確定K個中心點,，每一類有一個中心點,；第二個階段是把數(shù)據(jù)集的每個樣本點關(guān)聯(lián)到最近的中心點，并由此循環(huán)得到新的K個中心點,。循環(huán)的結(jié)果就是中心點位置不斷地變動,，直到穩(wěn)定不變，標(biāo)志著聚類收斂,。
    設(shè)待分類的數(shù)據(jù)集為{x1，x2,，…,，xC}，聚類的個數(shù)為K,。算法的具體步驟如下：

    在K-means算法中,，數(shù)據(jù)之間的相似度用歐氏距離來衡量，距離越大越不相似,，距離越小越相似,，兩個簇之間數(shù)據(jù)太密集就會合并為新的聚類簇，而離兩個聚類簇稀疏的數(shù)據(jù)就會形成新的簇,。因此如果選取兩個簇密集區(qū)域的聚類中心的平均值和離簇稀疏的數(shù)據(jù)作為初始聚類中心,，將有利于目標(biāo)函數(shù)的收斂。
    由此,，本文將依據(jù)樣本點實際分布情況,，利用類內(nèi)最短距離調(diào)整中心點的類間距離，不斷更新優(yōu)化初始聚類中心,?；舅悸啡缦拢?1)隨機選取的K個樣本（記為集合L）作為初始中心點,，按式（4）計算這K個數(shù)據(jù)兩兩之間的最小距離作為初始類間距離limit，設(shè)集合R=U-L,；(2)按式(4)計算R中任一樣本點到L的最短距離t=Dist[ri,，L](ri表示R中第i個樣本點)，如果t大于limit,，則刪除集合L中最近的兩個點,，把這兩點的中點ri加入到集合L中，更新limit為t,。否則,，不做任何操作；(3)更新R=R-ri,，重復(fù)步驟(2),，直至R為空。
    假設(shè)現(xiàn)在有一個二維數(shù)據(jù)樣本集合,，含有6個樣本點,，分成3個聚類簇，如圖1所示,。

    按照本文的算法思想：(1)首先隨機選取3個初始點A,、C、D構(gòu)成集合L,，按式(4)計算這3個數(shù)據(jù)兩兩之間的最小距離作為初始閾值limit,，設(shè)集合R=U-L={B、E,、F},；(2)按式(4)計算R中任一樣本點到L的最短距離t=Dist[B，L],，若t大于閾值limit,，則刪除集合L中最近的兩個點C和D，并把這兩點的平均值和B加入到集合L中,，更新閾值limit為Dist[B,，L]；(3)更新R=R-B={E,、F},。重復(fù)步驟(2)，直到R為空,。最終得到的聚類中心接近于聚類算法期望得到的聚類中心,。
    由上述動態(tài)選取初始聚類中心算法得到的聚類中心作為K-means算法的初始聚類中心，即為改進(jìn)的動態(tài)K-means算法。
    改進(jìn)的動態(tài)K-means算法的時間復(fù)雜度主要由兩部分組成,，一部分是生成初始聚類中心的時間,，另一部分是迭代所需要的時間。改進(jìn)的動態(tài)K-means算法計算出初始聚類中心需要的時間復(fù)雜度為O(K×C×N),，其中K為聚類數(shù),，C為所有樣本數(shù)據(jù)的個數(shù)，N為樣本屬性,。
3 實驗與結(jié)果分析
    為驗證改進(jìn)算法的有效性,，本文采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集中的葡萄酒Wine數(shù)據(jù)集和鳶尾花Iris數(shù)據(jù)集。對各數(shù)據(jù)集的描述如表1所示,。

    對于表1所描述的數(shù)據(jù),，本文做對比實驗，比較隨機選取聚類中心的K-means算法和本文改進(jìn)的動態(tài)K-means算法,，分別在Wine和Iris數(shù)據(jù)集上進(jìn)行10次試驗,。本文用隨機的方式選取初始中心點，實驗結(jié)果如表2,、表3,、圖2和圖3所示。

    從表2和圖2可以看出,，在Wine數(shù)據(jù)集進(jìn)行10次實驗,，K-means算法的準(zhǔn)確率在53.37%~70.22%之間浮動，平均準(zhǔn)確率為62.25%,；迭代次數(shù)最少5次,，最多16次，平均迭代次數(shù)為9,。由此可見,，K-means聚類算法結(jié)果不穩(wěn)定，并且受初始中心點影響很大,。本文算法平均準(zhǔn)確率為70.34%，平均迭代次數(shù)為5,。從表3和圖3可以看出,，在Iris數(shù)據(jù)集進(jìn)行10次實驗，K-means算法平均準(zhǔn)確率為75%,，平均迭代次數(shù)為9次,，本文算法平均準(zhǔn)確率為89.47%，平均迭代次數(shù)為7次,。實驗結(jié)果表明,，本文改進(jìn)的動態(tài)K-means算法選取的初始聚類接近簇中心，收斂速度快，準(zhǔn)確率高,，聚類效果好,。
    K-means算法的聚類結(jié)果受初始聚類中心影響很大且迭代次數(shù)多，本文改進(jìn)的算法優(yōu)化了初始聚類中心,，有效地提高了收斂速度,，提高了聚類的準(zhǔn)確率。但本文方法受噪聲點影響較大,，下一步將對減少噪聲點的影響方面進(jìn)行學(xué)習(xí)和研究,。
參考文獻(xiàn)
[1] 孫即祥，姚偉,，騰書華.模式識別[M].北京：國防工業(yè)出版社,，2009.
[2] CAO F Y，LIANG J Y,，JIANG G．An initialization method for the K-means algorithm using neighborhood model[J]．Computers＆Mathematics with Applications,，2009，58(3)：474－483．
[3] 張琳,，陳燕,，汲業(yè)，等.一種基于密度的K-means算法研究[J].計算機應(yīng)用研究,，2011,，28(11)：4071-4073.
[4] 張瓊，張瑩,，白清源,，等.基于Leader的K均值改進(jìn)算法[J].福州大學(xué)學(xué)報，2008,，36(4)：493-496.
[5] 黃韜,，劉勝輝，譚艷娜.基于K-means聚類算法的研究[J].計算機技術(shù)與發(fā)展,，2011,，21(7)：54-57.