決策樹詳解，從熵說起
熵，一個神奇的工具，用來衡量數據集信息量的不確定性。
首先，我們先來了解一個指標，信息量。對於任意一個隨機變量X，樣本空間為{X1,X2，…,Xn},對於任意的樣本Xi，樣本Xi的信息量也就是l(Xi) = -log(p(Xi))。由於p(Xi)是為樣本Xi的概率，也可以說是類Xi的概率，那麼l(Xi)的取值範圍為(+∞，0]。也就是X的的概率越小，其含有的信息量越大，反之亦然。這也不難理解，Xi的發生的概率越大，我們對他的了解越深，那麼他所含有的信息量就越小。如果隨機變量X是常量，那麼我們從任意一個Xi都可以獲取樣本空間的值，那麼我們可以認為X沒有任何信息量，他的信息量為0。如果說，我們要把隨機變量X樣本空間都了解完，才能獲得X的信息，那麼我們可以認為X的信息量「無窮大」，其取值為log（2，n)。
緊接着，我們就提出了隨機變量X的信息熵，也就是信息量的期望，H(X) = -∑ni=1p(Xi)log2(p(Xi))，從離散的角度得出的公式。他有三個特性：
- 單調性，即發生概率越高的事件，其所攜帶的信息熵越低。極端案例就是「太陽從東方升起」，因為為確定事件，所以不攜帶任何信息量。從信息論的角度，認為這句話沒有消除任何不確定性。也就是樣本空間的p(Xi)均為1。
- 非負性，即信息熵不能為負。這個很好理解，因為負的信息，即你得知了某個信息後，卻增加了不確定性是不合邏輯的。
- 累加性，即多隨機事件同時發生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和。
有了熵這個基礎，那麼我們就要考慮決策樹是怎麼生成的了。對於隨機變量X的樣本個數為n的空間，每個樣本都有若干個相同的特徵，假設有k個。對於任意一個特徵，我們可以對其進行劃分，假設含有性別變量，那麼切分後，性別特徵消失，變為確定的值，那麼隨機變量X信息的不確定性減少。以此類推，直到達到我們想要的結果結束，這樣就生成了若干棵樹，每棵樹的不確定性降低。如果我們在此過程中進行限制，每次減少的不確定性最大，那麼這樣一步一步下來，我們得到的樹，會最快的把不確定性降低到最小。每顆樹的分支，都可以確定一個類別，包含的信息量極少，確定性極大，這種類別，是可以進行預測的，不確定性小，穩定，可以用於預測。
有了以上的知識儲備，那麼我們要想生成一顆決策樹，只需要每次把特徵的信息量最大的那個找出來進行劃分即可。也就是不確定性最大的那個分支，我們要優先劃分。這就會得出另外一個定義，條件信息熵。也就是我的
