寫在前面的話：哈嘍，大家早安教寂、午安页慷、晚安嘍憔足，歡迎大家指點，也希望我的內(nèi)容可以溫暖酒繁、幫助同在學習路上的人們~
正文開始~~
再次申明：本文的理論知識來自Peter Harrington的《機器學習實戰(zhàn)》和李航的《統(tǒng)計學習方法》滓彰，非常感謝這些優(yōu)秀人物和優(yōu)秀書籍
決策樹(decision tree)算法簡介：決策樹算法思想主要來源于由Quinlan在1986年提出的IID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART(分類回歸決策樹)州袒。決策樹算法是一種基本的分類與回歸算法揭绑。決策樹學習通常包括3個步驟：特征選擇、決策樹的生成和決策樹的修剪郎哭。本文僅討論用于分類的決策樹他匪。
分類決策樹工作原理：分類決策樹模型是一種描述對實例進行分類的樹形結(jié)構(gòu)。決策樹由結(jié)點(node)和有向邊(directed node)組成夸研。結(jié)點分兩類：內(nèi)部結(jié)點(internal tree)和葉結(jié)點(leaf node)邦蜜。內(nèi)部結(jié)點表示一個特征或?qū)傩裕~結(jié)點表示一個類亥至。分類決策樹學習的算法通常是一個遞歸地選擇最優(yōu)特征悼沈，并根據(jù)該特征對訓練數(shù)據(jù)進行分割，使得對各個子數(shù)據(jù)集有一個最好的分類的過程姐扮。這一過程對應著對特征空間的劃分絮供，也對應著決策樹的構(gòu)建。開始茶敏，構(gòu)建根結(jié)點壤靶，將所有訓練數(shù)據(jù)都放在根結(jié)點。選擇一個最優(yōu)特征惊搏，按照這一特征將訓練數(shù)據(jù)集分割成子集贮乳，使得各個子集有一個在當前條件下最好的分類忧换。如果這些子集已經(jīng)能夠被基本正確分類，那么構(gòu)建葉結(jié)點塘揣，并將這些子集分到所對應的葉結(jié)點中去包雀；如果還有子集不能被基本正確分類宿崭，那么就對這些子集選擇新的最優(yōu)特征亲铡，繼續(xù)對其進行分割，構(gòu)建相應的結(jié)點葡兑。如此遞歸地進行下去奖蔓，直至所有訓練數(shù)據(jù)子集被基本正確分類，或者沒有合適的特征為止讹堤。最后每個子集都被分到葉結(jié)點上吆鹤，即都有了明確的類，最終生成了一顆決策樹洲守。以上方法生成的決策樹可能對訓練數(shù)據(jù)有很好的分類能力疑务，但對未知的測試數(shù)據(jù)卻并未有很好的分類能力，可能發(fā)生過擬合梗醇，因此需要對生成的決策樹自下而上剪枝知允，將樹變得簡單，從而使他具有更好的泛化能力叙谨。
分類決策樹算法的實現(xiàn)：
流程：1）收集數(shù)據(jù)：可以使用任何方法温鸽；2）準備數(shù)據(jù)：構(gòu)造算法只適用于標稱型數(shù)據(jù)，因此數(shù)值型數(shù)據(jù)必須離散化手负；3）分析數(shù)據(jù)：可以使用任何方法涤垫，構(gòu)造樹完成之后，應該檢查圖形是否符合預期竟终；4）訓練算法：構(gòu)造樹的數(shù)據(jù)結(jié)構(gòu)蝠猬；5）測試算法：使用經(jīng)驗樹計算錯誤率；6）使用算法：此步驟可以適用于任何監(jiān)督學習算法,而使用決策樹可以更好地理解數(shù)據(jù)的內(nèi)在含義统捶。
特征選擇：在上述第3）步中榆芦，決策樹通過信息增益來選擇特征，進而構(gòu)建決策樹瘾境。給定訓練數(shù)據(jù)集D和特征A歧杏，經(jīng)驗熵H(D)表示對數(shù)據(jù)集D進行分類的不確定性。而經(jīng)驗條件熵H(D|A)表示在特征A給定的條件下對數(shù)據(jù)集D進行分類的不確定性迷守。那么它們的差犬绒，即信息增益，就表示由于特征A而使得對數(shù)據(jù)集D的分類的不確定性減少的程度兑凿。顯然凯力，對于數(shù)據(jù)集D而言茵瘾，信息增益依賴于特征，不同的特征往往具有不同的信息增益咐鹤。信息增益大的特征具有更強的分類能力拗秘。
分類決策樹的Python實現(xiàn)
1）利用香農(nóng)熵公式計算整個數(shù)據(jù)集的信息熵，代碼見圖1
2）基于某一特征祈惶，會劃分數(shù)據(jù)集雕旨，代碼見圖2
3）通過計算信息增益，找讓信息增益最大的特征捧请，也就是最好的分類特征凡涩，代碼見圖3
4）逐步遞歸，構(gòu)建決策樹
遞歸的結(jié)束條件：1）程序遍歷完所有劃分數(shù)據(jù)集的屬性疹蛉。此時存在的一種情況是數(shù)據(jù)集以及處理了所有屬性活箕，但是類標簽依然不是唯一的，此時需要決定改如何定義該葉結(jié)點可款，一般采用多數(shù)表決的方法育韩；2）每個分支下的所有實例都具有相同的分類。如果所有實例具有相同的分類闺鲸，則得到一個葉子節(jié)點或者終止塊筋讨。任何到達葉子節(jié)點的數(shù)據(jù)必然屬于葉子節(jié)點的分類。
5）基于Matplotlib模塊來繪制決策樹翠拣。其中版仔，Matplotlib的一些繪圖操作可以查看Matplotlib官方文檔、Matplotlib博客等误墓。
好啦蛮粮，以上基本就是基于Python的決策樹實現(xiàn)算法，感覺自己還是不熟悉這塊兒谜慌，希望得到大神指導或者大家分享一些棒棒噠的學習資源哈然想，提前謝謝大家啦~~
同樣，接下來將基于scikit-learn的相關模型來實現(xiàn)決策樹算法欣范，敬請期待哈~~
