AODEのソースを表示
←
AODE
ナビゲーションに移動
検索に移動
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
この操作は、次のグループに属する利用者のみが実行できます:
登録利用者
。
このページのソースの閲覧やコピーができます。
'''AODE'''('''''A'''veraged '''O'''ne-'''D'''ependence '''E'''stimators'')は[[統計分類|確率的分類器]]の一つである。AODEは、代表的な確率的分類器である[[単純ベイズ分類器]]の単純な[[条件付き独立]]の仮定を緩和する分類器として考案された。多くの場合、単純ベイズ分類器に対して顕著に高い精度を示すが、計算コストもそれほど大きくはならないことが示された<ref>Webb, G. I., J. Boughton, and Z. Wang (2005). [http://www.springerlink.com/content/u8w306673m1p866k/ Not So Naive Bayes: Aggregating One-Dependence Estimators]. Machine Learning 58(1). Netherlands: Springer, pages 5-24. </ref>。 == AODE 分類器 == AODEは、特徴変数の実現値 ''x''<sub>1</sub>, ... ''x''<sub>n</sub> を条件とした各クラス ''y'' の確率、P(''y'' | ''x''<sub>1</sub>, ... ''x''<sub>n</sub>) を求める。これを計算するため、AODEは以下の式を用いる。 : <math>\hat{P}(y\mid x_1, \ldots x_n)=\frac{\sum_{i:1\leq i\leq n \wedge F(x_i)\geq m} \hat{P}(y,x_i)\prod_{j=1}^n\hat{P}(x_j\mid y,x_i)}{\sum_{y^\prime\in Y}\sum_{i:1\leq i\leq n \wedge F(x_i)\geq m} \hat{P}(y^\prime,x_i)\prod_{j=1}^n\hat{P}(x_j\mid y^\prime,x_i)}</math> ここで、<math>\hat{P}(\cdot)</math> は確率 <math>P(\cdot)</math> の推定値を表し、 <math>F(\cdot)</math> は引数の変数値が訓練データに現れる頻度を表し、 ''m'' は加算される各項が満たす条件として、各項を代表する変数が訓練データに現れるべき最小頻度を表す。 通常、''m'' としては 1 が指定される。 == AODE 分類器の導出 == 確率 P(''y'' | ''x''<sub>1</sub>, ... ''x''<sub>n</sub>) を求める。[[条件付き確率]]の定義より、次の式が成り立つ。 : <math>P(y\mid x_1, \ldots x_n)=\frac{P(y, x_1, \ldots x_n)}{P(x_1, \ldots x_n)}.</math> [[ベイズの定理]]より、任意の <math>1\leq i\leq n</math> について、次の式が成り立つ。 : <math>P(y, x_1, \ldots x_n)=P(y, x_i)P(x_1, \ldots x_n\mid y, x_i).</math> ''x''<sub>1</sub>, ... ''x''<sub>n</sub> が ''y'' と ''x<sub>i</sub>'' を条件として独立であることを仮定すると、次の式を得る。 : <math>P(y, x_1, \ldots x_n)=P(y, x_i)\prod_{j=1}^n P(x_j\mid y, x_i).</math> この式は、単純ベイズ分類器の条件付き独立の仮定を緩和した、1 つの One Dependence Estimator (ODE) の定義を与えている(ODE は、条件とする''x<sub>i</sub>''の個数、すなわち、変数の個数分、存在する)。したがって、それぞれの ODE は、単純ベイズ分類器に比べて、バイアスの小さな推定器となるはずである。しかしながら、分類器を構成する各確率の条件となる変数の個数が、単純ベイズ分類器では 1 つであるのに対して、ODE では 2 つとなるため、推定に利用できる訓練事例数が少なくなりがちである(訓練事例は 2 つの条件を満たさなければならない)。そのため、ODE はバリアンスが大きくなる傾向がある。そこで、AODE は、このような全ての ODE による推定結果を平均することによって、バリアンスを削減している。 == AODE 分類器の特徴 == 単純ベイズ分類器と同様に、AODE はモデル選択を行わないため、バリアンスが小さい。また、新しい事例が追加された場合に、その情報を反映して分類器を更新することも可能である。 AODE の学習時間の時間計算量は <math>O(ln^2)</math> であり、分類時間の時間計算量は <math>O(kn^2)</math> である。ここで、''n'' は特徴変数の個数であり、''l'' は訓練事例数であり、''k'' はクラスの個数である。高次元のデータへ適用した場合には実行不可能になるという制限はあるものの、訓練事例数に対して線形のオーダーであり、大量の訓練事例を効率的に処理することが可能である。 == 実装 == データマイニングツール [[Weka]] には AODE の実装が含まれている。 == 脚注 == <references/> {{DEFAULTSORT:えいおうていいい}} [[Category:分類アルゴリズム]] [[Category:ベイズ統計]]
AODE
に戻る。
ナビゲーション メニュー
個人用ツール
ログイン
名前空間
ページ
議論
日本語
表示
閲覧
ソースを閲覧
履歴表示
その他
検索
案内
メインページ
最近の更新
おまかせ表示
MediaWiki についてのヘルプ
特別ページ
ツール
リンク元
関連ページの更新状況
ページ情報