97三级片,鸡吧视频在线

本來以為決策樹很簡單，所以初次寫這篇帖子的時候也沒仔細(xì)深究，后來學(xué)到xgboost的時候有些環(huán)節(jié)怎么想不明白，后來才知道原來核心原因還是CART的原理沒有搞清楚，于是回來老老實實重寫這片帖子，尤其是CART部分！

帖子目錄：
1、CART原理
2、信息熵及其他決策樹簡介
2、隨機森林

一、CART原理
CART全稱為Classification and Regression Trees，即分類和回歸樹，既能處理回歸問題也能處理分類問題，CART應(yīng)該是應(yīng)用最廣泛的決策樹了，其他高級算法（例如隨機森林，Adaboost和xgboost等）的基分類器也是用的CART，所以務(wù)必要仔細(xì)弄清楚CART的原理，
本節(jié)數(shù)據(jù)集：

image.png

1、基尼指數(shù)
對于給定的樣本D，其基尼指數(shù)為：

Gini(D)=1-\sum_{k=1}^{K}\frac{|C_{k}|^{2}}{|D|}

其中，Ck是D中屬于第k類的樣本子集，K是類的個數(shù)。|Ck|和D分別表示子集的個數(shù)和樣本的個數(shù)。

如果樣本集合D根據(jù)特征A是否取某一可能的值分割成 $D_{1},D_{2}$
在特征A的條件下集合D的基尼指數(shù)為
$Gini(D,A)=\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$

2、分類樹
當(dāng)CART是分類樹的時候，采用GINI值作為分裂節(jié)點的依據(jù)

舉例：利用看電視時長，職業(yè)和年齡預(yù)測是否已婚
因為CART屬于二分叉樹，所以如果某個特征有三個以上屬性，這需要兩兩劃分，例如對于職業(yè)這個特征，有三種劃分情況{“學(xué)生”}，{“老師”，“上班族”}以及{“老師”，“學(xué)生”}、{“上班族”}，最后一種為{“學(xué)生”，“上班族”}、{“老師”}
對于
1）對于第一種情況 $R_{1}$ ={“學(xué)生”}, $R_{2}$ ={“老師”，“上班族”}

image.png

$Gini(D,\text{職業(yè)_1})=(\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$

職業(yè)_1_1={“學(xué)生”}，包含3個樣本，1個是，2個否
$\frac{|D_{1}|}{|D|}=\frac{3}{7}$
$Gini(D_{1})=1-((\frac{1}{3})^{2}+(\frac{2}{3})^{2})=\frac{4}{9}$
職業(yè)_1_2={“老師”，“上班族”}，包含4個樣本，3個是，1個否
$\frac{|D_{2}|}{|D|}=\frac{4}{7}$
$Gini(D_{2})=1-((\frac{1}{4})^{2}+(\frac{3}{4})^{2})=\frac{3}{8}$
最終：
$Gini(D,\text{職業(yè)_1})=\frac{3}{7}\cdot\frac{4}{9}+\frac{4}{7}\cdot\frac{3}{8}=\frac{17}{42}$

計算特征職業(yè)其他兩種情況的基尼指數(shù)，選擇最小的

對于年齡這個特征，因為年齡屬于連續(xù)型變量按照數(shù)值的大小順序排為12,18,21,26,29,36,47，可被分為6中情況，
對于第一種情況是{12}，{18,21,26,29,36,47}
$Gini(D,\text{年齡_1})=(\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$
年齡_1_1={12}，包含1個樣本，0個是，1個否
$\frac{|D_{1}|}{|D|}=\frac{1}{7}$
$Gini(D_{1})=1-1=0$

年齡_1_2={18,21,26,29,36,47},包含6個樣本，包含4個是，2個否
$\frac{|D_{2}|}{|D|}=\frac{6}{7}$
$Gini(D_{2})=1-((\frac{4}{6})^{2}+(\frac{2}{6})^{2})=\frac{4}{9}$
最終：
$Gini(D,\text{年齡_1})=\frac{1}{7}\cdot0+\frac{6}{7}\cdot\frac{4}{9}=\frac{8}{21}$

計算年齡其他5種情況的基尼指數(shù)，選擇最小的

所有的基尼指數(shù)計算出來之后，選擇最小那個作為當(dāng)前節(jié)點的分割依據(jù)，例如，如果最終職業(yè)的第一種情況的基尼指數(shù)最小，那么此時的決策樹為
$f(x)=\left\{\begin{matrix} 0 & \text{{'學(xué)生'}}\\ 1& \text{{'上班族'，'老師'}} \end{matrix}\right.$
注：
a)其中0代表未婚，1代表已婚
b)當(dāng)前葉子節(jié)點各樣本類別值的眾數(shù)即為預(yù)測值
c)xgboost會在此處計算gain和權(quán)值，可詳見下篇帖子

