前言
如果你能找到这里，真是我的幸运~这里是蓝白绛的学习笔记，本集合主要针对《统计学习方法》这本书，主要是基本机器学习算法代码实现的解读。
本篇的代码整理来自github：wepe-Basic Machine Learning and Deep Learning
本篇整理决策树实现，github地址为：wepe-DecisionTree
第五章 决策树
1、模型
- 分类决策树模型是一种描述对实例进行分类的树形结构，由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。
- 特征选择
特征选择在于选取对训练数据具有分类能力的特征。特征选择的准则通常是信息增益或信息增益比。
熵(entropy)：表示随机变量不确定性的度量。设是一个取有限个值的离散随机变量，其概率分布为
则随机变量
定义
。
以
为底单位为比特(bit)；以
为底单位为纳特(nat)。
条件熵(conditional entropy)：表示在已知随机变量的不确定性。随机变量
定义为
当熵和条件熵中的概率由数据统计(特别是极大似然估计)得到时，所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。
-
信息增益(Information gain)：特征
对训练数据集
的信息增益
，定义为集合
与特征
之差
其中
表示样本类别数，
为特征A的类别数，
表示样本中特征A为第
个取值且样本类别为第
一般地，熵与条件熵
-
信息增益比(Information gain ratio)：信息增益
的比
-
Gini指数(Gini index)：假设
个类，样本点属于第
，则概率分布的基尼指数定义为
二分类问题中，若样本点属于第一个类的概率为
，则概率分布的基尼指数为
对于给定样本集合
其中
是D中属于第
在特征分为两个子集
。在特征
- ID3、C4.5、CART树：
ID3：特征选择策略为信息增益。
C4.5：特征选择策略为信息增益比。信息增益偏向于选择取值较多的特征，用信息增益比进行校正。
CART树：特征选择策略为Gini index。既可做分类也可以做回归。ID3、C4.5可能是多叉树，CART树是二叉树。
2、决策树的剪枝
《统计学习方法》这本书上的剪枝均是后剪枝，如果要详细了解剪枝可以查阅其他资料，其中Hulu的《百面机器学习》这本书中的剪枝讲的非常容易理解。本站中我整理的百面机器学习｜第三章经典算法知识点记录了这本书中讲解的前剪枝、后剪枝算法介绍，感兴趣的朋友可以查阅。
3、代码实现
下面的代码块中的代码原作者依然是wepe：wepe-DecisionTree，我仅添加一些注释，方便理解。
下面的代码中的树是用字典实现的。
class DecisionTree:
"""决策树使用方法：
- 生成实例： clf = DecisionTrees(). 参数mode可选，ID3或C4.5，默认C4.5
- 训练，调用fit方法： clf.fit(X,y). X,y均为np.ndarray类型
- 预测，调用predict方法： clf.predict(X). X为np.ndarray类型
- 可视化决策树，调用showTree方法
"""
def __init__(self, mode='C4.5'):
self._tree = None# 树的根节点初始值设为None
if mode == 'C4.5' or mode == 'ID3':# ID3的特征选择方法为信息增益，C4.5的特征选择方法为信息增益比。
self._mode = mode
else:
raise Exception('mode should be C4.5 or ID3')
def _calcEntropy(self, y):
"""
函数功能：计算熵
参数y：数据集的标签
"""
num = y.shape[0]
# 统计y中不同label值的个数，并用字典labelCounts存储
labelCounts = {}
for label in y:
if label not in labelCounts.keys():
labelCounts[label] = 0
labelCounts[label] += 1
# 计算熵
entropy = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / num# 由label对应的个数计算出label的占比
entropy -= prob * np.log2(prob)# 计算每个label的信息熵，将他们相加，取负
return entropy
def _splitDataSet(self, X, y, index, value):
"""
函数功能：返回数据集中特征下标为index，特征值等于value的子数据集
"""
ret = []# ret保存当前特征列中特征值等于value的行数下标，后面用于筛选行。
featVec = X[:, index]# 筛选当前列数据
X = X[:, [i for i in range(X.shape[1]) if i != index]]# 去除当前列数据，留下剩下的数据
for i in range(len(featVec)):
if featVec[i] == value:# 如果当前特征列的值等于value时，保留下标到ret
ret.append(i)
return X[ret, :], y[ret]# 根据ret筛选行
def _chooseBestFeatureToSplit_ID3(self, X, y):
"""ID3
函数功能：对输入的数据集，选择最佳分割特征
参数dataSet：数据集，最后一列为label
主要变量说明：
numFeatures：特征个数
oldEntropy：原始数据集的熵
newEntropy：按某个特征分割数据集后的熵
infoGain：信息增益
bestInfoGain：记录最大的信息增益
bestFeatureIndex：信息增益最大时，所选择的分割特征的下标
"""
numFeatures = X.shape[1]# numFeatures是特征的数量
oldEntropy = self._calcEntropy(y)# 计算没有分裂前y的经验熵
bestInfoGain = 0.0# bestInfoGain为最大信息增益，初始设为0，后面逐步用更大的信息增益替代
bestFeatureIndex = -1# 每次替换最大信息增益时记录是哪一个特征
# 对每个特征都计算一下infoGain，并用bestInfoGain记录最大的那个
for i in range(numFeatures):# 对每个特征
featList = X[:, i]# 筛选出该特征对应列的数据
uniqueVals = set(featList)# uniqueVals为这列特征的可能取值
newEntropy = 0.0# newEntropy记录根据当前特征进行分裂后的经验条件熵
# 对第i个特征的各个value，得到各个子数据集，计算各个子数据集的熵，
# 进一步地可以计算得到根据第i个特征分割原始数据集后的熵newEntropy
for value in uniqueVals:
sub_X, sub_y = self._splitDataSet(X, y, i, value)
prob = len(sub_y) / float(len(y))
newEntropy += prob * self._calcEntropy(sub_y)
# 计算按特征i分裂的经验条件熵，将特征i对应的几个取值对应的经验条件熵加起来
infoGain = oldEntropy - newEntropy# 计算信息增益，根据信息增益选择最佳分割特征
if (infoGain > bestInfoGain):# 如果计算得到的信息增益大于当前信息增益，则更新信息增益及对应特征下标
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex
def _chooseBestFeatureToSplit_C45(self, X, y):
"""C4.5
ID3算法计算的是信息增益，C4.5算法计算的是信息增益比，对上面ID3版本的函数稍作修改即可
"""
numFeatures = X.shape[1]
oldEntropy = self._calcEntropy(y)
bestGainRatio = 0.0
bestFeatureIndex = -1
# 对每个特征都计算一下gainRatio=infoGain/splitInformation
for i in range(numFeatures):
featList = X[:, i]
uniqueVals = set(featList)
newEntropy = 0.0
splitInformation = 0.0
# 对第i个特征的各个value，得到各个子数据集，计算各个子数据集的熵，
# 进一步地可以计算得到根据第i个特征分割原始数据集后的熵newEntropy
for value in uniqueVals:
sub_X, sub_y = self._splitDataSet(X, y, i, value)
prob = len(sub_y) / float(len(y))
newEntropy += prob * self._calcEntropy(sub_y)
splitInformation -= prob * np.log2(prob)
# 计算信息增益比，根据信息增益比选择最佳分割特征
# splitInformation若为0，说明该特征的所有值都是相同的，显然不能作为分割特征，则计算下一个特征
if splitInformation == 0.0:
pass
else:
infoGain = oldEntropy - newEntropy
gainRatio = infoGain / splitInformation
if (gainRatio > bestGainRatio):
bestGainRatio = gainRatio
bestFeatureIndex = i
return bestFeatureIndex
def _majorityCnt(self, labelList):
"""
函数功能：返回labelList中出现次数最多的label
"""
labelCount = {}
for vote in labelList:
if vote not in labelCount.keys():
labelCount[vote] = 0
labelCount[vote] += 1
sortedClassCount = sorted(labelCount.iteritems(), key=lambda x: x[1], reverse=True)
# iteritems()形成的是tuple，x[0]是label，x[1]是count。
return sortedClassCount[0][0]# 返回排序后的第一个tuple的label
def _createTree(self, X, y, featureIndex):
"""建立决策树
featureIndex，类型是元组，它记录了X中的特征在原始数据中对应的下标。featureIndex为('x0','x1',...,'xn')
"""
labelList = list(y)
# 所有label都相同的话，则停止分割，返回该label
if labelList.count(labelList[0]) == len(labelList):
return labelList[0]
# 没有特征可分割时，停止分割，返回出现次数最多的label
if len(featureIndex) == 0:
return self._majorityCnt(labelList)
# 可以继续分割的话，确定最佳分割特征
if self._mode == 'C4.5':
bestFeatIndex = self._chooseBestFeatureToSplit_C45(X, y)
elif self._mode == 'ID3':
bestFeatIndex = self._chooseBestFeatureToSplit_ID3(X, y)
bestFeatStr = featureIndex[bestFeatIndex]
featureIndex = list(featureIndex)# featureIndex是一个tuple，先将其转化为list
featureIndex.remove(bestFeatStr)# 移除被选择的最优分裂特征
featureIndex = tuple(featureIndex)# 将list变回tuple
# 用字典存储决策树。最佳分割特征作为key，而对应的键值仍然是一棵树（仍然用字典存储）
myTree = {bestFeatStr: {}}
featValues = X[:, bestFeatIndex]
uniqueVals = set(featValues)
for value in uniqueVals:
# 对每个value递归地创建树
sub_X, sub_y = self._splitDataSet(X, y, bestFeatIndex, value)
myTree[bestFeatStr][value] = self._createTree(sub_X, sub_y, featureIndex)
# 最终的树类似{'x2':{1:{x0:{...}}, 2:{}, 3:{}}}
return myTree
def fit(self, X, y):
# 类型检查
if isinstance(X, np.ndarray) and isinstance(y, np.ndarray):# ndarray对象是用于存放同类型元素的多维数组
pass
else:
try:
X = np.array(X)
y = np.array(y)
except:
raise TypeError("numpy.ndarray required for X,y")
featureIndex = tuple(['x' + str(i) for i in range(X.shape[1])])# featureIndex为('x0','x1',...,'xn')的tuple
self._tree = self._createTree(X, y, featureIndex)# 建立决策树，这里是用字典存储的
return self # allow chaining: clf.fit().predict()
def predict(self, X):
if self._tree == None:
raise NotFittedError("Estimator not fitted, call `fit` first")
# 类型检查
if isinstance(X, np.ndarray):
pass
else:
try:
X = np.array(X)
except:
raise TypeError("numpy.ndarray required for X")
def _classify(tree, sample):
"""
用训练好的决策树对输入数据分类
决策树的构建是一个递归的过程，用决策树分类也是一个递归的过程
_classify()一次只能对一个样本（sample）分类
To Do: 多个sample的预测怎样并行化？
"""
featIndex = tree.keys()[0]# featIndex是特征名，一个str
secondDict = tree[featIndex]# 在当前树中找到当前特征对应的可能值
key = sample[int(featIndex[1:])]# 得到要预测的sample对应特征的值，为key
valueOfkey = secondDict[key]# 找到对应key的value
if isinstance(valueOfkey, dict):# 如果这个value是一个字典，则可继续递归
label = _classify(valueOfkey, sample)
else:# 如果这个value是一个值，则到了叶子节点，对应的valueOfkey是要预测的标签
label = valueOfkey
return label
if len(X.shape) == 1:# 预测单条数据
return _classify(self._tree, X)
else:# 预测多条数据，循环调用_classify()
results = []
for i in range(X.shape[0]):
results.append(_classify(self._tree, X[i]))
return np.array(results)
原作者在github中说明了代码还存在几个问题：
(1) 如果测试集中某个样本的某个特征的值在训练集中没出现，则会造成训练出来的树的某个分支对该样本不能分类，出现KeyError。
(2)目前还不能对多个样本并行预测。
结尾
如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！
