Теоремы Байеса - наивный байесовский классификатор
Введение
Вероятность - это численная мера степени объективной возможности наступления случайного события. Она может быть равна значению от 0 до 1. Она также приближенно выражена посредством пропорции числа случаев на протяжении всего эксперимента. Если вероятность события равна нулю, то тогда мы уверены что оно не произойдет. Тем не менее, если она равна 1, событие обязательно произойдет. Вероятность равная 0.5 означает, что наше сомнение по поводу происхождения события максимально.
Следующая часть описывает некоторые базовые формулы подсчета вероятности, которые будут использованы.
Условная вероятность - вероятность происхождения события может зависеть от происхождения или непроисхождения другого события. Данная зависимость записывается в следующей форме:
P(A|B)
“Вероятность того, что A произойдет, при условии что произошло B” или “вероятность выбора A среди B”
Заметьте, что B известно раньше и мы можем увидеть пропорцию A среди B при помощи:
Учитывая указанную выше формулу, событие A является Независимым от события B в том случае, если условная вероятность является такой же, как безусловная вероятность.
P(B|A) = P(B)
P(A|B) = P(A)
Теорема Байеса учитывает априорную вероятность - безусловная вероятность гипотез до того, как известные данные о Новых очевидностях. Проще говоря, состояние знаний должно быть раньше, чем данные будут обследованы.
Также учитывается и апостериорная вероятность - условная вероятность гипотез (наше состояние знаний) после того, как мы провели исследование на основе новых данных.
Вероятность происхождения - это условная вероятность, основанная на данных наших наблюдений при существующих гипотезах.
Теорема Байеса :
Бéйес (Байес) Томас (1702 – 1761) - английский математик, член Лондонского королевского общества (1742). Основные труды относятся к теории вероятностей; в частности, Бейес поставил и решил одну из основных задач элементарной теории вероятностей (Теорема Байеса).
Далее мы представим математический формализм и пример фильтрации спама, но учитывая основную идею.
Байессовский классификатор использует теорему Байеса, которая гласит следующее:
Учитывая каждый атрибут и класс в качестве случайной переменной и имея записи с атрибутами (A1,A2,…, An), целью является предсказание класса C. В частности, мы хотим найти значение C, которое максимизирует P(C| A1,A2,…An).
Принятый подход вычисляет апостериорную вероятность P(C| A1,A2,…An) для всех значений C используя теорему Байеса.
Итак, мы выбираем значение C, которое максимизирует P(C| A1,A2,…An). Это равно выбору значения C, которое максимизирует P(A1,A2,…An | C) P(C).
Чтобы упростить задачу наивного байесовского классификатора, мы предполагаем, что атрибуты имеют независимые распределения.
Теорема Байеса имеет следующие преимущества и недостатки:
Преимущества:
- Обработка количественных и дискретных данных
- Устойчивые и изолированные точки шума
- Обработка отсутствующих значений путем их игнорирования
- Прогноз подсчетов во время вычисления вероятности
- Быстрота и эффективность относительно пространствва
- Отсутствие чувствительности к посторонним функциям
- Квадратическая граница решений
Недостатки:
- В случае, когда условная вероятность равна нулю.
- Предполагает независимость функций
Предсказание на основе теоремы Байеса требует неравенства нулю каждой условной вероятности. В противном случае, предсказанная вероятность будет равна нулю.
Для преодоления этого мы используем один из прогнозов вероятности:
В данную статью не входит описание данных прогнозов.
Программа
Для того, чтобы классифицировать и предсказать спам-письмо, отличив от не-спама, мы будем использовать следующие методы и предположения:
- Мы будем сортировать на основе языка (спам или не-спам), затем на основе слов, затем по подсчетам
- Если слово не существует, то мы учтем апроксимацию P(word|class) используя Laplacian
- Мы будем использовать следующую таблицу для анализа
Файл antispam-table.txt - это файл, который содержит каждое слово, которое использует фильтрация контента для определения того, является ли сообщение спамом. Кроме каждого слова есть еще три числа. Первое число - это идентификатор назначенного антиспамовского движка. Второе - это количество появлений слова в не-спамовских письмах. Третье число представляет количество появлений слова в спамовских письмах.
http://support.ipswitch.com/kb/IM-20030513-DM01.htm
Мы создали базу данных из CSV-файла, указанного в уроке. Далее мы приведем код:
- Сначала необходимо удалить или заменить все известные и неизвестные специальные символы, тем самым только слова могут быть использованы для подсчета вероятности. Лучше не использовать заглавные буквы в словах.
String inputContent = TextBox1.Text;
inputContent = inputContent.Replace("\t", "");
inputContent = inputContent.Replace("\n", "");
inputContent = inputContent.Replace(",", "");
inputContent = inputContent.Replace(".", "");
inputContent = inputContent.Replace(";", "");
inputContent = inputContent.Replace(":", "");
inputContent = inputContent.Replace("?", "");
inputContent = inputContent.Replace("!", "");
inputContent = inputContent.Replace("&", ""); - Далее необходимо разделить каждое слово и найти соответствующее значение в базе данных. Значение демонстрирует то, как часто слово было найдено в спам- и неспамовских письмах. Если слово не будет найдено, вам надо выполнить laplace или просто приравнять к 1 (причина указана выше).
char seperator = ' ';
String[] words = inputContent.Split(seperator);
int CountWords = words.Length;
//сохранить P(score) и умножить
double SpamPercent = 1.0;
double NonSpamPercent = 1.0;
//найти процентное содержание слова в тексте без спама
for (int i = 0; i < CountWords; i++)
{
String thisword = words[i];
String DBaseValue = (BayesTheorem.FindNonSpamWord(thisword));
if (DBaseValue == "")
{
//выполнить Laplace или приравнять к 1
DBaseValue = "1";
}
NonSpamPercent = NonSpamPercent * (Convert.ToDouble(DBaseValue) /
Convert.ToInt32(BayesTheorem.TotalNonSpam()));
}
//найти процентное содержание слова в спаме
for (int i = 0; i < CountWords; i++)
{
String thisword = words[i];
String DBaseValue = (BayesTheorem.FindSpamWord(thisword));
if (DBaseValue == "")
{
//выполнить Laplacin или приравнять к 1
DBaseValue = "1";
}
SpamPercent = SpamPercent * (Convert.ToDouble(DBaseValue) /
Convert.ToInt32(BayesTheorem.TotalSpam()));
} - Получите финальную вероятность путем умножения каждого слова на общую вероятность:
//получение P(mailType).P(Word | MailType) для Spam
SpamPercent = SpamPercent * Convert.ToDouble(Label4.Text) * 100;
//получение P(mailType).P(Word | MailType) для NonSpam
NonSpamPercent = NonSpamPercent * Convert.ToDouble(Label3.Text) * 100; - Отображение результатов в таблице:
//Отобразить результаты в таблице
Label6.Text = NonSpamPercent.ToString();
Label7.Text = SpamPercent.ToString();Сравните результаты друг с другом и определите спам или неспам, основываясь на высшей вероятности.
if (SpamPercent > NonSpamPercent)
Label8.Text = "Почта со спамом";
else Label8.Text = "Почта без спама"; - Наконец, если вы определили письмо со спамом, обновите значения базы данных для каждого слова. Точно так же происходит с неспамовским письмом. Если значение не существует в базе данных, просто внесите его для будущего использования. Чем лучше тренировка слов, тем лучше будет классификация.