决策树（Decision Tree）

决策树是一种非参数有监督的机器学习方法，可以用于解决回归问题和分类问题。通过学习已有的数据，计算得出一系列推断规则来预测目标变量的值，并用类似流程图的形式进行展示。决策树模型可以进行可视化，具有很强的可解释性，算法容易理解，以决策树为基础的各种集成算法在很多领域都有广泛的应用。

成都创新互联总部坐落于成都市区，致力网站建设服务有成都网站建设、做网站、网络营销策划、网页设计、网站维护、公众号搭建、小程序定制开发、软件开发等为企业提供一整套的信息化建设解决方案。创造真正意义上的网站建设，为互联网品牌在互动行销领域创造价值而不懈努力！

熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度。在信息论里面，信息熵代表着一个事件或一个变量等所含有的信息量。 在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。

发生概率低的事件比发生概率高的事件具有更大的不确定性，需要更多的信息去描述他们，信息熵更高。

我们可以用计算事件发生的概率来计算事件的信息，又称“香农信息”（ Shannon Information ）。一个离散事件x的信息可以表示为：

h(x) = -log(p(x))

p() 代表事件x发生的概率， log() 为以二为底的对数函数，即一个事件的信息量就是这个事件发生的概率的负对数。选择以二为底的对数函数代表计算信息的单位是二进制。因为概率p(x)小于1，所以负号就保证了信息熵永远不为负数。当事件的概率为1时，也就是当某事件百分之百发生时，信息为0。

熵（ entropy ），又称“香农熵”（ Shannon entropy ），表示一个随机变量的分布所需要的平均比特数。一个随机变量的信息熵可以表示为：

H(x) = -sum(each k in K p(k)log(p(k)))

K表示变量x所可能具有的所有状态（所有事件），将发生特定事件的概率和该事件的信息相乘，最后加和，即可得到该变量的信息熵。可以理解为，信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上，信息熵其实是事件信息量的期望。

当组成该随机变量的一个事件的概率为1时信息熵最小，为0， 即该事件必然发生。当组成该随机变量的所有事件发生的概率相等时，信息熵最大，即完全不能判断那一个事件更容易发生，不确定性最大。

当一个事件主导时，比如偏态分布（ Skewed Probability Distribution ），不确定性减小，信息熵较低（low entropy）；当所有事件发生概率相同时，比如均衡分布（ Balanced Probability Distribution ），不确定性极大，信息熵较高（high entropy）。

由以上的香农信息公式可知，信息熵主要有三条性质：

- 单调性 。发生概率越高的事件，其所携带的信息熵越低。比如一个真理的不确定性是极低的，那么它所携带的信息熵就极低。

- 非负性 。信息熵不能为负。单纯从逻辑层面理解，如果得知了某个信息后，却增加了不确定性，这也是不合逻辑的。

- 可加性 。即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。

若两事件A和B同时发生，两个事件相互独立。 p(X=A,Y=B) = p(X = A)*p(Y=B) , 那么信息熵为 H(A,B) = H(A) + H(B) 。但若两事件不相互独立，那么 H(A,B) = H(A) + H(B) - I(A,B) 。其中 I(A,B) 是互信息（ mutual information，MI ），即一个随机变量包含另一个随机变量信息量的度量。即已知X的情况下，Y的分布是否会改变。

可以理解为，两个随机变量的互信息度量了两个变量间相互依赖的程度。X 和 Y的互信息可以表示为：

I(X;Y) = H(X) - H(X|Y)

H(X)是X的信息熵，H(X|Y)是已知Y的情况下，X的信息熵。结果的单位是比特。

简单来说，互信息的性质为：

- I(X;Y)=0 互信息永远不可能为负

- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是对称的

-当X，Y独立的时候， I(X;Y) = 0 互信息值越大，两变量相关性越强。

-当X，Y知道一个就能推断另一个的时候， I(X;Y) = H(Y) = H(X)

