决策树

Source: https://blog.csdn.net/u010089444/article/details/53241218

ID3算法

首先计算出原始数据集的信息熵,然后依次将数据中的每一个特征作为分支标准,并计算其相对于原始数据的信息增益,选择最大信息增益的分支标准来划分数据,因为信息增益越大,区分样本的能力就越强,越具有代表性。重复上述过程从而生成一棵决策树,很显然这是一种自顶向下的贪心策略。

信息熵:
$$
Ent(D)=- \sum_{k=1}^{K} p_k\cdot log_{2}p_k
$$

信息增益:(前后信息熵的差)
$$
Gain(D, a)=Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|}Ent(D^v)
$$

C4.5算法

C4.5算法是对ID3算法的改进,C4.5克服了ID3的2个缺点:

  1. 用信息增益选择属性时偏向于选择分枝比较多的属性值,即取值多的属性
  2. 不能处理连续属性

对于离散特征,C4.5算法不直接使用信息增益,而是使用“增益率”(gain ratio)= 信息增益/固有值(intrinstic value)。增益率准则对可取值数目较少的属性有所偏好,因此C4.5算法并不是直接选择增益率最大的属性作为分支标准,而是先从候选属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。

C4.5算法处理连续属性的方法是先把连续属性转换为离散属性再进行处理。如果有N条样本,那么我们有N-1种离散化的方法:<=vj的分到左子树,>vj的分到右子树。计算这N-1种情况下最大的信息增益率。在离散属性上只需要计算1次信息增益率,而在连续属性上却需要计算N-1次,计算量是相当大的。通过以下办法可以减少计算量:对于连续属性先按大小进行排序,只有在分类发生改变的地方才需要切开。
如果利用增益率来选择连续值属性的分界点,会导致一些副作用。分界点将样本分成两个部分,这两个部分的样本个数之比也会影响增益率。根据增益率公式,我们可以发现,当分界点能够把样本分成数量相等的两个子集时(我们称此时的分界点为等分分界点),增益率的抑制会被最大化,因此等分分界点被过分抑制了。子集样本个数能够影响分界点,显然不合理。因此在决定分界点时还是采用增益这个指标,而选择属性的时候才使用增益率这个指标。

CART算法

CART(Classification And Regression Tree)算法既可以用于创建分类树,也可以用于创建回归树。

  • 二分
  • 单变量分割
  • 剪枝策略

基于 GINI 指数(反映了从数据集中随机抽出两个样本,其类别不一致的概率)

特征双化:如果特征的值是离散的,并且是具有两个以上的取值,则CART算法会考虑将目标类别合并成两个超类别

如果特征的取值范围是连续的,则CART算法需要把连续属性转换为离散属性再进行处理。

决策树常用的剪枝常用的简直方法有两种:预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。

预剪枝是根据一些原则及早的停止树增长,如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数、不纯度指标下降的最大幅度小于用户指定的幅度等;后剪枝则是通过在完全生长的树上剪去分枝实现的,通过删除节点的分支来剪去树节点,可以使用的后剪枝方法有多种,比如:代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。

0%