关注公众号：用Python学机器学习，更多更新等着您。
上一篇文章，我们已经介绍了决策树的ID3算法，并编写了一个实现决策树ID3算法的程序。实际中，ID3算法应用并不多，C4.5才是应用较多的分类树算法。究其原因在于ID3算法存在以下几个缺点：1）倾向于选择类别较多的特征变量作为分割属性；2）无法处理连续变量；3）无法处理缺失值；4）没有完备的剪枝策略。C4.5算法在这四个方面做出了改进，这篇文章我们就来学习一下。关于剪枝策略，我们留到下一篇文章来介绍，这篇文章我们主要介绍C4.5对前三个问题的改进。
信息增益的改进
ID3算法使用信息增益进行特征选择，这导致算法倾向于选择类别较多的特征变量作为分割属性。针对这一缺点，C4.5算法提出一种新的特征选择算法——信息增益率。信息增益率的定义如下：
其中
IV被称为特征的固有值，其实就是特征的熵，信息增益率可以简单的理解为信息增益除以特征的熵。也就是评估特征的单位熵带来的信息增益的变化。编程如下：
def entropy(x):
"""
计算经验熵，熵被定义为信息量的加权平均，权重为概率。
:param x:numpy数组
:return: 经验熵，一个标量
"""
# 将ndarray数组转化为列表
x = list(x)
# 估计x的概率分布
x_p = np.array([x.count(i)/len(x) for i in set(x)])
# 计算熵
return -np.sum([p*np.log2(p) for p in x_p])
def con_entropy(x,y):
"""
计算条件熵
:param x: 一维数组
:param y: 一维数组
:return: 返回x条件下y的熵
"""
# 取出x中的不重复值
x_uni = np.unique(x)
# 取出不同的x中的所有y熵来计算条件熵
con_ent = 0
for i in x_uni:
y_new = y[x == i]
y_ent = entropy(y_new)
con_ent += len(y_new)*y_ent/len(x)
return con_ent
def info_gain(x,y):
"""
计算信息增益，ID3算法使用
:param x: 一个一维列表或数组
:param y: 一个一维列表或数组
:return: 返回信息增益
"""
return entropy(y)-con_entropy(x,y)
def info_gain_rate(x,y):
"""
计算信息增益率，C4.5算法使用
:param x: 一个一维列表或数组
:param y: 一个一维列表或数组
:return: 返回信息增益率
"""
if entropy(x) != 0:
return info_gain(x,y)/entropy(x)
else:
return 0处理连续变量
对于连续变量，C4.5算法提出使用二分法进行解决。其基本思想为，首先取出连续特征中的不重复值，并按照升序进行排列。在排序后的数据中取相邻数据点的中点（平均数）作为该连续特征的分割点，这样可以将样本分为两个类别。遍历所有中点，并计算以该中点为分割点时的信息增益，取信息增益最大的中点作为分割点对连续特征进行划分。编程如下：
def bin(x,y):
"""
连续变量离散化
:param x: x为一维数组
:return: 返回与x等长度的分箱结果
"""
# 拿到一维数组中不重复值
x_uni = np.unique(x)
# 获取分割点
x_split = (x_uni[0:-1]+x_uni[1:])/2
best_gain = 0
best_split = 0
# 遍历分割点，计算信息增益
for i in x_split:
x_i = np.zeros_like(x)
print(i)
x_i[x>i] = 1
x_i[x<i] = 0
curr_gain = info_gain(x_i,y)
if curr_gain> best_gain:
best_gain = curr_gain
best_split = i
x_new = np.zeros_like(x)
x_new[x>best_split] = 1
x_new[x<best_split] = 0
return x_new处理缺失值
关于如何处理缺失值，其实需要面对两个问题：
- 如何计算信息增益或信息增益率？前面在介绍计算信息增益或信息增益率时，是基于样本无缺失值的情况的，如果样本有缺失值，是否需要将缺失值考虑在内呢？
- 缺失样本应该划分到哪个子节点？例如上一篇文章我们的例子中，在判断一个人的性别时，我们首先选择的是喉结，根据喉结划分两个子节点，即有喉结和无喉结。如果当前一个样本的在喉结这个变量上为缺失值时，究竟应该将其划分到有喉结的分支还是无喉结的分支呢？
对于第一个问题，C4.5算法的处理思路很简单，算法首先会给每一个样本赋予一个权重，初始权重通常为1。然后会计算出当前特征上，无缺失值样本所占的比例，令为ρ。
这里的表示的是无缺失值样本集合，?表示的是全样本集合。很显然公式计算的是无缺失样本集合中样本权重求和除以全样本集中样本权重的求和。
紧接着，算法会计算无缺失值样本的信息增益：
这里我们参照周志华《机器学习》对公式做统一的说明。?计算的是特征变量a在无缺失值样本?上的信息增益，?表示的是无缺失值样本?上计算的信息熵，我们假定特征变量a有1,2...,v,...V个类别，?表示的是在无缺失值样本中第v个类别的信息熵，而第v个类别的概率分布计算如下：
这表明第v个类别的概率分布等于第v个类别中所有样本的样本权重求和，然后除以无缺失值样本中所有样本的样本权重求和。
信息熵的计算公式也发生了变化：
这里我们其实假定了因变量或者说标签的类别有1,2,...k,...y个类别。这里的?为：
因变量的概率分布同样也发生了变化，上一篇文章中概率使用频率来估计的，现在是用样本权重来估计的。计算好了上面的结果后，就可以计算全样本的信息增益了：
这就是C4.5在计算信息增益上给出的解决方案。简单的说，有两点变化，第一点就是全样本的信息增益等于无缺失值样本的比例乘以用无缺失值样本计算的信息增益，第二点是概率的计算发生了变化，这导致在计算信息熵、条件熵以及信息增益上都发生了变化，新的算法中概率是使用样本权重来估计的，而不是样本频率。与信息增益相同，计算信息增益率时同样会乘以无缺失样本的比例。接下来我们编程实现这一算法：
首先我们先编写计算熵的程序如下：
def entropy(x,weight=None):
"""
计算经验熵，熵被定义为信息量的加权平均
Parameters
----------
x : 一维ndarray数组
weight : 样本权重
Returns
-------
经验熵
"""
length = len(x)
if weight is None:
weight = np.array([1.0]*length)
# 计算权重和，后面用来的估计概率
weight_sum = np.sum(weight)
# 计算概率分布
x_p = [np.sum(weight[np.where(x==i)])/weight_sum for i in set(x)]
# 计算熵
return -np.sum([p*np.log2(p) for p in x_p])然后再编写计算条件熵的程序
def con_entropy(x,y,weight=None):
"""
计算条件熵
Parameters
----------
x : 一维ndarray数组
y : 一维ndarray数组
weight : 样本权重
Returns
-------
条件经验熵
"""
length = len(y)
if weight is None:
weight = np.array([1]*length)
# 计算权重和，后面用来的估计概率
weight_sum = np.sum(weight)
con_ent=0
# 循环x的每一个取值，计算y的熵
for x_i in np.unique(x):
# 拿到x_i对应的y
y_new = y[x==x_i]
# 拿到x_i对应的样本权重
weight_new = weight[x == x_i]
# 计算x_i的概率分布
x_i_prob = np.sum(weight_new)/weight_sum
# 计算x_i下y的条件熵
y_new_ent = entropy(y_new,weight_new)
# 条件熵求和
con_ent += x_i_prob*y_new_ent
return con_ent然后是信息增益：
def info_gain(x,y,weight=None):
"""
计算信息增益
Parameters
----------
x : 一维ndarray数组
y : 一维ndarray数组
weight : 样本权重
Returns
-------
信息增益
"""
# 计算数组的长度
length = len(y)
# 如果未输入权重，则权重为1
if weight is None:
weight = np.array([1]*length)
# 计算信息增益
return entropy(y)-con_entropy(x, y,weight)信息增益率
def info_gain_rate(x,y,weight=None):
"""
Parameters
----------
x : 一维ndarray数组
y : 一维ndarray数组
weight : 样本权重
Returns
-------
信息增益率
"""
length = len(y)
if weight is None:
weight = np.array([1]*length)
# 特征的固有值可能为0，如果为0，我们令信息增益率返回0
if entropy(x) != 0:
return info_gain(x, y,weight)/entropy(x,weight)
else:
return 0以上完成了特征选择算法的编程实现，接下来我们解决第二个问题：缺失样本应该划分到哪个子节点？对于这个问题，C4.5算法的做法是缺失样本以不同的概率划分到不同的子节点中，这里的概率计算公式为?。也就是说缺失样本会划分到所有的子节点中，只不过在不同子节点中有不同的权重。下面我们在上一节的基础上编程来实现这一过程。这里设计了两个类：
class Nodes(object):
def __init__(self
,n_sample=None
,entro=None
,children_nodes=None
,best_feature=None
,class_prob=None):
self.n_sample=n_sample
self.entro=entro
self.children_nodes=children_nodes
self.best_feature=best_feature
self.class_prob=class_prob
class DTClassifier(object):
def __init__(self,criterion='C4.5'):
self.criterion=criterion
if self.criterion == 'C4.5':
self.func = info_gain_rate
elif self.criterion == 'id3':
self.func = info_gain
else:
raise ValueError("值异常")
def fit(self,X,y,weight=None):
# 创建根节点对象
self.root_node = Nodes()
length = len(y)
if weight is None:
weight = np.array([1.0]*length)
# 开始种树
self.__plant_tree(X,y,self.root_node,weight)
def __plant_tree(self,X,y,node,weight=None):
# 记录当前节点的行数目和列数目
rows,cols = X.shape
weight_sum = np.sum(weight)
# 记录当前节点的样本量
node.n_sample = rows
# 记录当前节点的熵
node.entro=entropy(y,weight)
# 记录当前节点标签的概率分布
node.class_prob={key: np.sum(weight[y==key])/weight_sum for key in np.unique(y)}
# 如果当前样本属于同一个类别，则跳出递归
if len(np.unique(y))==1:
return
# 如果所有特征都只有一个取值，就跳出递归
if np.sum([len(np.unique(X[:,i])) for i in range(cols)])==cols:
return
# 循环特征，计算信息增益或者信息增益率
best_col = None
best_gain = 0
for col in range(cols):
x_col = X[:,col]
# 特征上无缺失值的索引
i_nonan = ~np.isnan(x_col)
# 无缺失索引所占的比例
nonan_prob = np.sum(weight[i_nonan])/weight_sum
curr_gain = self.func(x_col[i_nonan],y[i_nonan],weight[i_nonan])*nonan_prob
if curr_gain>best_gain:
best_gain = curr_gain
best_col = col
# 记录节点的最佳索引
node.best_feature=best_col
# 记录节点的子节点
node.children_nodes = {}
# 拿到最佳分支特征的数据
x_best = X[:,best_col]
# 最佳特征上非缺失值的索引
nonan_i = ~np.isnan(x_best)
#
for i in np.unique(x_best[nonan_i]):
i_prob = np.sum(weight[x_best==i])/np.sum(weight[nonan_i])
X_new = X[(x_best==i)+(~nonan_i)]
y_new = y[(x_best==i)+(~nonan_i)]
weight_new = weight[(x_best==i)+(~nonan_i)]
nan_new = np.isnan(X_new[:,best_col])
weight_new[nan_new] = weight_new[nan_new]*i_prob
node.children_nodes[i] = Nodes()
self.__plant_tree(X_new, y_new, node.children_nodes[i],weight_new)
def predict(self,x):
results = self.predict_prob(x)
pred = []
for i in range(len(results)):
p = max(results[i],key=lambda k : results[i][k])
pred.append(p)
return pred
def predict_prob(self,x):
# 获取输入数据的行数目
rows = x.shape[0]
# 定义一个列表，用来存储结果
results = []
# 遍历每一行数据，检索叶子节点，拿到叶子结点中标签的概率分布。
for i in range(rows):
result = self.__search_leaf_node(x[i],self.root_node)
results.append(result)
return results
def __search_leaf_node(self,x,node):
# 如果输入节点的子节点为None，说明当前节点为叶子节点，那么就从叶子节点中拿到标签的概率分布，这里定义为一个字典。
if node.children_nodes is None:
result = {i:node.class_prob.get(i,0) for i in self.root_node.class_prob.keys()}
return result
# 如果输入的节点的子节点不为None，说明有子节点，当前节点还不是叶子结点。
else:
# 那么就进入当前节点的子节点
curr_node = node.children_nodes[x[node.best_feature]]
# 递归，直到找到叶子结点
return self.__search_leaf_node(x, curr_node)预测
以上，我们完成了C4.5算法主要程序的设计（不包括剪枝策略），接下来，我们使用数据验证一下模型。数据来源于周志华《机器学习》86页，西瓜数据集2.0α。数据情况如下：
>>>a = np.array([[np.nan, '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', np.nan],
['乌黑', '蜷缩', np.nan, '清晰', '凹陷', '硬滑'],
['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],
[np.nan, '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
['青绿', '稍蜷', '浊响', '清晰', np.nan, '软沾'],
['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软沾'],
['乌黑', '稍蜷', '浊响', np.nan, '稍凹', '硬滑'],
['乌黑', np.nan, '沉闷', '稍糊', '稍凹', '硬滑'],
['青绿', '硬挺', '清脆', np.nan, '平坦', '软沾'],
['浅白', '硬挺', '清脆', '模糊', '平坦', np.nan],
['浅白', '蜷缩', np.nan, '模糊', '平坦', '软沾'],
[np.nan, '稍蜷', '浊响', '稍糊', '凹陷', '硬滑'],
['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑'],
['乌黑', '稍蜷', '浊响', '清晰', np.nan, '软沾'],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑'],
['青绿', np.nan, '沉闷', '稍糊', '稍凹', '硬滑']])
>>>b = np.array(['是','是','是','是','是','是','是','是','否','否','否','否','否','否','否','否','否'])我们需要将特征先编码一下：
"""
乌黑1；青绿2；浅白3
蜷缩1；稍蜷2；硬挺3
浊响1；沉闷2；清脆3
清晰1；稍糊2；模糊3
凹陷1；稍凹2；平坦3
硬滑1；软沾2
"""
>>>a = np.array([[np.nan, 1, 1, 1, 1, 1],
[1, 1, 2, 1, 1, np.nan],
[1, 1, np.nan, 1, 1, 1],
[2, 1, 2, 1, 1, 1],
[np.nan, 1, 1, 1, 1, 1],
[2, 2, 1, 1, np.nan, 2],
[1, 2, 1, 2, 2, 2],
[1, 2, 1, np.nan, 2, 1],
[1, np.nan, 2, 2, 2, 1],
[2, 3, 3, np.nan, 3, 2],
[3, 3, 3, 3, 3, np.nan],
[3, 1, np.nan, 3, 3, 2],
[np.nan, 2, 1, 2, 1, 1],
[3, 2, 2, 2, 1, 1],
[1, 2, 1, 1, np.nan, 2],
[3, 1, 1, 3, 3, 1],
[2, np.nan, 2, 2, 2, 1]])然后调用模型：
>>>dt = DTClassifier(criterion='C4.5')
>>>dt.fit(a, b)然后是预测：
>>>a1 = np.array([[2,1,1,1,1,1],
[1,2,1,1,1,2]])
>>>prob = dt.predict_prob(a1)
>>>prob
[{'否': 0, '是': 1.0}, {'否': 1.0, '是': 0}]
>>>class_ = dt.predict(a1)
>>>class_
['是', '否']一个被预测为好瓜，一个为坏瓜。
下一篇文章，我们介绍C4.5算法的剪枝策略，敬请关注。