在数据科学中，互信息常用于特征筛选。在通信系统中互信息也应用广泛。在一个点到点的通信系统中，发送信号为X，通过信道后，接收端接收到的信号为Y，那么信息通过信道传递的信息量就是互信息 I(X,Y) 。根据这个概念，香农推导出信道容量（即临界通信传输速率的值）。

信息增益（ Information Gain ）是用来按照一定规则划分数据集后，衡量信息熵减少量的指数。

那数据集的信息熵又是怎么计算的呢？比如一个常见的0,1二分类问题，我们可以计算它的熵为：

Entropy = -(p(0) * log(P(0)) + p(1)\ * log(P(1)))

当该数据集为50/50的数据集时，它的信息熵是最大的（1bit）。而10/90的数据集将会大大减少结果的不确定性，减小数据集的信息熵（约为0.469bit）。

这样来说，信息熵可以用来表示数据集的纯度（ purity ）。信息熵为0就表示该数据集只含有一个类别，纯度最高。而较高的信息熵则代表较为平衡的数据集和较低的纯度。

信息增益是提供了一种可以使用信息熵计算数据集经过一定的规则（比如决策树中的一系列规则）进行数据集分割后信息熵的变化的方法。

IG(S,a) = H(S) - H(S|a)

其中，H(s) 是原数据集S的信息熵（在做任何改变之前），H(S|a)是经过变量a的一定分割规则。所以信息增益描述的是数据集S变换后所节省的比特数。

信息增益可以用做决策树的分枝判断方法。比如最常用CART树（ Classification and Regression Tree ）中的分枝方法，只要在python中设置参数 criterion 为 “entropy” 即可。

信息增益也可以用作建模前的特征筛选。在这种场景下，信息增益和互信息表达的含义相同，会被用来计算两变量之间的独立性。比如scikit-learn 中的函数 mutual_info_classiif()

信息增益在面对类别较少的离散数据时效果较好，但是面对取值较多的特征时效果会有 偏向性 。因为当特征的取值较多时，根据此特征划分得到的子集纯度有更大的可能性会更高(对比与取值较少的特征)，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。举一个极端的例子来说，如果一个特征为身份证号，当把每一个身份证号不同的样本都分到不同的子节点时，熵会变为0，意味着信息增益最大，从而该特征会被算法选择。但这种分法显然没有任何实际意义。

这种时候，信息增益率就起到了很重要的作用。

gR(D,A)=g(D,A)/HA(D)

HA(D) 又叫做特征A的内部信息，HA(D)其实像是一个衡量以特征AA的不同取值将数据集D分类后的不确定性的度量。如果特征A的取值越多，那么不确定性通常会更大，那么HA(D)的值也会越大，而1/HA(D)的值也会越小。这相当于是在信息增益的基础上乘上了一个惩罚系数。即 gR(D,A)=g(D,A)∗惩罚系数 。

在CART算法中，基尼不纯度表示一个随机选中的样本被分错类别的可能性，即这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本均为一种时（没有被分错的样本），基尼不纯度达到最低值0。

举例来说，如果有绿色和蓝色两类数据点，各占一半（蓝色50%，绿色50%）。那么我们随机分类，有以下四种情况：

-分为蓝色，但实际上是绿色（❌），概率25%

-分为蓝色，实际上也是蓝色（✔️），概率25%

-分为绿色，实际上也是绿色（✔️），概率25%

-分为绿色，但实际上是蓝色（❌），概率25%

那么将任意一个数据点分错的概率为25%+25% = 50%。基尼不纯度为0.5。

在特征选择中，我们可以选择加入后使数据不纯度减少最多的特征。

噪音数据简单来说就是会对模型造成误导的数据。分为类别噪声（ class noise 或 label noise ）和 变量噪声（ attribute noise ）。类别噪声指的的是被错误标记的错误数据，比如两个相同的样本具有不同的标签等情况。变量噪声指的是有问题的变量，比如缺失值、异常值和无关值等。

