#決策樹簡介#
決策樹（Decision Tree）是一種簡單但是廣泛使用的分類器碉输。通過訓(xùn)練數(shù)據(jù)構(gòu)建決策樹籽前，可以高效的對未知的數(shù)據(jù)進(jìn)行分類。
決策數(shù)有兩大優(yōu)點(diǎn)：1）決策樹模型可以讀性好敷钾，具有描述性枝哄，有助于人工分析；2）效率高阻荒，決策樹只需要一次構(gòu)建挠锥，反復(fù)使用，每一次預(yù)測的最大計算次數(shù)不超過決策樹的深度侨赡。
決策樹的主要算法有ID3蓖租，C4.5，CART羊壹。其中C4.5是對于ID3的優(yōu)化蓖宦。本周主要就是學(xué)習(xí)了ID3算法的過程，基于我自己編的一組數(shù)據(jù)：
#基礎(chǔ)概念-信息熵#
信息是個很抽象的概念油猫。人們常常說信息很多稠茂，或者信息較少，但卻很難說清楚信息到底有多少情妖。比如一本五十萬字的中文書到底有多少信息量睬关。
直到1948年，香農(nóng)提出了“信息熵”的概念毡证，才解決了對信息的量化度量問題电爹。香農(nóng)從熱力學(xué)中借用過來的。熱力學(xué)中的熱熵是表示分子狀態(tài)混亂程度的物理量料睛。香農(nóng)用信息熵的概念來描述信源的不確定度丐箩。
假如事件A的全概率劃分是（A1,A2,...,An），每部分發(fā)生的概率是(p1,p2,...,pn)秦效，那信息熵定義為：
log通常以2為底數(shù)雏蛮，所以信息熵的單位是bit涎嚼。
#構(gòu)造決策樹-樹根#
構(gòu)造樹的基本想法是隨著樹深度的增加阱州，節(jié)點(diǎn)的熵迅速地降低。熵降低的速度越快越好法梯，因?yàn)檫@樣得到的樹的高度最矮苔货。讓熵減小犀概，就是說讓確定性增加，也就是越來越能夠做出判斷夜惭。
我們的例子中姻灶，最開始如果病人的任何特征都不看，根據(jù)歷史的數(shù)據(jù)诈茧，知道病人感冒的概率是1/2产喉，過敏的概率1/6，腦震蕩概率1/3敢会。此時的熵為：
E = -（1/2）×log（1/2）-（1/6）×log（1/6）-（1/3）×log（1/3）= 1.459
然后看特征曾沈，病人的特征有三個，癥狀鸥昏、職業(yè)塞俱、性別，我們要選擇一個作為樹根吏垮，先把原始6個病人情況做成一張表：
先看癥狀這個特征：
癥狀為“打噴嚏”的有3人障涯，2個感冒，1個過敏膳汪，因此打噴嚏時唯蝶，2/3概率感冒，1/3概率過敏遗嗽，0概率腦震蕩生棍，此時熵為：
-（2/3）×log（2/3）-（1/3）×log（1/3）= 0.918
癥狀為“頭疼”的有3人，1個感冒媳谁，2個腦震蕩涂滴，因此頭疼時，1/3概率感冒晴音，2/3概率腦震蕩柔纵，0概率過敏，此時熵為：
-（1/3）×log（1/3）-（2/3）×log（2/3）= 0.918
從整體看锤躁，一共6個人搁料，3個打噴嚏，3個頭疼系羞，因此郭计，打噴嚏和頭疼的概率都是1/2
所以已知特征“癥狀”的情況，總系統(tǒng)的信息熵為0.918×1/2+0.918×1/2 = 0.918椒振，
信息增益Gain（癥狀）=1.459-0.918= 0.541
再看“職業(yè)”這個特征：
職業(yè)為“護(hù)士”的有1人昭伸，1個感冒。因此職業(yè)為護(hù)士澎迎，1概率感冒庐杨，0概率其他病选调，熵為0
職業(yè)為“農(nóng)民”的有1人，1個過敏灵份。因此職業(yè)為農(nóng)民仁堪，1概率過敏，0概率其他病填渠，熵為0
職業(yè)為“工人”的有2人弦聂，1個感冒，1個腦震蕩氛什。因此職業(yè)為工人横浑，1/2概率感冒，1/2概率腦震蕩屉更，0概率過敏徙融，熵：
-（1/2）×log（1/2）-（1/2）×log（1/2）= 1
職業(yè)為“教師”的有2人，1個感冒瑰谜，1個腦震蕩欺冀。因此職業(yè)為教師，1/2概率感冒萨脑，1/2概率腦震蕩隐轩，0概率過敏，熵：
-（1/2）×log（1/2）-（1/2）×log（1/2）= 1
從整體看渤早，一共6個人职车，1護(hù)士，1農(nóng)民鹊杖，2工人悴灵，2教師，因此護(hù)士和農(nóng)民的概率都是1/6骂蓖，工人和教師概率都是1/3积瞒，所以已知特征“職業(yè)”的情況，總系統(tǒng)的信息熵為：
1/6 ×0 +1/6×0 +1/3×1+1/3×1=0.667登下，
信息增益Gain（職業(yè)）=1.459-0.667= 0.792
再看“性別”這個特征:
性別為“男”有2人茫孔，1過敏，1腦震蕩被芳，因此性別為男缰贝，1/2概率過敏，1/2概率腦震蕩畔濒，0概率感冒剩晴，熵為：
-（1/2）×log（1/2）-（1/2）×log（1/2）= 1
性別為“女”有4人，3個感冒篓冲，1個腦震蕩李破，因此性別為女，3/4概率感冒壹将，1/4概率腦震蕩嗤攻，熵為：
-（3/4）×log（3/4）-（1/4）×log（1/4）= 0.811
從整體看，一共6個人诽俯，2男4女妇菱，因此男概率1/3，女概率2/3暴区，已知性別的情況下闯团，總系統(tǒng)的信息熵為
1×1/3+0.811×2/3=0.874
信息增益Gain（性別）=1.459-0.874=0.585
可見“職業(yè)”讓總系統(tǒng)的信息熵下降的更快，決策樹的根就是職業(yè)仙粱，如下圖：
在護(hù)士和農(nóng)民分支房交，剛才已經(jīng)計算了熵為0，意味著已經(jīng)沒有任何不確定性了（給出的6個病人的數(shù)據(jù)也能看出來）伐割，可以直接判斷病情候味。
#構(gòu)造決策樹-其他枝葉#
構(gòu)造枝葉的方法和構(gòu)造樹根一樣，只是考慮的病人的范圍不同隔心。
接下來確定N1白群，方法類似，現(xiàn)在只需要考慮職業(yè)為“工人”的這個子系統(tǒng)硬霍，還是列一個表：
剛才已經(jīng)計算過帜慢，職業(yè)為工人的系統(tǒng)信息熵為1
先看癥狀這個特征:
癥狀為打噴嚏的沒有，熵為0
癥狀為頭疼的有2人唯卖，1人感冒粱玲，1人腦震蕩，因此“頭疼工人”里拜轨，1/2概率感冒密幔，1/2概率腦震蕩，熵為：
-（1/2）×log（1/2）-（1/2）×log（1/2）= 1
總的系統(tǒng)信息熵為1撩轰，沒有任何變化
再看性別這個特征
性別為男1人胯甩，是腦震蕩，因此“男工人”里堪嫂，腦震蕩概率1偎箫，其他概率0，熵為0
性別為女1人皆串，是感冒淹办，因此“女工人”里，感冒概率1恶复，其他概率0怜森，熵為0
總的系統(tǒng)熵為0速挑，把總系統(tǒng)熵一下降低為0
因此，N1就應(yīng)該選擇性別作為分支副硅，然后分支的熵都為0了姥宝，也就都能確定病情了。
接下來確定N2恐疲，方法類似腊满，現(xiàn)在只需要考慮職業(yè)為“教師”的這個子系統(tǒng)，還是列一個表：
每個分支的熵都為0省咨，總系統(tǒng)的熵也就為0肃弟，決策樹構(gòu)造完畢，最終如圖：
#判定規(guī)則#
決策樹比較直觀零蓉，好理解愕乎，關(guān)鍵就在于構(gòu)造完成之后可以演變成一條一條的判定規(guī)則。本例中：
IF 職業(yè)為護(hù)士 THEN 感冒
IF 職業(yè)為農(nóng)民 THEN 過敏
IF 職業(yè)為工人壁公，性別為男 THEN 腦震蕩
……
#其他#
構(gòu)造過程中感论，可能發(fā)生屬性用完還是沒有最終判定的情況（也就是葉子節(jié)點(diǎn)還是有很多可能性），那么就選擇最大可能性的判定作為判定（選判定結(jié)果最多的）
連續(xù)型數(shù)據(jù)的屬性紊册，ID3沒法處理（個人理解也可以預(yù)先進(jìn)行離散化操作比肄，例如分段處理，然后在構(gòu)造決策樹）
決策樹還有一個非常重要的問題是過度擬合囊陡，因?yàn)槭?00%按照給定的訓(xùn)練數(shù)據(jù)構(gòu)造的樹芳绩，訓(xùn)練數(shù)據(jù)中的噪音數(shù)據(jù)等都生成了特定的分支，應(yīng)用的時候就會發(fā)生錯誤率很高的問題撞反。對于決策樹妥色，必須要進(jìn)行剪枝。
