此文是斯坦福大学 Andrew Ng 所开设的 Coursera 课程：Machine Learning 的课程笔记。
课程网址：
https://www.coursera.org/learn/machine-learning/home/welcome

---

1. Unsupervised Learning

之前课程中说到的学习，都是监督学习，即有一个label，明确告诉你这个样本，属于哪个类型，或者导致的值是多少。但是，如果我碰到没有label，或者我也不知道label是怎样的情况，但是我还是想要分成若干类。这样的问题，就是一种无监督问题。

聚类（clustering）

聚类是一种典型的无监督学习例子，但是聚类不等同于无监督学习，密度估计同样是一个典型的无监督学习例子。回到聚类，例如有下图：

每种样本（蓝色圆圈）都没有label指定类别，但是人眼一看就知道分成两类比较合适。如何让机器也知道如何分类呢？这就是聚类问题。

2. K-Means Algorithm

K-Means 算法是解决无监督学习的有效算法之一。K（大写）表示将样本分为K个类型。算法具体的过程通俗易懂，如下图所示：

配合上图，再作一些简单的解释：

K-Means 算法进行一段时间后。可能会出现某个中心点没有分配到任何一个样本点的情况，这个时候可以直接去掉这个分类变为 (K-1) 簇。

但是在某些情况我们很执着的要分为 K 簇，这种情况下需要随机确定一个新的聚类中心替代当前中心点，之后再次迭代。

Optimization Objective

K-Means 算法同样有着 cost function，目标同样是为了最小化 cost。cost 记为：

分析K-Means的两个主要步骤，簇分配是以μ为常量，c为变量；移动聚类中心是以c为常量，μ为变量。通过不断修改，减小 cost。

不同于回归问题，因为学习率过大导致随着迭代次数增加竟然还会增大 cost。聚类问题中不会出现这种问题（就没有学习率），聚类中随着迭代次数增加 cost 一定是逐渐下降的。

Random Initialization

之前只是说，随机化取得K个聚类中心。具体究竟如何执行呢？

（1）在m个样本中，随机取得K个样本 (K<m)

（2）令μ1,…,μK等同于所取到的K个样本

但是，有的时候因为初始化的随机性，会陷入局部最大值的情况。例如下图所示：

这样即使 K-Means 算法停止了，所取得的依然不是较好的分类方法，cost 依然十分大。怎么解决？多随机初始化几次！一般是运行50~1000次 K-Means 算法，取其中 cost 最小一次的结果。

Choosing the numbers of clusters

好吧，最后一个问题来了，究竟应该分成几类？K=？

这个问题没有标准解，依照可视化图来观察是个不错的主意。有一种特殊情况，如果K−J(cost)图如下图左边所示，圆圈所指位置为“肘区”，一般我们取“肘区”所对应的 K 值。这种方法也称为 Elbow method.

但是绝大多数时候，我们看到的是如下图右边的情况，这种时候……好吧看你的心情以及实际需求（最多只能承受多少类的负担）取值吧。

如果出现K−J(cost)图随着 K 值的增加上下起伏，那说明出现了“局部最大值”的问题。这个时候就应该使用上一小节提到的，多进行几次 K-Means 算法，求出一个J(cost)最小时的 cost 作为当前 K 值的 cost.