机器学习之决策树学习笔记分享


决策树思维导图

机器学习之决策树学习笔记分享

特征选择

特征选择是为了选取具有分类能力的特征,选取准则为信息增益或信息增益比

信息增益

def:特征A对训练数据D的信息增益为g(D,A),定义为集合D的经验熵H(D)和特征A给定条件下D的经验条件熵H(D|A)之差,即

g(D,A)=H(D)H(DA)
g(D,A)=H(D)-H(D|A)

g(D,A)=H(D)−H(D∣A)
其中熵的定义为:

H(P)=i=1npilog2pipi=p(X=xi),i=1,2,3…)
H(P)=-\sum_{i=1}^{n}p_ilog_2p_i (pi=p(X=x_i),i=1,2,3…)

H(P)=−i=1∑n​pi​log2​pi​(pi=p(X=xi​),i=1,2,3…)
熵越大随机变量的不确定性就越大

条件熵的定义为:

H(YX)=i=1npiH(YX=xi)pi=p(X=xi),i=1,2,3…)
H(Y|X)=\sum_{i=1}^{n}p_iH(Y|X=x_i) (pi=p(X=x_i),i=1,2,3…)

H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​)(pi=p(X=xi​),i=1,2,3…)
当熵和条件熵为数据统计(特别时极大似然估计)得到时,所对应的熵和条件熵称为经验熵和经验条件熵

介绍完熵和条件熵后,我们继续回到信息增益上

一般地,熵与条件熵之差称为互信息,所以信息增益等价于训练数据集中类与特征的互信息

经验熵H(D)表示对数据集D进行分类的不确定性,经验条件熵表示在给定特征A条件下对数据集D进行分类的不确定性,它们的差,即信息增益表示由于特征A而使得对数据集D的分类的不确定性减少的程度

根据信息增益选取特征的方法为:对训练数据集D,计算每个特征的信息增益,选取信息增益最大的那个特征

信息增益比

以信息增益作为划分训练数据集的准则,存在偏向于选择取值较多的特征的问题。利用信息增益比即可矫正该问题

def:信息增益比的定义为信息增益与训练数据集D关于特征A的值的熵之比,即:

gR(D,A)=g(D,A)HA(D)
g_R(D,A)=\frac{g(D,A)}{H_A(D)}

gR​(D,A)=HA​(D)g(D,A)​
其中,

HA(D)=i=1nDiDlog2DiD(nA)
H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}(n为特征A的取值个数)

HA​(D)=−i=1∑n​∣D∣∣Di​∣​log2​∣D∣∣Di​∣​(n为特征A的取值个数)

基尼指数

def:分类问题中,假设有K个类,样本点属于第k类的概率为pk,则基尼指数定义为

Gini(p)=k=1Kpk(1pk)=1i=1Kpk2
Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{i=1}^{K}p_k^2

Gini(p)=k=1∑K​pk​(1−pk​)=1−i=1∑K​pk2​
如果样本D根据特征A是否取某一可能值a被划分为D1和D2两部分,即

{(x,y)DA(x)=a},D2=DD1
\{(x,y)\in D|A(x)=a\}, D_2=D-D_1

{(x,y)∈D∣A(x)=a},D2​=D−D1​
则在特征A的条件下,集合D的基尼指数定义为

Gini(D,A)=D1DGini(D1)+D2DGini(D2)
Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)

Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)
基尼指数Gini(D)表示集合D的不确定性,和熵类似,基尼指数越大,则样本集合不确定性越大

决策树的生成
ID3算法生成决策树

ID3算法生成决策树的具体方法:

从根节点开始,计算所有可能的特征的信息增益,选取信息增益最大的特征作为结点的特征,由该特征的不同取值建立子节点,再对子节点重复上述过程,直到所有特征的信息增益都很小或没有特征可以选择为止,最后得到一棵决策树。

过程:
输入:训练数据集D,特征值A和阈值

ε\varepsilon

ε
输出:决策树T
(1)若D中所有实例属于同一类

CkC_k

Ck​,将

CkC_k

Ck​作为该结点的类标记,返回T
(2)若A为空集,则将D中实例最大的类

CkC_k

Ck​作为该结点的类标记,返回T
(3)否则,计算A中各特征对D的信息增益,选择信息增益最大的特征

AgA_g

Ag​
(4)如果特征

AgA_g

Ag​小于阈值

ε\varepsilon

ε,则重复步骤(2)
(5)否则,对特征

AgA_g

Ag​的每一个可能值

aia_i

ai​,依

Ag=aiA_g=a_i

Ag​=ai​将D分割为若干非空子集

DiD_i

Di​,将

DiD_i

Di​中实例数最大的类作为标记,返回T
(6)对第i个结点,以

DiD_i

Di​为训练集,以

AAgA-{A_g}

A−Ag​为特征集,递归的调用(1)~(5),得到子树

TiT_i

Ti​,返回

TiT_i

Ti​

C4.5算法生成决策树

C4.5生成决策树与ID3类似,只是换成了信息增益比来选择特征

过程:
输入:训练数据集D,特征值A和阈值

ε\varepsilon

