(聚类分析—K-means and K-medoids聚类.ppt

CSE 802. Prepared by Martin Law 数据挖掘 Topic3--聚类分析 K-means K-medoids 聚类 主要内容 K-means算法 Matlab程序实现 在图像分割上的简单应用 K-medoids算法 k-中心点聚类算法--PAM K-medoids改进算法 基于划分的聚类方法 构造n个对象数据库D的划分, 将其划分成k个聚类 启发式方法: k-平均值(k- means)和 k-中心点(k- medoids) 算法 k-平均值(MacQueen’67): 每个簇用该簇中对象的平均值来表示 k-中心点或 PAM (Partition around medoids) (Kaufman Rousseeuw’87): 每个簇用接近聚类中心的一个对象来表示 这些启发式算法适合发现中小规模数据库中的球状聚类 对于大规模数据库和处理任意形状的聚类,这些算法需要进一步扩展 K-means聚类算法 算法描述 为中心向量c1, c2, …, ck初始化k个种子 分组: 将样本分配给距离其最近的中心向量 由这些样本构造不相交（ non-overlapping ）的聚类 确定中心: 用各个聚类的中心向量作为新的中心 重复分组和确定中心的步骤，直至算法收敛 K-means聚类算法（续） 算法的具体过程 从数据集 中任意选取k个赋给初始的聚类中心c1, c2, …, ck； 对数据集中的每个样本点xi，计算其与各个聚类中心cj的欧氏距离并获取其类别标号： 按下式重新计算k个聚类中心； 重复步骤2和步骤3，直到达到最大迭代次数为止。 Matlab程序实现 Matlab程序实现（续） k-平均聚类算法(续) 例 在图像分割上的简单应用 在图像分割上的简单应用（续） 在图像分割上的简单应用（续） k-平均聚类算法(续) 优点: 相对有效性: O(tkn), 其中 n 是对象数目, k 是簇数目, t 是迭代次数; 通常, k, t n. 当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好 Comment: 常常终止于局部最优. 全局最优 可以使用诸如确定性的退火(deterministic annealing)和遗传算法(genetic algorithms)等技术得到 k-平均聚类算法(续) 弱点 只有在簇的平均值(mean)被定义的情况下才能使用.可能不适用于某些应用, 例如涉及有分类属性的数据 需要预先指顶簇的数目k, 不能处理噪音数据和孤立点(outliers) 不适合用来发现具有非凸形状(non-convex shapes)的簇 k-中心点聚类方法 k-平均值算法对孤立点很敏感! 因为具有特别大的值的对象可能显著地影响数据的分布. k-中心点(k-Medoids): 不采用簇中对象的平均值作为参照点, 而是选用簇中位置最中心的对象, 即中心点(medoid)作为参照点. k-中心点聚类方法(续) 找聚类中的代表对象(中心点) PAM (Partitioning Around Medoids, 1987) 首先为每个簇随意选择选择一个代表对象, 剩余的对象根据其与代表对象的距离分配给最近的一个簇; 然后反复地用非代表对象来替代代表对象，以改进聚类的质量 PAM 对于较小的数据集非常有效, 但不能很好地扩展到大型数据集 CLARA (Kaufmann Rousseeuw, 1990)抽样 CLARANS (Ng Han, 1994): 随机选样 k-中心点聚类方法(续) 基本思想： 首先为每个簇随意选择选择一个代表对象; 剩余的对象根据其与代表对象的距离分配给最近的一个簇 然后反复地用非代表对象来替代代表对象, 以改进聚类的质量 聚类结果的质量用一个代价函数来估算, 该函数评估了对象与其参照对象之间的平均相异度 k-中心点聚类方法(续) 为了判定一个非代表对象Orandom 是否是当前一个代表对象Oj的好的替代, 对于每一个非代表对象p,考虑下面的四种情况： 第一种情况：p当前隶属于代表对象 Oj. 如果Oj被Orandom所代替, 且p离Oi最近, i≠j, 那么p被重新分配给Oi 第二种情况：p当前隶属于代表对象 Oj. 如果Oj 被Orandom代替, 且p离Orandom最近, 那么p被重新分配给Orandom 第三种情况：p当前隶属于Oi，i≠j。如果Oj被Orandom代替，而p仍然离Oi最近，那么对象的隶属不发生变化 第四种情况：p当前隶属于Oi，i≠j。如果Oj被Orandom代替，且p离Orandom最近，那么p被重新分配给Orandom k-中心点聚类方法(续)  k-中心点聚类方法(续) 算