机器学*之决策树(三)

发布于:2021-09-24 09:28:13

1.决策树

决策树是一种常见的 机器学*算法,可以用于分类任务,(也有回归的),且模型具有良好的可解释性,基本流程遵循简单且直观的“分而治之”的策略,其算法如下:



输入:训练集




D


=



(



x


1



,



y


1



)


,


(



x


2



,



y


2



)


,


.


.


.


,


(



x


m



,



y


m



)




D={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)}


D=(x1?,y1?),(x2?,y2?),...,(xm?,ym?)
?


? 属性集




A


=




a


1



,



a


2



,


.


.


.


,



a


d





A={a_1,a_2,...,a_d}


A=a1?,a2?,...,ad?


过程:函数TreeGenerate(D,A)


1:生成结点node


2: if D中样本全属于同一类别C then


3:将node 标记为C类叶结点;return


4:end if


5:if A=




?



phi


? OR D中样本在A上取值相同 then


6:将node标记为叶结点,其类别标记为D中样本数最多的类;return


7:end if


8.从A中选择最优划分属性





a


?




a_*


a??;


9:for





a


?




a_*


a??的每一个值





a


?


v




a_*^v


a?v? do


10:为node生成一个分支;令





D


v




D^v


Dv表示D中在





a


?




a_*


a??上取值为





a


?


v




a_*^v


a?v?的样本子集;


11:if





D


v




D^v


Dv为空then


12:将分支结点标记为叶结点,其类别标记为D中样本最多的类;return


13:else


14:以TreeGenerate(





D


v




D^v


Dv,A{





a


?




a_*


a??})为分支结点


15:end if


16:end for


输出:以node为根结点的一棵决策树



2.划分选择

算法中最关键的是第8行,如何选择最优划分属性。


2.1 信息增益

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标,假定当前样本集合 D中第k类样本所占的比例为





p


k




p_k


pk?,则D的信息熵为:







E


n


t


(


D


)


=


?







k


=


1




?


y


?





p


k



l


o



g


2




p


k




Ent(D)=-sum_{k=1}^{|y|}p_klog_2p_k


Ent(D)=?k=1∑?y??pk?log2?pk?


Ent(D)的值越小,则D的纯度越高。


假定离散属性a有V个可能的取值





a


1



,



a


2



,


.


.


.


,



a


V




{a^1,a^2,...,a^V}


a1,a2,...,aV,若使用a对样本进行划分,则产生V个分支节点,其中第v个节点包含了D中所有在属性a上取值为





a


V




a^V


aV的样本,记为





D


V




D^V


DV,因此我们可以计算出





D


V




D^V


DV的信息熵,再考虑到不同分支节点包含的样本数不同,给分支节点赋予权重





?



D


V



?



/



?


D


?




{|D^V|}/{|D|}


?DV?/?D?,即样本越多的分支节点的影响越大,于是可以计算出用属性a对样本集D划分所获得的信息增益(information gain):







G


a


i


n


(


D


,


a


)


=


E


n


t


(


D


)


?







v


=


1



V





?



D


V



?




?


D


?




E


n


t


(



D


V



)



Gain(D,a)=Ent(D)-sum_{v=1}^Vfrac{|D^V|}{|D|}Ent(D^V)


Gain(D,a)=Ent(D)?v=1∑V??D??DV??Ent(DV)


一般而言,信息增益越大,则用属性a来进行划分所获得的“纯度提升”越大。因此在第8步我们选择属性





a


?



=


arg


?



max


?



a





A




G


a


i


n


(


D


,


a


)



a_*=argmax_{ain{A}}Gain(D,a)


a??=argmaxa∈A?Gain(D,a),著名的ID3决策树学*算法就是用信息增益为准则来选择划分属性的。


2.2 增益率

实际上,信息增益准则对可取值数目较多的属性有所偏好。比如,假设用编号进行分类,那么每一类只有一个样本,这样每个节点都达到了最纯的效果,但是显然不是我们想要的结果。


为了减少这种偏好带来的不利影响,著名的C4.5决策树算法,不直接使用信息增益还是“增益率”来选择划分属性,定义为:







G


a


i



n


r



a


t


i


o


n


(


D


,


a


)


=




G


a


i


n


(


D


,


a


)




I


V


(


a


)





Gain_ration(D,a)=frac{Gain(D,a)}{IV(a)}


Gainr?ation(D,a)=IV(a)Gain(D,a)?


其中:







I


V


(


a


)


=







v


=


1



V





?



D


V



?




?


D


?




l


o



g


2





?



D


V



?




?


D


?





IV(a)=sum_{v=1}^Vfrac{|D^V|}{|D|}log_2frac{|D^V|}{|D|}


IV(a)=v=1∑V??D??DV??log2??D??DV??


称为属性a的“固有值”,属性a的可能取值越多,则IV(a)的值通常越大,需要注意的是,增益率准则对可取值数目较少的属性有所偏好,因此C4.5算法不是直接选择增益率最大的候选划分属性,而是使用了一个启发式:先从候选划分属性中找出信息增益高于*均水*的属性,再从中选择增益率最高的。


2.3 基尼指数

CART决策树使用“基尼指数”(Gini index)来选择划分属性,采用与上面相同的符号,数据集D的纯度为:







G


i


n


i


(


D


)


=







k


=


1




?


y


?










k









k





p


k




p



k







=


1


?







k


=


1




?


y


?





p


k


2




Gini(D)=sum_{k=1}^{|y|}sum_{k'
e{k}}p_kp_{k'}=1-sum_{k=1}^{|y|}p_k^2


Gini(D)=k=1∑?y??k′??=k∑?pk?pk′?=1?k=1∑?y??pk2?


直观来说,Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率,因此基尼指数越小,数据集D的纯度越高。


属性a的基尼指数定义为:







G


i


n



i


i



n


d


e


x


(


D


,


a


)


=







v


=


1



V





?



D


v



?




?


D


?




G


i


n


i


(



D


v



)



Gini_index(D,a)=sum_{v=1}^Vfrac{|D^v|}{|D|}Gini(D^v)


Ginii?ndex(D,a)=v=1∑V??D??Dv??Gini(Dv)


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


3剪枝处理

剪枝(pruning)是决策树学*算法对付“过拟合”的主要手段。决策树剪枝的基本策略有“预剪枝(prepruning)“和”后剪枝(postpruning)“。
预剪枝是在决策树生成过程中,对每个节点在划分前后进行估计,若当前节点的划分不能点来决策树泛化性能提升,则停止划分并将当前结点标记为叶节点,缺点是有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能下降,但在其基础上进行的后续划分却有可能导致性能显著提高,这是由预剪枝贪心的本质引起的;
后剪枝是先从训练集中生成一棵完整的决策树,然后自底向上地对叶节点进行考察,若将该结点对应的子树替换为叶节点能带来决策树泛化性能的提升,则将该子树替换为叶结点,后剪枝的欠拟合风险很小,泛化性能往往优于预剪枝,但后剪枝是在生成决策树之后进行的,训练时间开销要大得多。


4连续与缺失值

连续值可以采用离散化技术,最简单的策略是二分法对连续属性处理,这是C4.5算法中采用的。可以考察n个属性值之间的 n-1个元素作为候选划分点,这样就可以像离散属性一样来考察这些划分点。
首先,在属性值缺失时,如何选择属性:C4.5使用的是采用无缺失部分数据进行计算各划分属性带来的信息增益,增益需要加权,权重是该属性无缺失数据的比例。
第二,如何对样本进行划分,可以将空值样本同时划分到所有节点,这划分后可以将对应节点的信息熵进行更新。

相关推荐

最新更新

猜你喜欢