Jump to content

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где:

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

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

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

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

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

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

Функционально это эквивалентно вопросу: «Какой процент вхождений слова «реплика» встречается в спам-сообщениях?»

Эта величина называется «спамичностью» (или «спамностью») слова «реплика» и может быть вычислена. Число Используемая в этой формуле аппроксимируется частотой сообщений, содержащих «реплику» в сообщениях, идентифицированных как спам на этапе обучения. Сходным образом, аппроксимируется частотой сообщений, содержащих «реплику» в сообщениях, идентифицированных как нежелательные на этапе обучения. Чтобы эти приближения имели смысл, набор усвоенных сообщений должен быть большим и достаточно репрезентативным. Также желательно, чтобы изученный набор сообщений соответствовал 50%-ной гипотезе о перераспределении между спамом и ветчиной, т.е. чтобы наборы данных спама и ветчины имели одинаковый размер. [8]

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

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

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

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

где:

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

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

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

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

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

Берем бревна с обеих сторон:

Позволять . Поэтому,

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

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

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

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

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

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

где:

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

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

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

Эту формулу можно распространить на случай, когда n равно нулю (и спачность не определена), и в этом случае ее значение равно .

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

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

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

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

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

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

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

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

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

где С −1 является обратной функцией хи-квадрат .

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

Обсуждение

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

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

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

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

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

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

Недостатки

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

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

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

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

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

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

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

См. также

[ редактировать ]
  1. ^ Брантон, Финн (2013). Спам: теневая история Интернета . МТИ Пресс . п. 136. ИСБН  9780262018876 . Архивировано из оригинала 23 марта 2019 г. Проверено 13 сентября 2017 г.
  2. ^ М. Сахами; С. Дюмэ; Д. Хекерман; Э. Хорвиц (1998). «Байесовский подход к фильтрации нежелательной почты» (PDF) . Семинар AAAI'98 по обучению категоризации текста. Архивировано (PDF) из оригинала 27 сентября 2007 г. Проверено 15 августа 2007 г.
  3. ^ «Контроль нежелательной почты» . МозиллаЗин. Ноябрь 2009 г. Архивировано из оригинала 23 октября 2012 г. Проверено 16 января 2010 г.
  4. ^ «Установка» . Руководства по Ubuntu. 18 сентября 2010 г. Архивировано из оригинала 29 сентября 2010 года . Проверено 18 сентября 2010 г. f(x) Гэри Робинсона и алгоритмы комбинирования, используемые в SpamAssassin
  5. ^ «Фоновое чтение» . Проект SpamBayes. 18 сентября 2010 г. Архивировано из оригинала 6 сентября 2010 года . Проверено 18 сентября 2010 г. Заточите карандаши, это математическая основа (такая, какая она есть).* Статья, с которой дело пошло: «План борьбы со спамом» Пола Грэма.* У Гэри Робинсона есть интересное эссе, предлагающее некоторые усовершенствования оригинального подхода Грэма.* Гэри Робинсон В статье Linux Journal обсуждается использование распределения хи-квадрат.
  6. ^ «Архивная копия» . Архивировано из оригинала 07.10.2016 . Проверено 9 июля 2016 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
  7. ^ Дилан Морс и Дермот Харнетт (2009). «Состояние спама, ежемесячный отчет — отчет № 33» (PDF) . Архивировано из оригинала (PDF) 7 октября 2009 г. Проверено 30 декабря 2009 г.
  8. ^ Программное обеспечение процесса, Введение в байесовскую фильтрацию. Архивировано 6 февраля 2012 г. на Wayback Machine.
  9. ^ Гэри Робинсон (2003). «Статистический подход к проблеме спама» . Linux-журнал . Архивировано из оригинала 22 октября 2010 г. Проверено 19 июля 2007 г.
  10. ^ Брайан Бертон (2003). «SpamProbe — настройки байесовской фильтрации спама» . Архивировано из оригинала 1 марта 2012 г. Проверено 19 января 2009 г.
  11. ^ Джонатан А. Здзиарски (2004). «Байесовское шумоподавление: логика контекстной симметрии с использованием анализа согласованности шаблонов» . [ постоянная мертвая ссылка ]
  12. ^ Пол Грэм (2002), План борьбы со спамом. Архивировано 4 апреля 2004 г. в Wayback Machine.
  13. ^ «Gmail использует инновационную технологию Google для предотвращения попадания спама в ваш почтовый ящик» . Архивировано из оригинала 13 сентября 2015 г. Проверено 5 сентября 2015 г.
  14. ^ Чжу, З.; Цзя, З; Сяо, Х; Чжан, Г; Лян, Х.; Ван, П. (2014). Ли, С ; Джин, Кью; Цзян, X; Парк, Дж. (ред.). «Модифицированный байесовский метод минимального риска и его [sic] применение в спаме». Конспект лекций по электротехнике . 269 ​​. Дордрехт: Спрингер: 2155–2159. дои : 10.1007/978-94-007-7618-0_261 .
  15. ^ Андрутсопулос, Ион; Палиурас, Георгиос; Каркалецис, Вангелис; Саккис, Георгиос; Спиропулос, Константин Д.; Стаматопулос, Панайотис (2000). Галлинари, П ; Раджман, М; Сарагоса, Х. (ред.). «Учимся фильтровать спам по электронной почте: сравнение наивного байесовского подхода и подхода, основанного на памяти». 4-я Европейская конференция по принципам и практике обнаружения знаний в базах данных (PKDD-2000) . Лион, Франция: Лаборатория программного обеспечения и инженерии знаний Института информатики и телекоммуникаций, Национальный центр научных исследований «Демокритос»: 1–13. arXiv : cs/0009009 . Бибкод : 2000cs........9009A .
  16. ^ Христеа, Флорентина Т. (2013). Наивная байесовская модель для неконтролируемого устранения неоднозначности смысла слов . Лондон; Берлин: Springer-Verlag Heidelberg Berlin. п. 70. ИСБН  978-3-642-33692-8 .
  17. ^ Чжэн, Дж.; Тан, Юнчуань (2005). «Одно обобщение наивного байесовского классификатора на нечеткие множества и конструкция нечеткого наивного байесовского классификатора». В Мире, Хосе; Альварес, Хосе Р. (ред.). Приложения искусственного интеллекта и инженерии знаний: биоинспирированный подход . Конспекты лекций по информатике. Том. 3562. Берлин: Шпрингер, Берлин, Гейдельберг. п. 281. дои : 10.1007/11499305_29 . ISBN  978-3-540-26319-7 . ISSN   0302-9743 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 853b22624227f68e323b447aa0abd89b__1719400020
URL1:https://arc.ask3.ru/arc/aa/85/9b/853b22624227f68e323b447aa0abd89b.html
Заголовок, (Title) документа по адресу, URL1:
Naive Bayes spam filtering - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)