决策树

分类决策树模型是一种描述对实例进行分类的树形结构,决策树由结点和有向边组成,结点有两种类型:内部结点和叶结点。内部结点表示一个特征或属性,叶结点表示一个类。
用决策树分类,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点;这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点。最后将实例分到叶结点的类中。决策树学习的目的是为了产生一个泛化能力强,即处理未见示例能力强的决策树,其基本流程遵循简单且直观的分而治之(divide-and-conquer)策略。

决策树的构造

在构造决策树时,我们需要解决的第一个问题就是,当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征,划分出最好的结果,我们必须评估每个特征。完成测试之后,原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型,则已正确地划分数据分类。
下面我们将用ID3算法划分数据集(还有C4.5算法和CART算法,这里先不讨论)。每次划分数据集时我们只选取一个特征属性,那么就需要知道选哪些特征作为划分的参考属性。
下表中有5个海洋动物,特征包括不浮出水面是否可以生存,是否有脚蹼。我们可以将这些动物分成两类:鱼类和非鱼类。要决定用第一个特征还是第二个特征划分数据,需要用到量化的方法——信息增益

序号 不浮出水面可以生存 有脚蹼 属于鱼类
1
2
3
4
5

信息增益

划分数据集的大原则是:将无序的数据变得更加有序。在划分数据集前后信息发生的变化称为信息增益(information gain),可以计算每个特征值划分数据集获得的信息增益,信息增益越大,说明划分之后的信息熵越小,即数据更加有序。所以信息增益最高的特征就是我们要选择的。
信息论中度量信息的方式称为熵(entropy),熵定义为信息的期望值。假定当前样本集合\(D\)中第\(i\)类样本所占的比例为\(p_i\)(i = 1,2,…,n),则\(D\)的信息熵定义为

\[ H(D) = -\sum_{i=1}^n p_i log_2 p_i \]

\(H(D)\)的值越小,则\(D\)越有序。
假定离散属性\(a\)\(K\)个可能的取值{\(a^1,a^2,...,a^K\)},用\(a\)对样本集\(D\)进行划分,则会产生\(K\)个分支结点,其中第\(k\)个分支结点包含了\(D\)中所有属性\(a\)的属性值为\(a^k\)的样本,记为\(D^k\)。根据上面信息熵公式可以算出\(H(D^k)\),再考虑到各个分支所包含的样本数不同,给其赋予权重\(|D^v|/|D|\),于是可以计算出属性\(a\)对样本集\(D\)进行划分的信息增益:

\[ G(D,a) = H(D)-\sum_{k=1}^K \frac{|D^k|}{|D|} H(D^k) \]

划分数据集

下面用Python来计算信息熵,创建trees.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from math import log

def calcShannonEnt(dataSet):
numEntries = len(dataSet) # 计算信息数目
labelCounts = {}
# 将信息保存到字典中
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
# 计算每种类别的概率
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob * log(prob, 2)
return shannonEnt

接下来在trees.py中创建简单鱼鉴定数据集:

1
2
3
4
5
6
7
8
9
10
11
12
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing', 'flippers']
return dataSet, labels

myDat, labels = createDataSet()
print myDat
print calcShannonEnt(myDat)

运行结果:

1
2
3
$ python trees.py
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
0.970950594455

可以在数据集中添加数据来观察信息熵的变化情况。
另一种度量集合无需程序的方法是基尼不纯度(Gini impurity),简单地说就是从一个数据集中随机选取子项,度量其被错误分类到其他分组里的概率。本文对基尼不纯度也先不讨论。
接下来我们将对每个特征划分数据集的结果计算一次信息熵,然后判断按照哪个特征划分是最好的。

1
2
3
4
5
6
7
8
9
10
11
12
# 按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
# 去掉给定特征,重新构建数据集
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet

print splitDataSet(myDat, 0, 1)

运行结果:

1
2
3
4
$ python trees.py
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
0.970950594455
[[1, 'yes'], [1, 'yes'], [0, 'no']]

下面我们遍历整个数据集,计算按各个特征划分数据集的信息增益,找到最好的特征划分方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def chooseBestFeatureToSplit(dataSet):
# 计算共有多少个特征
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
# 遍历所有的特征
for i in range (numFeatures):
# 特征i有哪些值
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 0.0
# 遍历所有的特征值
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
# 计算按特征i划分后各分支的权重
prob = len(subDataSet) / float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature

print chooseBestFeatureToSplit(myDat)

运行结果:

1
2
3
4
5
$ python trees.py
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
0.970950594455
[[1, 'yes'], [1, 'yes'], [0, 'no']]
0

递归构建决策树

构建决策树的流程是:获得原始数据集,然后基于最好的特征划分数据集,第一次划分之后,数据将被向下传递到树分支的下一个结点,下一个结点再次划分数据,因此可以采用递归方式。
递归结束的条件是:程序遍历完所有划分数据集的特征,或者每个分支下的所有实例都具有相同的分类。
如果数据集已经处理了所有属性,但是类标签依然不是唯一的,此时我们需要采用多数表决的方法决定该叶子结点的分类。

1
2
3
4
5
6
7
8
import operator
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys(): classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]

创建决策树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
# 类别完全相同则停止继续划分
if classList.count(classList[0]) == len(classList):
return classList[0]
# 遍历完所有特征,返回出现最多的类
if len(dataSet[0]) == 1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree

print createTree(myDat, labels)

运行结果:

1
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

决策树最终以嵌套字典的方式表示,最左边是第一个划分特征,不浮出水面,0表示不是鱼类,1再以脚蹼划分。这棵树包含了3个叶子结点和2个判断结点。

reference
《机器学习实战》
《机器学习》
http://atlantic8.github.io/2017/03/02/Decision-Tree/