隨著時(shí)間的推移，我們對(duì)生物學(xué)（或生命科學(xué)）的了解大大增加，它已成為許多工程師解決挑戰(zhàn)性問(wèn)題并產(chǎn)生發(fā)明創(chuàng)造的的重要靈感來(lái)源。

以日本的高速列車“新干線”為例，它是世界上最快的火車之一，時(shí)速超過(guò)300公里/小時(shí)。 在設(shè)計(jì)過(guò)程中，工程師遇到了巨大的難題：火車前部空氣的位移所產(chǎn)生的噪音，其幅度大到可能破壞某些隧道的結(jié)構(gòu)。

他們以一個(gè)出乎意料的方式找到了這個(gè)問(wèn)題的解法：翠鳥(niǎo)。這種鳥(niǎo)的喙部細(xì)長(zhǎng)，使之在潛入水中捕食時(shí)能夠少濺水花。

因此，通過(guò)模仿這種鳥(niǎo)的形象重新設(shè)計(jì)列車，工程師不僅解決了最初的問(wèn)題，而且還將列車的耗電量減少了15％，速度提高了10％。

[[359373]] 

[[359374]]

圖1-日本的高速鐵路，新干線，來(lái)源

生物學(xué)知識(shí)也可以成為機(jī)器學(xué)習(xí)中靈感的來(lái)源。

內(nèi)容

本文重點(diǎn)關(guān)注的一個(gè)例子是進(jìn)化決策樹(shù)。

這類分類器使用進(jìn)化算法來(lái)構(gòu)建魯棒性更強(qiáng)，性能更好的決策樹(shù)。進(jìn)化算法依賴于生物進(jìn)化啟發(fā)的機(jī)制。

• 決策樹(shù)是什么？

• 如何根據(jù)進(jìn)化算法搭建決策樹(shù)？

• 與其它分類器相比，進(jìn)化決策樹(shù)的表現(xiàn)如何？

數(shù)據(jù)集

為了說(shuō)明本文中提及的概念，我將使用航空公司乘客滿意度的調(diào)查結(jié)果數(shù)據(jù)集。有關(guān)此數(shù)據(jù)集的更多信息，請(qǐng)參見(jiàn)此處。

其目的是預(yù)測(cè)顧客對(duì)航空公司的服務(wù)的滿意度。這樣的研究對(duì)公司的決策至關(guān)重要。它不僅可以使提供商品或服務(wù)的公司知曉其產(chǎn)品在哪些方面需要改進(jìn)，而且可以使公司知道應(yīng)該改進(jìn)到什么程度以及改進(jìn)的緊要程度

事不宜遲，讓我們從復(fù)習(xí)關(guān)于決策樹(shù)的基礎(chǔ)知識(shí)開(kāi)始吧。

1. 什么是決策樹(shù)？

決策樹(shù)是一種分類器，其分類流程可表示為樹(shù)形圖。模型在訓(xùn)練過(guò)程中根據(jù)數(shù)據(jù)的特征推斷出簡(jiǎn)單的決策規(guī)則，并依此對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類。

下圖展示了一個(gè)決策樹(shù)的例子。這是使用Scikit Learn決策樹(shù)模塊在航空公司乘客滿意度的調(diào)查結(jié)果數(shù)據(jù)集上進(jìn)行訓(xùn)練的結(jié)果。

圖2-決策樹(shù)示例

決策樹(shù)表明網(wǎng)上值機(jī)服務(wù)是商務(wù)旅行中乘客滿意度的重要因素，乘客在能簡(jiǎn)單高效地在網(wǎng)上辦理登機(jī)手續(xù)時(shí)更可能感到滿意。另外，艙內(nèi)wifi的信號(hào)質(zhì)量也十分重要。

決策樹(shù)由于具有許多優(yōu)點(diǎn)而被廣泛用于分類任務(wù)：

• 它的推理過(guò)程與人類相似，易于理解和解釋；

• 它能處理數(shù)值數(shù)據(jù)和分類數(shù)據(jù)；

• 它通過(guò)分層分解能更充分地利用變量。

大多數(shù)用于推導(dǎo)決策樹(shù)的算法都使用自上而下的遞歸劃分“貪心”策略。 

源集（source set）代表了樹(shù)的根節(jié)點(diǎn)。源集是根據(jù)特定規(guī)則劃分為各個(gè)子集（子節(jié)點(diǎn)）的。在每次劃分出的子集上重復(fù)該劃分過(guò)程，直到某個(gè)節(jié)點(diǎn)下的子集中的目標(biāo)變量的值全部相同，或者劃分過(guò)程不再使預(yù)測(cè)結(jié)果的值增加。

