K-Mean

K-Means 即K均值聚类，属于划分聚类。

工作原理：

根据初始化的聚类中心信息，计算每个样本到这些中心的距离 ，可以判断每个样本均归属于某个类簇，更新聚簇中心信息，重新计算每个样本到新的聚类中心的距离，重新划分样本到新的聚类中心对应的类中，重复进行，直到满足终止条件。

有N个样本点，使用K-Means将其聚类的步骤：

1. 确定聚类的个数k，并指定k个聚类的中心C1，C2...Ck；

2. 计算每个样本Si 点到k个中心的距离，并将该店归入最近的Cj 类中，其中 i∈(1,N), j∈(1,k);

3. 重新计算k个类簇的中心点，更新原有中心点的位置C1，C2...Ck

4. 重复步骤2、3，直到中心点位置不在发生变化或变化幅度小于约定阈值，或者大导预定义的最大循环次数，结束。得到最终聚类结果。

   实现步骤

第一步，确定聚类个数，确定聚类中心，确定距离计算公式

• 观察法
• 枚举法
• 其他技术手段

确定距离公式：常用欧氏距离计算

第二步，计算每个点和聚类中心的距离，归类；

第三步，计算当前类簇中心，更新聚类中心Ck的位置；

重复第二步，将各样本Si 点根据新聚类中心Ck进行重新划分；

重复第三步，根据最新聚类计算聚类中心，更新中心Ck取值；

重复第二步，第三步，知道聚类中心位置不在发生变化，或者循环次数大导预先设定的阈值，结束。得到最终聚类结果

实现伪码

选择k个点作为初始类簇中心

repeat

    将每个样本点指派到最近的类簇中心，形成k个类簇
    重新计算每个类簇的中心
until 类簇不发生变化 or 达到最大迭代次数

k-means优缺点

• 优点
  • 原理简单，容易理解，容易实现
  • 聚类结果容易解释
  • 聚类结果相对较好
• 缺点
  • 分类个数k需要事先指定，且指定的k值不同，聚类结果相差较大
  • 初识的k个类簇中心对最终结果有影响，选择不同，结果可能会不同
  • 能识别的类簇仅为球状，非球状的聚类效果差
  • 样本点较多时，计算量较大
  • 对异常值敏感，对离散值需要特殊处理