1 從LR到?jīng)Q策樹

相信大家都做過用LR來進(jìn)行分類，總結(jié)一下LR模型的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)

• 適合需要得到一個(gè)分類概率的場景。
• 實(shí)現(xiàn)效率較高。
• 很好處理線性特征。

缺點(diǎn)

• 當(dāng)特征空間很大時(shí)，邏輯回歸的性能不是很好。
• 不能很好地處理大量多類特征。
• 對于非線性特征，需要進(jìn)行轉(zhuǎn)換。

以上就是LR模型的優(yōu)缺點(diǎn)，沒錯(cuò)，決策樹的出現(xiàn)就是為了解決LR模型不足的地方，這也是我們?yōu)槭裁匆獙W(xué)習(xí)決策樹的原因了，沒有任何一個(gè)模型是萬能的。

決策樹（Decision Tree）
在數(shù)據(jù)挖掘領(lǐng)域，比較經(jīng)典的分類算法有：決策樹算法、貝葉斯網(wǎng)絡(luò)算法、人工神經(jīng)網(wǎng)絡(luò)算法、支持向量機(jī)以及其它一些基于關(guān)聯(lián)規(guī)則的算法等。國際權(quán)威的學(xué)術(shù)組織the IEEE International Conference on Data Mining（ICDM）曾在21世紀(jì)初期，將兩種決策樹算法（C4.5算法和CART算法）列入數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法之中?？梢姏Q策樹算法優(yōu)良的結(jié)構(gòu)特性和算法效率，使其得到更多專家學(xué)者的一致認(rèn)可。

決策樹（Decision Tree），又稱判斷樹，它是一種以樹形數(shù)據(jù)結(jié)構(gòu)來展示決策規(guī)則和分類結(jié)果的模型，作為一種歸納學(xué)習(xí)算法，其重點(diǎn)是將看似無序、雜亂的已知實(shí)例，通過某種技術(shù)手段將它們轉(zhuǎn)化成可以預(yù)測未知實(shí)例的樹狀模型，每一條從根結(jié)點(diǎn)（對最終分類結(jié)果貢獻(xiàn)最大的屬性）到葉子結(jié)點(diǎn)（最終分類結(jié)果）的路徑都代表一條決策的規(guī)則。決策樹算法的優(yōu)勢在于，它不僅簡單易于理解，而且高效實(shí)用，構(gòu)建一次，就可以多次使用，或者只對樹模型進(jìn)行簡單的維護(hù)就可以保持其分類的準(zhǔn)確性。

決策樹

決策樹算法采用自上至下遞歸建樹的技術(shù)，該算法的產(chǎn)生源于CLS系統(tǒng)，即概念學(xué)習(xí)系統(tǒng)，下圖展示一個(gè)CLS系統(tǒng)的簡易模型。該模型是決策樹發(fā)展的理論基礎(chǔ)，該模型定義了一個(gè)學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)。

CLS系統(tǒng)的簡易模型

J.R.Quinlan在上世紀(jì)80年代提出了ID3（Iterative Dichotomiser 3）算法，該算法奠定了日后決策樹算法發(fā)展的基礎(chǔ)。這種算法的提出得益于，香農(nóng)（Shannon C E.）在信息論中提出的信息熵的概念，其表示離散隨機(jī)事件出現(xiàn)的概率。ID3算法最核心的思想，就是以信息增益作為分裂屬性選取的依據(jù)，信息增益表示某個(gè)屬性能夠?yàn)榉诸愊到y(tǒng)帶來多少“信息”，信息越多，則通過該屬性對數(shù)據(jù)集的分類更為準(zhǔn)確。ID3算法適用于大多數(shù)據(jù)集的分類問題，分類速度和測試速度都比較快。但該算法在設(shè)計(jì)之初未考慮如何處理連續(xù)屬性、屬性缺失以及噪聲等問題。之后，隨后J.R.Quinlan針對ID3算法的不足設(shè)計(jì)了C4.5算法，引入信息增益率的概念。它克服了ID3算法無法處理屬性缺失和連續(xù)屬性的問題，并且引入了優(yōu)化決策樹的剪枝方法，使算法更高效，適用性更強(qiáng)。

Breiman.L.I等人在1984年提出了CART（Classification and Regression Tree）算法，即分類回歸樹算法。CART算法用基尼指數(shù)（Gini Index）代替了信息熵，用二叉樹作為模型結(jié)構(gòu)，所以不是直接通過屬性值進(jìn)行數(shù)據(jù)劃分，該算法要在所有屬性中找出最佳的二元?jiǎng)澐?。CART算法通過遞歸操作不斷地對決策屬性進(jìn)行劃分，同時(shí)利用驗(yàn)證數(shù)據(jù)對樹模型進(jìn)行優(yōu)化。

