0
| 本文作者： AI研習(xí)社-譯站 | 2020-12-22 10:28 |
譯者：AI研習(xí)社（精神小高）
雙語原文鏈接：Evolutionary Decision Trees: When Machine Learning draws its Inspiration from Biology
隨著時間的推移，我們對生物學(xué)（或生命科學(xué)）的了解大大增加，它已成為許多工程師解決挑戰(zhàn)性問題并產(chǎn)生發(fā)明創(chuàng)造的的重要靈感來源。
以日本的高速列車“新干線”為例，它是世界上最快的火車之一，時速超過300公里/小時。 在設(shè)計過程中，工程師遇到了巨大的難題：火車前部空氣的位移所產(chǎn)生的噪音，其幅度大到可能破壞某些隧道的結(jié)構(gòu)。
他們以一個出乎意料的方式找到了這個問題的解法：翠鳥。這種鳥的喙部細(xì)長，使之在潛入水中捕食時能夠少濺水花。
因此，通過模仿這種鳥的形象重新設(shè)計列車，工程師不僅解決了最初的問題，而且還將列車的耗電量減少了15％，速度提高了10％。
圖1-日本的高速鐵路，新干線，來源
生物學(xué)知識也可以成為機器學(xué)習(xí)中靈感的來源。
本文重點關(guān)注的一個例子是進(jìn)化決策樹。
這類分類器使用進(jìn)化算法來構(gòu)建魯棒性更強，性能更好的決策樹。進(jìn)化算法依賴于生物進(jìn)化啟發(fā)的機制。
決策樹是什么？
如何根據(jù)進(jìn)化算法搭建決策樹？
與其它分類器相比，進(jìn)化決策樹的表現(xiàn)如何？
為了說明本文中提及的概念，我將使用航空公司乘客滿意度的調(diào)查結(jié)果數(shù)據(jù)集。有關(guān)此數(shù)據(jù)集的更多信息，請參見此處。
其目的是預(yù)測顧客對航空公司的服務(wù)的滿意度。這樣的研究對公司的決策至關(guān)重要。它不僅可以使提供商品或服務(wù)的公司知曉其產(chǎn)品在哪些方面需要改進(jìn)，而且可以使公司知道應(yīng)該改進(jìn)到什么程度以及改進(jìn)的緊要程度
事不宜遲，讓我們從復(fù)習(xí)關(guān)于決策樹的基礎(chǔ)知識開始吧。
決策樹是一種分類器，其分類流程可表示為樹形圖。模型在訓(xùn)練過程中根據(jù)數(shù)據(jù)的特征推斷出簡單的決策規(guī)則，并依此對數(shù)據(jù)點進(jìn)行分類。
下圖展示了一個決策樹的例子。這是使用Scikit Learn決策樹模塊在航空公司乘客滿意度的調(diào)查結(jié)果數(shù)據(jù)集上進(jìn)行訓(xùn)練的結(jié)果。
圖2-決策樹示例
決策樹表明網(wǎng)上值機服務(wù)是商務(wù)旅行中乘客滿意度的重要因素，乘客在能簡單高效地在網(wǎng)上辦理登機手續(xù)時更可能感到滿意。另外，艙內(nèi)wifi的信號質(zhì)量也十分重要。
決策樹由于具有許多優(yōu)點而被廣泛用于分類任務(wù)：
它的推理過程與人類相似，易于理解和解釋；
它能處理數(shù)值數(shù)據(jù)和分類數(shù)據(jù)；
它通過分層分解能更充分地利用變量。
大多數(shù)用于推導(dǎo)決策樹的算法都使用自上而下的遞歸劃分“貪心”策略。
源集（source set）代表了樹的根節(jié)點。源集是根據(jù)特定規(guī)則劃分為各個子集（子節(jié)點）的。在每次劃分出的子集上重復(fù)該劃分過程，直到某個節(jié)點下的子集中的目標(biāo)變量的值全部相同，或者劃分過程不再使預(yù)測結(jié)果的值增加。
用于在節(jié)點和劃分中確定生成測試的最佳方法的量化指標(biāo)是因算法而異的。最常見的指標(biāo)是信息量（或熵）和基尼雜質(zhì)量。它們度量的是雜質(zhì)度，當(dāng)節(jié)點的所有樣本屬于同一類別時，這類指標(biāo)的值為0；當(dāng)節(jié)點的樣本的類別呈均一分布（即，該節(jié)點取到某一類別的概率為常數(shù)）時，這類指標(biāo)的值取到最大值。更多相關(guān)信息參見本文。
但是，此類指標(biāo)有兩個主要缺點：
1.可能取到次優(yōu)解；
2.可能生成過于復(fù)雜的決策樹，以至于在訓(xùn)練數(shù)據(jù)中泛化效果不好，導(dǎo)致過擬合。
目前已有幾種方法可用于克服這些問題：
剪枝：首先，構(gòu)建一顆完整的決策樹，即每片葉子中的所有實例都屬于同一類。然后刪除“不重要”的節(jié)點或子樹，以減小樹的大小。
組合樹：構(gòu)建不同的樹，并通過特定規(guī)則（一般是投票計數(shù)）選擇最終的分類結(jié)果。值得注意的是，這會導(dǎo)致決策樹的可解釋性降低。
因此，有必要探索生成樹模型的其它方法。最近，進(jìn)化算法（Evolutionary Algorithms, EA）獲得了極大的關(guān)注。進(jìn)化算法在所有可能的解法中進(jìn)行強大的全局搜索，而不僅僅是本地搜索。結(jié)果，與貪心策略相比，進(jìn)化算法更可能把屬性交互處理得更好。
進(jìn)化算法的具體工作方式見下。
2. 怎樣用進(jìn)化算法構(gòu)造決策樹？
進(jìn)化算法是搜索啟發(fā)式方法，其機理源自自然中的生物進(jìn)化過程。
在這個范式中，群體中的每個“個體”代表給定問題的一種候選解法。每個個體的適合度代表這種解法的質(zhì)量。這樣，隨機初始化的第一個群體會朝著搜索空間中更好的區(qū)域進(jìn)化。在每一代中，選擇過程使得適合度較高（原文為“適合度較低”，疑有誤）的個體具有較高的繁殖概率。
此外，還會對群體進(jìn)行特定的由遺傳學(xué)啟發(fā)的操作，例如重組，兩個個體的信息在混合后才會傳給他們的后代；以及突變，對個體進(jìn)行微小的隨機改變。對這一過程進(jìn)行迭代，直到達(dá)到某一終止條件。然后選擇最適個體為答案。
基于進(jìn)化算法的決策樹是通用方法的一種有意思的替代品，因為：
隨機搜索法能有效避免自上而下的遞歸劃分“貪心”策略可能找到的局部最優(yōu)解。
對決策樹的解釋與整體法相反。
不僅僅是優(yōu)化單一指標(biāo)，它可以將不同的目標(biāo)集成在適合度中。
在進(jìn)化決策樹中，一個個體代表的是一棵決策樹。初始群體由隨機生成的樹組成。
隨機樹可以按以下步驟生成：
在根節(jié)點和兩個子節(jié)點后，算法以預(yù)設(shè)概率p決定每個子節(jié)點是否繼續(xù)劃分或成為終點。
如果繼續(xù)劃分該子節(jié)點，算法會隨機選擇一些性質(zhì)和閾值作為劃分的標(biāo)準(zhǔn)。
如果該子節(jié)點成為終點（葉節(jié)點），就給它隨機分配一個類別標(biāo)簽。
分類器的目標(biāo)是在輸入未標(biāo)記的新數(shù)據(jù)時能獲得最高預(yù)測準(zhǔn)確度。此外，決策樹分類器還需要控制樹的最終尺寸。因為樹的尺寸小會導(dǎo)致欠擬合，而樹的結(jié)構(gòu)太復(fù)雜會導(dǎo)致過擬合。
因此，在定義適合度時需要在這兩項之間取得平衡：
適合度 = α1 f1 + α2 f2
其中：
f1是在訓(xùn)練集上的準(zhǔn)確度；
f2是對個體的尺寸（樹的深度）所設(shè)置的懲罰項；
α1 和
α2 是待指定的參數(shù)。
有多種方法可以選擇用于創(chuàng)建下一代樹的親本。最常見的是以下幾種：
基于適應(yīng)度按比例選擇，或輪盤賭式選擇：按適合度對群體排序，然后依次為每個個體賦予選擇概率。
淘汰制選擇：先從群體中隨機選出一些個體，再從選出的集合中取適合度最高的個體作為親本。
精英制選擇：直接把適合度最高的個體用到下一代。這種方法能保留每代最成功的個體。
獲得重組子代的過程需要使親本兩兩配對。
首先，選擇兩個個體作為親本。然后在兩棵樹中各隨機選一個節(jié)點。用第二棵樹中選擇的子樹代替第一棵樹中選中的子樹，獲得子代。
圖3-重組
突變指的是一個群體的部分個體中的隨機的小選擇。突變是遺傳多樣性的保證，這意味著遺傳算法能搜索到更大的范圍。
對決策樹而言，突變可以通過隨機更改屬性或者細(xì)分隨機選的節(jié)點來實現(xiàn)。
圖4-突變
如果最優(yōu)秀的個體的適合度在給定數(shù)量的世代中沒有上升，就可以認(rèn)為算法已經(jīng)收斂了。
為了在收斂得很慢時節(jié)約計算時間，這個世代數(shù)目是預(yù)先設(shè)定的參數(shù)。
進(jìn)化決策樹看起來很好，但跟常規(guī)機器學(xué)習(xí)算法相比，它的表現(xiàn)又如何？
為了評價分類器的效率，我搭建了一個決策樹，并在航空公司乘客滿意度調(diào)查結(jié)果數(shù)據(jù)集上進(jìn)行訓(xùn)練。
目標(biāo)是找出能導(dǎo)致乘客滿意度升高的因素。 這樣就需要一個簡單而抗干擾的模型來解釋導(dǎo)致乘客感到滿意（或不滿意）的途徑。
關(guān)于數(shù)據(jù)集
這個數(shù)據(jù)集很大，囊括了多于10萬條航線。
含有關(guān)于乘客及其行程的事實信息：乘客的性別，年齡，客戶類型（是否有慣性），旅行類型（個人或商務(wù)旅行），航班艙位（商務(wù)，環(huán)保，極環(huán)保 ）和飛行距離。
還包含乘客對以下服務(wù)的滿意度：艙內(nèi)wifi，出發(fā)/到達(dá)時間（是否合宜），網(wǎng)上預(yù)訂（是否方便），登機口位置，餐飲，網(wǎng)上值機，座椅舒適度，艙內(nèi)娛樂，登機服務(wù)，座椅腿部空間 ，行李服務(wù)，值機服務(wù)，艙內(nèi)服務(wù)，整潔度。
數(shù)據(jù)標(biāo)簽是乘客的滿意度，包括“滿意”，“中立”和“不滿意”。
我使用的計算步驟可簡要歸納如下：
1. 數(shù)據(jù)預(yù)處理：將類別變量轉(zhuǎn)換為指示變量。將數(shù)據(jù)集隨機劃分為訓(xùn)練集和測試集。
2. 建模和測試：訓(xùn)練每個模型在訓(xùn)練子集上考慮條件，在驗證子集上進(jìn)行衡量。
3. 比較各模型的表現(xiàn)。
我選擇將進(jìn)化決策樹（EDT）方法與基于簡單的樹的，基于決策樹（DT）的和基于隨機森林（RF）的模型進(jìn)行比較。限制樹的深度小于(等于?)3。 我還將EDT的群體大小和RF的評價器數(shù)量設(shè)置為10，以便于在合理的計算時間內(nèi)以一致的方式比較它們。
結(jié)果如下：
圖5-“滿意”以及“中立或不滿意”的乘客的數(shù)量
表1-DT模型的分類報告
表2-RF模型的分類報告
表3-EDT模型的分類報告
圖6-3個模型的ROC曲線和曲線下面積
在這種參數(shù)設(shè)置下，EDT的表現(xiàn)和另外兩種機器學(xué)習(xí)算法很接近。
然而，EDT的優(yōu)勢在于它能提供這樣一棵決策樹：
可以呈現(xiàn)多顆決策樹聚集的位點（與RF模型相比），并且
具有魯棒性（與簡單DT模型相比），因為它是一群樹中表現(xiàn)最好的那顆。
在訓(xùn)練過程中，將最大深度設(shè)為2，獲得的EDT群體中表現(xiàn)最好的決策樹可以表征為如下形式：
圖7（
上述實驗肯定不足以評估進(jìn)化決策樹跟其它機器學(xué)習(xí)算法相比時的性能和可靠性。
因為只用了一個數(shù)據(jù)集，因此沒有考慮到所有可能性，例如標(biāo)簽的類別數(shù)量，特征數(shù)量和觀測數(shù)量的影響等。
在[2]中，作者使用真實的UCI數(shù)據(jù)集對EDT方法與其他機器學(xué)習(xí)方法的性能進(jìn)行了比較。
這篇文章的發(fā)現(xiàn)如下。
下表簡要介紹了所用的數(shù)據(jù)集：
表4-數(shù)據(jù)集的性質(zhì)
如你所見，數(shù)據(jù)集在觀測次數(shù)，特征個數(shù)和類別個數(shù)這幾個方面的差別很大。
最困難的數(shù)據(jù)集肯定是第一個數(shù)據(jù)集，因為它有很多類別，而觀察次數(shù)較少。
以下是與更‘經(jīng)典’的機器學(xué)習(xí)算法相比時，作者用來評估EDT模型表現(xiàn)的方法的主要信息：
EDT模型已使用以下超參數(shù)進(jìn)行了訓(xùn)練：世代數(shù)為500，群體大小為400，重組/變異的概率分別為0.6 / 0.4，選擇方法為隨機統(tǒng)一的精英制選擇。
使用5x2交叉驗證來測量模型的表現(xiàn)。
表5-模型的正確率取決于所用的數(shù)據(jù)集
基于樹的算法幾乎總是優(yōu)于其它機器學(xué)習(xí)算法。 可以解釋為決策樹本身更能選擇出最重要的特征。 此外，基于規(guī)則的模型更適合用于特定的數(shù)據(jù)集，尤其是難以對目標(biāo)與特征間的關(guān)系建模時。
鮑魚數(shù)據(jù)集上的結(jié)果都很差：因為有28個類別，而且觀測次數(shù)很少（只有210次）。 但是，EDT模型以最高的準(zhǔn)確率脫穎而出。 這表明它能有效地處理困難的數(shù)據(jù)集并避免過擬合。
值得注意的是，EDT模型使用的是默認(rèn)參數(shù)。 調(diào)整參數(shù)能帶來更好的表現(xiàn)。
[1] R. Barros et al., A Survey of Evolutionary Algorithms for Decision Tree Induction, 2011
[2] D. Jankowski et al., Evolutionary Algorithm for Decision Tree Induction, 2016
[3] S. Cha, Constructing Binary Decision Trees using Genetic Algorithms, 2008
[4] D. Carvalho et al., A Hybrid Decision Tree/Genetic Algorithm Method for Data Mining, 2003
[5] Wikipedia, Traveling salesman problem
[6] Wikipedia, Genetic Algorithm
AI研習(xí)社是AI學(xué)術(shù)青年和AI開發(fā)者技術(shù)交流的在線社區(qū)。我們與高校、學(xué)術(shù)機構(gòu)和產(chǎn)業(yè)界合作，通過提供學(xué)習(xí)、實戰(zhàn)和求職服務(wù)，為AI學(xué)術(shù)青年和開發(fā)者的交流互助和職業(yè)發(fā)展打造一站式平臺，致力成為中國最大的科技創(chuàng)新人才聚集地。
如果，你也是位熱愛分享的AI愛好者。歡迎與譯站一起，學(xué)習(xí)新知，分享成長。
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
照片來自
