Python与机器学习——决策树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python与机器学习——决策树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8553字，纯文字阅读大概需要13分钟。

内容图文

决策树

理论基础

决策树是建立在信息论的基础上的，决策树的生成就是让数据的"不确定性"减少越多越好，意味着划分能获得越多的信息。信息的不确定性可以用信息熵和基尼指数来描述。

信息熵

信息熵的定义其实也比较简单：
$H(y)=\sum_{k=1}^Kp_k\log p_k\tag{信息熵公式}$H(y)=k=1∑K?pk?logpk?(信息熵公式)对于具体的、随机变量来说，生成的数据集$D=\{y_1,...,y_N\}$D={y1?,...,yN?},在实际计算信息熵可以用
$H(y)=H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log \frac{|C_k|}{|D|}\tag{信息熵公式2}$H(y)=H(D)=?k=1∑K?∣D∣∣Ck?∣?log∣D∣∣Ck?∣?(信息熵公式2)也就是假设y的取值空间为$\{c_1,...,c_K\}${c1?,...,cK?},$p_k$pk?表示y取$c_k$ck?的概率：$p_k=p(y=c_k)$pk?=p(y=ck?)，$|C_k|$∣Ck?∣表示y取$c_k$ck?的样本个数，$|D|$∣D∣表示总样本个数，$\frac{|C_k|}{|D|}$∣D∣∣Ck?∣?表示的就是频率，使用了"频率估计概率"。
当$p_1=p_2=...=p_K=\frac{1}{K}$p1?=p2?=...=pK?=K1?时候，$H(y)$H(y)达到了最大值$-\log\frac{1}{K}$?logK1?也就是$\log K$logK,意味着每个分类都是一样的，怎么区分全靠瞎蒙。让信息的不确定性减小，是能让分类清楚的条件。对于一个二分类问题的话，$K=2$K=2,假设$y$y只能取0，1。并且$p(y=0)=p,p(y=1)=1-p$p(y=0)=p,p(y=1)=1?p,那么信息熵也就是：
$H(y)=-p\log p-(1-p)\log(1-p)$H(y)=?plogp?(1?p)log(1?p)$\log$log可以以2为低，也可以以e为底。总之，信息混乱程度越大，信息熵越大，信息量越大。

基尼指数

基尼指数的定义为：
$Gini(y)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2\tag{Gini指数}$Gini(y)=k=1∑K?pk?(1?pk?)=1?k=1∑K?pk2?(Gini指数)同样，对于实际信息来说，使用频率估计概率：
$Gini(y)=Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2\tag{Gini指数2}$Gini(y)=Gini(D)=1?k=1∑K?(∣D∣∣Ck?∣?)2(Gini指数2)同样的，信息混乱程度越大，Gini指数越大，信息量越大。

信息增益

