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

Методика фильтрации спама в электронной почте

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

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

Фильтрация спама Naive Bayes — это базовый метод борьбы со спамом, который может адаптироваться к потребностям отдельных пользователей электронной почты и обеспечивать низкие показатели ложного срабатывания спама, которые в целом приемлемы для пользователей. Это один из старейших способов фильтрации спама, корни которого уходят в 1990-е годы.

История

Байесовские алгоритмы использовались для фильтрации электронной почты еще в 1996 году. Хотя наивные байесовские фильтры стали популярными лишь позднее, в 1998 году было выпущено несколько программ для решения растущей проблемы нежелательной электронной почты. ^[1] Первая научная публикация по байесовской фильтрации спама была опубликована Сахами и др. в 1998 году. ^[2]

Варианты базовой техники были реализованы в ряде исследовательских работ и коммерческих программных продуктов. ^[3] Многие современные почтовые клиенты реализуют байесовскую фильтрацию спама. Пользователи также могут устанавливать отдельные программы фильтрации электронной почты . Серверные фильтры электронной почты, такие как DSPAM, SpamAssassin , ^[4] SpamBayes , ^[5] Bogofilter и ASSP , используют байесовские методы фильтрации спама, и эта функциональность иногда встроена в само программное обеспечение почтового сервера . CRM114 , часто упоминаемый как байесовский фильтр, не предназначен для использования байесовского фильтра в производстве, но включает в себя функцию ″unigram″ для справки. ^[6]

Процесс

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

После обучения вероятности слов (также известные как функции правдоподобия ) используются для вычисления вероятности того, что электронное письмо с определенным набором слов в нем принадлежит к той или иной категории. Каждое слово в электронном письме вносит вклад в вероятность спама электронного письма или только самые интересные слова. Этот вклад называется апостериорной вероятностью и вычисляется с помощью теоремы Байеса . Затем вероятность спама электронного письма вычисляется по всем словам в электронном письме, и если общее значение превышает определенный порог (например, 95%), фильтр помечает электронное письмо как спам.

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

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

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

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

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

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

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

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

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

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

где:

• ${\displaystyle \Pr(S|W)}$вероятность того, что сообщение является спамом, зная, что в нем есть слово «реплика»;
• ${\displaystyle \Pr(S)}$общая вероятность того, что данное сообщение является спамом;
• ${\displaystyle \Pr(W|S)}$вероятность появления слова «реплика» в спам-сообщениях;
• ${\displaystyle \Pr(H)}$общая вероятность того, что данное сообщение не является спамом (является «не спамом»);
• ${\displaystyle \Pr(W|H)}$вероятность того, что слово «реплика» появится в любительских сообщениях.

(Для полной демонстрации см. теорему Байеса#Расширенная форма .)

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

Статистика ^[7] показывает, что в настоящее время вероятность того, что любое сообщение является спамом, составляет не менее 80%:

${\displaystyle \Pr(S)=0.8;\Pr(H)=0.2}$

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

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

Это функционально эквивалентно вопросу «какой процент появлений слова «реплика» встречается в спам-сообщениях?»

Эта величина называется «спамичностью» (или «спаминостью») слова «реплика» и может быть вычислена. Число, используемое в этой формуле, аппроксимируется частотой сообщений, содержащих «реплику», в сообщениях, идентифицированных как спам во время фазы обучения. Аналогично аппроксимируется частотой сообщений, содержащих «реплику», в сообщениях, идентифицированных как не спам во время фазы обучения. Чтобы эти аппроксимации имели смысл, набор изученных сообщений должен быть достаточно большим и репрезентативным. Также желательно, чтобы изученный набор сообщений соответствовал 50%-ной гипотезе о перераспределении между спамом и не спамом, т. е. чтобы наборы данных спама и не спама были одинакового размера. ^[8] ${\displaystyle \Pr(W|S)}$ ${\displaystyle \Pr(W|H)}$

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

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

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

${\displaystyle 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})}}}$

где:

• ${\displaystyle p}$вероятность того, что подозрительное сообщение является спамом;
• ${\displaystyle p_{1}}$вероятность появления первого слова (например, «реплика»), при условии, что сообщение является спамом; ${\displaystyle p(W_{1}|S)}$
• ${\displaystyle p_{2}}$вероятность появления второго слова (например, «часы»), при условии, что сообщение является спамом; ${\displaystyle p(W_{2}|S)}$
• и т. д...

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

Другое выражение формулы для объединения индивидуальных вероятностей

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

${\displaystyle {\frac {1}{p}}-1={\frac {(1-p_{1})(1-p_{2})\dots (1-p_{N})}{p_{1}p_{2}\dots p_{N}}}}$

Ведение журналов с обеих сторон:

