羅嵐

摘要：本文主要圍繞K均值聚類算法進(jìn)行研究，詳細(xì)分析了K均值算法的特點，尤其是其不足之處。并針對其現(xiàn)存的幾個明顯不足，提出了可以優(yōu)化的思路和基于該思路的改進(jìn)方法。力求在現(xiàn)基礎(chǔ)上更進(jìn)一步提高K均值算法的準(zhǔn)確率和穩(wěn)定性。

關(guān)鍵詞：K均值算法；算法優(yōu)化；無線傳感器網(wǎng)絡(luò)；植物生長條件

中圖分類號：TP18 文獻(xiàn)識別碼：A 文章編號：1001-828X（2016）002-000-02

在這信息大爆炸的“大數(shù)據(jù)”時代，全球的信息量每秒都在高速增長。僅據(jù)我國的數(shù)據(jù)統(tǒng)計，2014年全國出版的圖書種類就有448431種，期刊9966種，報紙1912種[1]。而數(shù)據(jù)挖掘（DataMining）技術(shù)在這一信息時代顯得尤為關(guān)鍵。它是指在大型數(shù)據(jù)存儲庫中，自動地發(fā)現(xiàn)有用信息的過程[2]。本文著重分析了聚類分析中最為經(jīng)典的算法——K均值（K-means）聚類算法，它是于1957年由Lloyd首次在文獻(xiàn)中提出的[3]，具有簡單、高效的特性。但其本身也存在著明顯的幾個缺陷。比如：聚類數(shù)目對K均值聚類算法過于依賴，對聚類結(jié)果的影響太大。還有對于初始中心點的選取非常敏感，算法很容易陷入局部最優(yōu)，而非全局最優(yōu)等。針對它的幾點不足，本文一一進(jìn)行了分析改進(jìn)。針對初始中心點的選取問題可以采用增量更新中心法，大大減小了因選取不當(dāng)帶來的誤差和影響；對K值的確定可利用數(shù)據(jù)采樣法選擇一個最優(yōu)解。K均值聚類算法通過改進(jìn)后都有效的改善了它的分類性能，取得了較高的分類準(zhǔn)確率和穩(wěn)定性。并且在其具體應(yīng)用上得到了驗證。

一、K均值聚類算法

K均值算法的具體流程如下：

輸入：數(shù)據(jù)集x={x1， x2， ..xn}，聚類數(shù)目k；

輸出：k個類簇cj， j=1，2，..k。

[stepl]令I(lǐng)=1，隨機(jī)選取k個數(shù)據(jù)點作為k個類簇的初始簇中心，mj（I）， j=1，2，..k；

[step2]計算每一個數(shù)據(jù)點與這k個簇中心的距離d（xi， mj， （I）），i=1，2，..n，j=1，2，..k，如果滿足d（xi， mj， （I））=min{d（xi， mj， （I））， j=1，2，..k}，則xi∈Cj；

[step3]計算k個新的聚類中心mj（I+1）= j=1，2，..k；

[step4]判斷：若mj（I+1）≠mj（I）， j=1，2，..k，則I=I+1，返回至step2；否則，算法結(jié)束[4]。

由以上步驟可以看出，K均值算法的實現(xiàn)比較簡單，并且在一定的數(shù)據(jù)量下，運行效率是非常高的。然而，K均值算法也存在著一些明顯的不足還有待改進(jìn)：

第一，對于時間復(fù)雜性和空間復(fù)雜性有要求[5]。K均值聚類算法每次迭代過程都要調(diào)整簇中心及重新分配數(shù)據(jù)點，因此當(dāng)數(shù)據(jù)量比較大時并不適用。

第二，聚類數(shù)K值需事先給出，聚類效果沒有保證。K均值算法的最初步驟就是要確定聚類的個數(shù)K[6]，而往往獲取K值的代價要比K均值聚類算法的代價大得多。