决策树其实是一种图结构，由节点和边构成。

-根节点：只有出边没有入边。包含样本全集，表示一个对样本最初的判断。

-内部节点：一个入边多个出边。表示一个特征或是属性。每个内部节点都是一个判断条件，包含数据集中从根节点到该节点所有满足条件的数据的集合。

-叶节点：一个入边无出边。表示一个类，对应于决策结果。

决策树的生成主要分为三个步骤：

1. 节点的分裂 ：当一个节点不够纯（单一分类占比不够大或者说信息熵较大）时，则选择将这一节点进行分裂。

2. 决策边界的确定 ：选择正确的决策边界（ Decision Boundary ），使分出的节点尽量纯，信息增益（熵减少的值）尽可能大。

3. 重复及停止生长 ：重复1，2步骤，直到纯度为0或树达到最大深度。为避免过拟合，决策树算法一般需要制定树分裂的最大深度。到达这一深度后，即使熵不等于0，树也不会继续进行分裂。

下面以超级知名的鸢尾花数据集举例来说明。

这个数据集含有四个特征：花瓣的长度（ petal length ）、花瓣的宽度( petal width )、花萼的长度( sepal length )和花萼的宽度( sepal width )。预测目标是鸢尾花的种类 iris setosa, iris versicolor 和 iris virginica 。

建立决策树模型的目标是根据特征尽可能正确地将样本划分到三个不同的“阵营”中。

根结点的选择基于全部数据集，使用了贪婪算法：遍历所有的特征，选择可以使信息熵降到最低、基尼不纯度最低的特征。

如上图，根节点的决策边界为' petal width = 0.8cm '。那么这个决策边界是怎么决定的呢？

-遍历所有可能的决策边界（需要注意的是，所有可能的决策边界代表的是该子集中该特征所有的值，不是以固定增幅遍历一个区间内的所有值！那样很没有必要的～）

-计算新建的两个子集的基尼不纯度。

-选择可以使新的子集达到最小基尼不纯度的分割阈值。这个“最小”可以指两个子集的基尼不纯度的和或平均值。

ID3是最早提出的决策树算法。ID3算法的核心是在决策树各个节点上根据 信息增益 来选择进行划分的特征，然后递归地构建决策树。

- 缺点 ：

（1）没有剪枝

（2）只能用于处理离散特征

（3）采用信息增益作为选择最优划分特征的标准，然而信息增益会偏向那些取值较多的特征(例如，如果存在唯一标识属性身份证号，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。)

C4.5 与ID3相似，但对ID3进行了改进：

-引入“悲观剪枝”策略进行后剪枝

-信息增益率作为划分标准

-将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；

-可以处理缺失值

对于缺失值的处理可以分为两个子问题：

（1）在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）

C4.5 中对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；

（2）选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）

C4.5 的做法是将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

（1）剪枝策略可以再优化；

（2）C4.5 用的是多叉树，用二叉树效率更高；

（3）C4.5 只能用于分类；

（4）C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；

（5）C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

可以用于分类，也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型，计算复杂度更低。

CART 包含的基本过程有 分裂，剪枝和树选择 。

分裂 ：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；

剪枝 ：采用“代价复杂度”剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；

树选择 ：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

（1）C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；

（2）C4.5 只能分类，CART 既可以分类也可以回归；

（3）CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；

（4）CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；

（5）CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

（1）决策树易于理解和解释，可以可视化分析，容易提取出规则

（2）可以同时处理分类型和数值型数据

（3）可以处理缺失值

（4）运行速度比较快（使用Gini的快于使用信息熵，因为信息熵算法有log）

（1）容易发生过拟合（集成算法如随机森林可以很大程度上减少过拟合）

（2）容易忽略数据集中属性的相互关联；

（3）对于那些各类别样本数量不一致的数据，在决策树中，进行属性划分时，不同的判定准则会带来不同的属性选择倾向。

