决策树(Decision Tree)
决策树(Decision Tree)
基本概念
决策树是以树状图为基础的、基于特征的、有监督的、贪心的、学习算法。决策树可以是二叉树也可以是非二叉树,其输出结果是一些进行判别的规则。
决策树由节点和有向边组成,内部的节点表示一个特征(属性),叶子节点表示一个分类。决策树可以用于分类问题也可以用于回归问题。对于分类问题,利用决策树进行预测时,将样本实例输入决策树,经过决策树内部的判别规则,最终会将样本实例分配到某一个叶节点的类中,该叶节点的类就是样本实例所属的类别。
例如,刘某需要贷款买房,银行需要评估其贷款风险,评估项有:Credit、Term、Income三项。根据用户的数据(样本)构造出决策树,再将刘某的信息作为决策树的输入,经过判定得出风险值。解决该问题的整体框架为:
如果ML model采用决策树算法,则可构造出类似图2的决策树:
决策树构造好之后对于具体实例预测方法为将实例作为输入使之贯穿整个决策树得出最终的判定结果,例如,对于刘某,假设其Credit=poor,Income=high,Term=5 years,则风险预测方法为:
构造决策树的算法
决策树的生成是一个递归过程,在决策树基本算法中,有三种情形会导致递归返回:
1. 当前结点包含的样本全属于同一类别,无需划分;
2. 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分;
3. 当前结点包含的样本集合为空,不能划分。
ID3
根据信息论的知识,系统的信息增益越大那么纯度就越高。ID3算法的核心就是根据信息增益作为选择特征(属性)的标准。每次都选择可以使系统信息增益最大的特征(属性)。
给定训练集
其中,
举例说明公式含义:
根据图2的数据,一共9个样本,包括5个safe,4个risky,则:
如果根据特征
划分后,数据
那么根据
那么根据特征
根据
比较图5和图6可知根据
根据
比较
接下来,需要根据特征
ID3缺点:
1. 以信息增益对训练集的特征进行划分,会产生偏向于选择取值较多的特征的问题。
2. ID3只有树的生成算法,没有剪枝,生成的树容易产生过拟合,即对训练集匹配的很好但是对于测试集效果较差。
例如,对于图8,当选择
C4.5
C4.5使用信息增益率作为选择特征的标准。给定特征
其中,
例如,对于图8,根据特征
而以
显然
需要注意的是,
利用C4.5构造决策树的过程和利用ID3是一样的,只需要将选择特征的标准由信息增益换成信息增益率即可。另外,C4.5可以处理连续数据,例如:
对于图9训练集,
C4.5处理连续属性的方法是先把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的,但对于有限的采样数据它是离散的,如果有
在离散属性上只需要计算
本来需要计算13次来确定分界点,现在只需计算7次。一般使用增益来选择连续值特征的分界点,因为如果利用增益率来选择连续值特征的分界点,会有一些副作用。分界点将样本分成两个部分,这两个部分的样本个数之比也会影响增益率。根据增益率公式可以发现,当分界点能够把样本分成数量相等的两个子集时(此时的分界点为等分分界点),增益率的抑制会被最大化,因此等分分界点被过分抑制了。子集样本个数能够影响分界点,显然不合理。因此在确定有连续值的特征的分界点时还是采用增益,而在分界点确定之后选择特征的时候才使用增益率。这个改进能够很好得抑制连续值属性的倾向。
对有连续值的特征构造出的决策树形如:
决策边界
决策树的决策边界是一些垂直于特征的线,例如对于一维特征,决策边界类似:
对于二维特征,决策边界类似:
C4.5优点:
a. 使用信息增益率作为划分的标准,克服了ID3使用信息增益带来的选择特征时偏向于选择取值多的特征的问题;
b. 可以处理连续的特征;
c. 在构造树的同时进行剪枝;
d. 可以处理不完整的数据
对于如何进行剪枝、如何处理不完整的数据,后续会有专题文章。
C4.5缺点:1.在构造决策树的过程中,需要对数据集进行多次顺序扫描和排序,因此算法比较低效;2.C4.5只适合处理训练集小的样本,如果训练集样本过大,内存无法容纳所有的数据集是无法完成决策树的构造的。
CART(Classification and Regression Tree)
分类与回归树(CART)算法也可以用来构造决策树,并且CART构造出的决策树是二叉树。CART算法既可以用于分类又可以用于回归。
分类与回归树模型采用不同的标准来选择最优的特征,CART分类树采用基尼指数,CART回归树采用最小加权平均方差。
CART分类树
对于给定样本集合
如果根据特征
其中,
为展示方便还拿图2的数据说明利用基尼指数构造CART分类树的过程。
-
以
Credit 为特征进行划分:
CART算法构造的决策树是二叉树,而特征Credit 有三个取值,因此需要将Credit 的三个取值中的两个进行合并,因此需要进行遍历合并求基尼指数来确定哪两个值合并是最好的。-
excellent 与fair 合并:Gini(D,excellent+fair)Gini(D,poor)Gini(D,Credit)======1−(46)2−(26)20.44441−(13)2−(23)20.444469∗0.4444+39∗0.44440.4444 -
excellent 与poor 合并:Gini(D,excellent+poor)Gini(D,fair)Gini(D,Credit)======1−(25)2−(35)20.481−(34)2−(14)20.37559∗0.48+49∗0.3750.4333 -
fair 与poor 合并:Gini(D,fair+poor)Gini(D,excellent)Gini(D,Credit)======1−(47)2−(37)20.48981−(12)2−(12)20.579∗0.4898+29∗0.50.4921
-
-
以
Term 为特征进行划分:Gini(D,3yrs)Gini(D,5yrs)Gini(D,Term)======1−(35)2−(25)20.481−(24)2−(24)20.559∗0.48+49∗0.50.4889 -
以
Income 为特征进行划分:Gini(D,high)Gini(D,low)=Gini(D,Income)======1−(35)2−(25)20.481−(24)2−(24)20.559∗0.48+49∗0.50.4889
比较Gini(D,Credit) 、Gini(D,Term) 、Gini(D,Income) 可知按照特征Credit 进行划分且将excellent 与poor 合并的基尼指数最小,所以决策树的根节点就取Credit 。
此时的树为:
下面需要分别对
- 对于
N1 :
以Term 为特征进行划分:Gini(N1,3yrs)Gini(N1,5yrs)Gini(N1,Term)======1−(13)2−(23)20.44441−(12)2−(12)20.535∗0.4444+25∗0.50.4666
以Income 为特征进行划分:Gini(N1,high)Gini(N1,low)Gini(N1,Income)======1−(13)2−(23)20.44441−(12)2−(12)20.535∗0.4444+25∗0.50.4666 - 对于
N2 :
以Term 为特征进行划分:Gini(N2,3yrs)Gini(N2,5yrs)Gini(N2,Term)======1−(22)2−(02)201−(12)2−(12)20.524∗0+24∗0.50.25
以Income 为特征进行划分:Gini(N2,high)Gini(N2,low)Gini(N2,Income)======1−(22)2−(02)201−(12)2−(12)20.524∗0+24∗0.50.25
根据上面的计算可知对于N1 和N2 利用Term 进行划分和利用Income 进行划分基尼指数都是相等的。此时满足了构造决策树终止的条件,因此算法终止。从这里我们也可以知道,该问题使用决策树算法并不能得到很好的解决。
CART回归树
学习决策树可归结为对实例空间进行划分,使得每个隔离的空间都具有较小的方差。在回归问题中,特征值是连续型而非二值型的,CART构造回归树就是找到合适的特征对数据集
定义数据集
其中,
如果根据特征
其中
从公式
利用下图中的样本来说明CART算法构造回归树的过程:
图
用
- 根据特征
Model 进行划分:Ave(A100)Ave(B3)Ave(E112)Ave(M102)Ave(T202)WeiSquAve(D,Model)=========1051+1770+190031573.666745137787099+270+6253331.333339∗Ave2(A100)+19∗Ave2(B3)+19∗Ave2(E112)+19∗Ave2(M102)+39∗Ave2(T202)3.2098⋅106 - 根据特征
Condition 进行划分:Ave(excellent)Ave(good)Ave(fair)WeiSquAve(D,Condition)========1770+451323141.5270+870+1051+190041022.7577+99+625326729∗Ave2(excellent)+49∗Ave2(good)+39∗Ave2(fair)2.6818⋅106 - 根据特征
Leslie 进行划分:Ave(yes)Ave(no)WeiSquAve(D,Leslie)======625+870+190031131.666777+99+270+1051+1770+451361296.666739∗Ave2(yes)+69∗Ave2(no)1.5478⋅106
比较WeiSquAve(D,Model) 、WeiSquAve(D,Condition) 、WeiSquAve(D,Leslie) 可知WeiSquAve(D,Model) 最大,因此应该选择特征Model 进行划分,该步划分的结果为:
接下来需要对数据集
对于
- 根据特征
Condition 进行划分:Ave(excellent)Ave(good)Ave(fair)WeiSquAve(N1,Condition)======17701051+190021475.5013∗Ave2(excellent)+23∗Ave2(good)+03∗Ave2(fair)2.4957⋅106 - 根据特征
Leslie 进行划分:Ave(yes)Ave(no)WeiSquAve(N1,Leslie)=====19001051+177021410.513∗Ave2(yes)+23∗Ave2(no)2.5297⋅106
比较WeiSquAve(N1,Condition) 、WeiSquAve(N1,Leslie) 可知WeiSquAve(N1,Leslie) 最大,因此应该选择特征Leslie 进行划分。
对于
- 根据特征
Condition 进行划分:Ave(excellent)Ave(good)Ave(fair)WeiSquAve(N2,Condition)======027099+625236203∗Ave2(excellent)+13∗Ave2(good)+23∗Ave2(fair)111,662.6667 - 根据特征
Leslie 进行划分:Ave(yes)Ave(no)WeiSquAve(N2,Leslie)=====62599+2702184.513∗Ave2(yes)+23∗Ave2(no)152,901.8333
比较WeiSquAve(N2,Condition) 、WeiSquAve(N2,Leslie) 可知WeiSquAve(N2,Leslie) 最大,因此应该选择特征Leslie 进行划分。
因此,最终构造的决策回归树为:
- scikit-learn实现CART分类决策树:
使用图9 的数据进行演示:
import numpy as np
import pandas as pd
from sklearn import tree
#导出为pdf所需package
import graphviz
#scikit learn中CART分类树
CARTClassificationTree = tree.DecisionTreeClassifier()
#准备数据
adict = {'Outlook':'Sunny','Sunny','Overcast','Rainy','Rainy','Rainy','Overcast',
'Sunny','Sunny','Rainy','Sunny','Overcast','Overcast','Rainy'],
'Temperature':[85,80,83,70,68,65,64,72,69,75,75,72,81,71],
'Humidity':[85,90,78,96,80,70,65,95,70,80,70,90,75,80],
'Windy':False,True,False,False,False,True,True,
False,False,False,True,True,False,True]}
dfx = pd.DataFrame(adict)
#进行one-hot编码
onehot_dfx = pd.get_dummies(dfx)
#给X赋值
dataX = onehot_dfx.values
#给Y赋值
dataY = np.array(['No','No','Yes','Yes','Yes','No','Yes',
'No','Yes','Yes','Yes','Yes','Yes','No'])
#训练模型
CARTClassificationTree.fit(dataX,dataY)
#输出CART分类决策树并导出为pdf格式
dot_data = tree.export_graphviz(CARTClassificationTree,out_file=None,
class_names=npY,feature_names=onehot_dfx.columns,
filled=True,rounded=True,special_characters=True)
graph = graphviz.Source(dot_data)
graph.render('PlayGolf')
最终的CART分类决策树为:
- scikit-learn实现CAR回归决策树:
使用图15 的数据进行演示:
import numpy as np
import pandas as pd
from sklearn import tree
#导出为pdf所需package
import graphviz
#scikit learn中CART回归树
CARTRegressionTree = tree.DecisionTreeRegressor()
#准备数据
adict = {'Model':['B3','T202','A100','T202','M102','A100','T202','A100','E112'],
'Condition':['excellent','fair','good','good','good','excellent','fair','good','fair'],
'Leslie':['no','yes','no','no','yes','no','no','yes','no']}
dfx = pd.DataFrame(adict)
#进行one-hot编码
onehot_dfx = pd.get_dummies(dfx)
#给X赋值
dataX = onehot_dfx.values
#给Y赋值
dataY = np.array([4513,625,1051,270,870,1770,99,1900,77])
#训练模型
CARTRegressionTree.fit(dataX,dataY)
#输出CART分类决策树并导出为pdf格式
dot_data = tree.export_graphviz(CARTRegressionTree,out_file=None,feature_names=onehot_dfx.columns,
filled=True,rounded=True,special_characters=True)
graph = graphviz.Source(dot_data)
graph.render('Price')
最终的CART回归决策树为:
更多完整资料请移步github:
https://github.com/GarryLau/MachineLearning
上一篇: 机器学习-逻辑回归
下一篇: lasso 回归 & 岭回归