機器學習_決策樹與資訊熵

1。 決策樹

決策樹（Decision Tree）是一種預測模型；它是透過一系列的判斷達到決策的方法。下面是一個判斷是否買房的例子，一共15個例項，有Age， Has_job， Own_house， Credit_rating四個屬性，樹的各個分叉是對屬性的判斷，葉子是各分枝的例項個數。

決策樹

這是個很簡單的例子，只用了兩層，每個葉子節點就得到了一致的結果（如2/2），如果不一致，則會使用其它屬性遞迴地劃分，直到屬性用完，或分支下得到一致的結果，或者滿足一定停止條件。對於有歧義的葉子節點，一般用多數表決法。 決策樹的優點是複雜度低，輸出結果直觀，對中間值缺失不敏感；缺點是可能過擬合，有時用到剪枝的方法避免過擬合。 決策樹的原理看起來非常簡單，但在屬性值非常多，例項也非常多的情況下，計算量是龐大的，我們需要採用一些最佳化演算法：先判斷哪些屬性會帶來明顯的差異，於是引出了資訊量的問題。

2。 資訊量

意外越大，越不可能發生，機率就越小，資訊量也就越大，也就是資訊越多。比如說“今天肯定會天黑”，實現機率100%，說了和沒說差不多，資訊量就是0。 資訊量= log2（1/機率）=log2（機率^-1）=-log2（機率），log2是以2為底的對數。 舉個例子：擲色子每個數有1/6的可能性，即log2（6）=2。6，1-6的全部可能性，二進位制需要3位描述（3>2。6）；拋硬幣正反面各1/2可能性，log（2）=1，二進位制用一位即可描述，相比之下，擲色子資訊量更大。

3。 熵

熵=H=-sum（機率*log2（機率）），可以看到它是資訊量的期望值，描述的也是意外程度，即不確定性。0

4。 資訊量與熵

分類越多->資訊量越大->熵越大，如圖所示：圖C將點平均分成5類（熵為2。32），圖B將點平均分成兩類（熵為1），則看起來C更復雜，更不容易被分類，熵也更大。 分類越平均->熵越大。圖B（熵為1）比A（熵為0。72）更復雜，更不容易被分類，熵也更大。

5。 資訊增益

資訊增益（Information Gain）：熵A-條件熵B，是資訊量的差值。也就是說，一開始是A，用了條件後變成了B，則條件引起的變化是A-B，即資訊增益（它描述的是變化Delta）。好的條件就是資訊增益越大越好，即變化完後熵越小越好（熵代表混亂程度，最大程度地減小了混亂）。因此我們在樹分叉的時候，應優先使用資訊增益最大的屬性，這樣降低了複雜度，也簡化了後邊的邏輯。

6。 舉例

假設使用8天股票資料例項，以次日漲/跌作為目標分類，紅為漲，藍為跌，如上圖所示漲跌機率各50%：50%（2分類整體熵為1），有D，E，F三個屬性描述當日狀態，它們分別將樣本分為兩類：方和圓，每類四個。D中方和圓中漲跌比例各自為50%：50%（條件熵為1，資訊增益0）。E中方的漲跌比例為25%：75%，圓的漲跌比例為75%：25%（條件熵為0。81，資訊增益0。19），F中方的漲跌比例為0：%：100%，圓的漲跌比例為100%：0%（條件熵為0，資訊增益1）。 我們想要尋找的屬性是可直接將樣本分成正例和反例的屬性，像屬性F為圓一旦出現，第二天必大漲，而最沒用的是D，分類後與原始集合正反比例相同。E雖然不能完全確定，也使我們知道當E為圓出現後，比較可能漲，它也帶有一定的資訊。 使用奧卡姆剃刀原則：如無必要，勿增實體。不確定有用的就先不加，以建立最小的樹。比如，如個屬性X（代表當日漲幅），明顯影響第二天，則優先加入，屬性Y（代表當天的成交量），單獨考慮Y，可能無法預測第二天的漲跌，但如果考慮當日漲幅X等因素之後，成交量Y就可能變為一個重要的條件，則後加Y。屬性Z（隔壁張三是否買了股票），單獨考慮Z，無法預測，考慮所有因素之後，Z仍然沒什麼作用。因此屬性Z最終被丟棄。策略就是先把有用的挑出來，不知道是不是有用的往後放。

7。 熵的作用

熵是個很重要的屬性，它不只是在決策樹裡用到，各個分類器都會用到這個量度。比如說，正例和反例為99：1時，全選正例的正確率也有99%，這並不能說明演算法優秀。就像在牛市裡能掙錢並不能說明水平高。另外分成兩類，隨機選的正確率是50%；分而三類，則為33%，並不是演算法效果變差了。在看一個演算法的準確率時，這些因類都要考慮在內。在多個演算法做組合時，也應選擇資訊增益大的放在前面。 在決策樹中利用熵，可以有效地減小樹的深度。計算每種分類的熵，然後優先熵小的，依層次劃分資料集。熵的演算法，一般作為決策樹的一部分，把它單拿出來，也可以用它篩選哪個屬性是最直接影響分類結果的。

8。 計算熵的程式

#-*- coding： utf-8 -*- import math def entropy（*c）： if（len（c）<=0）： return -1 result = 0 for x in c： result+=（-x）*math。log（x，2） return result； if （__name__==“__main__”）： print（entropy（0。99，0。01））；

9。 決策樹的核心程式（1） 軟體安裝

ubuntu系統

$sudo pip install sklearn $ sudo pip install pydotplus $ sudo apt-get install graphviz

（1） 程式碼

#訓練決策樹 X_train， X_test， y_train ，y_test = cross_validation。train_test_split（X，y，test_size=0。2） clf = tree。DecisionTreeClassifier（max_depth=5） clf。fit（X_train，y_train） accuracy = clf。score（X_test，y_test） print（“accuracy：”，accuracy） # 生成決策樹圖片 dot_data = StringIO（） tree。export_graphviz（clf，out_file=dot_data， feature_names=［“open”，“high”，“low”，“close”，“turnover”］， filled=True，rounded=True， impurity=False） graph = pydotplus。graph_from_dot_data（dot_data。getvalue（）） open（‘/tmp/a。jpg’，‘wb’）。write（graph。create_jpg（））

10。 如何看待決策樹的結果

使用sklearn的tree訓練資料後，可得到準確度評分。如果資料集中包含大量無意義的資料，評分結果可能不是很高。但是從圖的角度看，如果某一個葉子節點，它的例項足夠多，且分類一致，有的情況下，我們可以把這個判斷條件單獨拿出來使用。 使用一個模型，不是丟進一堆資料，訓練個模型，看個正確率，預測一下就完了。要需要仔細去看樹中的規則。樹本身就是一個無序到有序的變化過程。