K-means算法概述

宋慶蘭

隨著經(jīng)濟(jì)、科技的發(fā)展產(chǎn)生了大量的數(shù)據(jù)和爆炸的信息，傳統(tǒng)的處理方法已不能高效快速地對這龐大的數(shù)據(jù)進(jìn)行分析，云計(jì)算和大數(shù)據(jù)應(yīng)運(yùn)而生。當(dāng)前大數(shù)據(jù)已經(jīng)滲透到了人們生活的各個(gè)領(lǐng)域，比如：金融行業(yè)，醫(yī)學(xué)行業(yè)和管理行業(yè)等，其中以IT行業(yè)最為明顯，大數(shù)據(jù)分析最常用的分析方法就是聚類分析。聚類分析的方法大部分可以應(yīng)用于所有對象，簇內(nèi)的對象相似度越高，聚類的效果就越好，聚類算法為了得到改進(jìn)，試圖將相似的對象歸入同一簇，不相似的對象歸到不同簇。很明顯，我們需要一種合適的相似度計(jì)算方法，目前已經(jīng)知道的相似度的計(jì)算方法有歐氏距離、余弦距離以及漢明距離等，在應(yīng)用中要根據(jù)實(shí)際情況選擇合適的相似度計(jì)算方法。當(dāng)然，任何一種算法都存在一定的缺陷，K-means算法也有它的不足之處，但是可以通過一些方法處理后得到更好的聚類結(jié)果。

K-means算法

隨機(jī)從樣本數(shù)據(jù)中輸入聚類個(gè)數(shù)，還有數(shù)據(jù)庫，此數(shù)據(jù)庫包含個(gè)數(shù)據(jù)對象，然后輸出滿足方差最小標(biāo)準(zhǔn)個(gè)聚類，就是K-means算法。K-means算法接受輸入量；為了滿足所獲得的聚類，將個(gè)數(shù)據(jù)對象劃分為個(gè)聚類：相似度較高的為同一聚類中的對象；而不同聚類中的對象相似度較小。

K-means聚類算法的具體流程：

（1）任意選取個(gè)對象作為初始聚類中心；

（2）計(jì)算各個(gè)對象與中心對象的距離；并根據(jù)最小距離對這些對象重新進(jìn)行劃分；

（3）計(jì)算那些重新劃分的對象；

（4）計(jì)算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件時(shí)算法終止；否則返回到（2）。

K-means算法的研究現(xiàn)狀和發(fā)展動(dòng)態(tài)

傳統(tǒng)的K-means算法存在的缺點(diǎn)有：對網(wǎng)頁處理不足的；在文本聚類中有一定的局限性；中心值的個(gè)數(shù)難以確定、孤立點(diǎn)和噪聲也會有較大影響等。傳統(tǒng)K-means算法處理的數(shù)據(jù)僅限于數(shù)值型數(shù)據(jù)，但在實(shí)際生活中，我們要處理并非只有數(shù)值型數(shù)據(jù)，還有可能要處理類屬型的數(shù)據(jù)，甚至是混合屬性特征的數(shù)據(jù)。這時(shí)，傳統(tǒng)的K-means算法不能夠得到有效的結(jié)果，K-means算法可以對類屬性和混合型屬性的對象集進(jìn)行聚類。

基于初始聚類中心優(yōu)化的K-means算法，主要是通過計(jì)算對象相互之間的距離產(chǎn)生密度參數(shù)，非常好地優(yōu)化了傳統(tǒng)K-means算法的缺點(diǎn)。K-means動(dòng)態(tài)聚類算法也考慮到聚類過程中的信息變化，在數(shù)據(jù)量龐大的情況下，通過假定終止條件來減少迭代次數(shù)，降低時(shí)間復(fù)雜度，刪除冗余信息來減少聚類過程中的干擾等方法，K-means動(dòng)態(tài)聚類算法聚類效果得到一定的提高，這就是傳統(tǒng)K-means算法和K-means動(dòng)態(tài)聚類算法的區(qū)別。此外，為了可以獲得數(shù)據(jù)的基本情況，聚類分析被作為其他算法的預(yù)處理步驟，利用聚類對數(shù)據(jù)進(jìn)行預(yù)處理，在此基礎(chǔ)上，要想獲得更深層次的、更有用的信息，還要進(jìn)行特征抽取或分類以提高精確度和挖掘效率，或者對聚類結(jié)果做進(jìn)一步分析，這也更加適應(yīng)現(xiàn)代社會的需要。

針對K-means算法存在受初始值影響大的缺點(diǎn)，本文提出了一種新的K-means++算法。

K-means++算法的改進(jìn)在于初始聚類中心的選擇。K-means++算法選取初始聚類中心時(shí)，按照聚類中心之間的距離盡可能遠(yuǎn)的原則，選擇個(gè)初始聚類中心。K-means++算法選擇初始聚類中心的主要思想是：假如已經(jīng)選擇了（0< <）個(gè)初始聚類中心；再選擇第+1個(gè)聚類中心時(shí)，距離個(gè)聚類中心越遠(yuǎn)的對象，越有可能被選作第1個(gè)聚類中心。

經(jīng)過研究表明，雖然足夠多的實(shí)驗(yàn)次數(shù)和足夠大的迭代次數(shù)，都能使K-means算法和K-means++算法收斂至全局最小值，但K-means++算法的收斂速度更快、效果更好。也證明改進(jìn)后的K-means++算法降低了初始聚類中心對K-means影響，提高了算法的效率和準(zhǔn)確性。

本文主要對K-means算法的研究現(xiàn)狀和發(fā)展?fàn)顟B(tài)進(jìn)行了闡述，并分析了聚類算法中比較有代表性的K-means算法；如何對K-means算法的缺點(diǎn)進(jìn)行改進(jìn)；K-means算法的精簡優(yōu)化；以及如何選擇合適的初始聚類中心，以減少初始值對K-means算法的影響，從而提高算法效率。