步骤
1、计算数据集S中每个属性的熵 H(xi)
2、选择数据集S中熵最小(或信息增益，两者等价)的属性
3、该属性节点在决策树上生成
4、使用剩余节点重复上述步骤生成决策树的属性节点
实例
importnumpyasnp
importmath
fromcollectionsimportCounter
#创建数据
defcreate_data():
X1=np.random.rand(50,1)*100
X2=np.random.rand(50,1)*100
X3=np.random.rand(50,1)*100
deff(x):
return2ifx>70else1ifx>40else0
y=X1+X2+X3
Y=y>150
Y=Y+0
r=map(f,X1)
X1=list(r)
r=map(f,X2)
X2=list(r)
r=map(f,X3)
X3=list(r)
x=np.cX1、X2、X3、Y]
returnx,['courseA','courseB','courseC']
#集合信息熵的函数计算
defcalculate_info_entropy(dataset):
n=len(dataset)
#让我们用Counter统计Y的数量
labels=Counter(dataset[:,-1])
entropy=0.0
#应用信息熵公式
fork,vinlabels.items():
prob=v/n
entropy-=prob*math.log(prob,2)
returnentropy
#拆分函数的实现
defsplit_dataset(dataset,idx):
#下标idx是拆分的特征
splitData=defaultdict(list)
fordataindataset:
#这里删除了idx特征的值，因为它不能使用
splitData[data[idx]].append(np.delete(data,idx))
returnlist(splitData.values()),list(splitData.keys())
#选择函数来实现特征
defchoose_feature_to_split(dataset):
n=len(dataset[0])-1
m=len(dataset)
#切分之前的信息熵
entropy=calculate_info_entropy(dataset)
bestGain=0.0
feature=-1
foriinrange(n):
#根据特征I切分
split_data,_=split_dataset(dataset,i)
new_entropy=0.0
#计算切割后的信息熵
fordatainsplit_data:
prob=len(data)/m
new_entropy+=prob*calculate_info_entropy(data)
#获取信息增益
gain=entropy-new_entropy
ifgain>bestGain:
bestGain=gain
feature=i
returnfeature
#决策树创建函数
defcreate_decision_tree(dataset,feature_names):
dataset=np.array(dataset)
counter=Counter(dataset[:,-1])
#如果剩下一类数据集值，直接返回
iflen(counter)==1:
returndataset[0,-1]
#假如所有的特征都被切割了，也直接返回
iflen(dataset[0])==1:
returncounter.most_common(1)[0][0]
#寻找最佳切分的特征
fidx=choose_feature_to_split(dataset)
fname=feature_names[fidx]
node={fname:{}}
feature_names.remove(fname)
#递归调用，每个切分的取值递归建树
split_data,vals=split_dataset(dataset,fidx)
fordata,valinzip(split_data,vals):
node[fname][val]=create_decision_tree(data,feature_names[:])
returnnode
#决策树节点预测函数
defclassify(node,feature_names,data):
#获取当前节点判断的特征
key=list(node.keys())[0]
node=node[key]
idx=feature_names.index(key)
#递归是根据特征进行的
pred=None
forkeyinnode:
#找到相应的分叉
ifdata[idx]==key:
#若再往下还有子树，然后递回，否则返回结果
ifisinstance(node[key],dict):
pred=classify(node[key],feature_names,data)
else:
pred=node[key]
#假如没有相应的分叉，找一个分叉返回
ifpredisNone:
forkeyinnode:
ifnotisinstance(node[key],dict):
pred=node[key]
break
returnpred以上是python决策树算法的实现步骤，希望对大家有所帮助。更多Python学习指导：python基础教程
本教程的操作环境：windows7系统，Python 3.9.1，DELL G3电脑。