非监督学习

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

1 K均值聚类

支持向量机、逻辑回归、决策树等经典的机器学习算法主要用于分类问题，即根据一些已给定类别的样本，训练某种分类器，使得它能够对类别未知的样本进行分类。

与分类问题不同，聚类是在实现并不知道任何样本类别标签的情况下，通过数据之间的额内在关系把样本划分为若干类别，使得同类别样本之间的相似度高，不同类别之间的样本相似度低。

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

知识点：K均值聚类算法，ISODATA算法，EM算法

问题：简述K均值算法的具体步骤

K均值聚类的核心目标是将给定的数据集划分成K个簇，并给出每个数据对应的簇中心点。

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

缺点：例如受初值和离群点的影响每次的结果不稳定、结果通常不是全局最优而是局部最优解、无法很好地解决数据簇分布差别比较大的情况（比如一类是另一类样本数量的100倍）、不太适用于离散分类等。

优点：对于大数据集，K均值聚类算法相对是可伸缩和高效的，它的计算复杂度是O(NKt)接近于线性，N是数据对象的数目，K是聚类的簇数，t是迭代的轮数。尽管算法经常以局部最优结束，但一般情况下达到的局部最优已经可以满足聚类的需求。

K均值算法的调优一般可从以下几个角度出发：

（1）数据归一化和离群点处理

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

（2）合理选择K值

K值得选择是K均值聚类最大的问题之一，这也是K均值聚类算法的主要缺点。

手肘法，认为拐点就是K的最佳值
手肘法是一个经验方法，缺点就是不够自动化。

Gap Statistic方法

（3）采用核函数

面对非凸的数据分布形状时，可能需要引入核函数来优化，这时算法又称为核K均值算法，是核聚类方法中的一种。

核聚类的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，引入核函数可以达到更为准确的聚类效果。

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

主要缺点：
（1）需要人工预先确定初始K值，且该值和真实的数据分布未必吻合。
（2）K均值只能收敛到局部最优，效果受到初始值很大。
（3）易受到噪点的影响
（4）样本点只能被划分到单一的类中

• K-means++算法：

K均值的改进算法中，对初始值选择的改进是很重要的一部分。而这类算法中，最具影响力的是K-means。

原始K均值算法最开始随机选取数据集中K个点作为聚类中心，而K-means++按照如下的思想选取K个聚类中心。假设已经选取了n个初始聚类中心，则在选取第n+1个聚类中心时，距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第一个聚类中心时同样通过随机的方法。当选择完初始点后，K-means++后续的执行和经典K均值算法相同，这也是对初始值选择进行改进的方法的共同点。

• ISODATA算法

当K值大小不确定时，可以使用ISODATA算法（迭代自组织数据分析法）。

思想：当属于某个类别的样本数过少时，把该类别去除；当属于某个类别的样本数过多、分散程度较大时，把该类别分为两个子类别。

ISODATA算法在K均值算法的基础之上增加了两个操作，一是分裂操作，对应着增加聚类中心数；二是合并操作，对应着减少聚类中心数。

ISODATA算法是一个比较常见的算法，缺点是需要指定的参数比较多，不仅仅需要一个参考的聚类数量K，还需要制定3个阈值。

各个输入参数：
（1）预期的聚类中心数目 $K_0$
（2）每个类所要求的的最少样本数目$Nmin$
（3）最大方差σ。用于控制某个类别中 样本的分散程度。当样本的分散程度超过这个阈值时，且分裂后满足（2），进行分裂操作。
（4）两个聚类中心之间所允许最小距离Dmin。如果两个类靠的非常近，小于该阈值，则对这两个类进行合并操作。

问题：证明K均值算法的收敛性

2 高斯混合模型

高斯混合模型（GMM），即用多个高斯分布函数的线性组合来对数据分布进行拟合。也是一种常见的聚类算法，与K均值算法类似，同样适用了EM算法进行迭代计算。高斯混合模型假设每个簇的数据都符合高斯分布（又叫正态分布），当前数据呈现的分布就是各个簇的高斯分布叠加在一起的结果。

知识点：高斯分布，高斯混合模型，EM算法

高斯混合模型的核心思想是，假设数据可以看做从多个高斯分布中生成出来的。在该假设下，每个单独的分模型都是标准高斯模型，其均值和方差都是待估计的参数。此外，每个分模型都还有一个参数π，可以理解为权重或生成数据的概率。

