赞
踩
基于划分的聚类就是将n个数据对象组织为k个划分(k≤n),每个划分代表一个簇
K-modes算法是K-Means算法非数值属性版本,K-Means和K-Modes的对比如下:
K-Means | K-Modes |
---|---|
使用欧式距离计算样本之间的距离 | 样本和聚类中心的属性是否相同,相同则距离为0,否则为1 |
同一簇的平均位置作为新的中心 | 同一簇中出现频率最高的属性作为新中心的属性 |
PAM(Partitioning Around Medoid)和K-Means差不多,只是在更新新的中心点时的评判方法不一样。PAM的具体过程为:
1.随机确定K个聚类中心
2.对所有的点,通过找到离它们最近的聚类中心,将它们分类到这k个类中
3. 在每一个类中,总有一个点,它到本类其他所有点的距离之和是最小的,那么就将这个点作为本类新的聚类中心
4. 重复步骤3,直至聚类中心不再变化
可以看到,PAM和K-Means主要是第3步有所不同。PAM和K-Means的对比如下:
K-Means | PAM |
---|---|
对噪点和孤立点敏感,误差较大 | 对噪声和孤立点不敏感 |
聚类计算方式简单,高效,快 | 聚类时间长,聚类收敛慢 |
可适用于大规模数据的聚类 | 适用于小规模数据聚类 |
CLARA算法本质就是PAM算法,它将PAM应用到了大规模数据集中。具体做法是对所有的数据抽取多份样本,利用PAM找到每份样本聚类中心,最后选出最好的聚类中心作为最后的结果。
基于层次的聚类算法最开始将所有的点都看成簇,簇与簇之间通过接近度(closeness)来组合。对于“接近度”的不同定义有不同的算法。
CURE算法的基本步骤为:
1.对数据库抽样,得到一个样本
2.将样本划分为p个分区,每个分区的规模为n/p
3.对每个分区进行聚类,形成n/pq个簇,其中q为常数
4.删除增长缓慢的簇,同时在聚类的后期去掉规模较小的簇(簇增长缓慢说明簇中的数据点关联不大,聚类后期规模还比较小的簇例如一个簇只有3、4个数据点那簇的存在没有意义)
5.对每个簇选取特定数量的点来代表整个簇
CURE算法效率较高,适用于任意形状的数据集,对噪声不太敏感。
特点:算法效率高,适用于凸型或球型数据集,对噪声不敏感
基于密度的聚类算法假定类别可以通过样本分布的紧密程度决定。同一类别之间的样本是紧密联系的。
算法过程:
1.以每个数据点xi为圆心,以esp为半径画圆,这个圆圈为xi的eps领域
2.对圆圈包含的点进行计数,如果一个圆圈里面的点超过密度阈值Minpts,该圆圈的圆心记为核心点(核心对象);圆圈内的点小于阈值但是该点在其他核心点的领域内,则该点是边界点;否则该点为噪声点
3.称核心点到其领域内的其他点都是密度可达的,同时密度可达具有传递性,将所有密度可达的核心点连载一起就形成了聚类簇。
重要参数:
核心距离:核心为C,允许的阈值为5个数据点,则C到第5远的数据点的距离为核心距离
可达距离:如果一个点P在核心C的核心距离内,则该点到C的可达距离为核心距离;否则该点到C的可达距离为C和P之间的欧式距离
特点:算法效率一般,适用于任意形状的数据集,对噪声敏感
重要参数:
核心距离:核心为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
基于网格的聚类算法基本过程:
1、定义网格单元
2、将数据点指派到合适的网格并计算每个网格密度
3、删除密度低于指定阈值的网格
4、邻近的稠密单元形成簇
4.1 STING算法
4.2 CLIQUE算法
算法主要考虑两个参数:
网格步长:用于确定空间的划分
密度阈值:定义密集网格
算法主要过程:
扫描所有网格,发现一个密集网格时,将该网格放入密集区并从该网格开始扩展。如果该网格邻接的网格也是密集的,则将这些网格也加入到密集区。直到所有网格都遍历一遍,算法结束。
现在定义密集网格=4,对下图进行CLIQUE算法:
算法 | 算法类型 | 算法效率 | 适用数据集 | 是否对噪声和孤立点敏感 |
---|---|---|---|---|
K-Means | 基于划分 | 较高 | 凸型或球型 | 不太敏感 |
CURE | 基于层次 | 较高 | 任意形状数据集 | 不太敏感 |
BRICH算法 | 基于层次 | 高 | 凸型或球型 | 不敏感 |
DBSCAN算法 | 基于密度 | 一般 | 任意形状数据集 | 敏感 |
CLIQUE | 基于网格 | 低 | 任意形状 | 不太敏感 |
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。