基于結構系數的K-means 初始聚類中心選擇算法*

李漢波 魏福義 張嘉龍 劉志偉 黃 杰 方月宜

（華南農業大學數學與信息學院 廣州 510642）

1 引言

聚類分析是數據挖掘中的一個重要研究領域。聚類算法是衡量數據相似性的典型算法，它以“物以類聚”的思想，在文檔分析、圖像壓縮［1］、特征提取、圖像分割等領域得到廣泛的應用。Mac-Queen 于1967 年首次提出K-means算法，它基于樣本間相似度對數據進行劃分，具有聚類效果好和收斂速度快等特點，屬硬聚類算法［2］。傳統K-means算法隨機選取初始聚類中心會導致聚類結果不穩定［3］。為了削弱初始聚類中心選取的隨機性對聚類結果不穩定的影響，研究確定初始聚類中心的有效方法具有重要意義。

一個好的聚類算法具備各類中包含的樣本點彼此相似，并且聚類中心在空間分布上盡量分散［4］的特征，這樣才能更好地讓每一類體現不同于其他類的特性。確定聚類中心和數據分類問題一直是大數據研究的熱點內容［5～12］。文獻［13］運用了相異度的概念，通過構造相異度矩陣，選取K 個與其他樣本相異度較低且聚類個數最多的樣本作為初始聚類中心，該算法削弱了傳統算法對初始聚類中心的敏感性，在傳統算法的基礎上具有更高的分類準確率。文獻［14］在文獻［13］的基礎上增加了一個判斷，當最大相異度參數不唯一時，提出了一種合理選取最大相異度參數值的解決方案，改進算法與文獻［13］的算法在準確率和迭代次數方面有所優化。而文獻［15］提出了一種基于最大距離中位數及誤差平方和（SSE）的自適應改進算法，通過SSE變化趨勢決定終止聚類或繼續簇的分裂。本文算法基于文獻［13］的相異度概念，定義一個可變鄰域參數τ，從最小結構系數開始，按結構系數遞增的順序尋找初始聚類中心，直到找到K 個初始聚類中心。本文實驗表明：采用新方法構造的算法相比文獻［13］、文獻［14］以及文獻［15］具有更高的準確率和更少的迭代次數。

2 改進的選取初始聚類中心算法

首先給出基于相異度的四個新概念，在此基礎上推導改進的K-means 選取初始聚類中心的新方法，最后得到基于結構系數的新算法。

2.1 基本概念

設待聚類樣本數據：X={x1，x2，x3，…，xn}，其中xi={xi1，xi2，xi3，…，xim}，n為數據集中的樣本數，m為樣本屬性的個數。

采用三個步驟計算樣本間相異度并構造相異度矩陣［13］：

3）構造相異度矩陣：

記Ri={ri1，ri2，…，rii-1，rii+1，…，rin}，其 中i=1，2，…，n。

定義1 對于樣本xi和鄰域參數τ，從Ri中任意取τ-1個元素求和，和最小的值稱為樣本xi的τ鄰域的結構系數，記為D（τ，x）i。

定義3 對于樣本集X={x1，x2，x3，…，xn}，集合{D(τ，x1)，D(τ，x2)，…，D(τ，xn)}稱為對應參數τ的結構系數集合，記為M（τ）。

由定義2 和定義4 可知，最小結構系數D（τ）對應含有τ個樣本最密集的鄰域。對于樣本集X，若要選取K個聚類中心，則，其中表示數取下整。

2.2 算法思想

本文從τ=出發，計算并確定D（τ）及其對應的鄰域U（τ，x）i，逐步尋找初始聚類中心。

遴選K個初始聚類中心的方法：

1）首先采用三個步驟構造出相異度矩陣，以及計算鄰域的結構系數集合M（τ）；

2）計算M（τ）的最小結構系數D（τ），其對應的樣本不妨設為xi，將樣本xi作為第一個初始聚類中心，同時標記其鄰域U（τ，x）i的內點，并將其結構系數都設置為∞，記新的結構系數集合為M（1τ）；

3）選取M（1τ）中最小結構系數D（τ），其對應的樣本不妨設為xj，將樣本xj作為候選點。若鄰域U（τ，x）j的內點均沒有被標記，則選取xj作為下一個初始聚類中心，并標記其所有內點，同時將內點的結構系數設置為∞。否則，將D（τ，x）j設為∞，隨后選取M（1τ）中最小的元素對應的樣本作為候選點；

