在前文介绍的分类算法中，如果所有训练数据都有标签，则为有监督学习算法；如果数据没有标签，显然就是无监督学习算法了，即聚类算法。在监督学习中，分类算法的效果还是不错的，但相对来讲，聚类算法就有些“惨不忍睹”了。确实，无监督学习算法本身的特点使其难以得到如分类算法一样近乎完美的结果。在无监督学习算法中，我们基本不知道结果会是什么样子的，但可以通过聚类的方式从数据中提取一个特殊的结构，进行探究性研究，寻找各种方法。
那什么是聚类算法呢？聚类算法是在没有任何标签的情况下进行分类的算法，类似分类算法。那既然没有标签，算法如何工作呢？聚类算法根据功能可以分为基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于标签传播的聚类算法等，本章将对这几种算法进行讲解。
5.1K均值凝聚聚类
5.1.1算法介绍
K均值凝聚聚类又称K-means，属于基于划分的聚类算法。基于划分的聚类算法对样本数据进行划分，每一个类别代表一个簇。其原理简单来说就是，假设具有一堆样本，这些样本都没有标签，现在需要进行聚类，想要达到的聚类效果就是类别之内的点都离得足够近，不同类别的点都离得非常远。首先要确定这堆散点最后聚成几类，然后挑选几个点作为初始中心点，再对数据点进行迭代重置，直到最后得到想要的目标效果。
根据上述被称为启发式的算法，形成了K-means算法及为了处理类似的问题所形成的算法K-modes、K-medians、kernel K-means等。基于划分的聚类算法中比较常用的就是K-means。本节重点讲解K-means 算法。
K-means是聚类算法中最简单的，也是聚类算法中最实用的，平常使用次数也比较多。K-means 算法的“K”表示类别数，“means”表示均值。K-means算法就是一种通过均值对数据进行分类的算法。算法的原理很简单，对于给定的数据，一般按照数据之间的欧氏距离分为K个聚类。让聚类间的距离相对比较小，而聚类与聚类之间的距离相对比较远，这就是高内聚、低耦合。代码如下：
在K-means中有两个参数比较重要：n_clusters表示要生成的聚类数，默认值为8；n_init表示用不同的聚类中心初始化值运行算法的次数，最终解是在运行算法n_init次后选出的最优结果。K-means算法的迭代过程如下：首先通过n_clusters选择K个聚类，直接生成K个中心点作为均值定量，或者随机选择K个均值定量，然后将其作为聚类中心点；对每个点确定其聚类中心点；再计算其新聚类中心点。重复以上步骤直到满足收敛要求（通常就是确定的中心点不再改变），如图5-1所示。
看过K-means算法后，我们很容易将其与KNN算法搞混，因为它们都有一个相似的过程，就是都需要找到离某一个点最近的点，二者都采用了最近邻的思想。
其实它们的差别还是挺多的。K-means算法是无监督学习的聚类算法，而KNN算法是监督学习的分类算法。KNN算法基本不需要训练，只要从测试集里面根据距离度量公式找到K个点，用这K个点表示测试集的类别即可，而K-means算法有明显的训练过程，需要反复迭代找到K个类别的最佳中心来决定数据的类别。
5.1.2 算法实现
接下来利用make_blobs数据集生成3类数据，观察聚类效果。代码如下：
输出结果如图5-3所示。 先设置K值为3，然后随机从数据中找出3个点作为3个均值定量，再计算所有数据点到这3个点的距离，将数据分配到距离最近的一类，用不同的颜色表示数据所属的各类，经过第一轮的迭代后从各类中可以计算新的均值定量，然后计算每个数据点到各类的距离，并把数据点分到距离最近的类中，重复上述步骤，最终得到合适的均值定量来表示类别。当然在实际运用该算法时，一般要多次迭代才能得到理想的结果，在本数据集中仅迭代一次就得到了最终聚类的均值定量。对于K-means算法，还可以观察其决策边界。
5.1.3 算法的优缺点
1、优点 (1）K-means原理简单、实现容易，是解决聚类问题的一种经典算法，具有可伸缩性，且效率高，当数据集较密集时，它的效果较好。 (2) K-means算法的可解释性较强，需调整的参数只有聚类数K。
2、缺点 (1）K-means必须事先给出K值，而且对初始值敏感，对于不同的初始值，可能会有不同的结果。 (2）K-means对噪声和孤立点数据敏感。 (3) K-means采用迭代方法，得到的结果只是局部最优结果。
5.2层次聚类
5.1节对基于划分的聚类算法一K-means算法进行了讲解，本节将对基于层次的聚类算法进行讲解。
5.2.1算法介绍
基于层次的聚类算法最开始将所有点都看成簇，簇与簇之间通过接近度实现划分，通过不同的接近度划分出不同的簇。层次聚类算法还可以根据层次分解的顺序分为凝聚的层次聚类算法和分裂的层次聚类算法。
凝聚的层次聚类是一种自底向上的策略，指许多基于相同原理构建的聚类算法，算法的原理如下：所谓凝聚的层次聚类是指让算法在一开始的时候，将每一个点作为一个簇，计算两两之间的最小距离，每一次选代算法都将距离最小的两个簇合并成一个新簇，然后合并这些新簇为更大的簇，直到所有对象都在一个簇中，或者满足某个终止条件为止。
sklearn中实现该算法需满足的终止条件是类的个数为指定个数，当剩下指定个数的类时，算法自动停止。绝大多数层次聚类属于凝聚的层次聚类，它们只在簇间相似度的定义上有所不同。凝聚的层次聚类算法的原理如图5-5所示。
分裂的层次聚类与凝聚的层次聚类相反，采用自顶向下的策略，它首先将所有对象置于同一个簇中，然后将其逐渐细分为越来越小的簇，直到每个对象自成一簇，或者满足了某个终止条件为止。该算法一般较少使用。
凝聚的层次聚类和分裂的层次聚类没有好坏之分，只不过在处理实际问题的时候要根据样本类型和目的来考虑是凝聚的层次聚类合适还是分裂的层次聚类合适。至于划分簇的方法，有最短距离法、最长距离法、类平均法等，其中类平均法通常被认为是最常用也最好用的方法。接下来介绍凝聚的层次聚类算法在sklearn中的参数。sklearn库下的层次聚类算法存储在klearm.cluster的AgglomerativeClustering中。
这里的参数中重要的是n_clusters和linkage。n_clusters表示簇的个数，凝聚的层次聚类是不需要指定簇的个数的，但是sklearm的这个类需要指定簇的个数。算法会将簇的个数作为终止条件，这个参数会影响聚类质量。linkage表示链接方式，即划分簇的方式，AgglomerativeClustering库中包含3种链接方式。
(1)ward链接：是默认选项，通过挑选簇中点的方差增量最小的两个簇来合并，通过这种连接方式通常得到大小差不多的簇。
(2)average链接：将簇中所有点之间平均距离最小的两个簇合并。
(3)complete链接：也称为最大链接，将簇中点之间最大距离最小的两个簇合并。
ward适用于大多数数据集。如果簇中的成员个数相差很大，那么average或complete可能效果更好。
5.2.2算法实现
下面是对数据集分别采用3种链接方式得到的结果。代码如下：
参数linkage的取值依次为'ward'、'average''complete'。参数为'ward'的凝聚的层次聚类如图5-6所示。
对于'average'参数，不仔细看的话会误认为凝聚成了3类，其实凝聚成了4类，有一类只有一个样本，在图5-7中右上角。然后将参数改为'complete'，如图5-8所示。
从图5-6~图5-8中可以看到，选择不同的链接方式，效果各不相同，在实际应用中可以通过对每种链接方式的测试，选择理想的方式。
在层次聚类中还有一种算法比较常用，那就是Birch算法。Birch算法用层次方法来聚类和归约数据，它主要用于对大型数据集进行高质量的聚类。其原理是利用树结构来帮助我们快速地聚类，这个树结构类似于平衡B+树，一般将它称为聚类特征树。Birch算法通过扫描所有数据，建立初始化的聚类特征树，把稠密数据分成簇，稀疏数据作为孤立点对待，然后对建立的树进行筛选，去除异常节点，对距离非常近的簇进行合并。
Birch算法涉及的主要参数为簇的个数n_clusters、扫描阈值threshold、每个节点中聚类特征子集群的最大数量branching_factor（默认值为50)。最后通过读取computelabels来获取每个数据点的分类情况。
5.2.3算法的优缺点
优点 （1）层次聚类中距离和规则的相似度容易定义，限制少。 （2）层次聚类不需要预先指定聚类个数。 （3）层次聚类可以发现类的层次关系。
缺点 （1）层次聚类计算复杂度太高。 （2）层次聚类中的奇异值能产生很大影响。 （3）层次聚类算法很可能将模型聚类成链状。
5.3 DBSCAN
5.3.1 算法介绍
带噪声应用的基于密度的聚类（density-based spatial clusteringof applicationwith noise,DBSCAN）算法是一种基于密度的算法，这种算法通常根据数据的紧密程度进行分类，如果一个数据属于该类，则在其附近一定还存在属于该类的数据。通过将紧密分布的数据分为一类，就得到了一个聚类类别。通过将所有数据划分为不同类别，就得到了最终的聚类类别结果。该算法将具有足够密度的区域内的数据划分为一类，并在具有噪声的数据集中划分出不同形状的类别，它将类定义为密度相近的点的最大集合。
那么DBSCAN算法是怎么基于密度工作的呢？在一个数据集中，我们的目标是把数据中密度相近的聚为一类。先从数据中选择一点，然后按照一定规则寻找密度相近的点组成一类，其他的数据点也是如此。这个规则就是根据这个被选中的数据点画一个圆，规定这个圆的半径以及圆内最少包含的数据数，再在包含在内的数据中转移中心点，那么这个圆的圆心就转移到内部数据点，继续用相同的半径画圆去圈附近其他的数据点。一直重复上述过程，继续增加数据点，直到没有符合条件的数据为止。
基于密度工作有什么好处呢？我们知道K-means聚类算法只能根据距离进行计算，而现实中有各种形状的图，例如环形图，这时K-means算法就不适用了。于是可以使用根据数据的密度进行分类的算法——DBSCAN。
DBSCAN算法包括两个重要的参数，这两个参数比较难指定，公认的指定方法有以下两种。
(1）半径（eps)半径是比较重要的一个参数，如果半径过大，圈住的点多了，类别的个数就少了，反之圈住的点少了，类别的个数就多了。这对最后生成的结果非常重要。
(2)min_samples：这个参数表示圈住的点的个数，也相当于密度，一般先让这个值尽可能地小，然后进行多次尝试。
上述是DBSCAN算法的主要内容，相对比较简单，但是还有几个问题没有考虑。第一个问题是一些数据点远离于其他数据点，这些点不在任何一类的周围。在DBSCAN中，一般将这些点标记为噪声点。第二个问题是距离的度量问题，即如何计算某样本和核心对象样本的距离。DBSCAN一般采用最近邻思想，采用某一种距离度量方式来衡量样本距离例如欧氏距离，这和KNN分类算法的最近邻思想完全相同。
5.3.2 算法实现
下面对DBSCAN算法进行应用。先生成环状数据（见图5-10),代码如下：
从图5-10中可以看到分类结果一目了然。接下来再生成双半月数据（见图5-11），代码如下:
依据图5-11来看，分类仍然正确。还可以将DBSCAN算法与K-means算法和凝聚的层次聚类算法进行对比（见图5-12）代码如下：
输出结果如图5-13所示。 可以看到前文讲到的两种算法对这种数据集并不适用，DBSCAN算法在处理这些数据时的效果显而易见得好，所以根据不同的问题选择合适的算法是关键。
5.3.3 算法的优缺点
优点 (1)DBSCAN速度快。该算法不需要提前设定K值大小，不需要事先知道要形成的类别的数量。 (2)DBSCAN对噪声不敏感。该算法可以在聚类的同时发现异常点，对数据集中的异常点 不敏感。 （3）DBSCAN能发现任意形状的簇。这是因为该算法能够较好地判断离群点，并且即使错 判离群点，最终的聚类结果也没受什么影响。 (4)DBSCAN形成的类别没有偏倚，而K-means之类的聚类算法的初始值对聚类结果有很 大影响。
缺点 （1）DBSCAN对参数的设置敏感，当半径和密度变化时会很大程度地影响结果。 (2）当数据量较大时，DBSCAN要求的内存也大。 (3）当空间密度不均匀、聚类间距相差很大时，DBSCAN算法聚类质量较差。
5.4 Mean Shift
5.4.1 算法介绍
MeanShift 算法，即均值聚类算法，也是一种基于密度的聚类算法，但它是一种基于核密度的估计算法。
MeanShift算法通过高斯核函数迭代的过程，不需要事先知道数据的概率密度分布函数，仅依靠对各数据的计算，就能够在一组数据的密度分布中寻找局部最优解。而且它在采样充分的情况下，一定会收敛，即可以对服从任意分布的数据进行密度估计。MeanShift在聚类、图像分割、视频跟踪等方面有着广泛的应用。
MeanShift算法的聚类过程如下：有多个初始随机中心，每个中心都有一个半径为bandwidth的圆，我们要做的就是求解一个向量，使得圆心一直往数据集中密度最大的方向移动，也就是每次选代的时候，都以圆内点的平均位置作为新的圆心位置，直到满足某个条件时不再选代，这时候的圆心也就是密度中心，如图5-14和图5-15所示。
在MeanShift算法中，不需要定义簇的个数，只需要规定圆的半径，之后计算圆内圆心到所有点的向量距离的均值，如果圆内其他点作为圆心的距离均值都小于该圆心，该圆就不再继续移动。下面是Mean Shift 算法的参数：
bandwidth表示带宽，可以理解为设定的圆的半径。bin_seeding用于设定初始随机中心的位置参数的方式，默认为False，表示采用所有点的位置平均值，当为True时，表示采用离散后的点的位置平均值，前者比后者的计算速度要慢。
5.4.2 算法实现
对于DBSCAN算法，我们知道它也是基于密度的算法，而且能处理像环状数据、双半月数据这样的数据集，那么同为基于密度的算法，MeanShift算法是不是也可以处理这样的数据集呢？接下来通过实例来测试一下。
可以看到结果并没有像我们想象的那样，MeanShift对这类数据集并不能很好地做出预测。接下来调整一下参数，看看会有何种变化。发现不论如何调整参数，并不能获得像DBSCAN算法中那样的效果，但是将bandwidth增至0.7时，可发现整个数据集全部被分成了一类。
那么Mean Shift算法适用于什么情况呢？我们知道Mean Shift 算法是一种概率密度梯度估计的算法，其实K-means算法也是一种概率密度梯度估计的算法，所以可以利用K-means算法所使用的数据集，来观察MeanShift算法的情况。
对于这两个算法，其预测模型几乎无异。其实MeanShift算法主要用于视觉处理相关的场合，这里就不多阐述了。
5.4.3 算法的优缺点
1.优点 （1）Mean Shint算法计算量不大、不敏感，采用核函数直方图模型，在目标区域已知的情况下完全可以做到实时跟踪。 (2)Mean Shift算法只需设置带宽这一个参数，不需要设置簇的个数。 (3)Mean Shift 算法结果稳定，不需要进行类似K-means的样本初始化。
2.缺点 (1)Mean Shift跟踪过程中由于窗口宽度大小保持不变，当目标尺度有所变化时，跟踪就会失败。 (2)Mean Shift聚类结果取决于带宽的设置。带宽设置过小，收敛速度比较慢，簇的个数就会比较多；带宽设置过大，跟踪效果不好。
5.5 标签传播
5.5.1 算法介绍
标签传播（label propagation）算法属于半监督学习算法。半监督学习是监督学习与无监督学习相结合的一种学习方法。它主要利用少量含有标签的样本和大量无标签的样本进行训练。半监督学习是模式识别和机器学习领域重点研究的问题，对于减少标注代价、提高机器学习性能具有非常重大的实际意义。
之所以会出现半监督学习，是因为所给的样本数据集中，有时会出现有的样本有标签而有的样本没有标签的情况。在实际问题中这样的数据集并不少见，通常数据集只有少量的含有标签的数据，而如果对数据进行标记，代价会很高。实际中大量未标记的数据很容易得到，缺乏的并不是数据，而是带标签的数据。
虽然有大量的数据没有标签，但是它给我们提供了数据分布的信息。通常假定这些数据是可以实现分类的，只不过缺失了标签值。半监督学习使用的数据，小部分是标记过的，而大部分是没有标记过的。与监督学习相比较，半监督学习的成本较低，而且还能获得较高的准确度。
半监督学习又可以划分为半监督分类、半监督回归、半监督聚类和半监督降维算法。半监督分类可在无标签的数据上训练有标签的数据，这样能够弥补有标签的数据的不足，得到比只训练有标签数据的模型更好的模型。半监督回归可在无输出的输入上训练含有输出的输入，能够获得更好的回归模型。半监督聚类可在有标签数据的帮助下获得更好的簇，提高聚类算法的精度。半监督降维可在有标签数据的帮助下找到高维数据的低维结构，同时保持原始高维数据及其结构不变。具体的半监督学习方法有自训练、直推学习、生成式模型、基于差异的方法等，本节主要讲解半监督聚类中的标签传播算法。
标签传播算法是一种基于标签传播的局部社区划分算法。标签传播算法类似于监督学习算法中的KNN算法，主要依照标签相似度进行聚类。标签传播算法认为越相邻的两个数据点越有可能属于同一个标签，通过对一些含有标签的数据点，判断相邻数据点之间的相似性，对未标记的数据点进行划分。通过迭代，每个数据点的标签与其邻接数据点中出现次数最多的标签相同，直到达到收敛要求为止。此时具有相同标签的数据点即属于同一个社区。
标签传播算法的聚类过程如下：在初始阶段，标签传播算法为所有数据点均指定唯一的标签，那么n个数据点就有n个不同的标签，然后通过选代将每个数据点的标签更改为其邻接数据点中出现次数最多的标签，如果这样的标签有多个，则随机选择一个。在每一次迭代的过程中，每一个数据点根据与其相连的数据点所属的标签更改自己的标签，更改的原则是选择与其相邻的数据点中所属标签最多的社区标签为自已的社区标签，这便是标签传播的含义。随着社区标签的不断传播，最终紧密连接的数据点将拥有共同的标签。
标签传播算法利用网络的结构指导标签的传播过程，在这个过程中无须优化任何函数。如果其邻接数据点与其相似度越相近，则表示对其标签的影响权值就越大，邻接数据点的标签就更容易被传播。在算法开始前不必知道社区的个数，随着算法的迭代，最终算法将自己决定社区的个数。
标签传播算法的参数，主要是核kernel的选择，可选择的核有 knn、rbf、callable。半监督学习在本书中只作为选读内容，并不做重点介绍。
5.5.2 算法实现
因为sklear数据集中不存在一部分数据含有标签、一部分数据不含标签的数据集，所以先利用make_blobs数据集，并将其处理成需要的数据集。代码如下：
5.5.3算法的优缺点
优点 （1）标签传播算法的聚类过程比较简单，速度比较快。 （2）标签传播算法时间复杂度低，适合大型复杂网络。
缺点 (1）标签传播算法随机性强。 （2）标签传播算法每次选代的结果不稳定，准确率不高。
5.6 小结
本章介绍了 5种聚类算法，分别是K-means、层次聚类、DBSCAN、Mean Shift 和标签传播。K-means算法在数据集比较大的情况下也非常高效，时间、空间复杂度低。但其生成的结果容易是局部最优结果。它需要提前设定K值，对开始选择的K个点敏感。层次聚类可解释性强。研究表明通过这个算法产生的聚类一般都有效，可以解决一些不规则形状的数据的聚类问题。但层次聚类时间复杂度高，具有贪心算法的缺点，即“一步错步步错”。
DBSCAN对噪声不敏感，能发现任意形状的聚类。但是其对参数的设置敏感，当聚类的稀疏程度不同、空间密度不均匀、聚类间距相差很大时，聚类质量较差，即较稀疏的聚类会被划分为多个类或密度较大且离得较近的类会被合并成一个聚类。
MeanShift算法计算量不大，不敏感，采用核函数直方图模型，在目标区域已知的情况下完全可以做到实时跟踪。但聚类结果取决于带宽的设置。带宽设置过小，收敛速度比较慢，簇的个数就会比较多；带宽设置过大，跟踪效果不好。标签传播算法过程简单，时间复杂度低，速度快，但随机性强，准确率不高。
习题5
试分析K-means算法与KNN算法的异同点。
层次聚类算法可以划分为几种算法？这几种算法有何不同?
DBSCAN算法与MeanShift 算法都是基于密度的算法，但是侧重点有所不同，试说明 两者的侧重点。
标签传播是半监督学习中的聚类算法，半监督学习中除了聚类算法还有哪些算法？