开发者学堂课程【高校精品课北京理工大学数据仓库与数据挖掘(下)：Partitioning Methods】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1041/detail/15649
六、K-Medians 聚类算法
那么，除了采用 k 中心点来改善 K-Means 算法对异常敏感的问题，还可以采用这样的一个k中位数的方法，那么也就是可以不用所有数据对象的平均值来代表这个蔟，可以用所有数据对象的中位数来代表这个蔟。
那么如果使用中位数来代表这个蔟，那么相应的相似性度量方法也会发生变化，那么这个时候就会采用马市距离作为相似度测量方法，这个就是中位数聚类算法。
七、K-Means 聚类算法问题
对于这样的一个肯定是算法来说，它在执行过程中可能会产生一个问题，就是空蔟的问题。
1. 空蔟的产生
先看一下空蔟的产生。假设这个下图显示的这样的一个数据集是有六个数据对象，刚开始设定了三个聚类中心，在确定聚类中心之后，将每一个数据对象分配到离它最近的这个蔟里面去，就可以得到三个蔟。在得到三个蔟之后，根据K-Means算法，需要更新这个蔟的聚类中心，那么更新后的三个聚类中心的值分别是七点七五，十二点五和十七点二五。在更新蔟的聚类中心之后，需要再一次的对数据对象进行分配，将它分配到离聚类中心最近的蔟中去，那么经过这一次分配之后，就发现所有的数据对象都被分配到了7.75和17.25这两个数据所代表的蔟理面去，而以12.5维蔟中心的这个蔟，是没有任何数据对象的，从而就得到了一个空蔟。
2.空蔟解决策略
对于空蔟来说，解决主要是有两种策略。第一种策略是可以选择一个对 sse 贡献最大的一个数据对象，把它作为一个新的蔟的中心，那么其次，第二种策略是可以选择一个具有最大 sse 的蔟，在这个蔟中，随机地去选择一个数据对象，作为一个新的蔟中心。那假设在 K-Means 聚类算法中产生的多个空蔟，就可以基于以上策略得到多个新的蔟的聚类中心，然后再进行下一步。
八、K-Means 算法小结
最后，对 K-Means 算法做一个小结。对于 K-Means 算法来说，它有很多缺点，那么第一个缺点就是它是不能够处理不同尺寸，不同密度和非球形的蔟。
1.尺寸不同
其次 K-Means 算法，对于这样的一个包含异常的数据集合，它的聚类效果是比较差的。来看一下下面展示的这样的一个图，是一个数据集合，这个数据集合的特点就是它的蔟是具有不同的尺寸，可以看到其中左边和最右边的这两个蔟比较小，而中间红色部分的蔟比较大，如果使用k=3进行聚类，可以得到聚类结果，那么这个聚类结果和能观察到的这个数据的分布，它的差异性是比较大的，就是相当于聚类，结果质量是不太好的。
2.密度不同
再来看一下，对于下面的一个数据分布来说，那么每一个蔟中，看最左边的图，每一个蔟中的数据对象的数目大概是一样的，但是，第一个蔟面积比较大，就相当于它这个蔟的密度是比较低的，而这两个小蔟，它的密度是比较高的，比如说这代表的是它的密度分布不均匀的数据集合，对于这样的数据集，如果使用K-Means算法，可以看到得到的聚类结果和分布差异也是比较大的聚类结果，也是比较差。
3.非凸形蔟
再来看一下下面的一个数据集，这样的一个数据集很明显是有两个蔟，但是这两个蔟的形状是非凸形的，那如果是设置 k=2用，肯定是聚类，可以得到把它上面这一部分划分为一个蔟，下面这一部分划分为一个蔟，这跟初始的这个出的分布差异是非常大的，所以说对于 K-Means 算法来说，它是对于这种非凸形的，这种蔟的识别是比较差的。
4.解决方法
那针对于 K-Means 算法的，这些问题怎么样去解决和克服它呢？其中一种比较简单的策略就是，在利用 K-Means聚类的时候，可以开始把这个k的数目设置的比较大，也就是可以得到若干个比较小的蔟，然后再对这些比较小的蔟进行合并，从而得到比较好的聚类结果。那可以看一下，那么可以得到比较小的蔟，然后对于小蔟进行合并，那么得到的这些聚类，结果那么就比较的接近真实的数据分布。
关于基于划分的层次聚类算法就介绍到这里。
