机器学习(02)决策树

什么是决策树

你是否玩过二十个问题的游戏,游戏的规则很简单:参与游戏的一方在脑海里想某个事物,其他参与者向他提问题,只允许提20个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围。

决策树的工作原理与20个问题类似,用户输入一系列数据,然后给出游戏的答案。

决策树的概念非常简单。如下图就是一个决策树:

决策树图例

构造决策树能够读取数据集合,并从中提取出一系列规则。

专家系统中经常使用决策树,而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。

决策树的优缺点

优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。

缺点:可能会产生过渡匹配的问题。

使用数据类型:数值型和标称型。

决策树算法

实施决策树算法的步骤:

  • 1.收集数据

  • 2.处理数据,保证每条数据的最末尾的数据是当前类型。

  • 3.对多个可以划分的特征进行甄选,甄选的标准是保证通过甄选之后划分的结果的信息增益最大。划分的方式:按照当前甄选的特征进行划分。

比如影响是否是鱼类的类型的两个特征:不浮出水面是否可以生存,是否有脚蹼,若当前选择的特征“不浮出水面是否可以生存” 信息增益最大,那么将数据划分成:不浮出水面可以生存 和 不浮出水面不可以生存 两类数据。

  • 4.如果划分后的数据全是同一类型(即香浓熵为0),则不再划分,否则,继续递归调用第三步的方法。

分析

在构造决策树时,我们需要解决的第一个问题就是,当数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征,划分出最好的结果,我们必须评估每个特征

完成测试之后,原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。

如果某个分支下的数据属于同一类型,则当前分支下数据已经正确地划分,无需进行进一步对数据集进行分割。如果分支下的数据不属于同一类型,则需要重复划分数据子集,直到所有具有相同类型的数据均在一个数据子集内

伪代码实现:

1
2
3
4
5
6
7
8
9
10
检测数据集中的每个子项是否属于同一分类
If so return 类标签;
Else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
# 递归调用函数createBranch
调用函数createBranch并增加返回结果到分支节点中
return 分支节点

核心算法介绍

划分算法

主要参考ID3算法,每次划分数据集时只选取一个特征属性:

http://en.wikipedia.org/wiki/ID3_algorithm

香浓熵

克劳德·香农
克劳德·香农被公认为是二十世纪最聪明的人之一,威廉·庞德斯通在其2005年出版的《财富公式》一书中是这样描写克劳德·香农的:

“贝尔实验室和MIT有很多人将香农和爱因斯坦相提并论,而其他人则认为这种对比是不公平的--对香农是不公平的。”

划分数据集的大原则是:将无需的数据变得更加有序。组织杂乱无章的数据的一种方法就是使用信息论度量信息,信息论是量化处理信息的分支学科。

在划分数据前后信息发生的变化称为信息增益。

定义为信息的期望值,首先我们需要知道信息的定义。如果待分类的事务可能划分在多个分类之中,则符号$x_i$的信息定义为:

$$l(n_i) = -log_2p(x_i)$$

其中$p(x_i)$是选择该分类的概率。

为了计算,我们需要计算所有类别所有可能值包含的信息期望值,通过下面公式得到:

$$H = -\sum_{i=1}^np(x_i)log_2p(x_i)$$

其中n是分类的数目。

说这么多,不如举个栗子来的实在

接下来我们对下列数据通过决策树来进行分析:

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

上代码

对数据进行分类时,我们首先要思考按照哪一个特征分类。这里我们需要分别计算分别按照两个特征进行分类之后的香浓熵,与分类之前的香浓熵进行对比,选取差值最大的(即为信息增益最大的)结果作为分类标准。

模拟获取数据,注意数据的最末尾是当前数据的类型

1
2
3
4
5
6
7
8
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

传说中香农熵的计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

对数据进行分割:

1
2
3
4
5
6
7
8
9
10
11
# dataSet:传入数据
# axis:要进行切割的特征下标
# value:用来切割的特征值
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

甄选最适合划分的特征:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def chooseBestFeatureToSplit(dataSet):
# 获取每组数据除去分类标签的数据长度
numFeatures = len(dataSet[0]) - 1
# 计算数据的基础的shannon熵
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
print(dataSet)
print("------" + str(numFeatures))
# 遍历每一列标签
for i in range(numFeatures):
# 获取每一种标签下的对应的数据
featList = [example[i] for example in dataSet]
print featList
uniqueVals = set(featList)
newEntropy = 0.0
# 遍历并按照分类分割这一列下的数据 并计算分割后的shannone熵
for value in uniqueVals:
subDataSet = splitDataSet(dataSet,i,value)
prob = len(subDataSet)/float(len(dataSet))
print("shannone:" + str(calcShannonEnt(subDataSet)))
newEntropy += prob * calcShannonEnt(subDataSet)
# 之前基本的shannone熵 减去 分割后的数据的shannone熵 算出前后差值 差值越大,代表后面的分类中,分得的数据混杂项越少
infoGain = baseEntropy - newEntropy
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return bestFeature

执行结果:

1
2
3
>>> myDat,labels=createDataSet()
>>> chooseBestFeatureToSplit(myDat)
0

得到最好的分类是第0个特征。

坚持原创技术分享,您的支持将鼓励我继续创作!