线性/树型分类器的纯理论分析
纯理论分析
Preface
周志华老师的《机器学习》看到了第五章,可总感觉看得太快了(可惜起步太晚了,大三下才系统地学ML)。个人认为走马观花地看完全没有用处,最好是能自己将所有碰到的轮子都写一遍(理想情况),但人的精力毕竟有限,开学了时间也比较紧张,实现这一步就先跳过吧,而细致的理论分析与理解是完全必要的。LDA之前实现过Github Algorithm-Plus🔗,决策树倒是连理论都没怎么细看,只调过库。为了不当调库侠,有写轮子的能力,个人将对这两章进行一下梳理,写一下自己的理解。
LDA(消歧义:Linear Discriminant Analysis,不是Latent Dirichlet Allocation)和决策树都是两个非常简单但是又很优雅的分类器。
LDA的数学推导
同类样本的类内方差最小,而不同类样本的类间方差最大
LDA是给定标签下的有监督降维方式,希望找到更低维度上的投影,可以满足上述属性。而对于高维而言,协方差是描述样本关系的指标。协方差的定义如下(大二下学的,回忆一下):描述n维随机变量
二分类
假设有两类样本,
实际上,每个样本点
由于这是一下从n维降到1维,所以几何直观上并不好理解。个人觉得这样的降维跨度太大了。
为什么要投影到一条直线上?
由于二分类输出的指示结果为
- 三分类问题只需要求得在二维空间上的一个点,就能求出一个样本分属于三个类的概率。也即线性组合输出了一个二维的点
- 四分类问题只需求出三维空间中的一个点,就能求出一个样本分属于四个类的概率...
- M分类问题只需要求出M-1为空间中的一个点,就能求出一个样本分属于M个类的概率。
要注意特征空间(n维)和概率空间(M维)的不同。LDA实际上就是在正态分布以及同方差的假设下,认为只要线性组合n个特征,就能求出M维空间中的一个概率解。这也就解释了,为什么我一开始的理解是有问题的。问题的关键就在于:输出分类的概率是输入特征的线性组合。不能简单地想着投影,而要想为什么要这样投影,这样投影如何帮助求得分类概率。
那么数学上就比较好理解了:给定一条直线
多分类
从上述理解中已经可以知道LDA的“降维分类”方式,实际上是通过原特征的线性组合,将特征空间直接变换到“概率空间”(或者是可以被变换为概率的空间)。当分类数量为M时,只需要知道M-1个类上的概率或者等价概率值就可以求出所有类上的“概率输出”值。
也就是说:LDA的降维过程实际上是由n维特征空间变换为M-1维分类空间的过程。回顾二分类的情况,M
= 2,也就是将所有样本投影到一维(直线)上:
类内散度通常小于类间散度,在最优投影取得的情况下就更是这样了。所以每个样本,在类间散度很大的情况下,可以看作一个十分接近类内均值的点(如下图所示)。那么每个样本点都可以近似地被类内均值取代。
那么很自然,类间散度可以定义为(每个样本(近似)与全局均值的散度和)
树型 - 决策树
树越是向往高处的光亮,它的根就越要向下,向泥土,向黑暗的深处。—尼采
emmm。这句话只因为有个“树”字就被我拿出来镇一镇文章了。决策树,利用一个个不相互影响的特征(或者我们认为影响不太大的特征,实际上有影响也是可以通过某些操作进行转化的)进行层层分类。正如猜物游戏,每次只能问一个答案只有“是”和“否”的问题,通过答案产生的分支进行推测。通过对待分类样本的层层分解可以获得最终的分类推测。本节只讨论其相关的数学原理,对于具体的生成 / 剪枝算法将不会涉及(因为这没有吸引到我)。
信息论相关
回顾一下信息熵的两个定义:
在决策树一章中,《西瓜书》提到:
"信息熵" (information entropy) 是度量样本集合纯度最常用的一种指标。
为什么这么说呢?集合样本纯度又是指什么?纯度在此处指:同一个划分中,由于划分集合内的元素都存在相应的label,如果集合内的label越趋于一致,那么这个集合的纯度也就越高。如果用比例
显然,如果一种划分模式可以划分出纯度较高的子结点(样本子集合),那么:
- 全纯结点(只有一类)可以避免进一步分支,减小树结构复杂度
- 子集合越纯,说明分类效果越好(因为原集合是无序的,熵大,分类可以看作熵减过程)
由此我们定义信息增益:对于公式
互信息
信息论中,如果需要衡量两个随机变量之间的关系,可以计算
一个随机变量携带的信息包含另一个随机变量信息的量大小,这被定义为互信息(mutual
information)。可以这样认为:两个有关联的变量,给定其中一个变量的信息,另一个变量的不确定性随之减小:
互信息和信息增益是存在关系的[1]。在划分时,如果对属性集合A(也就是
增益率
实际上,纯使用信息增益并不太好。假设某个分支结点只有一个样本,那么显然分支纯度最大(杂度最小),那么假如有一个属性分支极多,可能一下就将所有的样本分到不同结点上了(比如《西瓜书》上提到的,样本序号),这样容易产生过拟合的分支属性是没有意义的,但是只用信息增益的话实际就会选择这个分支方法。所以使用一个因子来限定分支数的影响:
基尼指数
针对CART决策树的,而以上所说的决策树使用信息增益作为划分属性选择的度量。基尼指数(Gini impurity)指的是:
Gini impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset.[1]
翻译很简单:从集合中随机选择一个元素,再根据这个集合中的类别概率分布随机给这个元素进行分类,分类的错误概率就是基尼指数。
变量缺失处理的理解
在贝叶斯决策论中提到:
- 某一属性组合的变量可能根本不在样本中出现,但是不能直接认为这样的样本不存在。
而在决策树中,我们更多针对的问题是:当某一个样本某个属性值是未知的,如何处理这样的样本?丢弃是显然不可取的,这样可能损失太多的有效信息。而直接使用确实也不是办法,少掉一个属性要如何继续分支?《西瓜书》上将问题总结地很不错:
我们需解决两个问题: (1) 如何在属性值缺失的情况进行划分属性选择 ? (2) 给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分 ?
第一个问题我开始并没有什么很好的想法。而对于第二个问题,个人开始认为,假设已经知道了划分属性,可以根据其他完好样本来估计本样本在这个缺失属性上的分布,进行分布加权(事实上,这个想法类似《西瓜书》上提供的方法)。
问题一实际上比较容易,我想得太复杂了。由于划分属性只考虑一个属性与分类结果的关系,那么完全用不着考虑多属性关系,只需要取出这个属性下对应没有缺失的样本,利用这些样本估计【属性】对【分类结果】的影响即可。以信息增益法为例,考虑
问题2实际上是将“让同一个样本以不同的概率划入到不同的子结点中去”(《西瓜书》言)。也可以使用没有缺失属性a的样本信息,假设某一分支分到属性a的v取值
Kernelization
普通决策树的分类边界都是垂直于某个轴的(因为决策树是一种“非黑即白”的分类方法)。在某个属性(某个维度)上,只有固定的几种分法:
Figure 3. 决策树在单一维度上的分类边界总是垂直于轴的
啊这?太过于“一维”了,甚至连简单的线性可分分类都需要经过如下的艰难操作:
Figure 4. 决策树扭来扭去
一个简单的想法就是:不适用原属性进行分类,我们可以像PCA那样,使用属性的线性组合形成抽象属性,在这个抽象属性对应的新空间中,虽然分类边界仍然垂直于新的空间轴,但在原空间看起来,就成为一般线性分类器了。而进一步地,如果使用其他的非线性特征组合方法,也就是引入某些 kernel,甚至可以通过决策树达到任意分类边界生成的效果。
Reference
[1] Wikipedia, Decision tree learning