决策树之ID3算法_决策树算法csdn id3

一、几个概念

1.熵

熵在这里通俗的来说是平均信息量，是对被传送信息度量采用的平均值。与化学和物理中的概念类似，熵反应的是系统的混乱程度，熵越大，系统的混乱程度越高，信息越不纯。对于一个有序系统，它的熵为0.

2.消息量

一个消息的信息传递量为，其中p为一个消息的概率。因为概率是一个小于1的数，而信息传递量又是一个大于等于0的数，所以，消息传递量前面有一个负号，此时消息传递量为正。对于n个消息，概率分布为，其概率分布传递的信息量为，此时的信息量也成为该概率分布的信息熵。

3.信息增量

设D为记录集合，该记录集合为样本的数据，其中包括类别的分类标签和其他属性数据。信息增量为确定D中所有分类属性的信息量与已知的非分类属性X的值确定D中一个元素所属分类需要的信息量的差值。公式如下：

二、ID3算法步骤

 （1）计算所给定的训练集的信息熵

设训练集为S，训练集根据类别标签可以划分为S1、S2、S3...Sn个类别。设训练样本的总数为d，每个类别中含有的样本数设为d1、d2、d3...dn。则每个类别的概率为pi=di/d。则训练集的信息熵:

（2） 计算训练集中某个属性的划分信息熵

计算属性A中不同取值aj的信息熵，设dj是A=aj的样本数，dij为当A=aj时对应类标号属性的不同取值的个数，此时的概率pj=dij/dj。则属性A的划分信息熵为：

 （3）计算属性A的信息增益

选择信息增益最大的为划分属性！！！ 

三、举个栗子体验一下这个算法

 由于解题步骤有点多，我就不打字了，直接上过程！

根据这个决策树，回到那个问题 [‘Rain’,’Hot’,’Normal’,’Strong’]的情况下不打球。

四、使用python的sklearn实现ID3算法

因为sklearn不支持字符串进行ID3算法，所以所有的数据都需要重新编码，所以我下面写了一个函数进行转换，将字符串与数字对应。该代码可以绘制决策树的图，需要借助graphviz库，有关这个库的安装，就不详细说明了，可以自行去搜索一下安装这个库。话不多说放代码！！

import numpy as np
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
import graphviz
 
# 导入数据函数
def load_data():
    dataSet = [['Sunny', 'Hot', 'High', 'Weak', 'No'],
               ['Sunny', 'Hot', 'High', 'Strong', 'No'],
               ['Overcast', 'Hot', 'High', 'Weak', 'Yes'],
               ['Rain', 'Mild', 'High', 'Weak', 'Yes'],
               ['Rain', 'Cool', 'Normal', 'Weak', 'Yes'],
               ['Rain', 'Cool', 'Normal', 'Strong', 'No'],
               ['Overcast', 'Cool', 'Normal', 'Strong', 'Yes'],
               ['Sunny', 'Mild', 'High', 'Weak', 'No'],
               ['Sunny', 'Cool', 'Normal', 'Weak', 'Yes'],
               ['Rain', 'Mild', 'Normal', 'Weak', 'Yes'],
               ['Sunny', 'Mild', 'Normal', 'Strong', 'Yes'],
               ['Overcast', 'Mild', 'High', 'Strong', 'Yes'],
               ['Overcast', 'Hot', 'Normal', 'Weak', 'Yes'],
               ['Rain', 'Mild', 'High', 'Strong', 'No']
               ]
    lable = [data[-1] for data in dataSet]  # 标签属性->分类结果
    # 除去标签列的其余数据
    data_cindex = len(dataSet[0])-1  #除去标签的数据属性个数
    new_data_set = [] #除去标签属性的数据集，每一行数据表示原来数据每一列的属性值
    for i in range(data_cindex):
        shuxing = [] #存放每一个属性的值
        for data in  dataSet:
            shuxing.append(data[i])
        new_data_set.append(shuxing)
    return new_data_set,lable,dataSet
 
# 标签转换函数
def transform_lable(lable):
    lable_set = list(set(lable))
    lable_set.sort()
    print(lable_set)
    new_lable = []
    for liebei in lable:
        for i in range(len(list(lable_set))):
            if liebei == list(lable_set)[i]:
                new_lable.append(int(liebei.replace(liebei, str(i))))
    return new_lable
 
# 数据集转换函数
def transform_data(data, data_cindex):
    new_data = []
    temp = []
    for i in range(data_cindex):
        lable_set = list(set(data[i]))
        lable_set.sort()
        new_lable = []
        for liebei in data[i]:  # 循环每一行除去标签的数据集
            for i in range(len(list(lable_set))):
                if liebei == list(lable_set)[i]:
                    new_lable.append(int(liebei.replace(liebei, str(i))))
        temp.append(new_lable)
        print(lable_set)
    for j in range(len(temp[0])):  # 字列表的长度
        lie = []
        for i in range(len(temp)):  # 子列表的个数
            lie.append(temp[i][j])
        new_data.append(lie)
    return new_data
 
# 数据导入
new_data_set, lable, dataSet = load_data()
# 除去标签的数据属性个数  # 除去标签的数据属性个数
data_cindex = len(dataSet[0]) - 1
# 标签
final_lable = np.array(transform_lable(lable))
print(final_lable)
# 数据
final_data = transform_data(new_data_set, data_cindex)
print(final_data)
clf = DecisionTreeClassifier(criterion="entropy")
clf.fit(final_data,final_lable)
pre = clf.predict([[1,1,1,0]])
print(pre)
dot_data = tree.export_graphviz(clf, out_file=None)  # 导出决策树
graph = graphviz.Source(dot_data)                    # 创建图形
graph.render('运动')

下面进行运行结果解读

结果解读：
1.标签
['No', 'Yes']
[0 0 1 1 1 1 1 0 1 1 1 1 1 0]
0对应第一个列表的索引值，表示no，1表示yes
 
2.数据集的数值转化解读
['Overcast', 'Rain', 'Sunny']
['Cool', 'Hot', 'Mild']
['High', 'Normal']
['Strong', 'Weak']
[[2, 1, 0, 1], [2, 1, 0, 0], [0, 1, 0, 1], [1, 2, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0], [0, 0, 1, 0], [2, 2, 0, 1], [2, 0, 1, 1], [1, 2, 1, 1], [2, 2, 1, 0], [0, 2, 0, 0], [0, 1, 1, 1], [1, 2, 0, 0]]
比如第一条[2，1，0，1]表示['Overcast','Hot','High','Weak']，参照上方出现的字符串列表，进行索引解读即可。
 
3.结果
[0]
标签为0对应no，表示不运动
 
Process finished with exit code 0

决策树图形如下：

决策树不唯一，编码不同可能回导致画出来的图不一样。