数据挖掘中基于肘部法则的聚类分析在中小学生出行路线优化设计的应用

沈阳理工大学自动化与电气工程学院 郑英鑫

数据挖掘中基于肘部法则的聚类分析在中小学生出行路线优化设计的应用

沈阳理工大学自动化与电气工程学院 郑英鑫

本文介绍了在数据挖掘中，采用K-Means聚类分析算法对数据进行分析与挖掘。但由于K-Means使用时，初始重心是随机选取的，因此很容易陷入局部最优解。为解决该问题，引入了肘部法则（Elbow）。K-Means通常初始时要重复运行十几次甚至上百次，这时采用肘部法则计算出最小的成本函数对应的重心位置作为初始化位置，就很好的改善了局部最优解问题。

聚类分析；K-Means算法；肘部法则

1.引言

“数据挖掘(Data Mining)”这个概念最早是由Usama Fayaad1995年加拿大蒙特利尔的第一届知识发现和数据挖掘国际会议上提出的。数据挖掘是从大量的数据中“挖掘”或者提取知识[1]。数据挖掘的知识模式有：概念/类描述、关联模式、分类、聚类分析、预测、时间序列、偏差检测。

数据挖掘源于多个学科，将聚类分析应用到数据挖掘这样一个多学科交叉的复杂领域，必定需要满足一些要求，主要标准有：可伸缩性、能够发现任意形状的簇、能够处理不同数据类型属性、能够处理带噪声的数据、高维性、对于决定输入参数的领域知识需求最小化、对于输入记录的次序不敏感性和允许增量聚类、基于约束的聚类、可解释性和可用性。在保证这些要求的前提下，合理运用聚类分析算法对数据进行分析与挖掘。

2.K-Means聚类算法

K-Means算法是1967年由MacQueen首次提出的一种经典算法，经常用于数据挖掘和模式识别中，是一种无监督式的学习算法，其使用目的是对几何进行等价类的划分，即对一组具有相同数据结构的记录按某种分类准则进行分类，以获取若干个同类记录集[2]。K-Means算法具体实现步骤：

首先从n个数据对象中任意选择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据他们与这些聚类中心的相似度（距离），分别将他们分配给与其最相似的（聚类中心所代表的）聚类。然后再计算每个所新聚类的聚类中心（该聚类中所有对象的均值）。不断重复这一过程直到标准测度函数开始收敛为止。一般采用均方差作为标准测度函数，以欧式距离作为判断数据间相似度的依据。

3.基于Elbow-K-Means的聚类分析

K-Means的初始重心位置是随机选择的，随机选择的重心会导致K-Means陷入局部最优解，这样分类可能失去了实际意义。为了避免局部最优解，K-Means通常初始时要重复运行十几次甚至上百次。每次重复时，它会随机的从不同的位置开始初始化。最后把最小的成本函数对应的重心位置作为初始化位置。

肘部法则（Elbow）会把不同K值的成本函数值画出来。随着K值的增大，平均畸变程度会减小。每个类包含的样本数会减少，于是样本离其重心会更近。但是，随着K值继续增大，平均畸变程度的改善效果会不断减低。K值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的K值就是肘部。

4.仿真结果

运用K-Means聚类算法及肘部法则解决中小学生出行路线优化设计中校车停车站点数目及位置的选取问题。

针对单个学校的校车停车站点的位置选取。运用K-Means聚类算法，以欧式距离作为判断各点相似度的依据，均方差作为测度函数，找出K个聚类中心即得到K个校车停车站点的位置。其中问题中没有指定K的值，因此可以通过肘部法则进而合理地选定该校校车的停车站点的数量K作为聚类的类别数，本论文中数据来源于某市某十所学校，分别包括每个学校每个学生具体的位置，上学和放学的具体出行方式及上学的具体时间，是否有乘坐校车的意愿和每个学校及其校门的具体地址。由Matlab仿真后，结果表明，基于肘部法则确定的站点数目及位置更加准确。

[1]蒋盛益,李霞,郑琪.数据挖掘原理与实践[M].北京:电子工业出版社,2011.

[2]陈宝楼.K-Means算法研究在文本聚类中的应用[D].江苏:安徽大学,2013(04).