孫秀娟
摘 要:傳統(tǒng)的K-means算法要求事先給出聚類數(shù)k值,從而導(dǎo)致聚類質(zhì)量的下降。本文提出一種基于聚類有效性函數(shù)IG的K-means算法,該函數(shù)定義為數(shù)據(jù)特征軸總長度的平方與最小類間距的比值,當(dāng)比值達到最小時對應(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ù)學(xué)表達式。本文提出一種新聚類有效性函數(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ù)特征軸總長度的平方與最小類間距之比,當(dāng)該比值達到最小時,聚類結(jié)果是最優(yōu)的,此時對應(yīng)的聚類數(shù)也是最佳的。實驗表明IG函數(shù)與其它有效性函數(shù)相比,該函數(shù)對類(簇)密度不同的數(shù)據(jù)集有較好的聚類效果,能正確發(fā)現(xiàn)簇的個數(shù)。
[參考文獻]
[1]孫士保,秦克云.改進的k-平均聚類算法研究[J].計算機工程,2007,33(13):200-201.