汪美

【摘 要】隨著大數(shù)據(jù)算法的廣泛應(yīng)用與社會(huì)反響越來越大、應(yīng)用領(lǐng)域越來越廣泛，隨之而來的將是算法的逐步研究?jī)?yōu)化與多種實(shí)現(xiàn)。本文將從聚類算法K-means的理論知識(shí)為基準(zhǔn)，討論其優(yōu)缺點(diǎn)并給出不同實(shí)現(xiàn)方式的呈現(xiàn)結(jié)果與差異產(chǎn)生的原因。

【關(guān)鍵詞】大數(shù)據(jù)；K-means；R語(yǔ)言

1、K-means聚類算法簡(jiǎn)介

根據(jù)資料表明，聚類可以認(rèn)為是：一個(gè)類簇內(nèi)的實(shí)體是相似的，不同類簇的實(shí)體是不相似的；一個(gè)類簇是測(cè)試空間中點(diǎn)的會(huì)聚，同一類簇的任意兩個(gè)點(diǎn)間的距離小于不同類簇的任意兩個(gè)點(diǎn)間的距離；類簇可以描述為一個(gè)包含密度相對(duì)較高的點(diǎn)集的多維空間中的連通區(qū)域，它們借助包含密度相對(duì)較低的點(diǎn)集的區(qū)域與其他區(qū)域（類簇）相分離。[1]簡(jiǎn)而言之，聚類是一個(gè)根據(jù)某些數(shù)據(jù)集中程度進(jìn)行分組的構(gòu)造過程，將在某些方面相似的數(shù)據(jù)成員進(jìn)行分類與組織，聚類技術(shù)經(jīng)常被稱為無監(jiān)督學(xué)習(xí)。k均值聚類算法是一種著名的聚類算法，因其簡(jiǎn)單、便捷和高效率的特點(diǎn)令其成為最廣泛使用的聚類算法。

k均值聚類算法（k-means clustering algorithm）是一種迭代求解的聚類分析算法，其步驟是隨機(jī)選取K個(gè)對(duì)象作為初始的聚類中心，然后計(jì)算每個(gè)對(duì)象與各個(gè)種子聚類中心之間的距離，把每個(gè)對(duì)象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對(duì)象就代表一個(gè)聚類。每分配一個(gè)樣本，聚類的聚類中心會(huì)根據(jù)聚類中現(xiàn)有的對(duì)象被重新計(jì)算。這個(gè)過程將不斷重復(fù)直到滿足某個(gè)終止條件。終止條件可以是沒有（或最小數(shù)目）對(duì)象被重新分配給不同的聚類，沒有（或最小數(shù)目）聚類中心再發(fā)生變化，誤差平方和局部最小。

2、K-means的基本思想

K-means算法屬于一種經(jīng)典的聚類算法，一般以歐氏距離作為2 個(gè)樣本相似程度的評(píng)價(jià)指標(biāo)，基本思想如下：

在數(shù)據(jù)集中任意選擇若干個(gè)點(diǎn)作為初始聚類中心點(diǎn)，數(shù)據(jù)集中其他樣本到這些數(shù)據(jù)中心點(diǎn)之間距離，將其歸到距離最小的類中，再通過計(jì)算得到所有歸到各個(gè)類中的樣本的平均值，然后再更新各個(gè)類的中心，直到平方誤差準(zhǔn)則函數(shù)穩(wěn)定在最小值范圍內(nèi)為止[2]。也就是對(duì)于已給定的樣本集，根據(jù)樣本之間的距離差異區(qū)分樣本集為K個(gè)簇，并且讓簇內(nèi)部的點(diǎn)之間盡量緊密連接，而讓簇間的距離盡量的變大。K-means算法設(shè)計(jì)過程.首先，由用戶確定所要聚類的準(zhǔn)確數(shù)目k，并隨機(jī)選擇k個(gè)對(duì)象 （樣本） ，每個(gè)對(duì)象稱為一個(gè)種子，代表一個(gè)簇 （類） 的均值或中心，對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各簇中心的距離將它賦給最近的簇.然后重新計(jì)算每個(gè)簇內(nèi)對(duì)象的平均值形成新的聚類中心，這個(gè)過程重復(fù)進(jìn)行，直到準(zhǔn)則函數(shù)收斂為止。[3]

3、K-means的優(yōu)缺點(diǎn)

3.1優(yōu)點(diǎn)

K-means算法的原理比較簡(jiǎn)單，實(shí)現(xiàn)也很容易，并且收斂速度快，聚類效果較優(yōu)，算法的可解釋度也比較強(qiáng)。主要需要的參數(shù)只有是簇?cái)?shù)k。它的計(jì)算復(fù)雜度也相對(duì)低，為O（Nmq），其中N是數(shù)據(jù)總量，q是迭代次數(shù)，m是類別（即k）。一般來講m、q會(huì)比N小很多，那么，此時(shí)的復(fù)雜度相當(dāng)于O（N），與其它類似的算法相比算是很小的。當(dāng)然也就意味著它能夠在短時(shí)間內(nèi)處理非常多的數(shù)據(jù)，這種特點(diǎn)在如今這個(gè)數(shù)據(jù)爆炸的時(shí)代是非常重要的。為此，k-means目前仍然被各個(gè)企業(yè)廣泛使用。

3.2缺點(diǎn)