ε
输出:决策树T
(1)若D中所有实例属于同一类

CkC_k

Ck​,将

CkC_k

Ck​作为该结点的类标记,返回T
(2)若A为空集,则将D中实例最大的类

CkC_k

Ck​作为该结点的类标记,返回T
(3)否则,计算A中各特征对D的信息增益比,选择信息增益最大的特征

AgA_g

Ag​
(4)如果特征

AgA_g

Ag​小于阈值

ε\varepsilon

ε,则重复步骤(2)
(5)否则,对特征

AgA_g

Ag​的每一个可能值

aia_i

ai​,依

Ag=aiA_g=a_i

Ag​=ai​将D分割为若干非空子集

DiD_i

Di​,将

DiD_i

Di​中实例数最大的类作为标记,返回T
(6)对第i个结点,以

DiD_i

Di​为训练集,以

AAgA-{A_g}

A−Ag​为特征集,递归的调用(1)~(5),得到子树

TiT_i

Ti​,返回

TiT_i

Ti​

CART生成二叉决策树

输入:训练集D,停止计算的条件
输出:CART决策树
根据训练数据集,从根节点开始,递归的对每一个结点进行以下操作,生成二叉决策树
过程:
(1)设结点的训练数据为D,计算现有特征对数据集的基尼指数。此时对每一个特征,对其可能取的每个A值,根据样本点对A=a的测试为“是”或“否”将D分割为

D1D2D_1和D_2

D1​和D2​两部分,计算A=a时的基尼指数
(2)在所有可能的特征A以及它们可能的切分点a中,选择基尼指数最小的特征以及对应的切分点作为最优特征与最优切分点,从现结点生成两个子结点,将训练数据集依特征分配到两个子结点中
(3)对两个子结点递归的调用(1)~(2),直到满足停止条件
(4)生成CART决策树
算法停止条件是结点中的样本个数小于预定阈值或样本集中的基尼指数小于预定阈值(样本基本属于同一类)或者没有更多特征

决策树的修剪

令决策树的叶节点数为T,损失函数为:

Ca(T)=C(T)+aTC_a(T)=C(T)+a|T|

Ca​(T)=C(T)+a∣T∣
其中C(T)为决策树的训练误差,决策树模型用不确定性表示,不确定性越大,则训练误差亦越大。T表示决策树的复杂度惩罚,α参数权衡训练数据的训练误差与模型复杂度的关系,意义相当于正则化参数。

a0a\to0

a→0的时候,最优决策树模型的训练误差接近 0,模型处于过拟合;当

aa\to{\infty}

a→∞的时候,最优决策树模型是由根节点组成的单节点树。
决策树剪枝步骤:
(1) 将正则化参数α从小到大分成不同的区间

[ai,ai+1)[a_i,a_{i+1})

[ai​,ai+1​) ,对决策树的非叶节点进行剪枝,令该节点为T,以该节点为根节点的子树为Tt。
(2) 当α满足如下条件时:

a=C(T)C(Tt)Tt1a=\frac{C(T)-C(T_t)}{|T_t|-1}

a=∣Tt​∣−1C(T)−C(Tt​)​
即节点为单节点树的损失函数与子树Tt的损失函数相等,对该节点进行剪枝。
(3)遍历所有非叶节点,得到每个剪枝后的最优子树与对应的α参数
最后附上基于sklearn的决策树实现

#coding=="utf-8"#

#导入基础函数库
import numpy as np

#导入画图库
import matplotlib.pyplot as plt
import seaborn as sns

#导入决策树模型函数
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree

#构造数据集
x_features = np.array([[-1, -2], [-2, -1], [-3, -2], [1, 3], [2, 1], [3, 2]])
y_label = np.array([0, 1, 0, 1, 0, 1])

#调用决策树模型
tree_clf = DecisionTreeClassifier()

#训练数据集
tree_clf = tree_clf.fit(x_features, y_label)

#可视化数据构造在数据样本点
plt.figure()
plt.scatter(x_features[:,0], x_features[:,1], c=y_label, s=50, cmap='viridis')
plt.title('Dataset')
plt.show()

输出:
机器学习之决策树学习笔记分享

#可视化决策树
import graphviz
dot_data = tree.export_graphviz(tree_clf, out_file=None)#生成dot文件
graph = graphviz.Source(dot_data)#将dot文件转化为gv文件
graph.render("pengunis")

在命令提示符中输入pengunis.pdf:
机器学习之决策树学习笔记分享

#创建新样本
x_features_new1 = np.array([[0, -1]])
x_features_new2 = np.array([[2, 1]])

#使用训练好的模型进行分类预测
y_label_new1_predict = tree_clf.predict(x_features_new1)
y_label_new2_predict = tree_clf.predict(x_features_new2)

print("The New point 1 class:\n", y_label_new1_predict)
print("The New point 2 class:\n", y_label_new2_predict)

输出:

The New point 1 class:
[1]
The New point 2 class:
[0]

sklearn库中决策树算法采用的是优化后的CART算法
具体请详见《统计学习方法》,正在学习,敬请指教

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

机器学习之决策树学习笔记分享

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 机器学习之决策树学习笔记分享
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