Наивный классификатор Байеса

Алгоритм вероятностной классификации

Пример наивного байесовского классификатора, изображенного в виде байесовской сети

В статистике наивные классификаторы Байеса представляют собой семейство линейных « вероятностных классификаторов », которые предполагают , что признаки условно независимы, учитывая целевой класс. Сила (наивность) этого предположения и дала классификатору такое название. Эти классификаторы относятся к числу простейших моделей байесовских сетей . ^[1]

Наивные байесовские классификаторы хорошо масштабируются и требуют ряда параметров, линейных по количеству переменных (признаков/предикторов) в задаче обучения. Обучение максимальному правдоподобию может быть выполнено путем оценки выражения в закрытой форме ^{[2] : 718} , которое занимает линейное время , а не с помощью дорогостоящей итеративной аппроксимации , которая используется для многих других типов классификаторов.

В статистической литературе наивные модели Байеса известны под разными названиями, включая простой Байес и независимость Байеса . ^[3] Все эти названия относятся к использованию теоремы Байеса в решающем правиле классификатора, но наивный Байес не (обязательно) является байесовским методом. ^{[2] [3]}

Введение

Наивный Байес — это простой метод построения классификаторов: моделей, которые присваивают метки классов экземплярам задач, представленным в виде векторов значений признаков , где метки классов извлекаются из некоторого конечного набора. Не существует единого алгоритма обучения таких классификаторов, а есть семейство алгоритмов, основанных на общем принципе: все наивные байесовские классификаторы предполагают, что значение определенного признака не зависит от значения любого другого признака при заданной переменной класса. Например, яблоком можно считать фрукт, если он красный, круглый и диаметром около 10 см. Наивный байесовский классификатор считает, что каждая из этих характеристик независимо вносит вклад в вероятность того, что этот фрукт является яблоком, независимо от любых возможных корреляций между признаками цвета, округлости и диаметра.

Во многих практических приложениях для оценки параметров наивных моделей Байеса используется метод максимального правдоподобия ; другими словами, можно работать с наивной байесовской моделью, не принимая байесовскую вероятность и не используя какие-либо байесовские методы.

Несмотря на свою наивную конструкцию и явно упрощенные предположения, наивные байесовские классификаторы неплохо себя зарекомендовали во многих сложных реальных ситуациях. В 2004 году анализ проблемы байесовской классификации показал, что существуют веские теоретические причины для явно неправдоподобной эффективности наивных байесовских классификаторов. ^[4] Тем не менее, всестороннее сравнение с другими алгоритмами классификации в 2006 году показало, что байесовская классификация уступает другим подходам, таким как усиленные деревья или случайные леса . ^[5]

Преимущество наивного байесовского метода состоит в том, что для оценки параметров, необходимых для классификации, требуется лишь небольшой объем обучающих данных. ^[6]

Вероятностная модель

Абстрактно, наивный Байес представляет собой модель условной вероятности : она назначает вероятности для каждого из K возможных результатов или классов с учетом экземпляра проблемы, подлежащего классификации, представленного вектором, кодирующим некоторые n признаков (независимых переменных). ^[7] ${\displaystyle p(C_{k}\mid x_{1},\ldots ,x_{n})}$ ${\displaystyle C_{k}}$ ${\displaystyle \mathbf {x} =(x_{1},\ldots ,x_{n})}$

Проблема с приведенной выше формулировкой заключается в том, что если количество признаков n велико или признак может принимать большое количество значений, то основывать такую ​​модель на таблицах вероятностей невозможно. Поэтому модель необходимо переформулировать, чтобы сделать ее более управляемой. Используя теорему Байеса , условную вероятность можно разложить как:

${\displaystyle p(C_{k}\mid \mathbf {x} )={\frac {p(C_{k})\ p(\mathbf {x} \mid C_{k})}{p(\mathbf {x} )}}\,}$

На простом английском языке, используя терминологию байесовской вероятности , приведенное выше уравнение можно записать как

${\displaystyle {\text{posterior}}={\frac {{\text{prior}}\times {\text{likelihood}}}{\text{evidence}}}\,}$

На практике представляет интерес только числитель этой дроби, поскольку знаменатель не зависит от значений признаков, а значения признаков заданы, так что знаменатель фактически постоянен. Числитель эквивалентен совместной вероятностной модели . ${\displaystyle C}$ ${\displaystyle x_{i}}$

${\displaystyle p(C_{k},x_{1},\ldots ,x_{n})\,}$

которое можно переписать следующим образом, используя цепное правило для повторного применения определения условной вероятности :

