2024年09月21日

実例で見る機械学習：意思決定ツリーの基礎

Ai, システム開発, 機械学習

はじめに

人工知能の分野では、データから学習し適切な決定を下すアルゴリズムを開発するための、さまざまなアプローチがあります。Pedro Domingosは彼の著書「The Master Algorithm」で、機械学習の分野における主要なアルゴリズムを5つ紹介しています。

Symbolists (Logic-based algorithms): Symbolistsは、シンボルと論理ルールを使用してモデルを表現し、意思決定を行うことに焦点するアルゴリズムです。このカテゴリーの代表的な例は、意思決定ツリー（Decision tree）であり、意思決定とその結果をツリーのようなモデルで表現します。
Connectionists (Neural networks): Connectionistsは人間の脳の構造と機能に触発されたニューラルネットワークを使用してモデル化するアルゴリズムです。 Deepニューラルネットワーク、Recurrentニューラルネットワーク、Convolutionalニューラルネットワーク（DNN、RNN, CNN）が代表的な例です。
Evolutionaries (Genetic algorithms): Evolutionariesは、生物の進化方式に基づいたアプローチで、遺伝的アルゴリズム（Genetic Algorithms）や進化戦略（Evolutionary Strategies）を使用して問題を解決します。
Bayesians (Probabilistic models): Bayesiansアルゴリズムは、確率と統計を利用して意思決定の不確実性をモデル化するアルゴリズムです。Logistic regressionやBayesian networksが代表的な例です。
Analogizers (Instance-based learning): Analogizersは、過去の経験や既存のデータに基づいて新しい問題を解決するアルゴリズムであり、過去の事例やデータポイントを保存し、新しいデータポイントが現れたときに類似した過去の事例と比較して予測や分類を行います。ｋ－NNやサポートベクターマシン（SVM）が代表的な例です。

この記事では、 Symbolistsの一部である 意思決定ツリー（Decision tree） について掘り下げていきます。意思決定ツリーは、Symbolistsの中で最も直感的に理解しやすく、広く使用されているため、これを取り上げました。意思決定ツリーを利用することで、意思決定のプロセスとその結果をツリー構造で表現することができ、データに基づいた意思決定を簡単に実現することができます。

202409_decisiontrees_01 参照元：The Master Algorithm

意思決定ツリー（Decision tree）

意思決定ツリーは、入力された特徴量データ（Input features data）に基づいてラベルデータ（Label data）の値を予測するための強力な機械学習アルゴリズムで、機械学習の分野で広く使われるアルゴリズムの一つです。意思決定ツリーでは、複雑な意思決定プロセスをシンプルで理解しやすいステップまで分解し、それを元にツリー構造を構築することで意思決定を行います。

構造

意思決定ツリーは、ノード（node）とそれぞれのノードを連結するブランチ（branch）で構成され、ツリー構造を形成します。ここでは、ノードの種類とその機能を説明します。

①Root node： Root nodeは意思決定ツリーの出発点であり、データセット全体を表し、最初にデータが意思決定ルールに基づいて分割されるノードです。
②Decision node：このノードは意思決定ツリーの中間ノードであり、特定の基準に基づいてデータを分割します。各Decision nodeでは、データをより小さなサブセットに分割する質問や決定ルールを表します。
③Terminal Nodes (Leaf Nodes)： Terminal Nodes（Leaf Nodesとも呼ばれます）は、意思決定ツリーの終点にあるノードです。これ以上分割することはできず、最終的な決定や分類を表します。各Terminal Nodesでは、与えられた入力データに対する予測結果を提供します。

参照元：Uhmb, T. H., & Michibayashi, K. (2023). Relationships between intensity of deformation induced Cr–Al chemical zoning and geometrical properties of spinel: An approach applying machine learning analyses. Journal of Structural Geology, 177, 104977.

ノード内の情報

意思決定ツリーのそれぞれのノードは、以下のような重要な情報を含んでいます。

① Node Criterion： Node Criterionはノードでデータを分割するために使用するルールや条件であり、データがどのようにブランチで分割されるかを決定します。
② Gini Score： Gini Scoreはノードの純度を測る指標であり、ノード内のラベルデータカテゴリーの多様性を示します。 Gini Scoreが高いほど、ラベルデータのカテゴリーの種類が多く、 Gini Scoreがゼロであれば、そのノードには一つのラベルデータカテゴリーしか含まれていないことを意味します。すべてのTerminal Nodesは Gini Scoreがゼロであり、単一のラベルデータカテゴリーを持つ純粋なノードを示します。
③ Samples ：Samplesはそれぞれのノードに存在するデータの数を示します。
④ Value：Valueはノード内に存在するそれぞれのラベルデータカテゴリーの分布を示します。
⑤ Class：Classはそれぞれのノードで要則、決定したラベルデータカテゴリーを示します。

