蘇州高等職業(yè)技術(shù)學(xué)校 李志偉

K-means聚類算法研究淺析

蘇州高等職業(yè)技術(shù)學(xué)校 李志偉

K-means算法是聚類方法中使用度較高的一種劃分方法，具有明顯的特點(diǎn)及使用優(yōu)勢(shì)。本文主要對(duì)K-means算法工作原理及實(shí)現(xiàn)的一般步驟進(jìn)行簡(jiǎn)介，并分析算法的特點(diǎn)、優(yōu)缺點(diǎn)。希望能夠在清楚算法思想基礎(chǔ)上，能夠?qū)ζ溥M(jìn)行針對(duì)性學(xué)習(xí)、研究和改進(jìn)。

K-means；聚類

1.簡(jiǎn)介

K-means算法于1967年由J.B. Mac Queen提出，在聚類分析廣泛使用。該算法是一種典型的基于距離劃分的聚類算法，它使用距離的評(píng)價(jià)指標(biāo)作為樣本的相似性度量。K-means算法求解對(duì)應(yīng)某一初始聚類中心向量最優(yōu)分類使得評(píng)價(jià)指標(biāo)最小，距離越近其相似度越大。且該算法利用目標(biāo)函數(shù)求極值的方法作為迭代運(yùn)算的調(diào)整規(guī)則。它采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)。K-means算法認(rèn)為簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。它把n個(gè)對(duì)象根據(jù)他們的屬性分為k個(gè)聚類，以便使得所獲得的聚類滿足：同一聚類中的對(duì)象相似度較高；而不同聚類中的對(duì)象相似度較小。

然而初始類聚類中心的選取對(duì)聚類結(jié)果影響很大，原因在于實(shí)現(xiàn)算法的第一步是隨機(jī)選取k個(gè)對(duì)象作為初始聚類的中心，這些初始中心象征性地代表了各個(gè)簇。K-means算法的每次迭代都要對(duì)數(shù)據(jù)集中剩余的每個(gè)對(duì)象重新判歸至最近的簇。當(dāng)數(shù)據(jù)集中所有數(shù)據(jù)對(duì)象都有自己的歸屬簇（或類），一次迭代運(yùn)算就算完成，而新的聚類中心將會(huì)被再次計(jì)算出來。如果在一次迭代前后，聚類結(jié)果不再發(fā)生變化，說明算法已經(jīng)收斂。

到目前為止，K-means算法在科學(xué)和工業(yè)應(yīng)用中影響很大。它廣泛應(yīng)用于模式識(shí)別、圖像處理、機(jī)器學(xué)習(xí)、數(shù)據(jù)解壓縮等領(lǐng)域。除此之外，goole、百度、搜狗等搜索引擎及校內(nèi)的一些數(shù)據(jù)庫進(jìn)行相關(guān)內(nèi)容的檢索算法也是使用的K-means算法。

2.K-means算法原理及流程

K-means算法的工作原理：首先從n個(gè)數(shù)據(jù)對(duì)象（或數(shù)據(jù)集）中任意選取 k個(gè)點(diǎn)作為初始聚類中心，然后計(jì)算各個(gè)樣本到這k個(gè)聚類中心的距離得出相似度，將各樣本點(diǎn)歸化到離它最近（或最相似）的聚類中心所在的類。最后，計(jì)算新形成每個(gè)類的數(shù)據(jù)對(duì)象的平均值來得到新的聚類中心，如果相鄰兩次的聚類中心沒有任何變化，說明樣本調(diào)整結(jié)束，聚類準(zhǔn)則函數(shù)已經(jīng)收斂。不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測(cè)度函數(shù)收斂為止。值得說明的是一般采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)。本算法的一個(gè)特點(diǎn)是在每次迭代中都要考察每個(gè)樣本的分類情況是否有變化。若前后沒有發(fā)生改變，就需要繼續(xù)調(diào)整，待全部樣本調(diào)整完之后，再修改聚類中心，進(jìn)入下一輪迭代。使得最終得到的k個(gè)聚類類內(nèi)緊湊，類間盡可能分散的目的。具體來講，K-means聚類算法實(shí)現(xiàn)的一般步驟如下：（1）選取初始聚類中心：從待劃分?jǐn)?shù)據(jù)集中任意選擇得出；（2）計(jì)算距離得出相似度：根據(jù)每個(gè)聚類對(duì)象的均值，及距離，歸判類屬劃分；（3）重新計(jì)算尚有變化聚類的均值；（4）循環(huán)第（2）-（3）步直到各聚類不再發(fā)生變化完成聚類。

