進化する決定木: 機械学習が生物学からヒントを得るとき

生物学（または生命科学）に対する理解は時間の経過とともに大きく深まり、多くのエンジニアにとって、困難な問題を解決し、発明を生み出すための重要なインスピレーションの源となっています。

日本の高速鉄道「新幹線」を例に挙げてみましょう。新幹線は時速300kmを超える世界最速の鉄道の一つです。設計の過程で、エンジニアたちは大きな問題に遭遇しました。列車の前方の空気の移動によって発生する騒音が非常に大きく、一部のトンネルの構造に損傷を与える可能性があるという問題です。

彼らは予想外の方法でこの問題の解決策を見つけました。それはカワセミです。この鳥はくちばしが長く、水しぶきを少なくして獲物を捕まえるために水中に飛び込むことができます。

そこで、エンジニアたちは列車を鳥に似せて再設計することで、当初の問題を解決しただけでなく、列車の電力消費を 15% 削減し、速度を 10% 向上させました。

[[359373]]

[[359374]]

図1-日本の高速鉄道、新幹線、出典

生物学的知識は機械学習のインスピレーションの源にもなります。

コンテンツ

この記事で焦点を当てている例の 1 つは、進化する決定木です。

このタイプの分類器は進化的アルゴリズムを使用して、より堅牢でパフォーマンスの優れた決定木を構築します。進化アルゴリズムは、生物学的進化にヒントを得たメカニズムに依存しています。

決定木とは何ですか?
進化アルゴリズムに基づいて決定木を構築するにはどうすればよいでしょうか?
進化した決定木は他の分類器と比べてどのように機能しますか?

データセット

この記事の概念を説明するために、航空会社の乗客満足度に関する調査結果のデータセットを使用します。このデータセットの詳細については、こちらをご覧ください。

その目的は、航空会社のサービスに対する顧客満足度を予測することです。このような調査は企業の意思決定にとって非常に重要です。商品やサービスを提供する企業は、自社の製品の改善が必要な箇所を把握できるだけでなく、どの程度の改善が必要なのか、改善の緊急性はどの程度なのかも把握できるようになります。

では早速、決定木の基本を確認してみましょう。

1. 決定木とは何ですか?

決定木は、分類プロセスをツリー図として表現できる分類器です。トレーニングプロセス中に、モデルはデータの特性に基づいて単純な決定ルールを推測し、それに応じてデータポイントを分類します。

下の図は決定木の例を示しています。これは、航空会社の乗客満足度に関する調査結果のデータセットで Scikit Learn 決定木モジュールをトレーニングした結果です。

図2 - 決定木の例

意思決定ツリーは、オンラインチェックインサービスが出張中の乗客満足度の重要な要素であり、オンラインで簡単かつ効率的にチェックインできると乗客の満足度が高くなることを示しています。さらに、機内Wi-Fiの信号品質も非常に重要です。

決定木は、次のような多くの利点があるため、分類タスクで広く使用されています。

その推論プロセスは人間のものと似ており、理解しやすく説明しやすい。
数値データとカテゴリデータの両方を処理できます。
階層的分解により変数をより有効に活用します。

決定木を導出するためのほとんどのアルゴリズムは、トップダウンの再帰的分割の「貪欲」戦略を使用します。

ソースセットはツリーのルートノードを表します。ソースセットは、特定のルールに従ってサブセット (サブノード) に分割されます。特定のノード下のサブセット内のターゲット変数の値がすべて同じになるか、または分割プロセスによって予測結果の値が増加しなくなるまで、分割された各サブセットに対して分割プロセスが繰り返されます。

ノードとパーティションでテストを生成する最適な方法を決定するために使用される定量的なメトリックは、アルゴリズムに固有です。最も一般的な指標は、情報コンテンツ (またはエントロピー) とジニ不純度です。これらは不純度を測定します。ノードのすべてのサンプルが同じカテゴリに属している場合、このタイプの指標の値は 0 です。ノードのサンプルのカテゴリが均一に分布している場合 (つまり、ノードが特定のカテゴリを取る確率が一定である場合)、このタイプの指標の値は最大値に達します。詳細については、この記事をご覧ください。

ただし、このような指標には主に 2 つの欠点があります。

1. 最適ではない解決策が得られる可能性がある。

2. 複雑すぎる決定木が生成され、トレーニングデータ内で適切に一般化されず、過剰適合が発生する可能性があります。

これらの問題を克服するために、いくつかのアプローチが開発されました。

剪定: まず、完全な決定木を構築します。つまり、各リーフのすべてのインスタンスが同じクラスに属します。次に、「重要でない」ノードまたはサブツリーを削除して、ツリーのサイズを縮小します。
組み合わせツリー: さまざまなツリーを構築し、特定のルール (通常は投票数) を通じて最終的な分類結果を選択します。これにより、決定ツリーの解釈可能性が低くなることに注意してください。

したがって、ツリーモデルを生成する他の方法を検討する必要があります。最近、進化アルゴリズム（EA）が大きな注目を集めています。進化型アルゴリズムは、ローカル検索だけでなく、すべての可能なソリューションの中から強力なグローバル検索を実行します。その結果、進化的アルゴリズムは貪欲な戦略よりも属性の相互作用をより適切に処理できる可能性が高くなります。

進化アルゴリズムの具体的な動作方法を以下に示します。

2. 進化アルゴリズムを使用して決定木を構築するにはどうすればよいでしょうか?

進化アルゴリズムは、自然界の生物学的進化プロセスから派生したメカニズムを持つ探索的ヒューリスティック手法です。

このパラダイムでは、集団内の各「個体」が特定の問題に対する解決策の候補を表します。各個体の適応度はソリューションの品質を表します。このようにして、ランダムに初期化された最初の集団は、検索空間内のより良い領域に向かって進化します。各世代において、選択プロセスによって、適応度の高い個体（原文では「適応度が低い」となっているが、これは誤りである疑いがある）の繁殖確率が高くなります。

さらに、2 つの個体の情報が子孫に受け継がれる前に混合される組み換えや、個体に小さなランダムな変化をもたらす突然変異など、遺伝学にヒントを得た特定の操作が集団に対して実行されます。このプロセスは、特定の終了条件に達するまで繰り返されます。次に、回答として最適な個人を選択します。

進化的アルゴリズムに基づく決定木は、次のような理由から、汎用的な方法の興味深い代替手段となります。

ランダム検索法は、トップダウンの再帰的分割「貪欲」戦略によって見つかる可能性のある局所最適解を効果的に回避できます。
決定木の解釈は全体論的アプローチとは逆です。
単一のメトリックを最適化するだけでなく、フィットネスにさまざまな目標を統合できます。

2.1 人口の初期化

進化的決定木では、個体が決定木を表します。初期の集団はランダムに生成された木で構成されます。

ランダムツリーは次のように生成できます。

ルートノードと 2 つの子ノードの後、アルゴリズムは、各子ノードを分割し続けるか、事前に設定された確率 p で終了ポイントになるかを決定します。

子ノードの分割を続けると、アルゴリズムは分割基準としていくつかのプロパティとしきい値をランダムに選択します。
子ノードがターミナル (リーフノード) になった場合は、カテゴリラベルがランダムに割り当てられます。

2.2 フィットネス

分類器の目標は、新しいラベルなしデータを入力したときに、可能な限り最高の予測精度を達成することです。さらに、決定木分類器では、ツリーの最終的なサイズを制御する必要もあります。ツリーのサイズが小さいとアンダーフィッティングにつながり、ツリーの構造が複雑な場合はオーバーフィッティングにつながります。

したがって、フィットネスを定義するには、次のバランスが必要です。

適応度 = α1 f1 + α2 f2

で：

f1 はトレーニングセットの精度です。
f2は個体のサイズ（ツリーの深さ）に対して設定されるペナルティ項です。
α1とα2は指定するパラメータです。

2.3. 選考プロセス

次の世代の木を作成するために使用する親を選択する方法はいくつかあります。最も一般的なものは次のとおりです。

適応度に基づく比例選択、またはルーレットホイール選択: 集団は適応度によって分類され、各個体に順番に選択の確率が割り当てられます。
排除選択: 最初に集団からいくつかの個体をランダムに選択し、次に選択されたセットから最も適応度の高い個体を親として選択します。
エリート選択: 最も適応度の高い個体を次の世代に直接使用します。このアプローチにより、各世代で最も成功した個人が保持されます。

2.4 再編

組み換え子孫を得るプロセスでは、親をペアにする必要があります。

まず、2 人の個体が親として選択されます。次に、2 つのツリーのそれぞれでノードをランダムに選択します。最初のツリーで選択されたサブツリーを 2 番目のツリーで選択されたサブツリーに置き換えて、子孫を取得します。

図3-再編

2.5 突然変異

突然変異とは、集団内の少数の個体がランダムに選択されることです。突然変異により遺伝的多様性が確保され、遺伝的アルゴリズムはより広い範囲を検索できるようになります。

決定木の場合、属性をランダムに変更したり、ランダムに選択されたノードを細分化したりすることで突然変異を実現できます。

図4 - 突然変異

2.6 終了条件

最良の個体の適応度が指定された世代数にわたって増加しない場合、アルゴリズムは収束したとみなされます。

この世代数は、収束が遅い場合に計算時間を節約するために事前に設定されたパラメータです。

3. 進化した決定木のパフォーマンスは他の分類器と比べてどうですか?

進化する決定木は素晴らしいように見えますが、通常の機械学習アルゴリズムと比較してパフォーマンスはどうでしょうか?

3.1 簡単な実験

分類器の効率を評価するために、決定木を構築し、航空会社の乗客満足度調査結果のデータセットでトレーニングしました。

目標は、乗客満足度の向上につながる要因を特定することです。これには、乗客の満足度（または不満）につながる経路を説明するシンプルで堅牢なモデルが必要です。

[[359376]]

この写真はこのウェブサイト、この写真家からのものです

データセットについて

このデータセットは大規模で、100,000 を超えるルートをカバーしています。

乗客とその旅行に関する事実情報（乗客の性別、年齢、顧客タイプ（頻繁かどうか）、旅行タイプ（個人またはビジネス）、フライトクラス（ビジネス、エコ、ウルトラエコ）、飛行距離）が含まれます。
また、機内Wi-Fi、出発/到着時間（適切さ）、オンライン予約（利便性）、搭乗ゲートの場所、食事と飲み物、オンラインチェックイン、座席の快適さ、機内エンターテイメント、搭乗サービス、座席の足元の広さ、手荷物サービス、チェックインサービス、機内サービス、清潔さなどのサービスに対する乗客の満足度も含まれます。

データラベルは、「満足」、「中立」、「不満足」を含む乗客の満足度です。

方法

私が使用した計算手順は、次のように簡単にまとめることができます。

1. データ前処理: カテゴリ変数を指標変数に変換します。データセットをトレーニングセットとテストセットにランダムに分割します。

2. モデリングとテスト: 各モデルは、トレーニングサブセットの条件を考慮してトレーニングされ、検証サブセットで測定されます。

3. 各モデルのパフォーマンスを比較します。

私は、進化型決定木 (EDT) アプローチを、単純なツリーベース、決定木 (DT) ベース、ランダムフォレスト (RF) ベースのモデルと比較することを選択しました。ツリーの深さを 3 未満 (3 と等しい?) に制限します。また、妥当な計算時間内で一貫した方法で比較できるように、EDT の人口規模と RF の評価者の数を 10 に設定しました。

結果

結果は次のとおりです。

図5 - 「満足」と「中立または不満」の乗客数

表1-DTモデルの分類レポート

表2 - RFモデルの分類レポート

表3 - EDTモデルの分類レポート

図6-3 3つのモデルのROC曲線と曲線の下の領域

このパラメータ設定により、EDT は他の 2 つの機械学習アルゴリズムに非常に近いパフォーマンスを発揮します。

ただし、EDT の利点は、次のような決定ツリーを提供することです。

複数の決定木がクラスター化されたサイトを提示できる（RFモデルと比較して）、
これは、ツリーのグループの中で最もパフォーマンスの高いツリーであるため、(単純な DT モデルと比較して) 堅牢です。

トレーニングプロセス中、最大深度は 2 に設定され、EDT 集団内の最適な決定木は次のように表されます。

図7 ()-EDTにおける最良決定木の概略図

3.2 EDF法のより一般化された実験的検証

上記の実験は、他の機械学習アルゴリズムと比較して、進化した決定木のパフォーマンスと信頼性を評価するには明らかに不十分です。

使用されたデータセットは 1 つだけであったため、ラベルカテゴリの数、機能の数、観測数の影響など、すべての可能性が考慮されたわけではありません。

[2]では、著者らは実際のUCIデータセットを使用して、EDT法と他の機械学習法のパフォーマンスを比較しました。

この記事の調査結果は次のとおりです。

データセットについて

次の表では、使用されるデータセットについて簡単に説明します。

表4 - データセットのプロパティ

ご覧のとおり、データセットは観測値、特徴、クラスの数の点で大きく異なります。

最も難しいデータセットは、カテゴリが多く、観測値が少ないため、間違いなく最初のデータセットです。

方法

以下は、著者らが EDT モデルのパフォーマンスをより「古典的な」機械学習アルゴリズムと比較して評価するために使用したアプローチから得られた主なポイントです。

EDT モデルは、世代数が 500、集団サイズが 400、組み換え/突然変異の確率がそれぞれ 0.6/0.4、選択方法がランダム均一能力主義というハイパーパラメータでトレーニングされています。
モデルのパフォーマンスを測定するために、5x2 クロス検証が使用されました。

結果

表5 - 使用されるデータセットに応じたモデルの精度

ツリーベースのアルゴリズムは、ほとんどの場合、他の機械学習アルゴリズムよりも優れています。これは、決定木自体が最も重要な特徴を選択するのに優れていると解釈できます。さらに、ルールベースのモデルは、特にターゲットと機能の関係をモデル化することが難しい場合に、特定のデータセットに適しています。
アワビのデータセットの結果は非常に悪く、クラスは 28 個で、観測数は非常に少ない (わずか 210 個) です。しかし、EDT モデルは最高の精度で際立っていました。これは、難しいデータセットを効果的に処理し、過剰適合を回避できることを示しています。

EDT モデルではデフォルトのパラメータが使用されることに注意してください。パラメータを調整するとパフォーマンスが向上する可能性があります。