写在后面：这个专辑主要是本小白在机器学习算法学习过程中的一些总结笔记和心得，如有不对之处还请各位大神多多指正！（关于决策树的剪枝还有很多没有搞懂，之后弄明白了会再单独出一篇总结哒）

参考资料链接：

1.

2.

3.

4.

5.

6.

7.

8.

用python实现红酒数据集的ID3,C4.5和CART算法？

ID3算法介绍

ID3算法全称为迭代二叉树3代算法（Iterative Dichotomiser 3）

该算法要先进行特征选择，再生成决策树，其中特征选择是基于“信息增益”最大的原则进行的。

但由于决策树完全基于训练集生成的，有可能对训练集过于“依赖”，即产生过拟合现象。因此在生成决策树后，需要对决策树进行剪枝。剪枝有两种形式，分别为前剪枝（Pre-Pruning）和后剪枝（Post-Pruning），一般采用后剪枝。

信息熵、条件熵和信息增益

信息熵：来自于香农定理，表示信息集合所含信息的平均不确定性。信息熵越大，表示不确定性越大，所含的信息量也就越大。

设x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x

1

,x

2

,x

3

,...x

n

为信息集合X的n个取值，则x i x_ix

i

的概率：

P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n

P(X=i)=p

i

,i=1,2,3,...,n

信息集合X的信息熵为：

H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}

H(X)=−

i=1

∑

n

p

i

logp

i

条件熵：指已知某个随机变量的情况下，信息集合的信息熵。

设信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y

1

,y

2

,y

3

,...y

m

组成的随机变量集合Y，则随机变量（X，Y）的联合概率分布为

P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}

P(x=i,y=j)=p

ij

条件熵：

H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}

H(X∣Y)=

j=1

∑

m

p(y

j

)H(X∣y

j

)

由

H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}

H(X∣y

j

)=−

j=1

∑

m

p(y

j

)

i=1

∑

n

p(x

i

∣y

j

)logp(x

i

∣y

j

)

和贝叶斯公式：

p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)

p(x

i

y

j

)=p(x

i

∣y

j

)p(y

j

)

可以化简条件熵的计算公式为:

H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}

H(X∣Y)=

j=1

∑

m

i=1

∑

n

p(x

i

,y

j

)log

p(x

i

,y

j

)

p(x

i

)

信息增益：信息熵-条件熵，用于衡量在知道已知随机变量后，信息不确定性减小越大。

d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)

d(X,Y)=H(X)−H(X∣Y)

python代码实现

import numpy as np

import math

def calShannonEnt(dataSet):

""" 计算信息熵 """

labelCountDict = {}

for d in dataSet:

label = d[-1]

if label not in labelCountDict.keys():

labelCountDict[label] = 1

else:

labelCountDict[label] += 1

entropy = 0.0

for l, c in labelCountDict.items():

p = 1.0 * c / len(dataSet)

entropy -= p * math.log(p, 2)

return entropy

def filterSubDataSet(dataSet, colIndex, value):

"""返回colIndex特征列label等于value，并且过滤掉改特征列的数据集"""

subDataSetList = []

for r in dataSet:

if r[colIndex] == value:

newR = r[:colIndex]

newR = np.append(newR, (r[colIndex + 1:]))

subDataSetList.append(newR)

return np.array(subDataSetList)

def chooseFeature(dataSet):

""" 通过计算信息增益选择最合适的特征"""

featureNum = dataSet.shape[1] - 1

entropy = calShannonEnt(dataSet)

bestInfoGain = 0.0

bestFeatureIndex = -1

for i in range(featureNum):

uniqueValues = np.unique(dataSet[:, i])

condition_entropy = 0.0

for v in uniqueValues: #计算条件熵

subDataSet = filterSubDataSet(dataSet, i, v)

p = 1.0 * len(subDataSet) / len(dataSet)

condition_entropy += p * calShannonEnt(subDataSet)

infoGain = entropy - condition_entropy #计算信息增益

