入门机器学习(十五)--无监督学习(K均值)
1.无监督学习-简介(Unsupervised Learning-Introduction)
如下图所示是一个典型的监督学习，训练集中的每一个样本都有标签，我们需要根据标签来拟合一个假设函数。
什么是无监督学习呢? 如下图所示，训练集的每一个样本都没有标签，我们需要将一系列无标签的训练数据输入到一个算法中，然后这个算法可以根据这些没有标签的样本，找到可以对样本进行分类的结构。这种学习方式被称为无监督学习，这种算法被称为聚类算法。
聚类算法经常被应用在比如市场分割，社交网络分析等等很多领域。
2. K-均值算法(K-Means Algorithm)
K-均值算法是最普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的组。K-均值是一个迭代算法，它的实现过程是这样的：
下图中的数据集使我们要实现分类的无标签数据。
① 我们选择K个随机的点，称为聚类中心(cluster centroids)，K就是“K-均值”中的K，表示的是样本要进行分类的数目，在本例中K=2。我们随机地选择连个聚类中心，分别用红色的叉和蓝色的叉表示。
② 对于数据集中的每一个数据，按照距离聚类中心点的距离，将其与距离最近的中心点关联起来，组成一个类。如下图所示，与红色的聚类中心距离近的点被分为红色的类，与蓝色的聚类中心距离近的点被分为蓝色的类。
③ 计算每一个类中样本的平均值，将该类的聚类中心移动到平均值的位置。如下图所示，聚类中心进行了相应的移动。
④ 重复步骤②，将样本进行重新分类，如下图所示：
⑤ 重复步骤③，再次移动聚类中心。
⑥ 重复步骤②，将样本进行重分类。
⑦ 依次类推，重复步骤②③，一直迭代，直到聚类中心不在变化。
上述几张图很生动地展示了K-均值算法是如何将无标签的样本进行分类的，下面来说一下这个算法的伪代码是怎么实现的：
其中表示聚类中心，
用来存储与第i个样本最近的聚类中心的索引。
K-均值算法分为两个步骤，第一个for循环是赋值步骤：对于第i个样本，另其属于的类的值赋值给c^(i); 第二个for循环是聚类中心的移动，对于每一个聚类中心，重新计算其所属类中样本的平均值并移动该聚类中心。
我们举的例子都是视觉上有很明显分割的数据，那么对于分类不明显的数据，K-均值算法能够进行分类吗？答案是肯定的。如下图所示的数据集是T恤的尺码与身高和体重的关系。
假设要对该数据集分成三类，分别是S,M,L码，应用K-均值算法之后，分类结果大致如下图所示：
3. 优化目标(Optimization Objective)
K-均值的最小化问题，是要最小化所有的数据点与其所关联的聚类中心之间的距离之和，因此K-均值的代价函数(又称为畸变函数Distortion function)可以表示为：
其中代价函数中的表示样本i所关联的那个聚类中心，比如x^(i)属于第5类，那么c^(i)=5,
就是
我们的优化目标就是找出使得代价函数最小的
4.随机初始化(Random Initialization)
根据K-均值的伪代码，在运行K-均值算法之前，我们首先要随机初始化K个聚类中心点，具体的步骤为：
① 我们应该选择K<m，即聚类中心点的个数要小于所有训练集实例的数量；
② 随机选择K个训练实例，然后令K个聚类中心分别和这个K个训练实例相等。
K-均值的问题在于，他有可能会停留在一个局部最小值出，这个问题的出现和聚类中心的初始化有很大的关系。举个例子来说，对于下面这个无标签数据集：
如果K个聚类中心选择的比较好，那么分类结果也会比较好：
如果聚类中心随机选择的不好，那么分类可能不尽人意：
这种情况是K-均值算法的代价函数达到了局部最优而不是全局最优造成的。
那么怎么解决这个问题呢？我们通常需要多次运行该算法，每一次都重新随机初始化，然后选择代价函数最小的那个结果，伪代码可以表示为：
做100次随机化选择K个聚类中心，然后选择使代价函数最小的那一次作为聚类中心。这种方法在K比较小的时候（2-10）还是可行的，但是如果K的值比较大的话，这种方法可能也不会有明显的改善。
5. 选择聚类数(Choosing the Number of Clusters)
对一组数据集（如下图所示），我们可以将其分为四类，也可以分为两类，但是究竟分成几类比较好呢？
有一个可以帮我们选择聚类的方法被称为“肘部法则”(Elbow method)
如上图左所示，我们将分类的数目K与代价函数的关系表示出来，会得到类似于人类手臂的一条曲线，在“手肘”的部分所对应的K值是比较合理的聚类的个数。这种情况是比较理想的情况，一般情况下，得到的曲线图上图右所示是一条平滑的曲线，并没有“手肘”的部分，这样并不能确定K的值，这时可以结合自己的实际需求来确定合适的K值。
附：聚类参考资料