${\displaystyle {\begin{aligned}p(C_{k},x_{1},\ldots ,x_{n})&=p(x_{1},\ldots ,x_{n},C_{k})\\&=p(x_{1}\mid x_{2},\ldots ,x_{n},C_{k})\ p(x_{2},\ldots ,x_{n},C_{k})\\&=p(x_{1}\mid x_{2},\ldots ,x_{n},C_{k})\ p(x_{2}\mid x_{3},\ldots ,x_{n},C_{k})\ p(x_{3},\ldots ,x_{n},C_{k})\\&=\cdots \\&=p(x_{1}\mid x_{2},\ldots ,x_{n},C_{k})\ p(x_{2}\mid x_{3},\ldots ,x_{n},C_{k})\cdots p(x_{n-1}\mid x_{n},C_{k})\ p(x_{n}\mid C_{k})\ p(C_{k})\\\end{aligned}}}$

Теперь в игру вступают «наивные» предположения условной независимости : предположим, что все функции в взаимно независимы , обусловлены категорией . Согласно этому предположению, ${\displaystyle \mathbf {x} }$ ${\displaystyle C_{k}}$

${\displaystyle p(x_{i}\mid x_{i+1},\ldots ,x_{n},C_{k})=p(x_{i}\mid C_{k})\,}$.

Таким образом, совместную модель можно выразить как

${\displaystyle {\begin{aligned}p(C_{k}\mid x_{1},\ldots ,x_{n})\varpropto \ &p(C_{k},x_{1},\ldots ,x_{n})\\&=p(C_{k})\ p(x_{1}\mid C_{k})\ p(x_{2}\mid C_{k})\ p(x_{3}\mid C_{k})\ \cdots \\&=p(C_{k})\prod _{i=1}^{n}p(x_{i}\mid C_{k})\,,\end{aligned}}}$

где обозначает пропорциональность , поскольку знаменатель опущен. ${\displaystyle \varpropto }$ ${\displaystyle p(\mathbf {x} )}$

Это означает, что при вышеуказанных предположениях независимости условное распределение по переменной класса равно: ${\displaystyle C}$

${\displaystyle p(C_{k}\mid x_{1},\ldots ,x_{n})={\frac {1}{Z}}\ p(C_{k})\prod _{i=1}^{n}p(x_{i}\mid C_{k})}$

где свидетельство представляет собой коэффициент масштабирования, зависящий только от , то есть константу, если известны значения переменных признака. ${\displaystyle Z=p(\mathbf {x} )=\sum _{k}p(C_{k})\ p(\mathbf {x} \mid C_{k})}$ ${\displaystyle x_{1},\ldots ,x_{n}}$

Построение классификатора из вероятностной модели

В результате обсуждения до сих пор была выведена модель независимых признаков, то есть наивная вероятностная модель Байеса . Наивный байесовский классификатор сочетает эту модель с решающим правилом . Одно общее правило — выбирать наиболее вероятную гипотезу, чтобы свести к минимуму вероятность ошибочной классификации; это известно как максимальное апостериорное правило принятия решения или MAP . Соответствующий классификатор, байесовский классификатор , представляет собой функцию, которая присваивает метку класса некоторому k следующим образом: ${\displaystyle {\hat {y}}=C_{k}}$

${\displaystyle {\hat {y}}={\underset {k\in \{1,\ldots ,K\}}{\operatorname {argmax} }}\ p(C_{k})\displaystyle \prod _{i=1}^{n}p(x_{i}\mid C_{k}).}$

Функции правдоподобия , матрица неточностей и кривая ROC . Для наивного байесовского классификатора и учитывая, что априорные вероятности одинаковы для всех классов, граница решения (зеленая линия) будет помещена в точку пересечения двух плотностей вероятности из-за . ${\displaystyle p(\mathbf {x} \mid Y)}$ ${\displaystyle p(Y)}$ ${\displaystyle p(Y\mid \mathbf {x} )={\frac {p(Y)\ p(\mathbf {x} \mid Y)}{p(\mathbf {x} )}}\propto p(\mathbf {x} \mid Y)}$

Оценка параметров и модели событий

Приоритет класса можно рассчитать, предполагая равновероятные классы, т. е. или вычисляя оценку вероятности класса из обучающего набора: ${\displaystyle p(C_{k})={\frac {1}{K}}}$

${\displaystyle {\text{prior for a given class}}={\frac {\text{no. of samples in that class}}{\text{total no. of samples}}}\,}$

Чтобы оценить параметры распределения признака, необходимо предположить распределение или создать непараметрические модели для признаков из обучающего набора. ^[8]

