前言
此为本人学习《百面机器学习——算法工程师带你去面试》的学习笔记
第五章 非监督学习
引导语
非监督学习期望机器通过学习找到数据中存在的某种共性特征或结构，亦或是数据之前存在的某种关联。
非监督学习主要包含两大类学习方法：数据聚类和特征变量关联。其中，聚类算法往往通过多次迭代来找到数据的最优分割，而特征变量关联则是利用各种相关性分析方法来找到变量之间的关系。
1、K均值聚类
1、k均值聚类的基本思想是，通过迭代方法寻找K个簇（cluster）的一种划分方案，使得聚类结果对应的代价函数最小。特别的，代价函数可以定义为各个样本距离所属簇中心地点的误差平方和
其中代表第i个样本，
是
所属的簇，
代表簇对应的中心点，M是样本总数。
2、K均值聚类算法步骤：
数据预处理，如归一化、离群点处理等。(不归一化会影响误差平方和的计算，k均值对利群店敏感，影响簇中心点的计算)
随机选取K个簇中心，记为(初始化簇中心)。
定义代价函数：。
令t=0,1,2，...为迭代步数，重复下列过程直至J收敛。
（1）对每一个样本，将其分配到距离最近的簇：
（2）对于每一个类簇k，重新计算该簇的中心：
K均值在迭代时，假设当前代价函数没有达到最小值，则首先固定簇中心(最开始是随便选择K个中心)，调整每个样例数据所属的类别，选择最近的中心点，使代价函数减小；然后定下当前每个样例数据的类别后，调整簇中心使代价函数减小。交替进行，代价函数单调递减，最后中心点和样例数据所属的类别都收敛。
3、K均值的优缺点
优点：对于大数据集，K均值高效且可伸缩，它的复杂度为O(NKt)，接近于线性。其中N是数据对象的数目，K是聚类簇数，t是迭代轮数。
缺点：
（1）需要人工预设K值，且该值和真实数据分布未必吻合；
（2）受初值和离群点的影响，每次的结果不稳定；
（3）受初值影响，结果通常是局部最优；
（4）无法很好地解决数据簇分布差别比较大的情况（如一类是另一类样本数量的100倍）；
（5）不太适用于离散分布；样本点只能被划分到单一的类中。
4、K均值算法调优的方法：
预处理，数据归一化和离群点处理：K均值本质是一种基于欧氏距离度量的数据划分方法，均值和方差大的维度将对数据聚类结果产生决定性影响。离群点或少量噪声会对均值昌盛影响导致中心偏移。
合理选择K值：K值是实现设定的，这是一个主要缺点。K值的选择一般基于经验和多次试验结果。
（1）可以采用手肘法，尝试不同K值对应的损失，画出折线图，其该店就是手肘法认为的K的最佳值。
（2）手肘法是一个经验方法，不够自动化，有一个Gap Statistic方法，不需要肉眼判断，只需要找到最大的Gap Statistic对应的K即可。
采用核函数：面对非凸的数据分布形状时，可能需要引入核函数来优化，成为核K均值算法，是核聚类方法的一种。（通过非线性映射将空间数据点映射到高位的特征空间进行聚类）
5、K均值算法的改进模型：
k-means++：k-means最开始是随机选取数据集中的k个点作为聚类中心，K-means++改进了初始值的选择，会尽量使聚类中心越远越好。
ISODATA算法（迭代自组织数据分析法）：当遇到高维度、海量数据时，很难准确估计K的大小。其基本思想是当某个类别的样本数过少时，去除该类别；当某个类别的样本过多、分散程度较大时，分为你两个子类别（加入了分裂操作和合并操作）。其缺点是需要制定对的参数比较多，出去一个参考的K0，还有三个阈值用于分裂合并的判断。
为解决样本只能属于一个类，可以使用模糊C或高斯混合模型。
5、K均值的收敛性：K均值的迭代算法实际上是一种EM算法。EM (Expectation-Maximization algorithm)算法只能保证收敛到局部最优解。
2、高斯混合模型
1、高斯混合模型(Gaussian Mixed Model，GMM)也是一种常见的聚类算法，与K-means类似，都使用了EM算法进行迭代计算。高斯混合模型假设每个簇的数据都是符合高斯分布的，当前数据呈现的分布就是各个簇的高斯分布叠加在一起的结果。理论上，高斯混合模型可以拟合出任意类型的分布。
2、高斯混合模型的核心思想是，假设数据可以看做从多个高斯分布中生成出来的。在该假设下，每个单独的分模型都是标准高斯模型，其均值和方差
,此外，每个分模型都还有一个参数
,可以理解为权重或生成数据的概率。高斯混合模型公式如下：
3、高斯混合模型是一个生成式模型。
4、求解高斯混合模型的参数可以用EM算法框架，先固定一个变量使整体函数变为凸优化函数，求导得到最值，然后利用最优参数更新被固定的变量，进入下一个循环。也就是说每次循环时，先固定当前的高斯分布不变，或得每个数据点由各个高斯分布生成的概率。然后固定该生成概率不变，根据数据点的生成概率，获得一组更加的高斯分布。
5、高斯混合模型与K均值算法：
相同点：
（1）都是聚类算法
（2）都需要指定K值
（3）都用EM算法来求解
（4）往往只能收敛于局部最优
高斯混合模型的优点：
（1）可以给出一个样本属于某类的概率是多少；
（2）不仅仅用于聚类，还可以用于概率密度估计；
（3）可以用于生成新的样本点。
3、自组织映射神经网络
1、自组织映射神经网络（Self-Oraganizing Map，SOM）是无监督学习方法中的一类重要方法，可以用作聚类、高维可视化、数据压缩、特征提取等多种用途。
2、自组织神经网络本质上是一个两层的神经网络，包括输入层和输出层（竞争层）。输入层模拟感知外界输入信息的视网膜，输出层模拟做出相应的大脑皮层。输出层中神经网络的个数通常是聚类的个数。
训练时采用“竞争学习”的方式，每个输入样本在输入层中找到一个最匹配的节点，称为激活节点；紧接着用梯度下降法更新激活节点的参数；同时，激活节点临近的点也根据他们距离激活节点的远近适当地更新参数（模拟神经网络细胞的侧抑制现象，越远的更新程度越打折扣，但更远的则表现弱激励作用）。这种竞争可以通过神经元之间的横向抑制连接（负反馈路径）来实现。
3、自组织映射神经网络的自组织学习过程可以归纳为以下几个子过程：
（1）初始化：所有连接权重都用小的随机值初始化
（2）竞争：神经元计算每个输入模式各自的判别函数值，并宣布具有最小判别函数值的特定神经元为胜利者。
（3）合作：获胜的神经元决定了兴奋神经元拓扑领域的空间位置。确定激活节点后，更新节点，距离越远，更新程度越打折扣，但更远的则表现弱激励作用。
（4）适应：适当调整相关兴奋神经元的连接权重，使得获胜神经元对相似输入模式的后续应用的响应增强。
（5）迭代：回到（2）竞争步骤，迭代知道特征映射趋于稳定。
4、自组织映射神经网络具有保序映射的特点，可以将任意维度的输入在输入层映射为一维或二维图形，并保持拓扑结构不变。
5、自组织映射神经网络（SOM）与K-means。
SOM受K值影响要小一点，隐藏层中的某些节点可以没有任何输入数据属于它，因此聚类结果的簇可能会小于神经元的个数。将K设大一点即可。
SOM为每个输入数据找到一个最相似的类后，也会更新临近的节点，而K-means只更新这个类的参数。这样做有优点也有缺点，优点是SOM受噪声影响较小，缺点是准确性可能比K-means低（因为也跟新了临近节点）。
SOM的可视化比较好，而且具有优雅的拓扑关系图。
6、如何设计自组织映射神经网络并设定网络训练参数：
设定输出层神经元的数量：如果不清楚类别数，可以尽量设置较多的节点数。如果分类过细则酌情减少输出节点。 产生的从未更新过的“死节点”可以通过重新初始化权值来解决。
设计输出层节点的排列：对于一般的分类问题，一个输出节点能代表一个模式类，用一维线阵既结构简单又意义明确。对于颜色空间或旅行路径类问题，用二维平面比较直观。
初始化权重：可以随机初始化，但为避免大量初始“死节点”，可以从训练集中随机抽取m个输入样本作为初始权值。
设计拓扑领域：领域形状可以是正方形、六边形或者菱形。
设计学习率：一个递减函数。
4、聚类算法的评估
1、常见数据簇的特点：
以中心定义的数据簇：这类数据集合倾向于球形分布，通常中心被定义为质心（所有点的平均值）
以密度定义的数据簇：这类数据集合呈现和周围数据簇明显不同的密度。当数据簇不规则或相互盘绕，并且有噪声和离群点时，常常基于密度的簇定义。
以连通定义的数据簇：这类数据集合中的数据之间有连通关系，整个数据簇变现为图结构。对不规则形状或者缠绕的数据簇有效。
以概念定义的数据簇：这类数据集合中具有某种共同性质。
2、聚类评估的任务是估计在数据集上进行聚类的可行性，以及聚类方法产生结果的质量。这一过程分为三个子任务：
估计聚类趋势：这一步骤是检查数据分布中是否存在非随机的簇结构。如果数据是基本随机的，那么聚类结果毫无意义。我们可以观察聚类误差是否随聚类类别数量的增加而单调变化，如果数据是基本随机的，即不存在非随机簇结构，那么聚类误差随聚类类别数量增加而变化的幅度应该不限制，并且找不到合适的K。还可以用霍普金斯统计量(Hopkins Statistic)来判断数据在空间上的随机性。
判定数据簇数：找到与真实数据分布最吻合的簇数，据此判断聚类结果的质量。可手肘法或Gap Statistic等方法。需要说明是，用于评估的最佳数据簇数可能与程序输出的簇数是不同的。例如有些聚类算法可以自动确定K，但可能与我们通过其他方法得到的最优簇数有差别。
测定聚类质量：在无监督的情况下，我们可以通过考察簇的分离情况和紧凑情况来评估，常用的度量指标有：
(1)轮廓系数：与簇中数据紧凑程度和该簇与其他簇的分离程度有关。
(2)均方根标准偏差(Root-mean-square standard deviation，RMSSTD)：衡量聚类结果的同质性，即紧凑程度。
(3)R方(R-Square)：可以用来衡量聚类的差异度。
(4)改进的Hubert 统计：通过数据对的不一致性来评估聚类的差异。
此外，为了更加合理地评估不同聚类算法的性能，通常还需要人为构造不同类型的数据集，观察聚类算法在这些数据集上的效果，如下图：
