聚类算法简述

目录

聚类的目的

聚类划分

k-means算法

k-means算法流程

k-means优点与缺点

K-means++与K-means

AGNES算法和DIANA算法

AGNES和DIANA算法优缺点

CURE算法

CURE算法的特点

BIRCH算法

BIRCH算法优缺点

DBSCAN算法

DBCSAN算法的特点

Canopy算法

Canopy算法的特点

聚类的目的就是把不同的数据点按照它们的相似与相异度分割成不同的簇，确保每个簇中的数据都是尽可能相似，而不同簇的数据尽可能相异。从模式识别的角度来讲，聚类就是在发现数据中潜在的模式，帮助人们 进行分组归类已达到更好理解数据的分布规律。

基于划分的聚类算法：K-means，基于层次的聚类算法： AGNES， DIANA,

基于密度的聚类算法：DBSCAN、Canopy， 基于网格的方法(grid-based method)、

基于模型的方法(model-based method)等

1.选择聚类的个数k(kmeans算法传递超参数的时候，只需设置最大的K值)

2.任意产生k个簇，然后确定簇中心，或者直接随机生成k个中心。

3.将数据集中的每个点分配到距离最近的簇。

4.再计算其新的簇中心。

5.重复以上步骤直到满足收敛要求。(通常就是确定的簇中心点不再改变。)

优点：

1、原理简单(靠近中心点) ，实现容易

2、聚类效果中上(依赖K的选择)

3、空间复杂度o(N)时间复杂度o(IKN，N为样本点个数，K为中心点个数，I为迭代次数)

缺点：

1、对离群点， 噪声敏感 (中心点易偏移)

2、很难发现大小差别很大的簇及进行增量计算

3、结果不一定是全局最优，只能保证局部最优(与K的个数及初值选取有关)

注：K-means++与K-means的区别，K-means++仅仅与K-means在第一次确定簇中心时步骤不同，其他步骤都一样，K-means++从数据集中选取了K个相距最远的点作为簇中心（先从数据集中随机选取一个点作为簇中心点，然后再从数据集中选出一个距离该簇中心点最远的簇中心点，然后再从数据集中选出一个距离上面两个簇中心点都最远的簇中心点，直至选出K个点，即选出K个相距最远的点）。

主要在不同层次对数据集进行逐层分解，直到满足某种条件为止；先计算样本之间的距离。每次将距离最近的点合并到同一个类，然后再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成一个类。

AGNES算法思想（自底向上的凝聚方法）：

1.初始每个数据都是一个簇；

2.寻找每个簇之间的距离，获取距离列表；

3.合并距离最近的两个簇Ci，Cj，并删除Cj，更新距离列表，使簇个数减1；

4.重复第3步，直到簇个数等于所需个数k。

DIANA（DIvisive ANAlysis）（自上向下的分裂方法）先将所有的样本归为一个簇，然后按照某种规则逐渐分裂为越来越小的簇，直到达到某个停止条件，如指定的簇数目等。分裂方式如下：

1.在同一个簇c中计算两两样本之间的距离，找出距离最远的两个样本a、b；

2.将样本a、b分配到不同的类簇c1、c2中；

3.计算c中剩余的其他样本分别和a、b的距离，若dist(a) T2，T1和T2的值可以用交叉校验来确定；

2、从list中任取一点P，用低计算成本方法快速计算点P与所有Canopy之间的距离(如果当前不存在Canopy，则把点P作为一个Canopy)，如果点P与某个Canopy距离在T1以内，则将点P加入到这个Canopy；

3、如果点P曾经与某个Canopy的距离在T2以内，则需要把点P从list中删除，这一步是认为点P此时与这个Canopy已经够近了，因此它不可以再做其它Canopy的中心了；

4、重复步骤2、3，直到list为空结束。

Canopy聚类虽然精度较低，但其在速度上有很大优势，因此可以使用Canopy聚类先对数据进行“粗”聚类，得到k值后再使用K-means进行进一步“细”聚类。