3、回歸樹
當(dāng)CART作為回歸樹的時候，使用樣本的最小方差作為分裂節(jié)點的依據(jù),追小方差公式為：

舉例：根據(jù)看電視時間，是否已婚和職業(yè)隊年齡進行預(yù)測
對于職業(yè)這個特征，有三種劃分情況{“學(xué)生”}，{“老師”，“上班族”}以及{“老師”，“學(xué)生”}、{“上班族”}，最后一種為{“學(xué)生”，“上班族”}、{“老師”}
對于
1）對于第一種情況R_{1}={“學(xué)生”},R_{2}={“老師”，“上班族”}

image.png

職業(yè)_1_1={“學(xué)生”}，包含3個樣本，年齡均值為：
$c1=(12+18+21)/3=17$
$c2=(26+47+36+29)/4=34.5$

$m=min\left [ \sum (y_{i}-c_{1})^{2}+min\sum(y_{i}-c_{1})^{2} \right ]$
$y_{i}\in (\text(23))=\left ( {12,18,21} ,{26,47,36,29}\right )$
最小平方誤差計算得：
$m=42+261=303$

計算領(lǐng)完兩種情況m2=742.6,m3=238.8,m3的值最小，因此此時的決策樹為：
$f(x)=\left\{\begin{matrix} 41.5 & \text{{'上班族'}}\\ 21.2& \text{{'學(xué)生'，'老師'}} \end{matrix}\right.$

注：
a)當(dāng)前葉子節(jié)點各樣本y真實值的均值即為預(yù)測值

4、sklearn代碼
max_depth樹的最大深度，min_samples_split 樣本數(shù)>10,繼續(xù)分支

image.png

二、信息熵及其他決策樹簡介
數(shù)據(jù)集

image.png

0、信息熵
信息熵是最基礎(chǔ)的東西
$Ent(D)=-\sum_{k=1}^{|y|}p_{k}log_{2}p_{k}$
舉例：
1)對于西瓜數(shù)據(jù)集根節(jié)點（好瓜） |y|=2，p(好瓜=是)=8/19，p(好瓜=否)=7/19
$Ent(D)=-(\frac{8}{19}log_{2}\frac{8}{19}+\frac{7}{19}log_{2}\frac{7}{19})=0.998$

2)對于變量色澤|y|=3(青綠，烏黑，淺白)
$Ent(D^{1})=(\frac{3}{6}log_{2}\frac{3}{6}+\frac{3}{6}log_{2}\frac{3}{6})=1.00$
$Ent(D^{1})=(\frac{4}{6}log_{2}\frac{4}{6}+\frac{2}{6}log_{2}\frac{2}{6})=0.918$
$Ent(D^{1})=(\frac{1}{5}log_{2}\frac{1}{5}+\frac{4}{5}log_{2}\frac{4}{5})=0.722$

1、信息增益
$Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v})$
a是數(shù)據(jù)集的自變量，V是某一個自變量可分成幾個樣本集（例如自變量色澤可按照青綠，烏黑和淺白三個屬性將變量分為三個樣本集，則V=3）

image.png

$Gain(D,\text{色澤})=Ent(D)-\sum_{v=1}^{3}\frac{|D^{v}|}{|D|}Ent(D^{v})$
$=Ent(D)-(\frac{|D^{1}|}{|D|}Ent(D^{1})+\frac{|D^{2}|}{|D|}Ent(D^{2})+\frac{|D^{3}|}{|D|}Ent(D^{3}))$
$=0.998-(\frac{6}{17}\times1.00 +\frac{6}{17}\times0.918 +\frac{6}{17}\times0.722 )=0.109$