前言
上篇文章介绍了决策树(Decision Tree)
的原理和实现决策树算法,如果对这些不懂的,可以移步上篇
文章,本文章完成的是用ID3
算法实现决策树。
定义数据
假设以下数据
N1 | N2 | X |
---|---|---|
I | I | TRUE |
T | I | TRUE |
I | T | TRUE |
C | I | FALSE |
T | T | TRUE |
I | C | FALSE |
E | I | FALSE |
C | T | FALSE |
T | C | FALSE |
I | E | FALSE |
E | T | FALSE |
T | E | FALSE |
其中N1
、N2
为我们的featrues
, X
为我们的label
。决策目标是X
的值,TRUE
或者FALSE
。
定义以下数据:
def load_data():
data=[
['I','I','TRUE'],
['T','I','TRUE'],
['I','T','TRUE'],
['C','I','FALSE'],
['T','T','TRUE'],
['I','C','FALSE'],
['E','I','FALSE'],
['C','T','FALSE'],
['T','C','FALSE'],
['I','E','FALSE'],
['E','T','FALSE'],
['T','E','FALSE']
]
features=["N1","N2"]
return data,features
计算熵
由上数据得,共有12个样本,共有4个TRUE和8个FALSE,那么熵的计算公式就是
def cal_entropy(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
label = featVec[-1]
if label not in labelCounts.keys():
labelCounts[label] = 0
labelCounts[label] += 1
entropy = 0.0
for key in labelCounts.keys():
p_i = float(labelCounts[key] / numEntries)
entropy -= p_i * log(p_i,2)#log(x,10)表示以10 为底的对数
return entropy
选择信息增益
选择最大的信息增益
对应的feature
。信息增益的解释在上篇博客。
def choose_best_to_split(data):
'''
根据每个特征的信息增益,选择最大的划分数据集的索引特征
'''
count_feature=len(data[0])-1#特征个数2
# print(count_feature) #2
entropy=cal_entropy(data) #原数据总的信息熵
# print(entropy) #0.9182958340544896
max_info_gain=0.0 #信息增益最大
split_fea_index = -1 #信息增益最大,对应的索引号
# 遍历每个feature
for i in range(count_feature):
feature_list = [fe_index[i] for fe_index in data] #获取该列所有特征值
# print(feature_list)
'''
print('feature_list')
['I', 'T', 'I', 'C', 'T', 'I', 'E', 'C', 'T', 'I', 'E', 'T']
0.6666666666666666
0.2516291673878229
'''
unqval = set(feature_list) #去除重复
Pro_entropy=0.0 #特征的熵
for value in unqval: #遍历改特征下的所有属性
sub_data = split_data(data,i,value)
pro = len(sub_data) / float(len(data))
Pro_entropy += pro * cal_entropy(sub_data)
# print(Pro_entropy)
info_gain = entropy-Pro_entropy
# print(info_gain)
'''
N1的info_gain:0.2516291673878229
N2的info_gain:0.2516291673878229
两者一样,说明根决策点选择哪个feature都跟最终结果没有影响。
'''
if(info_gain > max_info_gain):
max_info_gain = info_gain
split_fea_index = i
return split_fea_index
通过输出每个feature
的信息增益,发现每个feature
对整个信息的影响程度都相同,所以无论选取哪个feature
作为根决策点,都对结果没有影响,文章末尾可以通过决策树可视化来说明。
划分数据
划分数据集,选择最大的信息增益之后,划分数据集,为下一层的划分做准备
def split_data(data,feature_index,value):
'''
划分数据集
feature_index:用于划分特征的列数
value:划分后的属性值
'''
data_split=[]#划分后的数据集
for feature in data:
if feature[feature_index]==value:
reFeature=feature[:feature_index]
reFeature.extend(feature[feature_index+1:])
data_split.append(reFeature)
return data_split
构建决策树
利用多重字典来构建决策树, 字典的key用来存节点信息,分支和叶子节点存放值。
建树的过程是一个递归的过程。
def build_decesion_tree(dataSet,featnames):
featname = featnames[:]
classlist = [featvec[-1] for featvec in dataSet] #此节点的分类情况
if classlist.count(classlist[0]) == len(classlist): #全部属于一类
return classlist[0]
if len(dataSet[0]) == 1: #就剩下一个属性了
return classlist
# 选择一个最优特征进行划分
bestFeat = choose_best_to_split(dataSet)
bestFeatname = featname[bestFeat]
del(featname[bestFeat]) # 删除元素
DecisionTree = {bestFeatname:{}} # 决策树的节点
# 创建分支,先找出所有属性值,即分支数
allvalue = [vec[bestFeat] for vec in dataSet]
specvalue = sorted(list(set(allvalue))) #字典序排序
for v in specvalue:
copyfeatname = featname[:]
DecisionTree[bestFeatname][v] = build_decesion_tree(split_data(dataSet,bestFeat,v),copyfeatname)
return DecisionTree
返回结果:
{'N1': {'C': 'FALSE', 'E': 'FALSE', 'I': {'N2': {'C': 'FALSE', 'E': 'FALSE', 'I': 'TRUE', 'T': 'TRUE'}}, 'T': {'N2': {'C': 'FALSE', 'E': 'FALSE', 'I': 'TRUE','T': 'TRUE'}}}}
如果选取N2
作为根决策点,输出的结果:
{'N2': {'C': 'FALSE', 'E': 'FALSE', 'I': {'N1': {'C': 'FALSE', 'E': 'FALSE', 'I': 'TRUE', 'T': 'TRUE'}}, 'T': {'N1': {'C': 'FALSE', 'E': 'FALSE', 'I': 'TRUE', 'T': 'TRUE'}}}}
说明对于此数据(其他数据除外),特征的选择顺序对决策的结果没有影响。
决策树可视化
对于两种决策树进行可视化的结果如下:
2 comments