关注我们的公众号哦获取更多精彩哦
1、问题导入
假如有这样一种情况在一天你想去某个城市旅游这个城市里你想去的有70个地方现在你只有每一个地方的地址这个地址列表很长有70个位置。事先肯定要做好攻略你要把一些比较接近的地方放在一起组成一组这样就可以安排交通工具抵达这些组的“某个地址”然后步行到每个组内的地址。那么如何确定这些组如何确定这些组的“某个地址”答案就是聚类。而本文所提供的k-means聚类分析方法就可以用于解决这类问题。
2. k均值聚类简介
2.1基本思想
聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程。k均值聚类是最著名的划分聚类算法由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要的聚类数目kk由用户指定k均值算法(k-means)根据某个距离函数反复把数据分入k个聚类中。k-means 算法的工作过程说明如下首先从n个数据对象任意选择 k 个对象作为初始聚类中心而对于所剩下其它对象则根据它们与这些聚类中心的相似度(距离)分别将它们分配给与其最相似的(聚类中心所代表的)聚类然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值)不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。
用以下例子加以解释
图1给定一个数据集
图2根据K 5初始化聚类中心保证 聚类中心处于数据空间内
图3根据计算类内对象和聚类中心之间的相似度指标将数据进行划分
图4将类内之间数据的均值作为聚类中心更新聚类中心。
最后判断算法结束与否即可目的是为了保证算法的收敛。
2.2 数学原理
以往的回归分类、朴素贝叶斯分类、SVM分类的样本的标签是已知的通过大量的训练样本得到模型然后判断新的样本所属已知类别中的哪一类。而k-means聚类属于无监督学习样本所属的类别是未知的只是根据特征将样本分类且类别空间也是根据人为需要选定的。
K-means核心思想最小化所有样本到所属类别中心的欧式距离和采用迭代的方式实现收敛。
K-means算法的具体步骤如下
2.3算法优缺点
K-Means的主要优点有
1)原理比较简单实现也是很容易收敛速度快。
2)聚类效果较优。
3)算法的可解释度比较强。
4)主要需要调参的参数仅仅是簇数k。
K-Means的主要缺点有
1)K值的选取不好把握
2)对于不是凸的数据集比较难收敛
3)如果各隐含类别的数据不平衡比如各隐含类别的数据量严重失衡或者各隐含类别的方差不同则聚类效果不佳。
4)采用迭代方法得到的结果只是局部最优。
5)对噪音和异常点比较的敏感。
6)可能收敛到局部最小值在大规模数据集上收敛较慢。
3.算法实现
3.1.K-means算法的相关描述
聚类是一种无监督的学习它将相似的对象归到同一簇中。聚类的方法几乎可以应用所有对象簇内的对象越相似聚类的效果就越好。K-means算法中的k表示的是聚类为k个簇means代表取每一个聚类中数据值的均值作为该簇的中心或者称为质心即用每一个的类的质心对该簇进行描述。聚类和分类最大的不同在于分类的目标是事先已知的而聚类则不一样聚类事先不知道目标变量是什么类别没有像分类那样被预先定义出来所以聚类有时也叫无监督学习。聚类分析试图将相似的对象归入同一簇将不相似的对象归为不同簇那么显然需要一种合适的相似度计算方法我们已知的有很多相似度的计算方法比如欧氏距离余弦距离汉明距离等。事实上我们应该根据具体的应用来选取合适的相似度计算方法。 当然任何一种算法都有一定的缺陷没有一种算法时完美的有的只是人类不断追求完美不断创新的意志。K-means算法也有它的缺陷但是我们可以通过一些后处理来得到更好的聚类结果这些在后面都会讲到。K-means算法虽然比较容易实现但是其可能收敛到局部最优解且在大规模数据集上收敛速度相对较慢。
3.2 K-means算法的工作流程
首先随机确定k个初始点的质心然后将数据集中的每一个点分配到一个簇中即为每一个点找到距其最近的质心并将其分配给该质心所对应的簇该步完成后每一个簇的质心更新为该簇所有点的平均值。具体算法表示如下下图展示了K-means聚类算法的支持函数在Python环境下的具体表示
在上述算法清单中包含了几个K-均值算法中要用到的辅助函数。LoadDataSet()函数是将文本文件导入到列表中文本文件每一行为tab分隔的浮点数每一个列表会被添加到dataMat中最后返回dataMat函数distEclud()用于计算两个向量的欧式距离函数randCent()为给定数据集构建一个包含k个随机质心的集合。下图表示以上3个函数的实际效果。
如果3个支持函数都可以正常运行就可以准备实现完整的K-means算法了该算法会创建K个质心然后将每个点分配到最近的质心再重新计算质心直到数据点的簇分配结果不再改变为止。具体代码如下
上面的代码给出了完整的K-means算法。上述算法的运行逻辑如下在第一步建立的Kmeans()函数接受4个输入参数。只有数据集及簇的数目是必选的而用来计算距离(我们这里用的是欧式距离)和创建初始质心的函数都是可选的(这里用的是randCent函数)。Kmeans()函数一开始确定数据集中数据点的总数然后创建一个矩阵来存储每个点的簇分配结果。这个矩阵clusterAssment有两列簇索引值和聚类误差。
按照上述方式反复迭代直到所有数据点的簇分配结果不再改变为止。程序中创建一个标志变量clusterChanged如果该值为True则继续迭代。上述迭代使用while循环来实现。接下来遍历所有数据找到距离每个点最近的质心(通过对每个点遍历所有质心并计算点到每个质心的欧式距离)。如果任一点的簇分配结果发生改变则更新clusterChanged标志。最后遍历所有质心并更新它们的取值具体实现步骤如下通过数组过滤来获得给定簇的所有点然后计算所有点的均值选项axis0表示沿矩阵的列方向进行均值计算最后程序返回所有的类质心和点分配结果。
算法的运行效果如下图所示我们可以看到上面的结果经过了3次迭代之后k-means算法收敛:
K-means算法进行到这里我们似乎已经得出了聚类的质心但是不要忘记了我们的算法采取的是随机初始化k个簇的质心的方法这样的话聚类效果可能会陷入局部最优解的情况这样虽然有效果但不如全局最优解的效果好。因此接下来的二分K--means算法就是针对这一问题所采取的相应的后处理使算法跳出局部最优解达到全局最优解获得最好的聚类效果。二分K-means算法首先将所有点作为一个簇然后将簇一分为二之后选择其中一个簇继续进行划分选择哪一个簇取决于对其划分是否能够最大程度地降低SSE(误差平方和即clusterAssment矩阵的第一列之和)的值。具体的代码如下
这个函数首先创建一个矩阵来存储数据集中每个点的簇分配结果及平方误差然后计算整个数据集的质心并使用一个列表来保留所有的质心。得到上述质心以后可以遍历数据集中所有点来计算每个点到质心的误差值(后面会用到)。然后程序进入while循环该循环会不停划分簇直到得到想要的簇数目为止。具体循环做法如上图所示当while循环结束时函数返回质心列表与簇分配结果。下图展示了一个上面所有算法一起运行的结果
二分k-means算法中直到簇的数目达到k值算法才会停止。在算法中通过将所有的簇进行划分然后分别计算划分后所有簇的误差。选择使得总误差最小的那个簇进行划分。划分完成后要更新簇的质心列表数据点的分类结果及误差平方。具体地假设划分的簇为m(m
4、应用举例
回到刚开始的问题我们现在有70个地方的地址但是只知道地址是不够的我们需要知道的是这些地址之间的距离远近信息。因此我们需要得到每个地址的经度和纬度然后对这些地址进行聚类以安排行程。具体的地址转换与算法过程如下所示
这一部分属于数据预处理工作在上述代码中首先创建一个字典字典里面存储的是通过URL获取经纬度所必要的参数即我们想要的返回的数据格式flogsJ获取数据的appid以及要输入的地址信息(stAddress,city)。然后通过urlencode()函数帮助我们将字典类型的信息转化为URL可以传递的字符串格式。最后打开URL获取返回的JSON类型数据通过JSON工具来解析返回的数据。且在返回的结果中当错误编码为0时表示得到了经纬度信息而为其他值时则表示返回经纬度信息失败。此外在代码中每次获取完一个地点的经纬度信息后延迟一秒钟。这样做的目的是为了避免频繁的调用API请求被封掉的情况。接下来就要正式利用k—means聚类方法对地理坐标进行聚类。
将上述算法加入到第三部分“算法示例”中的算法中然后在Python提示符下输入如下图所示的命令得到的结果如下图所示
执行上面的命令之后最后得出的聚类结果如下图所示
责编 | 薛 李 蔡 孙 赵
指导 | 老薛
指导教授简介
薛巍立男博士东南大学经济管理学院教授博士生导师国家自然科学基金优秀青年基金项目获得者。博士毕业于香港中文大学系统工程与工程管理系主要从事供应链物流管理、运营风险管理和医疗服务运作管理等。主要成果发表在Operations Research、Production and Operations Management、Transportation Science、European Journal of Operational Research、Operations Research Letters等期刊上。