ゼロから: Python で決定木アルゴリズムを実装する

決定木アルゴリズムは、非常に人気のある強力な予測方法です。初心者だけでなく専門家にも簡単に理解できるモデルであるため、人気があります。同時に、結果として得られる決定木は、特定の予測が行われた正確な理由を説明できるため、実際のアプリケーションで非常に人気があります。

同時に、決定木アルゴリズムは、より高度な統合モデル (バギング、ランダム フォレスト、勾配ブースティングなど) の基礎も提供します。

このチュートリアルでは、Python で分類と回帰ツリーのアルゴリズムを最初から実装する方法を学習します。

このチュートリアルを完了すると、次のことが分かります。

データセット内の候補分割ポイントを計算して評価する方法

決定木構造でこれらの分割ポイントを割り当てる方法

これらの分類および回帰アルゴリズムを実際の問題に適用する方法

1. 概要

このセクションでは、分類および回帰ツリー アルゴリズムに関する内容を簡単に紹介し、このチュートリアルで使用する Banknote データセットを示します。

1.1 分類木と回帰木

分類および回帰ツリー (CART) は、分類または回帰予測モデリングの問題に使用できる回帰ツリー アルゴリズムを説明するために Leo Breiman によって造られた用語です。

このチュートリアルでは、主に CART の分類問題への応用について説明します。

バイナリツリーは CART モデルの代表的なものの 1 つです。ここで言及されている二分木は、データ構造やアルゴリズムで言及されている二分木と何ら違いはなく、特別な点はありません (各ノードには 0、1、または 2 個の子ノードを含めることができます)。

各ノードは、ノードで渡され、何らかの変数に従って分類される入力変数を表します (変数は数値であると想定します)。ツリーのリーフ ノード (ターミナル ノードとも呼ばれます) は、予測を行うために使用される出力変数で構成されます。

ツリーが作成されると、各新しいデータ サンプルは各ノードの分割条件に従い、最終的な決定が出力されるまで上からツリーを下っていきます。

バイナリ分類ツリーの作成は、実際には入力空間をセグメント化するプロセスです。再帰バイナリ分割は、スペースを分割するために使用される貪欲アルゴリズムです。これは実際には数値的なプロセスです。一連の入力値が配置されると、一連の分割ポイントが試され、分類された後にコスト関数の値がテストされます。

最適なコスト関数 (通常は最小のコスト関数。最小であることが望まれることが多いため) を持つ分割ポイントが選択されます。貪欲アプローチの原則に従って、すべての入力変数とすべての可能な分割ポイントがテストされ、コスト関数でのパフォーマンスに基づいて評価されます。 （翻訳者注：以下では、回帰問題と分類問題でよく使われるコスト関数について簡単に説明します。）

• 回帰問題: 分割点によって決定された領域内にあるすべてのサンプルの二乗誤差の合計を取得します。
• 分類問題: 一般的に、セグメンテーション後の各ノードの純度を示すことができるジニコスト関数が使用されます。このうち、ノード純度とは、各ノード分類後のトレーニングデータの混同度合いを示す指標です。

分割は、各ノード（分類後）に含まれるトレーニング サンプルの数が最小値のみになるか、ツリーの深さが最大値に達するまで続行されます。

1.2 紙幣データセット

紙幣データセットでは、紙幣の写真の特定の特性分析に基づいて紙幣の真正性を予測する必要があります。

データ セットには 1372 個のサンプルが含まれており、各サンプルは 5 つの数値変数で構成されています。これはバイナリ分類問題です。 5 つの変数の意味とデータ プロパティを以下に示します。

1. ウェーブレット変換後の画像の分散（連続値）

2. ウェーブレット変換後の画像の歪度（連続値）

3. ウェーブレット変換後の画像の尖度（連続値）

4. 画像のエントロピー（連続値）

5. 紙幣の種類（整数、離散値）

以下はデータセットの最初の 5 行のサンプルです。

 3.6216,8.6661,-2.8073,-0.44699,0  
 4.5459,8.1674,-2.4586,-1.4621,0  
 3.866,-2.6383,1.9242,0.10645,0  
 3.4566,9.5228,-4.0112,-3.5944,0  
 0.32924,-4.4552,4.5718,-0.9888,0  
 4.3684,9.6718,-3.9606,-3.1625,0

ゼロ ルール アルゴリズムを使用して最も一般的なカテゴリを予測すると (翻訳者注: つまり、最も一般的なサンプルの種類を見つけて、すべてのサンプルがこのカテゴリに属する​​ことを予測します)、この問題のベンチマーク精度は約 50% になります。

このデータセットをダウンロードして、詳細を確認するには、UCI 機械学習リポジトリにアクセスしてください。

データセットをダウンロードし、現在の作業ディレクトリに配置し、ファイル名を data_banknote_authentication.csv に変更してください。

2. チュートリアル

このチュートリアルは 5 つのパートに分かれています。

1. ジニ係数の紹介

2. 分割ポイントを作成する方法

3. ツリーモデルを生成する方法

4. モデルを使用して予測を行う方法

5. 紙幣データセットのケーススタディ

これらの手順は、CART アルゴリズムを最初から実装し、予測モデリングの問題のサブセットに適用するための基盤を築くのに役立ちます。

2.1 ジニ係数

ジニ係数は、データセットの分割ポイントの品質を評価するコスト関数です。

データセットの分割ポイントは、入力内の特定の属性に基づく分割です。データ セット内のサンプルの場合、分割ポイントは、しきい値に従ってサンプルの対応する属性の値を分類します。彼は、トレーニング セットに現れたパターンに基づいて、データを 2 つのカテゴリに分類することができました。

ジニ係数は、分割ポイントによって作成された 2 つのカテゴリ内のデータ カテゴリ間の混乱の度合いを計算することで、分割ポイントがどの程度優れているかを示します。完全な分割点のジニ係数は 0 です (翻訳者注: つまり、あるクラスに別のクラスのデータが表示されず、各クラスが「純粋」です)。一方、最悪の分割点のジニ係数は 1.0 です (バイナリ問題の場合、各クラスに表示される別のクラスのデータの割合は 50% であり、つまり、データを異なるカテゴリに従ってまったく区別できません)。

以下では、具体的な例を使用してジニ係数の計算方法を説明します。

2 つのデータ セットがあり、それぞれに 2 つの行があります。最初のデータセットのすべての行はクラス 0 に属し、2 番目のデータセットのすべての行はクラス 1 に属します。これは完璧な分岐点です。

まず、次の式に従って、各データ グループ内の各データ カテゴリの割合を計算する必要があります。

割合 =カウント(クラス値) /カウント(行)

したがって、この例では、対応する比率は次のようになります。

グループ_1_クラス_0 = 2 / 2 = 1
グループ_1_クラス_1 = 0 / 2 = 0
グループ_2_クラス_0 = 0 / 2 = 0
グループ_2_クラス_1 = 2 / 2 = 1

ジニ係数は次の式に従って計算されます。

 gini_index =合計（割合 * (1.0 - 割合)）

この例のすべてのグループとすべてのデータクラスの割合を上記の式に代入します。

 gini_index = (group_1_class_0 * (1.0 - group_1_class_0)) +
 (グループ1クラス1 * (1.0 - グループ1クラス1)) +
 (グループ2クラス0 * (1.0 - グループ2クラス0)) +
 (グループ2クラス1 * (1.0 - グループ2クラス1))

単純化すると次のようになります。

ジニ指数 = 0 + 0 + 0 + 0 = 0

以下は、指定されたデータセット (グループとカテゴリはリストとして指定されます) のジニ係数を計算する gini_index() という関数です。これらのアルゴリズムの一部には、空のグループをゼロで割ることを回避できる堅牢性チェックが備わっています。

 # ジニ係数を計算する 分割データセットの場合
gini_index(グループ、クラス値):
ジニ = 0.0
 class_values内のclass_valueの場合:
のために グループ グループ内:
サイズ= len(グループ)
サイズ== 0 の場合:
続く 
割合 = [行[ -1 ]行の グループ] .count (class_value)/ float ( size )
ジニ係数 += (比率 * (1.0 - 比率))
ジニを返す

上記の例に基づいて関数の動作をテストすることも、最悪の分割ポイントをテストすることもできます。完全なコードは次のとおりです。

 # ジニ係数を計算する 分割データセットの場合
gini_index(グループ、クラス値):
ジニ = 0.0
 class_values内のclass_valueの場合:
のために グループ グループ内:
サイズ= len(グループ)
サイズ== 0 の場合:
続く 
割合 = [行[ -1 ]行の グループ] .count (class_value)/ float ( size )
ジニ係数 += (比率 * (1.0 - 比率))
ジニを返す
# ジニ値をテストする 
印刷(gini_index([[[1, 1], [1, 0]], [[1, 1], [1, 0]]], [0, 1]))
印刷(gini_index([[[1, 0], [1, 0]], [[1, 1], [1, 1]]], [0, 1]))

このコードを実行すると、2 つのジニ係数が出力されます。最初のジニ係数は最悪のケースの 1.0 に対応し、2 番目のジニ係数は最良のケースの 0.0 に対応します。

 1.0
 0.0

2.2 分割ポイントの作成

分割ポイントは、データ セット内の属性としきい値で構成されます。

これを要約すると、特定の属性のデータをセグメント化するためのしきい値を決定することになります。これはデータを分類するための実証済みの方法です。

カットポイントの作成には 3 つのステップがあり、最初のステップはジニ係数の計算のセクションで説明しました。残りの 2 つの部分は次のとおりです。

1. データセットを分割します。

2. すべての（実行可能な）分割ポイントを評価します。

それぞれのステップを詳しく見てみましょう。

2.2.1 データセットの分割

データセットを分割するということは、データセットの属性 (または属性リストの下の表) と対応するしきい値を指定して、データセットを 2 つの部分に分割することを意味します。

データが 2 つの部分に分割されると、ジニ係数を使用してその分割のコスト関数を評価できます。

データ セットを分割するには、各データ行を反復処理し、各データ ポイントの対応する属性の値としきい値のサイズに応じて、データ ポイントを対応する部分 (ツリー構造の左フォークと右フォークに対応) に配置する必要があります。

まさにそれを実行する test_split() という関数を次に示します。

 #属性と属性値に基づいてデータセットを分割する
def test_split(インデックス, 値, データセット):
左、右= list()、list()
データセット内の行:
 行[インデックス] < 値の場合:
左に.append(行)
それ以外：
右.append(行)
戻る 左、右 

コードはまだ非常にシンプルです。

コードでは、属性値がしきい値以上であるデータ ポイントが適切なグループに分類されることに注意してください。

2.2.2 すべてのセグメンテーションポイントの評価

Gini 関数 gini_index() と分類関数 test_split() の助けを借りて、分割ポイントを評価するプロセスを開始できます。

特定のデータセットの各属性について、候補となる分割ポイントとして考えられるすべてのしきい値をチェックします。次に、コストに基づいてこれらの分割ポイントを評価し、最終的に最適な分割ポイントを選択します。

最適な分割ポイントが見つかったら、それを決定木のノードとして使用できます。

これはいわゆる網羅的貪欲アルゴリズムです。

この例では、変数名に従ってデータを保存できる決定木内のノードを表すために辞書を使用します。最適な分割ポイントが選択され、ツリー内の新しいノードとして使用されると、対応する属性の添え字、対応する分割値、および分割値に従って分割した後の 2 つのデータ部分が保存されます。

分割後の各データグループは、より小さなデータセットです（分割操作は継続できます）。実際には、元のデータセットのデータが分割ポイントに応じて左フォークまたは右フォークに分割されたデータセットです。各データセットをさらに分割し、決定木全体が構築されるまでこのサイクルを続行できることが想像できます。

以下は、上記の手順を実装する get_split() という関数です。すべての属性 (カテゴリ値を除く) とその属性のすべての値を反復処理し、各反復でデータを分割してその分割ポイントを評価することがわかります。

