決策樹和隨機(jī)森林（Part1）

決策樹（decision tree）是一個(gè)樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）呼股。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測(cè)試按脚，每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹進(jìn)行決策的過程就是從根節(jié)點(diǎn)開始败京，測(cè)試待分類項(xiàng)中相應(yīng)的特征屬性，并按照其值選擇輸出分支梦染，直到到達(dá)葉子節(jié)點(diǎn)赡麦，將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果[1]
下面先來看一個(gè)小例子，看看決策樹到底是什么概念：

data1.png

決策樹的訓(xùn)練數(shù)據(jù)往往就是這樣的表格形式帕识，表中的前三列（ID不算）是數(shù)據(jù)樣本的屬性泛粹，最后一列是決策樹需要做的分類結(jié)果。通過該數(shù)據(jù)肮疗，構(gòu)建的決策樹如下：

tree_demo1.png

顯然晶姊，在每一個(gè)非葉節(jié)點(diǎn)選擇哪一個(gè)特征作為分支的標(biāo)準(zhǔn)，是構(gòu)建決策樹的核心問題伪货。

信息熵

信息熵就是解決我們上面標(biāo)準(zhǔn)選擇問題的一個(gè)重要指標(biāo)们衙。

一方面，熵是一個(gè)用來形容系統(tǒng)混亂程度的物理量碱呼。假設(shè)有135個(gè)點(diǎn) $(p_1, p_2,\ …,p_{135})$ 分布在二維平面上蒙挑，并且這些點(diǎn)分別屬于兩類。分布如下：

sample1.png

假設(shè)兩種類別的點(diǎn)（Rreen和Ged）分別有70和65個(gè)愚臀，概率分布如下：

X	G	R
P	$\frac{70}{135} =\frac{14}{27}$	$\frac{65}{130} = \frac{13}{27}$

從中隨機(jī)選擇一個(gè)點(diǎn)忆蚀，得到兩種類別的點(diǎn)的概率很相近，整個(gè)系統(tǒng)是一個(gè)完全混亂的整體姑裂。

假設(shè)我們按照?qǐng)D中的方式將所有的點(diǎn)一分為馋袜。左側(cè)有65個(gè)點(diǎn)，其中60個(gè)為Green炭分，5個(gè)為Red桃焕，則概率分布如下：

X	G	R
P	$\frac{5}{65}=\frac{1}{13}$	$\frac{60}{65}=\frac{12}{13}$

我們?cè)僭谧髠?cè)的點(diǎn)中隨機(jī)選擇，顯然屬于Green的概率要大很多捧毛，在預(yù)測(cè)的時(shí)候观堂，預(yù)測(cè)Green的正確率就高很多让网。

從兩種情況的混亂程度來看，第一種情況比第二種情況要混亂很多师痕，這種混亂程度和不同類別的概率有關(guān)溃睹。

另一方面，一個(gè)事件發(fā)生所包含的信息量和這個(gè)事件發(fā)生的概率有關(guān)的胰坟，即一個(gè)事件發(fā)生的概率越小因篇，這個(gè)事件包含的概率就越大。比如學(xué)校每天正常八點(diǎn)響鈴笔横，但是如果某一天八點(diǎn)沒有響鈴竞滓，沒有響鈴這個(gè)小概率事件包含的信息，明顯比正常響鈴這個(gè)大概率事件多吹缔。

因此商佑，概率分布就把一個(gè)事件發(fā)生所傳遞的信息和熵聯(lián)系起來了，這種熵就稱為信息熵厢塘。

信息熵的定義

假設(shè)變量 $X$ 的取值包含 $x_1, x_1, x_3,\ …, x_n$ 茶没，概率分布如下：

X	$x_1$	$x_2$	…	$x_n$
P	$p_1$	$p_2$	...	$p_n$

那么X包含的信息熵 $H(X)$ 定義為：

$H(X)=-\sum_{i}p_ilog\ p_i$

條件熵

$H(X,Y) - H(X)$ ： $(X,Y)$ 發(fā)生所包含的熵，減去 $X$ 發(fā)生所包含的熵：即在X發(fā)生的前提下晚碾，Y的發(fā)生所帶來的新的熵抓半，就是X發(fā)生的條件下，Y發(fā)生的條件熵 $H(Y|X)$ 格嘁。

接下來推導(dǎo) $H(X,Y) - H(X)$ 的計(jì)算公式：

