第5章 　非监督学习

非监督学习的输入数据没有标签信息，需要通过算法模型来挖掘数据内在的结构和模式。非监督学习主要包含两大类学习方法：数据聚类和特征变量关联。其中，聚类算法往往是通过多次迭代来找到数据的最优分割，而特征变量关联则是利用各种相关性分析方法来找到变量之间的关系。

聚类则是非监督学习，算法有：

K均值聚类算法，ISODATA算法，EM算法（Expectation-Maximization Algorithm，最大期望算法）

K均值聚类（K-Means Clustering）

最基础和最常用的聚类算法，通过迭代方式寻找K个簇（Cluster）的一种划分方案，使得聚类结果对应的代价函数最小。特别地，代价函数可以定义为各个样本距离所属簇中心点的误差平方和：

5.1 简述K均值算法的具体步骤？

5.2 K均值算法的优缺点是什么？如何对其进行调优？

缺点：

受初值和离群点的影响每次的结果不稳定。

结果通常不是全局最优而是局部最优解。

无法很好地解决数据簇分布差别比较大的情况（比如一类是另一类样本数量的100倍）。

不太适用于离散分类等。

优点：

对于大数据集，K均值聚类算法相对是可伸缩和高效的。

计算复杂度是O(NKt)接近于线性，其中N是数据对象的数目，K是聚类的簇数，t是迭代的轮数。

尽管算法经常以局部最优结束，但一般情况下达到的局部最优已经可以满足聚类的需求。

调优：

1、数据归一化和离群点处理。

K均值聚类本质上是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性的影响，所以未做归一化处理和统一单位的数据是无法直接参与运算和比较的。同时，离群点或者少量的噪声数据就会对均值产生较大的影响，导致中心偏移，因此使用K均值聚类算法之前通常需要对数据做预处理。

2、合理选择K值。

K值的选择是K均值聚类最大的问题之一，这也是K均值聚类算法的主要缺点。实际上，我们希望能够找到一些可行的办法来弥补这一缺点，或者说找到K值的合理估计方法。但是，K值的选择一般基于经验和多次实验结果。例如采用手肘法，我们可以尝试不同的K值，并将不同K值所对应的损失函数画成折线，横轴为K的取值，纵轴为误差平方和所定义的损失函数，

3、采用核函数。

采用核函数是另一种可以尝试的改进方向。传统的欧式距离度量方式，使得K均值算法本质上假设了各个数据簇的数据具有一样的先验概率，并呈现球形或者高维球形分布，这种分布在实际生活中并不常见。面对非凸的数据分布形状时，可能需要引入核函数来优化，这时算法又称为核K均值算法，是核聚类方法的一种[6] 。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

5.3 针对K均值算法的缺点，有哪些改进的模型？

K均值算法的主要缺点如下。

（1）需要人工预先确定初始K值，且该值和真实的数据分布未必吻合。

（2）K均值只能收敛到局部最优，效果受到初始值很大。

（3）易受到噪点的影响。

（4）样本点只能被划分到单一的类中。

K-means++算法：

对初始值选择的改进，K-means++按照如下的思想选取K个聚类中心。假设已经选取了n个初始聚类中心（0<n<K），则在选取第n+1个聚类中心时，距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。

ISODATA算法：

当K值的大小不确定时，可以使用ISODATA算法。ISODATA的全称是迭代自组织数据分析法。在K均值算法中，聚类个数K的值需要预先人为地确定，并且在整个算法过程中无法更改。而当遇到高维度、海量的数据集时，人们往往很难准确地估计出K的大小。ISODATA算法就是针对这个问题进行了改进，它的思想也很直观。当属于某个类别的样本数过少时，把该类别去除；当属于某个类别的样本数过多、分散程度较大时，把该类别分为两个子类别。ISODATA算法在K均值算法的基础之上增加了两个操作，一是分裂操作，对应着增加聚类中心数；二是合并操作，对应着减少聚类中心数。ISODATA算法是一个比较常见的算法，其缺点是需要指定的参数比较多，不仅仅需要一个参考的聚类数量K o ，还需要制定3个阈值。下面介绍ISODATA算法的各个输入参数。

（1）预期的聚类中心数目K o 。在ISODATA运行过程中聚类中心数可以变化，K o 是一个用户指定的参考值，该算法的聚类中心数目变动范围也由其决定。具体地，最终输出的聚类中心数目常见范围是从K o 的一半，到两倍K o 。

（2）每个类所要求的最少样本数目N min 。如果分裂后会导致某个子类别所包含样本数目小于该阈值，就不会对该类别进行分裂操作。

（3）最大方差Sigma。用于控制某个类别中样本的分散程度。当样本的分散程度超过这个阈值时，且分裂后满足（1），进行分裂操作。

（4）两个聚类中心之间所允许最小距离D min 。如果两个类靠得非常近（即这两个类别对应聚类中心之间的距离非常小），小于该阈值时，则对这两个类进行合并操作。

如果希望样本不划分到单一的类中，可以使用模糊C均值或者高斯混合模型，高斯混合模型会在下一节中详细讲述。

5.4 证明K均值算法的收敛性？

？？？

高斯混合模型:

一种常见的聚类算法，使用了EM算法进行迭代计算。高斯混合模型假设每个簇的数据都是符合高斯分布（又叫正态分布）的，当前数据呈现的分布就是各个簇的高斯分布叠加在一起的结果.

5.5 高斯混合模型的核心思想是什么？它是如何迭代计算的？

自组织映射神经网络（Self-Organizing Map，SOM）:

是无监督学习方法中一类重要方法，可以用作聚类、高维可视化、数据压缩、特征提取等多种用途.

5.6 自组织映射神经网络是如何工作的？它与K均值算法有何区别？

在迭代结束之后，每个样本所激活的神经元就是它对应的类别。

5.7 怎样设计自组织映射神经网络并设定网络训练参数？

聚类算法的评估:

5.8 以聚类问题为例，假设没有外部标签数据，如何评估两个聚类算法的优劣？

聚类评估的任务是估计在数据集上进行聚类的可行性，以及聚类方法产生结果的质量。这一过程又分为三个子任务。

（1）估计聚类趋势。

这一步骤是检测数据分布中是否存在非随机的簇结构。如果数据是基本随机的，那么聚类的结果也是毫无意义的。我们可以观察聚类误差是否随聚类类别数量的增加而单调变化，如果数据是基本随机的，即不存在非随机簇结构，那么聚类误差随聚类类别数量增加而变化的幅度应该较不显著，并且也找不到一个合适的K对应数据的真实簇数。

（2）判定数据簇数。

确定聚类趋势之后，我们需要找到与真实数据分布最为吻合的簇数，据此判定聚类结果的质量。数据簇数的判定方法有很多，例如手肘法和Gap Statistic方法。需要说明的是，用于评估的最佳数据簇数可能与程序输出的簇数是不同的。例如，有些聚类算法可以自动地确定数据的簇数，但可能与我们通过其他方法确定的最优数据簇数有所差别。

（3）测定聚类质量。

给定预设的簇数，不同的聚类算法将输出不同的结果，如何判定哪个聚类结果的质量更高呢？在无监督的情况下，我们可以通过考察簇的分离情况和簇的紧凑情况来评估聚类的效果。定义评估指标可以展现面试者实际解决和分析问题的能力。