このトピックでは、人気の高い機械学習アルゴリズムの一つである決定木を取り上げます。決定木は、人間の意思決定プロセスに似た、それなりに人気のある機械学習アルゴリズムである。この特徴により、このアルゴリズムは理解しやすい。回帰問題や分類問題で多用途に利用できる。

友達と散歩に行くか、夕方まで家にいるか、どちらかを選ぶ状況を想像してください。

機械学習で言えば、「時間」と「Netflixの新シリーズ」を特徴量とするエンターテイメントの二値分類の問題である。

つまり、これらの特徴量は、Xに沿った位置づけになります。 XとY軸に沿って配置し、2次元の平面を得ることができる。この平面を線で区切ると、平面の各サブドメインは、あるクラスのエンターテインメントを表していることがわかる。

多機能空間を表現するためには、もう少し想像力が必要だが、まずはそこからだ。

主な考え方

これらのツリーがどのように構築されるかを見る前に、まず用語の説明から始めましょう。

ノード。木のノードとは、ある条件を含む木の一部分である。ノードには0個以上の子ノードがある。 ルート。最初のツリーノード。 葉または終端ノード。子ノードを持たないノード（結果）。 条件（Condition）：内部ノード。ノード内の条件は、可能性のある結果またはサンプルの次のアクションを示す。 停止基準（Stopping criterion）。あるノードで分割を行うかどうかを決定する、特定の条件。分割が停止された場合、そのノードはリーフになる。

このような観点から、主なアルゴリズムを以下のように書くことができる。各ノードにおいて、あらかじめ決められた品質損失関数で、2つの部分、すなわち2つの葉に分割することを見つけたい。損失関数が何であるかは後ほど明らかにする。それでも、各ステップにおいて、我々は問題を得たい、その答えが我々の解をより正確にする、ということは直感的に明らかである。条件によって、サンプルは右のノードか左のノードに送られる。

注意すべきは、ノードで分割しても、常に2つの葉ができるわけではないことである。カテゴリカル特徴の場合、ノードはN N の葉に分割される。

さらに、各葉は次のノードとなる。このノードに対して、あらかじめ設定された停止基準を確認する。もしそれが満たされれば、そのノードはリーフ-最終地点-になる。そうでなければ、この動作が再帰的に繰り返される。最終葉（終点ノード）は、そこに落ちてくる各サンプルの予測解を決定する。つまり、1つのリーフからのサンプルはすべて1つのクラスまたは値になる。回帰のタスクでは、リーフは平均的な実数を生成し、分類のタスクでは、リーフはクラスまたはそのクラスに属する確率を生成する。

😊 このアルゴリズムのアーキテクチャにより、データ内の非線形依存性を識別できる解釈可能なツールを構築することができる。また、欠損値や非正規化データを扱うことができるのもツリーの利点である。 🥲 一方で、このアルゴリズムは離散的であるため、最適化が困難であることを意味する。複雑すぎる設計は、木を過剰適合させやすくする。

品質損失関数

一見単純に見えるが、木の主な問題は新しい分割をどのように選択するかである。直感的には、ノードを分割するたびに、異なるオブジェクトは異なる葉に行き、類似したオブジェクトは一緒にいてほしいことは明らかである。

まず、分類の問題を考えてみよう。上の例は、システムの状態に対するシャノン・エントロピー-情報利得とも呼ばれる-を数学的に記述したものである。簡単に言うと、エントロピーは系のカオス度を表すもので、カオス度が高いほどエントロピーが大きいことを意味します。もし、ある葉っぱの中に猫しかいなかったら、その葉っぱのエントロピーはゼロになります。これが私たちの目標です。

もう一つの基準は、経済学からMLに来た人にはなじみがあるかもしれません。それは，Gini Impurityです．これは，分類問題でシステムの情報量を計算するのに使われます．この基準は，データから無作為に抽出したサンプルが，誤ったクラスに割り当てられる確率に基づいています．

回帰問題では，この基準はより些細なもので，分散の減少である．1つの葉に入る値は，平均化される（たとえば，平均値や中央値を計算することによって）．1つの葉に属する変数の分散が小さければ小さいほど，より正確な予測であることを意味する．

!!!Table タスククライテリオン!!!(あとでTag編集) 分類（Classification） 🐶 🐱 情報利得、ジニ不純物 回帰（Regression） 📈 分散の減少

#停止基準と刈り込み 遅かれ早かれ、木の分割を止めなければならない。そうしないと，各葉に1つのサンプルしか入らなくなり，木が過剰適合してしまう．これは，木が訓練セットに適応してしまい，新しいデータへの汎化がうまくいかなくなることを意味する．

情報量の少ない木と過剰適合の木のバランスをとるには、停止基準と枝刈りの2つの方法がある。

枝刈りとは、木の複雑さを軽減し、汎化性を高めるために、木からノードを取り除くことである。一般的なアプローチは、木全体を成長させてから、結果に大きな影響を与えないノードを削除することである。

停止基準とは、分割をやめるかどうかを決めるために、各ノードで確認する基準である。木の最大深さ、葉のサンプル数、ある割合の精度による改善など、非常に多様なものがあります。

まとめ

決定木は、ルート、ノード、リーフから構成される。 各ノードでは、停止基準を意識して、ある条件に基づいて判断が行われる。 判定を行う前に、品質損失関数を用いて条件を選択する。 刈り込みと停止基準により、オーバーフィッティングを回避することができる。