${\displaystyle \ln \left({\frac {1}{p}}-1\right)=\sum _{i=1}^{N}\left[\ln(1-p_{i})-\ln p_{i}\right]}$

Пусть . Следовательно, ${\displaystyle \eta =\sum _{i=1}^{N}\left[\ln(1-p_{i})-\ln p_{i}\right]}$

${\displaystyle {\frac {1}{p}}-1=e^{\eta }}$

Отсюда альтернативная формула для вычисления объединенной вероятности:

${\displaystyle p={\frac {1}{1+e^{\eta }}}}$

Работа с редкими словами

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

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

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

${\displaystyle \Pr '(S|W)={\frac {s\cdot \Pr(S)+n\cdot \Pr(S|W)}{s+n}}}$

где:

• ${\displaystyle \Pr '(S|W)}$— скорректированная вероятность того, что сообщение является спамом, при наличии в нем заданного слова;
• ${\displaystyle s}$насколько большое значение мы придаем справочной информации о входящем спаме;
• ${\displaystyle \Pr(S)}$вероятность того, что любое входящее сообщение окажется спамом;
• ${\displaystyle n}$количество появлений этого слова на этапе обучения;
• ${\displaystyle \Pr(S|W)}$спамность этого слова.

(Демонстрация: ^[9] )

Эта скорректированная вероятность используется вместо спамности в формуле объединения.

Эту формулу можно распространить на случай, когда n равно нулю (и когда спамность не определена), и в этом случае она оценивается как . ${\displaystyle Pr(S)}$

Другие эвристики

«Нейтральные» слова, такие как «the», «a», «some» или «is» (в английском языке) или их эквиваленты в других языках, можно игнорировать. Они также известны как стоп-слова . В более общем смысле некоторые фильтры байесовской фильтрации просто игнорируют все слова, которые имеют спамность около 0,5, поскольку они мало способствуют принятию правильного решения. Принимаются во внимание слова, чья спамность около 0,0 (отличительные признаки законных сообщений) или около 1,0 (отличительные признаки спама). Метод может заключаться, например, в том, чтобы оставить только те десять слов в проверенном сообщении, которые имеют наибольшее абсолютное значение  |0,5 −  pI |.

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

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

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

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

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

${\displaystyle p=C^{-1}(-2\ln(p_{1}p_{2}\cdots p_{N}),2N)\,}$

где C ⁻¹ — обратная функция хи-квадрат .

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

Обсуждение

Преимущества

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

Законные электронные письма, которые получает пользователь, будут, как правило, отличаться. Например, в корпоративной среде название компании и имена клиентов или заказчиков будут упоминаться часто. Фильтр будет присваивать более низкую вероятность спама письмам, содержащим эти имена.

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

Недостатки

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

Слова, которые обычно появляются в спаме в больших количествах, также могут быть преобразованы спамерами. Например, «Viagra» будет заменено на «Viaagra» или «V!agra» в спам-сообщении. Получатель сообщения все еще может прочитать измененные слова, но каждое из этих слов встречается байесовским фильтром реже, что затрудняет его процесс обучения. Как правило, этот метод спама работает не очень хорошо, потому что полученные слова в конечном итоге распознаются фильтром так же, как и обычные. ^[12]

Другой метод, используемый для попытки обойти байесовские спам-фильтры, заключается в замене текста картинками, либо напрямую включенными, либо связанными. Весь текст сообщения или его часть заменяется картинкой, на которой «нарисован» тот же текст. Спам-фильтр обычно не может проанализировать эту картинку, которая может содержать такие чувствительные слова, как «Виагра». Однако, поскольку многие почтовые клиенты отключают отображение связанных картинок по соображениям безопасности, спамер, отправляющий ссылки на удаленные картинки, может достичь меньшего количества целей. Кроме того, размер картинки в байтах больше, чем размер эквивалентного текста, поэтому спамеру требуется большая пропускная способность для отправки сообщений напрямую, включающих картинки. Некоторые фильтры более склонны считать сообщение спамом, если оно имеет в основном графическое содержимое. Решение, используемое Google в своей системе электронной почты Gmail , заключается в выполнении OCR (оптического распознавания символов) на каждом изображении среднего и большого размера с анализом текста внутри. ^{[13] [14]}

Общие применения байесовской фильтрации

Хотя байесовская фильтрация широко используется для идентификации спама, эта техника может классифицировать (или «кластеризовать») практически любые данные. Она применяется в науке, медицине и технике. Одним из примеров является универсальная программа классификации под названием AutoClass, которая изначально использовалась для классификации звезд в соответствии со спектральными характеристиками, которые в противном случае были бы слишком тонкими, чтобы их заметить. ^[15]

Смотрите также

• Методы борьбы со спамом
• Байесовское отравление
• Фильтрация электронной почты
• Марковская дискриминация
• Почтовый клиент Mozilla Thunderbird с собственной реализацией фильтров Байеса ^{[16] [17]}

Ссылки

1. Брантон, Финн (2013). Спам: теневая история Интернета. MIT Press . стр. 136. ISBN 9780262018876. Архивировано из оригинала 2019-03-23 ​​. Получено 2017-09-13 .
2. M. Sahami; S. Dumais; D. Heckerman; E. Horvitz (1998). "Байесовский подход к фильтрации нежелательной электронной почты" (PDF) . Семинар AAAI'98 по обучению категоризации текста. Архивировано (PDF) из оригинала 27-09-2007 . Получено 15-08-2007 .
3. "Junk Mail Controls". MozillaZine. Ноябрь 2009. Архивировано из оригинала 2012-10-23 . Получено 2010-01-16 .
4. "Установка". Руководства Ubuntu. 2010-09-18. Архивировано из оригинала 29 сентября 2010 г. Получено 2010-09-18 . f(x) Гэри Робинсона и алгоритмы комбинирования, используемые в SpamAssassin
5. "Background Reading". Проект SpamBayes. 2010-09-18. Архивировано из оригинала 6 сентября 2010 г. Получено 2010-09-18 . Точите карандаши, это математическая основа (какая она есть).* Статья, с которой все началось: A Plan for Spam Пола Грэма.* У Гэри Робинсона есть интересное эссе, предлагающее некоторые улучшения оригинального подхода Грэма.* Статья Гэри Робинсона в Linux Journal обсуждает использование распределения хи-квадрат.
6. "Архивная копия". Архивировано из оригинала 2016-10-07 . Получено 2016-07-09 .{{cite web}}: CS1 maint: archived copy as title (link)
7. Дилан Морс и Дермот Харнетт (2009). "State of Spam, a Monthly Report - Report #33" (PDF) . Архивировано из оригинала (PDF) 2009-10-07 . Получено 2009-12-30 .
8. Process Software, Введение в байесовскую фильтрацию Архивировано 06.02.2012 на Wayback Machine
9. Гэри Робинсон (2003). "Статистический подход к проблеме спама". Linux Journal . Архивировано из оригинала 2010-10-22 . Получено 2007-07-19 .
10. Брайан Бертон (2003). "SpamProbe - байесовские настройки фильтрации спама". Архивировано из оригинала 2012-03-01 . Получено 2009-01-19 .
11. Джонатан А. Здзярски (2004). «Байесовское шумоподавление: контекстная логика симметрии, использующая анализ согласованности образов».^{[ постоянная мертвая ссылка ]}
12. Пол Грэм (2002), План по борьбе со спамом. Архивировано 04.04.2004 на Wayback Machine.
13. "Gmail использует инновационную технологию Google, чтобы не допустить попадания спама в ваш почтовый ящик". Архивировано из оригинала 2015-09-13 . Получено 2015-09-05 .
14. Чжу, З.; Цзя, З.; Сяо, Х; Чжан, Г; Лян, Х.; Ван, П. (2014). Ли, С; Цзинь, К; Цзян, Х; Парк, Дж (ред.). «Модифицированный минимальный риск Байеса и его [sic] применение в спаме». Конспект лекций по электротехнике . 269. Дордрехт: Springer: 2155–2159. doi :10.1007/978-94-007-7618-0_261.
15. Androutsopoulos, Ion; Paliouras, Georgios; Karkaletsis, Vangelis; Sakkis, Georgios; Spyropoulos, Constantine D.; Stamatopoulos, Panagiotis (2000). Gallinari, P; Rajman, M; Zaragoza, H (ред.). «Обучение фильтрации спама по электронной почте: сравнение наивного байесовского подхода и подхода, основанного на памяти». 4-я Европейская конференция по принципам и практике обнаружения знаний в базах данных (PKDD-2000) . Лион, Франция: Лаборатория разработки программного обеспечения и знаний Института информатики и телекоммуникаций Национального центра научных исследований «Демокритос»: 1–13. arXiv : cs/0009009 . Bibcode :2000cs........9009A.
16. Христеа, Флорентина Т. (2013). Наивная байесовская модель для неконтролируемого разрешения неоднозначности смысла слов . Лондон; Берлин: Springer-Verlag Heidelberg Berlin. стр. 70. ISBN 978-3-642-33692-8.
17. Zheng, J.; Tang, Yongchuan (2005). "Одно обобщение наивного байесовского метода для нечетких множеств и разработка нечеткого наивного байесовского классификатора". В Mira, Jose; Álvarez, Jose R (ред.). Искусственный интеллект и приложения для инженерии знаний: биоинспирированный подход . Lecture Notes in Computer Science. Vol. 3562. Berlin: Springer, Berlin, Heidelberg. p. 281. doi :10.1007/11499305_29. ISBN 978-3-540-26319-7. ISSN  0302-9743.