高斯混合模型的计算，便成了最佳的均值、方差、权重的寻找，这类问题通常通过最大似然估计来求解。然而，此问题中直接使用最大似然估计，得到的是一个复杂的非凸函数，目标函数是和的对数，难以展开和对其求偏导。

因此，用EM算法框架来求解该优化问题。EM算法是在最大化目标函数时，先固定一个变量使整体函数变为凸优化函数，求导得到最值，然后利用最优参数更新被固定的变量，进入下一个循环。

具体到高斯混合模型的求解，EM算法的迭代过程如下：
首先，初始随机选择各参数的值。然后，重复下属两步：
（1）E步骤。根据当前的参数，计算每个点由某个分模型生成的概率。
（2）M步骤。根据E步骤估计出的概率，来改进每个分模型的均值，方差和权重。

高斯混合模型与K均值算法的相同点是，它们都是可用于聚类的算法；都需要指定K值；都是用EM算法来求解；都往往只能收敛于局部最优。而它相比于K均值算法的优点是，可以给出一个样本属于某类的概率是多少；不仅仅可以用于聚类，还可以用于概率密度估计；并且可以用于生成新的样本点。

3 自组织映射神经网络

自组织映射神经网络（SOM）是无监督学习方法中的一类重要方法，可以用作聚类、高维可视化、数据压缩、特征提取等多种用途。

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

区别：

（1）K均值算法需要事先定下类的个数，也就是K的值。而自组织映射神经网络则不用，隐藏层中的某些节点可以没有任何输入数据属于它，因此聚类结果的实际簇数可能会小于神经元的个数。而K均值算法受K值设定的影响要更大一些。
（2）K均值算法为每个输入数据找到一个最相似的类后，只更新这个类的参数；自组织神经网络则会更新临近的节点。所以，K均值算法受noise data的影响比较大，而自组织映射神经网络的准确性可能会比K均值算法低（因为也更新了临近节点）
（3）相比较而言，自组织映射神经网络的可视化比较好，而且具有优雅的拓扑关系图。

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

• 设定输出层神经元的数量
  输出层的神经元的数量和训练集样本的类别数相关。
• 设计输出层节点的排列
  输出层的节点排列成哪种形式取决于实际应用的需要，排列形式应尽量直观的反映出实际问题的物理意义
• 初始化权值
• 设计拓扑领域
• 设计学习率

4 聚类算法的评估

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

为了评估不同聚类算法的性能优劣，需要了解常见的数据簇的特点：

• 以中心定义的数据簇：这类数据集合倾向于球形分布，通常中心被定义为质心，即此数据簇中所有点的平均值。集合中的数据到中心得距离相比到其他的簇中心的距离更近。
• 以密度定义的数据簇：这类数据集合呈现和周围数据簇明显不同的密度，或稠密或稀疏。当数据簇不规则或互相盘绕，并且有噪声和离群点时，常常使用基于密度的簇定义。
• 以连通定义的数据簇：这类数据集合中的数据点和数据点之间有连接关系，整个数据簇表现为图结构。该定义对不规则形状或者缠绕的数据簇有效。
• 以概念定义的数据簇：这类数据集合中的所有数据点具有某种共同性质。

聚类评估的任务时估计在数据集上进行聚类的可行性，以及聚类方法产生结果的质量。这一过程又分为三个子任务：
（1）估计聚类趋势
这一步骤是检测数据分布中是否存在非随机的簇结构。如果数据是基本随机的，那么聚类的结果也是毫无意义的。可以观察聚类误差是否随聚类类别数量的增加而单调变化，如果数据是基本随机的，即不存在非随机簇结构，那么聚类误差随聚类类别数量增加而变化的幅度应该较不显著，并且也找不到一个合适的K对应数据的真实簇数。

可用霍普金斯统计量来判断数据在空间上的随机性。

（2）判定数据簇数
确定聚类趋势之后，需要找到与真实数据分布最为吻合的簇数，据此判定聚类结果的质量。数据簇数的判定方法有很多，如手肘法和Gap Statistic方法。用于评估的最佳数据簇数可能与程序输出的簇数是不同的。

（3）测定聚类质量
在无监督的情况下，可以通过考察簇的分离情况和簇的紧凑情况来评估聚类的效果。
常见指标：
轮廓系数
均方根标准偏差（RMSSTD），可以看做经过归一化的标准差
R方（R-Square）:代表了聚类之后的结果与聚类之前相比，对应的平方误差和指标的改进幅度。