1996年Shafer.J.C等人提出了一種可伸縮的并行歸納決策樹算法，SPRINT算法（Scalable Parallelizable Induction of Decision Trees），通過并行運(yùn)算增加決策效率，增強(qiáng)了算法的的擴(kuò)展性和可伸縮性。同一年Mehta.M等人提出了C4.5算法的改進(jìn)算法SLIQ算法，該算法采用屬性表、分類表、類直方圖的策略來解決內(nèi)存溢出的問題。Cehrke.J等人設(shè)計(jì)了雨林（Rain Forest）算法，提高了對大數(shù)據(jù)集進(jìn)行分類的能力。2000年Rastogi.R等人以CART算法為理論基礎(chǔ)，提出了PUBLIC（A Decision Tree Classifier that Integrates Building and Pruning）算法，剪枝策略更加高效。

當(dāng)今社會(huì)，信息化得程度日益提高，人們被各種數(shù)據(jù)所包圍。數(shù)據(jù)挖掘作為一種新興的學(xué)術(shù)領(lǐng)域，它的發(fā)展極大的促進(jìn)了人們對海量數(shù)據(jù)中所蘊(yùn)含的知識的認(rèn)識程度。數(shù)據(jù)挖掘最根本的目的就是，通過各種有效的技術(shù)手段，在已知的數(shù)據(jù)中探尋有價(jià)值的信息。決策樹分類算法，作為一種簡單高效、容易理解的啟發(fā)式算法，有著廣泛的應(yīng)用領(lǐng)域。近年來隨著模糊理論與決策樹的融合，使得該算法更為智能，更符合人的思維方式，極大的擴(kuò)展了其應(yīng)用范圍。

決策樹的優(yōu)點(diǎn)

• 模擬人的直觀決策規(guī)則。
• 可以處理非線性特征。
• 考慮了特征之間的相互作用。

其實(shí)用一下圖片能更好的理解LR模型和決策樹模型算法的根本區(qū)別，我們可以思考一下一個(gè)決策問題：是否去相親，一個(gè)女孩的母親要給這個(gè)女海介紹對象。

大家都看得很明白了吧！LR模型是一股腦兒的把所有特征塞入學(xué)習(xí)，而決策樹更像是編程語言中的if-else一樣，去做條件判斷，這就是根本性的區(qū)別。

2 “樹”的成長過程

決策樹基于“樹”結(jié)構(gòu)進(jìn)行決策的，這時(shí)我們就要面臨兩個(gè)問題 ：

• “樹”怎么長。
• 這顆“樹”長到什么時(shí)候停。

弄懂了這兩個(gè)問題，那么這個(gè)模型就已經(jīng)建立起來了，決策樹的總體流程是“分而治之”的思想，一是自根至葉的遞歸過程，一是在每個(gè)中間節(jié)點(diǎn)尋找一個(gè)“劃分”屬性，相當(dāng)于就是一個(gè)特征屬性了。接下來我們來逐個(gè)解決以上兩個(gè)問題。

這顆“樹”長到什么時(shí)候停

• 當(dāng)前結(jié)點(diǎn)包含的樣本全屬于同一類別，無需劃分；例如：樣本當(dāng)中都是決定去相親的，屬于同一類別，就是不管特征如何改變都不會(huì)影響結(jié)果，這種就不需要?jiǎng)澐至恕?/li>
• 當(dāng)前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分；例如：所有的樣本特征都是一樣的，就造成無法劃分了，訓(xùn)練集太單一。
• 當(dāng)前結(jié)點(diǎn)包含的樣本集合為空，不能劃分。

3 “樹”怎么長

在生活當(dāng)中，我們都會(huì)碰到很多需要做出決策的地方，例如：吃飯地點(diǎn)、數(shù)碼產(chǎn)品購買、旅游地區(qū)等，你會(huì)發(fā)現(xiàn)在這些選擇當(dāng)中都是依賴于大部分人做出的選擇，也就是跟隨大眾的選擇。其實(shí)在決策樹當(dāng)中也是一樣的，當(dāng)大部分的樣本都是同一類的時(shí)候，那么就已經(jīng)做出了決策。

