kmeans

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