決策樹
@(技術博客)[機器學習, 決策樹, python]
學習決策樹首先要搞清楚決策樹是什么（what）偏窝，在弄清楚決策樹是什么的過程中充包，我們也就能夠了解決策樹這個技術能夠干什么至会；其次我們需要弄清楚決策樹是怎樣（how）工作的帅矗，包括算法的工作原理观游，訓練方法等等奖慌；最后我們進一步的研究為什么（why）決策樹算法能夠從數(shù)據(jù)中學習到知識的，這是我們弄清楚決策樹算法的最終目的灸促，即從最根本的原理上給出清晰的解釋诫欠。當然了，本著理論與實踐相結合的原則浴栽，我們也會利用已有的算法庫進行一個小實驗荒叼，一來更直觀的理解決策樹，二來在具體的例子中回顧前面的what-how-why典鸡。
決策樹簡介
關于決策樹的概念被廓，我們直接引用Tom M. Mitchell在Machine Learning一書中的一段描述。
決策樹學習是應用最廣泛的歸納推理算法之一萝玷。它是一種逼近離散數(shù)值目標函數(shù)的方法嫁乘，在這種方法中學習到的函數(shù)被表示為一棵決策樹。學習得到的決策樹也能再被表示為多個if-then的規(guī)則球碉，以提高可讀性蜓斧。這種學習算法是最流行的歸納推理算法之一，已經成功的應用到從學習醫(yī)療診斷到學習評估貸款申請的信用風險的廣闊領域睁冬。經典的決策樹學習方法包括像ID3（Quinlan 1986年）挎春、ASSISTANT和C4.5（Quinlan 1993年）這樣廣為應用的算法。
在這里要說一句題外話豆拨，隨著大數(shù)據(jù)直奋、人工智能技術的興起，目前這些領域應用神經網絡進行深度學習更為流行施禾。但是想想在1986年就有決策樹這樣的算法誕生脚线，將人從重復、繁瑣的工作中釋放出來弥搞，而且效果還挺不錯的邮绿，多么令人興奮渠旁。
決策樹的表示
下面我們首先來解決第一個問題，也就是what的問題斯碌。我們依舊拿Tom大神在Machine Learning一書中的一段敘述以及例子進行學習一死。
決策樹通過把實例從根結點排列（sort）到某個葉子結點來分類實例肛度，葉子結點即為實例所屬的分類傻唾。樹上的每一個結點指定了對實例的某個屬性（attribute）的測試，并且該結點的每一個后繼分支對應于該屬性的一個可能值承耿。分類實例的方法是從這棵樹的根結點開始冠骄，測試這個結點指定的屬性，然后按照給定實例的該屬性值對應的樹枝向下移動加袋。這個過程再在以新結點為根的子樹上重復凛辣。
簡而言之，決策樹首先是一棵樹职烧。沒錯扁誓，就是數(shù)據(jù)結構中所指的樹。樹中的非葉子節(jié)點都是數(shù)據(jù)在某一維的屬性蚀之，葉子節(jié)點是數(shù)據(jù)的輸出結果蝗敢。用簡單的形式化的語言表示的話，可以令一個數(shù)據(jù)樣本為X=(x_1,x_2,...,x_n)足删，該數(shù)據(jù)樣本對應的輸出為y寿谴。那么決策樹中非葉子節(jié)點則是x_i，葉子節(jié)點則是y失受。
千言萬語不如一張圖讶泰，我們使用書中的一個例子，例子是根據(jù)當前的天氣的情況（即X）拂到，來分類“星期六上午是否適合打網球”（y）痪署。決策樹如下圖示例所示。
圖中的決策樹上非葉子節(jié)點的Outlook兄旬、Humidity狼犯、Wind既是上述的x_i，而樹干上的值即是屬性x_i對應的值辖试，例如Humidity對應的High和Normal辜王。而葉子節(jié)點Yes和No既是上述的y。例如罐孝，下面的實例：<Outlook=Sunny呐馆，Temperature=Hot，Humidity=High莲兢，Wind=Strong>將被沿著這棵決策樹的最左分支向下排列汹来，因而被評定為反例续膳，即No。
到此我們已經對決策樹的概念有了一個基本的了解收班。
- 決策樹是一棵樹坟岔。
- 決策樹是用來對離散數(shù)據(jù)進行分類的。
- 非葉子節(jié)點上是數(shù)據(jù)的某一項屬性摔桦，葉子節(jié)點是數(shù)據(jù)的分類結果社付。
基礎的決策樹學習算法
在弄清楚what問題后，我們下一步的疑惑便是決策樹是怎么生成的邻耕，即給了你一組樣本數(shù)據(jù)后鸥咖，如何從數(shù)據(jù)中學習出來這一棵神奇的決策樹。話不多說兄世，我們開始圍繞how這一個主題來繼續(xù)啼辣。
大多數(shù)已開發(fā)的決策樹學習算法是一種核心算法的變體。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間御滩。也就是說決策樹的學習問題可以看做是一個搜索問題鸥拧，是從由數(shù)據(jù)各個維度的屬性張成的空間中，搜索得到一個合適的解的過程削解。這一核心算法是ID3算法（Quinlan 1986）和后繼的C4.5算法（Quinlan 1993）的基礎富弦，我們選擇這一基本的算法進行討論學習。
基本的ID3算法通過自頂向下構造決策樹來進行學習钠绍。那么我們就要問了舆声，該選擇哪一個屬性作為根節(jié)點來進行測試呢？答曰：選擇分類能力最好的屬性作為根節(jié)點柳爽。我們又要問了媳握，什么樣的屬性我們可以說它的分類能力好？這里我們先賣個關子磷脯，種個草蛾找，回頭再來拔草。我們先保持思路繼續(xù)往前赵誓。當我們選擇了分類能力最好的屬性作為根節(jié)點后打毛，那么所有的數(shù)據(jù)根據(jù)該屬性可以分成幾個分支（分支的個數(shù)即屬性的取值個數(shù)）。在不同分支下的數(shù)據(jù)俩功，我們又可以按照上面的操作幻枉，選擇分支下的自數(shù)據(jù)集里分類能力最好的屬性作為“根”節(jié)點（即分支里的根節(jié)點）。如此迭代诡蜓，就可以得到一棵決策樹熬甫。聽起來，挺簡單的吧蔓罚。
好了椿肩，我們發(fā)現(xiàn)算法的核心是如何選取每一個節(jié)點要測試的屬性瞻颂，我們希望是選擇的屬性是有助于分類的，也就是上面所提到的分類能力強郑象。那么啥叫分類能力強呢贡这？這里我們就要定義一個統(tǒng)計數(shù)值，稱作信息增益（information gain）**厂榛，我們用這個屬性來衡量屬性的分類能力盖矫。一看到“信息”這兩個字，我們立刻就會聯(lián)想到熵噪沙。沒錯炼彪，就是香農提出的信息熵（你大爺還是你大爺，提出來的東西應用就那么廣泛正歼，計算機網絡中也有我，機器學習依舊還有我）拷橘。關于信息熵更多的知識局义，大家可以去閱讀更多的文章。繼續(xù)回到主題冗疮，信息增益如何定義呢萄唇？我們先回顧下信息熵的概念，對于一個隨機變量x术幔，令它的概率密度為p(x)另萤，不失一般性的我令x是一個離散變量，那么x的信息熵可表示為H(x)=-\sum_x{p(x)\log_2{p(x)}}
我們把上述的隨機變量替換成一個數(shù)據(jù)集合诅挑，就可以得到一個數(shù)據(jù)集合的信息熵四敞。舉個例子，S是一個相對于某個布爾分類的14個樣例的集合拔妥，包含9個正例和5個反例忿危。那么S相對于這個布爾分類的信息熵為Entropy(S)=-(9/14)\log_2{9/14}-5/14\log_2{5/14}=0.940
已經有了信息熵作為信息的衡量標準，那么我們可以進一步的定義信息增益没龙。
信息增益就是由于使用這個屬性分割樣本數(shù)據(jù)集而導致的信息熵的降低铺厨。
我們可以這樣來理解，使用某個屬性分割樣本數(shù)據(jù)集硬纤，相當于我們獲取了數(shù)據(jù)中這一個屬性的信息解滓。使用這個屬性對數(shù)據(jù)集進行分類，使得我們對于數(shù)據(jù)集的了解更加清晰筝家，信息熵便會下降洼裤。信息熵下降前后的差值既是該屬性的信息增益。形式化的表示如下所示肛鹏，
Gain(S,A)=Entropy(S)-\sum_{v \in Values(A)} \frac{|S_v|}{|S|}Entropy(S_v)
其中Values(A)代表屬性A的取值集合逸邦，S_v是S中屬性A取值為v的集合恩沛。所以Gain(S,A)是由于給定了屬性A的值而導致的信息熵的減少（熵代表的是系統(tǒng)的混沌狀態(tài)，給定了信息后缕减，系統(tǒng)的熵值減少雷客，意味著狀態(tài)更加確定）。換句話來講桥狡，Gain(S,A)是由于給定屬性A的值而得到的關于目標函數(shù)值的信息搅裙。當對S的一個任意成員的目標值編碼時，Gain(S,A)的值是在知道屬性A的值后可以節(jié)省的二進制位數(shù)裹芝。說到這里大家是不是想起一種編碼方式部逮？是的，沒錯嫂易，就是哈夫曼編碼（Huffman Coding）兄朋，在這里就不展開討論了，依舊還是站在香農的肩膀上怜械。
好了颅和，又到了舉例子的時候了。為了演示ID3算法的具體操作缕允，考慮使用下表中的訓練數(shù)據(jù)來進行峡扩。
這里，目標屬性PlayTennis對于不同的星期六上午具有yes和no兩個值障本，我們將根據(jù)其他屬性來預測這個目標屬性值教届。首先考慮算法的第一步，選擇哪一個屬性作為根節(jié)點驾霜。ID3算法將計算每一個候選屬性（Outlook案训、Temperature、Humidity寄悯、Wind）的信息增益萤衰，然后選擇其中最高的一個。我們可以計算得到
Gain(S,Outlook)=0.246
Gain(S,Humidity)=0.151
Gain(S,Wind)=0.048
Gain(S,Temperature)=0.029
所以Outlook被作為根節(jié)點的決策屬性猜旬，并為它的每一個可能值（也就是Sunny脆栋，Overcast和Rain）在根結點下創(chuàng)建分支。部分決策樹的結果顯示在圖1中洒擦，同時畫出的還有被排列到每個新的后繼結點的訓練樣例椿争。注意到每一個Outlook=Overcast的樣例也都是PlayTennis的正例。所以熟嫩，樹的這個結點成為一個葉子結點秦踪，它對目標屬性的分類是PlayTennis=Yes。相反，對應Outlook=Sunny和Outlook=Rain的后繼結點還有非0的熵椅邓，所以決策樹會在這些結點下進一步展開柠逞。
對于非終端的后繼結點，再重復前面的過程選擇一個新的屬性來分割訓練樣例景馁，這一次僅使用與這個結點關聯(lián)的訓練樣例板壮。已經被收編入樹的較高結點的屬性被排除在外，以便任何給定的屬性在樹的任意路徑上最多僅出現(xiàn)一次合住。對于每一個新的葉子結點繼續(xù)這個過程绰精，直到滿足以下兩個條件中的任一個：
- 所有的屬性已經被這條路徑包括。
- 與這個結點關聯(lián)的所有訓練樣例都具有同樣的目標屬性值（也就是它們的熵為0）透葛。
決策樹學習的歸納偏置
ID3算法從觀測到的訓練數(shù)據(jù)泛化以分類未見實例的策略是什么呢笨使？換句話說，它的歸納偏置是什么僚害？這也是就關于why的問題硫椰。
如果給定一個訓練樣例的集合，那么我們能夠找到很多決策樹來滿足這個訓練樣例集合贡珊，為什么ID3算法從千千萬萬（也許實際上沒那么多）棵樹中選擇了這一棵呢最爬？ID3選擇在使用簡單到復雜的爬山算法遍歷可能的樹空間時遇到的第一個可接受的樹。概略地講门岔，ID3的搜索策略為：
- 優(yōu)先選擇較短的樹而不是較長的樹。
- 選擇那些信息增益高的屬性離根結點較近的樹烤送。
近似的ID3算法歸納偏置：較短的樹比較長的優(yōu)先寒随。那些信息增益高的屬性更靠近根結點的樹得到優(yōu)先。
那么為什么優(yōu)先最短的假設呢帮坚？ID3算法中優(yōu)選較短決策樹的歸納偏置妻往，是不是從訓練數(shù)據(jù)中泛化的可靠基礎？哲學家們以及其他學者已經對這樣的問題爭論幾個世紀了试和，而且這個爭論至今還未解決讯泣。威廉?奧坎姆大約在1320年提出類似的論點 ，是最早討論這個問題的人之一阅悍，所以這個偏置經常被稱為“奧坎姆剃刀”（Occam’s razor）好渠。
奧坎姆剃刀：優(yōu)先選擇擬合數(shù)據(jù)的最簡單假設。
這個問題就顯得很哲學了节视。在回歸問題里拳锚，我們也能找到類似的例子，例如給了一個九個點的樣本數(shù)據(jù)寻行，我們總能找到一個多項式y=\sum_{i=0}^8{w_ix^i}霍掺，使得這條曲線完美的穿過這9個點，但是這樣一條曲線真的能代表這些數(shù)據(jù)的實際情況么。例如杆烁，數(shù)據(jù)點是關于房子面積和房價的數(shù)據(jù)（扎心了吧）牙丽。顯然這樣一條曲線的泛化能力是很差的。所以奧坎姆剃刀法則是對“Simple is best”的詮釋兔魂。
當然給出一個歸納偏置的名字不等于證明了它烤芦。為什么應該優(yōu)先選擇較簡單的假設呢？請注意科學家們有時似乎也遵循這個歸納偏置入热。例如物理學家優(yōu)先選擇行星運動簡單的解釋拍棕，而不用復雜的解釋。為什么勺良？一種解釋是短假設的數(shù)量少于長假設（基于簡單的參數(shù)組合）绰播，所以找到一個短的假設但同時它與訓練數(shù)據(jù)擬合的可能性較小。相反尚困，常常有很多非常復雜的假設擬合當前的訓練數(shù)據(jù)蠢箩，但卻無法正確地泛化到后來的數(shù)據(jù)。例如考慮決策樹假設事甜。500個結點的決策樹比5個結點的決策樹多得多谬泌。如果給定一個20個訓練樣例的集合，可以預期能夠找到很多500個結點的決策樹與訓練數(shù)據(jù)一致逻谦，而如果一個5結點的決策樹可以完美地擬合這些數(shù)據(jù)則是出乎意外的掌实。所以我們會相信5個結點的樹不太可能是統(tǒng)計巧合，因而優(yōu)先選擇這個假設邦马，而不選擇500個結點的贱鼻。
關于why問題的討論就到這里，其實還有很多的解釋以及可以探討的地方滋将，大家可以閱讀更多的材料來解開謎題邻悬。
代碼示例
在這部分，我們將使用scikit-learn（python語言編寫的機器學習包）中的決策樹算法庫來進行演示随闽。實際動手操作總歸會帶來對算法不一樣的感受父丰。上文中我們只是對最基礎的決策樹算法ID3進行了理論分析和算法描述，而scikit-learn中包含的決策樹算法多種多樣掘宪。但是核心思想大同小異蛾扇，更詳細的算法細節(jié)大家可以閱讀大神們的論文、python源碼或者文檔說明進行了解添诉。
代碼如下：
from sklearn.datasets import load_iris
from sklearn import tree
import pydotplus
iris = load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)
dot_data = tree.export_graphviz(clf, out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True, rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data)
graph.write_pdf("iris.pdf")
數(shù)據(jù)集是鳶尾植物數(shù)據(jù)庫花瓣以及萼片的長和寬共四項數(shù)據(jù)屁桑，輸出為鳶尾植物的種類setosa、versicolor和virginica三種（更多的信息在代碼里debug下栏赴，觀察iris變量即可）蘑斧。最后的分類輸出如下圖。
我們得到了一棵通過學習算法學習得到的決策樹。這里我們可以看到我們沒有使用信息熵當做選擇根節(jié)點的依據(jù)竖瘾，而是選擇了gini值沟突，本著學一練二考三的科研訓練方法（大學本科某著名教授所提出的，這樣的強度確實酸爽）捕传，留給大家自己去探索更多的細節(jié)惠拭。
小結
文章對機器學習中最基礎的一種分類算法，決策樹庸论，進行了由淺及深的探討职辅。算是機器學習的入門算法，但是其中包含的學習的思想還是意味深遠聂示。接下來會和大家探討更多的機器學習算法以及目前流行的深度學習算法域携。
