是使用頻率最高的數(shù)據(jù)挖掘算法，原因是不需要了解機(jī)器學(xué)習(xí)的知識也能搞明白決策樹是怎么工作。
優(yōu)勢：數(shù)據(jù)形式非常容易理解，可以從不熟悉的數(shù)據(jù)集合中提取出一系列規(guī)則，計算復(fù)雜度不高，對中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)
缺點：可能會產(chǎn)生過度匹配問題
使用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型
基尼不純度：從一個數(shù)據(jù)集中隨機(jī)選取子項，度量其被錯誤分類到其他分組里的概率。
信息增益：計算每個特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇
熵定義為信息的期望值，如果待分類的事務(wù)可能劃分在多個分類中，則符號Xi的信息定義為l(Xi)=-lgP(Xi),P(Xi)是選擇該分類的概率，所有類別所有可能值包含的信息期望值E=-∑P(Xi)lgP(Xi)
算法流程：?
每次遍歷特征，對數(shù)據(jù)集按此特征進(jìn)行劃分后，計算數(shù)據(jù)集的新熵值，并對所以唯一特征值得到的熵求和，和越小，劃分結(jié)果越有序，用此特征劃分效果越好。
遞歸構(gòu)建決策樹， 直到遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，或者每個分枝下的所有實例都具有相同的分類
C4.5
信息增益準(zhǔn)則會對可能取值數(shù)目較多的屬性有所偏好，為了減少這種偏好帶來的不良影響，考慮內(nèi)在信息量，使用信息增益率
特征的重要性會隨著其內(nèi)在信息（Intrinsic Information）的增大而減小。 信息增益率作為一種補(bǔ)償（Compensate）措施來解決信息增益所存在的問題，但是它也有可能導(dǎo)致過分補(bǔ)償，而選擇那些內(nèi)在信息很小的特征，這一點可以嘗試：首先，僅考慮那些信息增益超過平均值的特征，其次再比較信息增益。
CART
使用基尼不純度進(jìn)行劃分
隨后選擇最小的Gini(T)作為結(jié)點劃分決策樹
剪枝
解決決策樹學(xué)習(xí)算法中過擬合
預(yù)剪枝： 在決策樹生成過程中，對每個節(jié)點在劃分前先進(jìn)行估計，如不能帶來泛化性能提高，則停止劃分
后剪枝：在生成完決策樹后，自底向上對非葉子節(jié)點進(jìn)行考察，如將其替換為葉子節(jié)點后泛化性能提升，則將該子樹替換為葉節(jié)點。
泛化性能的考察可以使用留出法:即留出一部分樣本用作測試。
數(shù)值型屬性的轉(zhuǎn)化
如密度，長度等，采用二分法轉(zhuǎn)化
如20個密度數(shù)據(jù)，進(jìn)行排序后相鄰兩個數(shù)據(jù)進(jìn)行折中，Ta = { ai+ai+1/2 1<=i<=n-1}
那么每個決策點的含義變?yōu)??“密度是否>Ta”,相當(dāng)于額外再增加N-1個屬性，但感覺這么做在數(shù)據(jù)量大的時候效率衰減會很快
缺失值的處理
可以采取加入權(quán)重的方法，表示這條數(shù)據(jù)可能處于這個劃分集的概念，對于屬性不缺失的數(shù)據(jù)，權(quán)重為1，對于剩余的，權(quán)重為元樣本中的概率分布
在計算信息增益的時候先不考慮屬性缺失數(shù)據(jù)，待確定劃分屬性后，將這條在該屬性上數(shù)據(jù)缺失的數(shù)據(jù)以原樣本中的概率分布分別加入到劃分的下一層去
多變量決策樹
軸平行是一般決策樹的決策邊界的特點，但存在一些情況需要多段劃分才能取得較好的近似
如某個決策點變?yōu)?-0.8*密度-0.44*含糖率<=-0.333
主要算法有OC1，先貪心的尋找每個屬性的最優(yōu)權(quán)值，在局部優(yōu)化的基礎(chǔ)上再對分類邊界進(jìn)行隨機(jī)擾動以試圖找到更好的邊界，
