使用C4.5算法实现一棵完整的树
决策树的构建需要找到最优特征列对树的节点进行层层划分，而找寻最优特征列常用的有ID3，C4.5，CART三种方法，今天我给大家讲解一下如何使用C4.5算法来找到最优特征列来建立决策树。
1.首先我们创建一组数据，该数据组一共由8组数据组成，共2列特征列，1列标签列
from math import log
import operator
def createDataSet():
dataSet = [[1,1,'yes'],
[1,1,'yes'],
[1,0,'yes'],
[0,1,'no'],
[0,1,'no'],
[0,0,'no'],
[0,0,'yes'],
[0,0,'no']]
labels = ['是否有房产','是否有车']
return dataSet,labels2.使用ID3算法，需计算信息熵，我们先创建calcShannonEnt方法计算信息熵
注：熵的计算公式为 
参照公式理解代码更加简单。
def calcShannonEnt(dataSet):
num = len(dataSet) # 总共有多少行数据 8
shannonEnt = 0.0 #初始化信息熵
labelCounts = {}
for item in dataSet: # 遍历整个数据集，每次取一行
label = item[-1] #取该行最后一列的值 即标签
if label not in labelCounts: # 在字典中这个label是否存在
labelCounts[label] = 0
labelCounts[label] += 1 #{ 'yes':2,'no':3 }
for key in labelCounts:
p = float(labelCounts[key]/num) # 即每个标签所占的比重
#print( p )
shannonEnt -= p * log(p,2) #log base 2 计算信息熵
return shannonEnt # 返回根节点信息熵
# labelCounts {'yes': ..., 'no': ...}我们来测试一下这个方法
dataSet,labels = createDataSet()
shan = calcShannonEnt( dataSet )
print( shan )
'''
熵值越高，则混合的数据越多
'''
# 下面再增加一个分类
dataSet[7][-1] = '不确定'
shan = calcShannonEnt( dataSet )
print( shan )运行上面代码得到结果
3. 接下来，我们创建一个splitDataSet方法来对我们的数据集进行切割
注：实际上就是将每一行的第二列特征列和标签列切分出来，以方便后面的计算
def splitDataSet( dataSet,axis,value ):
result = []
for item in dataSet: # item: [1,1,'yes']
if item[axis] == value:
r = item[:axis] + item[axis+1:] # []+[1,'yes'] => r=> [1,'yes']
# r = item[-1:] #TODO: 只作熵运算的话，只用保留最后一列的值即可
result.append(r)
return result我们再来测试一下代码，看看其实现效果如何
dataSet,labels = createDataSet()
result = splitDataSet( dataSet,0,1 )
print(result)
result = splitDataSet( dataSet,0,0 )
print(result)
result = splitDataSet( dataSet,1,1 )
print(result)
result = splitDataSet( dataSet,1,0 )
print(result)运行上面代码得到结果
4. 到了我们最重要的一步，通过信息熵计算信息增益率来求出划分数据集的最优特征
注：信息增益的计算公式为 
信息增益率的计算公式为 
其中 
# 选取当前数据集下，用于划分数据集的最优特征
def chooseBestFeatures(dataSet):
# 1. 特征总数 2
numFeatures = len(dataSet[0]) -1 # 获取当前数据集的特征个数，最后一列是分类标签 2
# 2. 计算信息熵 1
ent = calcShannonEnt(dataSet) # 计算当前数据集的信息熵 (根节点信息熵)
# 3. 最佳信息熵
bestGain = 0.0;
# 4. 最佳特征号 (0,1)
bestFeatureID = -1 # 初始化最优信息增益和最优的特征
# 5.最佳信息增益率
infogain = 0.0;
# 循环特征（列）
for i in range(numFeatures):
list1 = [line[i] for line in dataSet] # 获取数据集中当前特征下的所有值
uniqueValues = set(list1) # 每一列去重后的值， set可以去重 set(list) 将list列表强制转换为set {0,1}
#print( uniqueValues )
newEnt = 0.0 # 条件熵
s = 0.0
for value in uniqueValues:
# 调用splitDataSet ( 列,set中的值 ) -> 得到子集
subDataSet = splitDataSet(dataSet,i,value) # (dataSet,0,0) (dataSet,0,1) (dataSet,1,0) (dataSet,1,1)
# 计算概率
prob = len(subDataSet)/float(len(dataSet)) # 5/8 3/8 4/8 4/8
# 计算熵
newEnt += prob * calcShannonEnt(subDataSet)
s -= prob * log(prob, 2);
print( '信息熵为:' + str(ent) )
print( '第' + str(i) + '列的条件熵为:' + str(newEnt) )
gain = ent - newEnt
print( '第' + str(i) + '列的信息增益为:' + str(gain) )
infogain = gain/s # 求该列的信息增益比
print( '第' + str(i) + '列的信息增益比为:' + str(infogain) )
if (infogain > bestGain):
# 比较每个特征的信息增益比，只要最好的信息增益比
bestGain = infogain
bestFeatureID = i
return bestFeatureID在代码中，s 即为公式中的 IV(a)
测试一遍上面代码计算信息增益和信息增益率
dataSet,labels = createDataSet()
index = chooseBestFeatures( dataSet )
print(index)得到结果
5. 建立一个classNum()方法（为构建决策树做准备）
注：该方法实际上就是将传入的离散型数据按出现的频率进行降序排列，并返回第一个键名
def classNum( classList ):
'''
classList: 分类的名称
'''
classCount = {} # 存各种分类出现的频率 : {'yes',1,'no',2}
for label in classList:
classCount[label] = classCount.get(label,0) + 1
# 对字典进行排序
sortedClassCount = sorted( classCount.items(),key=operator.itemgetter(1),reverse=True )
print( sortedClassCount )
return sortedClassCount[0][0]对此方法进行测试
classNum( ['yes','no','no','yes','no'] )得到结果
6. 下面我们开始根据我们得到的最优特征来构建决策树
# 生成决策树的总方法
def createTree(dataSet,labels,depth=0,max_features=None,max_depth=None):
# 求出 dataSet 中的样本所属的类别，即递归停止的条件一
# 返回当前数据集下标签所有的值
classList = [example[-1] for example in dataSet] # ['yes','yes','yes','no','no','no','yes','no']
# 终止条件1： 可以加上判断 这个classList是否纯净
if classList.count(classList[0]) == len(classList):
# 纯净的意思就是此数据中所有特征都相等
# 当整个dataSet中的类别完全相同时类别已经纯净了，则停止继续划分，直接返回该类标签
return classList[0]
# 终止条件2： 列中的取值种类 <=max_features 时. max_features 即划分时考虑的最大特征数 默认为 None
if max_features == None:
max_features = 1
if len( dataSet[0] )<=max_features:
return classNum( classList ) # 返回数量多的那一个 标签
# max_depth 树的最大深度,也就是说当树的深度到达max_depth的时候无论还有多少可以分支的特征,决策树都会停止运算
if max_depth!=None:
if depth>=max_depth:
return classNum(classList)
depth = depth + 1
# 获取最好的分类特征索引
# dataSet = [1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'yes'], [0, 1, 'no'], [0, 1, 'no'], [0, 0, 'no'], [0, 0, 'yes'], [0, 0, 'no']
bestFeat = chooseBestFeatures(dataSet) # bestFeat: 0 bestFeat: 0
#print( 'bestFeat:',bestFeat )
# 获取该特征的名字
# labels = ['是否有房产', '是否有车']
bestFeatLabel = labels[bestFeat]
#print( 'bestFeatLabel:',bestFeatLabel ) # bestFeatLabel: 是否有房产 bestFeatLabel: 是否有车
# 这里直接使用字典变量来存储树信息，这对于回执树形图很重要
myTree = {bestFeatLabel:{}} # 当前数据集选取最好的特征存储在bestFeat中
del(labels[bestFeat]) # 删除已经在选取的特征 此时 labels = ['是否有车']
# 取出最优列的值
featValues = [example[bestFeat] for example in dataSet]
# featValues: [1, 1, 1, 0, 0, 0, 0, 0] featValues: [1, 1, 0, 0, 0]
#print( 'featValues:',featValues )
# 去重
uniqueVals = set(featValues) # [1,0]
# 根据这个列的这个 uniqueVals值来切分树的节点
for value in uniqueVals:
# myTree -> 房产 -> 1
# 房产 -> 0
subLabels = labels[:]
#print( 'subLabels:',subLabels )
temp = splitDataSet( dataSet,bestFeat,value )
#print( 'temp:',temp )
myTree[bestFeatLabel][value] = createTree(temp,subLabels,depth=depth,max_features=max_features,max_depth=max_depth)
return myTree我们来看看我们构建的决策树
该决策树共进行两次分类，第一次由‘是否有房产’进行一次划分，第二次由‘是否有车’进行一次划分
由于我们建立的数据并不合理，所以看上去我们建立的决策树并不可观，大家可以试试更多数据构建新的决策树
注：此文章为代码实现，看起来可能有些费解，大家可以参照本人的另一篇博客https://blog.csdn.net/LA401088242/article/details/89034077 了解其原理，以便大家更好的了解代码