机器学习决策树

决策树

构建决策树

步骤:

1. 准备若干的训练数据（假设 m 个样本）；
2. 标明每个样本预期的类别；
3. 人为选取一些特征（即决策条件）；
4. 为每个训练样本对应所有需要的特征生成相应值——数值化特征；
5. 将通过上面的1-4步获得的训练数据输入给训练算法，训练算法通过一定的原则，决定各个特征的重要性程度，然后按照决策重要性从高到底，生成决策树。

信息熵(Entropy)

熵表示的是信息的混乱程度，信息越混乱，熵值越大

几种常用算法

ID3 算法

以信息增益为度量，选择分裂后信息增益最大的特征进行分裂

假设一个随机变量 x 有 n 种取值，分别为 ${x_1,x_2,...,x_n}$，每一种取值取到的概率分别是 ${p_1,p_2,...,p_n}$，那么 x 的信息熵定义为：

$Entropy(x) = -\sum_{i=1}^{n}p_i \log(p_i)$

设 S 为全部样本的集合，全部的样本一共分为 n 个类，则：

$Entropy(S) = -\sum_{i=1}^{n}p_i \log(p_i) $

其中，$p_i$ 为属于第 $i$ 个类别的样本，在总样本中出现的概率。

信息增益的公式为（下式表达的是样本集合 S 基于特征 T 进行分裂后所获取的信息增益）：

$InformationGain(T)=Entropy(S)−\sum_{value(T)}\frac{|S_v|}{|S|}Entropy(S_v)$

其中：

$S$ 为全部样本集合，$|S| 为 S$ 的样本数；
$T$为样本的一个特征；
$value(T)$ 是特征 $T$ 所有取值的集合；
$v$ 是 $T$ 的一个特征值；
$S_v$ 是 $S$ 中特征 T 的值为 v 的样本的集合，$|S_v| 为 S_v$ 的样本数。

ID3 缺点: 一般会优先选择取值种类较多的特征作为分裂特征, 不能处理取值在连续区间的特征.

C4.5 算法

C4.5 是 ID3 算法的改进版

C4.5 选用信息增益率(Gain Ratio)——用比例而不是单纯的量——作为选择分支的标准。

信息增益率通过引入一个被称作 分裂信息(Split Information) 的项，来惩罚取值可能性较多的特征。

$SplitInformation(T) = -\sum_{value(T)}\frac{|S_v|}{|S|}\log{\frac{|S_v|}{|S|}} $

$GainRatio(T) = \frac{InformationGain(T)}{SplitInformation(T)}$

C4.5处理连续区间的特征步骤:

1. 把需要处理的样本（对应整棵树）或样本子集（对应子树）按照连续变量的大小从小到大进行排序。
2. 假设所有 m 个样本数据在特征上的实际取值一共有 k（k<=m）个，那么总共有 k−1 个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的特征值中两两前后连续元素的中点。根据这 k-1 个分割点把原来连续的一个特征，转化为 k-1 个 Bool 特征。
3. 用信息增益率选择这 k-1 个特征的最佳划分。

但是，C4.5 有个问题：当某个 $|S_v|$ 的大小跟 $|S|$ 的大小接近的时候：

$SplitInformation(T) → 0, GainRatio(T)→∞$

为了避免这种情况导致某个其实无关紧要的特征占据根节点，可以采用启发式的思路，对每个特征先计算信息增益量，在其信息增益量较高的情况下，才应用信息增益率作为分裂标准。

C4.5 的优良性能和对数据和运算力要求都相对较小的特点，使得它成为了机器学习最常用的算法之一。它在实际应用中的地位，比 ID3 还要高。

CART 算法(Classification and Regression Tree)

CART 是一棵严格二叉树。每次分裂只做二分。

CART 的特征选取依据不是增益量或者增益率，而是 Gini 系数（Gini Coefficient）。

每次选择 Gini 系数最小的特征作为最优切分点。

Gini 系数的计算方法是：

$Gini(p) = \sum_{i=1}^{n}p_i(1-p_i) = 1 - \sum_{i=1}^{n}p_i^2$

对于二分类问题，若样本属于第一类的概率是 $p$，则：

$Gini(p) = 2p(1-p)$

如果 p = 0.3， 则 Gini(p) = 0.42；

如果 p = 0.8， 则 Gini(p) = 0.32。

0.32 < 0.42，根据 CART 的原则，当 p=0.8 时，这个特征更容易被选中作为分裂特征。

对二分类问题中，两种可能性的概率越不平均，则越可能是更佳优越的切分点。

特征选取

提取七个特征，用来判断一个形象，是人是猫。

用 ID3 算法构造分类树

1. 先计算 Entropy(S)。因为总共只有两个类别：人和猫，因此 n=2。

$Entropy(S) = -\sum_{i=1}^{n}p_i \log(p_i) = -p_{Girl} \log(p_{Girl}) - p_{Cat}\log(p_{Cat}) = - 9/17 \cdot \log(9/17) - 8/17 \cdot \log(8/17)= 0.69$

2. 分别计算各个特征

$Entropy(S|T) = \sum_{value(T)}\frac{|S_v|}{|S|}Entropy(S_v)$

$value(T)$ 总共只有两个取值 Yes, No

以Has a bow为例来示意其计算过程:

$Entropy(S|Has A Bow)$

