Архив новостей

Применимость Байесовского классификатора для задачи определения спама

Формальное определение Байесовского классификатора


Постановка задачи классификации документов


Задача классификации документов состоит в том, чтобы найти приближенное отображение 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] вводится классификация не по двум категориям, а по трем.

Фильтры, основанные на вероятностных методах


Фильтров, использующих НБК, очень много. Для тестирования были выбраны несколько наиболее популярных из них:


  1. BayesIt! 0.6.0, встроенный в почтовый клиент The Bat! 3.0, http://www.ritlabs.com/ru/solutions/BayesIt.php.
  2. Mozilla Thunderbird 0.8, http://www.mozilla.org/products/thunderbird/. В этот почтовый клиент встроен собственный фильтр, основанный на НБК.
  3. PopFile 0.21.2, http://popfile.sourceforge.net/, pop3-прокси, использующий НБК. В качестве почтового клиента был выбран MS Outlook Express.
  4. 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




 

Большие количества писем не тестировались, потому что их обработка в большинстве случаев заканчивалась аварийно. Тем не менее, можно выделить две проблемы:


  1. Количество ложных срабатываний.
  2. Явное переобучение фильтра во время тестирования почтовых ящиков, содержащих 80% спама от всех сообщений, когда более половины нормальных сообщений были ошибочно опознаны как спам.

В почтовом ящике info количество спамерских писем было уменьшено до 800, чтобы его удалось обработать. После обучения фильтр допустил 10% ложных срабатываний и распознал 51% спама.

Mozilla Thunderbird


Встроенный фильтр спама, судя по описанию, также основан на работах Пола Грэма [4, 5]. В отличие от BayesIt!, он значительно более устойчив в работе. Имеет минимальное количество настроек и, судя по всему, самостоятельно следит за излишним переобучением.



























Количество не спамерских писем Объем спама в почтовом ящике
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%




 

Основная проблема данного фильтра — ложные срабатывания, во всяком случае, на разноязычной почте. Во всех почтовых ящиках, где было мало нормальных английских сообщений, почти все они были признаны спамом. С другой стороны, в одном почтовом ящике с небольшим количеством почты и полностью отсутствующими нормальными сообщениями на английском языке ложных срабатываний не возникло.

В почтовом ящике info было допущено 11% ложных срабатываний и 67% спама было распознано.

PopFile


Фильтр спама, работающий как pop3-прокси между любым почтовым клиентом и провайдером. В отличие от остальных фильтров, поддерживает классификацию более чем по одной категории (спам или не спам), основываясь на использовании нескольких двоичных классификаторов для каждой из категорий. Дает возможность пользователю заводить свои собственные категории. Тем не менее, во время тестирования использовался только как бинарный классификатор.

В связи с тем, что веб-интерфейс фильтра PopFile не позволяет удобно выбрать одновременно несколько сообщений для ручной классификации, опробовать его на больших почтовых ящиках не удалось. Ниже приведены числа только для тех из них, на которых это удалось сделать. Мало того, общее количество ящиков, на которых проверялся PopFile, было еще меньше, чем у остальных.

Даже при двух категориях (спам и не спам) PopFile имеет третью — Unclassified. При вычислениях считалось, что все содержимое этой категории было отнесено к нормальной почте.



























Количество не спамерских писем Объем спама в почтовом ящике
25% 50% 80%
180 5% / 97% 4% / 98%
500
1600




 

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

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

SpamAssassin


Фильтр спама, объединяющий в себе большое количество методов — от проверки по RBL до вероятностных методов с обучением. В отличие от предыдущих фильтров, использует не НБК, а метод Фишера, описанный в работе Гари Робинсона [7].

Во время тестирования спамом считались все письма, которые получали метку BAYES_60 и выше (т.к. соответствующие правила в стандартной поставке имеют вес более 3.5).



























Количество не спамерских писем Объем спама в почтовом ящике
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%




 

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

