欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

几种常见的聚类算法

程序员文章站 2022-07-14 20:56:51
...

(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!

 

 

 

相关标签: 聚类算法