开发者学堂课程【高校精品课北京理工大学数据仓库与数据挖掘(下)：Partitioning Methods】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1041/detail/15649
Partitioning Methods
内容介绍：
一、基于划分的聚类方法
二、K-Means 聚类算法
三、 K值的确定
四、中心点初始化
五、K-Medoids 算法
六、K-Medians 聚类算法
七、K-Means 聚类算法问题
八、K-Means 算法小结
本课程进行数据仓库与数据挖掘的学习。介绍基于划分的方法。在进行划分的聚类方法中，介绍划分方法的基本概念，K-Means 聚类算法，对 K-Means 聚类算法的初始化，K 中心点聚类算法,K中位数和 K 众数聚类算法。
一、基于划分的聚类方法
1.基本概念
那什么是基于划分的聚类方法呢？基于划分的聚类方法，首先会设定一个特定的目标函数。通过优化目标函数，不断地去提升划分的质量，最终得到最终的蔟。来看一下基于划分方法中的目标函数，那么目标函数称之为sse，也就是误差的平方和。
2. 公式
其中，在计算公式中，k代表的是需要划分的数目，也就是蔟的数目。被Ck代表的是每一个蔟的原型，蔟的原型可以是这个蔟的中心点，也可以是它的所有数据对象的平均值。Xi指的是属于这个蔟CK的数据对象。也就是SSE它的含义就指的是累计计算同一个蔟中每一个数据对象到这个蔟的圆形的距离。
因为对于蔟来说，是希望蔟中的数据对象是相似的，也就是希望蔟是比较紧凑的，因此对于这样的一个目标函数 sse希望它越小越好。
3.优化 sse 途径
对于sse的优化有两种途径，第一种，就是全局优化，可以列出k个划分的所有的可能性，然后依次计算每一个划分的ss e值，从中选择一个最小sse值最小的的划分。但是这样的一种方法实施起来是非常困难的，因为不可能列出k个划分的所有可能。
因此，对于划分的聚类算法来说，往往会采用一种局部最优的策略，采用这样的一种启发式的算法，那么逐步的去逼近最优值，像 K-Means 算法，k 中心点算法，K 中位数算法等算法，都是基于启发式的聚类算法。
二、K-Means 聚类算法
首先介绍 K-Means 聚类算法。K-Means 聚类算法的一个核心是它的每一个蔟的原型是用这个蔟中所有数据对象的平均值来代表。
1.算法过程
来看一下，K-Means 聚类算法的过程。对于 K-Means 聚类算法，首先需要设定一个参数k，也就是需要设定要将数据对象划分为多少个蔟。
在确定K值之后，首先从数据对象结合中随机的选择K个点作为初始的蔟中心。在得到K歌初始的蔟中心之后，依次重复以下两个步骤。将每个数据对象分配到离它最近的蔟中心所在的蔟中，从而形成k个蔟。
在形成K个蔟之后，根据每一个蔟中的数据对象去更新这个蔟的中心。那么，对于K-Means算法中的蔟来说，也就是进行形成蔟的这一步骤中，其实相当于是在给定K个蔟中心的情况下，是去优化sse，那么这一步，比如重新去计算蔟的中心的时候，它的含义是在给定蔟的前提下去，通过优化蔟中心来最小化sse的值。通过重复这两步一直到满足收敛条件为止，那么整个K-Means算法就结束了。
收敛条件，一般采用的是数据集合中的所有数据对象的蔟标签变化不太大，或者是基本上没有变化的时候。那么K-Means 算法的迭代宗旨。
在 K-Means 算法中，有一个重要的步骤，就是将数据对象要把它分配到离它最近的这样的一个蔟中心所代表的蔟中去，在这样的一个过程中，就需要使用到相似性的度量方法。在K-Means算法中，有很多种相似性，度量方法可以使用，比如说，可以使用马式距离，也就是L1 norm，也可以使用L2 norm，就是欧式距离，甚至还可以使用余弦相似性。
2. K-Means 算法过程图
来看一下，K-Means算法的过程。那么下图展示了一个K-Means算法的运行过程，首先第一幅图展示的是数据分布，也就是这个数据，它是一个二维数据，可以在二维平面上去展示它。根据K-Means算法，首先随机的选择了两个点，作为它的初始聚类中心，也就是首先设置k=2，然后从数据集合中随机的选择两个数据对象作为这两个蔟的中心。
在确定了两个初始聚类中心之后，将剩余的数据对象根据相似性度量分配到离它最近的这样的一个蔟中心所代表的蔟中去。那么在得到了两个蔟之后，会根据这两个蔟的分布，然后去更新它的蔟中心。迭代以上步骤，那一直到最后，这个数据对象的蔟标签不再发生变化为止，就得到了两个蔟。
3. K-Means 聚类算法缺点
对于 K-Means 聚类算法来说，它有一个缺陷，就是它对于k个初始中心点的选择是非常敏感的，如果k个初始中心点选择不好，那么会得到比较差的聚类质量，比如像下图这样的一个展示，
那么更新了两个初始聚类中心，也就是另外选择的两个初始聚类中心，那么依然也是经过K-Means算法的过程，可以看到最后得到的聚类结果是这样的，它跟初始的数据分布所观察得到的这样的一个蔟分布差异性是很大的，也就是说，这样的聚类结果，它的质量是比较差的，
4. K-Means 算法问题
（1）、效率快
K-Means聚类算法中的一些问题进行讨论，首先，对于 K-Means 聚类算法来说，它的效率是比较快的，它的法复杂度是O的（tKn），t指的是迭代的次数，k指的是要划分的蔟的数目，n指的是数据对象的数目。在实际应用中，t是远远小于n的，其实在K-Means聚类算法中，迭代次数是比较少的，一般铁代比较小的次数之后，就能够得到一个稳定的聚类结果，所以说K-Means聚类算法的一个特点是它的效率比较快。
（2）、局部最优结果
除了效率比较快，K-Means算法的一个特点是得到的聚类结果往往是局部优化的结果，那么，在之前介绍K-Means算法的时候，也讲到过它的sse的优化是针对特定的蔟，或针对特定蔟中心来进行优化的，所以说它的结果可能是一个局部最优的结果。
（3）、设定 k 值
其次，对于局部最优的结果算法k的值，是需要去设定的，如果这个k的值设定的不是很合理，那么得到的聚类质量也会比较差，在后面会介绍如何去确定k的数目。
（4）、对异常点敏感
此外，K-Means 聚类算法，它对异常点是很敏感的，因为知道 K-Means 聚类算法，它在构建蔟的时候是依赖距离去计算的，而且它的蔟中心是所有数据对象的平均值，那么因为均值是受益异常点影响非常强烈的，所以说对于肯定是聚类算法来说，它对于噪声和异常点很敏感。
（5）、离散型均值难以计算
其次，K-Means 聚类算法，它主要适用于去发现一些球形的蔟，也就是凸形的蔟，因为它是基于距离去分配，那么所以比如说像对于下图展示的这种非凸形的蔟，以及互相缠绕的这些蔟的聚类效果是较差的，而且因为在 K-Means算法中，它需要通过平均值去更新蔟的中心，所以说，当数据类型如果是离散类型的，那么这个均值就不太好计算，
三、K 值的确定
介绍一下，在 K-Means 算法中如何去确定k的数目。对k值的确定主要是通过绘制肘线图来发现。那在 K-Means 算法中，优化目标是ss e。随着k的数目的增大，这个sS e的值是会逐渐的减小，最极端的情况是，每一个数据对象为一个蔟，这个时候的sse最小。
通过这样的一个特点，可以绘制这样的一幅图，它的横坐标代表的是蔟的数目，那么从零一直到八进行增长，那么它的纵轴代表的是see的数目，那么把每一个k值的sse绘制出来，就可以得到一个下面这样的曲线图。
那也就是这个曲线展示的含义是，随着k值的增加，see 在不断的下降，但是下降的幅度不一样，比如刚开始随着k值的增加，sse下降的非常快，那么当在某一个点之后，这个下降率就会突变，就变得非常非常缓慢，那么形成的这样的一个曲线非常类似于人的肘关节的这样的一个曲线，所以把它称之为叫做肘线图，那么可以选取一个下降率突变点4作为k值。
四、中心点初始化
再来介绍一下，在 K-Means 算法中，如何对 K 个初始中心点进行初始化？这里主要介绍一下，K-Means 算法的思想。那么，因为初始中心点的选择对聚类质量的影响比较大，那么就必须要去选择尽可能合适的初始中心点。
那么K-Means算法的思想是，首先在数据对象中谁接的去选择一个数据对象作为第一个初始中心点。在下一次选择中心点的时候，可以根据数据对象的加权概率分数去选择一个离之前所有初始中心点最远的一个点，作为下一步的初始中心点，那么，迭代以上步骤一直的选出k个初始中心点。
五、K-Medoids 算法
对于 K-Means 算法来说，它对异常值是很敏感的，为了克服K-Means算法对异常点敏感的问题，提出了k中心点算法。对于k中心点算法来说，它和K-Means算法的过程比较类似，但是它使用了一个最具有代表性的数据对象去取代原型。
在K-Means算法中使用的是所有数据对象的平均值来作为蔟的原型。而在k中心点算法中，使用的是这个蔟中最能够代表这个蔟的数据对象，作为蔟的原型。
那么，最具有代表性的这个数据点，往往是离蔟中心最近的这样的一个数据对象。那么下图是k中心点的计算过程，那么它和肯定式算法是一样的。
那么，在k中心点算法中和 K-Means 算法有一个不同的点在哪里？就是在更新蔟中心的时候可以面试，K-Means 是重新计算这个蔟中所有数据对象的均值，但是对于k中心点来说，就需要去替换蔟中心，那么这个替换的时候呢？是需要从非代表性的数据对象中选择一个，去替代原始的数据对象，那么替代之后会计算一个 cost 就是一个代价。
这个代价就指的是更新后的ss e和更新前的ss e之间的差距。如果s小于零，就表示更新的这样的一个蔟的聚类中心，能够去缩小的 see，那么就可以替换。
那么重复以上步骤，那么一直也是到蔟标签不再发生变化的时候，聚类结果就完成了。
通过一个图解释。第一幅图展示的是数据对象的分布，从数据对象的分布可以看出，大概是由两个蔟，那首先随机的选择，两个数据对象作为这两个数的初始的初始蔟中心，然后将数据对象配到离它最近的这个蔟中心所代表的蔟中去。
在得到了这样的两个蔟之后，考虑用这个蔟中的一个数据对象去替代它的原始的蔟中心，那么就需要计算它的 cost，计算 cost 之后，发现这个 cost 是小于零的，也就是如果使用这个点取代原始的蔟中心是能够减少 sse 的，所以就更新这个的中心，为这样的一个点，那么重复以上过程，一直到数据对象的标签不再发生变化为止，就得到了最终的聚类结果。
那么这个就是 k 中心点的聚类过程算法，那么就是需要跟 K-Means 算法很类似，唯一不同的就是不是再重新计算出的中心，而是需要去替换，然后计算它的代价来确定蔟中心。
