当前位置:   article > 正文

聚类算法综述_kmodes基于密度

kmodes基于密度

聚类算法:


1.基于划分的聚类算法(partitioning method)

基于划分的聚类就是将n个数据对象组织为k个划分(k≤n),每个划分代表一个簇

K-modes算法是K-Means算法非数值属性版本,K-Means和K-Modes的对比如下:

K-MeansK-Modes
使用欧式距离计算样本之间的距离样本和聚类中心的属性是否相同,相同则距离为0,否则为1
同一簇的平均位置作为新的中心同一簇中出现频率最高的属性作为新中心的属性
  • 1.3 PAM算法

PAM(Partitioning Around Medoid)和K-Means差不多,只是在更新新的中心点时的评判方法不一样。PAM的具体过程为:

1.随机确定K个聚类中心


2.对所有的点,通过找到离它们最近的聚类中心,将它们分类到这k个类中


3. 在每一个类中,总有一个点,它到本类其他所有点的距离之和是最小的,那么就将这个点作为本类新的聚类中心


4. 重复步骤3,直至聚类中心不再变化

可以看到,PAM和K-Means主要是第3步有所不同。PAM和K-Means的对比如下:

K-MeansPAM
对噪点和孤立点敏感,误差较大对噪声和孤立点不敏感
聚类计算方式简单,高效,快聚类时间长,聚类收敛慢
可适用于大规模数据的聚类适用于小规模数据聚类
  • 1.4 CLARA算法

CLARA算法本质就是PAM算法,它将PAM应用到了大规模数据集中。具体做法是对所有的数据抽取多份样本,利用PAM找到每份样本聚类中心,最后选出最好的聚类中心作为最后的结果。



基于层次的聚类算法(hierarchical method):

基于层次的聚类算法最开始将所有的点都看成簇,簇与簇之间通过接近度(closeness)来组合。对于“接近度”的不同定义有不同的算法。

CURE算法的基本步骤为:
1.对数据库抽样,得到一个样本
2.将样本划分为p个分区,每个分区的规模为n/p
3.对每个分区进行聚类,形成n/pq个簇,其中q为常数
4.删除增长缓慢的簇,同时在聚类的后期去掉规模较小的簇(簇增长缓慢说明簇中的数据点关联不大,聚类后期规模还比较小的簇例如一个簇只有3、4个数据点那簇的存在没有意义)
5.对每个簇选取特定数量的点来代表整个簇

CURE算法效率较高,适用于任意形状的数据集,对噪声不太敏感。

  • 2.3 BIRCH聚类

特点:算法效率高,适用于凸型或球型数据集,对噪声不敏感

  • 2.4 ROCK算法
基于密度的聚类算法:

基于密度的聚类算法假定类别可以通过样本分布的紧密程度决定。同一类别之间的样本是紧密联系的。

  • 3.1 DBSCAN算法

算法过程:
1.以每个数据点xi为圆心,以esp为半径画圆,这个圆圈为xi的eps领域
2.对圆圈包含的点进行计数,如果一个圆圈里面的点超过密度阈值Minpts,该圆圈的圆心记为核心点(核心对象);圆圈内的点小于阈值但是该点在其他核心点的领域内,则该点是边界点;否则该点为噪声点
3.称核心点到其领域内的其他点都是密度可达的,同时密度可达具有传递性,将所有密度可达的核心点连载一起就形成了聚类簇。


重要参数:
核心距离:核心为C,允许的阈值为5个数据点,则C到第5远的数据点的距离为核心距离
可达距离:如果一个点P在核心C的核心距离内,则该点到C的可达距离为核心距离;否则该点到C的可达距离为C和P之间的欧式距离

特点:算法效率一般,适用于任意形状的数据集,对噪声敏感
在这里插入图片描述


  • 3.2 OPTICS算法

重要参数:
核心距离:核心为C,允许的阈值为5个数据点,则C到第5远的数据点的距离为核心距离
可达距离:如果一个点P在核心C的核心距离内,则该点到C的可达距离为核心距离;否则该点到C的可达距离为C和P之间的欧式距离

https://blog.csdn.net/xuanyuansen/article/details/49471807
https://blog.csdn.net/shnu_pfh/article/details/78769440

  • 3.3 DENCLUE算法

基于网格的聚类算法:

基于网格的聚类算法基本过程:

1、定义网格单元
2、将数据点指派到合适的网格并计算每个网格密度
3、删除密度低于指定阈值的网格
4、邻近的稠密单元形成簇

  • 4.1 STING算法

  • 4.2 CLIQUE算法

算法主要考虑两个参数:
网格步长:用于确定空间的划分
密度阈值:定义密集网格


算法主要过程:
扫描所有网格,发现一个密集网格时,将该网格放入密集区并从该网格开始扩展。如果该网格邻接的网格也是密集的,则将这些网格也加入到密集区。直到所有网格都遍历一遍,算法结束。
现在定义密集网格=4,对下图进行CLIQUE算法:
在这里插入图片描述

  • 4.3 WAVE-CLUSTER算法
基于模型的聚类算法:
  • 5.1 COBWEB算法
  • 5.2 SOM算法


    数据挖掘对聚类算法的要求:
    -可伸缩性
    -能处理不同类型数据
    -处理不同形状的聚类
    -处理噪声数据的能力
算法算法类型算法效率适用数据集是否对噪声和孤立点敏感
K-Means基于划分较高凸型或球型不太敏感
CURE基于层次较高任意形状数据集不太敏感
BRICH算法基于层次凸型或球型不敏感
DBSCAN算法基于密度一般任意形状数据集敏感
CLIQUE基于网格任意形状不太敏感
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/773366
推荐阅读
相关标签
  

闽ICP备14008679号