すべてのチェックが完了すると、最適な分割ポイントが記録され、返されます。

 #データセットに最適な分割ポイントを選択する
def get_split(データセット):
 class_values ​​= list(データセット内の行の行[-1]を設定)
 b_index、b_value、b_score、b_groups = 999、999、999、なし
のために 索引 範囲(len(dataset[0])-1):
データセット内の行:
 グループ = test_split(インデックス, 行[インデックス], データセット)
 gini = gini_index(グループ、クラス値)
 gini < b_scoreの場合:
 b_index、b_value、b_score、b_groups =インデックス、行[インデックス]、ジニ、グループ
戻り値: { 'インデックス' :b_index、 '値' :b_value、 'グループ' :b_groups}

この機能とデータセットのセグメンテーションプロセス全体を、小さな合成データセットでテストできます。

 X1 X2 ええ
2.771244718 1.784783929 0
 1.728571309 1.169761413 0
 3.678319846 2.81281357 0
 3.961043357 2.61995032 0
 2.999208922 2.209014212 0
 7.497545867 3.162953546 1
 9.00220326 3.339047188 1
 7.444542326 0.476683375 1
 10.12493903 3.234550982 1
 6.642287351 3.319983761 1

同時に、異なる色を使用して異なるクラスをマークし、データセットをプロットすることもできます。図からわかるように、X1 軸 (つまり図の X 軸) から値を選択してデータ セットを分割できます。

例のすべてのコードは次のように統合されます。

 #属性と属性値に基づいてデータセットを分割する
def test_split(インデックス, 値, データセット):
左、右= list()、list()
データセット内の行:
 行[インデックス] < 値の場合:
左に.append(行)
それ以外：
右.append(行)
戻る 左、右  
  
 # ジニ係数を計算する 分割データセットの場合
gini_index(グループ、クラス値):
 ジニ = 0.0
 class_values内のclass_valueの場合:
のために グループ グループ内:
サイズ= len(グループ)
 サイズ== 0 の場合:
続く 
 割合 = [行[ -1 ]行の グループ] .count (class_value)/ float ( size )
 ジニ係数 += (比率 * (1.0 - 比率))
ジニを返す
  
 #データセットに最適な分割ポイントを選択する
def get_split(データセット):
 class_values ​​= list(データセット内の行の行[-1]を設定)
 b_index、b_value、b_score、b_groups = 999、999、999、なし
のために 索引 範囲(len(dataset[0])-1):
データセット内の行:
 グループ = test_split(インデックス, 行[インデックス], データセット)
 gini = gini_index(グループ、クラス値)
 print( 'X%d < %.3f Gini=%.3f' % ((インデックス+1), 行[インデックス], gini))
 gini < b_scoreの場合:
 b_index、b_value、b_score、b_groups =インデックス、行[インデックス]、ジニ、グループ
戻り値: { 'インデックス' :b_index、 '値' :b_value、 'グループ' :b_groups} 
  
データセット = [[2.771244718,1.784783929,0],
 [1.728571309,1.169761413,0],
 [3.678319846,2.81281357,0],
 [3.961043357,2.61995032,0],
 [2.999208922,2.209014212,0],
 [7.497545867,3.162953546,1],
 [9.00220326,3.339047188,1],
 [7.444542326,0.476683375,1],
 [10.12493903,3.234550982,1],
 [6.642287351,3.319983761,1]]
分割 = get_split(データセット)
 print( '分割: [X%d < %.3f]' % ((split[ 'インデックス' ]+1), split[ '値' ]))

最適化された get_split() 関数は、各分割ポイントとそれに対応するジニ係数を出力できます。