if infoGain = bestInfoGain: #选择最大信息增益

bestInfoGain = infoGain

bestFeatureIndex = i

return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):

""" 通过训练集生成决策树 """

featureName = featNames[:] # 拷贝featNames，此处不能直接用赋值操作，否则新变量会指向旧变量的地址

classList = list(dataSet[:, -1])

if len(set(classList)) == 1: # 只有一个类别

return classList[0]

if dataSet.shape[1] == 1: #当所有特征属性都利用完仍然无法判断样本属于哪一类，此时归为该数据集中数量最多的那一类

return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #选择特征

bestFeatureName = featNames[bestFeatureIndex]

del featureName[bestFeatureIndex] #移除已选特征列

decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已选特征列所包含的类别， 通过递归生成决策树

for v in featureValueUnique:

copyFeatureName = featureName[:]

subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)

decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, copyFeatureName)

return decisionTree

def classify(decisionTree, featnames, featList):

""" 使用训练所得的决策树进行分类 """

classLabel = None

root = decisionTree.keys()[0]

firstGenDict = decisionTree[root]

featIndex = featnames.index(root)

for k in firstGenDict.keys():

if featList[featIndex] == k:

if isinstance(firstGenDict[k], dict): #若子节点仍是树，则递归查找

classLabel = classify(firstGenDict[k], featnames, featList)

else:

classLabel = firstGenDict[k]

return classLabel

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

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

下面用鸢尾花数据集对该算法进行测试。由于ID3算法只能用于标称型数据，因此用在对连续型的数值数据上时，还需要对数据进行离散化，离散化的方法稍后说明，此处为了简化，先使用每一种特征所有连续性数值的中值作为分界点，小于中值的标记为1，大于中值的标记为0。训练1000次，统计准确率均值。

from sklearn import datasets

from sklearn.model_selection import train_test_split

iris = datasets.load_iris()

data = np.c_[iris.data, iris.target]

scoreL = []

for i in range(1000): #对该过程进行10000次

trainData, testData = train_test_split(data) #区分测试集和训练集

featNames = iris.feature_names[:]

for i in range(trainData.shape[1] - 1): #对训练集每个特征，以中值为分界点进行离散化

splitPoint = np.mean(trainData[:, i])

featNames[i] = featNames[i]+'='+'{:.3f}'.format(splitPoint)

trainData[:, i] = [1 if x = splitPoint else 0 for x in trainData[:, i]]

testData[:, i] = [1 if x = splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)

classifyLable = [classify(decisionTree, featNames, td) for td in testData]

scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

print 'score: ', np.mean(scoreL)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

输出结果为：score: 0.7335，即准确率有73%。每次训练和预测的准确率分布如下：

数据离散化

然而，在上例中对特征值离散化的划分点实际上过于“野蛮”，此处介绍一种通过信息增益最大的标准来对数据进行离散化。原理很简单，当信息增益最大时，说明用该点划分能最大程度降低数据集的不确定性。

具体步骤如下：

对每个特征所包含的数值型特征值排序

对相邻两个特征值取均值，这些均值就是待选的划分点

用每一个待选点把该特征的特征值划分成两类，小于该特征点置为1， 大于该特征点置为0，计算此时的条件熵，并计算出信息增益

选择信息使信息增益最大的划分点进行特征离散化

实现代码如下：

def filterRawData(dataSet, colIndex, value, tag):

""" 用于把每个特征的连续值按照区分点分成两类，加入tag参数，可用于标记筛选的是哪一部分数据"""

filterDataList = []

for r in dataSet:

if (tag and r[colIndex] = value) or ((not tag) and r[colIndex] value):

newR = r[:colIndex]

newR = np.append(newR, (r[colIndex + 1:]))

filterDataList.append(newR)

return np.array(filterDataList)

def dataDiscretization(dataSet, featName):

""" 对数据每个特征的数值型特征值进行离散化 """

featureNum = dataSet.shape[1] - 1

entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #对于每一个特征

uniqueValues = sorted(np.unique(dataSet[:, featIndex]))

meanPoint = []

for i in range(len(uniqueValues) - 1): # 求出相邻两个值的平均值

meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)

bestInfoGain = 0.0

bestMeanPoint = -1

for mp in meanPoint: #对于每个划分点

subEntropy = 0.0 #计算该划分点的信息熵

for tag in range(2): #分别划分为两类

subDataSet = filterRawData(dataSet, featIndex, mp, tag)

p = 1.0 * len(subDataSet) / len(dataSet)

subEntropy += p * calShannonEnt(subDataSet)

## 计算信息增益

infoGain = entropy - subEntropy

## 选择最大信息增益

if infoGain = bestInfoGain:

bestInfoGain = infoGain

bestMeanPoint = mp

featName[featIndex] = featName[featIndex] + "=" + "{:.3f}".format(bestMeanPoint)

dataSet[:, featIndex] = [1 if x = bestMeanPoint else 0 for x in dataSet[:, featIndex]]

return dataSet, featName

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

32

33

34

35

36

37

38

39

重新对数据进行离散化，并重复该步骤1000次，同时用sklearn中的DecisionTreeClassifier对相同数据进行分类，分别统计平均准确率。运行代码如下:

from sklearn.tree import DecisionTreeClassifier

import matplotlib.pyplot as plt

scoreL = []

scoreL_sk = []

for i in range(1000): #对该过程进行1000次

featNames = iris.feature_names[:]

trainData, testData = train_test_split(data) #区分测试集和训练集

trainData_tmp = copy.copy(trainData)

testData_tmp = copy.copy(testData)

discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根据信息增益离散化

for i in range(testData.shape[1]-1): #根据测试集的区分点离散化训练集

splitPoint = float(discritizationFeatName[i].split('=')[-1])

testData[:, i] = [1 if x=splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)

classifyLable = [classify(decisionTree, featNames, td) for td in testData]

scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier('entropy')

clf.fit(trainData[:, :-1], trainData[:, -1])

clf.predict(testData[:, :-1])

scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print 'score: ', np.mean(scoreL)

print 'score-sk: ', np.mean(scoreL_sk)

fig = plt.figure(figsize=(10, 4))

plt.subplot(1,2,1)

pd.Series(scoreL).hist(grid=False, bins=10)

plt.subplot(1,2,2)

pd.Series(scoreL_sk).hist(grid=False, bins=10)

plt.show()

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

两者准确率分别为：

score: 0.7037894736842105

score-sk: 0.7044736842105263

准确率分布如下：

两者的结果非常一样。

（但是。。为什么根据信息熵离散化得到的准确率比直接用均值离散化的准确率还要低啊？？哇的哭出声。。）

最后一次决策树图形如下：

决策树剪枝

由于决策树是完全依照训练集生成的，有可能会有过拟合现象，因此一般会对生成的决策树进行剪枝。常用的是通过决策树损失函数剪枝，决策树损失函数表示为:

C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|

C

a

(T)=

t=1

∑

T

N

t

H

t

(T)+α∣T∣

其中，H t ( T ) H_t(T)H

t

(T)表示叶子节点t的熵值，T表示决策树的深度。前项∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑

t=1

T

N

t

H

t

(T)是决策树的经验损失函数当随着T的增加，该节点被不停的划分的时候，熵值可以达到最小，然而T的增加会使后项的值增大。决策树损失函数要做的就是在两者之间进行平衡，使得该值最小。

对于决策树损失函数的理解，如何理解决策树的损失函数? - 陶轻松的回答 - 知乎这个回答写得挺好，可以按照答主的思路理解一下

C4.5算法

ID3算法通过信息增益来进行特征选择会有一个比较明显的缺点：即在选择的过程中该算法会优先选择类别较多的属性（这些属性的不确定性小，条件熵小，因此信息增益会大），另外，ID3算法无法解决当每个特征属性中每个分类都只有一个样本的情况（此时每个属性的条件熵都为0）。

