決策樹是什么
決策樹(Decision Tree）是在已知各種情況發(fā)生概率的基礎(chǔ)上荣回，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率渐溶，評價項目風(fēng)險博脑，判斷其可行性的決策分析方法讲竿，是直觀運(yùn)用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干笑旺，故稱決策樹。在機(jī)器學(xué)習(xí)中馍资，決策樹是一個預(yù)測模型筒主，他代表的是對象屬性與對象值之間的一種映射關(guān)系。Entropy = 系統(tǒng)的凌亂程度鸟蟹，使用算法ID3,C4.5和C5.0生成樹算法使用熵乌妙。這一度量是基于信息學(xué)理論中熵的概念。
決策樹是一種樹形結(jié)構(gòu)建钥，其中每個內(nèi)部節(jié)點表示一個屬性上的測試藤韵，每個分支代表一個測試輸出，每個葉節(jié)點代表一種類別熊经。
分類樹（決策樹）是一種十分常用的分類方法泽艘。他是一種監(jiān)管學(xué)習(xí)，所謂監(jiān)管學(xué)習(xí)就是給定一堆樣本镐依，每個樣本都有一組屬性和一個類別匹涮，這些類別是事先確定的，那么通過學(xué)習(xí)得到一個分類器槐壳，這個分類器能夠?qū)π鲁霈F(xiàn)的對象給出正確的分類然低。這樣的機(jī)器學(xué)習(xí)就被稱之為監(jiān)督學(xué)習(xí)。
信息熵與最優(yōu)劃分
1）決策樹算法的思想
解決分類問題時务唐，決策樹算法的任務(wù)是構(gòu)造決策樹模型雳攘，對未知的樣本進(jìn)行分類；
決策樹算法利用了信息熵和決策樹思維：
信息熵越小的數(shù)據(jù)集绍哎，樣本的確定性越高来农，當(dāng)數(shù)據(jù)集的信息熵為 0 時，該數(shù)據(jù)集中只有一種類型的樣本崇堰；
訓(xùn)練數(shù)據(jù)集中有很多類型的樣本沃于，通過對數(shù)據(jù)集信息熵的判斷，逐層劃分?jǐn)?shù)據(jù)集海诲，最終將每一類樣本單獨劃分出來繁莹；
劃分?jǐn)?shù)據(jù)集的方式有很多種，只有當(dāng)按樣本類別劃分?jǐn)?shù)據(jù)集時（也就是兩部分?jǐn)?shù)據(jù)集中不會同時存在相同類型的樣本）特幔，劃分后的兩部分?jǐn)?shù)據(jù)集的整體的信息熵最凶裳荨；反相推斷蚯斯，當(dāng)兩部分?jǐn)?shù)據(jù)集的整體的信息熵最小時薄风，則兩部分?jǐn)?shù)據(jù)集中不會同時存在相同類型的樣本饵较；
2）劃分步驟
劃分點：某一特征的某一個數(shù)值；（根據(jù)該特征值對數(shù)據(jù)集樣本進(jìn)行劃分）
數(shù)據(jù)集中樣本的排序：根據(jù)特征的數(shù)值大小進(jìn)行排序遭赂；
（一般不直接打亂原始數(shù)據(jù)集中樣本的排列順序循诉，而是使用 np.argsorted( 特征向量 )，返回特征向量中元素排序后對應(yīng)的 index）
選取劃分點：要沒有遺漏的迭代所有情況的劃分點對應(yīng)的劃分情況撇他；
將特征值排序后茄猫，從 0 號開始，選取相鄰的但不相等的兩個特征值的平均數(shù)作為一個劃分點困肩；按此方式迭代找出一組特質(zhì)向量中的所有劃分點划纽；
3）劃分結(jié)果
兩種數(shù)據(jù)集：X_left、X_right 機(jī)器對應(yīng)的 y锌畸；
特征類型勇劣，及其最優(yōu)的劃分點的特征值；
Cart生成算法：
最小二乘回歸樹生成算法
之所以稱為最小二乘回歸樹芭毙，是因為，回歸樹以誤差平方和為準(zhǔn)則選擇最優(yōu)二分切點卸耘，該生成算法在訓(xùn)練數(shù)據(jù)集上所在的輸入空間中，遞歸的將每個區(qū)域劃分為兩個子區(qū)域并決定每個子區(qū)域的輸出值粘咖，在這里分為兩種情況蚣抗，一是輸出值為子區(qū)域輸出值的均值該種情況下為回歸樹，二是輸出值為子區(qū)域輸入與輸出的線性回歸瓮下，輸出值為回歸系數(shù)翰铡，該種情況下為模型樹。
算法實現(xiàn)步驟：
1）選擇最優(yōu)切分特征J與切分點s讽坏，按照如下原則：
minj,s[minc1∑(yi?c1)+minc2∑(yi?c2)]minj,s[minc1∑(yi?c1)+minc2∑(yi?c2)]
c1,c2c1,c2分別為左右子區(qū)域輸出的均值（模型樹時是輸出變量的回歸值）锭魔，可通過遍歷每個變量的每個可能取值來切分?jǐn)?shù)據(jù)集找出最優(yōu)切分點。
2）用切分點劃分區(qū)域并決定相應(yīng)的輸出值
3）遞歸調(diào)用1）2）直到滿足停止條件
4）利用字典路呜，遞歸調(diào)用創(chuàng)建二叉樹迷捧，生成決策樹
CART生成算法（分類樹）
在這里需要提一下基尼系數(shù)：
在分類問題中，假設(shè)有KK類胀葱，樣本點屬于第kk類的概率為pkpk,則概率分布的基尼指數(shù)定義為：
Gini(p)=∑Kk=1pk(1?pk)=(p1+p2+...+pK)?∑Kk=1p2k=1?∑Kk=1p2kGini(p)=∑k=1Kpk(1?pk)=(p1+p2+...+pK)?∑k=1Kpk2=1?∑k=1Kpk2
對于分類問題：設(shè)CkCk為DD中屬于第kk類的樣本子集漠秋，則基尼指數(shù)為：
Gini(D)=1?∑Kk=1(|Ck||D|)2Gini(D)=1?∑k=1K(|Ck||D|)2
設(shè)條件AA將樣本DD切分為D1D1和D2D2兩個數(shù)據(jù)子集，則在條件AA下的樣本DD的基尼指數(shù)為：
Gini(D,A)=|D1|DGini(D1)+|D2|DGini(D2)Gini(D,A)=|D1|DGini(D1)+|D2|DGini(D2)
注意：基尼指數(shù)也表示樣本的不確定性抵屿，基尼指數(shù)值越大庆锦，樣本集合的不確定性越大。
算法實現(xiàn)步驟：
1）計算現(xiàn)有樣本DD的基尼指數(shù)轧葛，之后利用樣本中每一個特征AA搂抒，及AA的每一個可能取值aa艇搀，根據(jù)A>=aA>=a與A<aA<a將樣本分為兩部分，并計算Gini(D,A)Gini(D,A)值
2）找出對應(yīng)基尼指數(shù)最小Gini(D,A)Gini(D,A)的最優(yōu)切分特征及取值求晶，并判斷是否切分停止條件中符，否，則輸出最優(yōu)切分點
3）遞歸調(diào)用1）2）
4）生成CART決策樹
