决策树|ID3、C4.5

目录：

1.决策树

• 决策树模型结构
• 决策树递归思想

2.信息增益

• 学习信息增益
• 学习信息增益率

3.决策树算法

• ID3算法
• C4.5算法
• C4.5算法在连续值上的处理

4.数据处理

• 划分数据集代码
• 选择最好的特征

1.决策树定义

• 定义
  分类决策树模型是一种描述对实例进行分类的树形结构。一棵决策树包含一个根节点，若干个内部节点和若干个叶节点，叶节点对应于决策结果。
• 决策树的示意图
  
• 树的递归思想
  由根节点出发到内部结点的每一条路径构建一条规则，内部结点的特征对应着规则的条件，结点的类对应着规则的结论。
  递归结束条件：

1. 遍历完所有划分数据集的属性；
2. 每个分支下的所有实例都具有相同的分类

2.信息增益

• 信息增益
  "信息熵"是度量样本的不确定度，是度量样本集合纯度最常用的一种方法。
  熵的计算(2为底熵的单位是bit，e为底是纳特)：
  $H(Y) = -\sum_{i=1}^{n}p(y_{i})log_{2}p(y_{i})$H(Y)=−i=1∑n​p(yi​)log2​p(yi​)
  信息增益定义
  表示得知特征A的信息而使得类X的信息的不确定性减少的程度。
  (A：代表数据集里面的特征，X：数据集里面标签的类别)
  统计学里面的公式：
  $g(D,A)=H(D)-H(D|A)$g(D,A)=H(D)−H(D∣A)
  西瓜书里面的公式：
  $Gain(D,a)=Ent(D)-\sum_{v=1}^{V} \frac{D^{v}}{D}Ent(D^{v})$Gain(D,a)=Ent(D)−v=1∑V​DDv​Ent(Dv)
  计算的方法就是按照西瓜书里面的，信息增益就是互信息，
  计算一下使用的是统计学里面的数据
  
  类别是“是”的有9个，类别是“否”的有6个。年龄是“青年”的有5个，年龄是“中年”的有5个，年龄是“老年”的有5个。
  $End(D) =-(\frac{9}{15}log\frac{9}{15}+\frac{6}{15}log\frac{6}{15})=0.971$End(D)=−(159​log159​+156​log156​)=0.971
  $D^{1}年龄是青年，其中“是”有2个，“否”有3个；D^{2}年龄是中年，其中“是”有3个，“否”有2个；D^{3}年龄是老年，其中“是”有4个，“否”有1个$D1年龄是青年，其中“是”有2个，“否”有3个；D2年龄是中年，其中“是”有3个，“否”有2个；D3年龄是老年，其中“是”有4个，“否”有1个
  $\begin{aligned}Ent(D^{1})&=-(\frac{2}{5}log\frac{2}{5}+\frac{3}{5}log\frac{3}{5})=0.971\\ Ent(D^{2})&=-(\frac{3}{5}log\frac{3}{5}+\frac{2}{5}log\frac{2}{5})=0.971\\ Ent(D^{3})&=-(\frac{4}{5}log\frac{4}{5}+\frac{1}{5}log\frac{1}{5})=0.722 \end{aligned}$Ent(D1)Ent(D2)Ent(D3)​=−(52​log52​+53​log53​)=0.971=−(53​log53​+52​log52​)=0.971=−(54​log54​+51​log51​)=0.722​

$\begin{aligned}Gain(D,年龄)&=Ent(D)-\sum_{v=1}^{3}\frac{D}{D^{v}}Ent(D^{v})\\ &=0.971-(\frac{5}{15} \times 0.971+\frac{5}{15} \times 0.971+\frac{5}{15} x\times 0.722)\\ &=0.083 \end{aligned}$Gain(D,年龄)​=Ent(D)−v=1∑3​DvD​Ent(Dv)=0.971−(155​×0.971+155​×0.971+155​x×0.722)=0.083​

