孫秀娟

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

關(guān)鍵詞：K-means；聚類；IG

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

1 改進的k-means算法

1.1 IG函數(shù)

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

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

1.2 基于IG函數(shù)的k-means算法

2 實驗

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

3 結(jié)論

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

[參考文獻]

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