Байесовская фильтрация спама
Для улучшения этой статьи желательно:
|
Ба́йесовская фильтра́ция спа́ма — метод для фильтрации спама, основанный на применении наивного байесовского классификатора, опирающегося на прямое использование теоремы Байеса. Теорема Байеса названа в честь её автора Томаса Байеса (1702—1761) — английского математика и священника, который первым предложил использование теоремы для корректировки убеждений, основываясь на обновлённых данных.
История
[править | править код]Первой известной программой, фильтрующей почту с использованием байесовского классификатора, была программа iFile Джейсона Ренни, выпущенная в 1996 году. Программа использовала сортировку почты по папкам[1]. Первая академическая публикация по наивной байесовской фильтрации спама появилась в 1998 году[2]. Вскоре после этой публикации была развернута работа по созданию коммерческих фильтров спама[источник не указан 4446 дней]. Однако в 2002 г. Пол Грэм смог значительно уменьшить число ложноположительных срабатываний до такой степени, что байесовский фильтр мог использоваться в качестве единственного фильтра спама[3][4][5].
Модификации основного подхода были развиты во многих исследовательских работах и внедрены в программных продуктах[6]. Многие современные почтовые клиенты осуществляют байесовское фильтрование спама. Пользователи могут также установить отдельные программы фильтрования почты. Фильтры для почтового сервера — такие, как DSPAM, SpamAssassin, SpamBayes, SpamProbe, Bogofilter, CRM114 — используют методы байесовского фильтрования спама[5]. Программное обеспечение серверов электронной почты либо включает фильтры в свою поставку, либо предоставляет API для подключения внешних модулей.
Описание
[править | править код]При обучении фильтра для каждого встреченного в письмах слова высчитывается и сохраняется его «вес» — оценка вероятности того, что письмо с этим словом — спам. В простейшем случае в качестве оценки используется частота: «появлений в спаме / появлений всего». В более сложных случаях возможна предварительная обработка текста: приведение слов в начальную форму, удаление служебных слов, вычисление «веса» для целых фраз, транслитерация и прочее.
При проверке вновь пришедшего письма вероятность «спамовости» вычисляется по указанной выше формуле для множества гипотез. В данном случае «гипотезы» — это слова, и для каждого слова «достоверность гипотезы» — доля этого слова в письме, а «зависимость события от гипотезы» — вычисленный ранее «вес» слова. То есть «вес» письма в данном случае — усреднённый «вес» всех его слов.
Отнесение письма к «спаму» или «не-спаму» производится по тому, превышает ли его «вес» некую планку, заданную пользователем (обычно берут 60-80 %). После принятия решения по письму в базе данных обновляются «веса» для вошедших в него слов.
Математические основы
[править | править код]Почтовые байесовские фильтры основываются на теореме Байеса. Теорема Байеса используется несколько раз в контексте спама:
- в первый раз, чтобы вычислить вероятность, что сообщение — спам, зная, что данное слово появляется в этом сообщении;
- во второй раз, чтобы вычислить вероятность, что сообщение — спам, учитывая все его слова (или соответствующие их подмножества);
- иногда в третий раз, когда встречаются сообщения с редкими словами.
Вычисление вероятности того, что сообщение, содержащее данное слово, является спамом
[править | править код]Давайте предположим, что подозреваемое сообщение содержит слово «Replica». Большинство людей, которые привыкли получать электронное письмо, знает, что это сообщение, скорее всего, будет спамом, а точнее — предложением продать поддельные копии часов известных брендов. Программа обнаружения спама, однако, не «знает» такие факты; всё, что она может сделать — вычислить вероятности.
Формула, используемая программным обеспечением, чтобы определить это, получена из теоремы Байеса и формулы полной вероятности:
где:
- — условная вероятность того, что сообщение—спам, при условии, что слово «Replica» находится в нём;
- — полная вероятность того, что произвольное сообщение—спам;
- — условная вероятность того, что слово «replica» появляется в сообщениях, если они являются спамом;
- — полная вероятность того, что произвольное сообщение не спам (то есть «ham»);
- — условная вероятность того, что слово «replica» появляется в сообщениях, если они являются «ham».
Спамовость слова
[править | править код]Недавние статистические исследования[7] показали, что на сегодняшний день вероятность любого сообщения быть спамом составляет по меньшей мере 80 %: .
Однако большинство байесовских программ обнаружения спама делают предположение об отсутствии априорных предпочтений у сообщения быть «spam», а не «ham», и полагает, что у обоих случаев есть равные вероятности 50 %: .
О фильтрах, которые используют эту гипотезу, говорят как о фильтрах «без предубеждений». Это означает, что у них нет никакого предубеждения относительно входящей электронной почты. Данное предположение позволяет упрощать общую формулу до:
Значение называют «спамовостью» слова ; при этом число , используемое в приведённой выше формуле, приближённо равно относительной частоте сообщений, которые содержат слово в сообщениях, идентифицированных как спам во время фазы обучения, то есть:
Точно так же приближённо равно относительной частоте сообщений, содержащих слово в сообщениях, идентифицированных как «ham» во время фазы обучения.
Для того, чтобы эти приближения имели смысл, набор обучающих сообщений должен быть большим и достаточно представительным. Также желательно, чтобы набор обучающих сообщений соответствовал 50 % гипотезе о перераспределении между спамом и «ham», то есть что наборы сообщений «spam» и «ham» имели один и тот же размер.
Конечно, определение, является ли сообщение «spam» или «ham», базируемой только на присутствии лишь одного определённого слова, подвержено ошибкам. Именно поэтому байесовские фильтры спама пытаются рассмотреть несколько слов и комбинировать их спамовость, чтобы определить полную вероятность того, что сообщение является спамом.
Объединение индивидуальных вероятностей
[править | править код]Программные спам-фильтры, построенные на принципах наивного байесовского классификатора, делают «наивное» предположение о том, что события, соответствующие наличию того или иного слова в электронном письме или сообщении, являются независимыми по отношению друг к другу. Это упрощение в общем случае является неверным для естественных языков — таких, как английский, где вероятность обнаружения прилагательного повышается при наличии, к примеру, существительного. Исходя из такого «наивного» предположения, для решения задачи классификации сообщений лишь на 2 класса: (спам) и («хэм», то есть не спам) из теоремы Байеса можно вывести следующую формулу оценки вероятности «спамовости» всего сообщения, содержащего слова :
- [по теореме Байеса] [так как предполагаются независимыми]
- [по теореме Байеса] [по формуле полной вероятности]
Таким образом, предполагая , имеем:
где:
- — вероятность, что сообщение, содержащее слова — спам;
- — условная вероятность того, что сообщение — спам, при условии, что оно содержит первое слово (к примеру, «replica»);
- — условная вероятность того, что сообщение — спам, при условии, что оно содержит второе слово (к примеру, «watches»);
- и т. д.
- — условная вероятность того, что сообщение — спам, при условии, что оно содержит N-е слово (к примеру, «home»).
(Demonstration:[8])
Результат p обычно сравнивают с некоторым порогом (например, ), чтобы решить, является ли сообщение спамом или нет. Если p ниже, чем порог, сообщение рассматривают как вероятный «ham», иначе его рассматривают как вероятный спам.
Проблема редких слов
[править | править код]Она возникает в случае, если слово никогда не встречалось во время фазы обучения: и числитель, и знаменатель равны нулю, и в общей формуле, и в формуле спамовости.
В целом, слова, с которыми программа столкнулась только несколько раз во время фазы обучения, не являются репрезентативными (набор данных в выборке мал для того, чтобы сделать надёжный вывод о свойстве такого слова). Простое решение состоит в том, чтобы игнорировать такие ненадёжные слова.
Другие эвристические усовершенствования
[править | править код]«Нейтральные» слова — такие, как, «the», «a», «some», или «is» (в английском языке), или их эквиваленты на других языках — могут быть проигнорированы. Вообще говоря, некоторые байесовские фильтры просто игнорируют все слова, у которых спамовость около 0.5, так как в этом случае получается качественно лучшее решение. Учитываются только те слова, спамовость которых около 0.0 (отличительный признак законных сообщений — «ham»), или рядом с 1.0 (отличительный признаки спама). Метод отсева может быть настроен, например, так, чтобы держать только те десять слов в исследованном сообщении, у которых есть самое большое absolute value |0.5 − Pr|.
Некоторые программные продукты принимают во внимание тот факт, что определённое слово появляется несколько раз в проверяемом сообщении[9], другие этого не делают.
Некоторые программные продукты используют словосочетания — patterns (последовательности слов) вместо изолированных слов естественных языков[10]. Например, с «контекстным окном» из четырёх слов они вычисляют спамовость словосочетания «Виагра, хорошо для», вместо того, чтобы вычислить спамовости отдельных слов «Виагры», «хорошо», и «для». Этот метод более чувствителен к контексту и лучше устраняет байесовский шум — за счёт большей базы данных.
Смешанные методы
[править | править код]Кроме «наивного» байесовского подхода, есть и другие способы скомбинировать—объединить отдельные вероятности для различных слов. Эти методы отличаются от «наивного» метода предположениями, которые они делают о статистических свойствах входных данных. Две различные гипотезы приводят к радикально различным формулам для совокупности (объединения) отдельных вероятностей.
Например, для проверки предположения о совокупности отдельных вероятностей, логарифм произведения которых, с точностью до константы, подчиняется распределению хи-квадрат с 2N степенями свободы, можно использовать формулу:
где через C−1 обозначена обратная функция для функции распределения хи-квадрат (см. Обратное распределение хи-квадрат[англ.]).
Отдельные вероятности могут быть объединены также методами марковской дискриминации.
Характеристика
[править | править код]Данный метод прост (алгоритмы элементарны), удобен (позволяет обходиться без «чёрных списков» и подобных искусственных приёмов), эффективен (после обучения на достаточно большой выборке отсекает до 95—97 % спама), причём в случае любых ошибок его можно дообучать. В общем, есть все показания для его повсеместного использования, что и имеет место на практике — на его основе построены практически все современные спам-фильтры.
Впрочем, у метода есть и принципиальный недостаток: он базируется на предположении, что одни слова чаще встречаются в спаме, а другие — в обычных письмах, и неэффективен, если данное предположение неверно. Впрочем, как показывает практика, такой спам даже человек не в состоянии определить «на глаз» — только прочтя письмо и поняв его смысл. Существует метод Байесова отравления[англ.], позволяющий добавить много лишнего текста, иногда тщательно подобранного, чтобы «обмануть» фильтр.
Ещё один не принципиальный недостаток, связанный с реализацией — метод работает только с текстом. Зная об этом ограничении, спамеры стали вкладывать рекламную информацию в картинку. Текст же в письме либо отсутствует, либо не несёт смысла. Против этого приходится пользоваться либо средствами распознавания текста («дорогая» процедура, применяется только при крайней необходимости), либо старыми методами фильтрации — «чёрные списки» и регулярные выражения (так как такие письма часто имеют стереотипную форму).
См. также
[править | править код]Примечания
[править | править код]- ↑ Jason Rennie. ifile (1996). Архивировано 25 октября 2012 года.
- ↑ Sahami, Dumais, Heckerman, Horvitz, 1998.
- ↑ Paul Graham (2003), Better Bayesian filtering Архивная копия от 21 июня 2010 на Wayback Machine
- ↑ Brian Livingston (2002), Paul Graham provides stunning answer to spam e-mails Архивная копия от 10 июня 2010 на Wayback Machine
- ↑ 1 2 Guzella, Caminhas, 2009.
- ↑ Junk Mail Controls . MozillaZine (ноябрь 2009). Архивировано 25 октября 2012 года.
- ↑ More Than 90 Percent of E-Mails in Third Quarter (of 2008) Were Spam, Certification Magazine . Дата обращения: 16 сентября 2012. Архивировано 23 сентября 2012 года.
- ↑ Combining probabilities . Архивировано 16 апреля 2012 года. at MathPages
- ↑ Brian Burton. SpamProbe - Bayesian Spam Filtering Tweaks (2003). Архивировано 16 апреля 2012 года.
- ↑ Jonathan A. Zdziarski. Bayesian Noise Reduction: Contextual Symmetry Logic Utilizing Pattern Consistency Analysis (2004). (недоступная ссылка)
Литература
[править | править код]- Guzella T. S., Caminhas W. M. A review of machine learning approaches to Spam filtering // Expert Systems with Applications. — 2009. — Vol. 36, no. 7. — P. 10206—10222. — doi:10.1016/j.eswa.2009.02.037.
- Metsis V., Androutsopoulos I., Paliouras G. . Spam Filtering with Naive Bayes — Which Naive Bayes? // CEAS 2006: Third Conference on Email and Anti-Spam, July 27-28, 2006, Mountain View, California, USA. — 2006.
- Sahami M., Dumais S., Heckerman D., Horvitz E. A Bayesian approach to filtering junk email // AAAI Workshop on Learning for Text Categorization. Technical Report. — 1998.
Ссылки
[править | править код]- Paul Graham. A plan for spam Архивная копия от 4 апреля 2004 на Wayback Machine // Персональный сайт Пола Грэхема.