• 信息增益率
  信息增益对可取数目较多的属性有所偏好，如果将ID也作为一个特征，那么它的信息增益为0.971，因为每一个ID对应一个，即每一个对应的$Ent(D^{id})$Ent(Did)熵为0，为了减少这种偏好带来的影响，可以使用“信息增益率”来选择最优划分的属性。
  统计学：特征A对训练数据集D的信息增益比$g_{R}(D,A)定义其为信息增益g(D,A)与训练数据集D的经验熵H(D)之比$gR​(D,A)定义其为信息增益g(D,A)与训练数据集D的经验熵H(D)之比
  $g_{R}(D,A)=\frac{g(D,A)}{H(D)}$gR​(D,A)=H(D)g(D,A)​
  西瓜书:
  $Gain_ratio(D,a)= \frac{Gain(D,a)}{IV(a)}$Gainr​atio(D,a)=IV(a)Gain(D,a)​
  $IV(a)=-\sum_{v=1}^{V}\frac{D^{v}}{D}log\frac{D^{v}}{D}$IV(a)=−v=1∑V​DDv​logDDv​

3.决策树算法

• ID3算法
  ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征

1. ID3优点：
   理论清晰、方法简单、学习能力较强。
2. 缺点：
   1. ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。
   2. 只能处理分类属性的数据，不能处理连续的数据
   3. ID3算法采用信息增益作为评价标准。信息增益的缺点是倾向于取值较多的特征，在有些情况下这类特征可能不会提供太多有价值的信息

• C4.5算法
  C4.5算法与ID3算法相似，C4.5使用的是信息增益比来选取特征。

1. 优点：
   • 解决偏向取值较多的属性的问题
   • 可以处理连续型属性。
2. 缺点：
   • 对数据集进行多次的顺序扫描和排序，算法的效率低。

• C4.5算法处理连续值
  • 需要连续属性离散化，最简单的策略采用二分法对连续属性进行处理，这就是C4.5算法采用的。
  • 连续值处理方法：
    给定数据集D和连续特征a，假定a出现了n个不同的值，将这n个值从小到大进行排序，取相邻的两个点的均值，作为划分点，这样的可以取n-1个划分点，计算哪个划分点的信息增益大。

4.处理数据集

• 划分数据集代码

def split_data_set(data_set,axis,value):
    """
    ID3算法需要对每个特征计算信息增益，选取最大的，这里就是对特征进行切分，
    传入每一列的索引，和值进行切分，返回的值不包括当前的这一个特征列。
    
    :param axis: 特征对应的 列名索引  [0,1,2,3]
    :param value: 特征值[id,color,root]对应列名里面所取的值，例如对color特征
                  进行切分传入value=dark_green,value=light_white,不同特征返回不同的列表
                  计算香浓熵
    :return: 
    """
    # 例如传入(data_set,1,dark_green),返回包含特征等于dark_green的列表
    ret_data_set = []
    for featVec in data_set:    # feat   合适的

        if featVec[axis] ==value:
            reduced_featVec = featVec[:axis]  # 0:0 的切片是一个[]

            reduce_eatVec_list = list(reduced_featVec)

            reduce_eatVec_list.extend(featVec[axis+1:])

            ret_data_set.append(reduce_eatVec_list)
    return ret_data_set


  

• 选择最好的特征

def choose_best_feature_to_split(data_set):
    "选择最好的特征"
    num_features =len(data_set[0])-1  # 统计有几个特征
    base_Entropy = calculation_Shannon_Ent(data_set)
    best_info_gain = 0.0
    best_feature =-1

    # unique 独特的，唯一的
    for i in range(num_features):
        feat_list = [example[i] for example in data_set]
        unique_values = set(feat_list)  # 统计每个特征，有几个值
        new_Entropy = 0.0

        for value in unique_values:
            sub_data_set =split_data_set(data_set,i,value)  # 特征里面不同的值进行切分数据
            prob =len(sub_data_set)/float(len(data_set))
            # 计算每个不同值的熵，再乘以概率 H(D|A)
            new_Entropy += prob * calculation_Shannon_Ent(sub_data_set)#
        # 就是信息增益H(D)-H(D|A)
        info_gain = base_Entropy -new_Entropy
        if info_gain >best_info_gain:
            best_info_gain = info_gain
            best_feature =i
    return best_feature