Предположения о распределении признаков называются «моделью событий» наивного байесовского классификатора. Для дискретных функций, подобных тем, которые встречаются при классификации документов (включая фильтрацию спама), популярны полиномиальные распределения и распределения Бернулли . Эти предположения приводят к двум различным моделям, которые часто путают. ^{[9] [10]}

Гауссов наивный Байес

При работе с непрерывными данными типичным предположением является то, что непрерывные значения, связанные с каждым классом, распределяются в соответствии с нормальным (или гауссовским) распределением. Например, предположим, что обучающие данные содержат непрерывный атрибут . Данные сначала сегментируются по классам, а затем в каждом классе вычисляются среднее значение и дисперсия . Пусть это среднее значение значений, связанных с классом , и пусть это скорректированная по Бесселю дисперсия значений, связанных с классом . Предположим, кто-то собрал некоторое значение наблюдения . Затем плотность вероятности данного класса , т. е. , может быть вычислена путем подстановки в уравнение для нормального распределения, параметризованного и . Формально, ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \mu _{k}}$ ${\displaystyle x}$ ${\displaystyle C_{k}}$ ${\displaystyle \sigma _{k}^{2}}$ ${\displaystyle x}$ ${\displaystyle C_{k}}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle C_{k}}$ ${\displaystyle p(x=v\mid C_{k})}$ ${\displaystyle v}$ ${\displaystyle \mu _{k}}$ ${\displaystyle \sigma _{k}^{2}}$

${\displaystyle p(x=v\mid C_{k})={\frac {1}{\sqrt {2\pi \sigma _{k}^{2}}}}\,e^{-{\frac {(v-\mu _{k})^{2}}{2\sigma _{k}^{2}}}}}$

Другой распространенный метод обработки непрерывных значений — использование группирования для дискретизации значений признаков и получения нового набора признаков, распределенных по Бернулли. В некоторой литературе предполагается, что это необходимо для использования наивного Байеса, но это неправда, поскольку дискретизация может отбросить дискриминационную информацию . ^[3]

Иногда распределение условно-классовых предельных плотностей далеко от нормального. В этих случаях оценка плотности ядра может использоваться для более реалистичной оценки предельных плотностей каждого класса. Этот метод, предложенный Джоном и Лэнгли ^[8] , может значительно повысить точность классификатора. ^{[11] [12]}

Полиномиальный наивный Байес

В полиномиальной модели событий выборки (векторы признаков) представляют частоты, с которыми определенные события были сгенерированы многочленом, где — вероятность того, что событие i произойдет (или K таких многочленов в случае мультикласса). Вектор признаков представляет собой гистограмму , в которой подсчитывается количество раз, когда событие i наблюдалось в конкретном случае. Это модель событий, обычно используемая для классификации документов, при этом события представляют появление слова в одном документе (см. предположение о наборе слов ). Вероятность наблюдения гистограммы x определяется выражением: ${\displaystyle (p_{1},\dots ,p_{n})}$ ${\displaystyle p_{i}}$ ${\displaystyle \mathbf {x} =(x_{1},\dots ,x_{n})}$ ${\displaystyle x_{i}}$

${\displaystyle p(\mathbf {x} \mid C_{k})={\frac {(\sum _{i=1}^{n}x_{i})!}{\prod _{i=1}^{n}x_{i}!}}\prod _{i=1}^{n}{p_{ki}}^{x_{i}}}$где . ${\displaystyle p_{ki}:=p(x_{i}\mid C_{k})}$

Полиномиальный наивный байесовский классификатор становится линейным классификатором , если его выразить в логарифмическом пространстве: ^[13]

${\displaystyle {\begin{aligned}\log p(C_{k}\mid \mathbf {x} )&\varpropto \log \left(p(C_{k})\prod _{i=1}^{n}{p_{ki}}^{x_{i}}\right)\\&=\log p(C_{k})+\sum _{i=1}^{n}x_{i}\cdot \log p_{ki}\\&=b+\mathbf {w} _{k}^{\top }\mathbf {x} \end{aligned}}}$

где и . Оценка параметров в пространстве журнала является преимуществом, поскольку умножение большого количества малых значений может привести к значительной ошибке округления. Применение логарифмического преобразования уменьшает влияние этой ошибки округления. ${\displaystyle b=\log p(C_{k})}$ ${\displaystyle w_{ki}=\log p_{ki}}$

