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

Ба́йесовская фильтра́ция спа́ма — метод для фильтрации спама, основанный на применении наивного байесовского классификатора, опирающегося на прямое использование теоремы Байеса. Теорема Байеса названа в честь её автора Томаса Байеса (1702—1761) — английского математика и священника, который первым предложил использование теоремы для корректировки убеждений, основываясь на обновлённых данных.

ИсторияПравить

Первой известной программой, фильтрующей почту с использованием байесовского классификатора, была программа iFile Джейсона Ренни, выпущенная в 1996 году. Программа использовала сортировку почты по папкам. Первая академическая публикация по наивной байесовской фильтрации спама появилась в 1998 году. Вскоре после этой публикации была развернута работа по созданию коммерческих фильтров спама. Однако в 2002 г. Пол Грэм смог значительно уменьшить число ложноположительных срабатываний до такой степени, что байесовский фильтр мог использоваться в качестве единственного фильтра спама.

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

ОписаниеПравить

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

При проверке вновь пришедшего письма вероятность «спамовости» вычисляется по указанной выше формуле для множества гипотез. В данном случае «гипотезы» — это слова, и для каждого слова «достоверность гипотезы» $P(A_i)=N_{wor{d}_i}/N_{wordstotal}$$P(A_{i})=N_{word_{i}}/N_{words~total}$  — доля этого слова в письме, а «зависимость события от гипотезы» $P(B\mid <!--\; \mid \; -->A_i)$$P(B\mid A_{i})$  — вычисленный ранее «вес» слова. То есть «вес» письма в данном случае — усреднённый «вес» всех его слов.

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

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

Почтовые байесовские фильтры основываются на теореме Байеса. Теорема Байеса используется несколько раз в контексте спама:

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

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

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

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

$Pr(S\mid <!--\; \mid \; -->W)=\frac{Pr(W\mid <!--\; \mid \; -->S)\cdot <!--\; \cdot \; -->Pr(S)}{Pr(W)}=\frac{Pr(W\mid <!--\; \mid \; -->S)\cdot <!--\; \cdot \; -->Pr(S)}{Pr(W\mid <!--\; \mid \; -->S)\cdot <!--\; \cdot \; -->Pr(S)+Pr(W\mid <!--\; \mid \; -->H)\cdot <!--\; \cdot \; -->Pr(H)}$$\Pr(S\mid W)={\frac {\Pr(W\mid S)\cdot \Pr(S)}{\Pr(W)}}={\frac {\Pr(W\mid S)\cdot \Pr(S)}{\Pr(W\mid S)\cdot \Pr(S)+\Pr(W\mid H)\cdot \Pr(H)}}$ 

где:

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

Спамовость словаПравить

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

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

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

$Pr(S\mid <!--\; \mid \; -->W)=\frac{Pr(W\mid <!--\; \mid \; -->S)}{Pr(W\mid <!--\; \mid \; -->S)+Pr(W\mid <!--\; \mid \; -->H)}$$\Pr(S\mid W)={\frac {\Pr(W\mid S)}{\Pr(W\mid S)+\Pr(W\mid H)}}$ 

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

$Pr(W_i\mid <!--\; \mid \; -->S)=\frac{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(M:W_i\in <!--\; \in \; -->M,M\in <!--\; \in \; -->S)}{\underset{j}{\sum <!--\; \sum \; -->}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(M:W_j\in <!--\; \in \; -->M,M\in <!--\; \in \; -->S)}$$Pr(W_{i}\mid S)={\frac {\mathrm {count} (M:W_{i}\in M,M\in S)}{\sum _{j}\mathrm {count} (M:W_{j}\in M,M\in S)}}$ 

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

$Pr(W_i\mid <!--\; \mid \; -->H)=\frac{\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(M:W_i\in <!--\; \in \; -->M,M\in <!--\; \in \; -->H)}{\underset{j}{\sum <!--\; \sum \; -->}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}(M:W_j\in <!--\; \in \; -->M,M\in <!--\; \in \; -->H)}$$Pr(W_{i}\mid H)={\frac {\mathrm {count} (M:W_{i}\in M,M\in H)}{\sum _{j}\mathrm {count} (M:W_{j}\in M,M\in H)}}$ 

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

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

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

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

$p(S\mid <!--\; \mid \; -->W_1,W_2,...W_N)=$$p(S\mid W_{1},W_{2},...W_{N})=$  [по теореме Байеса] $=\frac{p(W_1,W_2,...W_N\mid <!--\; \mid \; -->S)\cdot <!--\; \cdot \; -->p(S)}{p(W_1,W_2,...W_N)}=$$={\frac {p(W_{1},W_{2},...W_{N}\mid S)\cdot p(S)}{p(W_{1},W_{2},...W_{N})}}=$  [так как $W_i$$W_i$  предполагаются независимыми] $=$$=$ 

$=\frac{\underset{i}{\prod <!--\; \prod \; -->}p(W_i\mid <!--\; \mid \; -->S)\cdot <!--\; \cdot \; -->p(S)}{p(W_1,W_2,...W_N)}=$$={\frac {\prod _{i}p(W_{i}\mid S)\cdot p(S)}{p(W_{1},W_{2},...W_{N})}}=$  [по теореме Байеса] $=\frac{\underset{i}{\prod <!--\; \prod \; -->}\frac{p(S\mid <!--\; \mid \; -->W_i)\cdot <!--\; \cdot \; -->p(W_i)}{p(S)}\cdot <!--\; \cdot \; -->p(S)}{p(W_1,W_2,...W_N)}=$$={\frac {\prod _{i}{\frac {p(S\mid W_{i})\cdot p(W_{i})}{p(S)}}\cdot p(S)}{p(W_{1},W_{2},...W_{N})}}=$  [по формуле полной вероятности] $=$$=$ 