$H(X,Y) - H(X)\\ = -\sum_{x,y}p(x,y)log\ p(x,y) + \sum_{x}p(x)log\ p(x) \\ =-\sum_{x,y}p(x,y)log\ p(x,y) + \sum_x\left(\sum_yp(x,y)\right)log\ p(x)\\ =-\sum_{x,y}p(x,y)log\ \frac{p(x,y)}{p(x)}\\ =-\sum_{x,y}p(x,y)log\ p(y | x)\\ = -\sum_x\sum_yp(x,y)log\ p(y|x)\\ =-\sum_x\sum_yp(x)p(y|x)log\ p(y|x)\\ =\sum_xp(x)\left( -\sum_yp(y|x)log\ p(y|x) \right)\\ =\sum_xp(x)H(Y|X=x)$

相對(duì)熵

相對(duì)熵又稱為互熵笛求，交叉熵，鑒定信息讥蔽，Kullback熵等涣易。

設(shè) $p(x)$ 和 $q(x)$ 是X中取值的兩種概率分布，則p對(duì)q的相對(duì)熵是：

$D(p||q) = \sum_xp(x)log\ \frac{p(x)}{q(x)} = E_{p(x)}log\ \frac{p(x)}{q(x)}$

互信息

兩個(gè)隨機(jī)變量的互信息冶伞，定義為X，Y的聯(lián)合分布和獨(dú)立分布乘積的相對(duì)熵步氏。

$I(X,Y)=D\left( P(X,Y)||P(X)P(Y) \right) = \sum_{x,y}p(x,y)log\ \frac{p(x,y)}{p(x)p(y)}$

從公式可以看出响禽，互信息其實(shí)度量的是 $P(X,Y)$ 和 $P(X)P(Y)$ 這兩個(gè)概率分布的距離。如果X和Y的分布是完全獨(dú)立的荚醒，就會(huì)有 $P(X,Y)=P(X)P(Y)$ 芋类。代入公式就可以得到兩個(gè)變量的互信息為0。

如果我們用 $H(Y)$ 減去 $I(X,Y)$ ：

$H(Y) - I(X,Y)=\\ =-\sum_{y}p(y)log\ p(y) - \sum_{x,y}p(x,y)log\ \frac{p(x,y)}{p(x)p(y)}\\ =-\sum_y\left( \sum_xp(x,y) \right)log\ p(y) - \sum_{x,y}p(x,y)log\ \frac{p(x,y)}{p(x)p(y)}\\ =-\sum_{x,y}p(x,y)log\ p(y) - \sum_{x,y}p(x,y)log\ \frac{p(x,y)}{p(x)p(y)}\\ =-\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)}\\ =-\sum_{x,y}p(x,y)log\ p(y|x)\\ =H(Y|X)$

互信息的物理意義

從上面的推到界阁，我們可以得到等式：

$H(Y|X) = H(X,Y) - H(X)$

$H(Y|X) = H(Y) - I(X,Y)$

$I(X,Y) = H(X) + H(Y) - H(X,Y)$

也可以得到不等式：

$H(X|Y)\leq H(X)$ 侯繁， $H(Y|X)\leq H(Y)$

也就是說，只要X和Y不是完全獨(dú)立泡躯，而是存在某些聯(lián)系贮竟，那么只要在給定其中一個(gè)做為條件的情況下丽焊，另一個(gè)事件所包含的信息量都會(huì)減少。

這些物理量的關(guān)系可以整理成一個(gè)Venn圖：

Venn.png

決策樹的構(gòu)建

再來看上面的例子：

tree_demo1.png

在根結(jié)點(diǎn)中咕别，是否償還債務(wù)的概率分布為：

是否償還債務(wù)	是	否
P	7	3

信息熵： $H_0 = -\frac{3}{10}log\frac{3}{10} -\frac{7}{10}log\frac{7}{10}$

在根據(jù)是否擁有房產(chǎn)進(jìn)行劃分之后：

擁有房產(chǎn)的部分：

是否償還債務(wù)	是	否
P	3	0

信息熵： $H_1=0$

沒有房產(chǎn)的部分：

是否償還債務(wù)	是	否
P	4	3

信息熵： $H_2 = -\frac{4}{7}log\frac{4}{7} - \frac{3}{7}log\frac{3}{7}$

我們考慮分支前后的熵的變化技健，對(duì)分支之后的熵求加權(quán)平均，計(jì)算可得：

$\frac{3}{10}H_1 + \frac{7}{10}H_2 < H_0$

顯然這應(yīng)該是一次有效的分支惰拱，因?yàn)殪刈冃∫馕吨w變得更加有序雌贱。從分類的直觀效果來看，對(duì)于有房產(chǎn)的樣本偿短，可以直接判斷為可以償還債務(wù)欣孤。而且很容易理解，熵下降得越快昔逗，分支就越有效导街。

決策樹學(xué)習(xí)

決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法，其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹纤子，到葉節(jié)點(diǎn)處的熵值為零搬瑰，此時(shí)每一個(gè)葉節(jié)點(diǎn)中的實(shí)力都屬于同一類。

