无监督学习-聚类
引言
文章根据udacity 的机器学习视频进行整理，提供给初学者进行参考。主要围绕几种聚类算法：K-Means、层次聚类、DBSCAN、高斯混合模型聚类(GMM) 几种聚类算法进行叙述。简单讲述算法原理、算法在sklearn中实现、相关应用案例的论文、算法优缺点等。最后介绍评价聚类算法的两种指标：调整兰德系数和轮廓系数。
相关参考学习视频：
udacity--机器学习（PS：国外导师视频课程，中文字幕。课程简洁易懂、生动形象。具有项目实战、导师项目审核特色。比较推荐入门。点击此处可获得课程优惠券）
coursera--吴恩达机器学习(PS: 吴恩达的机器学习一直备受入门的欢迎。内容详细、由浅入深。)
书籍：吴恩达机器学习笔记
1. K均值聚类(K-Means)
1.1 算法概述
K-均值是最普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的组。
K-均值是一个迭代算法，假设我们想要将数据聚类成 n 个组，其方法为:
1. 首先选择 k 个随机的点，称为聚类中心(cluster centroids), 也叫质心;
2. 对于数据集中的每一个数据，按照距离 K 个中心点的距离，将其与距离最近的中心点关联起来，与同一个中心点关联的所有点聚成一类。
3. 计算每一个组的平均值，将该组所关联的中心点移动到平均值的位置。
可视化均值聚类过程。可在此点击进行详细了解。该网站将均值聚类的方法通过动态画方式进行展示，可以帮助理解均值聚类的过程。
1.2 K-Means 性质
K-Means 在指定质心之后，需要进行多次迭代。在“多次迭代”和“更新质心”的中，会算法最终达到收敛。但不幸的是算法最终会收敛，但是收敛最终集群却不唯一，这取决于初始化的质心的位置。如何初始化质心的位置？（可见1.3 K-Means 初始化策略）
K-Means 需要先指定 k 值，即聚类的数量。通常情况下，并不知道聚类的数量为多少？选择聚类数量可通过肘部法 (见1.4 选择聚类的数量)。
1.3 K-Means 初始化策略
如何初始化K-Means质心的位置？ 有三种方法：
1. 随机初始化所有的聚类中心点。随机选择 K 个训练实例，然后令K个聚类中心分别于K个训练实例相等，但有可能会停留在一个局部最小值处，这取决于初始化情况。解决这个问题，通常需要多次运行 K-均值算法，每一次都重新进行随机初始 化，最后再比较多次运行 K-均值的结果，选择代价函数最小的结果。这种方法如果K比较大，那么效果不会有明显改善。
2. 以“最远的”启发式方法实现。随机初始化第一个质心，然后将第二个质心初始化为距离它最远的数据点。
3. k-means ++。基于 K-Means 的改进。它的工作方式与“最远的”启发式相似，不同的是，它选择了一个点，其概率与其到最近的质心的距离的平方成正比，而不是选择第j个质心为距前一个质心最远的点。
1.4 选择聚类的数量
通常情况下，选择聚类的数量是需要根据不同的问题，人工进行选择的。选择的时候思考运用 K-均值算法聚类的动机是什么，然后选择能最好服务于该目的标聚类数。
当选择聚类数目时，通常会用到一个 “肘部法则” 的方法：
关于“肘部法则”，所需要做的是改变 k 值，也就是聚类类别数目的总数。这里利用K-均值的代价函数（又叫畸变函数）如图：
选择的K值不同，代价函数表现表现也不一样。通常情况下是 K 值越多，代价函数越小。但在实际中 K 值(代表聚类数量) 不是要越多越好。K 值和代价函数之间通常可表现如下图：
上图中，可以看到这样的曲线，像一个人的肘部。K 的选择从 1 到 2 ，2 到 3 时代价函数 J 下降最大。在 3 之后代价函数 J 下降变缓。看起来当选择 K = 3 时是相对比较好的。
选择聚类数目也可以参考 轮廓系数。见“6.3 内部评价指标-轮廓系数”
1.5 K-Means 的表现
K-Means在具有大致相等大小和大致规则形状的聚类的数据集中效果最好。但在一些 “月牙数据” 中，K 值表现就不尽人意。如下图K-means在一些数据集中的表现结果。
尽管有利有弊，但k-means算法还是聚类分析中的主要工具：它可在许多实际数据集上很好地工作，并且相对较快，易于实现且易于理解。许多改进或推广k均值的聚类算法，例如：k中值，k medoids，k-means ++和用于高斯混合的EM算法。
1.6 Sklearn 中的 K-Means
sklearn 中封装 K-Means API
exmaple ：
2. 层次聚类(Hierarchical Clustering)
2.1 概述
层次聚类(Hierarchical Clustering)是聚类算法的一种，通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。层次如同公司内部的人员体系，最高层是老板、老板下面是部门经理、部门经理下面是每个部门的员工。
层次聚类可以直观的了解类之间的关系。如下图：
2.2 四种不同的层次聚类法
2.2.1 概述
层次聚类法在主要有：单链接聚类法、全链接聚类法、组平均聚类、离差平方和法。四种不同的层次聚类算法基本原理基本相同，主要区别在于衡量距离的方式不同。
2.2.2 单链接聚类
基本原理:
1. 假设数据特征如下图模式：
2. 先假设每个点是一个类，然后计算任意两个类之间的距离。把距离最近的两个类合并成一个类。建立第一层，
如下图：将 1 和 2 合并为一类；4 和 5 合并为一类；6 和 8 合并为一类；3 、7 单独为一个类。
3. 在上面的基础上再计算两个类之间的距离。把距离最近的两个类合并为一个类。组建为第二层。
上图中可见：7 类 距离 [6,8] 类比较近。 这里注意单链接算法中两个类的距离，是以两个类中两点之间的最短距离为标准，如：7 到 6 的距离。由此，可将 3 、1、2 合并为一类；7、6、8 合并为一类。
4. 以此建立为一个完整的系统树。如下图：
单链接聚类法衡量距离的方法是两类之间两点最短的距离。将距离最短的类合并。如下图：
2.2.3 全链接聚类法表现
全链接聚类中衡量距离的方法是两类中最远的两点之间的距离，这样的衡量方法使得产生的类比较紧凑。
但是这些点可能是其他类中的一部分，全链接聚类法就忽视了它们，只考虑最远的两点。因此需要考虑其他方法，可参考下面的组平均和离差平方法。
如下图两个类中两点之间的最远距离：
2.2.4 组平均聚类法
组平均聚类法计算的是任意两点之间的距离，然后取平均值。
如下图：
2.2.4 离差平方和法
离差平方和法是sklearn中预设的一种层次聚类法。这种方法的目的就是把合并类时的变量最小化。
离差平方和法计算两类间距离的方法：
1. 找一个中心点，取所有点之间的平均位置，所得即为中心点。
2. 然后计算所有点与中心点之间的距离。分别计算其平方、再相加
3. 再减去类中的变量平方。找到类中变量的方法：找到每个类的中心点，然后计算类中点到中心点的距离。
下图中：X 为中心点、C 为两类中的点到中心点的距离、A 和 B 分别为类中变量的平方。
2.3 表现
层次聚类中各种聚类算法在数据集中的表现：
优点：
层次表达、内容鲜明、把聚类结果可视化。特别是当数据有层次结构的时候，例如生物学。
缺点：
对噪音和离群值比较敏感。需要提前清理噪声
计算量大。如果数据规模大、算法的执行会比较慢。
案例：
把分泌蛋白聚类，并创建不同的类表示不同种类的真菌
2.4 sklearn 中的层次聚类
sklearn 中的层次聚类法：https://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering
sklearn 中的层次聚类API：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.FeatureAgglomeration.html#sklearn.cluster.FeatureAgglomeration
如果需要绘制层次树，需要借助 SciPy ：
3. 密集聚类(DBSCAN)
3.1 概述
密集聚类指的是具有噪声的基于密度的聚类方法。对噪声具有很强的适用性。一般是把密集分布的点进行聚类，再将剩余的点标记为噪声。这种算法对 “月牙” 数据非常适用
3.2 基本原理
1. 假定这是对应的数据特征：
2. DBSCAN 在开始时任意选择一点。选择这个点后，查看点的领域。所谓领域是由 Epsilon 界定的，在算法开始时候指定。假如指定 Epsilon = 1 如下图：
3. 该点的领域内没有任何点，则它不属于任何类，标记为噪声。再重新选择一个点查看领域。
4. 如果重新选择的点中，包括其他点。需要查看包含点的数量是否满足指定数量。这里的指定数量用MinPts 指定，也是在算法开始时指定。假如指定 MinPts = 5 。表示领域内必须由5个或5个以上的点才满足要求，否则标为噪声。如下图找到Cluster 1
5. 同时再继续寻找，如果遇到多个数据点紧凑在一起，如下图，则标记为 cluster 2
3.3 表现
DBSCAN与K-Means 算法对比，在各种数据集的表现：
优点
不需要指明类的数量。DBSCAN能根据点的分布密度找到类。
不受限于某种外形的类，能灵活找到并分离各种形状和大小的类
能处理噪声和离群值
缺点
从两个类可达的边界点被分配给另一个类，因为这个类先发现的这个边界点，由于各个点被随机拜访，这种情况不能保证回传相同的聚类。但这种情况大多数数据集不会出现。
在找到不同密度的类方面有一定的困难。基于这个可以用DBSCAN的变体HDBSCAN 即具有噪声的基于密度的高层次空间聚类算法
应用案例
网络流量的研究。论文：Traffic Classification Using Clustering Algorithms
对温度数据值做异常检测论文：Anomaly detection in temperature data using dbscan algorithm
3.4 sklearn 中的DBSCAN
sklearn 中的DBSCAN ：https://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering
sklearn 中 DBSCAN 的 API：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN
4. 高斯混合模型聚类(GMM)
4.1 概述
高斯混合模型聚类(Gaussian Mixture Models) 是一种相对温和的聚类算法。意思是数据中的每个点，每个样本都属于现有的类。只是隶属不同。
例如：有这样的一组一维数据集。
高斯混合模型算法会检查每个点，算法会认为该点似乎是由高斯分布产生的。由此产生不同的隶属度。如下图：
高斯混合模型聚类算法是一种相对超前的算法。这种算法假设每个类都遵循统计分布的规律，它利用大量的概率和统计学知识来找出这些类。生活中很多都数据分布都遵循高斯分布(也叫正太分布) 的规律。如学生成绩、人的身高。
4.2 一维高斯混合模型
4.2.1 一维高斯分布
1. 简单概述一维高斯分布。以考试成绩为例，考试成绩一般都遵循高斯分布，如下图：
2. 上图中，中间可能有重叠的部分，无法看清，这时候需要借助柱状体表示。柱状图的高度即为学生取得的分数。其中最高的柱状表示频次最多。即该分数段的学生最多。如下图：
3. 由柱状图可以描述高斯分布或正太分布的曲线，同时描述正太分布曲线的数字有：平均值、标准差。在统计学中，以平均值为中心，向左减一个标准差，向右则加一个标准差。在1个标准差的范围内数据概率是 68%。（详细可见统计学知识）。如下图：
4.2.2 一维高斯混合模型聚类
同样借助考试成绩为例来描述一维高斯混合模型聚类。如下图的数据集。
1. 假设数据集是由数学成绩和物理成绩混合的，因为是混合而成的数据，所以它并不是高斯分布。如下图：
2. 但是在高斯混合模型中，能够通过高斯混合分布，找到这是两个类。高斯混合分布本身并不是高斯模型，而是两个高斯混合模型的混合物，但包含两个高斯分布。借助高斯分布，判断点属于对应的类。
如下图：
4.3 二维高斯混合模型聚类
4.3.1 二维高斯分布
1. 同样以考试成绩为例，如下图是学生的两门考试成绩，包含了平均值和标准差。
2. 借助二维图表，把 chemistry Score 设置为 X 轴，Geology Score 设置为 Y 轴。将对应的数据投射到图表中。如下图：
3. 可以看到每个变量呈现高斯分布，因此被称为多维高斯状态分布。如果用一种视觉化看待，圆心是两条轴的平均值，第一个椭圆是每条轴的平均值或加或减标准差，包含 68 % 的数据，第二个椭圆包含95%的数据集，第三个包含 99% 数据集。
4.3.2 二维高斯混合模型聚类
1. 假设有这样的两组数据，均为多变量高斯分布，也叫二维高斯分布。如下图：
2. 假设现在将两组数据集混合之后，无法检索原来的数据集。现在得到的数据集也不符合高斯分布。但我们知道这是由两个符合高斯分布的数据集混合而成的。如下图：
3. 到此实现利用高斯分布规律找到两个类，需要借助期望最大化算法(EM）。
算法步骤：
step 1: 初始化K个高斯分布(在本例中 K = 2)。需要给它们均值和标准差，有很多方法可以实现。最朴素方法是将它们设置为数据集本身的平均值。实践中还有一种更好的方法，是在数据集上使用K均值，然后使用K均值生成聚类初始化高斯分布。
在这个例子中，我们选取任意点，为每个高斯选择随机均值和随机方差(方差不是标准差，方差是标准差的平方) 。到此完成了第一步，如下图：
step 2: 将数据软聚类成初始化的的两个高斯。这一步骤称为 E 步骤。
数据集中，每个点有两个值，可以看着 feature1 和 feature2 。该步骤需要计算每个点的隶属度。
计算方式如下图：
step3: 基于软聚类重新估计高斯。这一步骤称为M步骤
该步骤是将 step2 中的所有点对聚类的隶属度，用这些隶属度为高斯模型提出新的参数，即新的均值和方差。所以该步骤以 step2 的结果作为输入，输出新的均值和方差
新的均值计算：
新的方差计算：
现在有了新方差和均值，对比之前的均值和方差，可以看到有微微移动。这样的过程可能需要重复5、10、20、30次直到收敛。
step4: 利用评估对数似然来检查收敛。如果收敛，则返回结果。否则返回第二步反复进行，直到收敛
通过选取的方差、均值来最大化。其结果可以表示为，值越大，说明该模型里有需要的数据集
4.3.3 期望最大化示例
在上一节中使用高斯混合模型找到聚集的数据集。
如下图：（黄色圆圈为需要找到的数据集）
上图中很明显使用圆形的高斯分布，无法收敛得到最终的两个类。这是因为没有选择好初始化参数。我们需要做一个更好类型的初始化来初始化K值。这里可先使用K-Means的结果初始化高斯模型。使用K-Means做高斯混合模型的默认值，协方差为 full ，初始化将是K-Means的默认值。如果我们进行这个一个过程，将可能是这样的。如下图：
这可能是最近两个数据集的模型，这就是高斯混合模型实现的。其他聚类模型或许无法实现。
4.4 表现
优点：
提供软聚类，软聚类是多个实例属性的隶属度。（比如说：你正在对文档进行分类，并且希望每个文档有多个主题和类别。高斯混合模型聚类对这类场景很有用）
聚类方面具有灵活性，一个聚类中可以包含另一个聚类
缺点：
对初始化值比较敏感，可能收敛的局部最优，但不是全局最优。
收敛速度慢
相关应用论文：
Nonparametric discovery of human routines from sensor data
Application of the Gaussian mixture model in pulsar astronomy
参考：
4.4 Sklearn 中的高斯混合模型
sklearn 中高斯混合模型的API：https://scikit-learn.org/stable/modules/generated/sklearn.mixture.GaussianMixture.html?highlight=mixture#sklearn.mixture.GaussianMixture
5. 聚类分析过程
使用各种聚类算法的目的主要在于将数据集 data 转化为 知识knowledge 。这个聚类算法的分析过程如下图，选择聚类算法只是其中一步。
step 1 ：特征选择和特征提取
特征选择：从一组候选特征中选择特征，不必对所有的数据集使用聚类方法，有时候数据集特征可能有成千上百。进行聚类需要消耗大量的资源，我们需要使用一些工具来选取特征。
特征提取：对数据进行转换，以生成有用的特征。最好的例子是PCA即主成成分分析。
step 2 : 选择聚类算法。
根据数据的特征选择合适的算法。通常是试验那一种算法能有更好的结果。没有一个算法普遍适合。
step 3 ：聚类评价。
即评估一个聚类的效果如何，因此除了在情况下对结果进行可视化之外，还需要一些评估方法，这些方法被称为指数，每一个指数称为聚类的有效评价指标。
step 4 ：聚类结果的解释
可以从最终聚类结构中得到什么样的见解
6. 聚类验证
6.1 概述
聚类评价是客观和定量评估聚类结果的过程。聚类评价指数有三种：外部指标、内部指标、相对指标
外部指标：这是处理有标签数据集时候使用的评分。因此在有标签数据集的情况下，可使用外部指标来进行评价。
内部指标：在数据集没有标签的情况下，则需要采用内部指标进行评价。仅使用数据来衡量数据和结构之间的吻合度。
相对指标：这些指标表明两个聚类结构中，哪一种在某种意义上更好。基本上所有的外部指标都能作为相对指标。
大多数评价指标都是通过紧凑性和可分性来定义的。紧凑性是衡量一聚类中元素之间彼此的距离。可分性是不同聚类之间距离
6.2 外部评价指标-调整兰德系数
外部评价指标是当数据集有标签时使用的评分方法。
在下图中可以看到在sklearn中给定的评分方法和范围。输入原始的标签，它会产生在范围内的一个得分。大多数在[0,1] 内。但调整兰德系数在[-1, 1]。
调整兰德系数中，调整兰德系数中 ARI 值为评价指标，ARI 越接近 1 。聚类结构越好。
可参考论文：Details of the Adjusted Rand index
6.3 内部评价指标-轮廓系数
内部评价指标是当无数据标签时使用的评价指标。
在下图中可以看到在sklearn中给定的评分方法和范围。其中给定的轮廓系数评分范围在[-1, 1] 内。它会给任何一个聚类在[-1,1] 之间的一个评分
轮廓系数评价指标
1. 假设这是一个已经聚类完成的数据集。需要利用轮廓系数进行评价打分。
2. 轮廓系数评分公式：
参数 a ： 同一个聚类中到某个点其他样本的平均距离，如下图，蓝色直线的距离。
参数 b：b 是某个点距离其他类中的点最近的距离平均值。如下图，就是黄色直线距离。
将a 和 b 代入公式即可得到轮廓系数。
获取每个点的轮廓系数，取平均值。就得到这个聚类的轮廓系数。
3. 参考不同数据集情况下， K 值情况下轮廓系数的。可得知K=3时候聚类结构最好。同时可以借助轮廓系数来找到最优的 K 值，即聚类数量。
但在DBSCAN下不能使用轮廓系数。
在“圆形”数据集情况下，DBSCAN聚类效果比较好，但是评分却比较低。如下图举例，所以在DBSCAN中，可参考基于密度的聚类验证
