《机器学习》ch4-决策树

(Updated: )
,

基本流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// D 训练集, A 属性集
GenerateTree (D, A) {
    node = new Node();
    if (D剩下的样本输入的x完 全 一 致) {
        node.y = D中占多数的y;
        return node;
    }
    选择划分属性a // optional: 预剪枝
    for a的每个变量
        node.children.add(new Node());
        if (D中没有这个变量) {
            node.currentChildren.y = D中占多数的y;
            continue;
        } else {
            node.currentChildren.y = GenerateTree(D, A-a);
        }
}

划分选择

信息熵&信息增益

Ent(D)越小，D纯度越高 （按y划分）

Gain(D, a) 越大，使用属性a进行划分的纯度提升越大

eg: ID3算法

增益率

Gain_ratio(D, a)越大，使用属性a进行划分的纯度提升越大，并且泛化性能越好

偏好数目较少的属性，因此一般先用Gain再用Gain_radio

eg: C4.5

剪枝处理

防止过拟合，提升泛化性能

预剪枝

选择划分属性时：用测试集比较划分前后的准确率

优点：提高效率

缺点：本质贪心，可能欠拟合

后剪枝

生成了决策树之后，对每个节点判断比较

优点：准确率高

缺点：效率低

连续与缺失值

连续值

样本中的n个值，取n-1个中间值，转化成离散值，测试生成的树的效率，最后取其中一个值

缺失值

  1. 选择划分属性：按已知的信息划分
  2. 给每个样本增加权重变量w，缺失属性在划分时w按照已知属性的比例减小，并且划分到每个子节点

多变量决策树

多个属性之间有关联