Наивный Байес, или о том, как математика позволяет фильтровать спам

МЕНЮ


Искусственный интеллект. Новости
Поиск
Регистрация на сайте
Сбор средств на аренду сервера для ai-news

ТЕМЫ


Новости ИИРазработка ИИРабота разума и сознаниеВнедрение ИИРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информации

Авторизация



RSS


RSS новости

Новостная лента форума ailab.ru

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

image

Без формул никуда, ну и краткая теория

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

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

$argmax[P(Q_k)prod_{i=1}^nP(x_i|Q_k)]$

$P(Q_k)=cfrac{	ext{число документов класса $Q_k$}}{	ext{общее количество документов}}$ $P(x_i|Q_k)=cfrac{alpha+N_{ik}}{alpha M+N_k}$ — вхождение слова $x_i$ в документ класса $Q_k$ (со сглаживанием)*
$N_k$ — количество слов входящих в документ класса $Q_k$
М — количество слов из обучающей выборки
$N_{ik}$ — количество вхождений слова $x_i$ в документ класса $Q_k$
$alpha$ — параметр для сглаживания

Когда объем текста очень большой, приходится работать с очень маленькими числами. Для того чтобы этого избежать, можно преобразовать формулу по свойству логарифма**:

$log{ab}=log{a}+log{b}$

Подставляем и получаем:

$argmax[log{P(Q_k)}+sum_{i=1}^nlog{P(x_i|Q_k)}]$

*Во время выполнения подсчетов вам может встретиться слово, которого не было на этапе обучения системы. Это может привести к тому, что оценка будет равна нулю и документ нельзя будет отнести ни в одну из категорий (спам/не спам). Как бы вы не хотели, вы не обучите свою систему всем возможным словам. Для этого необходимо применить сглаживание, а точнее – сделать небольшие поправки во все вероятности вхождения слов в документ. Выбирается параметр 0<??1 (если ?=1, то это сглаживание Лапласа)

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

От теории к практике

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

Спам:

  • «Путевки по низкой цене»
  • «Акция! Купи шоколадку и получи телефон в подарок»

Не спам:

  • «Завтра состоится собрание»
  • «Купи килограмм яблок и шоколадку»

Задание: определить, к какой категории отнести следующее письмо:

  • «В магазине гора яблок. Купи семь килограмм и шоколадку»

Решение:

Составляем таблицу. Убираем все «стоп-слова», рассчитываем вероятности, параметр для сглаживания принимаем за единицу.

image
Оценка для категории «Спам»:

$frac{2}{4}cdotfrac{2}{23}cdotfrac{2}{23}cdotfrac{1}{23}cdotfrac{1}{23}cdotfrac{1}{23}cdotfrac{1}{23}cdotfrac{1}{23}approx0,000000000587 (	ext{или 5,87E-10})$

Оценка для категории «Не спам»:

$frac{2}{4}cdotfrac{2}{21}cdotfrac{2}{21}cdotfrac{2}{21}cdotfrac{2}{21}cdotfrac{1}{21}cdotfrac{1}{21}cdotfrac{1}{21}approx0,00000000444 (	ext{или 4,44E-9})$

Ответ: оценка «Не спам» больше оценки «Спам». Значит проверочное письмо — не спам!

То же самое рассчитаем и с помощью функции, преобразованной по свойству логарифма:
Оценка для категории «Спам»:

$log{frac{2}{4}}+log{frac{2}{23}}+log{frac{2}{23}}+log{frac{1}{23}}+log{frac{1}{23}}+log{frac{1}{23}}+log{frac{1}{23}}+log{frac{1}{23}}approx-21,25$

Оценка для категории «Не спам»:

$log{frac{2}{4}}+log{frac{2}{21}}+log{frac{2}{21}}+log{frac{2}{21}}+log{frac{2}{21}}+log{frac{1}{21}}+log{frac{1}{21}}+log{frac{1}{21}}approx-19,23$

Ответ: аналогично предыдущему ответу. Проверочное письмо – не спам!

Реализация на языке программирования R

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

А тут, собственно, и сам код

