摘 要： 針對初始聚類中心對傳統K-means算法的聚類結果有較大影響的問題，提出一種依據樣本點類內距離動態調整中心點類間距離的初始聚類中心選取方法，由此得到的初始聚類中心點盡可能分散且具代表性，能有效避免K-means算法陷入局部最優。通過UCI數據集上的數據對改進算法進行實驗，結果表明改進的算法提高了聚類的準確性。
關鍵詞： K-means；聚類算法；初始聚類中心；動態聚類
聚類分析[1]是基于數據集客觀存在著若干個自然類，每個自然類中的數據的某些屬性都具有較強的相似性而建立的一種數據描述方法。因而可以講，聚類分析是將給定的一些模式分成若干組，對于多選定的屬性或者特征，每組內的各樣本模式是相似的，而與其他組的樣本模式差別較大。聚類分析有許多具體的算法，從算法策略上看，可以分為如下幾種典型方法：(1)根據相似性閾值和最小距離原則的簡單聚類方法；(2)譜系聚類算法；(3)近鄰函數法；(4)動態聚類法。其他方法基本是由這四種派生而來。
在眾多的聚類方法中，動態聚類法中的K-means算法因其方法簡單、效率高、結果尚令人滿意，因此得到了廣泛的應用。但是K-means算法本身存在缺陷和不足，如K值的選取、初始聚類中心的選取以及對噪聲敏感等問題。學術界對初始聚類中心的選取提出了多種改進算法，如參考文獻[2]提出利用數據樣本的近鄰點信息確定初始聚類中心的方法；參考文獻[3]采用基于密度的思想，將不重復的核心點作為初始聚類中心；參考文獻[4]選擇包含數據樣本最多的K個類中心作為初始聚類中心；黃韜等[5]通過對數據集的多次采樣，選取最終較優的初始聚類中心。這些算法提高了聚類準確性，但初始中心點的選取未能同時兼顧代表性和分散性的特性。
針對樣本點之間的近類內、遠類間的分布特性，本文提出一種依據類內距離動態調整中心點類間距離的初始聚類中心選取方法，得到的初始聚類中心能盡量分散，很好地代表K個簇，并且，掃描一遍數據集即可完成初始聚類中心的選取。實驗表明，與隨機選取初始聚類中心的傳統K-means算法相比，該方法提高了聚類的準確率，使得聚類結果更穩定。
1 K-means算法的基本理論
K-means算法有兩個階段，第一個階段是確定K個中心點，每一類有一個中心點；第二個階段是把數據集的每個樣本點關聯到最近的中心點，并由此循環得到新的K個中心點。循環的結果就是中心點位置不斷地變動，直到穩定不變，標志著聚類收斂。
設待分類的數據集為{x1，x2，…，xC}，聚類的個數為K。算法的具體步驟如下：
在K-means算法中，數據之間的相似度用歐氏距離來衡量，距離越大越不相似，距離越小越相似，兩個簇之間數據太密集就會合并為新的聚類簇，而離兩個聚類簇稀疏的數據就會形成新的簇。因此如果選取兩個簇密集區域的聚類中心的平均值和離簇稀疏的數據作為初始聚類中心，將有利于目標函數的收斂。
由此，本文將依據樣本點實際分布情況，利用類內最短距離調整中心點的類間距離，不斷更新優化初始聚類中心。基本思路如下：(1)隨機選取的K個樣本（記為集合L）作為初始中心點，按式（4）計算這K個數據兩兩之間的最小距離作為初始類間距離limit，設集合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，重復步驟(2)，直至R為空。
假設現在有一個二維數據樣本集合，含有6個樣本點，分成3個聚類簇，如圖1所示。
按照本文的算法思想：(1)首先隨機選取3個初始點A、C、D構成集合L，按式(4)計算這3個數據兩兩之間的最小距離作為初始閾值limit，設集合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}。重復步驟(2)，直到R為空。最終得到的聚類中心接近于聚類算法期望得到的聚類中心。
由上述動態選取初始聚類中心算法得到的聚類中心作為K-means算法的初始聚類中心，即為改進的動態K-means算法。
改進的動態K-means算法的時間復雜度主要由兩部分組成，一部分是生成初始聚類中心的時間，另一部分是迭代所需要的時間。改進的動態K-means算法計算出初始聚類中心需要的時間復雜度為O(K×C×N)，其中K為聚類數，C為所有樣本數據的個數，N為樣本屬性。
3 實驗與結果分析
為驗證改進算法的有效性，本文采用UCI標準數據集中的葡萄酒Wine數據集和鳶尾花Iris數據集。對各數據集的描述如表1所示。
對于表1所描述的數據，本文做對比實驗，比較隨機選取聚類中心的K-means算法和本文改進的動態K-means算法，分別在Wine和Iris數據集上進行10次試驗。本文用隨機的方式選取初始中心點，實驗結果如表2、表3、圖2和圖3所示。
從表2和圖2可以看出，在Wine數據集進行10次實驗，K-means算法的準確率在53.37%~70.22%之間浮動，平均準確率為62.25%；迭代次數最少5次，最多16次，平均迭代次數為9。由此可見，K-means聚類算法結果不穩定，并且受初始中心點影響很大。本文算法平均準確率為70.34%，平均迭代次數為5。從表3和圖3可以看出，在Iris數據集進行10次實驗，K-means算法平均準確率為75%，平均迭代次數為9次，本文算法平均準確率為89.47%，平均迭代次數為7次。實驗結果表明，本文改進的動態K-means算法選取的初始聚類接近簇中心，收斂速度快，準確率高，聚類效果好。
K-means算法的聚類結果受初始聚類中心影響很大且迭代次數多，本文改進的算法優化了初始聚類中心，有效地提高了收斂速度，提高了聚類的準確率。但本文方法受噪聲點影響較大，下一步將對減少噪聲點的影響方面進行學習和研究。
參考文獻
[1] 孫即祥，姚偉，騰書華.模式識別[M].北京：國防工業出版社，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] 張琳，陳燕，汲業，等.一種基于密度的K-means算法研究[J].計算機應用研究，2011，28(11)：4071-4073.
[4] 張瓊，張瑩，白清源，等.基于Leader的K均值改進算法[J].福州大學學報，2008，36(4)：493-496.
[5] 黃韜，劉勝輝，譚艷娜.基于K-means聚類算法的研究[J].計算機技術與發展，2011，21(7)：54-57.