用于在節(jié)點(diǎn)和劃分中確定生成測(cè)試的最佳方法的量化指標(biāo)是因算法而異的。最常見(jiàn)的指標(biāo)是信息量（或熵）和基尼雜質(zhì)量。它們度量的是雜質(zhì)度，當(dāng)節(jié)點(diǎn)的所有樣本屬于同一類別時(shí)，這類指標(biāo)的值為0；當(dāng)節(jié)點(diǎn)的樣本的類別呈均一分布（即，該節(jié)點(diǎn)取到某一類別的概率為常數(shù)）時(shí)，這類指標(biāo)的值取到最大值。更多相關(guān)信息參見(jiàn)本文。

但是，此類指標(biāo)有兩個(gè)主要缺點(diǎn)：

1.可能取到次優(yōu)解；

2.可能生成過(guò)于復(fù)雜的決策樹(shù)，以至于在訓(xùn)練數(shù)據(jù)中泛化效果不好，導(dǎo)致過(guò)擬合。

目前已有幾種方法可用于克服這些問(wèn)題：

• 剪枝：首先，構(gòu)建一顆完整的決策樹(shù)，即每片葉子中的所有實(shí)例都屬于同一類。然后刪除“不重要”的節(jié)點(diǎn)或子樹(shù)，以減小樹(shù)的大小。

• 組合樹(shù)：構(gòu)建不同的樹(shù)，并通過(guò)特定規(guī)則（一般是投票計(jì)數(shù)）選擇最終的分類結(jié)果。值得注意的是，這會(huì)導(dǎo)致決策樹(shù)的可解釋性降低。

因此，有必要探索生成樹(shù)模型的其它方法。最近，進(jìn)化算法（Evolutionary Algorithms, EA）獲得了極大的關(guān)注。進(jìn)化算法在所有可能的解法中進(jìn)行強(qiáng)大的全局搜索，而不僅僅是本地搜索。結(jié)果，與貪心策略相比，進(jìn)化算法更可能把屬性交互處理得更好。

進(jìn)化算法的具體工作方式見(jiàn)下。  

2. 怎樣用進(jìn)化算法構(gòu)造決策樹(shù)？

進(jìn)化算法是搜索啟發(fā)式方法，其機(jī)理源自自然中的生物進(jìn)化過(guò)程。

在這個(gè)范式中，群體中的每個(gè)“個(gè)體”代表給定問(wèn)題的一種候選解法。每個(gè)個(gè)體的適合度代表這種解法的質(zhì)量。這樣，隨機(jī)初始化的第一個(gè)群體會(huì)朝著搜索空間中更好的區(qū)域進(jìn)化。在每一代中，選擇過(guò)程使得適合度較高（原文為“適合度較低”，疑有誤）的個(gè)體具有較高的繁殖概率。

此外，還會(huì)對(duì)群體進(jìn)行特定的由遺傳學(xué)啟發(fā)的操作，例如重組，兩個(gè)個(gè)體的信息在混合后才會(huì)傳給他們的后代；以及突變，對(duì)個(gè)體進(jìn)行微小的隨機(jī)改變。對(duì)這一過(guò)程進(jìn)行迭代，直到達(dá)到某一終止條件。然后選擇最適個(gè)體為答案。

基于進(jìn)化算法的決策樹(shù)是通用方法的一種有意思的替代品，因?yàn)椋?/p>

• 隨機(jī)搜索法能有效避免自上而下的遞歸劃分“貪心”策略可能找到的局部最優(yōu)解。

• 對(duì)決策樹(shù)的解釋與整體法相反。

• 不僅僅是優(yōu)化單一指標(biāo)，它可以將不同的目標(biāo)集成在適合度中。

2.1 群體的初始化

在進(jìn)化決策樹(shù)中，一個(gè)個(gè)體代表的是一棵決策樹(shù)。初始群體由隨機(jī)生成的樹(shù)組成。

隨機(jī)樹(shù)可以按以下步驟生成：

在根節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)后，算法以預(yù)設(shè)概率p決定每個(gè)子節(jié)點(diǎn)是否繼續(xù)劃分或成為終點(diǎn)。

• 如果繼續(xù)劃分該子節(jié)點(diǎn)，算法會(huì)隨機(jī)選擇一些性質(zhì)和閾值作為劃分的標(biāo)準(zhǔn)。

• 如果該子節(jié)點(diǎn)成為終點(diǎn)（葉節(jié)點(diǎn)），就給它隨機(jī)分配一個(gè)類別標(biāo)簽。

2.2 適合度

分類器的目標(biāo)是在輸入未標(biāo)記的新數(shù)據(jù)時(shí)能獲得最高預(yù)測(cè)準(zhǔn)確度。此外，決策樹(shù)分類器還需要控制樹(shù)的最終尺寸。因?yàn)闃?shù)的尺寸小會(huì)導(dǎo)致欠擬合，而樹(shù)的結(jié)構(gòu)太復(fù)雜會(huì)導(dǎo)致過(guò)擬合。

因此，在定義適合度時(shí)需要在這兩項(xiàng)之間取得平衡：

適合度 = α1 f1 + α2 f2

其中：

• f1是在訓(xùn)練集上的準(zhǔn)確度；

• f2是對(duì)個(gè)體的尺寸（樹(shù)的深度）所設(shè)置的懲罰項(xiàng)；

• α1 和 α2 是待指定的參數(shù)。  

2.3. 選擇過(guò)程

有多種方法可以選擇用于創(chuàng)建下一代樹(shù)的親本。最常見(jiàn)的是以下幾種：

• 基于適應(yīng)度按比例選擇，或輪盤(pán)賭式選擇：按適合度對(duì)群體排序，然后依次為每個(gè)個(gè)體賦予選擇概率。

• 淘汰制選擇：先從群體中隨機(jī)選出一些個(gè)體，再?gòu)倪x出的集合中取適合度最高的個(gè)體作為親本。

• 精英制選擇：直接把適合度最高的個(gè)體用到下一代。這種方法能保留每代最成功的個(gè)體。

2.4 重組

獲得重組子代的過(guò)程需要使親本兩兩配對(duì)。

首先，選擇兩個(gè)個(gè)體作為親本。然后在兩棵樹(shù)中各隨機(jī)選一個(gè)節(jié)點(diǎn)。用第二棵樹(shù)中選擇的子樹(shù)代替第一棵樹(shù)中選中的子樹(shù)，獲得子代。

圖3-重組

2.5 突變

突變指的是一個(gè)群體的部分個(gè)體中的隨機(jī)的小選擇。突變是遺傳多樣性的保證，這意味著遺傳算法能搜索到更大的范圍。

對(duì)決策樹(shù)而言，突變可以通過(guò)隨機(jī)更改屬性或者細(xì)分隨機(jī)選的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)。

圖4-突變

2.6 終止條件

如果最優(yōu)秀的個(gè)體的適合度在給定數(shù)量的世代中沒(méi)有上升，就可以認(rèn)為算法已經(jīng)收斂了。

為了在收斂得很慢時(shí)節(jié)約計(jì)算時(shí)間，這個(gè)世代數(shù)目是預(yù)先設(shè)定的參數(shù)。

3. 跟其它分類器比，進(jìn)化決策樹(shù)的表現(xiàn)如何？

進(jìn)化決策樹(shù)看起來(lái)很好，但跟常規(guī)機(jī)器學(xué)習(xí)算法相比，它的表現(xiàn)又如何？

3.1 一個(gè)簡(jiǎn)單的實(shí)驗(yàn)

為了評(píng)價(jià)分類器的效率，我搭建了一個(gè)決策樹(shù)，并在航空公司乘客滿意度調(diào)查結(jié)果數(shù)據(jù)集上進(jìn)行訓(xùn)練。

目標(biāo)是找出能導(dǎo)致乘客滿意度升高的因素。 這樣就需要一個(gè)簡(jiǎn)單而抗干擾的模型來(lái)解釋導(dǎo)致乘客感到滿意（或不滿意）的途徑。

[[359376]]

 照片來(lái)自這個(gè)網(wǎng)站，這位攝影師

關(guān)于數(shù)據(jù)集

這個(gè)數(shù)據(jù)集很大，囊括了多于10萬(wàn)條航線。

• 含有關(guān)于乘客及其行程的事實(shí)信息：乘客的性別，年齡，客戶類型（是否有慣性），旅行類型（個(gè)人或商務(wù)旅行），航班艙位（商務(wù)，環(huán)保，極環(huán)保 ）和飛行距離。

• 還包含乘客對(duì)以下服務(wù)的滿意度：艙內(nèi)wifi，出發(fā)/到達(dá)時(shí)間（是否合宜），網(wǎng)上預(yù)訂（是否方便），登機(jī)口位置，餐飲，網(wǎng)上值機(jī)，座椅舒適度，艙內(nèi)娛樂(lè)，登機(jī)服務(wù)，座椅腿部空間 ，行李服務(wù)，值機(jī)服務(wù)，艙內(nèi)服務(wù)，整潔度。

數(shù)據(jù)標(biāo)簽是乘客的滿意度，包括“滿意”，“中立”和“不滿意”。

方法

我使用的計(jì)算步驟可簡(jiǎn)要?dú)w納如下：

1. 數(shù)據(jù)預(yù)處理：將類別變量轉(zhuǎn)換為指示變量。將數(shù)據(jù)集隨機(jī)劃分為訓(xùn)練集和測(cè)試集。

2. 建模和測(cè)試：訓(xùn)練每個(gè)模型在訓(xùn)練子集上考慮條件，在驗(yàn)證子集上進(jìn)行衡量。

3. 比較各模型的表現(xiàn)。

我選擇將進(jìn)化決策樹(shù)（EDT）方法與基于簡(jiǎn)單的樹(shù)的，基于決策樹(shù)（DT）的和基于隨機(jī)森林（RF）的模型進(jìn)行比較。限制樹(shù)的深度小于(等于?)3。 我還將EDT的群體大小和RF的評(píng)價(jià)器數(shù)量設(shè)置為10，以便于在合理的計(jì)算時(shí)間內(nèi)以一致的方式比較它們。

結(jié)果

結(jié)果如下：

圖5-“滿意”以及“中立或不滿意”的乘客的數(shù)量

表1-DT模型的分類報(bào)告

表2-RF模型的分類報(bào)告

表3-EDT模型的分類報(bào)告

圖6-3個(gè)模型的ROC曲線和曲線下面積

在這種參數(shù)設(shè)置下，EDT的表現(xiàn)和另外兩種機(jī)器學(xué)習(xí)算法很接近。

然而，EDT的優(yōu)勢(shì)在于它能提供這樣一棵決策樹(shù)：

• 可以呈現(xiàn)多顆決策樹(shù)聚集的位點(diǎn)（與RF模型相比），并且

• 具有魯棒性（與簡(jiǎn)單DT模型相比），因?yàn)樗且蝗簶?shù)中表現(xiàn)最好的那顆。

在訓(xùn)練過(guò)程中，將最大深度設(shè)為2，獲得的EDT群體中表現(xiàn)最好的決策樹(shù)可以表征為如下形式：

圖7（）-EDT中最佳決策樹(shù)的示意圖

3.2 對(duì)EDF方法的一個(gè)更泛化的實(shí)驗(yàn)驗(yàn)證

上述實(shí)驗(yàn)肯定不足以評(píng)估進(jìn)化決策樹(shù)跟其它機(jī)器學(xué)習(xí)算法相比時(shí)的性能和可靠性。

因?yàn)橹挥昧艘粋€(gè)數(shù)據(jù)集，因此沒(méi)有考慮到所有可能性，例如標(biāo)簽的類別數(shù)量，特征數(shù)量和觀測(cè)數(shù)量的影響等。

在[2]中，作者使用真實(shí)的UCI數(shù)據(jù)集對(duì)EDT方法與其他機(jī)器學(xué)習(xí)方法的性能進(jìn)行了比較。

這篇文章的發(fā)現(xiàn)如下。

關(guān)于數(shù)據(jù)集

下表簡(jiǎn)要介紹了所用的數(shù)據(jù)集：

表4-數(shù)據(jù)集的性質(zhì)

如你所見(jiàn)，數(shù)據(jù)集在觀測(cè)次數(shù)，特征個(gè)數(shù)和類別個(gè)數(shù)這幾個(gè)方面的差別很大。

最困難的數(shù)據(jù)集肯定是第一個(gè)數(shù)據(jù)集，因?yàn)樗泻芏囝悇e，而觀察次數(shù)較少。

方法

以下是與更‘經(jīng)典’的機(jī)器學(xué)習(xí)算法相比時(shí)，作者用來(lái)評(píng)估EDT模型表現(xiàn)的方法的主要信息：

• EDT模型已使用以下超參數(shù)進(jìn)行了訓(xùn)練：世代數(shù)為500，群體大小為400，重組/變異的概率分別為0.6 / 0.4，選擇方法為隨機(jī)統(tǒng)一的精英制選擇。

• 使用5x2交叉驗(yàn)證來(lái)測(cè)量模型的表現(xiàn)。

結(jié)果

表5-模型的正確率取決于所用的數(shù)據(jù)集

1. 基于樹(shù)的算法幾乎總是優(yōu)于其它機(jī)器學(xué)習(xí)算法。 可以解釋為決策樹(shù)本身更能選擇出最重要的特征。 此外，基于規(guī)則的模型更適合用于特定的數(shù)據(jù)集，尤其是難以對(duì)目標(biāo)與特征間的關(guān)系建模時(shí)。

2. 鮑魚(yú)數(shù)據(jù)集上的結(jié)果都很差：因?yàn)橛?8個(gè)類別，而且觀測(cè)次數(shù)很少（只有210次）。 但是，EDT模型以最高的準(zhǔn)確率脫穎而出。 這表明它能有效地處理困難的數(shù)據(jù)集并避免過(guò)擬合。

值得注意的是，EDT模型使用的是默認(rèn)參數(shù)。 調(diào)整參數(shù)能帶來(lái)更好的表現(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