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

智能数据挖掘 Topic3 聚类分析K means K medoids聚类 主要内容 K means算法Matlab程序实现在图像分割上的简单应用K medoids算法k 中心点聚类算法 PAMK medoids改进算法 2020 4 20 基于划分的聚类方法 构造n个对象数据库D的划分 将其划分成k个聚类启发式方法 k 平均值 k means 和k 中心点 k medoids 算法k 平均值 MacQueen 67 每个簇用该簇中对象的平均值来表示k 中心点或PAM Partitionaroundmedoids Kaufman Rousseeuw 87 每个簇用接近聚类中心的一个对象来表示这些启发式算法适合发现中小规模数据库中的球状聚类对于大规模数据库和处理任意形状的聚类 这些算法需要进一步扩展 2020 4 20 K means聚类算法 算法描述为中心向量c1 c2 ck初始化k个种子分组 将样本分配给距离其最近的中心向量由这些样本构造不相交 non overlapping 的聚类确定中心 用各个聚类的中心向量作为新的中心重复分组和确定中心的步骤 直至算法收敛 2020 4 20 K means聚类算法 续 分组 将样本分配给距离它们最近的中心向量 并使目标函数值减小确定中心 亦须有助于减小目标函数值 2020 4 20 K means聚类算法 续 算法的具体过程从数据集中任意选取k个赋给初始的聚类中心c1 c2 ck 对数据集中的每个样本点xi 计算其与各个聚类中心cj的欧氏距离并获取其类别标号 按下式重新计算k个聚类中心 重复步骤2和步骤3 直到达到最大迭代次数 聚类目标函数达到最优值或者两次迭代得到的目标函数变化小于给定的 为止 2020 4 20 k 平均聚类算法 续 例 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K 2任意选择K个对象作为初始聚类中心 将每个对象赋给最类似的中心 更新簇的平均值 重新赋值 更新簇的平均值 重新赋值 2020 4 20 Matlab程序实现 function M j e kmeans X K Max Its N D size X I randperm N M X I 1 K Mo M forn 1 Max Itsfork 1 KDist k sum X repmat M k N 1 2 2 end i j min Dist 2 fork 1 Kifsize find j k 0M k mean X find j k endend 2020 4 20 Matlab程序实现 续 Z zeros N K form 1 NZ m j m 1 ende sum sum Z Dist N fprintf dError f n n e Mo M end 2020 4 20 在图像分割上的简单应用 例1 图片 一只遥望大海的小狗 此图为100 x100像素的JPG图片 每个像素可以表示为三维向量 分别对应JPEG图像中的红色 绿色和蓝色通道 将图片分割为合适的背景区域 三个 和前景区域 小狗 使用K means算法对图像进行分割 2020 4 20 在图像分割上的简单应用 续 分割后的效果 注 最大迭代次数为20次 需运行多次才有可能得到较好的效果 2020 4 20 在图像分割上的简单应用 续 例2 注 聚类中心个数为5 最大迭代次数为10 2020 4 20 k 平均聚类算法 续 优点 相对有效性 O tkn 其中n是对象数目 k是簇数目 t是迭代次数 通常 k t n 当结果簇是密集的 而簇与簇之间区别明显时 它的效果较好 2020 4 20 k 平均聚类算法 续 弱点只有在簇的平均值 mean 被定义的情况下才能使用 可能不适用于某些应用 例如涉及有分类属性的数据需要预先指顶簇的数目k 不能处理噪音数据和孤立点 outliers 不适合用来发现具有非凸形状 non convexshapes 的簇 2020 4 20 k 中心点聚类方法 k 平均值算法对孤立点很敏感 因为具有特别大的值的对象可能显著地影响数据的分布 k 中心点 k Medoids 不采用簇中对象的平均值作为参照点 而是选用簇中位置最中心的对象 即中心点 medoid 作为参照点 2020 4 20 k 中心点聚类方法 续 找聚类中的代表对象 中心点 PAM PartitioningAroundMedoids 1987 首先为每个簇随意选择选择一个代表对象 剩余的对象根据其与代表对象的距离分配给最近的一个簇 然后反复地用非代表对象来替代代表对象 以改进聚类的质量PAM对于较小的数据集非常有效 但不能很好地扩展到大型数据集 2020 4 20 k 中心点聚类方法 续 基本思想 首先为每个簇随意选择选择一个代表对象 剩余的对象根据其与代表对象的距离分配给最近的一个簇 然后反复地用非代表对象来替代代表对象 以改进聚类的质量 聚类结果的质量用一个代价函数来估算 2020 4 20 k 中心点聚类方法 续 为了判定一个非代表对象Orandom是否是当前一个代表对象Oj的好的替代 对于每一个非代表对象p 考虑下面的四种情况 第一种情况 p当前隶属于代表对象Oj 如果Oj被Orandom所代替 且p离Oi最近 i j 那么p被重新分配给Oi第二种情况 p当前隶属于代表对象Oj 如果Oj被Orandom代替 且p离Orandom最近 那么p被重新分配给Orandom 1 重新分配给Oi2 重新分配给Orandom 2020 4 20 k 中心点聚类方法 续 第三种情况 p当前隶属于Oi i j 如果Oj被Orandom代替 而p仍然离Oi最近 那么对象的隶属不发生变化第四种情况 p当前隶属于Oi i j 如果Oj被Orandom代替 且p离Orandom最近 那么p被重新分配给Orandom 3 不发生变化4 重新分配给Orandom 2020 4 20 k 中心点聚类方法 续 算法 k 中心点 1 随机选择k个对象作为初始的代表对象 2 repeat 3 指派每个剩余的对象给离它最近的代表对象所代表的簇 4 随意地选择一个非代表对象Orandom 5 计算用Orandom代替Oj的总距离E 如果E比取代前下降则则用Orandom替换Oj 形成新的k个代表对象的集合 返回 4 6 until不发生变化 7 如果所有非代表对象都无法取代已存在的簇中心 则结束替代过程 并输出结果 2020 4 20 PAM 续 TotalCost 20 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K 2 Arbitrarychoosekobjectasinitialmedoids Assigneachremainingobjecttonearestmedoids Randomlyselectanonmedoidobject Oramdom Computetotalcostofswapping TotalCost 26 SwappingOandOramdomIfqualityisimproved DoloopUntilnochange 2020 4 20 PAM 续 当存在噪音和孤立点时 PAM比k 平均方法更健壮 这是因为中心点不象平均值那么容易被极端数据影响PAM对于小数据集工作得很好 但不能很好地用于大数据集每次迭代O k n k 2 其中n是数据对象数目 k是聚类数基于抽样的方法 CLARA ClusteringLARgeApplications 2020 4 20 CLARA ClusteringLargeApplications 1990 CLARA KaufmannandRousseeuwin1990 不考虑整个数据集 而是选择数据的一小部分作为样本它从数据集中抽取多个样本集 对每个样本集使用PAM 并以最好的聚类作为输出优点 可以处理的数据集比PAM大缺点 有效性依赖于样本集的大小基于样本的好的聚类并不一定是整个数据集的好的聚类 样本可能发生倾斜例如 Oi是最佳的k个中心点之一 但它不包含在样本中 CLARA将找不到最佳聚类 2020 4 20 CLARA 效率 由取样大小决定PAM 利用完整资料集CLARA 利用取样资料集盲点 取样范围不包含最佳解 Trade off 24 2020 4 20 CLARA改良 解決 CLARANS ClusteringLargeApplicationbaseduponRANdomizedSearch 应用graph考虑紧邻节点不局限于区域性复杂度 O n 2 缺点 25 2020 4 20 CLARA的有效性主要取决于样本的大小 如果任何一个最佳抽样中心点不在最佳的K个中心之中 则CLARA将永远不能找到数据集合的最佳聚类 同时这也是为了聚类效率做付出的代价 CLARANS聚类则是将CLARA和PAM有效的结合起来 CLARANS在任何时候都不把自身局限于任何样本 CLARANS在搜素的每一步都以某种随机性选取样本 算法步骤如下 CLARANS Randomized CLARA 1994 2020 4 20 CLARANS Randomized CLARA 1994 CLARANS AClusteringAlgorithmbasedonRandomizedSearch NgandHan 94 CLARANS将采样技术和PAM结合起来CLARA在搜索的每个阶段有一个固定的样本CLARANS任何时候都不局限于固定样本 而是在搜索的每一步带一定随机性地抽取一个样本聚类过程可以被描述为对一个图的搜索 图中的每个节点是一个潜在的解 也就是说k medoids相邻节点 代表的集合只有一个对象不同在替换了一个代表对象后得到的聚类结果被称为当前聚类结果的邻居 2020 4 20 CLARANS 续 如果一个更好的邻居被发现 CLARANS移到该邻居节点 处理过程重新开始 否则当前的聚类达到了一个局部最优如果找到了一个局部最优 CLARANS从随机选择的节点开始寻找新的局部最优实验显示CLARANS比PAM和CLARA更有效CLARANS能够探测孤立点聚焦技术和空间存取结构可以进一步改进它的性能 Esteretal 95 2020 4 20 1 输入参数numlocal和maxneighbor numlocal表示抽样的次数 maxneighbor表示一个节点可以与任意特定邻居进行比较的数目 令 i 1 i用来表示已经选样的次数mincost为最小代价 初始时设为大数 2 设置当前节点current为Gn中的任意一个节点 3 令j 1 j用来表示已经与current进行比较的邻居的个数 4 考虑当前点的一个随机的邻居S 并计算两个节点的代价差 5 如果S的代价较低 则current S 转到步骤3 6 否则 令j j 1 如果jmaxneighbor 当前节点为本次选样最小代价节点 如果其代价小于mincost 令mincost为当前节点的代价 bestnode为当前的节点 8 令i i 1 如果i numlocal 输出bestnode 运算中止 否则 转到步骤2 CLARANS Randomized CLARA 1994 2020 4 20 1 代价值 主要描述一个对象被分到一个类别中的代价值 该代价值由每个对象与其簇中心点间的相异度 距离或者相似度 的总和来定义 代价差则是两次随机领域的代价差值 2 更新邻接点 CLARANS不会把搜索限制在局部区域 如果发现一个更好的近邻 CLARANS就移到该近邻节点 处理过程从新开始 否则 当前的聚类则产生了一个局部最小 如果找到一个局部最小 CLARANS从随机选择的新节点开始 搜索新的局部最小 当搜索的局部最小解达到用户指定的数目时 最好的局部最小作为算法的输出 从上面的算法步骤也可以看出这一思想 在第5步中更新节点current CLARANS Randomized CLARA 1994 2020 4 20 综合比较 精確度 速度 31 2020 4 20 作业 自己编写K means算法实现图像分割 尝试不同的K值对结果的影响 编程对比实现K means和PAM算法针三维同心球数据集加5 20 的高斯噪声进行聚类 对比两个算法的聚类抗噪性 其中第一类样本的参数服从均匀布U 0 50 第二类样本的参数服从均匀分布U 5