十一、聚类

1. K-Means算法

现在我们要学的是目前为止第一个无监督算法，我们来看个例子来理解聚类算法中的K-Means算法。

现在我有一些样本，我想把它自动分为两类，那么我们先随机选取两个聚类中心。

然后就开始类内循环，每次循环都分两步，第一将离聚类中心近的点染成相同的颜色即分为己类，第二计算自己类别的样本均值，然后将聚类中心移动到均值点，再做相同的动作直至不能移动为止。

所以接下来看这个案例，先进行分类。

然后移动聚类中心。

然后再次分类 。

然后再移动聚类中心。

然后再分类。

最后再移动聚类中心，得到最终位置。

接下来，我们看看具体步骤。

K值算法（K-means algorithm）

首先，我们要输入要分出的簇数K和训练集。

然后进行我们上面提到的步骤，先随机选取聚类中心，然后反复进行循环操作：

对每个样本都计算其到每个聚类中心的距离，然后找出距离最小的那个，将其分类于它。

对每个类都计算类中所有样本的均值，然后将聚类中心移到均值处。

实际应用中，你可能会遇到一些不太好分类的情况，不会像左下图那样而是右下图T恤分类的例子，这时候分类的算法可能效果不会太好，不过K值算法仍然能分出三个类别，而设计师就可以通过分出的这三个类别观察这些样本的身高和体重，设计出相应适合大众人群的衣服大小。

2. 优化目标

这节课我们来讲讲K值算法的代价函数，有时候也称失真（Distortion）代价函数。

c(i)：表示x(i)所属的类别。

μk：表示聚类中心k。

μc(i)：表示x(i)所属的类别，这个主要用于下面的计算中。

3. 随机初始化

我们初始化时一般用的方法是，随机选取训练集中的样本直接作为聚类中心，所以有时候可能运气很好刚好分别选到两个簇中，但有时也会选到同个簇中，所以这可能会导致最终结果不相同。

正如下面所示，随机初始化可能会使K值算法得到**局部最优解（Local optima）**而不是全局最优解。

所以我们会进行多次随机初始化以寻求一个更好的结果，具体步骤如下：

假设我们进行100此循环，然后进行如上的步骤，每次循环都会计算一次J值，等循环结束后，我们就可以选取J值最小的那个例子去训练。而这种多次随机初始化的方法对于K比较小的时候十分有效，大概K在2-10的时候，但是当K十分大的时候，这种方法的效果就不会特别明显了。

4. 选取聚类数量

我们在选取聚类数量的时候可能会比较纠结，因为样本是没有标签的，分界线会比较模糊，难以划分类别，接下来我们先介绍一种方法叫肘部方法（Elbow method）。

我们可以通过画出J与K的图像观察曲线变化，如果想上图左侧曲线一样，就可以发现在K为3时是整个曲线的转折点，所以我们可以选取3作为聚类数量。但我们通常不用这种方法的原因是，一般曲线都会像上图右侧曲线那样，没有一个明确的转折点，就无法很好的选取聚类数量了。

还有一种方法，就是通过实际目的去选择聚类数量，还是用于市场分割设计T恤的那个例子。

我们可以去思考我要如何设计T恤的大小才能满足顾客的需求，我可能会选择K=3即分为S，M，L也可能会选择K=5等等，总之我是通过最终对于市场需求这个目的来选择聚类的数量。