$= p_{Yes} (-p_{(Girl|Yes)} \log (p_{(Girl|Yes)}) – p_{(Cat|Yes)} \log(p_{(Cat|Yes)}))+ p_{No} (-p_{(Girl|No)} \log(p_{(Girl|No)})– p_{(Cat|No)} \log(p_{(Cat|No)}))$

$= 8/17 \cdot (-4/8 \cdot \log(4/8) – 4/8 \cdot log(4/8)) + 9/17 \cdot (- 5/9 \cdot \log(5/9) – 4/9 \cdot \log(4/9)) = 0.69$

$InformationGain(T)=Entropy(S)−\sum_{value(T)}\frac{|S_v|}{|S|}Entropy(S_v)$

Entropy(S|Has A Bow) = 0.69

依次计算其他几项，得出如下结果：

Entropy(S|Wear Clothes) = 0.31
Entropy(S|Less than 5 apples tall) = 0.60
Entropy(S|Has whiskers) = 0.36
Entropy(S|Has round face) = 0.61
Entropy(S|Has cat ears) = 0.18
Entropy(S|Walks on 2 feet) = 0.36

3. InfoGain(Has cat ears) 最大，因此Has cat ears是第一个分裂节点

而从这一特征对应的类别也可以看出，所有特征值为 No 的都一定是 Girl；特征值为 Yes，可能是 Girl 也可能是 Cat，那么第一次分裂，我们得出如下结果：

现在Has cat ears已经成为了分裂点，则下一步将其排除，用剩下的6个 Feature 继续分裂成树：

然后是Walks on 2 feet，把Walks on 2 feet为No的标记为Cat，然后摘除这列

当我们将Wear Clothes作为分裂点时，会发现该特征只剩下了一个选项Yes

如果某个特征被选为当前轮的分裂点，但是它在现存数据中只有一个值，另一个值对应的记录为空，则这个时候针对不存在的特征值，将它标记为该特征在所有训练数据中所占比例最大的类型

所以看在原始表里, Wear Clothes为 No 的记录中 Girl 和 Cat 的比例。

在原始表中这两种记录数量为 0：6，因此Wear Clothes为 No 的分支直接标记成 Cat

摘除Wear Clothes列，然后继续用这两行数据分析

-> Has whiskers -> Less than 5 apples tall

Less than 5 apples tall为Yes中Cat:Girl=4:1，把 Yes 分支标记成 Cat

最后使得7个特征都成为分裂点

伪代码实现:

DecisionTree induceTree(training_set, features) {
    If(training_set中所有的输入项都被标记为同一个label){
        return 一个标志位该label的叶子节点;
    } else if(features为空) {
        # 默认标记为在所有training_set中所占比例最大的label
        return 一个标记为默认label的叶子节点; 
    } else {
        选取一个feature，F;
        以F为根节点创建一棵树currentTree;
        从Features中删除F；
        foreach(value V of F) {
            将training_set中feature F的取值为V的元素全部提取出来，组成partition_v；
            branch_v= induceTree(partition_V, features);
            将branch_v添加为根节点的子树，根节点到branch_v的路径为F的V值；
        }
        return currentTree；
    }
}

后剪枝优化决策树

决策树剪枝

剪枝方法大致可以分为两类：

1. 先剪枝（局部剪枝）：在构造过程中，当某个节点满足剪枝条件，则直接停止此分支的构造。
2. 后剪枝（全局剪枝）：先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。

后剪枝优化树

后剪枝法:

最后两个分裂点Has round face和Has a bow存在并无意义

遍历所有节点，将没有区分作用的节点删除，得到:

代码实现

python

    from sklearn import tree
    from sklearn.model_selection im
    port train_test_split
    import numpy as np

    #9个女孩和8只猫的数据，对应7个feature，yes取值为1，no为0
    features = np.array([
        [1, 1, 0, 0, 1, 0, 1],
        [1, 1, 1, 0, 0, 0, 1],
        [0, 1, 0, 0, 0, 0, 1],
        [1, 1, 0, 0, 1, 0, 1],
        [0, 1, 0, 0, 1, 0, 0],
        [0, 1, 0, 0, 1, 0, 1],
        [1, 1, 0, 0, 1, 0, 1],
        [0, 1, 0, 0, 1, 0, 1],
        [0, 1, 0, 1, 1, 1, 1],
        [0, 0, 0, 1, 1, 1, 0],
        [0, 1, 0, 1, 1, 1, 1],
        [1, 0, 1, 1, 1, 1, 0],
        [0, 0, 0, 1, 1, 1, 0],
        [1, 0, 0, 1, 1, 1, 0],
        [0, 0, 1, 0, 1, 1, 0],
        [1, 1, 1, 1, 1, 1, 0],
        [1, 0, 1, 1, 1, 1, 0]
    ])

    #1 表示是女孩，0表示是猫  
    labels = np.array([
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [1],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
        [0],
    ])

    # 从数据集中取20%作为测试集，其他作为训练集
    X_train, X_test, y_train, y_test = train_test_split(
        features,
        labels,
        test_size=0.2,
        random_state=0,
    )

    # 训练分类树模型
    clf = tree.DecisionTreeClassifier()
    clf.fit(X=X_train, y=y_train)

    # 测试
    print(clf.predict(X_test))
    # 对比测试结果和预期结果
    print(clf.score(X=X_test, y=y_test))

    # 预测HelloKitty
    HelloKitty = np.array([[1,1,1,1,1,1,1]])
    print(clf.predict(HelloKitty))

    # Output
    # [1 1 0 0]
    # 0.75
    # [0]