基于K-means的手肘法自動獲取K值方法研究

吳廣建 章劍林 袁丁

摘 ?要： 典型的K-means算法利用手肘法選擇合適的K值在實際項目中應用的較多，但是手肘法獲取K值自動性低，以及面對海量數據的處理，效率上也有待提高。提出利用手肘法關系圖初始點和末尾點連接的關系直線，求K值范圍下直線y值與誤差平方和的最大差值的方法，最大差值對應的K值為手肘法的最優肘點，由于手肘法需要多次迭代以及數據集稠密度對關系圖的影響較小，提出利用數據集預抽樣并且將程序部署在spark平臺之上的方式自動獲取手肘法的肘點K值，這樣不僅根據此方法自動獲取K-means最優K值而且提高了大數據集的處理效率。

關鍵詞： K-means算法;聚類K值;手肘法;誤差平方和;肘點

中圖分類號： TP301.6 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.05.032

本文著錄格式：吳廣建，章劍林，袁丁. 基于K-means的手肘法自動獲取K值方法研究[J]. 軟件，2019，40（5）：167170

【Abstract】： The typical k-means algorithm selecting the appropriate K value by elbow method is widely used in practical projects. However， the automation of the elbow method to obtain K value is low， and the efficiency in the face of massive data processing needs to be improved. This paper proposes a method to find the maximum difference between the line y value and the sum of squared errors in the range of K by using the line connecting the initial point and the end point of the elbow normal diagram. Since the elbow method requires multiple iterations and the data set density has little impact on the diagram， it is proposed to automatically obtain K value of the elbow method by pre-sampled data and deploying the program on spark platform. In this way， the optimal k-means k value can be acquired automatically according to this method， and the processing efficiency of large data sets can be improved.

【Key words】： K-means algorithm; Clustering of k-value; Elbow method; Sse value; Elbow point

0 ?引言

近年來，互聯網發展迅速，大數據時代已經到來，海量數據的處理和分析研究已成為學者們的一個重要課題。1967年，MacQueen J提出了一種聚類算法-k-means算法，由于k-means算法易于實現的特點，因此在學術界和工業界得到廣泛應用。學術界對k-means算法自身K值的選擇進行了廣泛的研究。馮等人提出通過生成最小生成樹，并將K個分支的中點的平均值作為聚類中心[1];翟等人通過構造迭代中聚類中心的計算公式和度量函數，確定聚類中心，減少聚類時間[2];張等人通過利用k類中心的個體輪廓系數和每個樣本與類中心之間的距離來選擇優秀的樣本，并將它們的平均值計算為初始聚類中心，從而提高獲得聚類中心的準確性[3];田等人提出一種改進的基于網絡的獲取K值和聚類中心方式在一定程度上減少了誤差[4];陳等人通過改進數據之間相似度測量提高了k-means聚類效果[5];王等人通過確定聚類數搜索范圍的上限和類之間以及類內的相似度，可以確定k均值的特定聚類K ? 值[6];邵等人通過利用多維網絡空間的思想來確定聚類中心，確定聚類K值[7];朱等人對mapreduce引擎進行了研究提出了一種規則的引擎實現方法[8];唐等人用熵值和動態規劃對k-means進行了改進提高了效率和精確度[9]。本文主要研究基于誤差平方和（Sum of Squared Error簡稱SSE）的手肘法獲取K值的算法，由于其實現簡單，在現實中被廣泛應用。因手肘法獲取K值需要借助工具畫出幾何二維圖，人為肉眼識別拐點，自動化低，又因數據量過大時算法迭代次數多，提出一種運行在spark上預抽樣自動獲取K值的方法，方法具有實現簡單，處理大量數據效率高特點。

1 ?相關工作

1.1 ?K-means算法原理

K均值算法是一種無監督學習算法，常被應用到數據挖掘的領域，是一種比較常用的聚類算法。其基本思想：

（1）隨機選取數據集中的K個數據作為初始 ?中心。

（2）運用歐式距離計算非中心點到聚類中心的距離，數據選定最近的中心作為一組

（3）計算每組中非聚類中心到聚類中心和的平均值作為新的聚類中心

（4）重復2，3步驟，直到聚類中心不再變化或者到達最大迭代次數。

定義1 ?歐式距離

歐式距離[10]的全稱為歐幾里得距離，是比較常見的距離度量方式，主要用于度量空間中兩點之間的距離。對于給定的數據集 ， 中的每個對象有m個特征。例如：對象 ? ，其中， 是對象 中m個特征的值。

1.2 ?手肘法

1.2.1 ?手肘法思想

