Теорема Байеса использует термин вероятности, вероятность представляет из себя степень возможности наступления события. Часто вероятность находится как частота наступления заданных событий ко всем рассматриваемым событиям. Теорема Байеса отражена в формуле (1), где в качестве объекта рассматривается сообщение.

                                           (1)

где,

 – вероятность принадлежности сообщение  к классу ;

 – вероятность встречи сообщение  среди класса ;

 – безусловная вероятность встречи сообщение класса ;

 – безусловная вероятность сообщение .

Применение теоремы Байеса к задаче к классификации спам сообщений возможна при помощи дополнения [1]. Чтобы определить к какому классу принадлежит сообщение необходимо посчитать вероятность принадлежности для каждого класса и выбрать класс, с максимальной вероятностью. Если записать данное утверждение в виде уравнения, то оно будет иметь следующий вид (2)

                                   (2)

Так как безусловная вероятность сообщения , находящееся в знаменателе представляет из себя константу и не влияет на ранжирование классов, то можно преобразовать уравнение (2) исключив из него безусловную вероятность сообщения , и получить уравнение виде (3):

                                      (3)

Уравнение (3) рассчитывает вероятность для сообщения целиком, чтобы повысить точность необходимо сообщение представить в виде набора слов, для это необходимо добавить аппроксимацию произведения условных вероятностей для слов в сообщении, для этого преобразуем часть формулы (3) в формулу (4):

                    (4)

Из-за независимости появления слов в классе от контекста Байесовский алгоритм называю наивным. Применив формулу (4) к формуле (5) получим формулу (6)

        (6)

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

                                   (7)

Учитывая свойство произведения логарифма (7) и монотонность будет корректным добавить аппроксимацию логарифма к уравнению (6) получив формулу (8) не учитывая основание логарифма, так как оно в данном случае не будет влиять на выразительность данных. Полученные значения из уравнения (8) будут более удобным для дальнейшего анализа.

                       (8)

Оценка вероятности  и  происходит на обучающей выборке, а вероятность класса рассчитывается по формуле

                                                  (9)

где

 – количество сообщений, принадлежащих классу ;

 – общее количество сообщений в обучающей выборке.

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

                                     (10)

где

– количество раз встречаемости рассчитываемого слова в сообщениях класса ;

V – список уникальных слов.

         Формула (10) не учитывает проблему неизвестных слов, появившихся после этапа обучения. То есть если во время классификации тестовой выборки появится слово, которого не было на этапе обучения, то значение  будет нулевым. Если  будет равно нулю, то сообщение нельзя будет отнести ни к какой категории. Решить данную проблему путем учета всех слов в обучающей выборки с учетом опечаток невозможно. Для решения проблемы неизвестных слов будет использоваться сглаживание Лапласа. Идея заключается в том, что алгоритм воспринимает каждое слово так, как будто видел каждое слово на один раз больше, то есть прибавляет единицу к частоте каждого слова.

                    (11)

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

Рассмотрим такое решение проблемы на практическом примере, допустим есть модель, которая обучается именами, и на этапе обучения были имена представленные в таблице Таблица 1, где в левой колонке указаны имена, а в правой частота их встречи в тексте.

После обучения на этапе классификации в тестовой выборке встретится имя Валера, которого не было на этапе обучения. Тогда оценки вероятностей смещенной и оригинальной будут выглядеть следующим образом, вероятность распознавания имени Миша снизится на 1 десятую, для  Паши снизится 4 сотых, а для Данила и Валеры вероятность распознавания возрастет, это видно на рисунке Рисунок 1.

         Из гистограммы Рисунок 1 видно, что результат распознавания ранее неизвестного имени Валера теперь не нулевой, что показывает актуальность применимости метода Лапласа к распознаванию неизвестных слов. Подставив выбранные оценки в уравнение (7) получим формулу байесовского классификатора, учитывавшего проблему неизвестных слов (12).

                    (12)

         Для того, чтобы реализовать классификатор на основе теоремы Байеса необходимо составить корректную обучающую выборку и собрать следующие данные: количество уникальность слов, частоту встречаемости экземпляров всех классов, относительную частота каждого класса и объем обучающей выборки. После сбора данных, необходимо рассчитать вероятность принадлежности для всех классу по формуле (13), чтобы определить максимальную из них. И к какому классу вероятность принадлежности будет максимальной, к тому классу и принадлежит документ.

                             (13)

где

 – количество сообщений в обучающей выборке, принадлежащих классу ;

 – общее количество сообщений в обучающей выборке;

 – множество слов классифицируемого сообщения вместе с повторами;

 – сколько раз слово с индексом  встречалось в сообщениях класса  в обучающей выборке;

 – количество уникальных слов во всех сообщениях обучающей выборки;

 – суммарное количество слов в сообщениях класса  в обучающей выборке.

Рассмотрим полученный классификатор, основанный на теореме Байеса на практике, для это возьмем тестовую выборку с сообщениями представлеными в таблице Таблица 2:

Модель классификатора будет использовать обучающую выборку в структурированном виде представленном в таблице Таблица 4 и параметры представленный в таблице Таблица 3.

Такие параметры как частота классов и суммарное количество слов, представленные в таблице Таблица 3 необходимы для расчета примера байесовского классификатора.

Классифицируем фразу «надо купить лекарство». Рассчитаем значение выражения для класса спам (15) по формуле (14):

             (15)

Теперь рассчитаем ту же фразу для класса не спам (16) по формуле (14):

              (16)

Данная фраза будет отнесена к классу не спам, так как выбирается наибольшая вероятность, а в результат вычислений в формуле (16) больше, чем в формуле (15).

         Формула (14) имеет недостаток, так как если показатели двух классов будут достаточно близкими, то невозможно будет добавить приоритет какой-либо группе с указанием процента. Реализовать такой приоритет возможно, если данные будут в диапазоне от 0 до 1 и сумма всех вероятностных оценок будет равна 1. Выполнить перечисленные условия можно для формулы (14) сформировав вероятностное пространство, то есть избавившись от логарифма и нормировав сумму по единице.

                                      (17)

где

 – логарифмическая оценка алгоритма для класса .

В формуле (17) возведение  в степень оценки используется для того, чтобы избавиться от логарифма ().

Для фразы «надо купить лекарство» вероятность принадлежности к классу спам по формуле (17) составит 0.327 исходя из расчетов в формуле (18)

                                    (18)

то есть сообщение является спамом с вероятностью 46.87%, а у на ограничение, что если сообщение не принадлежит к категории спам с вероятностью большей чем 75%, то значит такое сообщение относится к категории не спам.

В библиотеке sklearn алгоритм есть алгоритм байесовского классификатора, и имеет параметр, описанный в формуле (11), который позволяет избежать обнуления неизвестных слов. Зависимость данного параметра от распознавания спама представлена на графике Рисунок 2.

Из данного графика(рисунок Рисунок 2) видно, что наилучшее распознавание спама происходит при параметре 0.1, и чем больше его значение, тем меньше процент распознавания.

Проверка на тестовой выборке

Исходные данные состоят из более чем 5000[3] записей на английском языке. В которой есть две группы текстов: спам и общение. Задача классифицирующего алгоритма будет показать как можно более высокий процент на тестовой выборке.

Алгоритм пишется на языке программирования python 3 версии. Построенный алгоритм имеет следующие этапы:

1) считывания слов из файла;

2) преобразования слов с помощью алгоритма Стемминга [2,6];

3) обучение модели на обучающей выборке;

4) проверка алгоритмов на тестовой выборке дает следующие данные смотреть

По результатам тестирования, метод Байеса распознал спам в 98,6% случаев. При тестировании параметр, сглаживающий нулевую вероятность для неизвестных слов, описанный в формуле (11) был равен 0.1.