《机器学习》周志华读书笔记（三）线性模型（下）
本篇文章紧接《《机器学习》周志华读书笔记（三）线性模型（上）》，内容为3.4线性判别分析开始讲起
3.4线性判别分析
线性判别分析（Linear Discriminant Analysis ，LDA）：一种经典的线性学习法(经典的监督降维技术)，其思想非常朴素：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近，不同样例的投影点尽量远离。
上图所示为LDA二维示意图，“+”、“-” 分别代表正例和反例，椭圆代表数据簇的外轮廓，虚线代表投影，红色实心圆和实心三角形分别代表两类样本投影后的中心点。
给定数据集，
则第类示例的集合
，第
类示例的均值向量
，第
类示例的协方差矩阵
，
两类样本的中心在直线上的投影和
，两类样本的协方差
和
，
同类样例的投影点尽可能接近
+
尽可能小
异类样例的投影点尽可能远离
尽可能大
考虑上述因素，我们可以得到欲最大化的目标
定义类内散度矩阵（within-class scatter matrix）
定义类间散度矩阵（between-class scatter matrix）
求得LDA欲最大化的目标，即 和
的“广义瑞利商”（generalized Rayleigh quotient），则J可以重写为
如何确定 呢？
通过将 转化为在
时，求得
最小这一条件极值问题。
则我们可以通过拉格朗日乘子法进行求解，经过拉格朗日乘子法，上述极值问题等价于求 的解，
注意到 的方向恒为
，因为最大化目标的解与
的长度无关，只与其方向有关，
所以不妨设 ，带入
，可解得
当求解出 后对新的样本进行分类时，只需将该样本点投影到这条直线上，根据与各个类别的中心值进行比较，从而判定出新样本与哪个类别距离最近。
3.5多分类学习
多分类的问题常常使用差分策略，将多分类问题拆解为多个二分类任务求解，
经典拆分策略有三种：“一对一”（OvO）、“一对其余”（OvR） 和 “多对多”（MvM），核心思想与示意图如下所示：
给定数据集
一对一（OvO）：将这N个类别，一个对一个这样进行配对训练，显然会产生N（N-1）/2个二分类任务。这样的话带来的一个问题就是会造成存储开销较大，并且测试时间也较长。通过训练后产生N（N-1）/2个二分类器，在测试阶段，将新样本放入所有的二分类学习器中测试，得出N (N-1)个结果，最终通过投票产生最终的分类结果。
一对其余（OvR)：将一个类的样例作为正例，剩余其他类的样例都作为反例来训练。估有N个类别的话共能产生N个二分类器。需要注意的是在每个分类器训练的过程中，OvR需要使用到反例的所有样例，估该策略的训练时间开销较大。当新样本测试时，得出N个结果，若只有一个分类器预测为正类，则该预测作为最终结果。若有多个分类器预测为正类，则此时应考虑各个分类器的预测置信度，选择置信度最大的类别标记作为分类结果。
多对多”（MvM）：将若干个类视为正类，若干个类视为反类。文中介绍的是一种最常用的MvM技术：纠错输出码（ECOC）
纠错输出码（ECOC）：
（1）编码，对N个类别进行M次划分，每次划分将一部分类别作为正类，一部分类别作为反类，形成一个二分类训练集。这样一共可以产生M个训练集，可以训练出M个分类器。
（2）解码，M个分类器分别对测试样本进行预测，预测标记组成一个编码，将该预测标记编码与各个类别各自的编码进行比较，返回其中距离（欧氏距离，海明距离）最小的类别作为最终预测结果。
图中：“+1”、“-1”分别代表学习器 将该类样本作为正例、反例，三元码（-1，0，1）同理
图*4个类别，进行了M=5次划分，共有f1,f2,f3,f4,f5这5个分类器。每个类别经过这5个分类器都会输出一个编码，如图中的C1类的输出编码为（-1，+1，-1，+1，+1），同理每个测试新样本也会输出一个5位的编码，通过测试编码与各个类别编码之间的距离，例如欧式距离，海明距离，选取距离最小的一个类别作为最终输出类别即可完成分类任务。
一般来说ECOC在分类的时候因为有多位编码，存在一定的容错能力，如果训练类别与类别之间海明距离很大，那么即使测试样本在输出编码的时在某个或者某几个分类器输出的编码出错了，还是有可能能归到正确的类别中的。不失一般性，ECOC编码越长，纠错能力越强，同时分类器的训练，存储开销也都会增大，同时ECOC编码也不可能无限长，因为类别的组合是有限的，超过一定范围后的编码是没有意义的。
3.6类别不平衡问题
前面的问题都是有一个前提假设：不同类别的训练样本数目相当。如果差别很大，则存在很大问题。
例如：1000个样例中有998个反例，2个正例，那么学习方法只需要一直输出反例，则可达99.8%的精度。
类别不平衡问题不仅仅出现在原始数据中，而且也有可能出现在经过OvR，MvM策略后产生的二分类任务，因为这两个策略选取样本上面是存在类别不平衡问题的，不过这通常不需要专门处理，因为不同类别都经过OvR,MvM策略后会抵消掉该问题。
我们用 对新样本x进行分类，y表达了正例的可能性，几率y/（1-y）反映了正例可能性与反例可能性之间的比值