首先确定一些定义：数据集$D=\{(x_1,y_1),...,(x_N,y_N)\}$D={(x1?,y1?),...,(xN?,yN?)},其中$x_i=(x_i^{(1)},...,x_i^{(n)})^T$xi?=(xi(1)?,...,xi(n)?)T表示描述$y_i$yi?的n维特征向量，假设特征叫$A$A，那么$D=\{(A_1,y_1),...,(A_N,y_N)\}$D={(A1?,y1?),...,(AN?,yN?)}。引入条件熵的概念，根据特征$A$A的不同取值$\{a_1,...,a_m\}${a1?,...,am?}对y进行限制$y=y_k$y=yk?,对$y=y_k$y=yk?的部分计算信息熵并加权平均，得到条件熵$H(y|A)$H(y∣A)。条件熵越小，意味着y被$A$A限制后的总的不确定性越小。数学定义为：
$H(y|A)=\sum_{j=1}^mp(A=a_j)H(y|A=a_j)\tag{条件熵}$H(y∣A)=j=1∑m?p(A=aj?)H(y∣A=aj?)(条件熵)其中：
$H(y|A=a_j)=-\sum_{k=1}^Kp(y=c_k|A=a_j)\log p(y=c_k|A=a_j)$H(y∣A=aj?)=?k=1∑K?p(y=ck?∣A=aj?)logp(y=ck?∣A=aj?)经验条件熵估计真正条件熵的公式：
$H(y|A)=H(y|D)=\sum_{j=1}^m\frac{|D_j|}{|D|}\sum_{k=1}^K\frac{|D_{jk}|}{|D_j|}\log \frac{|D_{jk}|}{|D_j|}$H(y∣A)=H(y∣D)=j=1∑m?∣D∣∣Dj?∣?k=1∑K?∣Dj?∣∣Djk?∣?log∣Dj?∣∣Djk?∣?$D_j$Dj?表示在$A=a_j$A=aj?限制下的数据集，$|D_{jk}|$∣Djk?∣表示$D_j$Dj?中的第$k$k类样本的个数。信息增益就可以表示为
$g(y,A)=H(y)-H(y|A)\tag{信息增益(互信息量)}$g(y,A)=H(y)?H(y∣A)(信息增益(互信息量))也叫互信息量。决策树种ID3就是用这个指标来选择特征的。但是天然地，这样会优先选择取值比较多的特征，对于这样的情况，给取值比较多的一个惩罚使用信息增益比来计算，也就是C4.5的概念：
$g_R(y,A)=\frac{g(y,A)}{H_A(y)}\tag{信息增益比}$gR?(y,A)=HA?(y)g(y,A)?(信息增益比)其中：
$H_A(y)=-\sum_{j=1}^mp(y^A=a_j)\log p(y^A=a_j)$HA?(y)=?j=1∑m?p(yA=aj?)logp(yA=aj?)对于基尼指数，是差不多的原理：
$Gini(y|A)=1-\sum_{j=1}^m\frac{|D_j|}{|D|}\sum_{k=1}^K(\frac{|D_j|}{|D|})^2$Gini(y∣A)=1?j=1∑m?∣D∣∣Dj?∣?k=1∑K?(∣D∣∣Dj?∣?)2信息增益表示为：
$g_{Gini}(y,A)=Gini(y)-Gini(y|A)$gGini?(y,A)=Gini(y)?Gini(y∣A)CART种就是这种定义。

#决策树生成

决策数生成可以概括为2步：

• 将样本空间划分为若干个互不相交的子空间；
• 给每个子空间贴一个标签。

常用的决策树算法有ID3，C4.5，CART。

• ID3可以说是最朴素的决策树算法，是离散数据分类的解决方案。
• C4.5适用于混合型数据分类。
• CART可解决数据回归问题。

ID3

ID3是Interactive Dichotomiter-3,交互式二分法。
假设有数据集$D=\{(x_1,y_1),...,(x_N,y_N)\}$D={(x1?,y1?),...,(xN?,yN?)}。ID3的算法处理伪代码过程为：

(1) 将数据喂给一个节点；
(2) 若D中所有样本同属一个类别,则节点不再继续生成，标记为k类；
(3) 若样本已经是0维向量，则将这时的D中样本个数最多类别k类作为这个节点的类别输出；
(4)否则，按照互信息定义的信息增益：
$g(y,x^{(j)})=H(y)-H(y|x^{(j)})$g(y,x(j))=H(y)?H(y∣x(j))来计算第j维特征的信息增益，然后选择使得信息增益最大的特征作为划分标准
$y^*=\arg \underset{j}{\max}g(y,x^{(j)})$y?=argjmax?g(y,x(j))(5) 若满足停止条件，则不再继续生成并将此时的D中样本中个数最多的类别的k类作为类别标记
(6) 否则，依$x^{(j*)}$x(j?)的所有可能取值$\{a_1,...,a_m\}${a1?,...,am?}将数据集划分为$\{D_1,...,D_m\}${D1?,...,Dm?}使：
$(x_i,y_i)\in D_j\Leftrightarrow x_i^{(j^*)}=a_j,\forall i=1,...,N$(xi?,yi?)∈Dj??xi(j?)?=aj?,?i=1,...,N同时，将$x_1,...,x_N$x1?,...,xN?的第$j^*$j?维去掉，使他们成为n-1维特征向量。
(7) 对每个$D_j$Dj?从(1)开始调用算法。

对于(5)中的停止条件，常用的有：

• 选择$x^{(j^*)}$x(j?)作为特征时，信息增益$g(y,x^{(j^*)})$g(y,x(j?))任然很小，则停止；
• 事先把数据集分为训练集和测试集，训练集得到的$x^{(j^*)}$x(j?)不能再测试集熵的错误率更小，则停止。

C4.5

