吳廣建 章劍林 袁丁

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

關(guān)鍵詞： K-means算法;聚類K值;手肘法;誤差平方和;肘點(diǎn)

中圖分類號(hào)： TP301.6 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.05.032

本文著錄格式：吳廣建，章劍林，袁丁. 基于K-means的手肘法自動(dòng)獲取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 ?引言

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

1 ?相關(guān)工作

1.1 ?K-means算法原理

K均值算法是一種無監(jiān)督學(xué)習(xí)算法，常被應(yīng)用到數(shù)據(jù)挖掘的領(lǐng)域，是一種比較常用的聚類算法。其基本思想：

（1）隨機(jī)選取數(shù)據(jù)集中的K個(gè)數(shù)據(jù)作為初始 ?中心。

（2）運(yùn)用歐式距離計(jì)算非中心點(diǎn)到聚類中心的距離，數(shù)據(jù)選定最近的中心作為一組

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

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

定義1 ?歐式距離

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

1.2 ?手肘法

1.2.1 ?手肘法思想

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

1.2.2 ?手肘法步驟及定義

輸入：帶特征值的數(shù)據(jù)集，K值的大致范圍。

輸出：每個(gè)K值和對(duì)應(yīng)的SSE值。

1. 根據(jù)K-means進(jìn)行所有K值的聚類。

2. 計(jì)算每個(gè)K值對(duì)應(yīng)的誤差平法和SSE值。

3. 利用工具繪制二維圖形劃出SSE值和K值對(duì)應(yīng)的關(guān)系折線圖。

4. 確認(rèn)最優(yōu)K值。

1.3 ?Spark

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

Spark具有分布式框架的四大特征，高效性、易用性、通用型、兼容性。整個(gè)框架基于內(nèi)存，比MapReduce框架運(yùn)行速度提高一百倍，使用DAG調(diào)度程序、查詢優(yōu)化程序和物理執(zhí)行引擎，支持多種計(jì)算機(jī)操作語言。Spark內(nèi)部的多個(gè)模塊可以協(xié)同工作，優(yōu)化了數(shù)據(jù)在各種場(chǎng)景中的交互。如圖1。

RDD[13]又名抽象分布式數(shù)據(jù)集。它是分布式的數(shù)據(jù)元素，spark會(huì)根據(jù)分區(qū)自動(dòng)將數(shù)據(jù)分發(fā)到集群中。Spark通過創(chuàng)建RDD、轉(zhuǎn)換RDD、RDD求值以及對(duì)RDD進(jìn)行緩存來進(jìn)行數(shù)據(jù)操作。Spark內(nèi)部機(jī)制實(shí)現(xiàn)了k-means算法，其內(nèi)部k-means算法是一種變種的可并行的k-means||算法，優(yōu)化了尋找聚類中心的過程。

2 ?改進(jìn)方法

2.1 ?方法思想

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

2.2 ?數(shù)據(jù)集取樣

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

2.3 ?自動(dòng)獲取K值方法

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

2.4 ?流程圖及偽代碼

具體方法實(shí)現(xiàn)如下：

利用手肘法自動(dòng)獲取K值

輸入：抽樣數(shù)據(jù)集 （s根據(jù)具體數(shù)據(jù)集確認(rèn)），K值范圍

輸出：聚類數(shù)K值

1. 在磁盤或者接口獲取數(shù)據(jù)集

2. data.sample（false，S）進(jìn)行數(shù)據(jù)集非放回抽樣S

3. for（K值范圍）：利用spark K-means聚類算法獲取K值對(duì)應(yīng)誤差平方和，將值放入arr1數(shù)組

4. 利用數(shù)組arr1初始點(diǎn)和結(jié)束點(diǎn)確認(rèn)關(guān)系直線y=ax+b

5. 將每個(gè)K值對(duì)應(yīng)直線的y值放入arr2數(shù)組

6. arr2數(shù)組和arr1數(shù)組根據(jù)對(duì)應(yīng)下標(biāo)相減，結(jié)果放入arr3數(shù)組

7. 獲取arr3數(shù)組最大值對(duì)應(yīng)的下標(biāo)值，再加1，賦值給變量K

8. 返回K值

3 ?實(shí)驗(yàn)結(jié)果和分析

3.1 ?實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

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

本實(shí)驗(yàn)采用UCI機(jī)器學(xué)習(xí)常用數(shù)據(jù)集，選用iris，wine，wdbc三種聚類數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。表1為三種數(shù)據(jù)集的詳細(xì)信息。本實(shí)驗(yàn)用scala語言實(shí)現(xiàn)，在VMware上實(shí)現(xiàn)2個(gè)節(jié)點(diǎn)，1個(gè)master節(jié)點(diǎn)，1個(gè)slave節(jié)點(diǎn)。實(shí)驗(yàn)圖借助matplotlib（python語言中的第三方包）根據(jù)實(shí)驗(yàn)數(shù)據(jù)生成。

3.2 ?實(shí)驗(yàn)內(nèi)容及分析

3.2.1 ?對(duì)數(shù)據(jù)集進(jìn)行隨機(jī)抽樣

下圖圖4和圖5展示了數(shù)據(jù)集抽樣30%和未抽樣對(duì)應(yīng)的手肘法折線圖，由圖可知折線圖輪廓沒有大的變化，可驗(yàn)證數(shù)據(jù)集抽樣的可行性。

3.2.2 ?自動(dòng)獲取K值

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

4 ?結(jié)束語

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

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

參考文獻(xiàn)

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

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

[3] 張靖， 段富. 優(yōu)化初始聚類中心的改進(jìn)k-means算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2013， 34（05）： 1691-1694+1699.

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

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

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

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

[8] 朱思遠(yuǎn)， 張雷. 一種分布式規(guī)則引擎的實(shí)現(xiàn)方法[J]. 軟件， 2015， 36（12）： 158-161

[9] 唐波. 改進(jìn)的K-means聚類算法及應(yīng)用[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] 王書夢(mèng)， 吳曉松. 大數(shù)據(jù)環(huán)境下基于MapReduce 的網(wǎng)絡(luò)輿情熱點(diǎn)發(fā)現(xiàn)[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.