Байесовская фильтрация спама

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставив сноски, внести более точные указания на источники. Переработать оформление в соответствии с правилами написания статей. Исправить статью согласно стилистическим правилам Википедии. Викифицировать список литературы, используя шаблон {{книга}}, и проставить ISBN.

Байесовская фильтрация спама — метод для фильтрации спама, основанный на применении наивного байесовского классификатора, в основе которого лежит применение теоремы Байеса.

История

Первая известная программа фильтрующая почту, использующая Баесовский классификатор, была iFile программой Джейсона Ренни, выпущенной в 1996. Программа использовала сортировку почты в виде папок^[1]. Первая академическая публикация по наивной байесовской фильтрации спама появилась в 1998^[2]. Вскоре после этой публикации была развернута работа по созданию коммерческих фильтров спама^{[источник не указан 84 дня]}. Однако, в 2002 Пол Грэм смог значительно уменьшить число ложноположительных срабатываний до такой степени, что байесовский фильтр мог использоваться в качестве единственного фильтра спама^[3][4][5].

Модификации основного подхода были развиты во многих исследовательских работах и внедрены в программных продуктах^[6]. Многие современные почтовые клиенты осуществляют байесовское фильтрование спама. Пользователи могут также установить отдельные программы фильтрования почты. Фильтры для почтового сервера, такие как DSPAM, SpamAssassin, SpamBayes, SpamProbe, Bogofilter, CRM114 используют методы байесовского фильтрования спама^[5]. Программное обеспечение серверов электронной почты либо включает фильтры в свою поставку, либо предоставляет API для подключения внешних модулей.

Описание

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

При проверке вновь пришедшего письма вероятность «спамовости» вычисляется по указанной выше формуле для множества гипотез. В данном случае «гипотезы» — это слова, и для каждого слова «достоверность гипотезы» $P(A_i) = N_{word_i}/N_{words~total}$ — доля этого слова в письме, а «зависимость события от гипотезы» $P(B|A_i)$ — вычисленный ранее «вес» слова. То есть «вес» письма в данном случае — усредненный «вес» всех его слов.

Отнесение письма к «спаму» или «не-спаму» производится по тому, превышает ли его «вес» некую планку, заданную пользователем (обычно берут 60-80 %). После принятия решения по письму в базе данных обновляются «веса» для вошедших в него слов.

Математические основы

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

Вычисление вероятности того, что сообщение, содержащее данное слово, является спамом

Давайте предположим, что подозреваемое сообщение содержит слово «Replica». Большинство людей, которые привыкли получать электронное письмо, знает, что это сообщение, скорее всего, будет спамом, а точнее предложением продать поддельные копии часов известных брендов. Программа обнаружения спама, однако, не «знает» такие факты, все, что она может сделать—вычислить вероятности.

Формула, используемая программным обеспечением, чтобы определить это, получена из теоремы Байеса и формулы полной вероятности:

$\Pr(S|W) = \frac{\Pr(W|S) \cdot \Pr(S)}{\Pr(W)} = \frac{\Pr(W|S) \cdot \Pr(S)}{\Pr(W|S) \cdot \Pr(S) + \Pr(W|H) \cdot \Pr(H)}$

где:

• $\Pr(S|W)$ — условная вероятность того, что сообщение—спам, при условии, что слово «Replica» находится в нем;
• $\Pr(S)$ — полная вероятность того, что произвольное сообщение—спам;
• $\Pr(W|S)$ — условная вероятность того, что слово «replica» появляется в сообщениях, если они являются спамом;
• $\Pr(H)$ — полная вероятность того, что произвольное сообщение не спам (то есть «ham»);
• $\Pr(W|H)$ — условная вероятность того, что слово «replica» появляется в сообщениях, если они являются «ham».

Спамовость слова

Недавние статистические исследования^[7] показали, что на сегодняшний день вероятность любого сообщения быть спамом составляет по меньшей мере 80 %: $\Pr(S) = 0.8 ; \Pr(H) = 0.2$.

Однако, большинство байесовских программ обнаружения спама делают предположение об отсутствии априорных предпочтений у сообщения быть «spam», а не «ham», и полагает, что у обоих случаев есть равные вероятности 50 %: $\Pr(S) = 0.5 ; \Pr(H) = 0.5$.

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

$\Pr(S|W) = \frac{\Pr(W|S)}{\Pr(W|S) + \Pr(W|H)}$

