决策树算法
一、基本原理
决策树类似于二叉树结构,按照数据集中的特征依次对其分类,直到所有的数据分类完毕。
首先在已知数据集上确定哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征,划分出最好的结果,必须要评估每个特征。此时,原始数据集就会被划分为几个子数据集分支。如果某个分支下的数据都属于同一类型,即该子集中的所有数据的特性均相同,则无需进一步对数据集进行划分。否则需要重复划分数据子集,直到所有具有相同类型的数据均在一个数据子集内。
构造决策树最关键的是如何找到决定性的特征。是否划分的原则为子数据集中的所有数据是否均具有相同的特征。
二、算法实现
伪代码函数decisionTree():
检测数据集中每个子项是否属于同一类:
IF so
return 类标签
Else
寻找划分数据集的最好特性
划分数据集
创建分支节点
for 每个划分的子集
调用函数decisionTree()并将结果增加到分支节点中
return 分支节点
信息增益
在划分数据集之前之后信息发生的变化称为信息增益。获得信息增益最高的特征就是最好的分类选择。计算信息增益常用的是香农熵(熵)。熵的定义为信息的期望值,表示数据的无序性。其计算公式为:
python程序:1
2
3
4
5
6
7
8
9
10
11
12
13
14from 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
程序说明:
函数的输入为原始数据集,其中最后一列为分类标签。首先计算数据集的总个数,其次将数据集按照分类标签分类,并统计每个子类的总数。最后根据熵的计算公式,依次对每类的信息增益进行求和。
例:有一组已知分类标签的数据集,计算其香农熵。
利用python创建数据集:1
2
3
4def createDataSet():
dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
labels = ['no surfacing', 'flippers']
return dataSet, labels
根据公式其香农熵为:
数据集一共有5组数据,其中分类标签为’yes’的有3个,分类标签为’no’的有2个。熵越高,则混合的数据也越多。
划分数据集
除了计算整体数据的信息熵,还需要计算划分数据集的熵。对每个特征划分数据集的结果计算一次信息熵,然后判断按照哪个特征划分数据集是最好的划分方式。其计算公式为:
首先按照每个特征划分数据集:
python程序:1
2
3
4
5
6
7
8def 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
程序说明:
函数的三个输入分别为:待划分的数据集,数据集中的某个特征,该特征对应的特征值。例如splitDataSet(dataSet, 0, 1)表示划分出数据集dataSet中第0个特征为1的数据,即第1个特征为1的数据,python的列表索引从0开始。(dataSet即createDataSet()函数生成的数据集)
首先利用for循环遍历整个数据集,当对应的特征等于给定的值后,先将该特征之前的数据添加到列表中,然后将之后的数据添加到列表中。
splitDataSet(dataSet, 0, 1)的返回值为:[[1,’yes’], [1, ‘yes’], [0, ‘no’]]
对每个特征划分完成后,需要计算每个数据子集的熵,从而选择最好的数据集划分方式。
python程序:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 # 减去数据集中的标签
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet] # 获得数据集中某一列的值
uniqueVals = set(featList) # set():使数据为不重复的序列
newEntropy = 0.0
# 划分数据集,代入公式
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
# 计算最大的熵,作为划分数据集的方式
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
程序说明:
函数首先计算总的数据集的熵,然后将最好的熵和特征初始化为0和-1。然后需要将划分数据集,计算每个子集的熵,但首先要知道数据集中每个特征有多少特征值。函数首先获得每一个特征的所有特征值,然后利用set()将重复的值去掉。featList返回的就是每个特征对的所有特征值。createDataSet()生成的数据集的featList为:[1, 1, 1, 0, 0]和[1, 1, 0, 1, 1]。最后,对于划分好的每个数据集依次计算熵,并选择最大的熵作为最好的划分方式。
H(1)、H(2)分别表示第1,2种分类结果,数据集中特征0,即第1个特征的分类结果为1和0。其中结果为1的数据集为:[[1,’yes’], [1, ‘yes’], [0, ‘no’]],’yes’有2个,’no’有1个;结果为0的数据集为:[[1, ‘no’],[1, ‘no’]],’yes’有0个,’no’有2个。特征1的计算类似。
构建决策树
划分好一次数据集之后,数据将被向下传递到下一个节点,然后在此节点上做进一步的划分。因此可用递归的原则处理原始数据集。
递归的结束条件为:遍历完原始数据集的所有数据或者每个子集的数据特征均相同。
python程序实现:
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
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]
程序说明:
函数的输入参数为原始数据集和分类标签。首先判断该数据集是否能进行划分。其递归结束的条件有2个,一个是划分后的数据子集的所有特征属性均相同。即数据集中第一个特征的个数即该数据集的总特征个数。另一个是当遍历完所有的原始数据集的特征之后,仍然存在没有划分成包含唯一类别的子类,这时候采用出现出现次数最多的类别作为其返回值。然后计算数据集中的熵并选择最好的分类特征,再将此特征删除,得到数据子集,再依次对子集进行递归处理,直到分类完成。
该程序最终的结果为:{‘no surfacing’: {0: ‘no’, 1: {‘flippers’: {0: ‘no’, 1: ‘yes’}}}}。即首先根据“不浮在水面是否可以生存”的特征分成“0”(否)和“1”(是)两类。其中“0”这一类的子数据集的特征均相同,不需要在划分。而“1”这一类再按照“是否有脚蹼”继续分类。
三、感悟
3.1 python知识
(1)extend和append的区别:
extend:将一个序列添加到列表中;
append:将一个对象添加到列表中;
即append是将要添加的数据作为一个新的对象添加到列表中,不属于原来的列表,而extend添加后的数据仍然属于原来的列表。
例:a = [1, 2], b = [3]
a.extend(b) : [1, 2, 3]
a.append(b) : [1, 3, [3]]
(2)set():使数据为不重复的序列
3.2 算法
(1)决策树属于有监督的算法。因为其原始数据集的分类标签是已知的。
(2)决策树类似于二叉数,将原始数据集按照每个特征的标签依次划分,直到所有的数据划分完成。
(3)构建决策树主要分为两步,首先选择最好的划分类别,将原始数据集分成子数据集,其次判断递归的结束条件是否满足,即需不需要继续往下划分。
(4)选择最好的划分类别时,常用的判断依据是计算每个特征的子数据集的熵,熵代表的是数据集的混乱程度,数据越混乱,熵越高,其分类标准也越好。