第9讲 K-Means & K-Medoids Clustering在线视频

同学们好

欢迎来到

互联网大规模数据分析技术课堂

我是这节课的主讲教师张蕊

来自武汉理工大学

这节课我们一起来了解一下

K-Means 与K-Medoids两个经典的

聚类算法

K-Means 与K-Medoids算法

都属于聚类中的划分方法

划分方法是把

数据集D当中的n个对象

分配到k个簇里面去

使得误差的平方和最小

在这个公式里，p是数据点

ci是簇心，比如均值或者是中心点

d(p,ci)是点p到簇心的距离

这两个累加表示求出每个簇中

每个点到簇心距离的平方和

对于给定的k

要发现关于K个簇的划分

使得这些划分准出最优化

划分准则，可能是全局最优

那就需要穷举所有的划分来得到

而这是个np难度问题，不可行

更可行的选择是

采用一些直觉的方法来进行划分

典型代表就是我们今天要讲的

K-Means 与k-K-Medoids算法

K-Means算法的基本思想是这样的

给定k

K-Means算法按以下4个步骤来进行

首先，将对象划分到k个非空子集

第二步，计算种子结点作为簇心

这里是均值

第三步，将每个数据对象

分配到距离种子结点最近的簇

然后回到第二步进行迭代

直到划分不再改变，变得稳定

算法停止

我们来看一个K-Means算法的例子

我们的初始数据集是这样的

给定k=2

将所有点划分两个group里面

然后我们计算每个簇的均值作为簇心

根据这些簇心

我们重新计算每个点到簇心的距离

分配到距离最近的簇

然后我们重新计算每个簇的簇心

接着根据新的簇心

再次计算每个点到簇心的距离

来进行分配

但现在我们算下来

每个点的分配并没有改变

也就是说这时候划分已经稳定

算法停止

k-means算法有什么优点和缺陷呢

首先我们可以看到

假定一共有n个数据对象

k个簇，进行了T次迭代

那K-Means算法的复杂度应该是

t乘以k乘以n这个数量级

因为k和t，都远远小于n

所以它的复杂度

相对于其他聚类算法来说有优势

可以比较容易地

在大规模数据集上运行

相对来说是可伸缩的

但K-Means算法

经常终止于局部最优

不能保证发现全局最优

另外，他只能处理数值型数据

并且需要指定k

对噪声数据和离群点比较敏感

而且不适合发现

非凸形状的簇

特别是k均值对离群点非常敏感

如果有一个离群点的值非常的极端

它会严重影响

整个簇的计算出来的均值

针对这个问题

有人提出不采用簇的均值来代表簇

而是采用一个

位居中心的实际对象来代表簇

比如这两个较大的蓝色的点

就分别是这两个簇的中心点

而不是计算出来的均值

这就是K-Medoids算法的基本思想

我们来看一个典型的

K-Medoids算法的例子

我们的初始数据集是这样的

给定k=2，随机选择两个点

作为初始的簇的代表点

这里是深蓝的这两个

将剩余的数据对象

分配到距离最近的代表点所在的簇

然后随机选择一个非中心点对象

计算如果用这个随机对象代替中心点

交换后的代价是多少

这里我们计算出来总代价是26

如果，这个随机对象

计算出来的代价小于原代表对象

那就用这个随机对象替换原中心点

然后再根据新的中心点

再次将其他数据对象

分配到距离最近的代表点所在的簇

迭代进行，直到划分不再改变

算法停止

所以K-Medoids算法的重点

是要发现簇的代表点

对于PAM算法来说

先任意选择簇的代表点

然后用其他点去替换现有的代表点

看是否能提高聚类质量

要尝试所有可能的替换

直到聚类质量不再被任何替换提高

PAM算法

在小规模数据集上的运行结果不错

对离群点不敏感

但因为尝试所有替换的计算代价很高

所以它对大规模数据来说不是可伸缩的

有研究者针对这做了一些有效的改进

大家可以去查看相关资料

本节课的内容到此结束

谢谢大家的观看