44

私はデータマイニング、より正確には決定木に関する研究を行っています。

決定木を構築するための複数のアルゴリズムがあるかどうか (または 1 つだけですか?)、次のような基準に基づいてどれが優れているかを知りたいです。

  • パフォーマンス
  • 複雑
  • 意思決定の誤り
  • もっと。
4

1 に答える 1

93

ディシジョン ツリーの実装は、主に次の軸に沿って異なります。

  • 分割基準(つまり、「分散」の計算方法)

  • 回帰(連続変数、スコアなど) および分類(離散変数、クラス ラベルなど) のモデルを構築するかどうか

  • オーバーフィッティングを排除/削減する手法

  • 不完全なデータを処理できるかどうか


主なディシジョン ツリーの実装は次のとおりです。

  • ID3または Iterative Dichotomizer は、Ross Quinlan によって開発された 3 つの決定木の実装の最初のものでした (Quinlan, JR 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81-106.)。

  • CARTまたはClassification And Regression Treesは、Decision Tree という用語の一般的な頭字語としてよく使用されますが、明らかにより具体的な意味を持っています。つまり、CART の実装は C4.5 と非常によく似ています。注目すべき違いの 1 つは、CART がデータに再帰的に適用される数値分割基準に基づいてツリーを構築するのに対し、C4.5 にはルール セットs を構築する中間ステップが含まれていることです。

  • C4.5、クインランの次のイテレーション。新しい機能 (対 ID3) は次のとおりです。(i) 連続機能と離散機能の両方を受け入れます。(ii) 不完全なデータ ポイントを処理します。(iii) 通常「プルーニング」として知られる (非常に巧妙な) ボトムアップ手法によって、オーバーフィッティングの問題を解決します。(iv) トレーニング データを構成する特徴に異なる重みを適用できます。これらのうち、最初の3 つは非常に重要です。選択する DT 実装には、3 つすべてが含まれていることをお勧めします。4 番目 (微分重み付け) はそれほど重要ではありません

  • C5.0、最新の Quinlan イテレーション。この実装は特許で保護されており、その結果、(商用ソフトウェア パッケージ以外で) 実装されることはおそらくほとんどありません。私は C5.0 の実装を自分でコーディングしたことがない (ソース コードを見たことさえない) ため、C5.0 と C4.5 の十分な情報に基づいた比較を提供することはできません。その発明者 (Ross Quinlan) が主張する改良点について、私は常に懐疑的でした。たとえば、彼は、C4.5 よりも「数桁」高速であると主張しています。他の主張も同様に広範です (「メモリ効率が大幅に向上」) などです。 2 つの手法の比較結果を報告している研究を紹介するだけで、自分で決めることができます。

  • CHAID (カイ 2 乗自動相互作用検出器) は、実際には、元の ID3 の実装よりも約 6 年先行しています (1980 年に Gordon Kass によって博士論文が発表されました)。私はこの手法について少しずつ知っています。R プラットフォームには、優れたドキュメントを含むCHAIDと呼ばれるパッケージがあります。

  • MARS (多適応回帰スプライン) は、実際には、MARS の最初の発明者である Salford Systems によって商標登録された用語です。その結果、Salford が販売していないライブラリの MARS クローンは、MARS 以外の名前が付けられています。たとえば、R では、関連する機能は poly-spline ライブラリの polymars です。Matlab と Statistica には、MARS 機能を備えた実装もあります。

CART または C4.5 をお勧めします (ただし、C5.0 や CHAID の機能セットについてはよく知っていますが、C5.0 や CHAID を直接使用した経験はありません)。

C4.5 はOrangeで実装されたディシジョン ツリー フレーバーです。CART はsklearnのフレーバーです。どちらも優れた ML ライブラリの優れた実装です。

C4.5 は、範囲(トレーニング データの連続変数を処理できるため、C4.5 ははるかに広いユース ケース スペクトルを持つ) とモデルの品質の両方の点で、ID3 を超える大きな一歩です。

おそらく、C5.0 と C4.5 の最も重要な改善点は、ブースト ツリーのサポートです。Orange の DT 実装には、DT (ブーステッド ツリーとランダム フォレスト) のアンサンブル サポートが含まれています。ここでは、アンサンブルのサポートが C4.5 アルゴリズムに追加されました。sklearn は、さまざまなランダム フォレストとブースティング メソッドも備えています。

于 2012-04-03T15:42:10.133 に答える