Авторы
Формальное определение Байесовского классификатора
Постановка задачи классификации документов
Задача классификации документов состоит в том, чтобы найти приближенное отображение K´=DxC→{T,F} отображения K, такого что K(d, c)=T тогда и только тогда, когда документ d соответствует категории c и K(d,c)=F в обратном случае.
Полученная аппроксимация K’ называется классификатором. В случае если категории статистически независимы друг от друга (то есть K´(dj,c´) не зависит от K´(dj,c´´) для любых c´c´´ ), то можно без потери общности предположить, что множество категорий состоит только из двух непересекающихся категорий, к одной из которых обязательно принадлежит каждый из документов: 
. Это связано с тем, что случай с большим количеством категорий {c1,…cn} можно представить как n задач вида 
.
Таким образом, задача классификации приводится к виду поиска приближенного отображения K´=DxC→{T,F}.
Кроме того, вводится множество характеристик T, которые могут быть сопоставлены с документами. Тогда документ d представляется вектором коэффициентов (w1,…,w|T|), 0≤wi≤1. Коэффициенты wi, грубо говоря, определяют ‘вклад’ характеристики ti в семантику документа d.
В любом методе автоматической классификации сначала определяются характеристики документов и способ вычисления весов.
Наивный Байесовский классификатор
Байесовский классификатор основан на использовании знаменитой теоремы Байеса, и первые упоминания о нем можно встретить еще в 1960-м году [3]. За уже более чем 40-летнюю историю НБК использовался для решения самых разнообразных задач: от классификации текстов в новостных агентствах до первичной диагностики заболеваний в медицинских учреждениях.
При постановке задачи для НБК в качестве характеристик обычно выбирается наличие или отсутствие каких либо слов в документе, то есть за множество характеристик T принимается множество всех слов в обрабатываемых документах. Таким образом, вес характеристики wi=1 в том случае, если слово ti было найдено, и wi=0 в обратном случае. В случае с фильтрами, которые используются для классификации спама [5], учитывается еще и область, в которой встретилось слово: заголовки, тема письма (subject), тело письма. То есть слово ‘спам’, встретившееся в теме письма, есть иной термин, чем слово ‘спам’ в теле письма.
Кроме того, делается очень важное допущение: предполагается, что все характеристики документов, полученные таким образом (слова), статистически независимы; именно из-за этого допущения в названии классификатора присутствует слово ‘наивный’. Это сильно упрощает применение теоремы Байеса для построения классификатора.
НБК, обычно используемый в спам-фильтрах (предложенный Полом Грэмом [3, 4]) имеет вид p1·p2 … p|d|/(p1·p2 … p|d|+(1–p1)·(1–p2 … (1–p|d|))>W, где pi=P(wi=1|c), W — заданный пользователем порог. При этом используются вероятности только тех характеристик, которые встретились в документе. Такой НБК отличается от классической формулы [1, 2] тем, что в нем не используются вероятности самих категорий (или, точнее, эти категории приняты за равновероятные). Такое решение обосновывается авторами [7] тем, что принятие решения о конкретном письме не должно быть связано с количеством спама в почтовом ящике, а должно вычисляться исключительно по содержимому самого письма.
Для вычисления вероятностей pi используется т.н. процесс обучения, во время которого анализируются заранее классифицированные документы. Тогда вероятности можно рассчитать, к примеру, следующим образом: pi=bi/(gi+bj) , где bi — количество ‘плохих’ документов, содержащих характеристику ti; gi — количество ‘хороших’ документов, содержащих характеристику ti.
В реальных фильтрах, основанных на НБК, могут использоваться иные способы вычисления оценок вероятностей, учитывающие специальные случаи редких характеристик (встречающихся в малом количестве документов). К примеру, Гари Робинсон рекомендует заменить оценку pi на fi [7]: fi=(s·x+ni·pi)/(s+ni), где s и x — экспериментально подобранные параметры (рекомендуется 1 и 0.5), а n — количество документов с характеристикой ti.
Метод Фишера
Начиная с публикации статьи Гари Робинсона [7], в некоторых фильтрах (например, SpamAssassin) вместо НБК стал использоваться метод совмещения вероятностей, предложенный Р. Фишером в 1950 году.
Применительно к классификации документов, Робинсон сформулировал этот метод следующим образом: допустим, что документ имеет n характеристик, для каждой из которых уже рассчитана вероятность pi . Тогда, согласно Фишеру, если эти вероятности не распределены равномерно, то значение 
будет подчиняться закону распределения χ2(2n).
Таким образом, становится возможным найти вероятность того, что для некоторых иных значений pi соответствующее число будет больше, чем рассчитанное для данного документа. Если эта вероятность достаточно мала, то документ следует отнести к рассматриваемой категории.
Для определения спама Робинсон предложил рассчитать подобным образом не только вероятность ‘спамности’ документа (H), но и вероятность того, что письмо не является спамом (S), и использовать показатель I, рассчитываемый по формуле I=(1+H–S)/2. Если показатель I достаточно близок к 0, то письмо считается ‘не спамом’; если I достаточно близок к 1, письмо считается ‘спамом’. В противном случае письмо считается спорным. Таким образом, в работе [7] вводится классификация не по двум категориям, а по трем.
Фильтры, основанные на вероятностных методах
Фильтров, использующих НБК, очень много. Для тестирования были выбраны несколько наиболее популярных из них:
- BayesIt! 0.6.0, встроенный в почтовый клиент The Bat! 3.0, http://www.ritlabs.com/ru/solutions/BayesIt.php.
- Mozilla Thunderbird 0.8, http://www.mozilla.org/products/thunderbird/. В этот почтовый клиент встроен собственный фильтр, основанный на НБК.
- PopFile 0.21.2, http://popfile.sourceforge.net/, pop3-прокси, использующий НБК. В качестве почтового клиента был выбран MS Outlook Express.
- SpamAssassin 3.0.0 rc3, http://spamassassin.apache.org. В этом фильтре используется предложенный Гари Робинсоном способ вычисления совмещенных вероятностей. При этом он не является определяющим фактором для рубрикации спама, а учитывается вместе с другими методами. При тестировании учитывались только оценки модуля bayes.
Методика тестирования
Для тестирования использовались несколько персональных почтовых ящиков, уже очищенных вручную от спама за период в 3 месяца. Каждый из них разбавлялся спамом за то же время из архивов компании Ашманов и Партнеры таким образом, чтобы полученный почтовый ящик cодержал бы 25%, 50% или 80% спама. Источником спама всегда служил только один почтовый адрес. Фильтры обучались по периодам в два месяца, месяц, две недели и неделю, но не менее чем на 150-180 нормальных письмах. Затем проверялась работа классификатора в течение следующих двух недель.
Кроме того, отдельно исследовалось поведение фильтров на почтовом ящике info крупной компании. Этот ящик сильно отличается по своему составу от персональных почтовых ящиков обычных пользователей тем, что в нем присутствует действительно многоязычная переписка (русский, английский, итальянский, французский и китайский языки); присылаются приглашения на участие в различных конференциях и семинарах, предложения по подписке от туристических фирм, коммерческие предложения и т.п. Понятно, что потеря настоящего коммерческого предложения в таком почтовом ящике недопустима.
Из писем предварительно удалялась большая часть технической информации (заголовки received, метки других антиспамерских фильтров) для того, чтобы фильтр не мог бы настроиться на характерные для выбранного потока спама особенности, отличные от персонального почтового ящика, например, IP-адреса серверов компании ‘Ашманов и Партнеры’.
Для обучения использовались все обычные сообщения, которые были в почтовых ящиках, и все добавленные спамерские сообщения. В документации к некоторым Байесовским фильтрам указано, что обучение должно быть выборочным и пользователю необходимо либо ограничивать количество писем, на которых будет обучаться спам-фильтр, либо следить за тем, чтобы количество обычных и спамерских писем было бы одинаковым. Автор считает, что такая ситуация должна обрабатываться программным обеспечение фильтра, а не пользователем. Кроме того, случаи излишнего переобучения тоже требуют изучения.
Во всех фильтрах использовались настройки ‘по умолчанию’ для переноса спамерских писем в другую почтовую папку (если таковые были).
Конечно же, методика тестирования не является строгой: наиболее точным способом было бы использование всех перечисленных фильтров в реальной работе в течение нескольких месяцев на всех использованных почтовых ящиках. Кроме того, количество доступных почтовых ящиков для тестирования было ограниченным и, может быть, не репрезентативным. Тем не менее, можно считать, что проведенное тестирование является достаточным приближением к реальному использованию фильтров.
Результаты тестирования
В приведенных ниже результатах тестирования указан средний процент ложных срабатываний и распознавания спама для каждого классификатора в формате ‘процент ложных срабатываний / процент распознанного спама’. Все использованные ящики и периоды сгруппированы по количеству писем, которые подавались на обучение, так как ни один классификатор не смог обработать почтовые ящики с приемлемым количеством ложных срабатываний.
Почтовый ящик info обрабатывался специальным образом: в отличие от остальных ящиков, в нем оставались все спамерские сообщения, пришедшие за исследуемый период. При этом за месяц в нем содержалось 600 нормальных и 9000 спамерских писем. Для того чтобы облегчить фильтрам задачу, были выбраны для обучения вся нормальная почта и 1500 спамерских писем за последние дни этого месяца. Для тестирования были выбраны 190 нормальных писем за следующую неделю и 800 спамерских писем за следующие три дня.
BayesIt!
Данный фильтр является плагином к известному почтовому клиенту The Bat! и с третьей версии включен в стандартную поставку. Судя по описанию и генерируемым отчетам, он целиком основан на работах Пола Грэма [4, 5], то есть учитывает расположение слов (тело письма или заголовок) и техническую информацию; имеет ограничение на количество слов, выбираемых из документа для анализа.
| Количество не спамерских писем | Объем спама в почтовом ящике | ||
| 25% | 50% | 80% | |
| 180 | 4% / 85% | 2% / 90% | 71% / 92% |
| 500 | 3% / 89% | 4% / 93% | 43% / 92% |
| 1600 | — | — | — |
| Количество не спамерских писем | Объем спама в почтовом ящике | ||
| 25% | 50% | 80% | |
| 180 | 0.7% / 75% | 0.7% / 81% | 1.2% / 79% |
| 500 | 1% / 77% | 0.9% / 80% | 2% / 81% |
| 1600 | 2.5% / 85% | 2% / 84% | 3% / 81% |
| Количество не спамерских писем | Объем спама в почтовом ящике | ||
| 25% | 50% | 80% | |
| 180 | 5% / 97% | 4% / 98% | — |
| 500 | — | — | — |
| 1600 | — | — | — |
| Количество не спамерских писем | Объем спама в почтовом ящике | ||
| 25% | 50% | 80% | |
| 180 | 0.7% / 89% | 0.6% / 92% | 1.3% / 90% |
| 500 | 0.7% / 91% | 0.8% / 91% | 1.7% / 92% |
| 1600 | 1% / 90% | 1% / 92 % | 2% / 92% |
Применимость Байесовского классификатора для задачи определения спама