上記のコードを実行すると、すべてのジニ係数と選択された最適な分割ポイントが出力されます。この例では、最終的な完全な分割ポイントとして X1<6.642 を選択します (対応するジニ係数は 0 です)。

 X1 < 2.771 ジニ係数=0.494
 X1 < 1.729 ジニ係数=0.500
 X1 < 3.678 ジニ係数=0.408
 X1 < 3.961 ジニ係数=0.278
 X1 < 2.999 ジニ係数=0.469
 X1 < 7.498 ジニ係数=0.408
 X1 < 9.002 ジニ係数=0.469
 X1 < 7.445 ジニ係数=0.278
 X1 < 10.125 ジニ係数=0.494
 X1 < 6.642 ジニ係数=0.000
 X2 < 1.785 ジニ係数=1.000
 X2 < 1.170 ジニ係数=0.494
 X2 < 2.813 ジニ係数=0.640
 X2 < 2.620 ジニ係数=0.819
 X2 < 2.209 ジニ係数=0.934
 X2 < 3.163 ジニ係数=0.278
 X2 < 3.339 ジニ係数=0.494
 X2 < 0.477 ジニ係数=0.500
 X2 < 3.235 ジニ係数=0.408
 X2 < 3.320 ジニ係数=0.469
分割: [X1 < 6.642]

データセット内の最適な分割ポイントがわかったので、それを使用して決定木を構築する方法を見てみましょう。

2.3 スパニングツリーモデル

ツリーのルート ノードを作成すると便利です。これは、get_split() 関数を呼び出してデータセット全体を渡すことで実現できます。しかし、ツリーにノードを追加すると、さらに興味深いものになります。

ツリー構造の構築は、主に次の 3 つのステップに分かれます。

1. エンドポイントを作成する

2. 再帰的に分割する

3. ツリー全体を構築する

2.3.1 ターミナルノードの作成

いつ木の成長を止めるかを決める必要があります。

これは、ツリーの深さと各ノードが分割された後のデータ ポイントの数という 2 つの条件を使用して制御できます。

最大ツリー深度: これは、ルートから始まるツリー内のノード数の上限を表します。ツリー内のノードの数がこの上限に達すると、アルゴリズムはデータの分割と新しいノードの追加を停止します。より強力なツリーはより複雑になり、トレーニング セットに過剰適合する可能性が高くなります。

ノード レコードの最小数: これは、ノードがデータを分割した後の部分データの最小数です。最小値に達するか、または最小値が低下すると、アルゴリズムはデータの分割と新しいノードの追加を停止します。データセットを数個のデータ ポイントのみで 2 つの部分に分割する分割ノードは、詳細すぎるとみなされ、トレーニング セットに過剰適合する可能性が高くなります。

これら 2 つの方法は、ユーザーが指定したパラメータに基づいてツリー モデルを構築するプロセスに参加します。

さらに、別の状況もあります。アルゴリズムは分割ポイントを選択する場合があり、その後、すべてのデータが同じグループに分割されます (つまり、左のフォークまたは右のフォークの 1 つのブランチにのみデータがあり、他のブランチにはデータがありません)。この場合、ツリーの他のブランチにデータがないため、ノードの分割と追加の作業を続行できません。

上記に基づいて、ツリーの「成長」を停止するための判断メカニズムがすでにいくつかあります。ツリーが特定のノードで成長を停止すると、そのノードはターミナルノードと呼ばれ、最終的な予測を行うために使用されます。

予測プロセスは、グループ表現値を選択することによって実行されます。ツリーが走査され、最後のノード分割後にデータ グループに入ると、アルゴリズムはグループ内で最も一般的な値を予測値として選択します。

ここでは、各レシート セットのターミナル値を選択する to_terminal() という関数を示します。データ ポイントのセット内で最も一般的な値を返します。

 #ターミナルノード値を作成する
def to_terminal(グループ):
結果 = [行[-1 ]行の グループ]
戻る  max ( set (結果 )、キー= 結果.count )

2.3.2 再帰分割

ターミナルノードを作成する方法とタイミングを理解したので、ツリー モデルの構築を開始できます。

ツリーランドモデルを構築するには、指定されたデータセットに対して上記で定義した get_split() 関数を繰り返し呼び出して、ツリー内にノードを継続的に作成する必要があります。