聚類分析是數(shù)據(jù)挖掘中的重要分支，其原理是根據(jù)數(shù)據(jù)的相似性將數(shù)據(jù)分配到有差異的類中。聚類分析的應(yīng)用廣泛，為機(jī)器學(xué)習(xí)、人工智能、醫(yī)學(xué)、網(wǎng)絡(luò)安全等領(lǐng)域提供了重要的技術(shù)支持?；趧澐值木垲愂蔷垲愃惴ㄖ休^為常見的算法，由于其簡(jiǎn)單高效的特點(diǎn)得到了各領(lǐng)域廣泛應(yīng)用。其中，較為常見的是K-means聚類算法，其實(shí)現(xiàn)原理簡(jiǎn)單，而且算法效率較高。但是由于K-means算法易受限于初始聚類中心，其應(yīng)用也受到了很多限制。[4]除此之外，K值的選取也不好把握，對(duì)于區(qū)別步兵師很明顯的數(shù)據(jù)集來說比較難以收斂。如果各隱含類別的數(shù)據(jù)不平衡、嚴(yán)重失衡或者各類別的方差不同，那么，聚類效果將會(huì)不佳。采用迭代方法，得到的結(jié)果只是局部最優(yōu)。此外，對(duì)噪音和異常點(diǎn)比較的敏感。分類結(jié)果依賴于分類中心的初始化。對(duì)類別規(guī)模差異大的數(shù)據(jù)效果不友好。K-means對(duì)于距離非常近的類別的分類效果也不好。不適用于categorical的分類?？茖W(xué)家、工程師等也一直在研究不同的方法去克服k-means的缺點(diǎn)。

4、兩種實(shí)現(xiàn)方式及結(jié)果對(duì)比展示

對(duì)于K-means算法，最先要注意的就是k值的選擇。一般來說，我們對(duì)k值的選擇可以依據(jù)對(duì)數(shù)據(jù)的先驗(yàn)經(jīng)驗(yàn)，如果沒有相應(yīng)的先驗(yàn)經(jīng)驗(yàn)知識(shí)，還可以通過交叉驗(yàn)證選擇一個(gè)相對(duì)合適的k值。在確定了k的個(gè)數(shù)后，我們需要選擇k個(gè)初始化的隨機(jī)質(zhì)心，這k個(gè)初始化質(zhì)心的位置數(shù)據(jù)對(duì)最后的聚類分析的結(jié)果和運(yùn)行時(shí)間的長(zhǎng)短以及效率都會(huì)有很大的影響，因此需要選擇合適的k個(gè)質(zhì)心，這些質(zhì)心最好不能距離太近。實(shí)現(xiàn)過程為：

（a）選擇k個(gè)聚類中心點(diǎn)作為初始值

（b）分別計(jì)算數(shù)據(jù)點(diǎn)與這k個(gè)中心各自的距離，按照最小距離原則將其分配到最鄰近聚類

（c）使用每個(gè)聚類中的樣本均值作為新的聚類中心

（d）重復(fù)執(zhí)行步驟（b）和（c），直到聚類中心收斂，不再發(fā)生變化

（e）執(zhí)行結(jié)束，得到k個(gè)聚類

根據(jù)以上步驟繪制mahout聚類點(diǎn)，以及通過R語(yǔ)言實(shí)現(xiàn)聚類點(diǎn)的可視化，結(jié)果如圖。

從圖中可以看到有黑、藍(lán)、綠三種顏色的空心點(diǎn)，這些空心點(diǎn)代表原始的數(shù)據(jù)。圖中的3個(gè)紅色實(shí)點(diǎn)，是R語(yǔ)言kmeans后生成的3個(gè)中心。3個(gè)紫色實(shí)點(diǎn)，是Mahout的kmeans后生成的3個(gè)中心。R語(yǔ)言和Mahout生成的點(diǎn)，并不是重合的，原因可能有：距離算法不一樣，Mahout中，利用的是 “歐氏距離（EuclideanDistanceMeasure）”，而R語(yǔ)言中，默認(rèn)是”Hartigan and Wong”。此外，初始化的中心、迭代次數(shù)不一樣，點(diǎn)合并時(shí)，判斷的”閾值（threshold）”是不一樣的。

5、結(jié)語(yǔ)

本文從對(duì)K-means聚類算法的理論入手，通過總結(jié)、研究并給出本算法的基本思想，并通過圖示表示出來。緊接著，作者對(duì)K-means算法的優(yōu)缺點(diǎn)進(jìn)行了詳細(xì)的分析與鮮明的對(duì)比，本算法雖然存在若干缺點(diǎn)但仍在各個(gè)領(lǐng)域充分應(yīng)用，是因?yàn)樗惴ǖ膹?fù)雜度低，也就意味著它能夠在短時(shí)間內(nèi)處理非常多的數(shù)據(jù)，這在如今這個(gè)大數(shù)據(jù)時(shí)代是非常重要的。本文還提供了mahout聚類點(diǎn)的繪制和通過R語(yǔ)言實(shí)現(xiàn)，并介紹了二者得出不同結(jié)果的原因，也體現(xiàn)了不同算法只能得出在一定范圍內(nèi)相對(duì)正確的結(jié)果。

【參考文獻(xiàn)】

[1]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，2008（01）：48-61.

[2]張建輝. K-means 聚類算法研究及應(yīng)用[D]. 武漢理工大 學(xué)， 2007.

[3]楊善林，李永森，胡笑旋，潘若愚.K-MEANS算法中的K值優(yōu)化問題研究[J].系統(tǒng)工程理論與實(shí)踐，2006（02）：97-101.

[4]胡威. 一種改進(jìn)的 K-means 算法在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用研究[D]. 合肥工業(yè)大學(xué)， 2017.