©2016-2024 Matools All rights reserved,
粤ICP备17059708号
前面介绍的SVM方法中都是针对样本特征为数量特征的，但是在实际生活中，还有一些非数值特征的问题，如何进行解决呢？非数值特征具有离散，无法比较大小，无法比较相似性，只能比较相同或者不相同的特点。为了解决这个问题，可以采用把特征转化为实数特征，但是这样做可能会损失一部分数据特征，也会加入一些人为的因素，因为我们无法完全用实数描述特征；还可以采用非数值特征分类，比如列出所有的属性来代替实数向量，比如樱桃信息为{红色，小，圆形，甜}，但是我们如何用这些非数值特征进行分类呢？
一、决策树构造
在这里引出了本文想要介绍的一种方法：决策树。
1.1 介绍决策树
决策树（decision tree）：是一种基本的分类与回归方法，此处主要讨论分类的决策树。
其中每一个内部节点代表一个属性，每一个分支代表了相应属性的值，每一个叶节点代表了分类结果。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。（我们以ID3算法为例）
1） 开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
2） 如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。
4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。
举个例子：假如我们已经选择了一个分裂的属性，那怎样对数据进行分裂呢？
1、
分裂属性的数据类型分为离散型和连续性两种情况，对于离散型的数据，按照属性值进行分裂，每个属性值对应一个分裂节点；对于连续性属性，一般性的做法是对数据按照该属性进行排序，再将数据分成若干区间，如[0,10]、[10,20]、[20,30]…，一个区间对应一个节点，若数据的属性值落入某一区间则该数据就属于其对应的节点。
例：
表1.1 分类信息表
职业
年龄
是否贷款
白领
30
否
工人
40
否
工人
20
否
学生
15
否
学生
18
是
白领
42
是
（1）属性1“职业”是离散型变量，有三个取值，分别为白领、工人和学生，根据三个取值对原始的数据进行分割，如下表所示:
表1.2 属性1数据分割表
取值
贷款
不贷款
白领
1
1
工人
0
2
学生
1
1
表1.2可以表示成如下的决策树结构：
（2）属性2是连续性变量，这里将数据分成三个区间，分别是[10，20]、[20,30]、[30,40]，则每一个区间的分裂结果如下：
属性1.3 数据分割表
区间
贷款
不贷款
[0,20]
1
2
(20,40]
0
2
(40,—]
1
0
表1.3可以表示成如下的决策树结构：
1.2、分裂属性的选择
我们知道了分裂属性是如何对数据进行分割的，那么我们怎样选择分裂的属性呢？
决策树采用贪婪思想进行分裂，即选择可以得到最优分裂结果的属性进行分裂。那么怎样才算是最优的分裂结果？最理想的情况当然是能找到一个属性刚好能够将不同类别分开，但是大多数情况下分裂很难一步到位，我们希望每一次分裂之后孩子节点的数据尽量”纯”，以下图为例：
从图1.1和图1
.2可以明显看出，属性2分裂后的孩子节点比属性1分裂后的孩子节点更纯：属性1分裂后每个节点的两类的数量还是相同，跟根节点的分类结果相比完全没有提高；按照属性2分裂后每个节点各类的数量相差比较大，可以很大概率认为第一个孩子节点的输出结果为类1，第2个孩子节点的输出结果为2。
选择分裂属性是要找出能够使所有孩子节点数据最纯的属性，决策树使用信息增益或者信息增益率作为选择属性的依据。
* 信息增益
用信息增益表示分裂前后跟的数据复杂度和分裂节点数据复杂度的变化值，计算公式表示为：
其中Gain表示节点的复杂度，Gain越高，说明复杂度越高。信息增益说白了就是分裂前的数据复杂度减去孩子节点的数据复杂度的和，信息增益越大，分裂后的复杂度减小得越多，分类的效果越明显。
节点的复杂度可以用以下两种不同的计算方式：
1）熵
熵描述了数据的混乱程度，熵越大，混乱程度越高，也就是纯度越低；反之，熵越小，混乱程度越低，纯度越高。 熵的计算公式如下所示：
其中Pi表示类i的数量占比。以二分类问题为例，如果两类的数量相同，此时分类节点的纯度最低，熵等于1；如果节点的数据属于同一类时，此时节点的纯度最高，熵等于0。
举例代码如下：
from math import log """ 函数说明：创建测试数据集 Parameters：无 Returns： dataSet：数据集
labels：分类属性 """ def creatDataSet(): # 数据集 dataSet=[[0, 0, 0, 0,
'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'],
[0, 1, 1, 0, 'yes'], [0, 0, 0, 0, 'no'],
[1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1,
1, 1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2,
'yes'], [2, 0, 1, 2, 'yes'], [2, 0, 1, 1, 'yes'],
[2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'],
[2, 0, 0, 0, 'no']] #分类属性
labels=['年龄','有工作','有自己的房子','信贷情况'] #返回数据集和分类属性 return
dataSet,labels """ 函数说明：计算给定数据集的经验熵（香农熵） Parameters： dataSet：数据集 Returns：
shannonEnt：经验熵 """ def calcShannonEnt(dataSet): #返回数据集行数
numEntries=len(dataSet) #保存每个标签（label）出现次数的字典 labelCounts={}
#对每组特征向量进行统计 for featVec in dataSet: currentLabel=featVec[-1]
#提取标签信息 if currentLabel not in labelCounts.keys():
#如果标签没有放入统计次数的字典，添加进去 labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 #label计数
shannonEnt=0.0 #经验熵 #计算经验熵 for
key in labelCounts: prob=float(labelCounts[key])/numEntries
#选择该标签的概率 shannonEnt-=prob*log(prob,2) #利用公式计算
return shannonEnt #返回经验熵 #main函数 if
__name__=='__main__': dataSet,features=creatDataSet()
print("该数据集的经验熵为：%.3f" % (calcShannonEnt(dataSet)))
结果如下：
b）基尼值
基尼值计算公式如下：
其中Pi表示类i的数量占比。其同样以上述熵的二分类例子为例，当两类数量相等时，基尼值等于0.5 ；当节点数据属于同一类时，基尼值等于0 。基尼值越大，数据越不纯。
以熵作为节点复杂度的统计量，分别求出下面例子的信息增益，图3.1表示节点选择属性1进行分裂的结果，图3.2表示节点选择属性2进行分裂的结果，通过计算两个属性分裂后的信息增益，选择最优的分裂属性。
属性1：
属性2：
由于 ，所以属性1与属性2相比是更优的分裂属性，故选择属性1作为分裂的属性。
1.3、信息增益率
使用信息增益作为选择分裂的条件有一个不可避免的缺点：倾向选择分支比较多的属性进行分裂。为了解决这个问题，引入了信息增益率这个概念。信息增益率是在信息增益的基础上除以分裂节点数据量的信息增益（听起来很拗口），其计算公式如下：
其中 表示信息增益， 表示分裂子节点数据量的信息增益，其计算公式为：
其中m表示子节点的数量，表示第i个子节点的数据量，N表示父节点数据量，说白了， 其实是分裂节点的熵，如果节点的数据链越接近，越大，如果子节点越大，
越大，而就会越小，能够降低节点分裂时选择子节点多的分裂属性的倾向性。信息增益率越高，说明分裂的效果越好。
还是信息增益中提及的例子为例：
属性1的信息增益率：
属性2的信息增益率：
由于 ，故选择属性2作为分裂的属性。
代码演示如下：
from math import log """ 函数说明：创建测试数据集 Parameters：无 Returns： dataSet：数据集
labels：分类属性 """ def creatDataSet(): # 数据集 dataSet=[[0, 0, 0, 0,
'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'],
[0, 1, 1, 0, 'yes'], [0, 0, 0, 0, 'no'],
[1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1,
1, 1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2,
'yes'], [2, 0, 1, 2, 'yes'], [2, 0, 1, 1, 'yes'],
[2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'],
[2, 0, 0, 0, 'no']] #分类属性
labels=['年龄','有工作','有自己的房子','信贷情况'] #返回数据集和分类属性 return
dataSet,labels """ 函数说明：计算给定数据集的经验熵（香农熵） Parameters： dataSet：数据集 Returns：
shannonEnt：经验熵 """ def calcShannonEnt(dataSet): #返回数据集行数
numEntries=len(dataSet) #保存每个标签（label）出现次数的字典 labelCounts={}
#对每组特征向量进行统计 for featVec in dataSet: currentLabel=featVec[-1]
#提取标签信息 if currentLabel not in labelCounts.keys():
#如果标签没有放入统计次数的字典，添加进去 labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 #label计数 shannonEnt=0.0
#经验熵 #计算经验熵 for key in labelCounts:
prob=float(labelCounts[key])/numEntries #选择该标签的概率
shannonEnt-=prob*log(prob,2) #利用公式计算 return shannonEnt
#返回经验熵 """ 函数说明：信息增益最大特征的索引值 Parameters： dataSet：数据集
Returns： shannonEnt：信息增益最大特征的索引值 """ def chooseBestFeatureToSplit(dataSet):
#特征数量 numFeatures = len(dataSet[0]) - 1 #计数数据集的香农熵 baseEntropy =
calcShannonEnt(dataSet) #信息增益 bestInfoGain = 0.0 #最优特征的索引值
bestFeature = -1 #遍历所有特征 for i in range(numFeatures): #
获取dataSet的第i个所有特征 featList = [example[i] for example in dataSet]
#创建set集合{}，元素不可重复 uniqueVals = set(featList) #经验条件熵
newEntropy = 0.0 #计算信息增益 for value in uniqueVals:
#subDataSet划分后的子集 subDataSet = splitDataSet(dataSet, i,
value) #计算子集的概率 prob = len(subDataSet) /
float(len(dataSet)) #根据公式计算经验条件熵 newEntropy += prob *
calcShannonEnt((subDataSet)) #信息增益 infoGain = baseEntropy -
newEntropy #打印每个特征的信息增益 print("第%d个特征的增益为%.3f" % (i, infoGain))
#计算信息增益 if (infoGain > bestInfoGain):
#更新信息增益，找到最大的信息增益 bestInfoGain = infoGain
#记录信息增益最大的特征的索引值 bestFeature = i
#返回信息增益最大特征的索引值 return bestFeature """ 函数说明：按照给定特征划分数据集
Parameters： dataSet：待划分的数据集 axis：划分数据集的特征 value：需要返回的特征的值 Returns：
shannonEnt：经验熵 """ 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 #main函数 if
__name__=='__main__': dataSet,features=creatDataSet() # print(dataSet)
# print(calcShannonEnt(dataSet))
print("最优索引值："+str(chooseBestFeatureToSplit(dataSet)))
二、 决策树的生成和修剪：
我们已经学习了从数据集构造决策树算法所需要的子功能模块，包括经验熵的计算和最优特征的选择，其工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
构建决策树的算法有很多，比如C4.5、ID3和CART，这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。由于特征数目并不是每次划分数据分组时都减少，因此这些算法在实际使用时可能引起一定的问题。目前我们并不需要考虑这个问题，只需要在算法开始运行前计算列的数目，查看算法是否使用了所有属性即可。
决策树生成算法递归地产生决策树，直到不能继续下去未为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。
2.1 ID3算法
ID3代码伪代码：
1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。
2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；
3）最后得到一个决策树。
上面已经求得，特征A3（有自己的房子）的信息增益最大，所以选择A3为根节点的特征，它将训练集D划分为两个子集D1（A3取值为“是”）D2（A3取值为“否”）。由于D1只有同一类的样本点，所以它成为一个叶结点，结点的类标记为“是”。
对D2则需要从特征A1(年龄)，A2(有工作)和A4(信贷情况)中选择新的特征，计算各个特征的信息增益：
Gain(D2,A1)=Entropy(D2)-E(A1)=0.251 Gain(D2,A2)=Entropy(D2)-E(A2)=0.918
Gain(D2,A4)=Entropy(D2)-E(A4)=0.474
根据计算，选择信息增益最大的A2作为节点的特征，由于其有两个取值可能，所以引出两个子节点：
①对应“是”（有工作），包含三个样本，属于同一类，所以是一个叶子节点，类标记为“是”。
②对应“否”（无工作），包含六个样本，输入同一类，所以是一个叶子节点，类标记为“否”。
这样就生成一个决策树，该树只用了两个特征（有两个内部节点），生成的决策树如下图所示：
3.2 C4.5生成算法
C4.5算是ID3的算法改进，将信息增益率（GainRatio）来加以改进方法，选取有最大的分割变量作为准则，这种方法可以处理连续的数值特征，其思想是用二（多）分法将连续的数值特征离散化，对于每一种离散方案，计算信息增益率，选取信息增益率最大的方案来离散连续的数值特征。
from math import log import operator """ 函数说明：计算给定数据集的经验熵（香农熵） Parameters：
dataSet：数据集 Returns： shannonEnt：经验熵 """ def calcShannonEnt(dataSet): #返回数据集行数
numEntries=len(dataSet) #保存每个标签（label）出现次数的字典 labelCounts={} #对每组特征向量进行统计 for
featVec in dataSet: currentLabel=featVec[-1] #提取标签信息 if currentLabel not in
labelCounts.keys(): #如果标签没有放入统计次数的字典，添加进去 labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 #label计数 shannonEnt=0.0 #经验熵 #计算经验熵 for key in
labelCounts: prob=float(labelCounts[key])/numEntries #选择该标签的概率
shannonEnt-=prob*log(prob,2) #利用公式计算 return shannonEnt #返回经验熵 """ 函数说明：创建测试数据集
Parameters：无 Returns： dataSet：数据集 labels：分类属性 """ def createDataSet(): # 数据集
dataSet=[[0, 0, 0, 0, 'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1,
0, 'yes'], [0, 0, 0, 0, 'no'], [1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1, 1,
1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2, 'yes'], [2, 0, 1, 2, 'yes'],
[2, 0, 1, 1, 'yes'], [2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'], [2, 0, 0, 0,
'no']] #分类属性 labels=['年龄','有工作','有自己的房子','信贷情况'] #返回数据集和分类属性 return
dataSet,labels """ 函数说明：按照给定特征划分数据集 Parameters： dataSet:待划分的数据集 axis：划分数据集的特征
value：需要返回的特征值 Returns： 无 """ def splitDataSet(dataSet,axis,value): #创建返回的数据集列表
retDataSet=[] #遍历数据集 for featVec in dataSet: if featVec[axis]==value: #去掉axis特征
reduceFeatVec=featVec[:axis] #将符合条件的添加到返回的数据集
reduceFeatVec.extend(featVec[axis+1:]) retDataSet.append(reduceFeatVec)
#返回划分后的数据集 return retDataSet """ 函数说明：计算信息增益以及信息增益最大特征的索引值 Parameters：
dataSet：数据集 Returns： shannonEnt：信息增益最大特征的索引值 """ def
chooseBestFeatureToSplit(dataSet): #特征数量 numFeatures = len(dataSet[0]) - 1
#计数数据集的香农熵 baseEntropy = calcShannonEnt(dataSet) #信息增益 bestInfoGain = 0.0
#最优特征的索引值 bestFeature = -1 #遍历所有特征 for i in range(numFeatures): #
获取dataSet的第i个所有特征 featList = [example[i] for example in dataSet]
#创建set集合{}，元素不可重复 uniqueVals = set(featList) #经验条件熵 newEntropy = 0.0 #计算信息增益
for value in uniqueVals: #subDataSet划分后的子集 subDataSet = splitDataSet(dataSet,
i, value) #计算子集的概率 prob = len(subDataSet) / float(len(dataSet)) #根据公式计算经验条件熵
newEntropy += prob * calcShannonEnt((subDataSet)) #信息增益 infoGain = baseEntropy
- newEntropy #打印每个特征的信息增益 print("第%d个特征的增益为%.3f" % (i, infoGain)) #计算信息增益 if
(infoGain > bestInfoGain): #更新信息增益，找到最大的信息增益 bestInfoGain = infoGain
#记录信息增益最大的特征的索引值 bestFeature = i #返回信息增益最大特征的索引值 return bestFeature """
函数说明：统计classList中出现次数最多的元素（类标签） Parameters： classList：类标签列表 Returns：
sortedClassCount[0][0]：出现次数最多的元素（类标签） """ def majorityCnt(classList):
classCount={} #统计classList中每个元素出现的次数 for vote in classList: if vote not in
classCount.keys(): classCount[vote]=0 classCount[vote]+=1 #根据字典的值降序排列
sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0] """ 函数说明：创建决策树 Parameters: dataSet：训练数据集
labels：分类属性标签 featLabels：存储选择的最优特征标签 Returns： myTree：决策树 """ def
createTree(dataSet,labels,featLabels): #取分类标签（是否放贷：yes or no）
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] featLabels.append(bestFeatLabel) #根据最优特征的标签生成树
myTree={bestFeatLabel:{}} #删除已经使用的特征标签 del(labels[bestFeat]) #得到训练集中所有最优特征的属性值
featValues=[example[bestFeat] for example in dataSet] #去掉重复的属性值
uniqueVls=set(featValues) #遍历特征，创建决策树 for value in uniqueVls:
myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),labels,featLabels)
return myTree if __name__=='__main__': dataSet,labels=createDataSet()
featLabels=[] myTree=createTree(dataSet,labels,featLabels) print(myTree)
结果如下：
2.2决策树剪枝
决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类却没有那么精确，即会出现过拟合（也称过学习）现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。这里介绍奥卡姆剃刀准则：
* 选择最简单的方法（假设最少）来解释实际问题
* 当你有两个处于竞争地位的理论能得到同样的结论时，那么简单的那个更好。
即假设越少，越不像巧合。
ID3/C4.5就是在选择更小的树，因为信息增益越高的属性越接近根部，树很快就变纯，符合奥卡姆剃刀准则。
即可以通过剪枝来实现：剪枝（pruning），从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型，极小化决策树整体的损失函数或代价函数来实现。
决策树学习的损失函数定义为：
其中，T表示这棵子树的叶子节点；H(T)表示第t个叶子的熵；Nt表示该叶子所含的训练样例的个数；α表示惩罚系数。
所以：
其中C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度；α表示参数>=0控制两者之间的影响控制两者之间的影响，较大的α促使选择较简单的模型（树），较小的α促使选择较复杂的模型（树），α=0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
剪枝就是当α确定时，选择损失函数最小的模型，即损失函数最小的子树。
当α值确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度越高；子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好；损失函数正好表示了对两者的平衡。
损失函数认为对于每个分类终点（叶子节点）的不确定性程度就是分类的损失因子，而叶子节点的个数是模型的复杂程度，作为惩罚项，损失函数的第一项是样本的训练误差，第二项是模型的复杂度。如果一棵子树的损失函数值越大，说明这棵子树越差，因此我们希望让每一棵子树的损失函数值尽可能得小，损失函数最小化就是用正则化的极大似然估计进行模型选择的过程。
决策树的剪枝过程（泛化过程）就是从叶子节点开始递归，记其父节点将所有子节点回缩后的子树为Tb（分类值取类别比例最大的特征值），未回缩的子树为，如果说明回缩后使得损失函数减小了，那么应该使这棵子树回缩，递归直到无法回缩为止，这样使用“贪心”的思想进行剪枝可以降低损失函数值，也使决策树得到泛化。可以看出，决策树的生成只是考虑通过提高信息增益对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。公式定义的损失函数的极小化等价于正则化的极大似然估计，剪枝过程示意图：
树的剪枝算法：
输入：生成算法产生整个树T，参数；
输出：修剪后的子树；
* 计算每个结点的信息熵
* 递归地从树的叶结点向上回缩；
剪枝分为先剪枝与后剪枝。
先剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。但因为决策树是贪婪算法，缺乏后效性考虑，可能导致决策树提前停止。
后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。后剪枝在实际应用更为成功，因为信息利用充分，缺点是可能计算代价大。
热门工具 换一换