Значение $Pr(S|W)$ называют «спамовостью» слова $W$, при этом число $\Pr(W|S)$, используемое в формуле выше, приближенно равно относительной частоте сообщений, содержащих слово $W$ в сообщениях, идентифицированных как спам во время фазы обучения, то есть:

$Pr(W_i|S) = \frac{count(M : W_i \in M, M \in S)}{\sum_j count(M : W_j \in M, M \in S)}$

Точно так же $\Pr(W|H)$ приближенно равно относительной частоте сообщений, содержащих слово $W$ в сообщениях, идентифицированных как «ham» во время фазы обучения.

$Pr(W_i|H) = \frac{count(M : W_i \in M, M \in H)}{\sum_j count(M : W_j \in M, M \in H)}$

Для того, чтобы эти приближения имели смысл, набор обучающих сообщений должен быть большим и достаточно представительным. Также желательно чтобы набор обучающих сообщений соответствовал 50 % гипотезе о перераспределении между спамом и «ham», то есть что наборы сообщений «spam» и «ham» имели один и тот же размер.

Конечно, определение, является ли сообщение «spam» или «ham», базируемой только на присутствии лишь одного определённого слова, подвержено ошибкам, именно поэтому байесовские фильтры спама пытаются рассмотреть несколько слов и комбинировать их спамовость, чтобы определить полную вероятность того, что сообщение является спамом.

Объединение индивидуальных вероятностей

Программные спам-фильтры, построенные на принципах наивного байесовского классификатора, делают «наивное» предположение о том, что события, соответствующие наличию того или иного слова в электронном письме или сообщении, являются независимыми по отношению друг к другу. Это упрощение в общем случае является неверным для естественных языков таких как английский, где вероятность обнаружения прилагательного повышается при наличии, к примеру, существительного. Исходя из такого «наивного» предположения, для решения задачи классификации сообщений лишь на 2 класса: $S$ (спам) и $H = \neg S$ («хэм», то есть не спам) из теоремы Байеса можно вывести следующую формулу оценки вероятности «спамовости» всего сообщения, содержащего слова $W_1, W_2, ... W_N$:

$p(S|W_1, W_2, ... W_N) =$ [по теореме Байеса] $= \frac{p(W_1, W_2, ... W_N|S) \cdot p(S)}{p(W_1, W_2, ... W_N)} =$ [так как $W_i$ — предполагаются независимыми] $=$

$= \frac{\prod_{i} p(W_i|S) \cdot p(S)}{p(W_1, W_2, ... W_N)} =$ [по теореме Байеса] $=\frac{\prod_{i}\frac{p(S|W_i) \cdot p(W_i)}{p(S)} \cdot p(S)}{p(W_1, W_2, ... W_N)} =$ [по формуле полной вероятности] $=$

$=\frac{\prod_{i}\frac{p(S|W_i) \cdot p(W_i)}{p(S)} \cdot p(S)}{\prod_i(p(W_i|S)) \cdot p(S) + \prod_i(p(W_i|\neg S)) \cdot p(\neg S)} =$

$= \frac{\prod_{i}(p(S|W_i) \cdot p(W_i)) \cdot p(S)^{1-N}}{\prod_i(p(S|W_i) \cdot p(W_i)) \cdot p(S)^{1-N} + \prod_i(p(\neg S|W_i) \cdot p(W_i)) \cdot p(\neg S)^{1-N}} =$

$= \frac{\prod_{i}p(S|W_i)}{\prod_i(p(S|W_i)) + (\frac{p(\neg S)}{p(S)})^{1-N} \cdot \prod_i p(\neg S|W_i)}$

Таким образом, предполагая $p(S) = p(\neg S) = 0.5$, имеем:

$p = \frac{p_1 p_2 \cdots p_N}{p_1 p_2 \cdots p_N + (1 - p_1)(1 - p_2) \cdots (1 - p_N)}$

где:

• $p = Pr(S|W_1, W_2, ..., W_N)$ — вероятность, что сообщение, содержащее слова $W_1, W_2, ..., W_N$ — спам;
• $p_1$ — условная вероятность $p(S|W_1)$ того, что сообщение — спам, при условии, что оно содержит первое слово (к примеру «replica»);
• $p_2$ — условная вероятность $p(S|W_2)$ того, что сообщение — спам, при условии, что оно содержит второе слово (к примеру «watches»);
• и т. д.
• $p_N$ — условная вероятность $p(S|W_N)$ того, что сообщение — спам, при условии, что оно содержит Nое слово (к примеру «home»).

(Demonstration:^[8])

