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:ベイズ統計]]