意思決定ツリーの原理

意思決定ツリーは、 Root nodeから始まり、ツリーを下向きに進みながら意思決定アルゴリズムを作ります。以下は、その動作プロセスです。

①Root Nodeで始まる　→ ②Decision Nodesでデータを分割　→ ③続けて分割 → ④Terminal Nodesに到達

① データセット全体を表すRoot Nodeからスタートします。
② ノードの決定ルールを基準にしてデータを二つのブランチに分割します。各ブランチは、ノードの基準に対する真または偽の結果を表します。
③ データをDecision Nodesで分割するプロセスを、すべてのデータポイントが分類されるまで繰り返します。Terminal Nodeに到達した時点でこのプロセスを停止します。
④ それ以上分割できなくなったノードが、最終的な分類や予測を表します。

可視化

典型的な意思決定ツリーの図は、ノードとノードの間がブランチで接続されている構造を示して、各 Decision Nodesは二つのブランチに分かれ、左のブランチは基準が真である結果を、右のブランチは基準が偽である結果を表します。ツリー構造の視覚化は、Pythonのライブラリであるscikit-learnの「graphviz」アルゴリズムを使用して行うことができます。また、「DecisionTreeClassifier」アルゴリズムを使用することで、視覚化されたツリー構造内の各ノードの基準を分析し、データセットの分類基準を数学的に表現することができます。

from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import export_graphviz
import graphviz

# X_train, X_test, y_train, y_test, data_delta_scaledは事前に定義されていると仮定する。

# 学習
dt_clf = DecisionTreeClassifier()
dt_clf.fit(X_train, y_train)

# Defining feature、target namesを定義。
data_delta_scaled.columns
data_delta_scaled.feature_names = ['delta_20_60', 'delta_60_100']
data_delta_scaled.target_names = ['cluster1', 'cluster2', 'cluster3']

# 学習された意思決定ツリーを可視化
export_graphviz(dt_clf, out_file="tree.dot", class_names=data_delta_scaled.target_names, 
                feature_names=data_delta_scaled.feature_names, impurity=True, filled=True)

with open("tree.dot") as f:
    dot_graph = f.read()
graphviz.Source(dot_graph)

#参照元：Uhmb, T. H., & Michibayashi, K. (2023). Relationships between intensity of deformation induced Cr–Al chemical zoning and geometrical properties of spinel: An approach applying machine learning analyses. Journal of Structural Geology, 177, 104977.

意思決定ツリーを含むほとんどの機械学習モデルを設計する際には、学習データセットと評価データセットの分離、さまざまな評価方法を通じたモデルの評価（精度、適合率、再現率、F1スコアなど）、モデル評価に基づいたハイパーパラメータの調整が必要です。しかし、この記事では意思決定ツリーの紹介に重点を置いているため、コード部分ではモデルの設計と可視化の方法のみを提供いたします。

実例

意思決定ツリーの動作を説明するために、例のデータセットで考えてみます。このデータセットはUhmb et al.（2023）で利用した特徴量データとラベルデータで構成されており、これらを使って意思決定ツリーを訓練しました。

特徴量データ（Feature Data）

特徴量データは「∆CA (Delta CA)」、「∆CE (Delta CE)」で構成され、Standard scalerで標準化されているデータです。「∆CA」、「∆CE」は-3.5から3間の数値を持っており、意思決定ツリーはこの数値を基準にしてモデルを作成します。

ラベルデータ（Label Data）

ラベルデータはMean-shiftクラスタリング（Uhmb et al., 2023）によって決定された「Cluster 1」、「Cluster 2」、「Cluster 3」の3つのグループで構成されています。それぞれの特徴量データのデータポイントはこれらのグループのいずれかに割り当てられます。

意思決定ツリー

意思決定ツリーは、前のSectionで話した特徴量データ（∆CAおよび∆CE）とラベルデータ（Cluster 1、Cluster 2、Cluster 3）に基づいて構築されます。この例のツリー構造は以下のような11個の様々なノードで構成されています。

1つのRoot Node: ツリーの出発点になるノード。
4つのDecision Nodes: 特定の基準に基づいてデータが分割されるノード。
6つのTerminal Nodes: ツリーの終点で、最終的な分類が行われるノード。

それぞれのClusterは、6つのTerminal Nodesのうちの1つによって分類されます。Clusterの分類を担当するノードは以下のFigureに示されており、 Terminal Nodesは4、8、9、10、11、7ノードになります。

202409_decisiontrees_03 参照元：Uhmb, T. H., & Michibayashi, K. (2023). Relationships between intensity of deformation induced Cr–Al chemical zoning and geometrical properties of spinel: An approach applying machine learning analyses. Journal of Structural Geology, 177, 104977.

意思決定ツリーの重要ノード

ツリー構造における重要なノードは、 Root Node、Terminal NodeまたはDecision Nodeであり、多くのSample数と低いGini Scoreを持つノードになります。今からはそれぞれのラベルデータカテゴリー（cluster1、cluster2、cluster3）に対する重要ノードについて説明します。

cluster 1:
- 重要ノード: Root node (Node 1)、 Decision node (Node 2).
- Terminal Node: Node 4.
- 説明: Root nodeから分割プロセスを開始し、 Decision node2がデータをさらに分割して Terminal Node4に導き、これがcluster1を分類します。
cluster 2:
- 重要ノード: Root node (Node 1), Decision nodes (Nodes 3 and 6).
- Terminal Node: Node 11.
- 説明: Root nodeがデータを分割し、続いてDecision node3と6でさらに分割され、Terminal Node11に導かれ、これがcluster2を分類します。
cluster 3:
- 重要ノード: Root node (Node 1) and Decision node (Node 3).
- Terminal Node: Node 7.
- 説明: Root nodeから分割プロセスを開始し、Decision node３がデータをさらに分割してTerminal Node７に導き、これがCluster３を分類します。

重要ノードから考察した各Clusterにおける分割基準は、次のように表現できます。

cluster1={∆CA ≤ 0.176, ∆CE ≤ 0.311}
cluster2={∆CA < 0.176, -0.527 < ∆CE ≤ 0.826}
cluster3={∆CA > 0.176, ∆CE > 0.826}

このように、clusteringで分類され明確な基準がなかったCluster 1、Cluster 2、Cluster 3は、意思決定ツリーを用いて分類モデルを構築することで、数学的な分類基準を確認することができます。

要約

人工知能の分野では、データから学習し意思決定を行う様々なアルゴリズムがあり、Pedro Domingosの「The Master Algorithm」では5つの主要なアルゴリズムを紹介しています。（Symbolists、Connectionists、Evolutionaries、Bayesians、Analogizers）この記事では、Symbolistsに属する意思決定ツリーに焦点を当てました。
意思決定ツリーは、データを分割しながら予測や分類を行うツリー構造を持つアルゴリズムです。このツリーはRoot nodeから始まり、Decision nodeを経て、Terminal nodeで最終的な予測を行います。各ノードは分割基準やGini scoreなどの重要な情報を持ち、データに基づいてモデルを作ります。意思決定ツリーは、ルートノードから始まり、決定ノードを通過して終端ノードに到達するまで進みます。各ノードはデータを2つのbranchesに分割する基準を適用します。左のブランチは基準が真である結果を、右のブランチは基準が偽である結果を表します。このプロセスはすべてのデータポイントが特定のカテゴリーを表すTerminal nodeのいずれかに分類されるまで続きます。
意思決定ツリーの最大の利点は、その直感的でわかりやすい構造にあります。ツリー構造は、データの分岐と分類の過程を視覚的に表現するため、複雑なデータ分析を簡単に理解できます。また、意思決定ツリーはデータに基づいて明確なルールを提供するため、モデルの解釈が容易であり、さまざまな用途において有効な手段となっています。

参考

Cho, J. H., & Kurup, P. U. (2011). Decision tree approach for classification and dimensionality reduction of electronic nose data. Sensors and Actuators B: Chemical, 160(1), 542-548.
Domingos, P. (2015). The master algorithm: How the quest for the ultimate learning machine will remake our world. Basic Books.
Myles, A. J., Feudale, R. N., Liu, Y., Woody, N. A., & Brown, S. D. (2004). An introduction to decision tree modeling. Journal of Chemometrics: A Journal of the Chemometrics Society, 18(6), 275-285.
Uhmb, T. H., & Michibayashi, K. (2023). Relationships between intensity of deformation induced Cr–Al chemical zoning and geometrical properties of spinel: An approach applying machine learning analyses. Journal of Structural Geology, 177, 104977.