決策樹：
ID3：其核心是在決策樹的各級節(jié)點上伯诬，實用信息增益（information gain）作為屬性的選擇標準晚唇，來幫助確定生成每個節(jié)點是所應采用的合適屬性。ID3只是用于處理離散的描述屬性盗似。
C4.5: 相對于ID3的改進是使用信息增益率來選擇節(jié)點屬性哩陕。C4.5技能處理離散的描述屬性，也能處理連續(xù)的描述屬性赫舒。
CART：是一種十分有效的非參數分類和回歸方法悍及，通過構建樹、修剪樹接癌、評估樹來構建二叉樹心赶。當終結點是連續(xù)變量時，該樹為回歸樹缺猛；當終結點是分類變量時缨叫，該樹為分類樹。
ID3：基于信息增益選擇最佳屬性枯夜，構造一棵信息熵值下降最快的樹弯汰，樹不斷構建的過程也就是熵不斷下降的過程艰山。
信息熵：H(X) 描述X攜帶的信息量湖雹。 信息量越大（值變化越多，把事情搞清楚所需要的信息量就越多）曙搬，則越不確定摔吏，越不容易被預測鸽嫂。表示隨機變量的不確定性。
條件熵：在一個條件下征讲，隨機變量的不確定性据某。
信息增益IG(Y|X):?衡量一個屬性(x)區(qū)分樣本(y)的能力；在一個條件下诗箍，信息不確定性減少的程度癣籽。?當新增一個屬性(x)時，信息熵H(Y)的變化大小即為信息增益滤祖。 IG(Y|X)越大表示x越重要筷狼。
信息增益例子：明天下雨例如信息熵是2，條件熵（下雨|陰天）是0.01（因為如果是陰天就下雨的概率很大匠童，信息就少了）埂材，這樣相減后為1.99，在獲得陰天這個信息后汤求，下雨信息不確定性減少了1.99俏险！是很多的！所以信息增益大扬绪！也就是說竖独，陰天這個信息對下雨來說是很重要的！
采用劃分后樣本集的不確定性來作為衡量劃分好壞的標準挤牛，用信息增益值度量不確定性：信息增益越大预鬓，不確定性就越小。ID3在每個非葉節(jié)點選擇信息增益最大的屬性作為測試屬性赊颠，這樣可以得到當前情況下最純（最極端的情況是每個葉子節(jié)點只有一個樣本）的拆分格二，從而得到較小的決策樹。
定義：特征A對訓練集D的信息增益g(D,A)竣蹦，定義為集合D的經驗熵H(D)與特征A給定條件下D的經驗條件熵H(D|A)之差：
可以轉化得到：
建模步驟：
1. 對當前樣本集合顶猜，計算所有屬性的信息增益
2. 選擇信息增益最大的屬性作為測試屬性，把測試屬性取值相同的樣本化為同一個樣本集
3. 若子樣本集的類別墅型只有單個屬性痘括，則為葉子節(jié)點长窄，判斷其屬性值并標上相應的符號，然后返回調用處纲菌；否則對子樣本集本算法
C4.5: 基于信息增益率（gain ratio）的ID3改進版挠日。ID3不足在于選擇具體特征作為節(jié)點的時候，它會偏向于選擇取值較多的特征翰舌。一個極端情況是：以是否出去玩為例嚣潜，假設新來的一列特征為partner，有n個取值椅贱，且每個取值只有一條記錄懂算，則特征的信息熵為0只冻，
這樣的信息增益是最大的计技，必然選擇此特征為節(jié)點喜德，但是結果是樹很龐大而深度很淺，泛化預測能力較差垮媒。
IV(A): 屬性A的可能取值數目越多舍悯，則IV(A)的值通常越大。
這里的IV(A)也叫做split information
*注：
增益率準則對可取值數目較小的特征有所偏好睡雇，所以C4.5并不是直接選增益率最大的候選劃分特征贱呐，而是使用了一個啟發(fā)式：先從候選劃分特征中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的入桂。
對連續(xù)屬性的處理如下：
1.??????對特征的取值進行升序排序
2.??????兩個特征取值之間的中點作為可能的分裂點奄薇，將數據集分成兩部分，計算每個可能的分裂點的信息增益（InforGain）抗愁。優(yōu)化算法就是只計算分類屬性發(fā)生改變的那些特征取值馁蒂。
3.??????選擇修正后信息增益(InforGain)最大的分裂點作為該特征的最佳分裂點
4.??????計算最佳分裂點的信息增益率（Gain Ratio）作為特征的Gain Ratio。注意蜘腌，此處需對最佳分裂點的信息增益進行修正：減去log2(N-1)/|D|（N是連續(xù)特征的取值個數沫屡，D是訓練數據數目，此修正的原因在于：當離散屬性和連續(xù)屬性并存時撮珠，C4.5算法傾向于選擇連續(xù)特征做最佳樹分裂點）
CART(Classification And Regression Tree): 使用基尼指數（Gini index）來選擇劃分特征沮脖。該算法是一種二分遞歸分割法，把擋墻的樣本集合劃分為兩個子集合芯急，它生成的每個非葉子節(jié)點都只有兩個分支（binary tree）勺届。
基尼指數：表示數據的不純度性，基尼指數越大娶耍，越不平等免姿。總體內包含的類別越雜亂榕酒，GINI指數就越大（跟熵的概念很相似）
給定一個數據集D胚膊，其中包含的分類類別總數為K，類別k在數據集中的個數為|C|,其Gini指數表示為：
在候選特征集合A中想鹰，選擇那個使得劃分后基尼指數最小的特征為最優(yōu)化分數性紊婉，即：
a* = arg min GiniIndex(D,a)
小節(jié)：
算法????支持模型????樹結構????特征選擇? ? ? ? ? ? ?連續(xù)值處理????缺失值處理????剪枝? ? ? ? 樣本量
ID3? ? ?分類????????????多叉樹? ? ?信息增益? ? ? ? ? ? 不支持? ? ? ? ? 不支持? ? ? ? ? ? 不支持? ? ? ? /
C4.5? ?分類????????????多叉樹? ? ?信息增益比? ? ? ? ?支持? ? ? ? ? ? ?支持? ? ? ? ? ? ? ? 支持? ? ? ? ?小樣本（大樣本耗時）
CART分類|回歸? ? ?二叉樹? ? 基尼系數|均方差? 支持? ? ? ? ? ? 支持? ? ? ? ? ? ? ? ?支持? ? ? ? 大樣本（小樣本泛化誤差大）
決策樹算法優(yōu)缺點：
優(yōu)點：
1.簡單直觀
2.基本不需要數據預處理，歸一化辑舷，處理缺失值
3.預測代價O(logm)喻犁，m為樣本數
4.適用于離散和連續(xù)數據
4.邏輯上可以較好的解釋，相較于神經網絡的黑盒
5.可以用交叉驗證的剪枝來提高泛化能力
6.對異常點容錯能力好
缺點：
1.非常容易過擬合≈旰海可以通過設置節(jié)點樣本數量和先知決策樹深度以及后剪枝來改進
2.樹的結構會因為樣本的一點點改動而劇烈改變「柩辏可以通過集成學習方法改進
3.因為是貪心算法乔妈，只能確定局部最優(yōu)。通過集成學習改進
4.如果某特征樣本比例過大氓皱，生成的決策樹容易偏向這些特征路召，造成欠擬合〔ú模可以通過調節(jié)樣本權重來改進股淡。
信息熵越大，不純度越高廷区，信息越雜亂
剪枝pruning
預剪枝是指在決策樹生成過程中唯灵，對每個結點在劃分前先進行估計，若當前結點的劃分不能帶來決策樹泛化能力（在訓練時加入驗證集隨時進行泛化驗證）的提升隙轻，則停止劃分并將當前結點標記為葉節(jié)點埠帕。
根據不同決策樹算法，防止過擬合的參數有一些不同玖绿，但max_depth是通用的敛瓷；其他的一些參數：
min_samples_split：節(jié)點在分裂之前必須具有的最小樣本數。也就是斑匪，如果該節(jié)點上的樣本數量小于參數設置的數目時呐籽，不管怎樣，這個節(jié)點也不再分裂蚀瘸。
min_samples_leaf：葉節(jié)點必須擁有的最少樣本數狡蝶。如果分裂一個節(jié)點生成一些葉子，而某個葉子上的樣本數量少于參數設置的值時贮勃，將不將這些樣本單獨作為一個葉子牢酵。
min_weight_fraction_leaf：和上面一個參數差不多，但表示為加權實例總數的一小部分衙猪。
max_leaf_nodes：葉子節(jié)點的最大數量馍乙。
后剪枝則是先從訓練集中生成一顆完整的樹，然后自底向上對非葉節(jié)點進行考察垫释，若該節(jié)點對應的子樹替換為葉節(jié)點能夠提升泛化能力丝格，則進行剪枝將該子樹替換為葉節(jié)點，否則不剪枝棵譬。
評價函數：類似損失函數显蝌，越小越好。?
隨機森林random forest
bootstraping：有放回的抽樣
bagging：有放回的采樣n個樣本建立一個分類器