第三，聚類結(jié)果易受噪聲和離群點影響。噪聲和離群點的存在會嚴(yán)重干擾中心的計算，它們所帶來的影響也是不容小覷的。

第四，過度依賴簇中心的選取。K均值算法中首先需要根據(jù)初始聚類中心來確定一個初始劃分，使得K均值算法對初始簇中心點的嚴(yán)重依賴性。

二、K均值聚類算法的優(yōu)化

針對以上問題，本文提出了一種新的改進(jìn)方法。為了避免離群點影響結(jié)果，首先應(yīng)當(dāng)處理好離群點。但是處理它不代表刪掉它。通過預(yù)處理，移除具有異乎尋常影響的點，往往可以有效減少對簇中心選擇的判斷失誤。比如，刪除過小的聚簇，或者將彼此接近的一些聚簇合并成一個更大的聚簇[7]。

其次，鑒于簇中心的選擇相當(dāng)關(guān)鍵，為了減小由于簇中心選取不當(dāng)帶來的誤差，可以在點到簇的每一次指派之后，都適當(dāng)?shù)脑黾淤|(zhì)心的數(shù)量，更新原來的質(zhì)心。原始的算法規(guī)則是所有的點都指派到簇中以后再更新簇中心，這樣操作的局限就在于不能夠及時的更正由于質(zhì)心不準(zhǔn)確而引起聚類效果不佳的影響。而改進(jìn)后的算法能夠及時調(diào)整質(zhì)心，增量更新，并且可以調(diào)整點的相對權(quán)值。

通過在以上兩方面的優(yōu)化之后，再利用數(shù)據(jù)采樣方法，從數(shù)據(jù)集中抽樣若干數(shù)量的數(shù)據(jù)樣本，用不同的K值來進(jìn)行K均值算法聚類，然后選取結(jié)果最優(yōu)的K值作為此算法的初始簇數(shù)目，最后再針對所有的數(shù)據(jù)執(zhí)行最后的K均值算法聚類。這將對聚類的準(zhǔn)確率有著明顯的幫助。

三、應(yīng)用

數(shù)據(jù)挖掘在農(nóng)業(yè)環(huán)境監(jiān)測和植物生長條件完善方面起到非常重要的作用。利用無線傳感器網(wǎng)絡(luò)獲取植株的具體信息數(shù)據(jù)，包括：環(huán)境溫度，空氣濕度，CO2濃度，土壤PH，風(fēng)速等[8]。收集到的數(shù)據(jù)再通過k均值算法得到一個聚類結(jié)果，從結(jié)果中再分析適合植物生長的各方面的條件因素信息，以此來改善植物生長環(huán)境和條件。

數(shù)據(jù)采集整理過后，根據(jù)第2節(jié)介紹的算法步驟，輸入：n個數(shù)據(jù)對象集合Xi，和指定的聚類數(shù)目K。輸出：K個聚類中心和K個聚類集合Cj。通過反復(fù)迭代，最終用15次迭代運算將所有數(shù)據(jù)分為4個聚類簇。然后根據(jù)人工的經(jīng)驗將不同的簇分為優(yōu)、良、中、差四等生長環(huán)境[9]。其中24%的數(shù)據(jù)表示優(yōu)，30%表示良，28%的表示中，18%的表示差。聚類為優(yōu)的狀態(tài)可知道，該植物適合溫度在白天24-26度，在空氣濕度都比較高的時候，空氣中的二氧化碳濃度為300微升/升，光照在3萬到4萬雷克斯，PH值在6-7之間，風(fēng)速以0.47m/s左右為適合。

下面用本文提出的優(yōu)化算法再次進(jìn)行聚類分析，具體步驟如下：

[step1]初始化：選擇4個代表樣本作為初始聚類中心。

[step2]根據(jù)傳感器收集的數(shù)據(jù)類型，計算簇的均值，根據(jù)均值將數(shù)據(jù)分為不同簇。

