- 決策樹思想
- 特征選擇
- 信息增益與ID3
- 信息增益率與C4.5
- 基尼指數(shù)與CART
- ID3倦畅、C4.5與CART的對比
- 決策樹剪枝
- 對連續(xù)值的處理
- 對缺失值的處理
- 多變量決策樹
兩人去軒轅臺路上遇雨，郭靖道：那么咱們快跑。黃蓉搖了搖頭：靖哥哥肖卧，前面也下大雨，跑過去還不是一般的淋濕掸鹅？郭靖笑道：正是塞帐。黃蓉心中卻忽然想起了華箏之事：“前途既已注定了是憂患傷心，不論怎生走法巍沙，終究避不了葵姥、躲不開，便如長嶺遇雨一般句携±菩遥”當下兩人便在大雨中緩緩行去。# 1903 <長嶺遇雨>
一、決策樹（Decision Trees）
決策樹學習算法的構造思想很接近于人做決策的行為削咆，通過 if-then-else 的決策規(guī)則來得到結論或是進入下一次決策中牍疏。
舉個例子，例如中午到飯點了拨齐，我需要決定出去吃還是點外賣鳞陨，
- 第一個 if 是外面是否下雨了，如果沒下雨瞻惋，（then）那就出去吃厦滤，做出決定，決策結束歼狼。（else）但是如果下雨了掏导，就再看是否有人約，這就是第二次決策羽峰，依然是 if-then-else 趟咆。
- 如果有人約，那么出去吃梅屉，決策結束忍啸。沒人約，那就點外賣履植，并且沒有了其他的 if 條件可以影響決策的计雌，同樣的，決策結束玫霎。
每一次的做決策的結果都是得到結論，或是導出進一步決策的問題庶近，其考慮范圍是在上一次決策結果的限定范圍之內翁脆，例如在 “是否下雨 --> 下雨” 之后再判斷 “是否有約--> ？”鼻种，則只是在考慮下雨時是否有約的情況反番。
決策樹學習算法的目的就是創(chuàng)建一種模型，從數(shù)據(jù)特征中依據(jù)特征的重要程度一步步預測目標樣本的值叉钥。
決策樹學習算法通常包括特征選擇罢缸、決策樹生成和剪枝三個步驟。
二投队、特征選擇
特征選擇的標準有信息增益枫疆、信息增益率和基尼指數(shù), 特征選擇決定用哪個特征劃分特征空間。在介紹信息增益之前敷鸦，先來看信息熵和不純度息楔。
2.1寝贡、信息熵與不純度
熵 本來是表示分子狀態(tài)混亂程度的一個物理量，也可以作為一個系統(tǒng)的混亂程度的標準值依； 信息 是某種確定性的增加 （你掌握了某種信息圃泡，該事物的行為對你而言就可以預見，例如你上班的地方每正點和半小時有一趟車愿险，那你在家的時候就大致可以估計到下一次車什么時候來颇蜡，你趕不趕的上）。
而 信息熵 可以理解為某種信息不穩(wěn)定程度拯啦，即信息熵越小，事件越穩(wěn)定熔任，也就是發(fā)生概率越大褒链，搞清楚這個事件所需要的信息也就越小
香農用信息熵的概念來描述信源的不確定度。
而這個不穩(wěn)定程度疑苔，可以理解為“ 不純度 ”甫匹，數(shù)據(jù)的純度高，意味著在數(shù)據(jù)集里我們要分類的某一種類型的占比很高惦费，會更容易區(qū)分兵迅。例如在一個集合中，結果A占100%薪贫，B占0%恍箭，這個數(shù)據(jù)集就很純（不純度就很低），我們在進行分類時根本不需要費心瞧省。而在這個集合中扯夭，結果A占50%，B占50%鞍匾，這個數(shù)據(jù)集就很不純（不純度很高）交洗，在我們進行分類時，就很難過了橡淑，無異于隨機猜測构拳。
2.2、信息增益-ID3
在有了不純度的概念以后梁棠，我們只需要將決策分類之后的不純度和分類前的不純度相減置森，就可以得到一種純度提升值的概念。我們稱之為 信息增益 符糊。
這里給出具體的數(shù)學表達暇藏。
假定當前樣本集合 中第 k 類樣本所占的比例為
，則
的信息熵定義為
約定濒蒋，當
為0時盐碱，
把兔。
的最小值為0，最大值為
.
假定離散屬性 有
個可能的取值
,在上面吃飯的例子中瓮顽，
就有兩種可能的取值
。
如果以 屬性來對數(shù)據(jù)集
進行劃分暖混，就會產生
個分支結點缕贡，其中第
個分支結點包含了
中所有在屬性
上取值為
的樣本，記為
拣播。
什么意思呢晾咪，再拿吃飯來講，我們選取 是否下雨 這個屬性來劃分整個數(shù)據(jù)集（假設我每天中午都有記錄）贮配，就會產生 下雨 和 沒下雨 兩個分支結點谍倦，拿第一個結點 下雨 來說，第一個結點包含了我吃飯這個記錄里面所有下雨的情況泪勒，即吃飯數(shù)據(jù)集中 是否下雨 屬性值為 下雨 的樣本昼蛀。就是將數(shù)據(jù)集根據(jù)屬性的取值分為 份，每一份對應一種情況圆存，
就對應第
種情況叼旋。
解釋這么多，是因為我在第一次看的時候繞進去了沦辙，如果專業(yè)看就不用看我這些亂七八糟的例子夫植，自己理解就行。
利用信息熵的公式（1）油讯，我們可以計算出 的信息熵偷崩，再考慮到不同分支結點所包含的樣本數(shù)目不同，我們再給
的信息熵加上各自結點的權重
撞羽。而根結點是包括
中所有樣本的阐斜，同樣可計算出根節(jié)點的信息熵，這樣我們就可以得到以屬性
對樣本集
進行劃分時所獲得的 信息增益（information gain）：
著名的 ID3決策樹學習算法 就是以信息增益為準則來劃分屬性诀紊。
這里還是以西瓜為例好了谒出。
今天在肯德基看了一天書，回來聽朋友吐槽同事和直男邻奠。感覺有這么多不好的東西笤喳，人和事物，但這也正好是世界的可愛之處呀碌宴！#190311
這里是一段計算各個特征信息增益的過程杀狡，大晚上的用Markdown寫公式會頭疼睡不著的，明天白天補充
需要注意的有兩點：
1贰镣、在選擇下一結點的時候為什么不直接使用信息熵呜象，誰小就用誰膳凝，而采用信息增益多做一步減法。
2.1恭陡、在西瓜書中蹬音，選擇根結點時，比較信息增益休玩，這個時候根結點的上一結點（不存在著淆，但體現(xiàn)在計算中就是 ）選擇的是全樣本，直接分為
和
兩類來直接計算信息熵拴疤。
2.2永部、在按紋理劃分完后，計算 色澤信息增益那一步怎么都算不對呐矾，不知道哪里有問題
2.3苔埋、信息增益率與C4.5
講了這么多 ID3決策樹學習算法，但是他有問題凫佛，而且很大讲坎。在 E1 里面我們有介紹歸納偏好孕惜，而 ID3 就是很明顯的對可取值數(shù)量較多的特征有偏好。
當我們的數(shù)據(jù)里面有一項是身份信息的時候衫画，m個樣本就對應 這個特征有m種可取值毫炉，那么在計算信息增益的時候削罩，
會始終為1弥激，這時候
就為 0趾疚，那么無關于其他因素糙麦，這時候的信息增益就是
冶匹，即此時最大的信息增益（也就是此時選
特征為結點的信息熵為0）。
很多時候這種偏好是沒有意義的节值，只能造成樹生成的時候浪費內存資源徙硅。
為了解決這一問題，ID3 算法的創(chuàng)造者又對他進行了改進搞疗，采用 信息增益率 來代替信息增益作為特征選擇的準則嗓蘑。
信息增益率 就是用信息增益除一個 。
其中
稱為屬性 的固有值（instrinsic value）匿乃，屬性
的可取值數(shù)目越多（即
越大）桩皿，其固有值
通常越大。這樣就消除了使用信息增益帶來的歸納偏好問題幢炸。
但但但是泄隔，說了每一種算法都會存在歸納偏好，那采用信息增益率的這種算法它的歸納偏好是什么呢宛徊？
它所帶來的結果是消除了信息增益的偏好佛嬉，而指向了相反的一面，信息增益率對可取值數(shù)目較少的特征有所偏好闸天。
到這里你可能覺得暖呕，沒完沒了了(╯‵□′)╯︵┴─┴ 。所以苞氮，C4.5算法 并不是簡單的直接選擇信息增益率最大的候選劃分特征湾揽，而是啟發(fā)式的：先從候選劃分特征中找出信息增益高于平均水平的特征，再從中選擇信息增益率最高的
2.4笼吟、基尼指數(shù)與CART
基尼指數(shù)
后續(xù)內容库物，
三種特征選擇方法的表格比較
決策樹剪枝（預剪枝和后剪枝，生成時自上而下和生成后自下而上）
對連續(xù)值的處理
對缺失值的處理
多變量決策樹
