孫秀娟

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

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

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

1 改進(jìn)的k-means算法

1.1 IG函數(shù)

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

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

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

2 實(shí)驗(yàn)

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

3 結(jié)論

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

[參考文獻(xiàn)]

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