Unsupervised learning introduction

通过和监督学习进行对比，简单介绍了无监督学习。

在一个监督学习问题中，我们的训练集是有标签（y）的，我们需要据此训练假设函数，来拟合出一个决策边界。

而在无监督学习问题中，我们的训练集是没有任何标签的，我们需要算法自己从这些数据中找出隐藏的结构，比如聚类算法（clustering algorithm）就可能会把下面的数据划分为两个簇（cluster）。

K-means algorithm

主要介绍最常见的聚类算法——K-均值算法（k-means algorithm）。

Example

下面以一个简单的例子介绍K-均值算法的整个流程。

1. 我们希望把数据集分成两个簇，因此首先随机选择2个聚类中心（cluster centroid）：

   

2. 划分每个点所属的中心（相当于分成两类）：

   

3. 根据划分好的两簇，分别计算其中心点：

   

4. 根据计算出来的新的两个聚类中心，重新划分为两簇：

   

5. 根据划分好的两簇，分别计算其聚类中心：

   

6. 根据计算出来的新的两个聚类中心，重新划分为两簇:

   

7. 根据划分好的两簇，分别计算其聚类中心：

   

8. 根据计算出来的新的两个聚类中心，重新划分为两簇:

   

最终，聚类中心不再发生改变，聚类完成。

K-means algorithm

总结起来，K-均值算法的循环过程一共分为两个步骤：

1. 簇分配：对于每一个样例\(i\)，计算其所属的簇\(C^{(i)}\)；
2. 聚类中心的移动：对于每一类\(k\)，重新计算其聚类中心\(\mu^{(k)}\)。

首先初始化聚类中心，然后通过循环以上两步，得出最终的K簇以及对应的K个聚类中心。

伪代码如下：

K-means for non-separated clusters

我们讲解的例子都是不同簇之间间隔非常明显的，如下图所示。

但是实际上，K-均值算法也可以运用在没有明显区分的数据集上。比如我们有一些身高体重的数据集，我们就可以通过K-均值算法将数据分为3类，用于帮助确定要生产的T-shirt的3种尺寸。

Optimization objective

主要讲解K-均值算法的优化目标。

K-means optimization objective

• \(c^{(i)}\)：表示实例\(x^{(i)}\)所属的簇的索引；
• \(\mu_k\)：表示聚类中心（\(\mu_k \in \R^n\)）；
• \(\mu_{c^{(i)}}\)：表示与\(x^{(i)}\)最近的聚类中心点。

K-均值最小化问题就是要使得所有的数据点与其聚类中心之间的距离之和最小，因此K-均值算法的代价函数，又称畸变函数（Distortion funcion），为：

所以优化目标就是找出使得代价函数最小的\(c^{(1)},c^{(2)}, \cdots ,c^{(m)}\)和\(\mu_1,\mu_2, \cdots ,\mu_K\)。

K-means algorithm

回顾之前K-均值算法的循环过程中的两个步骤，可以得出其分别是在，

1. 簇分配：求解使得代价函数最小的\(c^{(1)},c^{(2)}, \cdots ,c^{(m)}\)；
2. 聚类中心的移动：求解使得代价函数最小的\(\mu_1,\mu_2, \cdots ,\mu_K\)。

Random initialization

主要讲解了如何随机初始化聚类中心，以及找到更好的局部最优解的方法。

Random initialization

在随机初始化聚类中心时，有很多的方法，但是有一种方法通常能得到更好的结果：

• 选择\(K \lt m\)，即聚类中心点的个数应该小于训练实例的数量；
• 随机选取\(K\)个训练实例，把这\(K\)个训练实例作为初始化的\(K\)个聚类中心。

E.g. \(K=2\)，那么初始化的聚类中心点可能如下：

Local optima

K-均值的问题在于有可能得到一个局部最优解，E.g. 左边的数据集有可能得到右边3种聚类结果，这取决于初始化的情况。

为了解决这个问题，通常的作法是多次运行K-均值算法，每次都重新进行随机初始化，最后再选取代价函数最小的结果。这种做法在\(K\)较小（E.g K=2-10）的时候通常能得到一个全局最优解，但是当\(K\)比较大的时候，可能不会有明显的改善。

Choosing the number of clusters

主要讲解了如何选择聚类数。

What is the right value of K?

实际上并没有所谓的最好的选择聚类数的方法，通常是通过可视化的方法进行人工选择的。这是因为无监督学习的数据集本身就是没有标签的，因此划分数据集本身就没有唯一“正确”的答案。

比如对于下面的数据集，划分成2个类或者4个类都是非常合理的选择。

当然在选择聚类数目的时候，还是有一些可以参考的方法，比如“肘部法则”（Elbow method）。

“肘部法则”的原理是通过不断地改变聚类数目\(K\)的值，然后分别计算代价函数，绘制出函数曲线，假如我们得到了类似下图的曲线，我们可以明显地看到在\(K=3\)地时候发生了一个拐点，类似于手的肘部，那么我们就可以选择聚类数目为3.

但是实际上我们通常得到的曲线是连续递减的，没有任何“肘部”，这就是“肘部法则”的局限性。

通常我们使用K-均值进行聚类，是有后续用途的，所以选择合适的类别\(K\)最好的方法应该是通过后续应用的一些指标，来判断应该选择什么样的\(K\)。

例如在T-shirt制造时，我们就可以通过想要得到更低的制造成本，还是想要使得顾客穿着更合适，来决定我们应该选择3个类别还是5个类别。