手肘法[11]是一種利用SSE和K值的關系圖確認最優K值的方式，SSE還可以替換為樣本點到聚類中心歐式距離平均值，本文選用SSE。其算法思想為：數據集在K-means算法聚類下，隨著K的不斷增大，數據被分割的更加詳細，聚類中心不斷增多，SSE逐漸減小。當k值小于真實聚類數時，隨著K值的增大，SSE值的變化比較大，關系圖顯示兩點之間的連線會比較陡峭。當k與真實聚類數相等時，隨著K值的增大，SSE值的變化較小，關系圖顯示兩點之間的連線會變得平緩。所以SSE值和K值關系圖是一個“手肘型”的折線圖，“肘部”為最優的K值。

1.2.2 ?手肘法步驟及定義

輸入：帶特征值的數據集，K值的大致范圍。

輸出：每個K值和對應的SSE值。

1. 根據K-means進行所有K值的聚類。

2. 計算每個K值對應的誤差平法和SSE值。

3. 利用工具繪制二維圖形劃出SSE值和K值對應的關系折線圖。

4. 確認最優K值。

1.3 ?Spark

Apache Spark官方定義是一種大規模數據處理的統一分析引擎。Spark是市面上比較火爆的基于內存的分布式大數據計算框架，其內部機制繼承了MapReduce[12]的內部思想，但是不會將數據寫入磁盤，這樣大大提高了該框架的計算速度，對于迭代次數較多的算法尤為重要。

Spark具有分布式框架的四大特征，高效性、易用性、通用型、兼容性。整個框架基于內存，比MapReduce框架運行速度提高一百倍，使用DAG調度程序、查詢優化程序和物理執行引擎，支持多種計算機操作語言。Spark內部的多個模塊可以協同工作，優化了數據在各種場景中的交互。如圖1。

RDD[13]又名抽象分布式數據集。它是分布式的數據元素，spark會根據分區自動將數據分發到集群中。Spark通過創建RDD、轉換RDD、RDD求值以及對RDD進行緩存來進行數據操作。Spark內部機制實現了k-means算法，其內部k-means算法是一種變種的可并行的k-means||算法，優化了尋找聚類中心的過程。

2 ?改進方法

2.1 ?方法思想

由于現在面對海量數據的處理效率慢，手肘法圖的輪廓跟非聚類中心點到聚類中心的距離有關，又因手肘法確定K值需要人員肉眼分辨以及spark分布式平臺實現了K-means算法和優化了獲取聚類初始中心點的問題，因此本文提出了一種運行在spark上數據集預抽樣模型訓練自動獲取K值的方式，不僅提高了處理海量數據的效率而且利用此算法可以方便的獲取K值。

2.2 ?數據集取樣

給定的數據集 ， 中的每個對象有m個特征。從原數據集 中隨機抽取一個較小的數據集 ，令 ，其中， 和 分別代表數據集的個數，s為抽樣比例，s的值為0.1～0.4之間，由于該算法受數據集中異常點的影響較大，當數據集中點之間較為密集以及異常點較少時，s的值可以取的小一些，相反如果異常點較多數據集較離散，s的值應該取大一些，具體根據數據集而定。

2.3 ?自動獲取K值方法

手肘法不確定的因素就是K值的范圍，可以利用可視化工具確認K值的大致范圍，最大邊界值M要大于K值。手肘法中關系折線圖的第一個點和最后一個點連接形成一條直線y=ax+b，利用折線圖中x軸K值獲取直線y=ax+b中對應的y值，記為集合Y= {y1， y2，…， yM}。手肘法折線圖中每個K值對應的誤差平方和（SSE），記為集合Z={z1， z2，…， zM}。集合Y與集合Z中每個對應元素相減得到結果集合H={h1， h2，…， hM}，獲取集合H中的最大值，此最大值對應集合Y或者集合Z的x軸的值就為最優K值，如圖2：K值為3時y=ax+b和SSE差值最大，因此3為最優K值。

2.4 ?流程圖及偽代碼

具體方法實現如下：

利用手肘法自動獲取K值

輸入：抽樣數據集 （s根據具體數據集確認），K值范圍

輸出：聚類數K值

1. 在磁盤或者接口獲取數據集

2. data.sample（false，S）進行數據集非放回抽樣S

3. for（K值范圍）：利用spark K-means聚類算法獲取K值對應誤差平方和，將值放入arr1數組

4. 利用數組arr1初始點和結束點確認關系直線y=ax+b

5. 將每個K值對應直線的y值放入arr2數組

6. arr2數組和arr1數組根據對應下標相減，結果放入arr3數組

