機械学習アルゴリズム（1）：決定木とランダムフォレスト

モデルの組み合わせ (ブースティング、バギングなど) と決定木に関連するアルゴリズムは多数あります。これらのアルゴリズムの最終結果は、N (場合によっては数百) のツリーを生成することです。これにより、単一の決定木によって発生する問題を大幅に削減できます。これは、「3 人の靴屋は 1 人の諸葛亮に等しい」ということわざに少し似ています。これらの数百の決定木はそれぞれ非常に単純ですが (C4.5 のような単一の決定木と比較すると)、それらを組み合わせると非常に強力になります。

近年の論文では、ICC などの重量級カンファレンスでも、ICC 2009 では Boosting や Random Forest に関する記事が多く掲載されています。モデルの組み合わせ + 決定木に関連するアルゴリズムには、ランダム フォレストと GBDT (勾配ブースト決定木) という 2 つの基本的な形式があります。モデルの組み合わせ + 決定木の他の新しいアルゴリズムは、これら 2 つのアルゴリズムの拡張です。この記事では主に GBDT に焦点を当て、ランダム フォレストは比較的単純なので簡単に説明します。

この記事を読む前に、まず機械学習と数学(3)とそこに引用されている論文を読むことをお勧めします。この記事のGBDTは主にこれに基づいていますが、ランダムフォレストは比較的独立しています。

基本コンテンツ:

ここでは主に他の人の記事を参考にしながら、簡単に基礎的な部分についてお話します。ランダムフォレストとGBDTでは、重要なポイントが2つあり、1つ目は情報ゲイン、2つ目は決定木です。特に、Andrew Moore の Decision Trees Tutorial と Information Gain Tutorial をお勧めします。ムーアのデータマイニングチュートリアルシリーズは素晴らしいです。上記の 2 つの内容を理解した後にのみ、記事を読み進めることができます。

決定木は、実際には超平面で空間を分割する方法です。パーティションが作成されるたびに、現在の空間が 2 つに分割されます。たとえば、次の決定木は次のようになります。

スペースは次のように分割されます。

これにより、各リーフノードは空間内で重複しない領域になります。決定を行う際には、入力サンプルの各次元の値に応じて段階的に進み、最終的にサンプルが N 個の領域のいずれかに分類されます (N 個のリーフノードがあると仮定)。

ランダムフォレスト:

ランダム フォレストは最近人気のアルゴリズムで、多くの利点があります。

• データセット上で良好なパフォーマンスを発揮

• 現在の多くのデータセットでは、他のアルゴリズムに比べて大きな利点がある。

• 特徴選択なしで非常に高次元（多くの特徴）のデータを処理できます。

• トレーニング後、どの機能がより重要であるかを判断できるようになります。

• ランダム フォレストを作成するときは、一般化エラーの不偏推定値が使用されます。

• トレーニング速度が速い

• トレーニングプロセス中に、特徴間の相互影響を検出できる。

• 並列化が容易

• 実装が比較的簡単

名前が示すように、ランダム フォレストはランダムな方法でフォレストを構築します。フォレストは多数の決定木で構成され、ランダム フォレスト内の各決定木の間には相関関係はありません。フォレストを取得した後、新しい入力サンプルが入力されると、フォレスト内の各決定木は、サンプルがどのカテゴリに属する​​べきかを判断し（分類アルゴリズムの場合）、どのカテゴリが最も多く選択されているかを確認し、サンプルがそのカテゴリに属する​​ことを予測します。

各決定木を構築するプロセスでは、サンプリングと完全分割という 2 つの点に注意する必要があります。 1 つ目は、2 つのランダム サンプリングのプロセスです。ランダム フォレストは、入力データの行と列をサンプリングします。行サンプリングでは置換方式が採用されており、サンプリングによって得られたサンプル セットに重複サンプルが存在する場合があります。入力サンプルの数が N であると仮定すると、サンプリングされるサンプルの数も N になります。つまり、トレーニング中、各ツリーの入力サンプルはすべてのサンプルではないため、過剰適合が発生する可能性が低くなります。次に、列サンプリングが実行され、M 個の特徴から m 個の特徴が選択されます (m << M)。次に、完全な分割方法を使用して、サンプリングされたデータに基づいて決定木が構築されます。これにより、決定木のリーフ ノードはそれ以上分割できなくなるか、その中のすべてのサンプルが同じカテゴリを指すようになります。一般的に、多くの決定木アルゴリズムには重要なステップである剪定がありますが、ここではそうではありません。前の 2 つのランダム サンプリング プロセスによってランダム性が保証されるため、剪定を行わなくても過剰適合は発生しません。

このアルゴリズムによって得られたランダムフォレスト内の各ツリーは非常に弱いですが、組み合わせると非常に強力になります。ランダム フォレスト アルゴリズムは次のように比較できると思います。各決定木は狭い分野の専門家です (各決定木が学習する M 個の特徴から m 個を選択するため)。このように、ランダム フォレストにはさまざまな分野の専門家が多数存在します。新しい問題 (新しい入力データ) については、さまざまな角度から検討することができ、最終的に専門家が投票して結果を得ます。

ランダムフォレストプロセスについては、Mahout のランダムフォレストを参照してください。このページは非常に明確です。理解できないのは、Information Gain です。以前私が推奨した Moore のページを確認してください。

勾配ブースト決定木:

GBDT は、分類と回帰に使用できる広く使用されているアルゴリズムです。多くのデータで良い結果が得られます。 GBDTアルゴリズムには、MART（多重加法回帰ツリー）、GBRT（勾配ブースト回帰ツリー）、ツリーネットなど、いくつかの別名があります。実際、これらはすべて同じものです（wikipedia – 勾配ブースティングから参照）。発明者はフリードマンです。

Gradient Boostは、実際にはさまざまなアルゴリズムを実装するために使用できるフレームワークです。機械学習と数学(3)の説明を参照してください。ブーストは「改善」を意味します。一般的に、ブースティング アルゴリズムは反復的なプロセスであり、新しいトレーニングごとに前回の結果が改善されます。

オリジナルの Boost アルゴリズムでは、アルゴリズムの開始時に各サンプルに重み値を割り当てます。最初は、すべてのサンプルは同等に重要です。トレーニングの各ステップで得られたモデルは、データ ポイントの推定を正しいか正しくないかを決定します。各ステップの後に、誤って分類されたポイントの重みを増やし、正しく分類されたポイントの重みを減らします。このように、一部のポイントが常に誤って分類されている場合、それらのポイントには「深刻な懸念」があり、非常に高い重みが割り当てられます。その後、N 回の反復 (ユーザーが指定) を実行すると、N 個の単純な分類器 (基本学習器) が得られ、それらを組み合わせて (たとえば、重み付けしたり、投票させたりすることができます)、最終モデルが得られます。

勾配ブーストと従来のブーストの違いは、各計算が前の計算の残差を削減することです。残差を排除するために、残差削減の勾配方向に新しいモデルを構築できます。したがって、Gradient Boost では、新しい各モデルの目的は、勾配の方向で以前のモデルの残差を減らすことであり、これは正しいサンプルと誤ったサンプルに重み付けする従来の Boost 方式とは大きく異なります。

分類問題には、多クラスロジスティックという非常に重要なトピックがあります。これは、多分類ロジスティック問題です。カテゴリ数> 2の問題に適用でき、分類結果では、サンプルxが必ずしも1つのクラスだけに属するとは限りません。サンプルxが複数のクラスに属する確率を得ることができます（サンプルxの推定yが特定の幾何分布に従うとも言えます）。これは、実は一般化線型モデルで議論されている内容です。ここでは説明しません。今後機会があれば、特別な章を使って説明します。結論は次のとおりです。分類問題が幾何分布に準拠している場合、後続の操作にロジスティック変換を使用できます。

サンプルxはK個のカテゴリに属し、その推定値はF1(x)…FK(x)であると仮定します。ロジスティック変換は次のとおりです。ロジスティック変換は、データを正規化する（ベクトルの長さを1にする）滑らかなプロセスです。結果は、カテゴリkに属する確率pk(x)です。

ロジスティック変換後の結果では、損失関数は次のようになります。

このうち、yk は入力サンプルデータの推定値です。サンプル x がカテゴリ k に属する場合、yk = 1 となり、それ以外の場合は yk = 0 となります。

ロジスティック変換の式を損失関数に代入し、その導関数を取ることで、損失関数の勾配を得ることができます。

上記は比較的抽象的なので、例を見てみましょう。

入力データ x が 5 つのカテゴリ (それぞれ 1、2、3、4、5) に属すると仮定します。トレーニング データでは、x はカテゴリ 3 に属しているため、y = (0、0、1、0、0) となります。モデルが F(x) = (0、0.3、0.6、0、0) と推定すると仮定します。ロジスティック変換後のデータは p(x) = (0.16、0.21、0.29、0.16、0.16) です。y - p によって得られる勾配 g は、(-0.16、-0.21、0.71、-0.16、-0.16) です。この観察から興味深い結論を導き出すことができます。

gk が特定の次元（特定の分類）におけるサンプルの勾配であると仮定します。

gk>0 の場合、それが大きいほど、この次元での確率 p(x) は改善されるはずです。たとえば、上記の 3 番目の次元の確率は 0.29 であり、これは改善されるはずであり、「正しい方向」に移動するはずです。

値が小さいほど、推定値は正確になります。

gk<0 の場合、値が小さく負の値が大きいほど、この次元の確率は減少します。たとえば、2 番目の次元 0.21 は減少します。それは「間違った反対方向」に向かっているはずだ

大きいほど、マイナスの度合いが小さくなり、推定値が「間違っている」可能性が低くなることを示しています。

一般に、サンプルの場合、最も理想的な勾配は 0 に近いものになります。したがって、関数の推定値が勾配を反対方向に移動できるようにする必要があります（次元 > 0 では負の方向に移動し、次元 < 0 では正の方向に移動し、最終的に勾配を 0 にできるだけ近づけます）。アルゴリズムは、Boost の意味に似た、勾配の大きいサンプルに細心の注意を払います。

勾配を取得したら、次のステップは勾配を減らすことです。ここで使用される方法は、反復 + 決定木法です。初期化時に、推定関数 F(x) がランダムに与えられ (F(x) はランダムな値、または F(x)=0 になります)、その後、各反復で現在の各サンプルの勾配に基づいて決定木が確立されます。関数を勾配の反対方向に移動させ、N 回の反復後に勾配が小さくなるようにする。

ここで構築される決定木は、通常の決定木とは異なります。まず、この決定木には固定数のリーフノード J があります。J 個のノードが生成された後、新しいノードは生成されません。

アルゴリズムの流れは次のとおりです。(treeBoost 論文より引用)

0. 初期値が与えられていることを示す

1. M個の決定木（M回の反復）の確立を示します。

2. 関数推定値F(x)のロジスティック変換を示す。

3. K 個のカテゴリに対する次の操作を示します (実際、この for ループはベクトル操作としても理解できます。各サンプル ポイント xi は K 個の可能なカテゴリ yi に対応するため、yi、F(xi)、p(xi) はすべて K 次元ベクトルであり、理解しやすいかもしれません)

4. 残差を減らすための勾配方向を示す

5.各サンプル点xに応じて、その残差減少の勾配方向が得られ、J個の葉ノードからなる決定木が得られることを示す。

6. 決定木が構築された後、この式を使用して各リーフノードのゲインを取得できます（このゲインは予測に使用されます）

各ゲインの構成は実際には K 次元ベクトルであり、決定木予測プロセス中にサンプル ポイントがこのリーフ ノードに該当する場合、対応する K 分類値は何であるかを意味します。たとえば、GBDT は 3 つの決定木を取得します。予測時に、サンプル ポイントも 3 つのリーフ ノードに分類され、そのゲインは次のようになります (3 つの分類問題を想定)。

(0.5、0.8、0.1)、(0.2、0.6、0.3)、(0.4、0.3、0.3)の場合、分類2を選択する決定木が最も多いため、最終的な分類は2番目になります。

7. これは、現在の決定木を以前の決定木と統合して新しいモデルを作成することを意味します（6の例と同様）。

GBDTアルゴリズムはこれで終わりです。前回の記事で不明瞭だった部分を補えるといいのですが:)

成し遂げる：

アルゴリズムを理解したら、それを実装するか、他の人のコードを見る必要があります。ここでは、Wikipedia の勾配ブースティングのページをお勧めします。次に、次のようなオープンソース ソフトウェアの実装をいくつか示します。http://elf-project.sourceforge.net/

オリジナルリンク: http://www.cnblogs.com/LeftNotEasy/archive/2011/03/07/random-forest-and-gbdt.html