【摘 要】K-means 算法是最常用的聚類算法之一，有很多的優(yōu)點(diǎn)，但也存在著不足。它不僅對(duì)樣本的輸入順序敏感， 可能產(chǎn)生局部最優(yōu)解，而且受孤立點(diǎn)的影響很大。文章首先探討了k-means算法的思想與實(shí)現(xiàn)，并進(jìn)一步研究了算法優(yōu)缺點(diǎn)。

【關(guān)鍵詞】聚類分析 聚類算法 K- means算法

聚類，即將數(shù)據(jù)對(duì)象按其性質(zhì)特征進(jìn)行分組，使得組內(nèi)數(shù)據(jù)間的相似度最大，而組間的數(shù)據(jù)相似度最小。組通常也被稱為簇。目前已經(jīng)提出許多聚類算法，這些算法可劃分為：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法等?；趧澐值姆椒ň哂袌?jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)，所以，雖然此類聚類技術(shù)出現(xiàn)較早，但依然受到業(yè)界的重視。

一、基于劃分的聚類方法

給定一個(gè)數(shù)據(jù)對(duì)象，該對(duì)象包含了數(shù)據(jù)庫(kù)的N，和簇的數(shù)目以生成算法的基礎(chǔ)上進(jìn)入目標(biāo)組織的數(shù)據(jù)劃分為K個(gè)（K≤N），其中每個(gè)分區(qū)代表一個(gè)集群。這種分工的K滿足以下條件：

（一）每個(gè)分區(qū)包含至少一個(gè)數(shù)據(jù)記錄；

（二）每個(gè)數(shù)據(jù)記錄屬于一個(gè)且只有一個(gè)分區(qū)（注：這需要一些模糊聚類算法可以適當(dāng)放寬）。

對(duì)于一個(gè)給定的K值，給出一個(gè)初始的算法首先劃分方法，迭代法改變師，這樣每次劃分方案，改進(jìn)后的第一個(gè)比以前更好，所謂的好標(biāo)準(zhǔn)是：在同一部門記錄越近越好，不同的分工盡可能記錄。

使用這個(gè)想法算法：k-means算法，K-medoids算法，CLARANS算法。經(jīng)常使用的分區(qū)標(biāo)準(zhǔn)（通常稱為相似性函數(shù)），如距離在同一個(gè)集群的對(duì)象是“相似”，而不同的對(duì)象集群中的“異種”。

二、k-means算法的思想與實(shí)現(xiàn)

基于分區(qū)的聚類算法，k-means算法是最簡(jiǎn)單的。 K-means算法與k n個(gè)對(duì)象作為輸入?yún)?shù)，組合成k個(gè)聚類，結(jié)果使得集群內(nèi)的相似性高，而簇間的相似度低。與k-means算法的過(guò)程如下：

（一）隨機(jī)分配到所有K表對(duì)象非空簇；

（二）計(jì)算出的平均值為每個(gè)群集的平均值，表示相應(yīng)的群集；

（三），根據(jù)它們之間的距離從每個(gè)群集的中心中的每個(gè)對(duì)象，它重新分配到最接近的群集；

（四）把前兩個(gè)）的步驟，直到收斂標(biāo)準(zhǔn)功能。

參考文獻(xiàn)：

[1] 韓家煒.數(shù)據(jù)挖掘——概念與技術(shù)[M]（范明，孟小峰譯）.機(jī)械工業(yè)出版社.2001.

[2] 行小帥，焦李成.數(shù)據(jù)挖掘的聚類方法.電路與系統(tǒng)學(xué)報(bào)，1（2003），59-67.

[3] Aristidis Likas， Nikos Vlassis， Jakob J. Verbeek. The global k-means clustering algorithm. Pattern Recognition 36 （2003） 451-461.

[4] Raymond T. Ng， Jiawei Han. Efficient and Effective Clustering Methods for Spatial Data Mining. Procedings of the 20th VLDB Conference， Santiago， Chile， 1994，144-155.