数模-决策树和随机森林
决策树原理
决策树算法原理
决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先以数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
决策树算法构造决策树来发现数据中蕴含的分类规则。如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。
- 决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定程度的，用于分析处理的数据集。
- 决策树的剪枝：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修正的过程，主要是用新的样本数据集(称为测试数据集)中的数据校验决策树生成过程中产生的初步规则，将那些影响预测准确性的分枝剪除。
决策树ID3算法的原理：
机器学习算法其实很古老，作为一个程序猿，可能会经常敲if,else if,else，其实就已经在用到决策树的思想了。只是有那么多条件，用哪个条件特征先做if，哪个条件特征后做if比较优呢？怎么准确的定量选择这个标准就是决策树机器学习算法的关键。
1970年代，一个昆兰的大牛找到了用信息论中的熵来度量决策树的决策选择过程，方法一出，它的简介和高效就引起了轰动，昆兰把这个算法叫做ID3。
ID3算法如何选择特征？
首先，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大.具体的,随机变量X的熵的表达式如下: \[ H(X)=-\sum_{i=1}^np_ilogp_i \] 其中n代表X的n种不同的离散取值.而\(p_i\)代表了X取值为i的概率,log为以2或e为底的对数.举个例子,比如X有2个可能的取值,而这两个取值各为1/2时X的熵最大,此时X具有最大的不确定性.值为\(H(X)=-(\frac{1}{2}log\frac{1}{2}+\frac{1}{2}log\frac{1}{2})=log2\).如果一个值概率大于1/2,另一个值概率小于1/2,则不确定性减少,对应的熵也会减少.比如一个概率1/3,一个概率2/3,则对应熵为\(H(X)=-(\frac{1}{3}log\frac{1}{3}+\frac{2}{3}log\frac{2}{3})=log3-\frac{2}{3}log2<log2\).
熟悉了一个变量的熵,很容易推广到多个变量的联合熵,这里给出两个变量X和Y的联合熵表达式:\(H(X,Y)=-\sum_{i=1}^np(x_i,y_i)logp(x_i,y_i)\)
有了联合熵,又可以得到条件熵的表达式H(X|Y),条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性.表达式如下: \[ H(X|Y)=-\sum_{i=1}^np(x_i,y_i)logp(x_i|y_i)=\sum_{j=1}^np(y_j)H(X|y_j) \] 前面提到H(X)度量了X的不确定性,条件熵H(X|Y)度量了在知道Y以后X剩下的不确定性,那么H(X)-H(X|Y)呢?从上面的描述可以看出,它度量了X在知道Y以后不确定性减少程度,这个度量在信息论中称为互信息,记为I(X,Y).在决策树ID3算法中叫做信息增益.ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树.信息增益大,则越适合用来分类.
使用上图就很容易明白他们的关系.左边的椭圆代表H(X),右边的椭圆代表H(Y),中间重合的部分就是我们的互信息或信息增益I(X,Y),左边的椭圆去掉重合部分就是H(X|Y),右边的椭圆去掉重合部分就是H(Y|X).两个椭圆的并就是H(X,Y)
决策树算法的主要内容
一棵决策树生成过程的主要分为以下3个部分:
- 特征选择:特征选择是指从训练数据中众多的特征中选择一个特征作为当前 节点的分裂标准,如何选择特征有着很多不同量化评估标准,从而衍生出不同的决策树算法.
- 决策树生成:根据选择的特征评估标准,从上至下递归地生成子节点,直到数据集不可分则停止决策树生长.树结构来说,递归结构是最容易理解的方式.
- 剪枝:决策树容易过拟合,一般来说需要剪枝,缩小树结构规模，缓解过拟合.剪枝技术有预剪枝和后剪枝两种.
主要思想
- 树以代表训练样本的单个结点开始
- 如果样本都在同一个类,则该结点成为树叶,并用该类标记
- 否则,算法选择最有分类能力的属性作为决策树的当前结点
- 根据当前决策结点属性聚会的不同,将训练样本数据集分为若干子集,每个取值形成一个分枝,有几个取值形成几个分枝.均针对上一步得到的一个子集,重复进行先前的步骤,形成每个划分样本上的决策树.一旦一个属性出现在一个结点上,就不必在该结点的任何后代远程考虑它.
- 递归划分步骤仅当下列条件之一成立时停止
- 给定结点的所有样本属于同一类
- 没有剩余属性可以用来进一步划分样本.在这种情况下,使用多数表决将给定的结点转换成树叶,并以样本中元组个数最多的类别作为类别标记,同时也可以存放该结点样本的类别分布.
- 如果某一分支,没有满足该分支中已有分类的样本,则以样本的多数类创建一个树叶
决策树ＩＤ３算法的主要内容
输入的是ｍ个样本，样本输出集全为Ｄ，每个样本有n个离散特征,特征集合即为A,输出决策树T.
算法过程为:
- 初始化信息增益的阈值\(\epsilon\)
- 判断样本是否为同一类输出\(D_i\),如果是则返回节点树T.标记类别为\(D_i\)
- 判断特征是否为空,如果是则返回单节点树T,标记类别为样本中输出类别D实例数最多的类别
- 计算A中各个特征(一共n个)对输出D的信息增益,选择信息增益最大的特征\(A_g\)
- 如果\(A_g\)的信息增益小于阈值\(\epsilon\),则返回单节点树T,标记类别为样本中输出类别D实例数最多的类别
- 否则,按特征\(A_g\)的不同取值\(A_{gi}\)将对应的样本输出D分成不同的类别\(D_i\).每个类别产生一个子节点.对应特征值为\(A_{gi}\).返回增加节点的数T.
- 对于所有的子节点,令\(D=D_i\),\(A=A-\{A_g\}\)递归调用2-6步,得到子树\(T_i\)并返回
随机森林的原理
随机森林指的是利用多棵树对样本进行训练并预测的一种分类器.
决策树相当于一个大师,通过自己在数据集中学到的知识对于新的数据进行分类.但是俗话说得好,三个臭皮匠,顶个诸葛亮.随机森林就是希望构建多个臭皮匠,希望最终的分类效果能够超过单个大师的一种算法.
那随机森林具体如何构建呢?有两个方面:数据的随机性选取,以及待选特征的随机选取.
数据的随机选取
首先,从原始的数据集中采取有放回的抽样,构造子数据集,子数据集的数据量是和原始数据集相同的.不同子数据集的元素可以重复,同一子数据集中的元素也可以重复.
第二,利用子数据集来构建子决策树,将这个数据放到每个子决策树中,每个子决策树输出一个结果.最后,如果有了新数据需要通过随机森林得到分类结果,就可以通过对子决策树的判断结果投票,得到随机森林的输出结果.
待选特征的随机选取
与数据集的随机选取类似,随机森林中的子树的每一个分裂过程并未用到所有的待选特征,而是从所有待选特征中随机选取一定的特征,之后再随机选取的特征中选取最优的特征.这样能够使得随机森林中的决策树都能彼此不同,提升系统的多样性,从而提升分类性能.
随机森林的主要内容
- 从原始训练集中使用Bootstraping方法随机有放回的采样选出m个样本,共进行n_tree次采样,生成n_tree个训练集
- 对于n_tree个训练集,我们分别训练n_tree个决策树模型
- 对于单个决策树模型,假设训练样本特征的个数为n,那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂
- 每棵树都一直这样分裂下去,直到该节点的所有训练样例都属于同一类.在决策树的分裂过程中不需要剪枝
- 将生成的多棵决策树组成随机森林.对于分类问题,按多棵分类器投票决定最终分类结果;对于回归问题,由多棵树预测值的均值决定最终预测结果
决策树和随机森林的MATLAB调用
已知训练数据和训练数据类,获得决策树模型:
t=treefit(train_X,y);%train_X的行数为样本数,列数为特征数;y的行数为样本数,1列表征类
t=classregtree(train_Y,y);%用法与上一致,只是treefit为ID3算法,classregtree为CART算法;现在多使用classregtree(现treefit在matlab中会报错)
计算获得的决策树的精确度:
cost=treetest(t,'test',X,y);%测试错误率;
[cost,secost,ntnodes,besetleavel]=treetest(...);% cost为误差率向量;ntnodes为决策树包含的节点向量; 两者对应
已知决策树计算测试数据类:
yfit=treeval(t,X)
[yfit,node,cname]=treeval(...)%cname获得测试数据类
裁剪决策树
t2 = treeprune(t1,'level',level)%裁剪t1树的最后level级
t2 = treeprune(t1,'nodes',nodes)
相关函数
| 函数名 | 作用 |
|---|---|
| catsplit | |
| children | 查看子节点个数 |
| classcount | 查看节点各类实例数 |
| classprob | 查看节点各类概率 |
| classregtree | 构建决策树 |
| cutcatrgories | 剪枝范畴 |
| cutpoint | 分枝点的阀值 |
| cuttype | 分枝的类型 |
| cutvar | 分枝点的属性名 |
| eval | 进行预测 |
| isbranch | 是否是分枝节点 |
| nodeerr | |
| nodeprob | 节点的概率 |
| nodesize | 节点的尺寸,即各类实例之和 |
| numnodes | 节点数量 |
| parent | 父节点 |
| prune | 剪枝 |
| risk | 节点风险 |
| test | 错误率 |
| type | 树类别 |
| varimportance | 估算输入特征的重要性 |
| view | 画出决策树 |
决策树和随机森林的优缺点和改进方法
决策树的优缺点
决策树算法的优点:
- 分类精度高
- 生成的模式简单
- 对噪声数据有很好的健壮性
决策树算法(ID3)的缺点:
- ID3没有考虑连续特征,比如长度,密度都是连续值 ,无法在ID3运用.这大大限制了ID3的用途
- ID3采用信息增益大的特征优先建立决策树的节点.很快就被人发现,在相同条件下,取值比较多的特征比取值少的特征信息增益大
- ID3算法对于缺失值的情况没有做考虑
- 没有考虑过拟合的问题
随机森林的优缺点
随机森林的优点:
- 具有极高的准确率
- 随机性的引入,使得随机森林不容易过拟合
- 随机性的引入,使得随机森林有很好的抗噪声能力
- 能处理很高维度的数据,并且不用做特征选择
- 既能处理离散型数据,也能处理连续型数据,数据集无需规范化,训练速度快,可以得到变量重要性排序
- 容易实现并行化
随机森林的缺点:
- 当随机森林中的决策树个数很多时,训练时需要的空间和时间会较大
- 随机森林模型还有许多不好解释的地方,有点算个黑盒模型
决策树算法的改进方法
１． Ｃ4.5算法
C4.5算法是ID3的一个改进算法,继承了ID3算法的优点
C4.5算法用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝; 能够完成对连续属性的离散化处理; 能够对不完整数据进行处理.C4.5算法产生的分类规则易于理解,准确率较高; 但效率低,因树构造过程中,需要对数据集进行多次的顺序扫描和排序.也是因为必须多次数据集扫描,C4.5只适合于能够驻留于内存的数据集
- CART算法
CART算法的全称是Classification And Regression Tree,采用的是Gini指数(选Gini指数最小的特征s)作为分裂标准,同时它也是包含后剪枝操作.ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息,但其生成的决策树分支较大,规模较大.为了简化决策树的规模,提高生成决策树的效率,就出现了根据GINI系数来选择测试属性的决策树算法CART.