K-均值算法

（机器学习课堂作业中出现过）

K-均值算法（K-means）是一种距离计算聚类，同时也可以理解为一种原型聚类，希望由簇中样本的平均值来代表整个簇。

把 个点划分到 个聚类中，使得每个点都离其的聚类中心。给定样本集 ， 均值算法针对聚类所得簇划分 最小化均方误差

最小均方误差在一定程度上刻画了簇内样本围绕簇均值当紧密程度。误差平方和达到最优（小）时，可以使各聚类的类内尽可能紧凑，而使各聚类之间尽可能分开。对于同一个数据集，由于k-means 算法对初始选取的聚类中心敏感，因此可用该准则评价聚类结果的优劣。通常，对于任意一个数据集，k-means 算法无法达到全局最优，只能达到局部最优。

算法

  • 求得最优解需要考虑样本集 所有可能的划分，是 NP 难问题
  • 使用贪心策略，通过迭代优化近似求解
  • 算法首先初始化 个簇中心，之后将每一个样本点划分到与簇中心距离最短的簇中，再重新计算簇中心，由此迭代进行，直到聚类结果保持不变。

输入：样本集 ，聚类簇数

输出： 个簇

过程：

  • 从 中随机选择 个样本作为初始均值向量
  • 重复：
    • 基于每个簇的平均值，将每个样本重分配到与之最相似的簇中
    • 为每个簇重新计算平均值
  • 直到不发生变化

特点

  • 是一种解决聚类问题的一种经典算法，简单、快速
  • 对处理大数据集，该算法相对可伸缩性和高效率，算法复杂度为 ，其中 为样本个数， 为簇的个数， 是迭代次数。
  • 当结果簇是密集的，球状的，它的效果较好

不足：

  • 在簇的平均值被定义的情况下才能使用，可能不适用于某些应用
  • 必须事先给出要生成的簇的数目
  • 而且对初值敏感，不同的初始聚类中心的选择会对结果有较大影响
  • 对噪声和离群点数据敏感
  • 不适合发现非球状簇

举例

例1

假设现在有六个点 ，分别记为 ，如果要求划分为两个簇，并且选取 和 作为初始点

解：

第一次迭代，先分别考察各点距离哪一个中心最近

距离矩阵
0 1 1
1 0 5
聚类归属 1 1 2 2 2 2

因此第一次迭代聚类结果为 ，计算新的聚类中心为

第二次迭代，先分别考察各点距离哪一个中心最近

距离矩阵
0.5 0.5
聚类归属 1 1 1 2 2 2

因此第一次迭代聚类结果为 ，计算新的聚类中心为

第三次迭代，先分别考察各点距离哪一个中心最近

距离矩阵
聚类归属 1 1 1 2 2 2

因此第一次迭代聚类结果为 ，与上一次迭代结果不变，因此迭代收敛。得到最终聚类结果。

例2

假设现在有 8 个点 ，分别记为 .如果要求划分为两个簇，并且选取 和 作为初始点

解：

  1. 按照距离最近原则，，，得到新的聚类中心为
  2. 按照距离最近原则，，，得到新的聚类中心为
  3. 按照距离最近原则，仍为 ，，此时收敛，聚类结束

性能评价

可以采用误差平方和进行评价

Interactive Graph
Table Of Contents
K-均值算法
算法
特点
举例
例1
例2
性能评价