ppt课件-kmeans.ppt

K-Means聚类算法 东华大学计算机科学与技术学院 钟芸龙 何谓聚类？ 英文为clustering，与classification不同，也可以称为grouping 简单地说，就是将一组向量分成若干组，组内数据是相似的，而组间数据是有较明显差异 数据相异性的度量(dissimilarity measure)比聚类算法更重要 是机器学习(machine learning)中的概念 是一种无监督的学习（unsupervised learning），不同于像 SVM 那样需要样本库的训练 何谓k-means? k-means是一种经典的聚类算法 由James MacQueen于1976年提出，但算法本身就已经由Stuart Lloyd 于1957年给出 给定一系列N维向量，和一个聚类数目的变量k，该算法将这些向量聚为k类 通常我们将每个向量映射为欧氏空间里的一个点，距离越近越相似，即把欧氏距离作为相异性度量 k-means 是一种迭代式(iterative)算法 算法过程 从数据中随机抽取k个点作为初始聚类的中心，由这个中心代表各个聚类 计算数据中所有的点到这k个点的距离，将点归到离其最近的聚类里 调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）处，也就是k-means中的mean的含义 重复第2步直到聚类的中心不再移动，此时算法收敛 下面是摘自pluskid博客的图例 图例（初始聚类） 图例（第一次迭代） 图例（下一次迭代） 图例（最终结果） 刚才的图例是第一种比较好的结果，下面是由于初始点选择较差而导致的差的聚类结果，同样也是摘自pluskid的博客 糟糕的图例（初始聚类） 糟糕的图例（最终结果） 算法特性 只能对数值数据进行处理 只能局部最优，不一定是全局最优（不同的起始点可能导致不同的结果），例如上面的糟糕图例 效率很高，计算聚类中心的算法复杂度为 O(N) k值可以通过其他的算法来估计，如： BIC(Bayesian information criterion) MDL(minimum description length) 在欧式距离作为相异性度量时工作良好，但其他距离度量时则需要更为通用的算法如k-medoids，但k-medoids效率较差（计算聚类中心的复杂度为O(N2)） k-means的改进 初始聚类的选择，尽可能分散，不要挤在一起 多次选择不同的初始点，将结果平均之 k-medoids是泛化的k-means(generalized k-means)能有效地处理非欧氏空间的问题 GMM(Gaussian Mixture Models)与k-means类似，但是算出的是概率