Если данный класс и значение признака никогда не встречаются вместе в обучающих данных, то оценка вероятности на основе частоты будет равна нулю, поскольку оценка вероятности прямо пропорциональна количеству появлений значения признака. Это проблематично, поскольку при их умножении будет уничтожена вся информация о других вероятностях. Поэтому часто желательно включать поправку малой выборки, называемую псевдосчетом , во все оценки вероятности, чтобы ни одна вероятность никогда не становилась точно равной нулю. Этот способ регуляризации наивного Байеса называется сглаживанием Лапласа , когда псевдосчет равен единице, и сглаживанием Лидстоуна в общем случае.

Ренни и др. обсудить проблемы с полиномиальным предположением в контексте классификации документов и возможные способы решения этих проблем, включая использование весов tf–idf вместо необработанных частот терминов и нормализации длины документа, чтобы создать наивный байесовский классификатор, конкурентоспособный с опорным вектором машины . ^[13]

Бернулли, наивный Байес

В многомерной модели событий Бернулли функции представляют собой независимые логические значения ( двоичные переменные ), описывающие входные данные. Как и полиномиальная модель, эта модель популярна для задач классификации документов, ^[9] где используются признаки встречаемости двоичных терминов, а не частоты терминов. Если это логическое значение, выражающее появление или отсутствие i -го термина в словаре, то вероятность того, что документ имеет класс, определяется выражением: ^[9] ${\displaystyle x_{i}}$ ${\displaystyle C_{k}}$

${\displaystyle p(\mathbf {x} \mid C_{k})=\prod _{i=1}^{n}p_{ki}^{x_{i}}(1-p_{ki})^{(1-x_{i})}}$

где вероятность того, что класс породит термин . Эта модель событий особенно популярна для классификации коротких текстов. Его преимущество заключается в явном моделировании отсутствия терминов. Обратите внимание, что наивный байесовский классификатор с моделью событий Бернулли — это не то же самое, что полиномиальный классификатор NB с числом частот, усеченным до единицы. ${\displaystyle p_{ki}}$ ${\displaystyle C_{k}}$ ${\displaystyle x_{i}}$

Полуконтролируемая оценка параметров

Имея способ обучения наивного байесовского классификатора на основе размеченных данных, можно построить полуконтролируемый алгоритм обучения, который может обучаться на комбинации размеченных и неразмеченных данных, запуская алгоритм обучения с учителем в цикле: ^[14]

Учитывая коллекцию помеченных выборок L и немаркированных выборок U , начните с обучения наивного байесовского классификатора на L . ${\displaystyle D=L\uplus U}$

До схождения делаем:

Спрогнозируйте вероятности классов для всех примеров x в . ${\displaystyle P(C\mid x)}$ ${\displaystyle D}$

Переобучите модель на основе вероятностей (а не меток), предсказанных на предыдущем шаге.

Сходимость определяется на основе улучшения правдоподобия модели , где обозначает параметры наивной байесовской модели. ${\displaystyle P(D\mid \theta )}$ ${\displaystyle \theta }$

Этот алгоритм обучения является примером более общего алгоритма максимизации ожидания (EM): шагом прогнозирования внутри цикла является E -шаг EM, а повторное обучение наивного байесовского алгоритма представляет собой M -шаг. Алгоритм формально обоснован предположением, что данные генерируются моделью смеси , а компоненты этой модели смеси являются в точности классами задачи классификации. ^[14]

Обсуждение

Несмотря на то, что далеко идущие предположения о независимости часто бывают неточными, наивный классификатор Байеса обладает несколькими свойствами, которые делают его удивительно полезным на практике. В частности, разделение распределений условных признаков классов означает, что каждое распределение можно независимо оценить как одномерное распределение. Это помогает смягчить проблемы, возникающие из-за проклятия размерности , такие как необходимость в наборах данных, которые экспоненциально масштабируются в зависимости от количества объектов. Хотя наивный Байес часто не может дать хорошую оценку правильных вероятностей классов, ^[15] это может не быть требованием для многих приложений. Например, простой байесовский классификатор выполнит правильную классификацию по правилу принятия решений MAP, если правильный класс прогнозируется как более вероятный, чем любой другой класс. Это верно независимо от того, является ли оценка вероятности незначительной или даже крайне неточной. Таким образом, общий классификатор может быть достаточно надежным, чтобы игнорировать серьезные недостатки лежащей в его основе наивной вероятностной модели. ^[16] Другие причины наблюдаемого успеха наивного байесовского классификатора обсуждаются в цитируемой ниже литературе.

Связь с логистической регрессией