ID3是使用信息增益的最大特征作为当前特征选择的依据，但是这样就特别容易选择特征的值比较多的一个特征，比如特征$F_1$F1?可能的选择值有100个，而特征$F_2$F2?只有3个，那么选择$F_1$F1?的概率就比$F_2$F2?高，这样是不合理的。C4.5就是使用了信息增益比来选择特征的。所以C4.5可以处理ID3算法比较难处理的混合型数据。
原理上来讲，只需要将ID3的第(4)点替换为：
(4) 否则，按照信息增益比的定义：
$g_R(y,x^{(j)})=\frac{g(y,x^{(j)})}{H_{x^{(j)}}(y)}$gR?(y,x(j))=Hx(j)?(y)g(y,x(j))?来计算第$j$j维特征的信息增益比，然后选择使得信息增益最大的特征作为划分标准，也就是:
$j^*=\arg \underset{j}{\max}g_R(y,x^{(j)})$j?=argjmax?gR?(y,x(j))混合型数据处理最主要的内容就是处理连续特征。可以简单转化为一个二分问题，
$Y_1=\{y:y^A<a_1\},Y_2=\{y:y^A\geqslant a_1\}$Y1?={y:yA<a1?},Y2?={y:yA?a1?}也就是:
$A=\{a_1,a_2\},Y_1=\{y:y^A=a_1\},Y_2=\{y:y^A=a_2\}$A={a1?,a2?},Y1?={y:yA=a1?},Y2?={y:yA=a2?}$a_1$a1?就是一个二分标准，确定二分标准的方法为：

• 若$x^{(j)}$x(j)在当前数据集有$m$m个取值，为$u_1,...,u_m$u1?,...,um?,并且$u_1<...<u_m$u1?<...<um?依次选$v_1,...,v_p$v1?,...,vp?作为二分标准，并选择最好的一个，其中$v_1-v_p$v1??vp?构成等差数列，$u_1=v_1,u_m=v_p$u1?=v1?,um?=vp?。p的选择试情况而定。如果数据不均衡时候可能有不合理的情况。还有一种确定二分标准的方式.
• 依次选择$v_1=\frac{u_1+u_2}{2},...,v_{m_1}=\frac{v_{m-1}+v_m}{2}$v1?=2u1?+u2??,...,vm1??=2vm?1?+vm??作为二分标准，并计算信息增益比，选择最优的一个。

CART

CART是Classification and Regression Tree, 分类与回归树。所以CART能做分类与回归问题。CART是使用Gini增益比来选择特征的，它的特色是假设了最终生成的树为二叉树，所以在处理离散数据时候也会通过决出二分标准来划分数据。
将ID3算法的第(4)点替换为：
(4) 否则，不妨设$x^{(j)}$x(j)在当前数据集中有$S_j$Sj?个取值$u_1^{(j)},...,u_{S_j}^{(j)}$u1(j)?,...,uSj?(j)?,并且$u_1^{(j)}<...<u_{S_j}^{(j)}$u1(j)?<...<uSj?(j)?,那么：
a)若$x^{(j)}$x(j)是离散变量，依次选择$u_1^{(j)}<...<u_{S_j}^{(j)}$u1(j)?<...<uSj?(j)?作为二分标准$a_p$ap?，此时：
$A_{jp}=\{x^{(j)}=a_p,x^{(j)}\neq a_p\}$Ajp?={x(j)=ap?,x(j)?=ap?}
b)若$x^{(j)}$x(j)是连续变量，依次选择$\frac{u_1+u_2}{2},...,\frac{v_{m-1}+v_m}{2}$2u1?+u2??,...,2vm?1?+vm??作为二分标准$a_p$ap?，此时：
$A_{jp}=\{x^{(j)}<a_p,x^{(j)}\geqslant a_p\}$Ajp?={x(j)<ap?,x(j)?ap?}按照基尼系数的定义增益增益：
$g_{Gini}(y,A_{jp})=Gini(y)-Gini(y|A_{jp})$gGini?(y,Ajp?)=Gini(y)?Gini(y∣Ajp?)来计算第$j$j维特征在二分标准下的信息增益，选择使得信息增益最大的特征$x^{(y^*)}$x(y?)和相应的二分标准$u_{p^*}^{(j^*)}$up?(j?)?作为划分标准：
$(j^*,p^*)=\arg \underset{j,p}{\max}g_{Gini}(y,A_{jp})$(j?,p?)=argj,pmax?gGini?(y,Ajp?)回归问题暂且不表。

代码实现

参考git repo:Python_and_ML:03DT

• 点赞
• 收藏
• 分享
• • 文章举报

内容总结

以上是互联网集市为您收集整理的Python与机器学习——决策树全部内容，希望文章能够帮你解决Python与机器学习——决策树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端