基于一種有效性函數的k—means算法

孫秀娟

摘 要：傳統的K-means算法要求事先給出聚類數k值，從而導致聚類質量的下降。本文提出一種基于聚類有效性函數IG的K-means算法，該函數定義為數據特征軸總長度的平方與最小類間距的比值，當比值達到最小時對應的值為最佳聚類數k。而且，與其它有效性函數比較，IG能高效處理簇密度不同的數據集。實驗證明，改進算法提高了聚類質量。

關鍵詞：K-means；聚類；IG

K-means算法是一種最廣泛使用的聚類劃分方法。傳統的K-means算法需要預先指定聚類數k，如果初始k選取得不合適，會使聚類結果產生較大的偏差。多數情況下，聚類數k事先無法確定，因此需要對最佳聚類數k進行搜索。搜索最佳k值的有效方法是構造聚類有效性函數。因此，本文提出一種基于幾何結構的新聚類有效性函數，該函數被定義為數據特征軸總長度的平方與最小類間距的比值，最優聚類數為比值達到最小時對應的k值。

1 改進的k-means算法

1.1 IG函數

一般來說，聚類有效性函數的構造主要是從反映類內緊致性和類間分離度入手，其關鍵在于構造一個能使兩個指標有機結合的數學表達式。本文提出一種新聚類有效性函數，該函數可使以上兩個指標有機結合。聚類有效函數定義如下：

其中λjm是類Cm中數據協方差矩陣的特征值，假設Mm為類Cm中數據對象的平均值， ，Vm是類Cm的中心， 是兩個類中心Vm、Vn的歐氏距離。

1.2 基于IG函數的k-means算法

2 實驗

下面本文使用兩種數據集對聚類有效性函數IG、CH和I進行測試比較。CH函數計算簇間距離和簇內距離的比例，CH值越大，代表聚類效果越好；有效性函數I（k）最大時對應的k值就是最優的簇個數。對每個有效性函數，將其對應的算法（IG對應文中的算法2，將算法2中的IG函數改為CH、I后的算法就是CH、I分別對應的算法）分別運行30次。我們將比較每個有效性函數達到最優時對應的k值。

3 結論

本文提出了一種確定與數據實際分布相符合的簇數目k的有效性函數，該函數定義為計算聚類中數據特征軸總長度的平方與最小類間距之比，當該比值達到最小時，聚類結果是最優的，此時對應的聚類數也是最佳的。實驗表明IG函數與其它有效性函數相比，該函數對類（簇）密度不同的數據集有較好的聚類效果，能正確發現簇的個數。

[參考文獻]

[1]孫士保，秦克云.改進的k-平均聚類算法研究[J].計算機工程，2007，33（13）：200-201.