C4.5算法ID3算法的改进，它不是依据信息增益进行特征选择，而是依据信息增益率，它添加了特征分裂信息作为惩罚项。定义分裂信息：

S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}

SplitInfo(X,Y)=−

i

∑

n

∣X∣

∣X

i

∣

log

∣X∣

∣X

i

∣

则信息增益率为：

G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}

GainRatio(X,Y)=

SplitInfo(X,Y)

d(X,Y)

关于ID3和C4.5算法

在学习分类回归决策树算法时，看了不少的资料和博客。关于这两个算法，ID3算法是最早的分类算法，这个算法刚出生的时候其实带有很多缺陷：

无法处理连续性特征数据

特征选取会倾向于分类较多的特征

没有解决过拟合的问题

没有解决缺失值的问题

即该算法出生时是没有带有连续特征离散化、剪枝等步骤的。C4.5作为ID3的改进版本弥补列ID3算法不少的缺陷：

通过信息最大增益的标准离散化连续的特征数据

在选择特征是标准从“最大信息增益”改为“最大信息增益率”

通过加入正则项系数对决策树进行剪枝

对缺失值的处理体现在两个方面：特征选择和生成决策树。初始条件下对每个样本的权重置为1。

特征选择：在选取最优特征时，计算出每个特征的信息增益后，需要乘以一个**“非缺失值样本权重占总样本权重的比例”**作为系数来对比每个特征信息增益的大小

生成决策树：在生成决策树时，对于缺失的样本我们按照一定比例把它归属到每个特征值中，比例为该特征每一个特征值占非缺失数据的比重

关于C4.5和CART回归树

作为ID3的改进版本，C4.5克服了许多缺陷，但是它自身还是存在不少问题：

C4.5的熵运算中涉及了对数运算，在数据量大的时候效率非常低。

C4.5的剪枝过于简单

C4.5只能用于分类运算不能用于回归

当特征有多个特征值是C4.5生成多叉树会使树的深度加深

————————————————

版权声明：本文为CSDN博主「Sarah Huang」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：

C4.5算法

C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习：给定一个数据集，其中的每一个元组都能用一组属性值来描述，每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习，找到一个从属性值到类别的映射关系，并且这个映射能用于对新的类别未知的实体进行分类。

C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构，其中每个内部节点（非树叶节点）表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点存放一个类标号。一旦建立好了决策树，对于一个未给定类标号的元组，跟踪一条有根节点到叶节点的路径，该叶节点就存放着该元组的预测。决策树的优势在于不需要任何领域知识或参数设置，适合于探测性的知识发现。

决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型；预测时，对新的数据，利用决策模型进行分类。

决策树是一种通过对特征属性的分类对样本进行分类的树形结构，包括有向边以及三类节点：

上图给出了（二叉）决策树的示例。决策树具有以下特点：

决策树学习的本质是从训练集中归纳出一组分类规则。但随着分裂属性次序的不同，所得到的决策树也会不同。如何得到一棵决策树既对训练数据有较好的拟合，又对未知数据有很好的预测呢？

首先，我们要解决两个问题：

一般的，一颗决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点则对应于一个属性册书；每个叶结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶结点的路径对饮过了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强的决策树，其基本流程遵循简单且只管的“分而治之”（divide-and-conquer）策略，如下图所示：

显然，决策树的生成是一个递归的过程。在决策树基本算法中，有三种情形会导致递归返回：

在第二种情形下，我们把当前结点标记为叶结点，并且将其类别设定为该结点所含样本最多的类别；在第三种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多类别。注意这两种情形的处理实质不同：情形二是在利用当前结点的后验分布，而情形三则是把父结点的样本分布当做当前结点的先验分布。

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。假定当前样本集合 中第k类样本所占比例为 ，则 的信息熵定义为

的值越小，则 的纯度越高。