[step3]重新計算簇中心均值，將數(shù)據(jù)對象重新分配到最相似的聚類簇中。并在點到簇的每一次指派之后，都適當(dāng)?shù)脑黾哟刂行牡臄?shù)量，更新原來的簇中心。

[step4]計算新的聚中心：更新簇均值，重復(fù)以上步驟2和3，直到聚類不再發(fā)生變化，或是達(dá)到最大迭代次數(shù)，那么就算迭代完成。

此算法在每次循環(huán)中，不斷修改中心點，每次的循環(huán)的中心點記錄下來。當(dāng)本次循環(huán)的聚類中心點與下次循環(huán)聚類中心點的值相同，就退出。

由上表可知，優(yōu)化后的算法與前次結(jié)果基本一致，但是優(yōu)化后算法在得到最終結(jié)果的過程中只進(jìn)行了9次迭代，大大減少了原本算法的迭代次數(shù)。減少了工作量和時間空間的復(fù)雜度，適合農(nóng)業(yè)中大數(shù)據(jù)量的分析。

四、總結(jié)

聚類分析是數(shù)據(jù)挖掘的重要技術(shù)和手段之一，是數(shù)據(jù)挖掘領(lǐng)域中的研究熱點之一。K均值聚類算法作為一個發(fā)展最早、并且應(yīng)用最廣的聚類分析算法，因其具有算法思想簡單、易于實現(xiàn)等優(yōu)點已經(jīng)在眾多研究領(lǐng)域得到廣泛而成功的應(yīng)用。但是 K均值聚類算法仍然存在一些不足可以完善的地方。

本文就 K均值聚類算法的四點明顯缺陷進(jìn)行了分析，通過研究分析后提出了優(yōu)化方法。優(yōu)化后的K均值算法可以應(yīng)用到農(nóng)業(yè)領(lǐng)域等各個領(lǐng)域，本來舉了一個適用在探究植物生長條件的例子，由聚類結(jié)果可以知道一個大致的數(shù)據(jù)范圍對植物生長是比較好的，因此，盡量讓那些條件聚集到該條件的變量范圍，采取加溫，增補(bǔ)二氧化碳濃度，增加光照強(qiáng)度的要求等等，讓植物在最佳條件下得到培育。

參考文獻(xiàn)：

[1]中華人民共和國國家統(tǒng)計局. 中國統(tǒng)計年鑒—2015[M]. 北京：中國統(tǒng)計出版社，2015.

[2]Pang-Ning Tan，Michael Steinbach，Vipin Kumar. 數(shù)據(jù)挖掘?qū)д揫M]. 北京：人民郵電出版社，2011.

[3]董騏瑞. k-均值聚類算法的改進(jìn)與實現(xiàn)[D]. 長春：吉林大學(xué)，2015.

[4]蔣帥. k-均值聚類算法研究[D]. 西安：陜西師范大學(xué)，2010.

[5]邵峰晶，于忠清. 數(shù)據(jù)挖掘原理與算法[M]. 北京：中國水利水電出版社，2003.

[6]歐陳委. K-均值聚類算法的研究與改進(jìn)[D]. 長沙：長沙理工大學(xué)，2012.

[7]Xindong Wu，Vipin Kumar. 數(shù)據(jù)挖掘的十大算法[M]. 北京：清華大學(xué)出版社，2013.

[8]張輝宜，孫倩文，袁志祥等. 基于無線傳感器網(wǎng)絡(luò)的溫濕度監(jiān)控系統(tǒng)設(shè)計[J]. 計算機(jī)技術(shù)與發(fā)展，2014（11）：246-249.

[9]李春輝. 大數(shù)據(jù)在農(nóng)業(yè)物聯(lián)網(wǎng)中的應(yīng)用研究[D]. 齊齊哈爾：齊齊哈爾大學(xué)，2015.

作者簡介：羅 嵐（1993–），女，漢族，湖南邵陽人，西南民族大學(xué)計科學(xué)院，研究方向：物聯(lián)網(wǎng)方向。