Все ложные срабатывания имели высокий вес BAYES_90 или BAYES_99, поэтому изменение критерия спама на более высокий не изменило бы количество ложных срабатываний, но уменьшило бы процент распознавания спама.

В почтовом ящике info было допущено 8% ложных срабатываний и 75% спама было распознано.

Выводы


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

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

Рассмотрим основные проблемы, которые встретились при использовании НБК.

Разноязыковый спам


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

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

Коммерческие предложения


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

Этот факт очень хорошо виден в ящике info, который оказался наиболее сложным почтовым ящиком для всех классификаторов (кроме popfile, который на нем не проверялся из-за неудобности пользовательского интерфейса). Приглашения на известные конференции и семинары, коммерческие предложения, даже адресованные лично представителям фирмы, написанные с реальных почтовых адресов, были определены фильтрами как спамерские сообщения. Кроме того, большое количество коммерческих предложений в ‘хорошей’ части обучающей базы сильно понизило и качество распознавания спама.

Чрезмерное обучение


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

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

Но при обучении может нарушиться равновесие между количеством спамерских сообщений и обычных, что может привести к лавинообразному увеличению количества ложных срабатываний, как это наблюдалось у фильтра BayesIt!

Проблема заключается в том, что до сих пор не появилось способов оценки базы НБК на ее ‘переобученность’, не говоря уж о выделении неактуальных или ложных ее элементов. Авторы фильтров, основанных на НБК, часто оставляют обработку базы на пользователе, который должен следить за количеством писем или характеристик в базе и удалять или добавлять письма, чтобы поддерживать равновесие фильтра. Таким образом, ответственность за ложные срабатывания перекладывается на конечного получателя.

Тем не менее, несмотря на описанные выше проблемы, вероятностные методы вполне могут быть использованы в современных фильтрах.

Применимость НБК


НБК может вполне удачно работать в персональных фильтрах спама, но выступая не как решающий фактор признания письма спамом, а как дополнительный. То есть, если фильтр уже нашел иными способами какие-то формальные признаки спама, недостаточные для достижения порога ‘спама’, но при этом НБК тоже сигнализирует о ‘спамности’ письма, то такое письмо можно отнести к категории ‘спам’. Тем самым можно нивелировать ложные срабатывания НБК.

Метод Фишера


Следует отдельно отметить реализацию описанного выше метода Фишера, использованного в фильтре SpamAssassin. Данный фильтр показал наименьшее количество ложных срабатываний при лучшем уровне распознавания спама и оказался чрезвычайно стойким к проблеме излишнего переобучения. Таким образом, можно рекомендовать его к использованию в фильтрах спама вместо НБК как значительно более надежный метод. Хотя стоит еще раз обратить внимание на то, что на ящике info и этот метод показал 8% ложных срабатываний.

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

Ссылки



  1. David D. Lewis. Naпve (Bayes) at forty: the independence assumption in information retrieval, 2000.
  2. Fabrizio Sebastiani. Machine learning in automated text categorization, ACM Computing Surveys, Vol. 34, No. 1, 2002.
  3. M.E. Maron, J.L. Kuhns. On relevance, probabilistic indexing and information retrieval. Journal of the ACM, July 1960.
  4. Paul Graham, A plan for spam, http://paulgraham.com/spam.html .
  5. Paul Graham, Better Bayesian filtering, http://paulgraham.com/better.html .
  6. В. С. Пугачев. Теория вероятностей и математическая статистика. М.: Физматлит, 2002.
  7. Gary Robinson, A statistical approach to the spam problem, 2003, http://www.linuxjournal.com/article.php?sid=6467.

Применимость Байесовского классификатора для задачи определения спама

Ваш e-mail не будет опубликован. Обязательные поля помечены *

 

Отчеты

MosaicRegressor: угроза в недрах UEFI

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

Подпишитесь на еженедельную рассылку

Самая актуальная аналитика – в вашем почтовом ящике