K均值聚類算法的優化

羅嵐

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

關鍵詞：K均值算法；算法優化；無線傳感器網絡；植物生長條件

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

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

一、K均值聚類算法

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

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

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

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

[step2]計算每一個數據點與這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；否則，算法結束[4]。

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

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

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

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

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

二、K均值聚類算法的優化

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

其次，鑒于簇中心的選擇相當關鍵，為了減小由于簇中心選取不當帶來的誤差，可以在點到簇的每一次指派之后，都適當的增加質心的數量，更新原來的質心。原始的算法規則是所有的點都指派到簇中以后再更新簇中心，這樣操作的局限就在于不能夠及時的更正由于質心不準確而引起聚類效果不佳的影響。而改進后的算法能夠及時調整質心，增量更新，并且可以調整點的相對權值。

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

三、應用

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

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

下面用本文提出的優化算法再次進行聚類分析，具體步驟如下：

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

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

[step3]重新計算簇中心均值，將數據對象重新分配到最相似的聚類簇中。并在點到簇的每一次指派之后，都適當的增加簇中心的數量，更新原來的簇中心。

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

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

由上表可知，優化后的算法與前次結果基本一致，但是優化后算法在得到最終結果的過程中只進行了9次迭代，大大減少了原本算法的迭代次數。減少了工作量和時間空間的復雜度，適合農業中大數據量的分析。

四、總結

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

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

參考文獻：

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

[2]Pang-Ning Tan，Michael Steinbach，Vipin Kumar. 數據挖掘導論[M]. 北京：人民郵電出版社，2011.

[3]董騏瑞. k-均值聚類算法的改進與實現[D]. 長春：吉林大學，2015.

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

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

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

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

[8]張輝宜，孫倩文，袁志祥等. 基于無線傳感器網絡的溫濕度監控系統設計[J]. 計算機技術與發展，2014（11）：246-249.

[9]李春輝. 大數據在農業物聯網中的應用研究[D]. 齊齊哈爾：齊齊哈爾大學，2015.

作者簡介：羅 嵐（1993–），女，漢族，湖南邵陽人，西南民族大學計科學院，研究方向：物聯網方向。