python实现决策树实现决策树ID3算法的示例代码算法的示例代码
主要介绍了python实现决策树ID3算法的示例代码，小编觉得挺不错的，现在分享给大家，也给大家做个参考。
一起跟随小编过来看看吧
在周志华的西瓜书和李航的统计机器学习中对决策树ID3算法都有很详细的解释，如何实现呢？核心点有如下几个步骤
step1:计算香农熵计算香农熵
from math import log
import operator
# 计算香农熵
def calculate_entropy(data):
label_counts = {}
for feature_data in data:
laber = feature_data[-1] # 最后一行是laber
if laber not in label_counts.keys():
label_counts[laber] = 0
label_counts[laber] += 1
count = len(data)
entropy = 0.0
for key in label_counts:
prob = float(label_counts[key]) / count
entropy -= prob * log(prob, 2)
return entropy
step2.计算某个计算某个feature的信息增益的方法的信息增益的方法
# 计算某个feature的信息增益
# index:要计算信息增益的feature 对应的在data 的第几列
# data 的香农熵
def calculate_relative_entropy(data, index, entropy):
feat_list = [number[index] for number in data] # 得到某个特征下所有值（某列）
uniqual_vals = set(feat_list)
new_entropy = 0
for value in uniqual_vals:
sub_data = split_data(data, index, value)
prob = len(sub_data) / float(len(data))
new_entropy += prob * calculate_entropy(sub_data) # 对各子集香农熵求和
relative_entropy = entropy - new_entropy # 计算信息增益
return relative_entropy
step3.选择最大信息增益的选择最大信息增益的feature
# 选择最大信息增益的feature
def choose_max_relative_entropy(data):
num_feature = len(data[0]) - 1
base_entropy = calculate_entropy(data)#香农熵
best_infor_gain = 0
best_feature = -1
for i in range(num_feature):
info_gain=calculate_relative_entropy(data, i, base_entropy)
#最大信息增益
if (info_gain > best_infor_gain):
best_infor_gain = info_gain
best_feature = i
return best_feature
step4.构建决策树构建决策树
def create_decision_tree(data, labels):
class_list=[example[-1] for example in data]
# 类别相同，停止划分
if class_list.count(class_list[-1]) == len(class_list):
return class_list[-1]
# 判断是否遍历完所有的特征时返回个数最多的类别
if len(data[0]) == 1:
return most_class(class_list)
# 按照信息增益最高选取分类特征属性
best_feat = choose_max_relative_entropy(data)
best_feat_lable = labels[best_feat] # 该特征的label
decision_tree = {best_feat_lable: {}} # 构建树的字典
评论0