分类: 大数据
2015-11-26 14:30:35
1)CURE算法
特点:固定数目有代表性的点共同代表类
优点:识别形状复杂,大小不一的聚类,过滤孤立点
2)ROCK算法
特点:对CURE算法的改进
优点:同上,并适用于类别属性的数据
3)CHAMELEON算法
特点:利用了动态建模技术
优点:适用于任意形状和任意属性的数据集;灵活控制不同层次的聚类粒度,强聚类能力
缺点:大大延长了算法的执行时间,不能回溯处理
2、分割聚类算法
将密度足够大的相邻区域连接,能有效处理异常数据,主要用于对空间数据的聚类
1)DBSCAN:不断生长足够高密度的区域
2)DENCLUE:根据数据点在属性空间中的密度进行聚类,密度和网格与处理的结合
3)OPTICS、DBCLASD、CURD:均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进
利用属性空间的多维网格数据结构,将空间划分为有限数目的单元以构成网格结构;
1)优点:处理时间与数据对象的数目无关,与数据的输入顺序无关,可以处理任意类型的数据
2)缺点:处理时间与每维空间所划分的单元数相关,一定程度上降低了聚类的质量和准确性
1)STING:基于网格多分辨率,将空间划分为方形单元,对应不同分辨率
2)STING+:改进STING,用于处理动态进化的空间数据
3)CLIQUE:结合网格和密度聚类的思想,能处理大规模高维度数据
4)WaveCluster:以信号处理思想为基础
转换为组合优化问题,并利用图论和相关启发式算法来解决,构造数据集的最小生成数,再逐步删除最长边
1)优点:不需要进行相似度的计算
1)基于超图的划分
2)基于光谱的图划分
逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解
1)概率聚类算法
期望最大化、能够处理异构数据、能够处理具有复杂结构的记录、能够连续处理成批的数据、具有在线处理能力、产生的聚类结果易于解释
2)最近邻聚类算法——共享最近邻算法SNN
特点:结合基于密度方法和ROCK思想,保留K最近邻简化相似矩阵和个数
不足:时间复杂度提高到了O(N^2)
3)K-Medioids算法
特点:用类中的某个点来代表该聚类
优点:能处理任意类型的属性;对异常数据不敏感
4)K-Means算法
1》特点:聚类中心用各类别中所有数据的平均值表示
2》原始K-Means算法的缺陷:结果好坏依赖于对初始聚类中心的选择、容易陷入局部最优解、对K值的选择没有准则可依循、对异常数据较为敏感、只能处理数值属性的数据、聚类结构可能不平衡
3》K-Means的变体
Bradley和Fayyad等:降低对中心的依赖,能适用于大规模数据集
Dhillon等:调整迭代过程中重新计算中心方法,提高性能
Zhang等:权值软分配调整迭代优化过程
Sarafis:将遗传算法应用于目标函数构建中
Berkh in等:应用扩展到了分布式聚类
还有:采用图论的划分思想,平衡聚类结果,将原始算法中的目标函数对应于一个各向同性的高斯混合模型
5)优缺点
优点:应用最为广泛;收敛速度快;能扩展以用于大规模的数据集
缺点:倾向于识别凸形分布、大小相近、密度相近的聚类;中心选择和噪声聚类对结果影响大
对个体对象的约束、对聚类参数的约束;均来自相关领域的经验知识
对存在障碍数据的二维空间按数据进行聚类如COD(Clustering with Obstructed Distance):用两点之间的障碍距离取代了一般的欧式距离
通常只能处理特定应用领域中的特定需求
1)无关属性的出现使数据失去了聚类的趋势
2)区分界限变得模糊
1)对原始数据降维
2)子空间聚类
CACTUS:对原始空间在二维平面上的投影
CLIQUE:结合基于密度和网格的聚类思想,借鉴Apriori算法
3)联合聚类技术
特点:对数据点和属性同时进行聚类
文本:基于双向划分图及其最小分割的代数学方法
4.3不足:不可避免地带来了原始数据信息的损失和聚类准确性的降低
1)人工神经网络方法
自组织映射:向量化方法,递增逐一处理;映射至二维平面,实现可视化
基于投影自适应谐振理论的人工神经网络聚类
2)基于进化理论的方法
缺陷:依赖于一些经验参数的选取,并具有较高的计算复杂度
模拟退火:微扰因子;遗传算法(选择、交叉、变异)
优点:利用相应的启发式算法获得较高质量的聚类结果
缺点:计算复杂度较高,结果依赖于对某些经验参数的选择
下面附上个人对聚类算法的选择及比较的理解: