2

ここで基本的な疑似コードの概要を探しています。

私の目標は、分類木をゼロからコーディングすることです (私は機械学習を学んでいて、直感を得たいと思っています)。しかし、私のトレーニング データは膨大です。40000 の例と 1000 の機能です。必要な分割数の上限が 2 40000であることを考えると、これらすべての分割されたデータセットを追跡する方法がわかりません。

完全なデータセットから始めて、1 つの分割を取得するとします。次に、分割の片側に落ちた 20000 ほどの例をデータセットに保存し、分割アルゴリズムを再実行して、そのデータセットの貪欲な分割を見つけます。次に、これを続けて、木の一番左の枝に沿って何十回も分割するとします。

左端のすべての分割に満足したら、次に何をしますか? 最大 2 40000 個の個別のサブセットを保存するにはどうすればよいですか? また、テスト例を分類するときに、取得したすべての分割を追跡するにはどうすればよいですか? 私にとって意味をなさないのはコードの構成です。

4

2 に答える 2

2

詳細な回答をありがとう@natan。

ただし、私の理解が正しければ、あなたが懸念している主な問題は、各トレーニング サンプルがデシジョン ツリーを伝搬する際に効率的に追跡する方法です。

これはかなり簡単に行うことができます。

必要なのは、N=40000トレーニング サンプルごとのエントリを持つサイズのベクトルだけです。このベクトルは、各サンプルがツリー内のどこにあるかを示します。このベクトルを としましょうassoc。

このベクトルをどのように使用しますか?

私の意見では、最も洗練された方法はassoc、型uint32を作成し、ビットを使用して、ツリーを介した各トレーニング サンプルの伝播をエンコードすることです。

の各ビットassoc(k)は、ツリーの特定の深さを表します。このビットが設定されている場合 (1)、サンプルkが右に移動したことを意味し、それ以外の場合は、サンプルkが左に移動したことを意味します。

この戦略に従うことにした場合、次の Matlab コマンドが便利であることがわかります。bitget、bitset、bitshiftおよびその他のビット単位の関数。

次の木を考えてみましょう

       root
      /    \
     a      b
           / \
          c   d

したがって、ノードaに移動したすべての例のassoc値は00b- ルートで左に移動したためです (最下位ビット (LSB) のゼロに対応)。

リーフ ノードcに移動したすべての例。assoc値は01b- ルートで右に移動し (LSB=1)、次に左に曲がった (2 番目のビット = 0) です。

最後に、葉ノードdに移動したすべての例、それらのassoc値は11b- 分岐が正しすぎました。

さて、ノードbを通過したすべての例をどのように見つけることができますか?

それは簡単です！

>> selNodeB = bitand( assoc, 1 );

LSB が1ルートで右折され、ノードbを通過するすべてのノード。

于 2013-01-10T08:05:23.857 に答える
1

2^40000 ビットを格納する方法があると考えている場合、この数値がどれほど大きいかを理解していないことになり、約 10000 桁で間違っています。classregtreeの Matlab のドキュメントを確認してください。

@Amroの詳細な回答からコピーしました（ここにあります）：

" 分類ツリー モデルの一般的なパラメータを次に示します。

  • x : データ行列、行はインスタンス、列は予測属性
  • y : 列ベクトル、各インスタンスのクラス ラベル
  • categorical : どの属性が離散型であるかを指定します (連続ではなく)
  • method : 分類木または回帰木を生成するかどうか (クラス タイプに依存)
  • names : 属性に名前を付けます
  • prune : エラー削減プルーニングを有効/無効にします
  • minparent/minleaf : ノードをさらに分割する場合、ノード内のインスタンスの最小数を指定できます
  • nvartosample : ランダム ツリーで使用されます (各ノードで K 個のランダムに選択された属性を考慮します)
  • weights : 重み付けされたインスタンスを指定します
  • cost : コスト マトリックスを指定します (さまざまなエラーのペナルティ)
  • splitcriterion : 各分割で最適な属性を選択するために使用される基準。私が知っているのは、情報獲得基準のバリエーションであるジニ指数だけです。
  • Priorprob : トレーニング データから計算するのではなく、事前のクラス確率を明示的に指定します。

プロセスを説明する完全な例:

%# load data
load carsmall

%# construct predicting attributes and target class
vars = {'MPG' 'Cylinders' 'Horsepower' 'Model_Year'};
x = [MPG Cylinders Horsepower Model_Year];
y = strcat(Origin,{});

%# train classification decision tree
t = classregtree(x, y, 'method','classification', 'names',vars, ...
                'categorical', [2 4], 'prune','off');
view(t)

%# test
yPredicted = eval(t, x);
cm = confusionmat(y,yPredicted);           %# confusion matrix
N = sum(cm(:));
err = ( N-sum(diag(cm)) ) / N;             %# testing error

%# prune tree to avoid overfitting
tt = prune(t, 'level',2);
view(tt)

%# predict a new unseen instance
inst = [33 4 78 NaN];
prediction = eval(tt, inst)

木

于 2013-01-10T07:38:20.067 に答える