今天我们来介绍一种机器学习中的经典算法——决策树（DTrees）。在机器学习中算法可分为监督学习，非监督学习，半监督学习和强化学习。而决策树算法就是一种典型的监督学习算法。它既可以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林等。
顾名思义，我们认为决策树就是根据数据集的属性构建树模型来帮助我们做出决断。事实上，拿我们最近的例子来说，我们写代码时经常会不停的敲if,else if,else，其实这就是在用决策树的思想了。只是我们往往不会去考虑，有这么多条件，用哪个条件特征先做if，哪个后做if比较优呢？谁先谁后的这个准确的定量选择标准就是我们今天研究的决策树算法的核心思想了。
决策树目前有三个常见的算法:ID3,C4.5,CART。这一篇我们主要讨论ID3和C4.5算法，而CART作为优化版决策树算法用到了机器学习库中的sklearn，放到下篇讨论。
首先我们需要储备一些基础理论知识。
-
信息熵
关于熵的概念我们并不陌生，热力学中的熵通过分子的运动状态描述体系的混乱程度。将熵用到信息学中同样可以反映信源的混乱程度，或者说不确定程度，如一个数据集U中的样本都属于同一类，那么这时样本纯度最高而凌乱程度最低，可以认为熵值为0。举个例子，我现在想买一部iphone8，如果我去苹果专卖店很容易就能找到，而如果我去手机大卖场，里面有三星，oppo，小米，苹果等各种手机，这个时候我找起来就没那么容易了吧。在这个例子中，苹果专卖店的熵值就低于手机大卖场的熵值。
当一个体系中有多个属性类别时，我们可以根据如下公式计算出整体的信息熵：
其中pk是每个属性出现的概率，D表示样本集合，|y|是样本中类别的数目。由于概率是在0~1之间对数为负，所以整体加一个负号。
-
信息增益
它是指使用某一个属性a进行划分后，所带来的纯度提高的大小，也就是熵值下降了多少。信息增益越大，纯度提升越大，说明这个分类属性越好。
即信息增益 = 根节点的信息熵 - 所有分支节点的信息熵的加权和。
以打球为例，已知在历史数据中（14天）有9天打球，5天不打球，所以此时的熵应为：
基于天气划分：
Outlook=sunny：熵值为0.971（两天打球，三天不打球）
Outlook=rainy：熵值为0.971（两天打球，三天不打球）
Outlook=overcast：熵值为0（四天全部打球）
根据数据统计，Outlook取值分别为sunny,overcast,rainy的概率分别为：5/14，4/14，5/14
熵值计算：5/14 * 0.971+4/14 * 0+5/14 * 0.971=0.693
信息增益：系统的熵值从原始的0.940下降到了0.693，增益为0.247。
同样的方式可以计算出其他特征的信息增益。 -
信息增益率
信息增益率为信息增益与该特征的信息熵之比：
当样本集中的某一属性取值使得所有样本被分到不同类别，此时分支的纯度达到最高，无需再继续划分。然而这样的决策树不具备泛化能力。这就是ID3算法（信息增益准则）没有考虑到的问题，事实上，信息增益准则对可取值较多的属性有所偏好，这是因为特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低。
属性A的可能取值越大，固有值IV(a)通常越大。
- 基尼值
基尼值 Gini(D) 反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。当数据集的纯度越高，每次抽到不同类别标记的概率越小。打个比方，在一个袋子里装100个乒乓球，其中有99个白球，1个黄球，那么当我们随机抽取两个球的时候，很大概率是抽到两个白球。
所以数据集D的纯度可以用基尼值来度量，其定义如下：
基尼值越小，数据集D纯度越高。
ID3
了解了基本理论，接下来看一下ID3算法的实现过程。
ID3算法是以信息熵为度量，用于决策树节点的属性选择，每次优选信息量最多的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0，此时每个叶子节点对应的实例集中的实例属于同一类。
- 首先要做数据处理，按照一定的格式创建数据集，理清属性和标签类别
- 第二步就是最优特征选取，即每次都选择信息增益最大的特征（递归实现），计算信息熵和信息增益
- 第三步递归创建决策树，每一次计算都要去掉上一步已经选出来的那个属性。需要注意的是递归结束的两个条件：（1）所有类标签都相同也就是都属于一类时，直接返回该类标签，划分完毕（2）当数据集样本只有一列（类标签）也就是所有特征都使用完了仍然不能将数据划分为仅包含唯一类别的分组，特征不够用，这时采用投票机制，即选取数量最多的类别作为返回值。
- 第四步进行可视化展示。需要用到Graphviz工具和机器学习库sklearn的相关包和函数，
具体实现过程如下（一个简单的数据集）：
#coding=utf-8
from math import log
import pandas as pd
import numpy as np
# 数据集种类越多越复杂熵越大
# 创建数据集 （返回DataFrame）
def createdata():
data = pd.DataFrame(
{'water': [1, 1, 1, 0, 0],
'feet': [1, 1, 0, 1, 1],
'survive': ['yes', 'yes', 'no', 'no', 'no']})
return data
# 计算香农熵 （DataFrame）
def calculateshang(data):
names = data[data.columns[-1]] # 依据公式求某列特征的熵 目标变量作为概率依据
n = len(names)
labels = {}
for i, j in names.value_counts().items():
labels[i] = j
shang = 0
for i in labels: # 利用循环求熵
pi = labels[i] / n
shang -= pi * log(pi, 2.0)
return shang
# 划分数据集 （DataFrame,特征列名,该列某个特征值）
def splitdataSet(data, feature, feature_value):
recvdata = []
n = len(data)
for i in range(n): # 如果该行的这个特征值==循环到的这个特征值，去掉该特征加入返回列表
if (data.iloc[[i], :][feature].values[0] == feature_value):
temp = data.iloc[[i], :]
k = temp.index.values[0]
temp_t = temp.loc[k]
tem = temp_t.drop(feature)
recvdata.append(tem)
recvDF = pd.DataFrame(recvdata) # 将满足条件的所有行定义为DataFrame
return recvDF
# 得出最好的特征名，用来划分数据集 （DataFrame）
def choosebestfeaturetosplit(data):
nameFeatures = data.columns
baseEntropy = calculateshang(data) # 基础最大原始香农熵
bestinfoGain = 0.0 # 初始化最好信息增益
bestFeature = -1 # 初始化最好的特征名
for Feature in nameFeatures[:-1]: # 循环所有特征
uniquevalue = set(data[Feature]) # 该特征的所有唯一值
newEntropy = 0.0 # 中间熵
for value in uniquevalue:
subdata = splitdataSet(data, Feature, value)
pi = len(subdata) / len(data)
newEntropy += pi * calculateshang(subdata)
infoGain = baseEntropy - newEntropy # 中间信息增益
if (infoGain > bestinfoGain):
bestinfoGain = infoGain
bestFeature = Feature # 循环比较所有特征，返回信息增益最大的特征列名
return bestFeature
# 若创建数结束后目标变量仍不唯一，则以最多的一类为准 (Series)
def major_k(classlist):
classcount = classlist.value_counts()
result = classcount.sort_values(ascending=False).index[0]
return result
# 建立决策树 （DataFrame）（返回dict）： {'water': {0: 'no', 1: {'food': {0: 'no', 1: 'yes'}}}}
def createtree(data):
labels = data.columns
classlist = data[labels[-1]]
if (len(classlist.values) == classlist.value_counts()[0]): # 结束条件1：该分支目标变量唯一
return classlist.values[0]
if (len(labels) == 1): # 结束条件2：所有特征名都循环完了
return major_k(classlist) # 这里并不能直接返回目标变量名，可能不唯一，所以调用major_k
bestFeature = choosebestfeaturetosplit(data)
myTree = {bestFeature: {}} # 这里很巧妙，以此来创建嵌套字典
unique = set(data[bestFeature])
for value in unique:
myTree[bestFeature][value] = createtree(splitdataSet(data, bestFeature, value)) # 递归创建树
return myTree
# 分类器预测 （嵌套字典 列表特征名 列表测试数据）
def classfiy(myTree, labels, test):
firstStr = list(myTree.keys())[0] # 需要获取首个特征的列号，以便从测试数据中取值比较
secondDict = myTree[firstStr] # 获得第二个字典
featIndex = labels.index(firstStr) # 获取测试集对应特征数值
for key in secondDict.keys():
if (test[featIndex] == key):
if (type(secondDict[key]).__name__ == 'dict'): # 判断该值是否还是字典，如果是，则继续递归
classlabel = classfiy(secondDict[key], labels, test)
else:
classlabel = secondDict[key]
return classlabel
# 画决策树pdf图 （DataFrame）
def showtree_pdf(data):
from sklearn import tree # 导入sklearn的决策树模型（包括分类和回归两种）
import pydotplus # 画句子的依存结构树
a = data.iloc[:, :-1] # 特征矩阵
b = data.iloc[:, -1] # 目标变量
clf = tree.DecisionTreeClassifier() # 分类决策树
clf.fit(a, b)
dot_data = tree.export_graphviz(clf, out_file=None) # 利用export_graphviz将树导出为Graphviz格式
graph = pydotplus.graph_from_dot_data(dot_data)
graph.write_pdf("dtrees.pdf") # 保存树图dtrees.pdf到本地
if __name__ == "__main__":
data = createdata() # 创建数据集
myTree = createtree(data) # 创建嵌套字典树
print(myTree)
result = classfiy(myTree, list(data.columns), [1, 0]) # 预测测试数据
print(result)
showtree_pdf(data) #画pdf图
一起来看看最终的预测结果和生成的决策树吧：
怎么样，是不是很有意思呢？那就试着动手做一下吧~
ID3算法最大的特点就是构建方式简单易懂，构建速度快，但是作为初期的版本还是几个问题没有考虑到：
- 不能处理连续特征
- 第二个就是用信息增益作为标准容易偏向于取值较多的特征
- 第三个是缺失值处理的问题
- 过拟合问题
C4.5
因此，在ID3算法思想的基础上，又有了C4.5算法。相比于ID3算法，C4.5算法做了如下的改进：
-
对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为a1,a2,...,am,则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示为：Ti=（ai+ai+1）/2。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为at,则小于at的值为类别1，大于at的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
-
对于第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比的变量Gain_Radio(X,Y)，它是信息增益和特征熵的比值，即信息增益率。特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。
-
对于第三个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。
（1）C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2. 然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。
（2）可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。
-
对于第4个问题，C4.5引入了正则化系数进行初步的剪枝。具体方法这里不讨论。下篇讲CART的时候会详细讨论剪枝的思路。
与此同时C4.5算法还是有它的缺点和不足：
-
由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。后面在下篇讲CART树的时候我们会专门讲决策树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。
-
C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
-
C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
-
C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。
这4个问题在CART树里面部分加以了改进。在普通的决策树算法里，CART算法算是比较优的算法了。scikit-learn的决策树使用的也是CART算法。下篇将会详细介绍关于CART算法。
网友评论