Результат p обычно сравнивают с некоторым порогом, например, $0.5$, чтобы решить, является ли сообщение спамом или нет. Если p ниже чем порог, сообщение рассматривают как вероятный «ham», иначе его рассматривают как вероятный спам.

Проблема редких слов

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

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

Другие эвристические усовершенствования

«Нейтральные» слова такие, как, «the», «a», «some», или «is» (в английском языке), или их эквиваленты на других языках, могут быть проигнорированы. Вообще говоря, некоторые байесовские фильтры просто игнорируют все слова, у которых спамовость около 0.5, так как в этом случае получается качественно лучшее решение. Учитываются только те слова, спамовость которых около 0.0 (отличительный признак законных сообщений — «ham»), или рядом с 1.0 (отличительный признаки спама). Метод отсева может быть настроен например так, чтобы держать только те десять слов в исследованном сообщении, у которых есть самое большое absolute value |0.5 − Pr|.

Некоторые программные продукты принимают во внимание тот факт, что определённое слово появляется несколько раз в проверяемом сообщении^[9], другие не делают.

Некоторые программные продукты используют словосочетания — patterns (последовательности слов) вместо изолированных слов естественных языков^[10]. Например, с «контекстным окном» из четырех слов, они вычисляют спамовость словосочетания «Виагра, хорошо для», вместо того, чтобы вычислить спамовости отдельных слов «Виагры», «хорошо», и «для». Этот метод более чувствителен к контексту и устраняет байесовский шум лучше, за счет большей базы данных.

Смешанные методы

Кроме «наивного» байесовского подхода есть и другие способы скомбинировать—объединить отдельные вероятности для различных слов. Эти методы отличаются от «наивного» метода предположениями, которые они делают о статистических свойствах входных данных. Две различные гипотезы приводят к радикально различным формулам для совокупности (объединения) отдельных вероятностей.

Например, для проверки предположения о совокупности отдельных вероятностей, логарифм произведения которых, с точностью до константы подчиняется распределению хи-квадрат с 2N степенями свободы, можно было использовать формулу:

$p = C^{-1}(-2 \ln(p_1 p_2 \cdots p_N), 2N) \,$

где C⁻¹ is the inverse of the chi-square function.

Отдельные вероятности могут быть объединены также методами марковской дискриминации.

Характеристика

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

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

Еще один не принципиальный недостаток, связанный с реализацией — метод работает только с текстом. Зная об этом ограничении, спамеры стали вкладывать рекламную информацию в картинку. Текст же в письме либо отсутствует, либо не несёт смысла. Против этого приходится пользоваться либо средствами распознавания текста («дорогая» процедура, применяется только при крайней необходимости), либо старыми методами фильтрации — «черные списки» и регулярные выражения (так как такие письма часто имеют стереотипную форму).

Примечания

1. ↑ Jason Rennie ifile (1996). Архивировано из первоисточника 25 октября 2012.
2. ↑ Sahami, Dumais, Heckerman, Horvitz, 1998
3. ↑ Paul Graham (2003), Better Bayesian filtering
4. ↑ Brian Livingston (2002), Paul Graham provides stunning answer to spam e-mails
5. ↑ ^{1 2} Guzella, Caminhas, 2009
6. ↑ Junk Mail Controls. MozillaZine (November 2009). Архивировано из первоисточника 25 октября 2012.
7. ↑ More Than 90 Percent of E-Mails in Third Quarter (of 2008) Were Spam, Certification Magazine
8. ↑ Combining probabilities. Архивировано из первоисточника 16 апреля 2012. at MathPages
9. ↑ Brian Burton SpamProbe - Bayesian Spam Filtering Tweaks (2003). Архивировано из первоисточника 16 апреля 2012.
10. ↑ Jonathan A. Zdziarski Bayesian Noise Reduction: Contextual Symmetry Logic Utilizing Pattern Consistency Analysis (2004).(недоступная ссылка — история)(недоступная ссылка)

Литература

• M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz A Bayesian approach to filtering junk email (англ.) // AAAI Workshop on Learning for Text Categorization : Technical Report. — 1998.
• Paul Graham. A plan for spam  (англ.) // Персональный сайт Paul Graham.
• Thiago S. Guzella, Walmir M. Caminhas A review of machine learning approaches to Spam filtering (англ.) // Expert Systems with Applications. — 2009. — Т. 36. — № 7. — С. 10206–10222. — DOI:10.1016/j.eswa.2009.02.037
• Vangelis Metsis. Spam Filtering with Naive Bayes — Which Naive Bayes? (2006)  (англ.)