决策树-ID3

决策树的ID3算法

基本概念

• 决策树是包含一个根节点、多个内部节点和多个叶节点的树结构。根节点包含完整的样本集，叶节点对应决策结果，内部节点对应特征和属性或属性测试。从根节点到每个叶节点的路径对应于一个决策测试序列。决策树学习的目的是产生具有很强泛化能力的决策树，即处理未见过的例子的能力很强。机器的基本流程简单直观。对于分治策略来说，决策树的生成是一个递归过程。
• 构建决策树的核心问题是如何在每一步选择合适的特征来分割样本。主要算法有CART、ID3、C4.5； CART使用基尼指数作为选择特征的标准。 ID3使用信息增益作为特征选择的标准。 C4.5使用信息增益比作为特征选择的标准。决策树的剪枝是为了防止树的过拟合，增强其泛化能力，包括预剪枝和后剪枝。
• 决策树的优点和缺点

1. 决策树算法易于理解，能做可视化分析，容易提取出规则。其次，决策树可同时处理标称型和数值型数据。在
   次，决策树能很好的扩展到大型数据库中。

2. 决策树由于样本太少、特征太多，容易出现过拟合，忽略了数据集中属性的相关性。 ID3算法计算的信息增益偏向于数值较多的特征。

信息熵

数学期望：每次可能的结果的概率乘以其结果的的总和。
信息价值：在沙漠地区，告诉你明天不下雨，和明天下雨的信息价值是不同的，前者为高概率，显然概率越小的事件其价值越高。信息价值公式：$$我（X我）=-我哦G_{2}p（X我）$$

// 信息值与概率的关系
from math import log
import matplotlib.pyplot as plt
x= [i/100 for i in range(1,100)]
p=[-log(i,2) for i in x]
plt.xlabel("x")
plt.ylabel("l(x)")
plt.plot(x,p)
plt.show()

决策树原理（以是否打球决策树为例）：

为了简化程序，ID3 算法处理数值数据。先把文本转换成数值会方便很多。这里0、1、2分别代表三个特征，天气、场馆人数、加时赛； 4代表类别；表中的0、1代表该特性的状态“否”和“是”。

在构造决策树树时，需要将那些起决定性作用的特征作为首要决策点，须利用一定算法对特征进行评估也是上面的三个算法。 

信息熵：一条信息的信息量大小和和它的不确定性有直接关系，信息熵是信息价值的数学期望【即类别的信息价值平均值】。公式：$$H=-\underset{n=0}{\overset{n}{\Sigma }}p（X我）我哦G_{2}p（X我）$$

# 导入包
import numpy as np
import pandas as pd

#导入数据
data={
    0:[1,0,0,"打球"],
    1:[1,0,1,"打球"],
    2:[0,1,1,"打球"],
    3:[0,0,1,"不打球"],
    4:[1,1,1,"打球"]
}

# 计算熵的函数
def ent(data):
    print("原始数据：")
    df0=pd.DataFrame(data)
    print(df0)
    print("整理后的数据")
    df=df0.T
    print(df)
    print("数据长度：")
    data_length=len(data)
    print(data_length)
    print("取出结论熵【信息价值的期望值】")
    target=df.iloc[:,-1]  # pandas的行列操作函数loc和iloc
    print(target)
    print("分类计数")
    label_counts=target.value_counts()  # pandas的value_counts()计数函数
    print(label_counts)
    print("转字典类型")
    label_dict=label_counts.to_dict()    #pandas的转换字典的函数
    print(label_dict)
    entropy=0
    for key in label_dict:
        prob=float(label_dict[key])/data_length
        entropy-=prob*np.log2(prob)
    return entropy
print(ent(data))

最终输出0.7219280948873623就是类别信息熵。

信息增益：类别信息熵与某个属性状态下不同特征的信息熵【条件概率】的差值，公式：$$我nF哦（H）=H-\underset{我=1}{\overset{v}{\Sigma }}\frac{Hv}{H}\chi H（v）$$

公式的含义是：不同属性下，每个特征占数据总量的比例乘以该特征下的信息熵之和。 （有点难理解，接下来用数学表达式进一步解释）

#导入库
import pandas as pd
import numpy as np
#写入数据
data={
    0:[1,1,0,0,1],
    1:[0,0,1,0,1],
    2:[0,1,1,1,1],
    3:["打球","打球","打球","不打球","打球"]
}
#pandas处理数据
df=pd.DataFrame(data)
print(df)

#封装计算熵的函数
def ent(df):
    target=df.iloc[:,-1] #取表的最后一列仍为DataFrame类型
    data_length=len(df)
    label_counts=target.value_counts() #value_count()聚合函数，统计数量
    label_dict=label_counts.to_dict() #将统计后的结果转化为字典类型
    entropy=0 #初始化熵的值
    #熵的计算公式
    for key in label_dict:
        prob=float(label_dict[key])/data_length
        entropy-=prob*np.log2(prob)
    return entropy

