一種K—均值聚類的改進(jìn)算法

郭德超 胡昌盛

【摘 要】聚類分析是一種無(wú)監(jiān)督的學(xué)習(xí)方法，是數(shù)據(jù)挖掘領(lǐng)域進(jìn)行數(shù)據(jù)處理的重要分析工具和方法。K-均值聚類算法是一種典型的基于劃分的方法，該方法的主要優(yōu)點(diǎn)是，算法思想簡(jiǎn)單易行、快速而高效；但是該方法也存在其固有的缺陷：要求預(yù)先給定聚類個(gè)數(shù)；容易陷入局部極小值而得不到全局最優(yōu)解等。針對(duì)以上問(wèn)題，利用分類領(lǐng)域中的特征選擇及特征加權(quán)方法，提出了一種改進(jìn)的特征加權(quán) K-均值聚類算法。實(shí)驗(yàn)結(jié)果證明，所提出的算法能產(chǎn)生質(zhì)量較高的聚類結(jié)果。

【關(guān)鍵詞】聚類分析；K-均值算法；特征加權(quán)

K-均值聚類算法因結(jié)構(gòu)簡(jiǎn)單、快速高效且適用于處理大數(shù)據(jù)集，在眾多科研領(lǐng)域得到廣泛應(yīng)用。但它同時(shí)存在一些缺陷和不足，要求預(yù)先給定聚類個(gè)數(shù)；容易陷入局部極小值而得不到全局最優(yōu)解等。針對(duì)以上問(wèn)題研究人員提出了各種各樣的有效改進(jìn)措施。文獻(xiàn)[1]的作者通過(guò) DBI 聚類指標(biāo)和最大最小距離方法來(lái)自動(dòng)確定最佳聚類數(shù)目，較好地解決了 K-均值聚類算法中聚類數(shù)目 K 值的確定問(wèn)題。文獻(xiàn)[2]提出一種有效的混合聚類算法，在一定程度上克服了 K-均值聚類算法和層次聚類算法各自的缺陷。文獻(xiàn)[3]提出一種基于變長(zhǎng)編碼的改進(jìn)遺傳算法，有效地解決了 K-均值聚類算法對(duì)初始中心選取敏感的問(wèn)題。文獻(xiàn)[4]提出了一種基于密度及最近鄰相似度的初始聚類中心選取方法，大大提高聚類結(jié)果的穩(wěn)定性。文獻(xiàn)[5]提出了一種基于數(shù)據(jù)對(duì)象在空間分布規(guī)律的新的初始聚類中心選取方法，有效解決由于初始中心選取的隨機(jī)性而導(dǎo)致的聚類結(jié)果不穩(wěn)定的問(wèn)題。本文利用分類領(lǐng)域中的特征選擇及特征加權(quán)方法，提出了一種改進(jìn)的特征加權(quán) K-均值聚類算法。實(shí)驗(yàn)結(jié)果證明，所提出的算法能產(chǎn)生質(zhì)量較高的聚類結(jié)果。

2.K-均值算法的改進(jìn)

3.實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文所提出算法的有效性和可行性，選用 UCI 提供的機(jī)器學(xué)習(xí)公共數(shù)據(jù)庫(kù)中的5 個(gè)數(shù)據(jù)集對(duì)本文改進(jìn)的聚類算法的聚類性能進(jìn)行聚類實(shí)驗(yàn)。（見(jiàn)表1）

從表 2 中不難看出，隨機(jī)選取初始聚類中心的傳統(tǒng) K-均值算法得到的聚類結(jié)果準(zhǔn)確率低且不穩(wěn)定，而且對(duì)于有大值屬性存在的 Wine數(shù)據(jù)集，錯(cuò)分?jǐn)?shù)大大增加；而使用本文所設(shè)計(jì)的改進(jìn)聚類算法所得到的聚類結(jié)果不僅準(zhǔn)確率高，而且相對(duì)穩(wěn)定。

4.結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)K-均值算法由于隨機(jī)選取初始聚類中心而導(dǎo)致聚類結(jié)果不穩(wěn)定、準(zhǔn)確率低的缺點(diǎn)，提出了一種改進(jìn)的特征加權(quán)K-均值聚類算法。實(shí)驗(yàn)結(jié)果表明，本文算法可以有效得到準(zhǔn)確率高、較為穩(wěn)定的聚類結(jié)果。

參考文獻(xiàn)：

[1] 馮超.K-means聚類算法的研究：[大連理工大學(xué)碩士學(xué)位論文].大連：大連理工大學(xué)，2007

[2] 曾志雄.一種有效的基于劃分和層次的混合聚類算法.計(jì)算機(jī)應(yīng)用，2007

[3] 范光平.一種基于變長(zhǎng)編碼的遺傳K均值算法研究：[浙江大學(xué)碩士學(xué)位論文].杭州：浙江大學(xué)，2007

[4] 孫可，劉杰，王學(xué)穎.K均值聚類算法初始質(zhì)心選擇的改進(jìn).沈陽(yáng)師范大學(xué)學(xué)報(bào)，2009

[5] 徐義峰，陸春明，徐云青.一種改進(jìn)的K-均值聚類算法. 計(jì)算機(jī)應(yīng)用與軟件，2008

作者簡(jiǎn)介：

郭德超（1978-），男，碩士，研究方向：網(wǎng)絡(luò)信息安全。