假定离散属性 有 个可能的取值 ,若使用 来对样本集合 进行划分，则会产生 个分支结点，其中第v个分支结点包含了 中所有在属性 上取值为 的样本，记为 ，我们根据上述公式计算出 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 ，即样本越多的分支结点影响越大，于是可以计算出用属性 对样本集合 进行划分所获得的"信息增益"（information gain）

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升越大”。因此，我们可用信息增益来进行决策树的划分属性选择。

实际上，信息增益准则对可取值数目较多的属性有所偏好（如何以序号作为划分属性，每一个事物作为一个单独存在的类别的时候，信息增益往往会很高，但是这样进行划分并没有什么意义），为了减少这种偏好可能带来的不利影响，著名的C4.5算法并不是直接使用信息增益，而是使用增益率（gain ratio）来选择最优的划分属性。增益率的定义为：

值得注意的是： 增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式： 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

CART决策树使用“基尼指数”来选择划分属性。数据集 的纯度可用基尼值来度量：

直观来说， 反映了从数据集 中随机抽取两个样本，其类别标记不一致的概率，因此 值越小，则数据集 的纯度就越高。属性 的基尼指数定义为：

于是，我们在候选属性集合 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即

银行希望能够通过一个人的信息（包括职业、年龄、收入、学历）去判断他是否有贷款的意向，从而更有针对性地完成工作。下表是银行现在能够掌握的信息，我们的目标是通过对下面的数据进行分析建立一个预测用户贷款一下的模型。

上表中有4个客户的属性，如何综合利用这些属性去判断用户的贷款意向？决策树的做法是每次选择一个属性进行判断，如果不能得出结论，继续选择其他属性进行判断，直到能够“肯定地”判断出用户的类型或者是上述属性都已经使用完毕。比如说我们要判断一个客户的贷款意向，我们可以先根据客户的职业进行判断，如果不能得出结论，再根据年龄作判断，这样以此类推，直到可以得出结论为止。决策树用树结构实现上述的判断流程，如图所示：

以熵作为节点复杂度的统计量，分别求出下面例子的信息增益，图3.1表示节点选择属性1进行分裂的结果，图3.2表示节点选择属性2进行分裂的结果，通过计算两个属性分裂后的信息增益，选择最优的分裂属性。

属性一

属性二

由于 ，所以属性1是比属性2更优的分裂属性，故而选择属性1作为分裂属性。

由于 ，故而选择属性2作为分裂属性。

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有事会造成决策树分支过多，这是就可能因为训练样本学得太好了，以致把训练集自身的一些特点党组哟所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

其中{1,2,3,6,7,10,14,15,16,17}为测试集，{4,5,8,9,11,12,13}为训练集。

预剪枝是要对划分前后泛化性能进行评估。对比决策树某节点生成前与生成后的泛化性能。

2.计算训练集的信息增益，得知脐部的信息增益最大，因此按照脐部进行划分。又因为在训练集中，凹陷特征好瓜的占比多，因此凹陷划分为好瓜，稍凹特征好过占比多，因此将其标记为好瓜，因此按照脐部划分的子树结果如下：

划分后，对比结果如下：

由图可知，预剪枝使得很多分支没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间。但是，有些分支虽当前不能提升泛化性。甚至可能导致泛化性暂时降低，但在其基础上进行后续划分却有可能导致显著提高，因此预剪枝的这种贪心本质，给决策树带来了欠拟合的风险。

后剪枝表示先从训练集中生成一颗完整决策树。

对比标记节点的划分类与各数据的真实分类，计算准确率，如下表所示：

生成的决策树，在验证集上的准确度为3/7*100%=42.9%.

对比预剪枝与后剪枝生成的决策树，可以看出，后剪枝通常比预剪枝保留更多的分支，其欠拟合风险很小，因此后剪枝的泛化性能往往由于预剪枝决策树。但后剪枝过程是从底往上裁剪，因此其训练时间开销比前剪枝要大。