2.6　无监督与半监督学习

除了监督学习以外，机器学习还包含另外两个重要的模块：无监督学习（unsupervised learning）和半监督学习（semi-supervised learning）。它们与监督学习的主要区别在于数据是否有标注。如果对于所有的输入数据x，正确地输出数据y，则称为监督学习；如果对于所有的输入数据x都没有输出数据y，则称为无监督学习；如果有些输入数据有对应的输出，有些没有，则称为半监督学习。

因为数据标注工作往往非常繁琐费力，无监督学习和半监督学习在实际中都比较常见。不过人们发现，虽然在没有数据标注y的情况下，任何关于标注的预测学习都难以实现，但我们仍然可以完成一些重要的计算。下面用图2.9中的简单例子，介绍最常见的一个无监督学习的任务，叫做聚类（clustering）。

图2.9　聚类举例

所谓聚类，就是对于给定的数据按照某个标准分类。这种问题是非常常见的，例如我们会对用户人群进行分类，对考试出现的题型进行分类，对动植物进行分类，等等。虽然这种分类问题不一定有统一或者确定的答案，例如可以把用户人群按照收入分成3类，也可以按照年龄分成5类，或者用别的标准分类，等等。但是适当的分类可以让我们对数据有更加清晰地认识，提高算法的运行效率，或者快速找到相似的数据。

以图2.9为例。首先，我们注意到图中包含了很多个没有标签只有位置信息的点。这时，可以根据点与点之间的距离，把它们分成3类，分别标成黄色、蓝色和红色。这个聚类结果并不唯一，这是因为虽然大部分点确实形成了一个聚类，但在边缘上的点的归属并不非常明确。在图2.9的例子中，注意到最边缘的黄色点其实也可以被标成别的颜色。

下面介绍一个常见的聚类方法——K平均算法，用以将给定点集分成K个聚类（K为事先设定）。K平均算法的目标是找到一个聚类方案，使得它包含k个聚类，且各个聚类的点到其中心的平均距离尽可能小。具体来说，假设第i个聚类S_i的中心点是c_i，则K平均算法的目标是找到一个聚类分割方案，使得最小。

当然，要找到这个问题的最优解非常困难，K平均算法是解决这个问题的一种启发式算法。

K平均算法的具体步骤如下：

（1）随机选取K个中心点作为初始值；

（2）对于数据集中的每个点，分别找离它最近的中心点，将其归为相应的聚类；

（3）根据已有聚类的分配方案，对每个聚类（包括中心点和数据点）重新计算最优的中心点位置。具体来说，最优的中心点位置应该是该聚类所有数据点的平均位置。

（4）重复步骤（2）和步骤（3），直到算法收敛，即中心点的位置与聚类的分配方案不再改变。

步骤（1）中随机选初始值非常重要。这是因为采用固定的方法选择中心点很容易遇到一些特殊情况，导致K平均算法给出较差的结果。通过采用随机选择的方法，可以有效降低出现这种情况的概率。另外，随机选择也保证可以通过重复K平均算法选取最好的结果。

图2.10是一个K平均算法运行的例子。

图2.10　K平均算法举例

图2.10（续）

由于K平均算法是一个启发式算法，它不一定总能找到最优的解。但在实际运行过程中，它往往能够给出较好的聚类分配方案。同时，也可以证明K平均算法一定会收敛，因为它每次给出的聚类分配方案中，每个点到中心点的距离都是在不断减小的。