В случае дискретных входных данных (индикатор или частотные характеристики для дискретных событий) наивные байесовские классификаторы образуют генеративно-дискриминативную пару с классификаторами полиномиальной логистической регрессии : каждый наивный байесовский классификатор можно рассматривать как способ подбора вероятностной модели, которая оптимизирует совместное правдоподобие. , тогда как логистическая регрессия соответствует той же вероятностной модели для оптимизации условной . ^[17] ${\displaystyle p(C,\mathbf {x} )}$ ${\displaystyle p(C\mid \mathbf {x} )}$

Более формально мы имеем следующее:

Теорема  .  Наивные байесовские классификаторы бинарных признаков включаются в состав классификаторов логистической регрессии.

Доказательство

Рассмотрим общую задачу мультиклассовой классификации с возможными классами , тогда (ненаивный) байесовский классификатор дает по теореме Байеса: ${\displaystyle Y\in \{1,...,n\}}$

$${\displaystyle p(Y\mid X=x)={\text{softmax}}(\{\ln p(Y=k)+\ln p(X=x\mid Y=k)\}_{k})}$$

Наивный классификатор Байеса дает

$${\displaystyle {\text{softmax}}\left(\left\{\ln p(Y=k)+{\frac {1}{2}}\sum _{i}(a_{i,k}^{+}-a_{i,k}^{-})x_{i}+(a_{i,k}^{+}+a_{i,k}^{-})\right\}_{k}\right)}$$

где

$${\displaystyle a_{i,s}^{+}=\ln p(X_{i}=+1\mid Y=s);\quad a_{i,s}^{-}=\ln p(X_{i}=-1\mid Y=s)}$$

Это и есть классификатор логистической регрессии.

Связь между ними можно увидеть, заметив, что функцию решения для наивного Байеса (в двоичном случае) можно переписать как «предсказать класс, если шансы превышают шансы «. Выражение этого в пространстве журнала дает: ${\displaystyle C_{1}}$ ${\displaystyle p(C_{1}\mid \mathbf {x} )}$ ${\displaystyle p(C_{2}\mid \mathbf {x} )}$

${\displaystyle \log {\frac {p(C_{1}\mid \mathbf {x} )}{p(C_{2}\mid \mathbf {x} )}}=\log p(C_{1}\mid \mathbf {x} )-\log p(C_{2}\mid \mathbf {x} )>0}$

Левая часть этого уравнения представляет собой логарифм шансов, или logit , величину, предсказанную линейной моделью, которая лежит в основе логистической регрессии. Поскольку наивный байесовский метод также является линейной моделью для двух «дискретных» моделей событий, его можно перепараметризовать как линейную функцию . Получение вероятностей тогда является вопросом применения логистической функции к или, в случае с несколькими классами, функции softmax . ${\displaystyle b+\mathbf {w} ^{\top }x>0}$ ${\displaystyle b+\mathbf {w} ^{\top }x}$

Дискриминационные классификаторы имеют меньшую асимптотическую ошибку, чем генеративные; однако исследования Нг и Джордана показали, что в некоторых практических случаях наивный байесовский метод может превзойти логистическую регрессию, поскольку он быстрее достигает своей асимптотической ошибки. ^[17]

Примеры

Классификация лиц

Задача: определить, является ли данный человек мужчиной или женщиной на основе измеренных характеристик. К характеристикам относятся рост, вес и размер стопы. Хотя в классификаторе NB мы рассматриваем их как независимые, на самом деле это не так.

Обучение

Пример обучающего набора ниже.

Классификатор, созданный на основе обучающего набора с использованием предположения о распределении Гаусса, будет иметь вид (учитывая, что дисперсии являются несмещенными выборочными дисперсиями ):

В следующем примере предполагается, что классы равновероятны, так что P(мужской) = P(женский) = 0,5. Это априорное распределение вероятностей может быть основано на предварительном знании частот в большей популяции или в обучающем наборе.

Тестирование

Ниже приведен образец, который можно отнести к мужскому или женскому полу.

Чтобы классифицировать образец, необходимо определить, какая задняя часть больше: самец или самка. Для классификации мужского пола задняя часть определяется выражением

${\displaystyle {\text{posterior (male)}}={\frac {P({\text{male}})\,p({\text{height}}\mid {\text{male}})\,p({\text{weight}}\mid {\text{male}})\,p({\text{foot size}}\mid {\text{male}})}{evidence}}}$

Для классификации как женщины задняя часть определяется как

${\displaystyle {\text{posterior (female)}}={\frac {P({\text{female}})\,p({\text{height}}\mid {\text{female}})\,p({\text{weight}}\mid {\text{female}})\,p({\text{foot size}}\mid {\text{female}})}{evidence}}}$

Доказательство (также называемое нормализующей константой) может быть рассчитано:

${\displaystyle {\begin{aligned}{\text{evidence}}=P({\text{male}})\,p({\text{height}}\mid {\text{male}})\,p({\text{weight}}\mid {\text{male}})\,p({\text{foot size}}\mid {\text{male}})\\+P({\text{female}})\,p({\text{height}}\mid {\text{female}})\,p({\text{weight}}\mid {\text{female}})\,p({\text{foot size}}\mid {\text{female}})\end{aligned}}}$

Однако, учитывая выборку, доказательства являются постоянными и, таким образом, одинаково масштабируют обе апостериорные области. Поэтому он не влияет на классификацию и его можно игнорировать. Теперь можно определить распределение вероятностей для пола выборки:

${\displaystyle P({\text{male}})=0.5}$

${\displaystyle p({\text{height}}\mid {\text{male}})={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}\exp \left({\frac {-(6-\mu )^{2}}{2\sigma ^{2}}}\right)\approx 1.5789}$,

где и – параметры нормального распределения, определенные ранее по обучающей выборке. Обратите внимание, что здесь допустимо значение больше 1 — это плотность вероятности, а не вероятность, поскольку рост — непрерывная переменная. ${\displaystyle \mu =5.855}$ ${\displaystyle \sigma ^{2}=3.5033\cdot 10^{-2}}$

${\displaystyle p({\text{weight}}\mid {\text{male}})={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}\exp \left({\frac {-(130-\mu )^{2}}{2\sigma ^{2}}}\right)=5.9881\cdot 10^{-6}}$

${\displaystyle p({\text{foot size}}\mid {\text{male}})={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}\exp \left({\frac {-(8-\mu )^{2}}{2\sigma ^{2}}}\right)=1.3112\cdot 10^{-3}}$

${\displaystyle {\text{posterior numerator (male)}}={\text{their product}}=6.1984\cdot 10^{-9}}$

${\displaystyle P({\text{female}})=0.5}$

${\displaystyle p({\text{height}}\mid {\text{female}})=2.23\cdot 10^{-1}}$

${\displaystyle p({\text{weight}}\mid {\text{female}})=1.6789\cdot 10^{-2}}$

${\displaystyle p({\text{foot size}}\mid {\text{female}})=2.8669\cdot 10^{-1}}$

${\displaystyle {\text{posterior numerator (female)}}={\text{their product}}=5.3778\cdot 10^{-4}}$

Поскольку задний числитель больше в случае женщины, прогнозируется, что выборка будет женщиной.

Классификация документов

Вот проработанный пример наивной байесовской классификации проблемы классификации документов . Рассмотрим задачу классификации документов по их содержанию, например на спамовые и неспамовые электронные письма . Представьте, что документы взяты из нескольких классов документов, которые можно смоделировать как наборы слов, где (независимая) вероятность того, что i-е слово данного документа встречается в документе из класса C, можно записать как

${\displaystyle p(w_{i}\mid C)\,}$

(При таком подходе все упрощается, если предположить, что слова распределены в документе случайным образом, то есть слова не зависят от длины документа, положения внутри документа по отношению к другим словам или другого контекста документа. )

Тогда вероятность того, что данный документ D содержит все слова данного класса C , равна ${\displaystyle w_{i}}$

${\displaystyle p(D\mid C)=\prod _{i}p(w_{i}\mid C)\,}$

Вопрос, на который необходимо ответить: «Какова вероятность того, что данный документ D принадлежит данному классу C ?» Другими словами, что такое ? ${\displaystyle p(C\mid D)\,}$

Теперь по определению

${\displaystyle p(D\mid C)={p(D\cap C) \over p(C)}}$

и

${\displaystyle p(C\mid D)={p(D\cap C) \over p(D)}}$

Теорема Байеса превращает их в формулировку вероятности с точки зрения правдоподобия .

${\displaystyle p(C\mid D)={\frac {p(C)\,p(D\mid C)}{p(D)}}}$

Предположим на мгновение, что существует только два взаимоисключающих класса, S и ¬ S (например, спам и не спам), так что каждый элемент (электронное письмо) принадлежит либо к одному, либо к другому;

${\displaystyle p(D\mid S)=\prod _{i}p(w_{i}\mid S)\,}$

и

${\displaystyle p(D\mid \neg S)=\prod _{i}p(w_{i}\mid \neg S)\,}$

Используя приведенный выше байесовский результат, можно написать:

${\displaystyle p(S\mid D)={p(S) \over p(D)}\,\prod _{i}p(w_{i}\mid S)}$