library("tm")         #Библиотека для stopwords library("stringr")    #Библиотека для работы со строками  #Обучаюшая выборка со спам письмами: spam <- c(   'Путевки по низкой цене',   'Акция! Купи шоколадку и получи телефон в подарок' )  #Обучающая выборка с не спам письмами: not_spam <- c(   'Завтра состоится собрание',   'Купи килограмм яблок и шоколадку' )  #Письмо требующее проверки test_letter <- "В магазине гора яблок. Купи семь килограмм и шоколадку"  #----------------Для спама-------------------- #Убираем все знаки препинания spam <- str_replace_all(spam, "[[:punct:]]", "")  #Делаем все маленьким регистром spam <- tolower(spam)  #Разбиваем слова по пробелу spam_words <- unlist(strsplit(spam, " "))  #Убираем слова, которые совпадают со словами из stopwords spam_words  <- spam_words[! spam_words %in% stopwords("ru")]  #Создаем таблицу с уникальными словами и их количеством unique_words <- table(spam_words)  #Создаем data frame main_table <- data.frame(u_words=unique_words)  #Переименовываем столбцы names(main_table) <- c("Слова","Спам")  #---------------Для не спама------------------ not_spam <- str_replace_all(not_spam, "[[:punct:]]", "") not_spam <- tolower(not_spam) not_spam_words <- unlist(strsplit(not_spam, " ")) not_spam_words  <- not_spam_words[! not_spam_words %in% stopwords("ru")]  #---------------Для проверки------------------ test_letter <- str_replace_all(test_letter, "[[:punct:]]", "") test_letter <- tolower(test_letter) test_letter <- unlist(strsplit(test_letter, " ")) test_letter <- test_letter[! test_letter %in% stopwords("ru")] #---------------------------------------------  #Создаем новый столбик для подсчета не спам писем main_table$Не_спам <- 0   for(i in 1:length(not_spam_words)){ #Создаем логическую переменную   need_word <- TRUE   for(j in 1:(nrow(main_table))){ #Если "не спам" слово существует, то к счетчику уникальных слов +1     if(not_spam_words[i]==main_table[j,1])                            {       main_table$Не_спам[j] <- main_table$Не_спам[j]+1       need_word <- FALSE     }   } #Если слово не встречалось еще, то добавляем его в конец data frame и создаем счетчики   if(need_word==TRUE)   {     main_table <- rbind(main_table,data.frame(Слова=not_spam_words[i],Спам=0,Не_спам=1))   } }  #------------- #Создаем столбик содержащий вероятности того, что выбранное слово - спам main_table$Вероятность_спам <- NA  #Создаем столбик содержащий вероятности того, что выбранное слово - не спам main_table$Вероятность_не_спам <- NA  #------------- #Создаем функцию подсчета вероятности вхождения слова Xi в документ класса Qk formula_1 <- function(N_ik,M,N_k) {                                                                (1+N_ik)/(M+N_k) } #-------------  #Считаем количество слов из обучающей выборки quantity <- nrow(main_table)  for(i in 1:length(test_letter)) { #Используем ту же логическую переменную, чтобы не создавать новую   need_word <- TRUE                                              for(j in 1:nrow(main_table))   { #Если слово из проверочного письма уже существует в нашей выборке то считаем вероятность каждой категории     if(test_letter[i]==main_table$Слова[j])     {       main_table$Вероятность_спам[j] <- formula_1(main_table$Спам[j],quantity,sum(main_table$Спам))       main_table$Вероятность_не_спам[j] <- formula_1(main_table$Не_спам[j],quantity,sum(main_table$Не_спам))       need_word <- FALSE     }   } #Если слова нет, то добавляем его в конец data frame, и считаем вероятность спама/не спама   if(need_word==TRUE)   {     main_table <- rbind(main_table,data.frame(Слова=test_letter[i],Спам=0,Не_спам=0,Вероятность_спам=NA,Вероятность_не_спам=NA))     main_table$Вероятность_спам[nrow(main_table)] <- formula_1(main_table$Спам[nrow(main_table)],quantity,sum(main_table$Спам))     main_table$Вероятность_не_спам[nrow(main_table)] <- formula_1(main_table$Не_спам[nrow(main_table)],quantity,sum(main_table$Не_спам))   } }  #Переменная для подсчета оценки класса "Спам" probability_spam <- 1  #Переменная для подсчета оценки класса "Не спам" probability_not_spam <- 1  for(i in 1:nrow(main_table)) {   if(!is.na(main_table$Вероятность_спам[i]))   { #Шаг 1.1 Определяем оценку того, что письмо - спам     probability_spam <- probability_spam * main_table$Вероятность_спам[i]   }   if(!is.na(main_table$Вероятность_не_спам[i]))   { #Шаг 1.2 Определяем оценку того, что письмо - не спам     probability_not_spam <- probability_not_spam * main_table$Вероятность_не_спам[i]        } }  #Шаг 2.1 Определяем оценку того, что письмо - спам probability_spam <- (length(spam)/(length(spam)+length(not_spam)))*probability_spam  #Шаг 2.2 Определяем оценку того, что письмо - не спам probability_not_spam <- (length(not_spam)/(length(spam)+length(not_spam)))*probability_not_spam    #Чья оценка больше - тот и победил ifelse(probability_spam>probability_not_spam,"Это сообщение - спам!","Это сообщение - не спам!") 
Спасибо большое за потраченное время на чтение моей статьи. Надеюсь, Вы узнали для себя что-то новое, или просто пролили свет на непонятные для Вас моменты. Удачи! Источники:
  1. Очень хорошая статья о наивном бейесовском классификаторе
  2. Черпал знания из Wiki: тут, тут, и тут
  3. Лекции по Data Mining Чубуковой И.А.

Источник: habr.com



Поддержи проект ai-news рублем. Машины верят в тебя! >>



Комментарии: