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

综合比较 K means K medoids CLARA CLARANS 优点 简单 不受极值影响 可处理大数据 找到最佳解 缺点 受极值影响 无法处理大数据 不一定是最佳解 速度慢 复杂度 O(nkt) O(k(n-k)^2) O(ks^2+k(n-k)) O(n^2) 精確度 速度 * * 作业 自己编写K-means算法实现图像分割，尝试不同的K值对结果的影响； 编程对比实现K-means和PAM算法针三维同心球数据集加5%、20%的高斯噪声进行聚类，对比两个算法的聚类抗噪性。 其中第一类样本的参数 服从均匀布U [0,50]，第二类样本的参数服从均匀分布 U [50,100],随机产生20000个样本数据进行聚类. due date：11月5日 * k-中心点聚类方法(续)  1.重新分配给Oi 2. 重新分配给Orandom 3. 不发生变化 4.重新分配给Orandom k-中心点聚类代价函数的四种情况 * k-中心点聚类方法(续) 基本思想： 首先为每个簇随意选择选择一个代表对象; 剩余的对象根据其与代表对象的距离分配给最近的一个簇 然后反复地用非代表对象来替代代表对象, 以改进聚类的质量 聚类结果的质量用一个代价函数来估算, 该函数评估了对象与其参照对象之间的平均相异度 * * * * * * * 智能数据挖掘 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-means聚类算法（续） 算法的具体过程 从数据集 中任意选取k个赋给初始的聚类中心c1, c2, …, ck； 对数据集中的每个样本点xi，计算其与各个聚类中心cj的欧氏距离并获取其类别标号： 按下式重新计算k个聚类中心； 重复步骤2和步骤3，直到达到最大迭代次数、聚类目标函数达到最优值或者两次迭代得到的目标函数变化小于给定的?为止。 * k-平均聚类算法(续) 例 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 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个对象作为初始聚类中心 将每个对象赋给最类似的中心 更新簇的平均值 重新赋值 更新簇的平均值 重新赋值 * Matlab程序实现 function [M, j, e] = kmeans(X, K, Max_Its) [N,D]=size(X); I=randperm(N); M=X(I(1:K),:); Mo = M; for n=1:Max_Its for k=1:K Dist(:,k) = sum((X - repmat(M(k,:),N,1)).^2,2); end [i, j]=min(Dist, [], 2); for k=1:K if size(find(j==k))0 M(k, :) = mean(X(find(j==k), :)); end end * Matlab程序实现（续） Z = zeros(N,K); for m=1:N Z(m,j(m)) = 1;