$=\frac{\underset{i}{\prod <!--\; \prod \; -->}\frac{p(S\mid <!--\; \mid \; -->W_i)\cdot <!--\; \cdot \; -->p(W_i)}{p(S)}\cdot <!--\; \cdot \; -->p(S)}{\underset{i}{\prod <!--\; \prod \; -->}(p(W_i\mid <!--\; \mid \; -->S))\cdot <!--\; \cdot \; -->p(S)+\underset{i}{\prod <!--\; \prod \; -->}(p(W_i\mid <!--\; \mid \; -->\mathrm{\neg <!--\; \neg \; -->}S))\cdot <!--\; \cdot \; -->p(\mathrm{\neg <!--\; \neg \; -->}S)}=$$={\frac {\prod _{i}{\frac {p(S\mid W_{i})\cdot p(W_{i})}{p(S)}}\cdot p(S)}{\prod _{i}(p(W_{i}\mid S))\cdot p(S)+\prod _{i}(p(W_{i}\mid \neg S))\cdot p(\neg S)}}=$ 

$=\frac{\underset{i}{\prod <!--\; \prod \; -->}(p(S\mid <!--\; \mid \; -->W_i)\cdot <!--\; \cdot \; -->p(W_i))\cdot <!--\; \cdot \; -->p(S{)}^{1-<!--\; -\; -->N}}{\underset{i}{\prod <!--\; \prod \; -->}(p(S\mid <!--\; \mid \; -->W_i)\cdot <!--\; \cdot \; -->p(W_i))\cdot <!--\; \cdot \; -->p(S{)}^{1-<!--\; -\; -->N}+\underset{i}{\prod <!--\; \prod \; -->}(p(\mathrm{\neg <!--\; \neg \; -->}S\mid <!--\; \mid \; -->W_i)\cdot <!--\; \cdot \; -->p(W_i))\cdot <!--\; \cdot \; -->p(\mathrm{\neg <!--\; \neg \; -->}S{)}^{1-<!--\; -\; -->N}}=$$={\frac {\prod _{i}(p(S\mid W_{i})\cdot p(W_{i}))\cdot p(S)^{1-N}}{\prod _{i}(p(S\mid W_{i})\cdot p(W_{i}))\cdot p(S)^{1-N}+\prod _{i}(p(\neg S\mid W_{i})\cdot p(W_{i}))\cdot p(\neg S)^{1-N}}}=$ 

$=\frac{\underset{i}{\prod <!--\; \prod \; -->}p(S\mid <!--\; \mid \; -->W_i)}{\underset{i}{\prod <!--\; \prod \; -->}(p(S\mid <!--\; \mid \; -->W_i))+{\left(\frac{p(\mathrm{\neg <!--\; \neg \; -->}S)}{p(S)}\right)}^{1-<!--\; -\; -->N}\cdot <!--\; \cdot \; -->\underset{i}{\prod <!--\; \prod \; -->}p(\mathrm{\neg <!--\; \neg \; -->}S\mid <!--\; \mid \; -->W_i)}$$={\frac {\prod _{i}p(S\mid W_{i})}{\prod _{i}(p(S\mid W_{i}))+\left({\frac {p(\neg S)}{p(S)}}\right)^{1-N}\cdot \prod _{i}p(\neg S\mid W_{i})}}$ 

Таким образом, предполагая $p(S)=p(\mathrm{\neg <!--\; \neg \; -->}S)=0.5$$p(S)=p(\neg S)=0.5$ , имеем:

$p=\frac{p_1{p}_2\cdots <!--\; \cdots \; -->p_N}{p_1{p}_2\cdots <!--\; \cdots \; -->p_N+(1-<!--\; -\; -->p_1)(1-<!--\; -\; -->p_2)\cdots <!--\; \cdots \; -->(1-<!--\; -\; -->p_N)}$$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\mid <!--\; \mid \; -->W_1,W_2,...,W_N)$$p=Pr(S\mid W_{1},W_{2},...,W_{N})$  — вероятность, что сообщение, содержащее слова $W_1,W_2,...,W_N$$W_{1},W_{2},...,W_{N}$  — спам;
• $p_1$$p_{1}$  — условная вероятность $p(S\mid <!--\; \mid \; -->W_1)$$p(S\mid W_{1})$  того, что сообщение — спам, при условии, что оно содержит первое слово (к примеру, «replica»);
• $p_2$$p_{2}$  — условная вероятность $p(S\mid <!--\; \mid \; -->W_2)$$p(S\mid W_{2})$  того, что сообщение — спам, при условии, что оно содержит второе слово (к примеру, «watches»);
• и т. д.
• $p_N$$p_{N}$  — условная вероятность $p(S\mid <!--\; \mid \; -->W_N)$$p(S\mid W_{N})$  того, что сообщение — спам, при условии, что оно содержит N-е слово (к примеру, «home»).

(Demonstration:)

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

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

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

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

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

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

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

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

Смешанные методыПравить

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

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

$p=C^{-<!--\; -\; -->1}(-<!--\; -\; -->2\ln <!--\; \; -->(p_1{p}_2\cdots <!--\; \cdots \; -->p_N),2N)$$p=C^{-1}(-2\ln(p_{1}p_{2}\cdots p_{N}),2N)$ 

где через C⁻¹ обозначена обратная функция для функции распределения хи-квадрат (см. Обратное распределение хи-квадрат^[en]).

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

ХарактеристикаПравить

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

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

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

См. такжеПравить

• Байесовское программирование

ЛитератураПравить

• 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 // Персональный сайт Пола Грэхема.