既存のノードの下に追加された新しいノードは子ノードと呼ばれます。ツリー内の任意のノードには、子ノードが存在しない (その場合、ノードは終端ノードになります)、子ノードが 1 つ存在する (その場合、ノードは直接予測できます)、または子ノードが 2 つ存在する場合があります。プログラムでは、ノードを表す辞書で、ツリーの 2 つの子ノードに left と right という名前を付けます。

ノードが作成されると、ノードを分割して取得した 2 つのサブデータセットに対して同じ関数を再帰的に呼び出し、サブデータセットを分割して新しいノードを作成できます。

以下はこの再帰プロセスを実装する関数です。入力パラメータには、ノード (node)、最大ツリー深度 (max_depth)、ノード レコードの最小数 (min_size)、および現在のツリー深度 (depth) が含まれます。

当然のことながら、関数が最初に実行されると、ルート ノードが渡され、現在の深さは 1 になります。関数の機能は次のステップに分かれています。

1. まず、ノードによって分割されたデータの 2 つの部分が抽出されて使用され、ノード内のデータが削除されます (分割作業が進むにつれて、以前のノードは対応するデータを使用する必要がなくなります)。

2. 次に、ノードの左フォークと右フォークのデータセットが空かどうかを確認します。そうであれば、エンドポイントを作成します。

3. 同時に、最大深度に達したかどうかを確認します。そうであれば、エンドポイントを作成します。

4. 次に、左の子ノードに対してさらに操作を実行します。グループ内のデータ数がしきい値より少ない場合、ターミナルノードが作成され、それ以降の操作は停止されます。それ以外の場合は、フォークが最下部に到達するまで深さ優先方式でノードを作成して追加します。

5. 右の子ノードに対して上記の手順を繰り返し、終端ノードに到達するまでノードを追加し続けます。

2.3.3 ツリー全体の構築

すべてをひとつにまとめます。

ツリーを作成するには、ルート ノードを作成し、split() 関数を再帰的に呼び出してデータを継続的に分割し、ツリー全体を構築します。

以下は、上記の機能を実装する build_tree() 関数の簡略化されたバージョンです。

 # 決定木を構築する
def build_tree(train, max_depth, min_size):
ルート = get_split(データセット)
分割(ルート、最大深さ、最小サイズ、1)
ルートを返す

上記のように、合成データセットでプロセス全体をテストできます。以下に完全なケーススタディを示します。

また、決定木のノードを 1 つずつ再帰的に出力できる print_tree() 関数も含まれています。これによって出力されるのは明らかなツリー構造ではありませんが、ツリー構造の全体的な印象を与え、意思決定に役立ちます。

 #属性と属性値に基づいてデータセットを分割する
def test_split(インデックス, 値, データセット):
左、右= list()、list()
データセット内の行:
行[インデックス] < 値の場合:
左に.append(行)
それ以外：
右.append(行)
戻る 左、右  
 
 # ジニ係数を計算する 分割データセットの場合
gini_index(グループ、クラス値):
ジニ = 0.0
 class_values内のclass_valueの場合:
のために グループ グループ内:
サイズ= len(グループ)
サイズ== 0 の場合:
続く 
割合 = [行[ -1 ]行の グループ] .count (class_value)/ float ( size )
ジニ係数 += (比率 * (1.0 - 比率))
ジニを返す
 
 #データセットに最適な分割ポイントを選択する
def get_split(データセット):
 class_values ​​= list(データセット内の行の行[-1]を設定)
 b_index、b_value、b_score、b_groups = 999、999、999、なし
のために 索引 範囲(len(dataset[0])-1):
データセット内の行:
グループ = test_split(インデックス, 行[インデックス], データセット)
 gini = gini_index(グループ、クラス値)
 gini < b_scoreの場合:
 b_index、b_value、b_score、b_groups =インデックス、行[インデックス]、ジニ、グループ
戻り値: { 'インデックス' :b_index、 '値' :b_value、 'グループ' :b_groups} 
 
 #ターミナルノード値を作成する
def to_terminal(グループ):
結果 = [行[-1 ]行の グループ]
戻る  max ( set (結果 )、キー= 結果.count ) 
 
 #ノードの子分割を作成するか、ターミナルを作成します
