溫曉敏　唐德玉

摘要：傳統(tǒng)的K-均值算法依賴于初始聚類中心的選取，使聚類結(jié)果只能收斂于局部最優(yōu)解；差分演化算法是一類利用隨機(jī)偏差擾動產(chǎn)生新個體的方式獲得非常好的收斂性的結(jié)果。為了克服K-均值聚類算法的上述缺點(diǎn)，該文提出基于差分演化的K-均值聚類算法，新算法結(jié)合K-均值算法的高效性和差分演化算法的全局優(yōu)化能力，較好地解決了聚類中心優(yōu)化問題。實(shí)驗(yàn)證明，此算法能夠有效改善聚類質(zhì)量。以肝功能疾病為例對新方法在醫(yī)學(xué)中的應(yīng)用進(jìn)行了探討。

關(guān)鍵詞：K-均值算法；聚類；差分演化算法；肝功能疾病診斷

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）08-1900-03

1 概述

隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展，聚類分析[1]被用作數(shù)據(jù)分析、數(shù)據(jù)理解和模式識別的有效工具，其中k均值（K-means）算法是聚類分析中一種被廣泛應(yīng)用的啟發(fā)式方法，具有簡單，快速的優(yōu)點(diǎn)。但K-means算法對初始聚類中心敏感，存在易陷入局部最優(yōu)解的缺點(diǎn)。因此本文重點(diǎn)討論了K-means算法的改進(jìn)，提出一種基于差分演化算法的K-means算法，以肝功能疾病的診斷為例，對新方法是否改進(jìn)了K-means算法進(jìn)行了研究討論。

2 K-均值（K-means）聚類算法

3.2算法描述

4 實(shí)驗(yàn)結(jié)果及其分析

為了驗(yàn)證提出的算法的有效性，利用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的Liver Disorders數(shù)據(jù)集作為測試樣本集。樣本集的實(shí)驗(yàn)資料是取自英國醫(yī)學(xué)研究有限公司于1990年所建立的肝功能疾病資料集。該資料集是對英國保柏健康小組進(jìn)行血液測試，并紀(jì)錄測試結(jié)果而得。資料集中共有345個記錄樣本，6個輸入屬性為連續(xù)性資料，一個類別標(biāo)記屬性（輸出屬性）status，status的值有0與1兩種，當(dāng)status=1時確定病例。樣本集可分為2個種類，這兩類樣本的個數(shù)分別為138、207。

5 結(jié)論

通過對K-means算法的研究，提出了基于差分演化算法的K-means算法。實(shí)驗(yàn)結(jié)果表明，該方法很好地解決了K-means算法易陷入局部最優(yōu)的問題，得到了較好的聚類效果，在醫(yī)學(xué)診斷方面有很大的幫助。

參考文獻(xiàn)：

[1] Han J W， Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.2版.北京：機(jī)械工業(yè)出版社，2007：251-252.

[2] MacQueen J. Some Methods for Classification and Analysis of Multitvariate Observations [C]. Proceeding of the 5th Berkeley symposium on mathematical statistcs and probability. Berkeley，university of California press，1967：281-297.

[3] Lampinen J.A bibliography of differential evolutionalgorithm[EB/OL]. 2002-10-14.

[4] 龔文引.差分演化算法的改進(jìn)及其在聚類分析中的應(yīng)用研究[D].中國地質(zhì)大學(xué)，2010.

[5] 由雪梅，楊連中.求解復(fù)雜問題的差分演化算法研究[D].山東：山東大學(xué).2011.