Усредненные оценки с одной зависимостью - Averaged one-dependence estimators

Усредненные оценки с одной зависимостью (AODE) является вероятностным классификационное обучение техника. Он был разработан для решения проблемы независимости атрибутов популярных наивный байесовский классификатор. Он часто разрабатывает значительно более точные классификаторы, чем наивный байесовский классификатор, за счет небольшого увеличения объема вычислений.^[1]

Классификатор AODE

AODE стремится оценить вероятность каждого класса у учитывая указанный набор функций Икс₁, ... Икс_п, П(у | Икс₁, ... Икс_п). Для этого используется формула

{ displaystyle { 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})}}}

куда ${ Displaystyle { шляпа {P}} ( cdot)}$ обозначает оценку ${ Displaystyle Р ( cdot)}$ , ${ Displaystyle F ( cdot)}$ - частота, с которой аргумент появляется в выборке данных и м - указанная пользователем минимальная частота, с которой должен появляться термин, чтобы его можно было использовать во внешнем суммировании. В недавней практике м обычно устанавливается на 1.

Вывод классификатора AODE

Мы стремимся оценить P (у | Икс₁, ... Икс_п). По определению условной вероятности

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

Для любого ${ Displaystyle 1 Leq я Leq п}$ ,

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

При предположении, что Икс₁, ... Икс_п независимы, учитывая у и Икс_я, следует, что

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

Эта формула определяет специальную форму Одной оценки зависимости (ODE), вариант наивный байесовский классификатор что делает вышеупомянутое предположение о независимости более слабым (и, следовательно, потенциально менее опасным), чем наивное предположение о независимости Байеса. Следовательно, каждое ОДУ должно создавать менее предвзятую оценку, чем наивный байесовский метод. Однако, поскольку каждая базовая оценка вероятности обусловлена двумя переменными, а не одной, они формируются из меньшего количества данных (обучающие примеры, удовлетворяющие обеим переменным) и, следовательно, вероятно, будут иметь большую дисперсию. AODE уменьшает эту дисперсию путем усреднения оценок всех таких ODE.

Особенности классификатора AODE

Как и наивный байесовский метод, AODE не выполняет выбор модели и не использует настраиваемые параметры. В результате он имеет низкую дисперсию. Он поддерживает постепенное обучение посредством чего классификатор может эффективно обновляться информацией из новых примеров по мере их появления. Он предсказывает вероятности классов, а не просто предсказывает один класс, позволяя пользователю определять уверенность, с которой может быть произведена каждая классификация. Его вероятностная модель может напрямую обрабатывать ситуации, когда некоторые данные отсутствуют.

AODE имеет вычислительную сложность ${ displaystyle O (ln ^ {2})}$ во время тренировки и ${ displaystyle O (kn ^ {2})}$ во время классификации, где п это количество функций, л количество обучающих примеров и k количество классов. Это делает его неприменимым к многомерным данным. Однако в рамках этого ограничения он является линейным по отношению к количеству обучающих примеров и, следовательно, может эффективно обрабатывать большое количество обучающих примеров.