人工智能基础（十九）决策树

决策树

决策树分类原理
1、信息增益
信息增益 = entroy (前) - entroy (后)
注意：信息增益越大，我们优先选择这个属性进行计算
信息增益优先选择属性总类别比较多的进行划分
2、信息增益率
维持了一个分离信息度量，通过这个分离信息度量当分母，进行限制
3、基尼增益
基尼值： 从数据集D中随机抽取两个样本，其类别标记不一致的概率
Gini(D)值越小，数据集D的纯度越高
基尼指数：选择使划分后基尼系数最小的属性作为最优划分属性
基尼增益：选择基尼增益最大的点，进行优化划分

基尼增益构造过程：

• 开始将所有记录看作一个节点
• 遍历每个变量的每一种分割方式，找到最好的分割点
• 分割成节点N1和N2
• 对N2和N2分别继续执行2-3步，直到每个节点足够“纯”为止

决策树的变量可以有两种，分别对应的划分方式：

• 1、数字型
  通过对数据取两个数字之间的中间值进行划分

• 2、名称型
  通过对属性的类别进行划分

如何评估分隔点的好坏？
主要看分割的纯不纯

三种算法的比较
ID3算法

• 采用信息增益作为评价标准
• 只能对描述属性为离散型属性的数据集构造决策树
• 缺点是倾向于选择值较多的属性

C4.5算法

• 用信息增益率来选择属性
• 可以处理连续数值型属性
• 采用了一种后剪枝算法
• 对于缺失值的处理
• 缺点：只适于能够驻留于内存的数据集

cart剪枝
1、剪枝原因
噪声、样本冲突，即错误的样本数据
特征即属性不能完全作为分类标准
巧合的规律性，数据量不够大
2、常用剪枝
预剪枝
在构建树的过程中，同时剪枝
eg: 限制节点最小样本数
指定数据高度
指定熵值的最小值

后剪枝
把一棵树，构建完成之后，再进行从上往下的剪枝