7. 獲取arr3數組最大值對應的下標值，再加1，賦值給變量K

8. 返回K值

3 ?實驗結果和分析

3.1 ?實驗環境及數據

硬件環境：Intel（R）Core（TM） i7-6700 CPU 主頻3.4GHz，內存8G ?1T硬盤。軟件環境：Window7 64位操作系統VMware14.0.0，CentOS7，jdk1.8，spark2.3.1，idea。

本實驗采用UCI機器學習常用數據集，選用iris，wine，wdbc三種聚類數據集進行實驗。表1為三種數據集的詳細信息。本實驗用scala語言實現，在VMware上實現2個節點，1個master節點，1個slave節點。實驗圖借助matplotlib（python語言中的第三方包）根據實驗數據生成。

3.2 ?實驗內容及分析

3.2.1 ?對數據集進行隨機抽樣

下圖圖4和圖5展示了數據集抽樣30%和未抽樣對應的手肘法折線圖，由圖可知折線圖輪廓沒有大的變化，可驗證數據集抽樣的可行性。

3.2.2 ?自動獲取K值

利用spark分布式框架進行聚類運算獲取K范圍內每個K對應的誤差平方和，有效的提高了數據量大及數據多次迭代的效率，利用本文提出的方法取1～10，表22為數據集wdbc和iris的實驗數據，其中wdbc為未抽樣數據，iris為抽樣數據，表中只給出K值為1～8的實驗數據值，圖6展示了實驗的效果圖，由圖可直觀的確認最長的紅線所在的X軸坐標為聚類數K值。

4 ?結束語

本文通過將數據集進行預抽樣并提出一種在手肘法基礎上利用關系直線的方式獲取直線與誤差平方和的最大差值，從而獲取肘點最優K值的方式，并將此算法運行在分布式集群spark上。實驗表明該算法數據集預抽樣對于手肘法的關系折線圖輪廓影響不大，抽樣法減少了算法迭代的數據量并且將其部署在spark上從而大大提高了算法的執行效率，根據實驗通過獲取關系直線與SSE最大差值的方式得到最優K值，可以自動獲取手肘法最優K值從而免去繪制二維關系圖的繁瑣過程提高了工作效率。

由于數據集異常點的問題和手肘法本身存在一些缺陷，比如：肘點不明確，K值范圍不確定，下一步進一步研究一下如何去除數據集中異常點以及手肘法中K值范圍的確定問題。

參考文獻

[1] 馮波， 郝文寧， 陳剛， 等. K-means算法初始聚類中心選擇的優化[J]. 計算機工程與應用， 2013， 49（14）： 182-185.

[2] 翟東海， 魚江， 高飛， 于磊， 丁鋒. 最大距離法選取初始簇中心的K-means文本聚類算法的研究[J]. 計算機應用研究， 2014， 31（03）： 713-715+719.

[3] 張靖， 段富. 優化初始聚類中心的改進k-means算法[J]. 計算機工程與設計， 2013， 34（05）： 1691-1694+1699.

[4] 楊婷婷， 王雪梅. 基于百度地圖的改進的K-means算法研究[J]. 軟件， 2016， 37（01）： 76-80

[5] 陳磊磊. 不同距離測度的K-Means 文本聚類研究[J]. 軟件， 2015， 36（1）： 56-61

[6] 王勇， 唐靖， 饒勤菲， 袁巢燕. 高效率的K-means最佳聚類數確定算法[J]. 計算機應用， 2014， 34（05）： 1331-1335.

[7] 邵倫， 周新志， 趙成萍， 張旭. 基于多維網格空間的改進K-means聚類算法[J]. 計算機應用， 2018， 38（10）： 2850-2855.

[8] 朱思遠， 張雷. 一種分布式規則引擎的實現方法[J]. 軟件， 2015， 36（12）： 158-161

[9] 唐波. 改進的K-means聚類算法及應用[J]. 軟件， 2012， 33（03）： 100-104.

[10] LIBERTI L， LAVOR C， MACULAN N， et al. Euclidean distance geometry and applications[J]. Quantiy Bioloy. 2012. 56（1）： 63-69.

[11] Andrew Ng， Clustering with the K-Means Algorithm， Machine Learning， 2012

[12] 王書夢， 吳曉松. 大數據環境下基于MapReduce 的網絡輿情熱點發現[J]. 軟件， 2015， 36（7）： 108-113

[13] S. Gopalani R. Arora "Comparing apache spark and map reduce with performance analysis using k-means" Int. J. Comp. Appl. vol. 113 no. 1 2015.