几种常见的聚类算法
(1) k均值聚类
思想:先确定聚类中心个数K,初始化聚类中心,计算每个样本到每个聚类中心的距离,将其归为最近的一类。
#伪代码
输入:样本集D={x1,x2....xm}
聚类中心(簇)个数k.
迭代过程:
1:从D中随机选择K个样本作为初始聚类中心{u1,u2....uk}
2:repeat:
3: 令Ci=空集(1<=i<=k)
4: for j=1,2 .....m ,do #遍历所有样本
5: 计算样本xj到k个聚类中心的距离(一般是欧氏距离)
6: 将该样本归为距离最小的那一个中心,并将xj添加到相应的集合Ci中
7: end
8 for i=1,2....k do
9: 重新计算聚类中心 new_ui=mean(Ci),即取这个簇所有样本的均值
10: if new_ui!=ui #说明:当 |new_ui-ui|的绝对值变化的很小时也会停止更新
11: ui=new_ui
12: else:
13: 保持ui不变
14: end
15: end
16:直到所有的聚类中心满足条件
输出:最终的类簇划分
Ps:python中需要设置最大迭代次数
优缺点:
优点:对于大型数据集也是简单高效、时间复杂度、空间复杂度低。
缺点:最重要是数据集大时结果容易局部最优;需要预先设定K值,对最先的K个点选取很敏感;对噪声和离群值非常敏感
一些改进:
k-means对初始值的设置很敏感,所以有了k-means++、intelligent k-means、genetic k-means。
k-means对噪声和离群值非常敏感,所以有了k-medoids和k-medians。
k-means只用于numerical类型数据,不适用于categorical类型数据,所以k-modes。
k-means不能解决非凸(non-convex)数据,所以有了kernel k-means。
(2)DBSCAN
思想:DBSCAN是一种基于密度聚类的方法,它假设样本能够通过分布的紧密程度来区分。这个算法有一篇博客讲的很好:
https://www.cnblogs.com/pinard/p/6208966.html
优缺点:
DBSCAN的主要优点有:
1) 可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。
2) 可以在聚类的同时发现异常点,对数据集中的异常点不敏感。
3) 聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响。
DBSCAN的主要缺点有:
1)如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差,这时用DBSCAN聚类一般不适合。
2) 如果样本集较大时,聚类收敛时间较长,此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
3) 调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值ϵϵ,邻域样本数阈值MinPts联合调参,
(3)层次聚类
层次聚类试图在不同层次对数据集进行划分,形成树形的聚类结构,既可以”自底向上“聚合,也可以”自顶向下“拆分。这主要讲下AGNES这种自底向上聚合的算法。
思想:将每个样本都视为一个初始聚类簇,在算法的每一步找出距离最近的两个聚类簇进行合并。不断重复,直到达到预设的聚类簇数。(关键是如何计算距离)。
伪代码如下:
蓝鲸博客进行了具体说明:http://bluewhale.cc/2016-04-19/hierarchical-clustering.html
另外常用的还有高斯混合聚类、谱聚类等,有空再补充,hope so!
上一篇: EM算法
下一篇: 文本聚类(二)KMeans 聚类