<jupyter_start><jupyter_text>4 决策树算法 4.1 算法描述：采用基本的分而治之的思想，将一个大决定，分成若干小决定，根据每个小决定进行分类，然后得出最终决定。算法描述*输入*:    训练集 $D = \{(x_1,y_1),(x_2,y_2),\dots\,(x_m,y_m)\}$        属性集 $A = \{a_1,a_2, \dots, a_d\}$*过程*:```pythondef TreeGenerate(D,A):      生成节点node；    if D中样本全属于同一类别C:        将node标记为C类叶节点        return    if A == Ø or D中样本在A上取值相同:        将node标记为叶节点，其类别标记为D中样本数最多的类        return    从A中选择最优划分属性av    for a in av:        为node的生成一个分支，令Dv表示D在av上取值为a的样本子集        if Dv == Ø:            将分支节点标记为叶节点，其类别标记为D中样本最多的类            return        else:            以TreeGenerate(Dv, A\{a})为分支节点```*输出*:以node为一根节点的一颗决策树  4.2 划分选择由算法我们可以看出，决策树学习的关键是“选择最优划分属性”。一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的"纯度"越来越高。 4.2.1 信息增益   “信息熵”(information entropy)是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占比例为$p_k(k=1,2,\dots\,\vert\nu\vert)$则D的信息熵定义为   $$Ent(D) =-\sum_{k=1}^{\vert\nu\vert}p_klog_2p_k$$Ent(D)值越小,D的纯度越高。假定离散属性a有V个可能的取值$\{a^1,a^2,\dots\,a^{\nu}\}$，若使用a对样本集D进行划分，则会产生V个分支节点，其中第$v$个包含了D中所有在属性a上取值为$a^{\nu}$的样本，记为$D^{\nu}$,我们可以计算出$D^{\nu}$的信息熵，在考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重$\vert{D^{\nu}}\vert/\vert{D}\vert$,即样本数越多的分支节点的影响越大，于是可计算出用属性a对样本集D进行划分所得“信息增益”(information gain)$$Gain(D, a)= Ent(D) =  \sum_{v=1}^{V} \frac{\vert{D^{\nu}}\vert}{\vert{D}\vert}{Ent(D^{\nu})}$$一般而言信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。著名的ID3决策树学习法就是以信息增益为准则来选择划分属性。  示例西瓜数据集<jupyter_code>import pandas as pd
import numpy as np
from cytoolz import *
from itertools import product
from operator import *

melon = pd.DataFrame({'色泽':['青绿', '乌黑', '乌黑', '青绿', '浅白','青绿', '乌黑', '乌黑', '乌黑', '青绿', '浅白', '浅白', '青绿','浅白', '乌黑', '浅白','青绿'],
 '根蒂':['蜷缩', '蜷缩', '蜷缩', '蜷缩', '蜷缩','稍蜷', '稍蜷', '稍蜷', '稍蜷', '硬挺', '硬挺', '蜷缩', '稍蜷', '稍蜷', '稍蜷','蜷缩','蜷缩'],
 '敲声':['浊响', '沉闷', '浊响', '沉闷', '浊响','浊响', '浊响', '浊响', '沉闷', '清脆', '清脆', '浊响', '浊响', '沉闷', '浊响','浊响','沉闷'],
 '纹理':['清晰', '清晰', '清晰', '清晰', '清晰','清晰', '稍糊', '清晰', '稍糊', '清晰', '模糊', '模糊', '稍糊', '稍糊', '清晰','模糊','稍糊'],
 '脐部':['凹陷', '凹陷', '凹陷', '凹陷', '凹陷','稍凹', '稍凹', '稍凹', '稍凹', '平坦', '平坦', '平坦', '凹陷', '凹陷', '稍凹','平坦','稍凹'],
 '触感':['硬滑', '硬滑', '硬滑', '硬滑', '硬滑','软粘', '软粘', '硬滑', '硬滑', '软粘', '硬滑', '软粘', '硬滑', '硬滑', '软粘','硬滑','硬滑'],
 '好瓜':['是', '是', '是', '是', '是','是', '是', '是', '否', '否', '否', '否', '否', '否', '否','否','否']})

def EntropyBase(x):
    if x == 0:
        return 0;
    else:
        return x*np.log2(x)

def Entropy(p):
    return reduce(add, map(lambda x: -EntropyBase(x), p))

def Ent(df, y):
    p = list(map(lambda x: len(df[df[y]==x])/len(df), np.unique(df[y])))
    return Entropy(p)
    
def EntSub(df, col,y):
    sz = df.groupby([col, y])[y].count()
    def g(sz, c, t):
        try:
            return sz[c, t]
        except:
            return 0
    ens = np.array(list(map(lambda c: list(map(lambda t: g(sz,c,t),np.unique(df[y]))), np.unique(df[col]))))
    return list(map(lambda x : Entropy(x/x.sum()), ens))

def Dv(df, col, y):
    return df.groupby([df[col]])[y].count().values

def Gain(df, col, y):
    nm = Dv(melon, col, y)
    es = EntSub(melon, col, y)
    n = sum(nm)
    return Ent(df, y) - reduce(add, map(lambda x: x[0]*x[1]/n, zip(es, nm)))
    
def IV(df, col, y):
    n = len(df)
    return reduce(add, map(lambda x: - EntropyBase(x/n), Dv(df, col, y)))    
IV(melon, '触感', '好瓜')
gains = pd.DataFrame({'value':list(map(lambda x: Gain(melon, x,'好瓜'), melon.columns.values[1:])),
 'name':melon.columns.values[1:]})
gains
Gain(melon, '色泽', '好瓜')
EntSub(melon, '色泽', '好瓜')
Dv(melon, '色泽', '好瓜')
Ent(melon, '好瓜')<jupyter_output><empty_output><jupyter_text>4.2.2 增益率实际上信息增益对可取值数目较多的属性有所偏好，为减少这种偏好带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而使用增益率(gain radio)来选择最优划分属性，增益率定义如下$$Gain\_ratio(D, \alpha) = \frac{Gain(D,\alpha)}{IV(\alpha)}$$其中$$IV(\alpha)=-\sum^{V}_{v=1}\frac{\vert{D}^v\vert}{\vert{D}\vert}log_2\frac{\vert{D}^v\vert}{\vert{D}\vert}$$<jupyter_code>ivs = pd.DataFrame({'value':list(map(lambda x: IV(melon, x,'好瓜'), melon.columns.values[1:])),
 'name':melon.columns.values[1:],
 'count':list(map(lambda x: len(np.unique(melon[x])), melon.columns.values[1:]))})
ivs<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.2649763857817549, 'fraction_numerical': 0.009942828734775044, 'mean_word_length': 4.831884057971014, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '195566', 'license': 'MIT', 'n_tokens_mistral': 2523, 'n_tokens_neox': 2726, 'n_words': 306, 'path': 'Model-Data/Classify/decision.ipynb', 'repo_name': 'inessus/ai-skills', 'size': '4023'}