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

редактировать

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

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

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

Содержание
  • 1 История
  • 2 Процесс
  • 3 Математическая основа
    • 3.1 Расчет вероятности того, что сообщение, содержащее данное слово, является спамом
    • 3.2 Спамность слова
    • 3.3 Объединение индивидуальные вероятности
    • 3.4 Другое выражение формулы для объединения индивидуальных вероятностей
    • 3.5 Работа с редкими словами
    • 3.6 Другая эвристика
    • 3.7 Смешанные методы
  • 4 Обсуждение
    • 4.1 Преимущества
    • 4.2 Недостатки
  • 5 Общие приложения байесовской фильтрации
  • 6 См. Также
  • 7 Ссылки
История

К 1996 году для сортировки и фильтрации электронной почты использовались байесовские алгоритмы. Хотя наивные байесовские фильтры не стали популярными до тех пор, пока в 1998 году не было выпущено несколько программ для решения растущей проблемы нежелательной электронной почты. Первая научная публикация по байесовской фильтрации спама была написана Sahami et al. в 1998 году. Вскоре после этого эта работа была развернута в коммерческих фильтрах спама. Однако в 2002 году Пол Грэм значительно снизил частоту ложных срабатываний, так что его можно было использовать самостоятельно в качестве единого спам-фильтра.

Варианты базовой техники были реализованы в количество исследовательских работ и коммерческих программных продуктов. Многие современные почтовые клиенты реализуют байесовскую фильтрацию спама. Пользователи также могут установить отдельные программы фильтрации электронной почты. Серверные фильтры электронной почты, такие как DSPAM, SpamAssassin, SpamBayes, Bogofilter и ASSP, используют байесовские методы фильтрации спама, а функциональность иногда встроена в само программное обеспечение почтового сервера. CRM114, часто упоминаемый как байесовский фильтр, не предназначен для использования байесовского фильтра в производстве, но включает функцию «униграмма» для справки.

Процесс

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

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

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

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

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

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

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

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

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

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

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

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

где:

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

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

Спамлин ess of a word

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

Pr (S) = 0,8; Pr (H) = 0,2 {\ displaystyle \ Pr (S) = 0,8; \ Pr (H) = 0,2}\ Pr (S) = 0,8; \ Pr (H) = 0,2

Однако большинство байесовских программ для обнаружения спама предполагает, что нет никаких априорных причин, по которым входящее сообщение быть спамом, а не ветчиной, и считает, что оба случая имеют равные вероятности 50%:

Pr (S) = 0,5; Pr (H) = 0,5 {\ displaystyle \ Pr (S) = 0,5; \ Pr (H) = 0,5}\ Pr (S) = 0,5; \ Pr (H) = 0,5

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

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

Это функционально эквивалентно вопросу, "какой процент вхождений слова" реплики "появляться в спам-сообщениях?"

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

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

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

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

p = p 1 p 2 ⋯ p N p 1 p 2 ⋯ p N + (1 - p 1) (1 - p 2) ⋯ (1 - p N) {\ 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})}}}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 {\ displaystyle p}p - вероятность того, что подозрительное сообщение - спам;
  • p 1 {\ displaystyle p_ {1}}p_ {1} - вероятность p (S | W 1) {\ displaystyle p (S | W_ {1})}p (S | W_ {1}) , что это спам, если он содержит первое слово (например, «реплика»);
  • p 2 {\ displaystyle p_ {2}}p_ {2} - вероятность p ( S | W 2) {\ displaystyle p (S | W_ {2})}p (S | W_ {2}) , что это спам, если он содержит второе слово (например, «часы»);
  • и т. Д....
  • p N {\ displaystyle p_ {N}}p_ {N} - вероятность p (S | WN) {\ displaystyle p (S | W_ {N})}p (S | W_ {N}) , что это спам, если он содержит N-е слово (например, «дом»).

Это формула, на которую ссылается Пол Грэм в его август 2002, статья. Некоторые ранние комментаторы заявляли, что «Грэм извлек свои формулы из воздуха», но Грэм фактически сослался на свой источник, который включал подробное объяснение формулы и идеализации, на которых она основана.

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

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

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

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

Взятие бревен с обеих сторон:

ln ⁡ (1 p - 1) = ∑ i = 1 N [ln ⁡ (1 - pi) - пер ⁡ пи] {\ Displaystyle \ пер \ влево ({\ гидроразрыва {1} {р}} - 1 \ вправо) = \ сумма _ {я = 1} ^ {N} \ влево [\ ln (1- p_ {i}) - \ ln p_ {i} \ right]}\ ln \ left ({\ frac {1} {p}} - 1 \ right) = \ sum _ {{i = 1}} ^ {N} \ left [\ ln (1-p_ {i}) - \ ln p_ {i} \ right]

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

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

Следовательно, альтернативная формула для вычисления комбинированной вероятности:

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

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

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

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

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

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

где:

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

(Демонстрация :)

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

Pr (S) {\ displaystyle \ Pr (S)}\ Pr (S) снова можно принять равным 0,5, чтобы не слишком подозрительно относиться к входящей электронной почте. 3 - хорошее значение для s, означающее, что изученный корпус должен содержать более 3 сообщений с этим словом, чтобы больше доверять значению спамности, чем значению по умолчанию.

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

Другая эвристика

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

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

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

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

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

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

p = C - 1 (- 2 ln ⁡ (п 1 п 2 ⋯ п N), 2 N) {\ Displaystyle р = C ^ {- 1} (- 2 \ ln (p_ {1} p_ {2} \ cdots p_ {N}), 2N) \, }p = C ^ {{- 1}} (- 2 \ ln (p_ {1} p_ {2 } \ cdots p_ {N}), 2N) \,

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

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

Обсуждение

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

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

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

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

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

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

Недостатки

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

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

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

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

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

См. Также
Ссылки
Последняя правка сделана 2021-05-31 08:33:49
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте