機(jī)器學(xué)習(xí)（四）決策樹

一、信息熵

首先給出信息熵的定義如下$$H\left( x\right) =-\sum _{x\in \chi }p\left( x\right) \ln p\left( x\right) $$
1、無約束條件時(shí)，均勻分布熵最大
2、若給定分布的期望和方差，則正態(tài)分布的熵最大

二、決策樹是什么

決策樹就是下圖所示的東西

三、決策樹

1、幾個(gè)名詞：

1、訓(xùn)練數(shù)據(jù)集：D
2、數(shù)據(jù)的標(biāo)簽有K種，即有K個(gè)類，記為\(C_{k}\)
3、數(shù)據(jù)有多個(gè)特征，其中有某一個(gè)特征叫A，這個(gè)A特征有n個(gè)取值，記所有A特征取值為i的數(shù)據(jù)的集合為\(D_{i}\)
4、在子集\(D_{i}\)中屬于第k個(gè)類的樣本集合記為\(D_{ik}\)
定義如下兩個(gè)量：
$$H\left( D\right) =\sum ^{K}{k=1}\dfrac {\left| C\right| }{\left| D\right| }\log\dfrac {\left| C_{k}\right| }{\left| D\right| }$$
$$H\left( D| A\right) =-\sum ^{n}{i=1}\dfrac {\left| Di\right| }{\left| D\right| }\sum ^{K}\dfrac {\left| D_{ik}\right| }{\left| D_{i}\right| }log\dfrac {\left| D_{ik}\right| }{\left| D_{i}\right|}$$

2、評(píng)估指標(biāo)

根據(jù)以上定義的量，定義如下幾個(gè)評(píng)估指標(biāo)：
1、信息增益：\(g(D,A)=H(D)-H(D|A)\)
2、信息增益率：\(g_{r}(D,A)=g(D,A)/H(A)\)
3、基尼系數(shù)：\(Gini(p)=1-\sum ^{K}_{k=1}(\dfrac {\left| C_{k}\right| }{\left| D\right| })^{2}\)

3、決策樹算法

常用決策樹算法包括ID3算法、C4.5算法，CART決策樹，它們最重要的不同在于評(píng)估指標(biāo)不同，其中，ID3采用信息增益作為評(píng)估指標(biāo)，C4.5采用信息增益率作為評(píng)估指標(biāo)，CART決策樹采用基尼系數(shù)作為評(píng)估指標(biāo)。

我們以ID3為例，它首先掃描所有特征，找出信息增益最大的特征作為其根節(jié)點(diǎn)，在對(duì)其各個(gè)子節(jié)點(diǎn)遞歸地進(jìn)行這個(gè)過程，直至達(dá)到某個(gè)收斂條件。

4、決策樹的目標(biāo)函數(shù)

決策樹的目標(biāo)函數(shù)，或者說決策樹的損失函數(shù)為：
\(C(T)=\sum_{t\in leaf}N_{t}\times H(t)\)
其中，\(N_{t}\)代表某一葉結(jié)點(diǎn)中包含的樣本數(shù)；\(H(t)\)代表該葉結(jié)點(diǎn)中的熵

對(duì)該目標(biāo)函數(shù)進(jìn)行正則化后的目標(biāo)函數(shù)為：\(C_{\alpha}(T)=C(T)+\alpha\times|leafs|\),即加上葉節(jié)點(diǎn)個(gè)數(shù)的信息。