AODE

AODE（Averaged One-Dependence Estimators）は確率的分類器の一つである。AODEは、代表的な確率的分類器である単純ベイズ分類器の単純な条件付き独立の仮定を緩和する分類器として考案された。多くの場合、単純ベイズ分類器に対して顕著に高い精度を示すが、計算コストもそれほど大きくはならないことが示された。

AODE 分類器

AODEは、特徴変数の実現値 x₁, ... x_n を条件とした各クラス y の確率、P(y | x₁, ... x_n) を求める。これを計算するため、AODEは以下の式を用いる。

${\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})}}$

ここで、${\hat {P}}(\cdot )$ は確率 $P(\cdot )$ の推定値を表し、 $F(\cdot )$ は引数の変数値が訓練データに現れる頻度を表し、 m は加算される各項が満たす条件として、各項を代表する変数が訓練データに現れるべき最小頻度を表す。 通常、m としては 1 が指定される。

AODE 分類器の導出

確率 P(y | x₁, ... x_n) を求める。条件付き確率の定義より、次の式が成り立つ。

$P(y\mid x_{1},\ldots x_{n})={\frac {P(y,x_{1},\ldots x_{n})}{P(x_{1},\ldots x_{n})}}.$

ベイズの定理より、任意の $1\leq i\leq n$ について、次の式が成り立つ。

$P(y,x_{1},\ldots x_{n})=P(y,x_{i})P(x_{1},\ldots x_{n}\mid y,x_{i}).$

x₁, ... x_n が y と x_i を条件として独立であることを仮定すると、次の式を得る。

$P(y,x_{1},\ldots x_{n})=P(y,x_{i})\prod _{j=1}^{n}P(x_{j}\mid y,x_{i}).$

この式は、単純ベイズ分類器の条件付き独立の仮定を緩和した、1 つの One Dependence Estimator (ODE) の定義を与えている（ODE は、条件とするx_iの個数、すなわち、変数の個数分、存在する）。したがって、それぞれの ODE は、単純ベイズ分類器に比べて、バイアスの小さな推定器となるはずである。しかしながら、分類器を構成する各確率の条件となる変数の個数が、単純ベイズ分類器では 1 つであるのに対して、ODE では 2 つとなるため、推定に利用できる訓練事例数が少なくなりがちである（訓練事例は 2 つの条件を満たさなければならない）。そのため、ODE はバリアンスが大きくなる傾向がある。そこで、AODE は、このような全ての ODE による推定結果を平均することによって、バリアンスを削減している。

AODE 分類器の特徴

単純ベイズ分類器と同様に、AODE はモデル選択を行わないため、バリアンスが小さい。また、新しい事例が追加された場合に、その情報を反映して分類器を更新することも可能である。

AODE の学習時間の時間計算量は $O(ln^{2})$ であり、分類時間の時間計算量は $O(kn^{2})$ である。ここで、n は特徴変数の個数であり、l は訓練事例数であり、k はクラスの個数である。高次元のデータへ適用した場合には実行不可能になるという制限はあるものの、訓練事例数に対して線形のオーダーであり、大量の訓練事例を効率的に処理することが可能である。

実装

データマイニングツール Weka には AODE の実装が含まれている。