實(shí)際過程中我們通常會(huì)采用一些剪枝的策略控硼，來避免熵值為零的情況泽论，因?yàn)殪刂禐榱阃ǔＲ馕吨鴮?duì)訓(xùn)練數(shù)據(jù)的過擬合。

建立決策樹的關(guān)鍵卡乾，即為在當(dāng)前狀態(tài)下選擇哪一個(gè)屬性作為分類依據(jù)翼悴。根據(jù)不同的目標(biāo)函數(shù)，建立決策樹主要有以下三種算法：

ID3
- Iterative Dichotomiser
C4.5
CART
- Classification and Regression Tree

信息增益

當(dāng)熵和條件中的概率由數(shù)據(jù)估計(jì)（特別是極大似然估計(jì)）得到時(shí)幔妨，所對(duì)應(yīng)的熵和條件熵分別分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵鹦赎。

信息增益表示得知特征A的信息而使得類X的信息的不確定性減少的程度。

定義：特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益 $g(D,A)$ 误堡，定義為集合D的經(jīng)驗(yàn)熵 $H(D)$ 和特征A給定條件下D的經(jīng)驗(yàn)條件熵 $H(D|A)$ 之差古话。

$g(D,A) = H(D) - H(D|A) = I(D,A)$

其他目標(biāo)

信息增益率： $g_r(D,A)=g(D,A)/H(A)?$
Gini系數(shù)

$Gini(p) = \sum_{k=1}^{K}p_i(1-p_i) = \sum_{k=1}^{K}1-p_i^2$

三種決策樹的學(xué)習(xí)策略

ID3：使用信息增益、互信息進(jìn)行特征選擇
- 取之多的屬性锁施，更容易使得數(shù)據(jù)更純陪踩，起信息增益更大
- 訓(xùn)練得到的是一棵龐大且深度淺的樹，不合理
C4.5：信息增益率 $g_r(D,A)=g(D,A)/H(A)$
CART：基尼系數(shù)

參考資料

[1]https://blog.csdn.net/xbinworld/article/details/44660339

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末悉抵，一起剝皮案震驚了整個(gè)濱河市肩狂，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌姥饰，老刑警劉巖傻谁，帶你破解...
沈念sama閱讀 212,884評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異列粪，居然都是意外死亡审磁，警方通過查閱死者的電腦和手機(jī)谈飒，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,755評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來力图，“玉大人步绸，你說我怎么就攤上這事〕悦剑” “怎么了瓤介？”我有些...
開封第一講書人閱讀 158,369評(píng)論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長赘那。經(jīng)常有香客問我刑桑，道長，這世上最難降的妖魔是什么募舟？我笑而不...
開封第一講書人閱讀 56,799評(píng)論 1贊 285
?港島之戀（遺憾婚禮）
正文為了忘掉前任祠斧，我火速辦了婚禮，結(jié)果婚禮上拱礁，老公的妹妹穿的比我還像新娘琢锋。我一直安慰自己，他們只是感情好呢灶，可當(dāng)我...
茶點(diǎn)故事閱讀 65,910評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布吴超。她就那樣靜靜地躺著，像睡著了一般鸯乃。火紅的嫁衣襯著肌膚如雪鲸阻。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 50,096評(píng)論 1贊 291
城市分裂傳說
那天缨睡，我揣著相機(jī)與錄音鸟悴，去河邊找鬼。笑死奖年，一個(gè)胖子當(dāng)著我的面吹牛细诸，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播拾并，決...
沈念sama閱讀 39,159評(píng)論 3贊 411
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼揍堰，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了嗅义？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 37,917評(píng)論 0贊 268
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤隐砸，失蹤者是張志新（化名）和其女友劉穎之碗，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體季希，經(jīng)...
沈念sama閱讀 44,360評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡褪那，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,673評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年幽纷，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片博敬。...
茶點(diǎn)故事閱讀 38,814評(píng)論 1贊 341
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡友浸，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出偏窝，到底是詐尸還是另有隱情收恢，我是刑警寧澤，帶...
沈念sama閱讀 34,509評(píng)論 4贊 334
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布祭往，位于F島的核電站伦意，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏硼补。R本人自食惡果不足惜驮肉，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 40,156評(píng)論 3贊 317
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望已骇。院中可真熱鬧离钝，春花似錦、人聲如沸褪储。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,882評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽乱豆。三九已至奖恰，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間宛裕，已是汗流浹背瑟啃。一陣腳步聲響...
開封第一講書人閱讀 32,123評(píng)論 1贊 267
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留揩尸，地道東北人蛹屿。一個(gè)月前我還...
沈念sama閱讀 46,641評(píng)論 2贊 362
代替公主和親
正文我出身青樓，卻偏偏與公主長得像岩榆，于是被迫代替她去往敵國和親错负。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,728評(píng)論 2贊 351