def split(ノード、最大深さ、最小サイズ、深さ):
左、右= ノード[ 'グループ' ]
 del(ノード[ 'グループ' ])
 ＃チェック 分割なし​​
そうでなければ 左 または ない 右：
ノード[ 'left' ] = ノード[ 'right' ] = to_terminal( left + right )
戻る 
 ＃チェック のために 最大深度
深さ >= max_depth の場合:
ノード[ '左' ]、ノード[ '右' ] = to_terminal(左)、to_terminal(右)
戻る 
 #左の子プロセス
len( left ) <= min_sizeの場合:
ノード[ 'left' ] = to_terminal( left )
それ以外：
ノード[ 'left' ] = get_split( left )
分割(ノード[ 'left' ], 最大深さ, 最小サイズ, 深さ+1)
 #右の子プロセス
len(右) <= min_sizeの場合:
ノード[ 'right' ] = to_terminal( right )
それ以外：
ノード[ 'right' ] = get_split( right )
分割(ノード[ 'right' ], max_depth, min_size, depth+1) 
 
 # 決定木を構築する
def build_tree(train, max_depth, min_size):
ルート = get_split(データセット)
分割(ルート、最大深さ、最小サイズ、1)
ルートを返す
 
 # 決定木を印刷する
def print_tree(ノード、深さ=0):
 isinstance(ノード、辞書)の場合:
 print( '%s[X%d < %.3f]' % ((深さ* ' ' , (ノード[ 'インデックス' ]+1), ノード[ '値' ])))
 print_tree(ノード[ 'left' ], 深さ+1)
 print_tree(ノード[ 'right' ], 深さ+1)
それ以外：
 print( '%s[%s]' % ((depth* ' ' , ノード))) 
 
データセット = [[2.771244718,1.784783929,0],
 [1.728571309,1.169761413,0],
 [3.678319846,2.81281357,0],
 [3.961043357,2.61995032,0],
 [2.999208922,2.209014212,0],
 [7.497545867,3.162953546,1],
 [9.00220326,3.339047188,1],
 [7.444542326,0.476683375,1],
 [10.12493903,3.234550982,1],
 [6.642287351,3.319983761,1]]
ツリー = build_tree(データセット, 1, 1)
 print_tree(ツリー)

実行時に、ツリーの最大深度を変更し、印刷されたツリーへの影響を確認できます。

最大深度が 1 の場合 (build_tree() 関数を呼び出すときの 2 番目の引数)、ツリーは以前に見つけた完全な分割ポイント (ツリー内の唯一の分割ポイント) を使用していることがわかります。ツリーには、決定スタンプとも呼ばれる 1 つのノードのみがあります。

 [X1 < 6.642]  
 [0]  
 [1]

最大深度が 2 に増加すると、分割が必要ないときにもアルゴリズムが分割を実行するように強制します。その結果、X1 属性は左フォークと右フォークで 2 回使用され、すでに完全に分割されたデータが分割されます。

 [X1 < 6.642]
 [X1 < 2.771]
 [0]
 [0]
 [X1 < 7.498]
 [1]
 [1]

最後に、最大深度が 3 の場合を試してみましょう。

 [X1 < 6.642]
 [X1 < 2.771]
 [0]
 [X1 < 2.771]
 [0]
 [0]
 [X1 < 7.498]
 [X1 < 7.445]
 [1]
 [1]
 [X1 < 7.498]
 [1]
 [1]

これらのテストは、不要な分割を避けるためにコードを最適化できることを示しています。拡張セクションの関連コンテンツを参照してください。

これで決定木を（完全に）作成できるようになったので、それを使用して新しいデータに対して予測を行う方法を見てみましょう。

2.4 予測モデルの使用

決定木モデルを使用して意思決定を行うには、与えられたデータに基づいて決定木全体を走査する必要があります。

以前と同様に、このプロセスを実装するには再帰関数を使用する必要があります。この場合、特定の分割ポイントが特定のデータに与える影響に基づいて、同じ予測ルールが左の子ノードまたは右の子ノードに適用されます。