由此可知，K-means 算法的輸入量是k，輸出的是滿足方差最小標(biāo)準(zhǔn)的k個(gè)聚類。然而在將數(shù)據(jù)對(duì)象進(jìn)行聚類的時(shí)候，需滿足條件：類內(nèi)相似度越高越好；類間相似度則越低越好；而聚類的相似度是利用各聚類的中心對(duì)象的均值所獲得一個(gè)中心點(diǎn)（或稱引力中心）來進(jìn)行計(jì)算的。盡管K-means算法過程比較簡(jiǎn)單，但算法中求點(diǎn)群中心的公式對(duì)聚類來講很重要。一般來說，可以使用 X/Y坐標(biāo)的平均值來計(jì)算，也可以用歐氏距離、曼哈頓距離、切比雪夫距離、閔可夫斯基距離、標(biāo)準(zhǔn)化歐氏距離、夾角余弦、相關(guān)系數(shù)或相關(guān)距離中的一種來求。

3.K-means算法優(yōu)缺點(diǎn)分析

由于K-means聚類算法是一種自下而上的聚類方法，通過原理及實(shí)現(xiàn)方法不難得知算法本身的特點(diǎn)和優(yōu)缺點(diǎn)。首先其特點(diǎn)是：（1）指定聚類，即確定聚類數(shù)目條件下，將數(shù)據(jù) 對(duì)象歸化至某一個(gè)聚類，使得它與這個(gè)聚類中心的距離比它到其它聚類中心的距離要近；（2）選定某種距離度量作為樣本（或?qū)ο螅╅g的相似性度量；（3）動(dòng)態(tài)修改聚類中心。在確定評(píng)價(jià)聚類結(jié)果質(zhì)量的好壞的準(zhǔn)則函數(shù)下，用迭代算法找出使準(zhǔn)則函數(shù)取極值的最好的聚類結(jié)果。

K-Means算法的優(yōu)點(diǎn)主要表現(xiàn)出：（1）是一種解決聚類問題的經(jīng)典算法，具有實(shí)現(xiàn)簡(jiǎn)單、計(jì)算速度快的優(yōu)點(diǎn)；（2）對(duì)大數(shù)據(jù)集表現(xiàn)出較高的實(shí)現(xiàn)效率，且伸縮性好；（3）時(shí)間復(fù)雜度為O（nkt），接近于線性，適合大規(guī)模數(shù)據(jù)集。其中n代表數(shù)據(jù)集中對(duì)象的數(shù)量或個(gè)數(shù)，t代表著算法迭代次數(shù)，k代表聚類數(shù)目。一般來說，k＜＜n，t＜＜n 。（4）.k個(gè)聚類劃分具有平方誤差最小的特點(diǎn)。算法適用于用密集型數(shù)據(jù)集，且類間區(qū)別明顯時(shí)的情況。

K-means算法的缺陷主要表現(xiàn)為：（1）聚類數(shù)目或聚類中心個(gè)數(shù)k需要事先給定，但在實(shí)際中k 值的選定是非常難以估計(jì)的，很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適。這對(duì)本條缺陷，可以選擇hierarchical或mean shift算法聚類。（2）聚類結(jié)果對(duì)初值敏感，不同的初始聚類中心可能導(dǎo)致完全不同的聚類結(jié)果。初值選擇不好，可能得不到滿意理想的聚類結(jié)果。有的時(shí)候挑選優(yōu)化的初值，不僅耗時(shí)而且浪費(fèi)系統(tǒng)資源。對(duì)本條缺陷可以使用K-means++算法來改善。（3）在聚類的平均值被定義的情況下才能使用。對(duì)于符號(hào)屬性數(shù)據(jù)集不適用。另外，算法對(duì)含有“噪聲”和孤立點(diǎn)的數(shù)據(jù)集敏感。

4.結(jié)束語

K-means算法作為一種使用度較高的劃分方法，廣泛應(yīng)用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和模式識(shí)別領(lǐng)域中。本文簡(jiǎn)要介紹K-means算法實(shí)現(xiàn)原理及流程，并小結(jié)其特點(diǎn)和優(yōu)缺點(diǎn)。目前，針對(duì)K-means算法的缺點(diǎn)先后提出多種改進(jìn)算法，這將是我們以后研究的方向。