4）反復進行以上判斷直至所有樣本的結構系數都為∞，此時得到的初始聚類中心個數記為l0；

5）若l0≥K，則選擇前K 個候選點為初始聚類中心；若l0＜K，則清空初始聚類中心和內點標記；

6）縮小鄰域參數τ，循環以上方法，直到選出K個初始聚類中心。

根據以上分析，得到算法的流程圖如圖1 所示。

圖1 算法流程圖

3 實驗結果與分析

以常用的五個UCI數據集為實驗數據，將本文算法與文獻［5］、文獻［6］和文獻［7］的算法進行對比實驗，驗證新算法的有效性。

3.1 實驗數據集

UCI 數據集作為標準數據集，經常用于測試機器學習算法的性能，為了驗證以上算法選取初始聚類中心的有效性，本文采用UCI 數據集中的Diabetes 數據集、Iris 數據集、Harbeman 數據集、Wine 數據集和Seed 數據集作為實驗數據集，數據集詳細信息如表1所示。

表1 實驗數據集描述信息

由于Diabetes 數據集、Haberman 數據集和Wine 數據集各維度屬性取值范圍差異較大，先對這三個數據集進行零-均值規范化，以便消除屬性差異對聚類性能的影響。對于每一維度屬性，有如下計算公式：

3.2 聚類效果評價指標

衡量聚類算法性能的評價指標有許多種，本文選用準確度和迭代次數作為判定聚類算法性能優劣的指標。設數據要求分為K 類，則準確度的計算公式［14］如下：

其中n 為樣本總量，αi表示被正確劃分為第i 類的樣本數量，MP值越接近1，表示聚類效果越好。

對于數據集要求分為K 類，在保證準確度前提下，迭代次數越少越好。

3.3 實驗結果和分析

表2～表6 分別是文獻［13］、［14］、［15］算法和本文算法在5個UCI數據集上的對比實驗。

表2 Diabetes數據集的實驗結果

表3 Iris數據集的實驗結果

表4 Haberman數據集的實驗結果

表5 Wine數據集的實驗結果

表6 算法在Seed數據集的實驗結果

在Diabetes 數據集中，使用本文算法改進的K-means算法的準確率最高，為71.35%。雖然在迭代次數方面略微高于文獻［14］算法，但與文獻［13］算法持平。由此可見，本文算法對于Diabetes 數據集聚類性能具有改良效果。

對于Iris 數據集，本文算法的準確率為89.33%，準確率效果與文獻［13］、［14］、［15］的算法持平。在迭代次數方面，本文算法與文獻［13］算法性能相同，相比文獻［15］迭代次數減少3 次，但略遜于文獻［14］算法。

在Haberman 數據集中，雖然本文算法在準確度方面略低于文獻［14］算法，但略高于文獻［13］算法。且本文算法的迭代次數為5，均低于文獻［13］和文獻［14］算法的迭代次數。

在Wine 數據集中，本文算法在準確度方面略遜于文獻［13］、［14］算法，但相對于文獻［13］、［14］算法，本文算法的迭代次數較小，收斂速度快。因此，本文算法對于Wine 數據集的改進性能可以接受。

在Seed 數據集中，對比于文獻［15］算法，本文算法能取得相同的準確率，且本文算法的迭代次數為3，遠低于文獻［15］算法。

由表2～表6 的實驗結果可見，相比于文獻［13］、［14］、［15］算法，本文算法均能取得較為良好的聚類效果。

4 結語

K-means算法應用廣泛，但由于其選取初始聚類中心的隨機性，會導致聚類結果不穩定。針對這一缺陷，本文提出鄰域及其結構系數的概念，在充分考慮數據集的整體分布后，結合數據集的局部密集程度和樣本的相異度這兩個性質，選取周圍密集程度較大且相距較遠的樣本作為初始聚類中心，采用依次縮小鄰域的方法，逐個找出K 個不同的初始聚類中心。同時，本文給出了一種數據聚類新方法，不僅得到數據集的K 個初始聚類中心，而且還得到了li=(i=0，1，…，q-1)個初始聚類中心及其對應的數據分類。

實驗結果表明，新方法有效地削弱了傳統K-means算法選取初始聚類中心的盲目性，改進后的算法提高了準確度和減少了迭代次數，具有準確性高和收斂速度快的聚類效果。