基于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.