### 分類（Classification） 分類預測的是分類標號，什么是分類標號呢？ 分類標號是離散值，比如把一個群體分成屌絲、土豪、高富帥三類，分類標號則分別是屌絲、土豪、高富帥。再比如把土豪分為小土豪、大土豪、高級土豪，可以根據月收入來分，5000以下的為小土豪，5000到0000的為大土豪，10000以上的為高級土豪。所以，分類標號需要離散化。 分類是預測的一種，預測的是分類標號，即把沒有分類標號的群體分到有分類標號的群體里，也就完成了分類，具體如何分類則需要分類算法。 不管使用什么算法，分類過程主要有兩個步驟，如下圖表示。  在分類算法中，比較基礎的有樸素貝葉斯分類與貝葉斯網絡兩種分類算法。這兩種算法都以貝葉斯定理為基礎，可以對分類及決策問題進行概率推斷。這個在之后再討論。 在這一篇文章中，將討論一種被廣泛使用的歸納推理算法——決策樹（decision tree）。它是一種逼近離散值函數的方法，對噪聲數據有很良好的健壯性且能夠學習析取表達式。相比貝葉斯算法，決策樹的優勢在于構造過程不需要任何領域知識或參數設置，因此在實際應用中，對于探測式的知識發現，決策樹更加適用。 ### 決策樹（Decision Tree） 通俗來說，決策樹分類的思想類似于找對象。現想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話： > 女兒：多大年紀了？ 母親：26。 女兒：長的帥不帥？ 母親：挺帥的。 女兒：收入高不？ 母親：不算很高，中等情況。 女兒：是公務員不？ 母親：是，在稅務局上班呢。 女兒：那好，我去見見。 這個女孩的決策過程就是典型的分類樹決策。相當于通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見。假設這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務員，那么這個可以用下圖表示女孩的決策邏輯。  上圖完整表達了這個女孩決定是否見一個約會對象的策略，其中綠色節點表示判斷條件，橙色節點表示決策結果，箭頭表示在一個判斷條件在不同情況下的決策路徑，圖中紅色箭頭表示了上面例子中女孩的決策過程。 這幅圖基本可以算是一顆決策樹，說它“基本可以算”是因為圖中的判定條件沒有量化，如收入高中低等等，還不能算是嚴格意義上的決策樹，如果將所有條件量化，則就變成真正的決策樹了。 有了上面直觀的認識，我們可以正式定義決策樹了： 決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。其每個非葉節點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節點存放一個類別。使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。 可以看到，決策樹的決策過程非常直觀，容易被人理解。目前決策樹已經成功運用于醫學、制造產業、天文學、分支生物學以及商業等諸多領域。知道了決策樹的定義以及其應用方法，下面介紹決策樹的構造算法。 ### 決策樹的構造 不同于貝葉斯算法，決策樹的構造過程不依賴領域知識，它使用屬性選擇度量來選擇將元組最好地劃分成不同的類的屬性。所謂決策樹的構造就是進行屬性選擇度量確定各個特征屬性之間的拓撲結構。 構造決策樹的關鍵步驟是分裂屬性。所謂分裂屬性就是在某個節點處按照某一特征屬性的不同劃分構造不同的分支，其目標是讓各個分裂子集盡可能地“純”。盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類別。分裂屬性分為三種不同的情況： 1、屬性是離散值且不要求生成二叉決策樹。此時用屬性的每一個劃分作為一個分支。 2、屬性是離散值且要求生成二叉決策樹。此時使用屬性劃分的一個子集進行測試，按照“屬于此子集”和“不屬于此子集”分成兩個分支。 3、屬性是連續值。此時確定一個值作為分裂點split_point，按照>split_point和<=split_point生成兩個分支。 構造決策樹的關鍵性內容是進行屬性選擇度量，屬性選擇度量是一種選擇分裂準則，是將給定的類標記的訓練集合的數據劃分D“最好”地分成個體類的啟發式方法，它決定了拓撲結構及分裂點split_point的選擇。 屬性選擇度量算法有很多，一般使用自頂向下遞歸分治法，并采用不回溯的貪心策略。這里介紹[ID3](http://en.wikipedia.org/wiki/ID3_algorithm)和[C4.5](http://en.wikipedia.org/wiki/C4.5_algorithm)兩種常用算法。 ### ID3算法 從[信息論](http://en.wikipedia.org/wiki/Information_theory)知識中我們直到，期望信息越小，[信息增益](http://en.wikipedia.org/wiki/Information_gain)越大，從而純度越高。所以ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進行分裂。下面先定義幾個要用到的概念。 設D為用類別對訓練元組進行的劃分，則D的[熵（entropy）](http://en.wikipedia.org/wiki/Entropy)表示為： info(D)=?∑i=1mpilog2(pi) 其中pi表示第i個類別在整個訓練元組中出現的概率，可以用屬于此類別元素的數量除以訓練元組元素總數量作為估計。熵的實際意義表示是D中元組的類標號所需要的平均信息量。 現在我們假設將訓練元組D按屬性A進行劃分，則A對D劃分的期望信息為： infoA(D)=∑j=1v|Dj||D|info(Dj) 而信息增益即為兩者的差值： gain(A)=info(D)?info(D) ID3算法就是在每次需要分裂時，計算每個屬性的增益率，然后選擇增益率最大的屬性進行分裂。下面我們繼續用SNS社區中不真實賬號檢測的例子說明如何使用ID3算法構造決策樹。為了簡單起見，我們假設訓練集合包含10個元素：  我們也介紹一下這里面的專有名詞： - 日至密度、好友密度、是否使用真實的頭像——條件屬性 - 賬號是否為真實——決策屬性 其中s、m和l分別表示小、中和大。 設L、F、H和R表示日志密度、好友密度、是否使用真實頭像和賬號是否真實，下面計算各屬性的信息增益。 info(D)=?0.7log20.7?0.3log20.3=0.879 infoL(D)=0.3?(?03log203?33log233)+0.4?(?14log214?34log234)+0.3?(?13log213?23log223)=0.603 因此日志密度的信息增益是0.276。 用同樣方法得到H和F的信息增益分別為0.033和0.553。 因為F具有最大的信息增益，所以第一次分裂選擇F為分裂屬性，分裂后的結果如下圖表示：  在上圖的基礎上，再遞歸使用這個方法計算子節點的分裂屬性，最終就可以得到整個決策樹。 上面為了簡便，將特征屬性離散化了，其實日志密度和好友密度都是連續的屬性。對于特征屬性為連續值，可以如此使用ID3算法： 先將D中元素按照特征屬性排序，則每兩個相鄰元素的中間點可以看做潛在分裂點，從第一個潛在分裂點開始，分裂D并計算兩個集合的期望信息，具有最小期望信息的點稱為這個屬性的最佳分裂點，其信息期望作為此屬性的信息期望。 ID3算法存在一些問題： - (1)信息增益的計算依賴于特征數目較多的特征，而屬性取值最多的屬性并不一定最優。 - (2)ID3是非遞增算法。 - (3)ID3是單變量決策樹(在分枝節點上只考慮單個屬性)，許多復雜概念的表達困難，屬性相互關系強調不夠，容易導致決策樹中子樹的重復或有些屬性在決策樹的某一路徑上被檢驗多次。 - (4)抗噪性差，訓練例子中正例和反例的比例較難控制。 由于ID3算法在實際應用中存在一些問題，于是Quilan提出了C4.5算法，嚴格上說C4.5只能是ID3的一個改進算法。 ### C4.5算法 ID3算法存在一個問題，就是偏向于多值屬性，例如，如果存在唯一標識屬性ID，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。ID3的后繼算法C4.5使用[增益率（gain ratio）](http://en.wikipedia.org/wiki/Information_gain_ratio)的信息增益擴充，試圖克服這個偏倚。 C4.5算法首先定義了“分裂信息”，其定義可以表示成： split_infoA(D)=?∑j=1v|Dj||D|log2(|Dj||D|) 其中各符號意義與ID3算法相同，然后，增益率被定義為： gainratio(A)=gain(A)split_info(A) C4.5選擇具有最大增益率的屬性作為分裂屬性，其具體應用與ID3類似，不再贅述。 ### 舉例 ### 代碼