${\displaystyle p(\neg S\mid D)={p(\neg S) \over p(D)}\,\prod _{i}p(w_{i}\mid \neg S)}$

Деление одного на другое дает:

${\displaystyle {p(S\mid D) \over p(\neg S\mid D)}={p(S)\,\prod _{i}p(w_{i}\mid S) \over p(\neg S)\,\prod _{i}p(w_{i}\mid \neg S)}}$

Что можно перефакторизовать как:

${\displaystyle {p(S\mid D) \over p(\neg S\mid D)}={p(S) \over p(\neg S)}\,\prod _{i}{p(w_{i}\mid S) \over p(w_{i}\mid \neg S)}}$

Таким образом, отношение вероятностей p( S | D )/p(¬ S | D ) может быть выражено через ряд отношений правдоподобия . Фактическая вероятность p( S | D ) может быть легко вычислена из log (p( S | D ) / p(¬ S | D )) на основе наблюдения, что p( S | D ) + p(¬ S | D ) = 1.

Логарифмируя все эти отношения, получаем :

${\displaystyle \ln {p(S\mid D) \over p(\neg S\mid D)}=\ln {p(S) \over p(\neg S)}+\sum _{i}\ln {p(w_{i}\mid S) \over p(w_{i}\mid \neg S)}}$

(Этот метод « логарифмических отношений правдоподобия » является распространенным методом в статистике. В случае двух взаимоисключающих альтернатив (таких как этот пример) преобразование логарифмического отношения правдоподобия в вероятность принимает форму сигмовидной кривой . : подробности см. в журнале .)

Наконец, документ можно классифицировать следующим образом. Это спам, если (т.е. ), в противном случае это не спам. ${\displaystyle p(S\mid D)>p(\neg S\mid D)}$ ${\displaystyle \ln {p(S\mid D) \over p(\neg S\mid D)}>0}$

Смотрите также

• АОДЭ
• Классификатор Байеса
• Байесовская фильтрация спама
• Байесовская сеть
• Случайный наивный Байес
• Линейный классификатор
• Логистическая регрессия
• Персептрон
• Эвристика «Возьми лучшее»

Рекомендации

1. МакКаллум, Эндрю. «Графические модели, Лекция 2: Представление байесовской сети» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 22 октября 2019 г.
2. Рассел, Стюарт ; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Прентис Холл. ISBN 978-0137903955.
3. Hand, диджей; Ю, К. (2001). «Идиотский Байес — не такой уж и глупый?». Международный статистический обзор . 69 (3): 385–399. дои : 10.2307/1403452. ISSN  0306-7734. JSTOR  1403452.
4. Чжан, Гарри. Оптимальность наивного Байеса (PDF) . Конференция FLAIRS2004.
5. Каруана, Р.; Никулеску-Мизил, А. (2006). Эмпирическое сравнение алгоритмов обучения с учителем . Учеб. 23-я Международная конференция по машинному обучению. CiteSeerX 10.1.1.122.5901 . 
6. «Почему наивный байесовский метод работает лучше, когда количество функций >> размер выборки по сравнению с более сложными алгоритмами машинного обучения?». Обмен стеками с перекрестной проверкой . Проверено 24 января 2023 г.
7. Нарасимха Мурти, М.; Сушила Деви, В. (2011). Распознавание образов: алгоритмический подход . ISBN 978-0857294944.
8. Джон, Джордж Х.; Лэнгли, Пэт (1995). Оценка непрерывных распределений в байесовских классификаторах. Учеб. Одиннадцатая конф. О неопределенности в искусственном интеллекте. Морган Кауфманн. стр. 338–345. arXiv : 1302.4964 .
9. МакКаллум, Эндрю; Нигам, Камаль (1998). Сравнение моделей событий для текстовой классификации Наивного Байеса (PDF) . Семинар AAAI-98 по обучению категоризации текста. Том. 752. Архивировано (PDF) из оригинала 9 октября 2022 г.
10. Мецис, Вангелис; Андрутсопулос, Ион; Палиурас, Георгиос (2006). Фильтрация спама с помощью Наивного Байеса — какой Наивный Байес? Третья конференция по электронной почте и борьбе со спамом (CEAS). Том. 17.
11. Пирионеси, С. Маде; Эль-Дираби, Тамер Э. (01.06.2020). «Роль анализа данных в управлении инфраструктурными активами: преодоление проблем с размером и качеством данных». Журнал транспортной техники, Часть B: Тротуары . 146 (2): 04020022. doi :10.1061/JPEODX.0000175. S2CID  216485629.
12. Хасти, Тревор. (2001). Элементы статистического обучения: интеллектуальный анализ данных, логические выводы и прогнозирование: с 200 полноцветными иллюстрациями . Тибширани, Роберт, Фридман, Дж. Х. (Джером Х.). Нью-Йорк: Спрингер. ISBN 0-387-95284-5. ОСЛК  46809224.
13. Ренни, Дж.; Ши, Л.; Тиван, Дж.; Каргер, Д. (2003). Устранение плохих предположений наивных классификаторов Байеса (PDF) . ИКМЛ. Архивировано (PDF) из оригинала 9 октября 2022 г.
14. Нигам, Камаль; МакКаллум, Эндрю; Трун, Себастьян; Митчелл, Том (2000). «Учимся классифицировать текст из маркированных и немаркированных документов с помощью EM» (PDF) . Машинное обучение . 39 (2/3): 103–134. дои : 10.1023/А:1007692713085 . S2CID  686980. Архивировано (PDF) из оригинала 9 октября 2022 г.
15. Никулеску-Мизил, Александру; Каруана, Рич (2005). Прогнозирование хороших вероятностей с помощью обучения с учителем (PDF) . ИКМЛ. дои : 10.1145/1102351.1102430. Архивировано из оригинала (PDF) 11 марта 2014 г. Проверено 24 апреля 2016 г.
16. Риш, Ирина (2001). Эмпирическое исследование наивного классификатора Байеса (PDF) . Семинар IJCAI по эмпирическим методам в искусственном интеллекте. Архивировано (PDF) из оригинала 9 октября 2022 г.
17. Нг, Эндрю Ю .; Джордан, Майкл И. (2002). О дискриминативных и генеративных классификаторах: сравнение логистической регрессии и наивного Байеса. НИПС . Том. 14.

