MLK, 即 Machine Learning Knowledge, 本专栏在于对机器学习的重点知识做一次梳理, 便于日后温习, 内容主要来自于《百面机器学习》一书, 结合自己的经验与思考做的一些总结与归纳. 本次主要讲解的内容是机器学习里的非监督学习经典原理与算法, 非监督, 也就是没有 target(标签)的算法模型.
Index
K-Mean 聚类算法
高斯混合模型
自组织映射神经网络
聚类算法的评估指标
常见聚类算法对比
常见聚类算法的 Python 实现
在机器学习中存在一种问题, 那就是模型是没有 target 的, 给机器输入大量的特征数据, 期望机器可以学习出当中的共性或者结构又或者是关联, 并不需要像监督学习那样输出某个预测值.
K-Mean 聚类算法
K-Mean 的基本思想就是通过迭代的方式寻找 K 个簇 (Cluster) 的一种划分方案, 使得聚类结果对应的 Cost Function 最小, 一般 K-Mean 的 Cost Function 为各个样本距离所属簇中心点的误差平方和, 公式为:
其中 Xi 代表第 i 个样本, Ci 是 Xi 所属的簇,μci 代表簇对应的中心点, M 是样本总数.
首先先来看一下 K-Mean 算法的具体步骤描述:
1)数据预处理, 如归一化, 异常值处理;
2)随机抽取 K 个簇(K 由人工设定);
3)定义 Cost Function:
4)不断迭代下面步骤, 直到 CF 收敛:
对于每个样本 Xi, 将其分配到距离最近的簇:
对于每个簇, 重新计算簇中心:
K-Mean 的优点
1)对于大数据集, 算法还是相对高效的, 计算复杂度为 O(NKt), 其中 N 为样本数, K 为聚类数, t 为迭代的论数;
2)一般情况下都可以满足聚类的需求.
K-Mean 的缺点
1)需要人工确定 K 值, 人工对大数据的 K 值预判有的时候不太好;
2)K-Mean 很容易局部最优, 所以效果很受一开始的初始值影响;
3)容易受到异常值, 噪点的影响.
K-Mean 调优思路
1)数据归一化和异常值处理.
因为 K-Mean 本质上是基于欧式距离度量的数据聚类方法, 所以少量的极端值会影响聚类效果的, 而且不同量纲的数据也会有不一样的影响, 所以需要做一下预处理.
2)合理选择 K 值.
K 值并不是拍脑袋拍出来的, 需要用科学的办法去确定. 一般可以通过多次试验结果决定, 如采用手肘法:
其中, 横轴为 K 的取值, 纵轴为误差平方和所定义的 Loss Function.
可以看出, K 值越大, 距离和越小, 我们看到当 K=3 的时候, 曲线出现 "拐点", 因此一般我们选择这个点作为我们的 K 值.
此外, 这里还介绍一个 GS(Gap Statistic)方法, 可参考:
3)采用核函数.
传统的欧式距离度量方式使得 K-Mean 算法本质上是假设各个簇的数据具有一样的先验概率, 并呈现球形或者高维球形分布, 但这种分布在现实中不太常见, 这个时候我们引入一个核 K-Mean 算法, 主要面对非凸的数据分布.
这类核聚类方法主要是通过一个非线性映射, 将输入控件中的数据点映射到高位的特征空间中, 并在新的特征空间中进行聚类, 非线性映射增加了数据点线性可分的概率, 从而达到更高精度的聚类结果.
再说说两种算法
1)K-Mean++ 算法
这个从名字上看, 就是 K-Mean 的改良版, 主要是在初始值的选取上作了改进. 原先的 K-Mean 是随机选择初始值, 而 K-Mean++ 算法则是:
第 1 个聚类中心也是随机;
接下来的聚类中心, 也就是第 2 个, 按照距离当前聚类中心越远越好;
按照上述思想, 选择了 k 个初始的聚类中心;
初始值选取完毕后, 后续的流程和 K-Mean 是一样的.
2)ISODATA 算法
当 K 值的大小不确定的时候, 可以使用 ISODATA 算法, 全称叫迭代自组织数据分析法. ISODATA 算法在 K-Mean 算法的基础上增加了两个操作:
分裂操作, 对应着增加聚类中心数
合并操作, 对应着减少聚类中心数
ISODATA 的应用也是比较复杂的, 需要填比较多的参数:
预期的聚类中心数据 K0: 在 ISODATA 运行过程中聚类中心数可以自动变化, 这里的 K0 只是一个参考值;
每个类所要求的的最少样本数 Nmin: 如果分裂后会导致某个子类别所包含的样本数量少于该阈值, 会拒绝本次分裂操作;
最大方差 Sigma: 用于控制某个类别中样本的分散程度, 当样本的分散程度超过某个阈值时, 且分裂后满足第一条要求, 则进行分裂操作;
两个聚类中心之间所允许的最小距离 Dmin: 如果两个簇靠得很近, 就会被进行合并操作.
高斯混合模型
高斯模型, 对应着高斯分布, 高斯分布也就是我们平时常说的正态分布, 高斯混合模型 (Gaussian Mixed Model,GMM) 也是一种聚类算法, 和 K-Mean 算法类似, 都是用了 EM 算法进行迭代计算. 高斯混合模型是假设每个簇的数据都符合正态分布, 当前数据呈现的分布则是每个正态分布的混合结果.
高斯混合模型的核心思想, 每个单独的分模型都是标准高斯分布模型, 其均值和方差都是待估计的参数, 还有一个参数π, 可以理解为权重(or 生成数据的概率), 其公式为:
它是一个生成式模型, 并且通过 EM 算法框架来求解, 具体的迭代过程如下:
首先, 初始随机选择各个参数的值(总共 3 个参数, 均值, 方差和权重), 然后迭代下面两步, 直到收敛:
1)E 步骤: 根据当前的参数, 计算每个点由某个分模型生成的概率.
2)M 步骤: 使用 E 步骤估计出来的概率, 来改进每个分模型的均值, 方差和权重.
高斯混合模型与 K-Mean 算法的相同点:
1)他们都是用于聚类的算法, 都需要指定 K 值;
2)都是使用 EM 算法来求解;
3)往往都是得到局部最优.
而它相比于 K-Mean 算法的优点, 就是它还可以用于概率密度的估计, 而且可以用于生成新的样本点.
生成式模型 (Generative Model): 对联合分布概率 p(x,y) 进行建模, 常见生成式
模型有: 隐马尔可夫模型 HMM, 朴素贝叶斯模型, 高斯混合模型 GMM,LDA
等.
判别式模型 (Discriminative Model): 直接对条件概率 p(y|x) 进行建模, 常见判
别模型有: 线性回归, 决策树, 支持向量机 SVM,k 近邻, 神经网络等.
自组织映射神经网络
自组织映射神经网络 (Self-Organizing Map,SOM) 是无监督学习方法中的一类重要方法, 可以用于聚类, 高维可视化, 数据压缩, 特征提取等等用途, 因为提出者是 Teuvo Kohonen 教授, 因此也被称为 Kohonen 网络.
讲 SOM 之前, 先科普一些生物学研究:
1)在人脑的感知通道上, 神经元组织是有序排列的;
2)大脑皮层会对外界特定的信息在特定的区域产生兴奋;
3)在生物神经系统中存在着一种侧抑制现象, 即一个神经细胞兴奋后, 会对周围其他神经细胞产生抑制作用, 这种抑制作用会使得神经细胞之间出现竞争, 其结果是某些获胜, 某些失败, 表现则为获胜细胞兴奋, 失败细胞抑制.
而我们的 SOM 就是对以上的生物神经系统功能的一种人工神经网络模型.
SOM 本质上是一个两层神经网络, 包含输入层和输出层. 输入层模拟感知外界输入信息, 输出层模拟做出响应的大脑皮层.
1)输出层中, 神经元的个数就是聚类的个数;
2)训练时采用 "竞争学习" 的方式, 每个输入的样本, 都会在输出层中找到与之最为匹配的节点, 这个节点被称之为 "激活节点"(winning neuron);
3)紧接着采用随机梯度下降法更新激活节点的参数, 同时适当地更新激活节点附近的节点(会根据距离远近选择更新的 "力度");
4)上面说到的 "竞争学习", 可以通过神经元之间的横向抑制连接 (负反馈路径) 来实现.
一般, SOM 模型的常见网络结构有两种, 分别是一维和二维的:
SOM 的自组织学习过程, 可以归纳为下面几个子过程:
1)初始化: 所有连接权重都用小的随机值进行初始化.
2)竞争: 神经元计算每一个输入模式各自的判别函数值, 并宣布具有最小判别函数值的特定神经元为胜利者, 每个神经元 j 的判别函数为:
3)合作: 获胜的神经元决定了兴奋神经元拓扑邻域的空间位置, 确定了激活节点后, 更新临近的节点.
4)适应: 适当调整相关兴奋神经元的连接权重, 使得获胜神经元对相似输入模式的后续应用的响应增强.
5)迭代第 2-4 步, 直到特征映射趋于稳定.
等到最后迭代结束之后, 每个样本所激活的神经元就是它对应的类别.
SOM 与 K-Mean 算法的区别:
1)K-Mean 算法需要事先确定好 K 值, 而 SOM 不需要;
2)K-Mean 算法为每个输入数据找到一个最相似的类, 只更新这个类的参数; 而 SOM 则会更新临近的节点, 所以, K-Mean 算法受噪声影响比较大, SOM 则可能准确性方面会差一些;
3)SOM 的可视化很好, 有优雅的拓扑关系图.
如何训练参数
1)设定输出层神经元的数量: 如果不清楚, 可以尽可能设定较多的节点数.
2)设计输出节点的排列: 对于不同的问题, 事先选择好模式.
3)初始化权值.
4)设计拓扑邻域: 拓扑邻域的设计原则是使得邻域不断缩小, 从而输出平面上相邻神经元对应的权向量既有区别又有相当的相似度, 从而保证获胜节点对某一类模式产生最大响应时, 其邻域节点也产生较大响应.
5)设计学习率: 学习率是一个递减函数, 可以结合拓扑邻域一起考虑. 在训练开始时, 可以选择较大的值, 这样子比较快下降, 后面慢慢减少.
聚类算法的评估指标
聚类算法不像有监督学习有一个 target, 更多的都是没有目标的, 所以评估指标也是不一样的, 下面介绍几种常用的评估指标:
1)轮廓系数(Silhouette Coefficient)
silhouette 是一个衡量一个结点与它属聚类相较于其它聚类的相似程度, 取值范围 - 1 到 1, 值越大表明这个结点更匹配其属聚类而不与相邻的聚类匹配. 如果大多数结点都有很高的 silhouette value, 那么聚类适当. 若许多点都有低或者负的值, 说明分类过多或者过少.
定义
轮廓系数结合了凝聚度和分离度, 其计算步骤如下:
对于第 i 个对象, 计算它到所属簇中所有其他对象的平均距离, 记为 ai(体现凝聚度)
对于第 i 个对象和不包含该对象的任意簇, 记为 bi(体现分离度)
第 i 个对象的轮廓系数为 si=(bi-ai)/max(ai,bi)
2)Calinski-Harabaz 指数
如果标签是未知的, sklearn.metrics.calinski_harabaz_score 则可以使用 Calinski-Harabaz 指数来评估模型, 其中较高的 Calinski-Harabaz 分数与具有更好定义的聚类的模型相关.
优点:
当集群密集且分离好时, 分数更高, 这与集群的标准概念有关.
得分快速计算
缺点:
凸群的 Calinski-Harabaz 指数通常高于簇的其他概念, 例如通过 DBSCAN 获得的基于密度的集群.
3)Adjusted Rand index(调整后兰德指数)
该指标是衡量两个赋值相似度的函数, 忽略排列组合
优点:
随机 (统一) 标签分配 对于任何值的 ARI 分数接近 0.0n_clusters,n_samples(对于原始的兰德指数或 V 度量, 情况不是这样).
有界范围[-1,1]: 负值是坏的(独立标注), 相似的聚类具有正的 ARI,1.0 是完美的匹配得分.
对集群结构没有作出任何假设: 可以用于比较聚类算法, 例如 k-means, 其假设各向同性斑点形状与可以找到具有 "折叠" 形状的聚类的频谱聚类算法的结果.
缺点:
与惯性相反, ARI 需要对地面真相类的知识, 而在实践中几乎不可用, 或者需要人工注释者的人工分配(如在受监督的学习环境中).
然而, ARI 也可以在纯无人监控的设置中用作可用于聚类模型选择 (TODO) 的共识索引的构建块.
4)Mutual Information based scores(基于相互信息的分数)
鉴于 labels_true 相同样本的基本真实类分配和我们的聚类算法分配的知识 labels_pred, 互信息是衡量两个分配的一致性的函数, 忽略排列. 这种措施的两个不同的标准化版本是可用的, 归一化互信息 (NMI) 和调整的相互信息(AMI). 文献中经常使用 NMI, 而最近提出了 AMI, 并针对机会进行归一化:
优点:
随机的 (均匀的) 标签指定具有 AMI 得分接近 0.0 为任何值 n_clusters 和 n_samples(其不是生互信息或 V - 措施例如的情况下).
有界范围[0,1]: 接近零的值表示两个主要独立的标签分配, 而接近 1 的值表示重要的一致性. 此外, 恰好为 0 的值表示纯独立的标签分配, 并且恰好为 1 的 AMI 表示两个标签分配是相等的(有或没有排列).
对集群结构没有作出任何假设: 可以用于比较聚类算法, 例如 k-means, 其假设各向同性斑点形状与可以找到具有 "折叠" 形状的聚类的频谱聚类算法的结果.
缺点:
与惯性相反, 基于 MI 的措施需要了解地面真相类, 而在实践中几乎不可用, 或需要人为注释者的人工分配(如在受监督的学习环境中). 然而, 基于 MI 的措施也可用于纯粹无监督的设置, 作为可用于聚类模型选择的共识索引的构建块.
常见聚类算法对比
下面一张图介绍几种 Scikit learn 的常用聚类算法的比较:
常见聚类算法的 Python 实现
上面说了这么多聚类算法, 还是在最后面, 把算法的 Python 实现代码给大家贴一下:
1)K-Means 聚类
2)分层聚类(Hierarchical clustering)
3)t-SNE 聚类
4)DBSCAN 聚类
5)MiniBatchKMeans
6)Affinity Propagation(近邻传播)
Reference
《百面机器学习》--chapter5
更多最新最干内容请访问我的微信公众号: SAMshare
来源: https://segmentfault.com/a/1190000020656161