基于肘部法则优化的K-means聚类算法的应用

第1章绪论1.1研究背景随着科学的发展，互联网技术在逐渐成熟，随之也产生了大量数据，数据种类繁多而复杂。为了能够从杂乱的数据中获取有价值可利用的数据，数据挖掘发挥着非常重要的作用。聚类是数据挖掘中重要的一步，它把众多复杂数据通过不同的聚类方法，产生不同的数据集合，在相同的集合中数据近似一类，因此可以从中获取相同共性，在不同的数据集合中，找到不同，通过异同分析找到我们想要的结果，这就是聚类。目前为止，已提出多种聚类算法，如基于划分的算法[1]、模糊聚类算法[2]、层次聚类算法[3]、密度峰值聚类算法[4]、基于模型算法[5]等。对于不同的数据集合采用不同的聚类方法，针对不同维度的数据集合采用不同的聚类方法，往往聚类效果是不同的，随之也带来了一个问题，如何得到一个我们想要的聚类结果，根据什么来评定聚类的结果，这也是我们要研究的一项重要课题[6][7][8][9]。1.2研究现状及意义聚类分析的重要研究方向是提高算法的有效性和适用性，不断的研究和改进现有的聚类算法，创造出最优的算法，这是算法研究的主体方向。传统的聚类算法已经不能满足当今复杂的大数据时代，因此要开辟新的聚类算法来满足不同的聚类任务。聚类分析应用于很多领域，如图像处理[10]、生物学[11]、信息检索[12]、数据挖掘[13]、音频分析检索[14]和统计学[15]等。聚类分析解决了数据丰富、信息贫乏这一问题，是数据挖掘的一个重要环节，对数据分析具有重要意义。1.3课题主要工作本课题的工作将从下面所叙述的几个方面完成：介绍聚类算法基本流程及优缺点；通过采集数据实验聚类流程；针对java实现K-means聚类算法应用肘部法则和曲率确定k值；实现聚类相似度的衡量；得出最优聚类结果。第2章基本理论概述2.1聚类介绍2.1.1聚类的定义 聚类是把一个繁杂的数据集合分成若干个数据集合，每个数据集合中数据具有相似属性，不同集合中的数据具有相异属性。聚类的表达形式如下：（2-1）其中X为整个数据集，C为每个类，即所有类构成整个数据集合，并且为空。2.1.2聚类的过程聚类是根据数据的相似性，采用合适的算法把相似的数据聚成一类，最后得到结果。聚类的整个过程首先要选取样本数据，即我们要实验的数据，然后我们要根据数据确定好维度，通过聚类算法，把具有相同属性的对象分配到一个簇中，把不同属性的对象分配到不同的簇中，这样就得到了聚类结果。我们根据聚类结果可以根据现实验证，或者采用指标衡量标准衡量得到的结果是否贴近真实，然后给出结果判定，最后根据所得到的结果获取我们所需要的知识。具体实现过程如图2-1-2所示：图2-1-2聚类算法实现2.1.3常见的聚类算法常用的聚类算法按照原理可以分为5类，如图2-1-3所示：图2-1-3常用的聚类分析算法实现基于层次的聚类算法基于层次的聚类算法主要分为两类，其中凝聚层次算法是将每个数据视为一个簇，然后通过迭代数据，将相邻的簇合并在一起，直到所有数据合并为一个簇为止。分裂层次算法是将所有数据视为一个整体，视为一个簇，然后通过迭代将一个簇分裂成多个簇，然后重复迭代，再讲多个簇分为更多的簇，直到分裂为不在有新的簇为止。层次算法的执行步骤如图2-1-3.1所示：图2-1-3.1基于层次的聚类算法执行过程图基于划分的聚类算法基于划分的聚类算法是最开始确定要分的簇，也就是我们最终的聚类结果要分成的类，然后根据最小原则通过迭代将数据，根据每个数据到每个簇的距离，取距离近的，即把该数据分配到该簇中，重复迭代，在这个过程中，有些粗会不断变化，最后直到每个簇不再变化为止。基于划分的聚类算法的执行步骤如图2-1-3.2所示：图2-1-3.2基于划分的聚类算法执行过程图基于网格的聚类算法基于网格的聚类算法的思想是首先将聚类空间划分成表格，然后将我们需要聚类的数据在网格上聚类。主要包括CLIQUE算法，其算法执行步骤如图2-1-3.3所示：图2-1-3.1基于层次的聚类算法执行过程图基于模型的聚类算法基于模型的聚类算法是将我们要聚类的数据与某个模型进行拟合。主要包括EM算法，其算法执行步骤如图2-1-3.4所示：图2-1-3.1基于模型的聚类算法执行过程图基于密度的聚类算法基于密度的聚类算法是根据数据的分布特点，根据密度，将聚集在同一区域的数据划分为一类。主要包括DBSCAN算法，其算法执行步骤如图2-1-3.5所示：图2-1-3.5DBSCAN算法实现过程图2.1.4K-means聚类算法（1）K-means聚类算法的基本思想K-means聚类算法也称k均值聚类算法，它是一种基于距离的聚类算法。采用距离作为参考指标，即数据样本点到簇的距离。该算法的目标是把一个庞大杂乱的数据集合分成若干个小集合，每个集合的数据越相似越好。其步骤是根据输入的数据集合随机选取K个对象作为我们本次实验的初始的聚类中心，然后计算每个每个数据点到每个簇的距离，根据计算结果，把其分配到离它最近的簇中。按照上面步骤重复迭代，确定新的质心，把数据分配到最近的簇，直到没有新的数据被重新分配给不一样的类，没有聚类中心再发生变化，这就完成了K-means聚类。（2）K-means聚类算法的基本流程输入要聚类的数据，聚类的数目即k值，特征维度即我们要根据衡量数据指标的方面，初始化k个聚类中心，分配到距离最近的簇，形成k个簇，判断是否收敛，收敛则直接输出结果，否则，重复迭代直到数据收敛为止。具体流程如图2-1-4所示：图2-1-4聚类流程图K-means聚类算法的优缺点主要优点：K-means算法实现原理简单，代码容易编写；原理简单，计算速度快；思想简洁，好理解，参数少，好控制。主要缺点：k的选取不好确定，事先不知道分为多少类才合适；采用循环迭代方法，迭代后只是得到局部得到了最优，不一定全局最优。2.2肘部法则2.2.1肘部法则的基本思想肘部法则是用来衡量k值好坏的标准，即聚类所要分类的数目，聚类的好坏很大程度上取决于k值的选取，随着聚类数k的不断增大，我们采集的数据样本划分会逐渐精细，这样每个类的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。当k趋近于最优聚类数目是，SSE值下降幅度会很大，当k偏离最优聚类数目时，SSE值随k值增大会逐渐变平缓，然而这个拐点处就是我们要求的最优k值。肘部法则公式如下：（2-2）2.2.2基于曲率的肘部法则（1）曲率的基本思想曲线的曲率是关于曲线弧上某个点的转动率，即曲线偏离直线的程度。曲率表示曲线的弯曲程度。如果一条曲线的曲率越大，表示曲线的弯曲程度越大。如果曲率越小，表示弯曲程度越小，曲率的倒数就是曲率半径。设a，b，c分别是三角形的三边，它的内切圆半径为R，如图2-2-2所示：cacaααbb图2-2-2三角形内切圆图则（2-3）而，（2-4）所以（2-5）又因为圆上任意一点的曲率为该圆半径的倒数，即（2-6）（2）根据曲率确定肘部法则的拐点已知确定k值的肘部法则SSE与k值的关系类似于手肘图形，并且已知拐点处的k值即为最优聚类数目。因为拐点处曲率最大，所以我们可以根据曲率确定哪里是拐点，即根据每相邻三点确定其内接圆，得到内切圆半径，即曲半径，根据半径与曲率关系求出每个k值下的曲率，做出两者关系，观察曲率最大处对应的k值即为肘部法则的拐点。基于肘部法则优化的K-means聚类算法3.1基于肘部法则优化的K-means聚类算法的基本思想根据输入的数据，采用K-means聚类算法，依据特征维度和k值迭代数据，形成k个簇，直到数据收敛，然后选取多个k值重复迭代，得到不同k下的聚类结果。根据肘部法则行程k与SSE的关系，最后根据曲率确定k值的选取，即最佳聚类。3.2基于肘部法则优化的K-means聚类算法的基本流程基于肘部法则优化的K-means聚类算法首先输入数据，根据数据统计层次选取k和数据特征维度，应用K-means聚类算法进行聚类，产生该k值下的聚类结果。循环迭代k，选取多个k值，得到不同k值下得聚类结果。通过不同k下的聚类结果，根据肘部法则确定各个k值的好坏，因为该该关系形成的形状类手肘，有已知手肘的拐点处是最优k值，但是我们通过肉眼观察到的拐点与数据实验的事时是不相符的，因此我们通过曲线的曲率，做出曲率与k的关系，曲率反应的是曲线的弯曲程度，即曲率最大的时候就是最优的k值，得到最优的k值，我们相应的也就得到了该k值下的聚类结果。具体流程如图3-2所示：图3-2基于肘部法则优化的K-means聚类算法的基本流程图第4章基于肘部法则优化的K-means聚类算法的应用4.1数据选取从以下6个方面采集27个城市家庭人均全年消费支出，进行统计，如表4-1所示：表4-1城市居民家庭平均每人全年消费支出统计表地区食品衣着家庭设备用品及服务医疗保健交通和通信居住北京4560.521442.42977.471322.362173.261212.89天津3680.22864.89634.391049.331092.871368.20河北2492.26849.58460.27737.43875.43864.92山西2252.501016.69441.82589.97825.18830.38内蒙古2323.551168.93464.55555.00928.48802.26辽宁3102.13846.91362.10767.13797.64909.42吉林2457.21907.61318.65671.44815.02984.95黑龙江2215.68971.44319.37634.30665.01755.32上海5248.951026.87877.59762.922332.831435.72江苏3462.66886.82647.52600.691203.45997.53浙江4393.401383.63615.45852.272492.01122925安徽3091.28869.55336.99441.42788.25694.17福建3854.26784.71525.65513.611232.701233.49江西2636.93725.72451.32357.03600.16742.93山东2711.651091.22526.29624.061175.57838.17河南2215.32919.31431.02520.57762.08737.00湖北2868.39877.01401.22517.19763.14752.56湖南2850.94868.23513.63632.52965.09871.70广东4503.86719.26633.03707.862394.661254.69广西2857.40477.67360.62401.06785.01826.86海南3079.71375.42405.81369.331154.87743.60重庆3415.921038.98615.74705.72976.02954.56陕西2588.91768.47478.58612.30824.46746.59甘肃2408.37854403.80562.74703.07716.35青海2366.42724.96420.31542.93753.07653.04宁夏2444.98874.39480.70578.75774.57890.97新疆2368.97953.03364.11472.35765.72698.66|4.2数据预处理首先将依据衣着、食品等6各方面统计的北京、上海等27个城市的数据写入txt文件，数据格式标题和数据之间以“/t”分隔，数据与数据之间以“\\s+”分隔，文件编码为gbk，通过java流遍历统计的txt数据文件，根据特征维度将每个城市的统计数据转化成向量。代码如下：publicDataList(Stringin,intnumFeatures)throwsIOException{BufferedReaderreader=newBufferedReader(newInputStreamReader(new FileInputStream(newFile(in)),"gbk"));Strings=null;inti=0;while((s=reader.readLine())!=null){Stringarry[]=s.split("\t");String[]vectorString=arry[1].split("\\s+");Vectorvector=newVector(numFeatures);for(intj=0;j<vectorString.length;j++){vector.set(j,Double.parseDouble(vectorString[j]));}Stringtitle=arry[0];Datadata=newData(i,title);data.setVector(vector);datas.add(data);i++;}reader.close();}4.3仿真模拟实验根据向量集合和k值进行K-means运算，运算时首先清除数据分配，随机选取某个点作为质心，创建一个开始的簇，如果簇的数量小于定义的簇的数量，则给予离质心最远的点，创建新的簇，开始迭代，基于K-means聚类的质心到所采集样本数据点的欧式距离，把剩余数据分配到相应的簇，即计算样本数据中所有未分配的数据点到质心k的距离，比较与各个簇的距离，把其基分配到最近的簇中，基于各维度的算术平均值更新每个簇质心，最后得到k个簇和每个簇的质心，将结果写到文件中。代码如下：publicClusterListrunKMeansClustering(DataListdataList,intk){ClusterListclusterList=newClusterList();dataList.clearIsAllocated();clusterList.add(createClusterWithRandomlySelectedDataPoint(dataList));while(clusterList.size()<k){clusterList.add(createClusterBasedFurthestData(dataList,clusterList));}for(intiter=0;iter<clusteringIterations;iter++){assignUnallocatedDataPoints(dataList,clusterList);clusterList.updateCentroids();if(iter<clusteringIterations-1){clusterList.clear();}}returnclusterList;}4.4实验结果与分析通过K-means算法进行聚类分析：得到每个簇的质心，计算每个簇中数据点距离质心的欧氏距离，形成k与该距离之间的关系，迭代k值。当k=2时，分为2类，数据点到质心的欧式距离如图4-4-1所示，聚类结果如图4-4-2所示：图4-4-1数据点到质心欧氏距离与k的关系图图4-4-2k=2时聚类结果图当k=3时，分为3类，数据点到质心的欧式距离如图4-4-3所示，聚类结果如图4-4-4所示：图4-4-3数据点到质心欧氏距离与k的关系图图4-4-4k=3时聚类结果图当k=4时，分为4类，数据点到质心的欧式距离如图4-4-5所示，聚类结果如图4-4-6所示：图4-4-5数据点到质心欧氏距离与k的关系图图4-4-6k=4时聚类结果图当k=5时，分为5类，数据点到质心的欧式距离如图4-4-7所示，聚类结果如图4-4-8所示：图4-4-7数据点到质心欧氏距离与k的关系图图4-4-8k=5时聚类结果图当k=6时,分为6类，数据点到质心的欧式距离如图4-4-9所示，聚类结果如图4-4-10所示：图4-4-9数据点到质心欧氏距离与k的关系图图4-4-10k=6时聚类结果图当k=7时,分为7类，数据点到质心的欧式距离如图4-4-11所示，聚类结果如图4-4-12所示：图4-4-11数据点到质心欧氏距离与k的关系图图4-4-12k=7时聚类结果图当k=8时,分为8类，数据点到质心的欧式距离如图4-4-13所示，聚类结果如图4-4-14所示：图4-4-13数据点到质心欧氏距离与k的关系图图4-4-14k=8时聚类结果图当k=9时，分为9类，数据点到质心的欧式距离如图4-4-15所示，聚类结果如图4-4-16所示：图4-4-15数据点到质心欧氏距离与k的关系图图4-4-16k=9时聚类结果图根据聚类结果分析k值，取多个k值分别进行聚类，并记录k和对应SSE的值。代码如下：publicclassSSE{ publicstaticvoidchooseK(intk,intfeature_number)throwsIOException{ doublesseNew=0; intflag=1; for(inti=0;i<k;i++){ Stringfileinput="C:\\k-means"+flag+".txt"; DataListdocumentList=newDataList(fileinput,feature_number); Vectorvector=newVector(feature_number); double[]values=newdouble[feature_number]; for(inti0=0;i0<feature_number;i0++){ values[i0]=documentList.get(0).getVector().get(i0); vector.set(i0,values[i0]); } doubledistnce=0; doublesse=0; for(intj=1;j<documentList.size();j++){