機械学習の決定木とランダムフォレストモデル

[[206785]]

決定木

導入

決定木は機械学習において非常に一般的な分類方法です。すべてのアルゴリズムの中で最も直感的で理解しやすいアルゴリズムとも言えます。最も簡単な例を見てみましょう。

A: 食べますか？

B: あなたが行くなら私も行きます。

「あなたが行くなら、私も行きます」これは典型的な意思決定ツリーの考え方です。

もう一つの例を挙げます。

もし誰かが私にお金を借りるよう頼んできた場合（もちろんそんなことはまずありませんが…）、私はその人にお金を貸すべきでしょうか？私は、お金を持っているかどうか、私自身がそのお金を必要としているかどうか、そして相手の信用度が高いかどうかという3つの要素に基づいて答えを決めます。

より一般的な視点に目を向けてみましょう。いくつかの特徴的なデータについては、このような決定木を作成できれば、サンプルの結論を非常に簡単に予測することもできます。したがって、問題は、適切な決定木を見つける方法、つまり、これらの機能をどのように並べ替えるかになります。

特徴を分類する前に、特定の特徴について決定を下すときに、分類されたサンプルの純度が可能な限り高いこと、つまり、ブランチノードのサンプルが可能な限り同じカテゴリに属することを確実に望んでいると想像してください。

したがって、ルートノードを選択するときは、「ブランチノードの純度を最も高くできる」機能を選択する必要があります。ルートノードを処理した後、ルートノードの考え方をそのブランチノードに再帰的に適用し続け、ツリーを形成できるようにします。これは実は貪欲アルゴリズムの基本的な考え方です。では、「最高の純度」をどのように定量化するのでしょうか? エントロピーは純度を測定するための最も一般的に使用される指標であるため、当然の選択です。その数式は次のようになります。

ここで、N は結論が取り得る値の数を表し、p は k 番目の値を取ったときの発生確率を表します。サンプルの場合は、発生頻度 / 総数になります。

エントロピーが小さいほど、サンプルは純粋になります。

2 点分布サンプル X (x=0 または 1) のエントロピー関数グラフを使用して説明しましょう。横軸はサンプル値が 1 になる確率を表し、縦軸はエントロピーを表します。

p(x=1)=0、つまりすべてのサンプルが0のとき、エントロピーは0であることがわかります。

p(x=1)=1、つまりすべてのサンプルが1の場合、エントロピーも0になります。

p(x=1)=0.5、つまり0と1がそれぞれサンプルの半分を占める場合、エントロピーは最大値に達する可能性があります。

これを拡張すると、サンプルXはn個の値（x1...xn）を取ることができます。 p(xi) が 1/n に等しい場合、つまりサンプルが完全に均一である場合、エントロピーは最大に達することが証明できます。 p(xi)の1つが1で他が0の場合、つまりサンプル値がすべてxiの場合、エントロピーは最小になります。

決定木アルゴリズム

ID3

サンプルセット X では、特徴 a に値 (a1、a2...an) があるとします。サンプルセット X を特徴 a (ルートノードとして) で分割すると、必ず n 個のブランチノードが存在します。前述したように、分割後、ブランチノードのサンプルが可能な限り純粋になること、つまり、ブランチノードの「総エントロピー」が可能な限り小さくなることが期待されます。

各ブランチのノード数が異なるため、「総エントロピー」を計算する際には重み付け計算を行う必要があります。i 番目のノードのサンプル数を W(ai) とすると、すべてのサンプルの中でのその重みは W(ai) / W(X) です。したがって、総エントロピーは次のようになります。

この式は一言で言えば、重み付け後の各ノードのエントロピーの合計を意味します。この値が小さいほど、純度が高くなります。

ここで、情報ゲイン G(X, a) という用語を導入します。これは、特徴 a がサンプルにもたらす情報の増加を意味します。式は次のとおりです。H(X) はサンプルの固定値なので、情報ゲイン G はできるだけ大きくする必要があります。情報ゲインを最大化する特徴をターゲットノードとして見つけ、徐々に再帰的にツリーを構築します。これがID3アルゴリズムの考え方です。情報ゲインの計算を説明するために簡単な例を見てみましょう。

上記の例では、特徴1の情報ゲインを計算しました。

まずサンプルのエントロピーH(X)を計算する

総エントロピーを再度計算すると、特徴 1 には 3 つのノード A、B、C があり、それぞれ 6、6、5 であることがわかります。

したがって、Aの重みは6/(6+6+5)、Bの重みは6/(6+6+5)、Cの重みは5/(6+6+5)です。

分割後のノードの純度が可能な限り高くなることを期待するため、ノード A、B、C のエントロピーを個別に計算する必要があります。

特徴1 = A: 3つはい、3ついいえ、そのエントロピーは

特徴1 = B: 2 はい、4 いいえ、そのエントロピーは

特徴1 = C: 4つの「はい」と1つの「いいえ」、そのエントロピーは

ブランチノードの合計エントロピーは次の式に等しくなります。

特徴1の情報ゲインは0.998-0.889=0.109に等しい。

