• 在 “无监督学习” 中，样本的标记信息是未知的，目的是通过对无标记训练样本的学习揭示数据的内在性质及规律，为进一步的数据分析提供基础。
• 聚类试图将数据集中的样本划分为若干个不相交的子集，每个子集称为一个 “簇”，子集的中心点称为 “簇心”。聚类过程仅自动形成若干个簇，簇所对应的意义由使用者来把握。
• 例如，聚类算法可根据西瓜的密度与含糖率划分为三个簇，使用者则可将这三个簇命名为 “甜西瓜”、“有点甜瓜”、“不甜瓜”。

k-means聚类

一、概括x

算法对原型进行初始化，然后对原型迭代更新求解。

二、补充

• 距离计算
  欧氏距离: d= \sqrt [] { \sum_{k = 1}^{n} {(x_1^k - x_2^k)^2}}
• 性能度量：
  平方误差：min E = \sum_{i=1}^k\sum_{x∈C_i}{||x-μ_i||_2^2}
• k的取值：
  1.横坐标为簇心数，纵坐标为损失函数（例如：平方误差的值）。若随着k值的增大，出现了明显的拐点，则取出现拐点时的k值，但未出现明显的拐点，则方法失效。
  
  Andrew Ng
  2.簇心数的取值是为了使用者接下来的用途服务的。
  例如：若T恤生产商需要生产S、M、L三种类型的T恤，则需要将购买者的数据划分为三类，取簇心作为生产模板，簇心k取3；若T恤生产商需要生产XS、S、M、L、XL五类型的T恤，则需要将购买者的数据划分为五类，取簇心作为生产模板，簇心k取5。

Andrew Ng

三、具体过程

输入：样本集D = {x₁,x₂,x₃,...,x_m}，聚类簇数k

过程：

从D中随机选择k个样本作为初始均值向量，即簇心向量{μ₁, μ₂,...,μ_k}
repeat:
令C{_i} = ɸ（1<= i <= k）
  for x in 样本D:
    计算样本与各簇心{μ₁, μ₂,...,μ_k}的距离
    x离哪个簇心近则将其划分到哪个簇（{C₁, C₂, ...,C_k }）
  计算新的均值向量（簇心向量）
  更新簇新{μ₁, μ₂,...,μ_k}
直到簇心向量未更新，或已最小化平方误差

输出：簇划分（簇标签与簇成员）

四、举个例子

输入：

聚类数k = 3，西瓜样本D如下图：

编号	西瓜密度	西瓜含糖率
1	0.697	0.460
2	0.774	0.376
3	0.634	0.264
..	...	...
30	0.446	0.459

过程:

1. 从D中随机选择3个样本作为初始均值向量{μ₁, μ₂, μ₃ }
   假设随机选取的样本为前三个样本，则μ_1 =(0.697, 0.460), μ_2 = (0.774, 0.376), μ_3= (0.634, 0.264)
2. 计算样本与各簇心{μ₁, μ₂,...,μ_k}的距离
   例如：第30个样本据簇心的欧式距离分别为：d_{(30,1)} = \sqrt [] { (0.446 - 0.697)^2 + (0.459 - 0.460)^2}=0.251、d_{(30,2)}~ =\sqrt [] { (0.446 - 0.774)^2 + (0.459 - 0.376)^2}=0.338、d_{(30,3)}~ =\sqrt [] { (0.446 - 0.634)^2 + (0.459 - 0.264)^2}=0.271
3. x离哪个簇心近则将其划分到哪个簇（{C₁, C₂, ...,C_k }）
   例如：d_(30,2)最大，故将第30个样本划分到C₂簇。
      簇划分的结果为：C_1={\{x_3, x_5, x_6, x_7, x_8, x_9, x_{10}, x_{13}, x_{14}, x_{17}, x_{18}, x_{19}, x_{20}, x_{23}}\} C_2={\{ x_{11}, x_{12}, x_{16}, x_{20} }\} C_3={\{x_1, x_2, x_4, x_{15}, x_{21}x_{22}, x_{24}, x_{25}, x_{26}, x_{27}, x_{28}, x_{29}}\}
4. 将样本都划分到3个簇后，计算新的均值向量，更新簇新{μ₁, μ₂,...,μ_k}
   例如：μ_{1new} =(0.493, 0.208), μ_{2new }= (0.396, 0.076), μ_{3new}= (0.602, 0.395)
5. 重复2-3步，直到簇心向量未更新，或已最小化平方误差：min E = \sum_{i=1}^k\sum_{x∈C_i}{||x-μ_i||_2^2}

参考资料：
《机器学习》 周志华
《machine learning》 Andrew Ng