第五篇 统计学习方法是如何实现分类与聚类的（十九）
清华大学计算机系 马少平
第十九节
总结
本篇主要结合一些典型的分类、聚类算法介绍统计机器学习方法。
1、统计机器学习是依据统计学原理而提出的机器学习方法，其特点是，从以特征表示的数据出发，抽象出问题的模型，发现数据中隐含的规律和知识，再用获得的模型对新的数据做出分析和预测。
一般来说，统计机器学习方法，都事先假定了所要学习的模型的“样子”，不同的“样子”就决定了不同的学习方法，最终通过数据训练得到模型所需要的参数。比如支持向量机就假定了模型的“样子”是个超平面，学习的目的就是依据训练数据找到一个最优的分界超平面。
2、贝叶斯方法按照特征的概率分布，依据所属类别的概率大小，将待识别样本分类到概率最大的类别。由于存在特征组合爆炸的问题，假设特征间具有独立性，这样特征的联合分布就可以用每个特征分布的乘积代替，简化了问题的求解。这种引入独立性假设的贝叶斯方法称作朴素贝叶斯方法。
3、决策树是一种用于分类的特殊树结构，叶节点代表类别、非叶节点表示特征。依据特征的取值逐步细化，实现分类。构建决策树的关键问题就是如何依据训练数据选择特征问题，不同的选择原则就有了不同的决策树构建方法，也即决策树的训练方法。
按照信息增益选择特征的方法称作ID3方法。一个特征的信息增益定义为数据集的熵与该特征条件熵的差值，信息增益越大说明该特征分类能力越强，ID3方法选择信息增益最大的特征优先使用。
针对ID3算法存在的倾向于选择分值多的特征的问题，提出了C4.5方法。C4.5方法与ID3方法的主要区别是采用信息增益率选择特征。信息增益率定义为特征的信息增益与其分离信息之比。特征的分离信息是按照特征取值计算的熵，其最大值反应了特征取值的多少。同时C4.5还引入了连续特征，允许特征取连续值。
4、按照“近朱者赤近墨者黑”的原则，根据距离最近的样本类别对未知样本分类的方法称作最近邻方法。如果根据最近的k个样本中含有最多样本的类别作为未知样本的类别，这种分类方法称作k近邻方法。k近邻方法最主要的问题就是如何选择k值，恰当的k值可以达到比较理想的分类效果。可以通过实验测试的方法获取一个比较合理的k值，在多个不同的k值中，选取错误率最小的k值。
5、支持向量机是以两个类别间隔最大化为原则的二分类方法，按照训练样本的分布情况，分为线性可分支持向量机、线性支持向量机和非线性支持向量机三种情况。
线性可分支持向量机要求最优分界面到两类样本的函数间隔大于等于1，到最优分界面函数间隔等于1的样本就是支持向量。通过求解对偶问题最优解 αi* 的方法可以得到原问题的最优分界面，其中 αi*>=0 ，不等于0的 αi* 所对应的样本就是支持向量，其他样本为非支持向量。
线性支持向量机允许部分样本到最优分界面的函数间隔小于1，但要求大于 1-ξi ，其中ξi>=0 。在满足间隔最大化的同时，线性支持向量机要求所有的ξi 之和尽可能地小。同样通过求解对偶问题最优解 αi* 的方法得到原问题的最优分界面，与线性可分支持向量机不同的是要求满足条件0<= αi* <=C 。
非线性支持向量机是通过一个变换函数将原问题变换到一个新空间中求解，要求在新空间中样本的分布可以用线性支持向量机求解。一般采用核函数的方法，在不需知道变换函数的情况下，在原空间通过核函数求得新空间的最优分界面，同样用核函数得到原空间的最优分界超曲面。
通过多个二分类支持向量机的组合可以得到多分类支持向量机。组合方法包括一对一法、一对多法、层次法等。
6、K均值算法是一种聚类算法，在给定类别数的情况下，通过迭代的方式逐步实现聚类。一般来说，K均值方法对初始值比较敏感，不同的初始值可能会得到不同的聚类结果。二分K均值方法每次选定一个类别将其划分为两类，通过逐步划分的方法得到聚类结果，其特点是对初始值敏感性不强。
K值的选取对于K均值算法至关重要，通常是做出J值随K值的变化曲线，从比较小的K值开始，逐步增加K值，当K值增加J值变化不大时，就认为得到了一个比较好的K值。
7、层次聚类采用自底向上的方法实现聚类，开始时每个训练样本为一个类别，然后逐步合并两个最相似的类别，直到总类别数为指定的类别为止，或者只剩下了两个类别。其特点是可以得到不同粒度下的聚类结果。
8、DBSCAN算法是一种典型的基于密度的聚类方法。该方法指定一个半径r和最少包含的样本数minPts，以任意一个样本为圆心，以r为半径画圆。如果圆内包含的样本数大于等于minPts，则称该样本为核心样本。从一个核心样本开始，将其包含的所有样本归为一类，如果类中含有其他核心样本，则将这些核心样本包含的样本也加入进来，迭代该过程，直到类中所有核心样本都处理完毕，就得到了一个聚类结果。重复该过程，直到完成所有类别的聚类。
9、一个数据集可以划分为训练集、验证集和测试集。训练集用于训练分类器，验证集用于得到合适的超参数，测试集用于测试分类器的性能。这三个数据集是各自独立的，不包含重复样本。这比较适用于数据量比较大的场合。为了充分利用数据集，可以采用k折交叉验证的方法。其基本方法是，将数据分为k等份，然后1份作为验证集、k-1份作为训练集。循环使用这些数据，用k个验证集的平均指标作为验证集上的结果，用于选择合适的超参数。进一步也可以扩展为用其中的1份做验证集、另取1份做测试集，剩余的k-2份做训练集，同样采用循环使用数据的方法，用平均值作为验证集和测试集上的测试结果，选择超参数的同时，也测试得到了分类器的性能。
分类器常用的评价指标有准确率、召回率和F1值。准确率反应的是分类器得到的结果的可信性，召回率反应的是一个样本被分类到正确类别的可信性。F1值是准确率、召回率的调和平均值，是二者的综合评价。
10、统计机器学习方法处理的是特征数据，好的特征是模型性能的基本保证，如何抽取特征在统计机器学习方法中起着非常重要的作用。好的特征，一方面对面临的任务具有很好的区分性，一方面计算机可以自动抽取。本篇的最后部分以文本分类任务和脱机手写体汉字识别任务为例，分别介绍了两种不同的特征抽取方法。
未完待续