同様に、他の特徴の情報ゲインを計算し、最終的に情報ゲインが最大の特徴をルートノードとして取得することもできます。

上記の計算は、経験的条件付きエントロピーを使用して導くこともできます: G(X,A)=H(X) - H(X|A)。興味のある学生はこれについて学ぶことができます。

C4.5

実際、ID3 アルゴリズムには非常に明白な問題があります。

id または name と呼ばれる (一意の) 機能を持つサンプルセットがある場合、失敗に終わります。 n 個のサンプルがある場合、ID 機能はサンプルを必ず n 個の部分に分割します。つまり、n 個のノードがあり、各ノードには 1 つの値のみがあり、各ノードのエントロピーは 0 になります。つまり、すべてのブランチノードの合計エントロピーが 0 の場合、この機能の情報ゲインは確実に最大値に達します。したがって、この時点で決定木アルゴリズムとして ID3 を使用する場合、ルートノードは特徴 ID である必要があります。しかし、明らかにこれは不合理です。。。

もちろん、上記は極端なケースです。一般的に、特徴がサンプルをあまりにまばらに分割する場合も、これは不合理です (言い換えると、より多くの値を持つ特徴が優先される傾向があります)。この問題を解決するために、C4.5 アルゴリズムは情報ゲイン率を特徴選択基準として使用します。

いわゆる情報ゲイン率は、分割された情報の 1 つの項目を除く情報ゲインに基づいており、値が高い属性にペナルティを課します。

そして、この分割された情報は、実際には特徴数のエントロピー H(A) です。

なぜこれを減らすことができるのでしょうか? 上記の id の例で理解してみましょう。 id が n 個のサンプルを n 個の部分に分割する場合、特徴 id の値の確率は 1/n です。記事の冒頭で述べたように、サンプルが完全に均一な場合、エントロピーは最大になります。

そのため、この場合、idを特徴として情報ゲインは最大になりますが、ペナルティファクタ分割情報も最大になるため、そのゲイン率は低下します。これがC4.5の考え方です。

カート

決定木の最終的な目標は、サンプルの純度を区別するための定量的な基準を見つけることです。 CART 決定木では、ジニ係数が測定基準として使用されます。ジニ係数の直感的な理解は、セットから 2 つのサンプルをランダムに選択した場合、サンプルセットが純粋であればあるほど、異なるサンプルが得られる確率が低くなるということです。この確率はジニ係数を反映しています。

つまり、サンプルに K 個のカテゴリがある場合です。サンプルの特徴 a に n 個の値があると仮定すると、ノードが異なるサンプルを取る確率は次のようになります。

したがって、k 個のカテゴリの確率の合計はジニ係数と呼ばれます。

ジニ指数は、すべてのノードのジニ係数を加重処理したものです。

計算後、ジニ係数が最も小さい特徴を最適な分割特徴として選択します。

剪定

剪定の目的は、実際には過剰適合を防ぐことであり、決定木が過剰適合を防ぐための主な手段です。決定木では、分類されたトレーニングサンプルをできるだけ多く取得するために、決定木は成長し続けます。ただし、トレーニングサンプルが過度に学習され、一部のサンプルの固有の属性が一般的な属性と見なされる場合があります。現時点では、過剰適合のリスクを減らすために、いくつかのブランチを積極的に削除する必要があります。

一般的に、剪定には事前剪定と事後剪定の 2 つの方法があります。

事前剪定

通常、ノードサンプルが 100% 純粋になると、ツリーの成長は停止します。しかし、これは過剰適合を引き起こす可能性があるため、100% 成長させる必要はありません。その前に、早期に終了するための終了条件をいくつか設定します。これは事前剪定と呼ばれ、決定木が構築される前に行われます。

一般的に、当社の事前剪定方法は次のとおりです。

1. ツリーの深さを制限する

2. ノードの子ノードの数が閾値未満である

3. ノードエントロピーのしきい値を設定する

等

剪定後

名前が示すように、この剪定は決定木の構築プロセスの後に行われます。ポストプルーニングアルゴリズムは数多くあり、その中には非常に奥深いものもあります。ここでは、単純なアルゴリズムのアイデアについてのみ触れ、詳細には触れません。

エラー削減プルーニング (REP)

この剪定方法では、ツリー内の各ノードが剪定の候補として考慮されますが、剪定するかどうかを決定する条件がいくつかあり、通常は次の手順に従います。

1. すべてのサブツリーを削除し、リーフノードにします。

2. ノードに最も関連性の高いカテゴリを割り当てる

3. 検証データを使用してその正確性を検証し、処理前と比較する

元のものより悪くない場合は、そのサブツリーは実際に削除されます。次に、ノードを下から上へ繰り返し処理します。このアプローチでは、実際にそれらの「有害な」ノードが削除されます。

ランダムフォレスト

ランダムフォレストの理論は、決定木自体とは関係ありません。決定木は、そのアイデアのアルゴリズムとしてのみ使用できます。

ランダムフォレストを導入する理由は何ですか?同じデータバッチに対しては、決定木を 1 つしか生成できないことがわかっており、この変更は比較的簡単です。複数のアルゴリズムの組み合わせはありますか?

これがアンサンブル学習の概念です。

図からわかるように、個々の学習器 (弱学習器) には、同じアルゴリズムまたは異なるアルゴリズムを含めることができます。これらが同じであれば、同質統合と呼び、そうでない場合は異質統合と呼びます。

ランダムフォレストは、バギング戦略に基づくアンサンブル学習の特殊なケースです。

上の図からわかるように、バギングの個々の学習者のトレーニングセットはランダムサンプリングによって取得されます。 n 回のランダムサンプリングにより、n 個のサンプルセットを取得できます。これらの n 個のサンプルセットに対して、n 個の個別学習者を個別にトレーニングし、アンサンブル戦略を使用してこれらの n 個の個別学習者の最終出力を取得できます。これらの n 個の個別学習者は互いに独立しており、並列で実行できます。

注: アンサンブル学習にはブースティングと呼ばれる別の方法があります。この方法では、学習者間に強い相関関係があります。興味があれば、それについて学ぶことができます。

ランダムフォレストで使用されるサンプリング方法は、一般的にブートストラップサンプリングです。元のサンプルセットに対して、最初にランダムにサンプルを収集してサンプリングセットに入れ、その後、元に戻します。つまり、次のサンプリングでもサンプルが収集される可能性があります。一定数のサンプリングの後、サンプルセットが得られます。ランダムサンプリングであるため、各サンプリングセットは元のサンプルセットや他のサンプリングセットとは異なり、取得される個々の学習者も異なります。

ランダムフォレストの主な問題は、結果が n 個ある場合の組み合わせ戦略をどのように設定するかです。主な方法はいくつかあります。

加重平均法:

平均化法は回帰分析でよく使用されます。このアプローチでは、まず各学習者に事前に設定された重み wi を与えます。

最終的な出力は次のようになります。

学習器の重みがすべて 1/n の場合、この平均化方法は単純平均化方法と呼ばれます。

投票法:

各学習者の重みが同じであれば、投票方法は私たちの生活における投票と似ています。

次に絶対投票方式があり、これは過半数の投票を意味します。相対投票では、少数派が多数派に従います。

重み付けがある場合、少数派は依然として多数派に従いますが、ここでの数字は重み付けされています。

例

簡単な二次関数コードを使用して決定木を使用する方法を見てみましょう。

トレーニングデータは 100 個のランダムな実数平方データです。深度が異なると曲線も異なります。

テストデータもランダムデータですが、異なる深さのツリーのモデルによって生成される予測値も異なります。図のように

この画像のコードは次のとおりです。

私の環境は Python 3.6 で、numpy、matplotlib、sklearn の 3 つのライブラリをインストールする必要があります。必要な場合は、pip でインストールするだけです。試してみてください。シンプルですが、非常に興味深いです。

 #!/usr/bin/python
 # -*- コーディング:utf-8 -*- 
 
 numpyをnpとしてインポートする
matplotlib をmplとしてインポートする
matplotlib.pyplot をpltとしてインポートします。
 sklearn.treeからDecisionTreeRegressor をインポートします
 
 
 __name__ == "__main__"の場合: 
 
    # トレーニングデータを準備する
    100 位
    x = np.random.rand(N) * 6 - 3
    x.ソート()
    y = x*x
    x = x.reshape(-1, 1) 
 
    mpl.rcParams[ 'font.sans-serif' ] = [ 'SimHei' ]
    mpl.rcParams[ 'axes.unicode_minus' ] = False   
 
    # 決定木の深さとその曲線の色
    深さ = [2, 4, 6, 8, 10]
    clr = 'rgbmy'   
 
    # 実際の値
    plt.figure(フェイスカラー= 'w' )
    plt.plot(x, y, 'ro' , ms=5, mec= 'k' , label= '実際の値' ) 
 
    # テストデータを準備する
    x_test = np.linspace(-3, 3, 50).reshape(-1, 1) 
 
    # 決定木を構築する
    dtr = デシジョンツリー回帰関数()
    # さまざまな深さで決定木モデルをループし、それらを使用してデータの出力をテストします
zip(depth, clr)内のd、c の場合:
        # 最大深度を設定する（事前剪定）
        dtr.set_params(最大深度=d)
        # 決定木を訓練する
        dtr.fit(x, y)
        # トレーニングデータから取得したモデルを使用してテストデータを検証する
        y_hat = dtr.predict(x_test)
        # モデルによって得られた曲線を描く
        plt.plot(x_test, y_hat, '-' , color=c, linewidth=2, markeredgecolor= 'k' , label= '深さ=%d' % d)
    # 基本的な描画パラメータ
    plt.legend(loc= '上部中央' 、フォントサイズ=12)
    plt.xlabel( 'X' )
    plt.yラベル( 'Y' )
    plt.grid(b= True 、 ls= ':' 、 color= '#606060' )
    plt.title( '二次関数決定木' 、フォントサイズ=15)
    plt.タイトレイアウト(2)
    plt.show()