子ノードが予測結果として返すことができる終端ノードであるかどうか、または考慮する必要がある次のレイヤーの分割ノードが含まれているかどうかを確認する必要があります。

以下は上記のプロセスを実装する predict() という関数です。特定のノードのインデックスと値をどのように処理するかを確認できます。

次に、合成データセットを使用して関数をテストします。以下は、1 つのノード (つまり、決定スタンプ) のみを持つハードコードされたツリーを使用する例です。この場合、データセット内の各データ ポイントに対して予測が行われます。

例を実行すると、各データ ポイントの予測が期待どおりに出力されます。

予想=0、結果=0
予想=0、結果=0
予想=0、結果=0
予想=0、結果=0
予想=0、結果=0
予想=1、結果=1
予想=1、結果=1
予想=1、結果=1
予想=1、結果=1
予想=1、結果=1

これで、決定木を作成する方法だけでなく、それを使用して予測を行う方法もわかりました。それでは、このアルゴリズムを実際のデータ セットに適用してみましょう。

2.5 紙幣データセットのケーススタディ

このセクションでは、紙幣データセットで CART アルゴリズムを使用するプロセスについて説明します。

最初のステップは、データをインポートし、読み込まれたデータを数値形式に変換して、分割ポイントの計算に使用できるようにすることです。このため、補助関数 load_csv() を使用してデータをロードし、str_column_to_float() を使用して文字列データを浮動小数点数に変換します。

アルゴリズムのパフォーマンスを評価するために、5 段階のクロス検証を使用します。つまり、1 つのレコードには 1273/5 = 274.4 または 270 のデータ ポイントがあることになります。補助関数evaluate_algorithm() を使用してクロス検証セットでのアルゴリズムのパフォーマンスを評価し、accuracy_metric() を使用して予測の精度を計算します。

完成したコードは次のとおりです。

上記で使用されているパラメータは次のとおりです: max_depth は 5、min_size は 10。いくつかの実装を行った後、上記の CART アルゴリズムで使用されるパラメータを決定しましたが、これは使用されるパラメータが最適であることを意味するものではありません。

この例を実行すると、データの各部分の平均分類精度と、データのすべての部分の平均パフォーマンスが出力されます。

データから、CART アルゴリズムによって選択された分類設定では、平均分類精度が約 83% 達成されていることがわかります。そのパフォーマンスは、精度がわずか 50% 程度のゼロ ルール アルゴリズムよりもはるかに優れています。

スコア: [83.57664233576642, 84.30656934306569, 85.76642335766424, 81.38686131386861, 81.75182481751825]

平均精度: 83.358%

3. 拡張

このセクションでは、このセクションについて探索できる拡張項目を一覧表示します。

1. アルゴリズムの調整: 紙幣データセットで使用される CART アルゴリズムは調整されていません。より良い、より最適な結果を得るために、さまざまなパラメータ値を試すことができます。

2. クロスエントロピー: 分割ポイントを評価するために使用されるもう 1 つのコスト関数は、クロスエントロピー関数 (対数損失) です。代わりに、このコスト関数を使用してみることもできます。

3. ツリーの剪定: トレーニング中の過剰適合を減らすもう 1 つの重要な方法は、ツリーの剪定です。いくつかの剪定方法を研究して実装してみることもできます。

4. カテゴリ データセット: 上記の例では、ツリー モデルは数値データまたは順序付きデータを解くように設計されています。カテゴリ データを処理できるように、ツリー モデルを変更してみることができます (主にセグメンテーション プロパティを変更し、ソートではなく等式を使用します)。

5. 回帰: このモデルは、さまざまなコスト関数とターミナルノードを作成するさまざまな方法を使用して、回帰問題を解決するために使用できます。

6. その他のデータセット: このアルゴリズムを UCI 機械学習リポジトリの他のデータセットで試すことができます。

[この記事は、51CTOコラムニストのMachine Heart、WeChatパブリックアカウント「Machine Heart（id: Almosthuman2014）」からのオリジナル記事です]

この著者の他の記事を読むにはここをクリックしてください