我們可以把大眾的選擇抽象化，這就引入了一個(gè)概念就是純度，想想也是如此，大眾選擇就意味著純度越高。好，在深入一點(diǎn)，就涉及到一句話：信息熵越低，純度越高。我相信大家或多或少都聽說過“熵”這個(gè)概念，信息熵通俗來說就是用來度量包含的“信息量”，如果樣本的屬性都是一樣的，就會(huì)讓人覺得這包含的信息很單一，沒有差異化，相反樣本的屬性都不一樣，那么包含的信息量就很多了。

一到這里就頭疼了，因?yàn)轳R上要引入信息熵的公式，其實(shí)也很簡單：

Pk表示的是：當(dāng)前樣本集合D中第k類樣本所占的比例為Pk。

信息增益
廢話不多說直接上公式：

3.1 ID3算法

解釋：在根節(jié)點(diǎn)處計(jì)算信息熵，然后根據(jù)屬性依次劃分并計(jì)算其節(jié)點(diǎn)的信息熵，用根節(jié)點(diǎn)信息熵--屬性節(jié)點(diǎn)的信息熵=信息增益，根據(jù)信息增益進(jìn)行降序排列，排在前面的就是第一個(gè)劃分屬性，其后依次類推，這就得到了決策樹的形狀，也就是怎么“長”了。

不過，信息增益有一個(gè)問題：對可取值數(shù)目較多的屬性有所偏好，例如：考慮將“編號”作為一個(gè)屬性。這就引出了另一個(gè) 算法C4.5。

3.2 C4.5

為了解決信息增益的問題，引入一個(gè)信息增益率：

屬性a的可能取值數(shù)目越多(即V越大)，則IV(a)的值通常就越大。信息增益比本質(zhì)： 是在信息增益的基礎(chǔ)之上乘上一個(gè)懲罰參數(shù)。特征個(gè)數(shù)較多時(shí)，懲罰參數(shù)較小；特征個(gè)數(shù)較少時(shí)，懲罰參數(shù)較大。不過有一個(gè)缺點(diǎn)：

缺點(diǎn)：信息增益比偏向取值較少的特征。
使用信息增益比：基于以上缺點(diǎn)，并不是直接選擇信息增益率最大的特征，而是現(xiàn)在候選特征中找出信息增益高于平均水平的特征，然后在這些特征中再選擇信息增益率最高的特征。

3.3 CART算法

數(shù)學(xué)家真實(shí)聰明，想到了另外一個(gè)表示純度的方法，叫做基尼指數(shù)(討厭的公式)：

表示在樣本集合中一個(gè)隨機(jī)選中的樣本被分錯(cuò)的概率。舉例來說，現(xiàn)在一個(gè)袋子里有3種顏色的球若干個(gè)，伸手進(jìn)去掏出2個(gè)球，顏色不一樣的概率，這下明白了吧。Gini(D)越小，數(shù)據(jù)集D的純度越高。

舉個(gè)例子
假設(shè)現(xiàn)在有特征 “學(xué)歷”，此特征有三個(gè)特征取值： “本科”，“碩士”， “博士”，
當(dāng)使用“學(xué)歷”這個(gè)特征對樣本集合D進(jìn)行劃分時(shí)，劃分值分別有三個(gè)，因而有三種劃分的可能集合，劃分后的子集如下：
1.劃分點(diǎn)： “本科”，劃分后的子集合 ： {本科}，{碩士，博士}
2.劃分點(diǎn)： “碩士”，劃分后的子集合 ： {碩士}，{本科，博士}
3.劃分點(diǎn)： “碩士”，劃分后的子集合 ： {博士}，{本科，碩士}}
對于上述的每一種劃分，都可以計(jì)算出基于 劃分特征= 某個(gè)特征值 將樣本集合D劃分為兩個(gè)子集的純度：

因而對于一個(gè)具有多個(gè)取值（超過2個(gè)）的特征，需要計(jì)算以每一個(gè)取值作為劃分點(diǎn)，對樣本D劃分之后子集的純度Gini(D,Ai)，(其中Ai 表示特征A的可能取值)

然后從所有的可能劃分的Gini(D,Ai)中找出Gini指數(shù)最小的劃分，這個(gè)劃分的劃分點(diǎn)，便是使用特征A對樣本集合D進(jìn)行劃分的最佳劃分點(diǎn)。到此就可以長成一棵“大樹”了。

3.4 三種不同的決策樹

• ID3：取值多的屬性，更容易使數(shù)據(jù)更純，其信息增益更大。
  訓(xùn)練得到的是一棵龐大且深度淺的樹：不合理。
• C4.5：采用信息增益率替代信息增益。
• CART：以基尼系數(shù)替代熵，最小化不純度，而不是最大化信息增益。