#封装分割数据的函数
def split(df,feature_rank):
    groups=df.groupby(feature_rank)
    data_group={}
    for key in groups.groups.keys():
        data_group[key]=df.loc[groups.groups[key],:]
    return data_group

def _main_(data,feature_rank):
    init=ent(data)
    group_dict=split(data,feature_rank)
    new_ent=0
    for key in group_dict:
        prob=len(group_dict[key])/len(data)
        new_ent+=prob*ent(group_dict[key])
    return init-new_ent
print(_main_(data,0))
    

数据的数值算法思想均来源于Python机器学习的实际开发（王新宇主编，邮电出版社出版，谢谢！！！）

// 分别计算0，1，2特征的信息增益
print("特征0的信息增益为：",_main_(data,0))
print("特征1的信息增益为：",_main_(data,1))
print("特征2的信息增益为：",_main_(data,2))

计算出的信息增益可以看出，天气对是否比赛影响很大，加时赛影响最小。通过排序，可以按顺序列出特征对结果的影响分布，并选择特征构建决策树。

信息获取详情： （以下表中的数据为例）

该表是两周内是否有PlayTimes的数据，对于Outlook的属性来说，其一共有三种特征即Sunnny,Rain,Overcast
对于类别统计：

那么对于整个表来说其类别信息熵为：$$H（磷我Ay时间我米es）=-\frac{9}{14}我哦G_2\frac{9}{14}-\frac{5}{14}我哦G_2\frac{5}{14}=0。942107$$

属性Outlook的熵（三个熵值）：

Rain特征总数为5个，其中Yes占3/5，No占2/5； Sunny特征总数为5个，其中Yes占2/5，No占3/5； Overcast特征总数为4个，Yes占100%

$$氧verCAst的信兴趣熵：H（氧verCAst）=-\frac{4}{4}我哦G_2\frac{4}{4}-0=1。0$$
$$S你nny的信兴趣熵：H（S你nny）=-\frac{2}{5}我哦G_2\frac{2}{5}-\frac{3}{5}我哦G_2\frac{3}{5}=0。970$$
$$右A我n的信兴趣熵：H（右A我n）=-\frac{4}{5}我哦G_2\frac{4}{5}-\frac{1}{5}我哦G_2\frac{1}{5}=0。722$$
$$氧ver我哦哦k的信兴趣增加有利：G（右A我n）=H（磷我Ay时间我米es）-（\frac{4}{14}H（氧verCAst）+\frac{5}{14}H（S你nny）+\frac{5}{14}H（右A我n）=0。888$$
到此已经计算出Overlook的信息增益了。

构造决策树

计算信息增益就是为了在当前的状态下选择最合适特征作为节点，以递归构造决策树，而构造决策树的目的反过来又是对新的数据分类，确定未知的数据类别。具体就是需要一部分数据作为训练集指定规则（决策树），然后利用这些规则（决策树）对新的数据进行分类。

具体构造决策树的流程参照生成决策树@代码拖拉鸡，谢谢！！！

那么，如何用代码实现呢？决策树分类器方法已经集成了生成决策树的代码，我们只需要会运用即可。

上表数据构造决策树，判断[1,1,0]是否打球？

#以是否打球为例构建决策树

import pandas as pd
data={
    0:[1,0,0,"打球"],
    1:[1,0,1,"打球"],
    2:[0,1,1,"打球"],
    3:[0,0,1,"不打球"],
    4:[1,1,1,"打球"]
}
df0=pd.DataFrame(data)
df=df0.T
print(df)

from sklearn import tree  #导入模块
x=[[1,0,0],[1,0,1],[0,1,1],[0,0,1],[1,1,1]]   #训练集的数据，矩阵类型(0，1分别表示不同特征)
y=[1,1,1,0,1]    #训练集类别  列表类型（0，1表示不同类别）
tree_model = tree.DecisionTreeClassifier(criterion='entropy')  #构造决策树模型，entropy表示信息增益计算即ID3算法
clf = tree_model.fit(x, y)   #用构建的决策树模型拟合训练数据
clf.predict([[1,1,0]])   #预测[1,1,0]是否打球

结果：

输出了1，表示打球，即[1,1,0]状态下也打球。
构建的决策树如下：

// 输出决策树代码
# 可以用 Graphviz 格式（export_graphviz）输出。
# 如果使用的是 conda 包管理器，可以用如下方式安装：
# conda install python-graphviz  window+r +cmd中进行
# pip install graphviz


# 以下展示了用 Graphviz 输出上述从鸢尾花数据集得到的决策树，结果保存为 iris.pdf

# import graphviz
# iris = load_iris()
# dot_data = tree.export_graphviz(clf, out_file=None)
# graph = graphviz.Source(dot_data)
# graph.render("iris")
# export_graphviz 支持使用参数进行视觉优化，包括根据分类或者回归值绘制彩色的结点，也可以使用显式的变量或者类名。
# Jupyter Notebook 还可以自动内联呈现这些绘图。


import graphviz     
#iris = load_iris()
clf = tree.export_graphviz(tree_model, out_file=None)
graph = graphviz.Source(clf)
graph

未来会更新c4.5算法