限 时 特 惠： 本站每日持续稳定更新内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： muyang-0410
from
目录
决策树
我们经常使用决策树处理分类问题，它的过程类似二十个问题的游戏：参与游戏的一方在脑海里想某个事物，其他参与者向他提出问题，只允许提20个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小带猜测事物的范围。如图1所示的流程图就是一个决策树，长方形代表判断模块（ block），椭圆形代表终止模块（ block），表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作分支（），它可以到达另一个判断模块或终止模块。
图1构造了一个假象的邮件分类系统，它首先检测发送邮件域名地址。如果地址为.com，则将其放在分类”无聊时需要阅读的邮件”中。如果邮件不是来自这个域名，则检查内容是否包括单词曲棍球，如果包含则将邮件归类到”需要及时处理的朋友邮件”，否则将邮件归类到”无须阅读的垃圾邮件”。
图1 流程图形式的决策树
第2章介绍的k-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。
本章构造的决策树算法能够读取数据集合，构建类似图1的决策树。决策树可以在数据集合中提取出一系列规则，规则创建的过程就是机器学习的过程。现在我们已经大致了解决策树可以完成哪些任务，接下来我们将学习如何从一堆原始数据中构造决策树。首先我们讨论构造决策树的方法，以及如何编写构造树的代码；接着提出一些度量算法成功率的方法；最后使用递归建立分类器。
1. 决策树的构造
在构造决策树时，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征pickle.dump，划分出最好的结果，我们必须评估每个特征。我们假设已经根据一定的方法选取了待划分的特征，则原始数据集将根据这个特征被划分为几个数据子集。这数据子集会分布在决策点（关键特征）的所有分支上。如果某个分支下的数据属于同一类型，则无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要递归地重复划分数据子集的过程，直到每个数据子集内的数据类型相同。
创建分支的过程用伪代码表示如下：
检测数据集中的每个子项是否属于同一类型：
如果是，则返回类型标签
否则：
寻找划分数据集的最好特征
划分数据集
创建分支节点
对划分的每个数据子集：
递归调用本算法并添加返回结果到分支节点中
返回分支节点
决策树的一般流程：
收集数据：可以使用任何方法。
准备数据：树构造算法只适用于标称数据，因此数值型数据必须离散化。
分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
训练算法：构造树的数据结构。
测试算法：使用经验树计算错误率。
使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
一些决策树算法使用二分法划分数据，本书并不采用这种方法。如果依据某个属性划分数据将会产生4个可能的值，我们将把数据划分成四块，并创建四个不同的分支。
本书将使用ID3算法划分数据集，该算法处理如何划分数据集，何时停止划分数据集（进一步的信息可以参见）。每次划分数据集我们只选取一个特征属性，那么应该选择哪个特征作为划分的参考属性呢？
表1的数据包含5个海洋动物，特征包括：不浮出水面是否可以生存，以及是否有脚噗。我们可以将这些动物分成两类：鱼类和非鱼类。
表1 海洋生物数据
不浮出水面是否可以生存
是否有脚蹼
属于鱼类
是
是
是
是
是
是
是
否
否
否
是
否
否
是
否
1.1 信息增益
划分数据集的大原则是：将无序的数据变得更加有序。我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。我们可以在划分数据之前或之后使用信息论量化度量信息的内容。
在划分数据集之前之后信息发生的变化成为信息增益，我们可以计算每个特征划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
集合信息的度量方式成为香农熵或者简称为熵。
熵定义为信息的期望值。我们先确定信息的定义：
如果待分类的事务可能划分在多个分类之中，则符号xi”>xixi定义为：
l(xi)=−log2p(xi)”>l(xi)=−log2p(xi)l(xi)=−log2p(xi)
其中p(xi)”>p(xi)p(xi)是选择该分类的概率。
为了计算熵，我们需要计算所有类型所有可能值包含的信息的期望值，通过下面的公式得到：
H=−∑i=1np(xi)log2p(xi)”>H=−∑ni=1p(xi)log2p(xi)H=−∑i=1np(xi)log2p(xi)
其中n是分类的数目。
下面给出计算信息熵的函数，创建名为trees.py文件，添加如下代码：
10
11
12
13
14
15
():
=len()
={}
:
=[-1]
.keys():
[]=0
[]+=1
=0.0
:
prob=float([key])/
-=prob*log(prob,2)
代码说明：
在trees.py文件中，我们利用()函数得到一些样例数据：
():
=[[1,1,’yes’],
[1,1,’yes’],
[1,0,’no’],
[0,1,’no’],
[0,1,’no’]]
=[‘no ‘,”]
,
熵越高，则混合的数据也越多。得到熵之后，我们就可以按照获得最大信息增益的方法划分数据集。
另一个度量集合无序程度的方法是基尼不纯度（Gini ），简单地说就是从一个数据集中随机选取子项，度量其被错误分类到其他分组里的概率。
1.2 划分数据集
我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集市最好的划分方法。
添加划分数据集的代码：
(, axis, value):
=[]
:
[axis]==value:
=[:axis]
.([axis+1:])
.()
该函数使用了三个输入参数：带划分的数据集、划分数据集的特征、需要返回的特征的值。函数先选取数据集中第axis个特征值为value的数据，从这部分数据中去除第axis个特征，并返回。
测试这个函数，效果如下：
>>> myDat, =trees.()
>>> myDat
[[1,1,’yes’], [1,1,’yes’], [1,0,’no’], [0,1,’no’], [0,1,’no’]]
>>> trees.(myDat,0,1)
[[1,’yes’], [1,’yes’], [0,’no’]]
>>> trees.(myDat,0,0)
[[1,’no’], [1,’no’]]
接下来我们将遍历整个数据集，循环计算香农熵和()函数，找到最好的特征划分方式。
10
11
12
13
14
15
16
17
18
():
=len([0])-1
=()
=0.0
=-1
():
=[[i]]
=set()
=0.0
e:
=(, i, value)
prob=len()/float(len())
+=prob*()
=-
if( > ):
=
=i
注意数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签，而不是特征；保存了整个数据集的原始香农熵。
测试上面代码的实际输出结果：
>>> , =trees.()
>>> trees.plit(myDat)
函数选取了第一个特征用于划分。
1.3 递归构建决策树
构造决策树所需的子功能模块已经介绍完毕，构建决策树的算法流程如下：
得到原始数据集，
基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。
第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。我们可以采用递归的原则处理数据集。
递归结束的条件是，程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。
参加图2所示：
图2 划分数据集时的数据路径
添加下面的程序代码：
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
():
={}
:
t.keys(): [vote]=0
[vote]+=1
=(.(), key=.(1), =True)
nt[0][0]
(, ):
=[[-1]]
# 类型完全相同则停止继续划分
.count([0])==len():
[0]
# 遍历完所有特征时返回出现次数最多的
iflen([0])==1:
()
=plit()
=[]
={: {}}
del([])
# 得到列表包含的所有属性值
=[[]]
=set()
:
=[:]# 复制列表
[][value]=((, , value), )# 递归构造子树
函数统计列表中每个类型标签出现频率，返回出现次数最多的分类名称。
函数使用两个输入参数：数据集和标签列表。标签列表包含了数据集中所有特征的标签，算法本身并不需要这个变量，但是为了给出数据明确的含义，我们将它作为一个输入参数提供。上述代码首先创建了名为的列表变量，其中包含了数据集的所有类标签。列表变量包含了数据集的所有类标签。递归函数的第一个停止条件是所有类标签完全相同，则直接返回该类标签。递归函数的第二个停止条件是使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。这里使用函数挑选出现次数最多的类别作为返回值。
下一步程序开始创建树，这里直接使用的字典类型存储树的信息。字典变量存储树的所有信息。当前数据集选取的最好特征存储在变量中，得到列表中包含的所有属性值。
最后代码遍历当前选择特征包含的所有属性值，在每个数据集划分上递归待用函数()，得到的返回值将被插入到字典变量中，因此函数终止执行时，字典中将会嵌套很多代表叶子节点信息的字典数据。
注意其中的 = [:]复制了类标签，因为在递归调用函数中会改变标签列表的值。
测试这些函数：
>>> myDat, =trees.()
>>> =trees.(myDat, )
>>>
{‘no ‘: {0:’no’,1: {”: {0:’no’,1:’yes’}}}}
2. 测试和存储分类器
2.1 测试算法：使用决策树进行分类
依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于决策树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子结点；最后将测试数据定义为叶子结点所属的类型。
使用决策树分类的函数：
10
11
(, , ):
=.keys()[0]
=[]
=.index()
.keys():
[]==key:
([key]).==’dict’:
=([key], , )
else:
=[key]
测试上面的分类函数：
>>> myDat, =trees.()
>>> =trees.(myDat, [:])
>>> trees.(, , [1,0])
‘no’
>>> trees.(, , [1,1])
‘yes’
2.2 使用算法：决策树的存储
可以使用模块序列化对象，参见下面的程序。序列化对象可以在磁盘上保存对象，并在需要的时候读取出来。
10
(, ):
fw=open(,’w’)
.dump(, fw)
fw.close()
():
fr=open()
.load(fr)
3. 示例：使用决策树预测隐形眼镜类型
隐形眼镜数据集市非常著名的数据集，它包含很多患者眼部状态的观察条件以及医生推荐的因性眼睛类型。隐形眼镜类型包括硬材质、软材质以及不适合佩戴隐形眼镜。数据来源于UCI数据库，为了更容易显示数据，本书对数据做了简单的更改，数据存储在源代码下载路径的文本文件中。
在命令提示符中输入下列命令加载数据：
>>> fr=open(‘.txt’)
>>> =[inst.strip().split(‘t’).()]
>>> =[‘age’,”,”,”]
>>> =trees.(, )
>>>
决策树很好地匹配了实验数据，然而这些匹配选项可能太多了。我们将这种问题称之为过度匹配（）。为了减少过度匹配问题，我们可以裁剪决策树，去掉一些不必要的叶子结点。如果叶子结点只能增加少许信息，则可以删除该节点pickle.dump，将他并入到其他叶子结点中。第9章将进一步讨论这个问题。
第九章将学习另一个决策树构造算法CART，本章使用的算法成为ID3，它是一个好的算法但并不完美。ID3算法无法直接处理数值型数据，尽管我们可以通过量化的方法将数值型数据转化为标称型数据，但是如果存在太多的特征划分，ID3算法仍然会面临其他问题。
附录
1. 关于基尼不纯度（Gini ）的更多信息，请参考Pan-Ning Tan, Vipin Kumar and , to Data . (-, 2005), 158.
2. 隐形眼镜数据集：The is a of the from the UCI 3, 2001 []. The of the data is and was in “PRISM: An for rules,” in of Man- (1987), 27, 349-70. 本书使用的数据的下载链接在：[链接]。
限 时 特 惠： 本站每日持续稳定更新内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： muyang-0410