дальнейшее чтение

• Домингос, Педро; Паццани, Майкл (1997). «Об оптимальности простого байесовского классификатора при потерях ноль-единица». Машинное обучение . 29 (2/3): 103–137. дои : 10.1023/А:1007413511361 .
• Уэбб, Дж.И.; Боутон, Дж.; Ван, З. (2005). «Не такой уж наивный Байес: агрегирование оценщиков с одной зависимостью». Машинное обучение . 58 (1): 5–24. дои : 10.1007/s10994-005-4258-6 .
• Мозина, М.; Демсар, Дж.; Каттан, М.; Зупан, Б. (2004). Номограммы для визуализации наивного байесовского классификатора (PDF) . Учеб. ПКДД-2004. стр. 337–348.
• Марон, Мэн (1961). «Автоматическое индексирование: экспериментальное исследование». Журнал АКМ . 8 (3): 404–417. дои : 10.1145/321075.321084. hdl : 2027/uva.x030748531 . S2CID  6692916.
• Минский, М. (1961). Шаги к искусственному интеллекту . Учеб. ИРЭ. Том. 49. стр. 8–30.

Внешние ссылки

• Глава книги: Наивная байесовская классификация текстов, Введение в информационный поиск
• Наивный Байес для классификации текста с несбалансированными классами
• Сравнительные результаты реализаций Наивного Байеса
• Иерархические наивные байесовские классификаторы для неопределенных данных (расширение наивного байесовского классификатора).

Программное обеспечение

• Наивные байесовские классификаторы доступны во многих пакетах машинного обучения и НЛП общего назначения, включая Apache Mahout , Mallet, NLTK , Orange , scikit-learn и Weka .
• Числовые библиотеки IMSL Коллекции математических и статистических алгоритмов, доступных на C/C++, Fortran, Java и C#/.NET. Процедуры интеллектуального анализа данных в библиотеках IMSL включают в себя наивный байесовский классификатор.
• Интерактивная реализация электронной таблицы Microsoft Excel с использованием метода Наивного Байеса с использованием VBA (требуются включенные макросы) с доступным для просмотра исходным кодом.
• jBNC — набор инструментов байесовского классификатора сетей
• Набор инструментов статистического распознавания образов для Matlab.
• ifile — первый свободно доступный (наивный) байесовский фильтр почты и спама.
• NClassifier — NClassifier — это библиотека .NET, поддерживающая классификацию и обобщение текста. Это порт Classifier4J.
• Classifier4J — Classifier4J — это библиотека Java, предназначенная для классификации текста. Он поставляется с реализацией байесовского классификатора.
• Наивный байесовский классификатор JNBC, работающий в памяти или использующий быстрые хранилища значений ключей (MapDB, LevelDB или RocksDB).
• Blayze — Blayze — это минимальная JVM-библиотека для наивной байесовской классификации, написанная на Котлине.