資源描述：
《具有全局優(yōu)化能力的K均值聚類算法.pdf》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、第39卷第7期西南師范大學學報(自然科學版)2014年7月Vo1．39No．7JournalofSouthwestChinaNormalUniversity(NaturalScienceEdition)Ju1．2014具有全局優(yōu)化能力的K均值聚類算法①李彬樂山師范學院智能信息處理及應用實驗室，四JIl樂山614004摘要：傳統(tǒng)的K均值聚類算法是確定性的迭代算法，具有探索能力弱、容易陷入局部最優(yōu)的缺點．在聚類中心的更新過程中加入系數因子線性遞減的隨機項，使改進的迭代算法在前期具有強的探索能力，而在后期保持良好的
2、局部搜索能力，同時保持了傳統(tǒng)K均值聚類算法結構簡單的特點．實例說明，增加了隨機項的K均值聚類算法具有良好的全局優(yōu)化能力．關鍵詞：K均值聚類；確定性的；隨機項；全局最優(yōu)中圖分類號：TP301文獻標志碼：A文章編號：1000—5471(2014)7—0036—05對事物進行分類是人們在日常生活、工業(yè)生產和科學研究中經常遇到的問題．隨著研究的不斷深入，僅僅依靠經驗進行分類已經很難達到要求．將數理統(tǒng)計中的多元分析方法應用到分類問題中，形成了聚類分析這樣一個統(tǒng)計研究領域．聚類分析不僅是數理統(tǒng)計、多元分析的重要內容，它在
3、計算機領域的數據挖掘、圖像識別等方面都有重要應用．曾接賢等將聚類算法用于圖像檢索中，黃月等l_2]在傳感器網絡的多目標定位中用到了聚類分析方法．聚類分析方法的研究內容十分豐富，主要有系統(tǒng)聚類法和動態(tài)聚類法，如粒子群優(yōu)化算法[3]、蟻群聚類算法]、K均值聚類法等等．K均值聚類法是一種重要的動態(tài)聚類算法，因其算法結構簡單、迭代步驟少等優(yōu)點，使得它成為人們在做聚類分析時首先考慮的算法之一．但是K均值聚類算法的探索性能較差，在搜索過程中很容易得到局部最優(yōu)解，算法解的質量很大程度上受初始解的影響，因此很多學者對K均值聚
4、類算法的改進做了大量研究．胡偉結合空間中的層次結構，提出了改進的層次K均值聚類算法．將基于生物群體行為機理的群智能算法應用到K均值聚類算法中，是K均值聚類算法的一個改進方向．如劉靖明等將粒子群算法引入K均值聚類算法中，提高了聚類算法的全局優(yōu)化能力；陶新民等]進一步將改進的粒子群算法與K均值聚類算法相結合，給出了一種混合聚類算法．根據具體問題提出算法的改進措施也是K均值聚類的一個改進方向，如：王紅睿等根據連續(xù)隱馬爾可夫模型進行語音識別時初值提取中訓練矢量分類不均勻的問題，提出了均衡化的改進K均值聚類算法；Ale
5、xandraPi—ryatinskaE等將K均值算法應用于睡眠模式的研究中；余心杰noj研究了結合K均值的遺傳算法聚類分析．雖然以上改進措施在一定程度上提高了K均值聚類算法的全局優(yōu)化能力，但同時也增加了算法結構的復雜性，為得到全局最優(yōu)解，往往要付出較大的時間成本．一個好的優(yōu)化算法應平衡其開發(fā)能力和探索能力．群智能算法是一種很好的優(yōu)化算法，它在迭代過程中通過保留一部分當前的劣解，在保證開發(fā)能力的同時，增強了算法的探索能力，使算法能夠跳出局部最優(yōu)解，具有良好的全局尋優(yōu)能力．基于上述想法，本文在傳統(tǒng)的確定性的K均值
6、聚類算法中，在聚類中心的迭代中增加了一個隨機項，使算法能跳出局部最優(yōu)位置，減小對初值的依賴．為了使更新的聚類中心不至于偏離原數據集太遠，增加的隨機項與原聚類中心和整個數據集的幾何中心的距離有關．同時，隨機項的系數線性地減小，使算法在初期的探索能力強，在后期的開發(fā)能力強．改進算法同時吸收了粒子群算法等群智能算法中使用的最優(yōu)保留策略的優(yōu)點，如果當前的聚類中心差于前一步的聚類中心，就不對聚類中心進行替換，以保證迭代過程①收稿日期：2O14—01—11基金項目：四川省教育廳科研項目(12ZB238)；樂山市科技計劃項
7、目(13GZD051)．作者簡介：李彬(1979一)，女，四川眉山人，講師，碩士，主要從事數據挖掘、網絡安全方面的研究第7期李彬：具有全局優(yōu)化能力的K均值聚類算法37指向更優(yōu)的方向．另外改進措施還保持了傳統(tǒng)K均值聚類算法結構簡單的特點，有利于算法的推廣應用．1傳統(tǒng)的K均值聚類算法設X=：=(，z，?，,27}是D維空間R。中含有個數據的數據集，其中．78ER。．假設根據問題，需要把數據集X分成k個類別C，C。，?，，其中要求X—CUc。U?U，而且C，C一，C兩兩之間互不相交，每個類別ci(J一1，2，?，走
8、)不是空集．令類別C，的幾何中心為1?J一而厶tlIJI∈Cj其中：iC，f表示類別C，中樣本的個數．設數據集x中的每個樣本與其所在類別的中心，的距離為(z，m，)，通常D維空間R。中兩個元素之間的距離可以取為歐氏距離d(x，174．j)：定義總類間離散度為F(1，2，?，)一鬲>—>d。(z，)(3)xiECjF(m，m，?，m)的值度量了分別用k個聚類中心去代表k個類別C，C“，所付出的代價，F
