Слияние кода завершено, страница обновится автоматически
[toc]
Формула Байеса описывает связь между априорной и апостериорной вероятностями.
Пусть $A_1, A_2, \dots, A_n$ образуют полную группу событий, и для $\forall A_i, P(A_i) > 0$. $B$ — произвольное событие в пространстве выборок, $P(B) > 0$, тогда: $$ P(A_k | B) = \frac{P(A_k)P(B|A_k)}{\displaystyle\sum^{n}_{i=1}P(A_i)P(B|A_i)} $$
Для формулы Байеса можно дать следующее понимание[^2]: $$ P(\text{класс}|\text{признак}) = \frac{P(\text{признак}|\text{класс})P(\text{класс})}{P(\text{признак})} $$ Когда мы вычисляем $P(\text{класс}|\text{признак})$, затем относим данную выборку к классу с максимальной вероятностью, фактически мы завершаем процесс байесовской классификации.
Однако, вышеуказанное понимание формулы Байеса требует добавления одного необходимого условия, а именно, независимости переменных, чтобы удовлетворить условию "полная группа событий". Поэтому на практике мы также предполагаем, что признаки независимы друг от друга.
Однако на практике почти невозможно, чтобы статистически наблюдаемые переменные были полностью независимы. Например, пусть событие $A=\text{в письме появляется “http”},$ $B = \text{в письме содержится полная ссылка}$, когда $A$ и $B$ происходят одновременно, письмо скорее всего является спам-рекламой. Однако, очевидно, что $B \subseteq A$, то есть $A$ и $B$ не являются независимыми. Наша программа в процессе обработки с трудом может определить сложные семантические и логические связи между словами, то есть не может определить, являются ли события появления двух слов независимыми. Кроме того, из-за сложности человеческого языка слова обычно связаны друг с другом и не могут быть напрямую абстрагированы как взаимоисключающие события. Поэтому использование алгоритма наивного Байеса для классификации текстовых спам-писем имеет определенную теоретическую погрешность.
Однако при небольшом использовании алгоритм наивного Байеса все еще может хорошо работать в простых задачах классификации писем.
Пусть $A_i$ — появление i-го слова из словаря, $B$ — это письмо является спамом, $\because A_i, A_j \text{независимы}(i \neq j)$, тогда: $$ \begin{align} P(B|A_1,A_2,\cdots,A_n) & = \frac{P(A_1|B)P(A_2|B)\cdots P(A_n|B) P(B)}{P(A_1)P(A_2)\cdots P(A_n)} \\ & = \frac{P(B) \Pi^{n}{i=1}P(A_i|B)}{\Pi^n{i=1}P(A_i)} \end{align} $$
В процессе обработки программы нам нужно выполнять вычисления с числами, но наш повседневный язык состоит из слов и других элементов. Для преобразования между ними и обеспечения правильного "понимания" слов программой нам нужен метод правильного представления слов числами.
Часто используемые методы включают one-hot кодирование, векторные представления слов и т.д. Здесь используется one-hot кодирование.
В one-hot кодировании данные, которые нужно использовать, имеют значение 1 на соответствующей позиции в векторе, а остальные данные имеют значение 0. В контексте этой задачи классификации словарь состоит из всех слов, встречающихся в обучающих данных, длина вектора равна длине словаря, а one-hot кодирование каждого слова имеет вид $[0,0,\dots,1,\dots,0]$.
Рассмотрим формулу Байеса: знаменатель равен $\Pi^n_{i=1}P(A_i)$, но если знаменатель равен 0, вычисленная вероятность становится бессмысленной. Чтобы решить эту проблему, нам нужно гарантировать, что знаменатель не равен 0. Для этого мы используем метод Лапласовского сглаживания для обработки данных знаменателя.
Лапласовское сглаживание, также известное как сглаживание "плюс один", является часто используемым методом сглаживания, применяемым для решения проблемы нулевой вероятности[^3].
Пусть $\alpha > 0$, когда $\alpha \rightarrow 0$, $\Pi^n_{i=1}P(A_i) \approx \Pi^n_{i=1}P(A_i) + \alpha$.
Теперь знаменатель уже не равен 0, но все еще существуют некоторые проблемы: вычисленная вероятность $P(B|A_1,A_2,\cdots,A_n)$ может быть слишком большой из-за малого знаменателя. Поэтому лучше добавить к ней логарифмическую функцию, чтобы предотвратить переполнение при больших числах. Поскольку используется логарифмическая функция, требуется $\text{параметр} > 0$, поэтому мы можем добавить $\alpha$ к числителю $P(B) \Pi^{n}{i=1}P(A_i|B)$. Итоговая формула выглядит следующим образом: $$ \begin{align} Q_B & = \ln(P(B|A_1,A_2,\cdots,A_n)) \ & = \ln(\frac{P(B) \Pi^{n}{i=1}P(A_i|B)}{\Pi^n_{i=1}P(A_i)}) \ & \approx \ln P(B) + \displaystyle\sum^{n}{i=1}\ln(\frac{P(A_i|B)}{P(A_i) + \alpha_2} + \alpha_1) \ & \approx \ln P(B) + \displaystyle\sum^n{i-1}\ln(P(A_i|B)+\alpha_1) - \displaystyle\sum^n_{i-1}\ln(P(A_i)+\alpha_2) \end{align}
\qquad (\alpha_1, \alpha_2 > 0) $$
def split_text(text: str):
# Разделение строки по специальным символам, то есть не буквам и не цифрам
tokens = re.split(r'\W+', text)
# Преобразование всех слов в нижний регистр, кроме одиночных букв (например, заглавной I), и исключение чисто числовых слов
return [tok.lower() for tok in tokens if len(tok) > 2 and not tok.isdigit()]
def get_words_data():
"""
Получение текстовых данных для обучения и форматирование их на уровне слов
:return: Полученные текстовые данные, список классов
"""
class_types = [r for r in os.listdir('email') if os.path.isdir(os.path.join('email', r))]
def read_data(filename_: str) -> str:
with open(filename_, 'r', encoding='gbk') as f:
return f.read()
words_data = []
for c in class_types:
for filename in os.listdir(os.path.join('email', c)):
file_data = read_data(os.path.join(f'email/{c}', filename))
words_data.append((c, split_text(file_data)))
return words_data, class_types
def get_words_label(words_data: list) -> list:
"""
Получение словаря для текущего набора данных
:param words_data: Полученные данные слов
:return: Словарь
"""
# Использование set для удаления дубликатов
words_label = set({})
for words in words_data:
words_label.update(words[1])
res = list(words_label)
res.sort()
return res
def get_words_vector(words, words_label: list) -> list:
"""
Получение векторного представления слова или списка слов
:param words: Слово или список слов
:param words_label: Словарь
:return: Векторное представление
"""
return [(1 if val == words else 0) if not isinstance(words, list)
else (1 if val in words else 0) for val in words_label]
def native_bayes_train(words_label: list, train_data: list, class_types: list, alpha: float = 1e-3):
"""
Обучение классификатора наивного Байеса
:param words_label: Словарь
:param train_data: Обучающий набор данных
:param class_types: Список классов
:param alpha: > 0 и очень малое число для Лапласовского сглаживания
:return: Результат обучения, вероятности различных классов
"""
# Инициализация с этим alpha для предотвращения появления NaN.
p_result = {c: np.array([alpha for _ in range(len(words_label))]) for c in class_types}
p_b = {c: alpha for c in class_types}
for data in train_data:
# Получение векторного представления слов
words_vector = np.array(get_words_vector(data[1], words_label))
# Запись данных в обучающую выборку
p_result[data[0]] += words_vector + alpha
# Запись вероятности соответствующего класса
p_b[data[0]] += 1 / len(train_data)
for k in p_result:
p_result[k] = np.log(p_result[k])
return p_result, p_b
def native_bayes_test(words_label: list, p_result: dict, test_data: list, p_b: dict, alpha: float = 1e-3) -> float:
"""
Тестирование классификатора наивного Байеса
:param words_label: Словарь
:param p_result: Результат обучения
:param test_data: Тестовый набор данных
:param p_b: Вероятности различных классов
:param alpha: > 0 и очень малое число для Лапласовского сглаживания
:return: Вероятность правильного тестирования
"""
accurate = 0
for data in test_data:
# Получение векторного представления слов
words_vector = np.array(get_words_vector(data[1], words_label))
# Вычисление относительных вероятностей
Qs = {key: np.log(p_b[key]) + sum(p_result[key] * words_vector) - np.log(sum(words_vector + alpha)) for key in
p_result}
# Выбор класса с максимальной относительной вероятностью
classification = reduce((lambda x, y: x if x[1] > y[1] else y), ((k, Qs[k]) for k in Qs))[0]
print(f"result {classification == data[0]}, classification = {classification}, label = {data[0]}; Qs: {Qs}")
# Запись точности
accurate += (1 if classification == data[0] else 0) / len(test_data)
return accurate
def main():
# Чтение обучающих и тестовых данных
words_data, class_types = get_words_data()
# Перемешивание обучающих данных
random.shuffle(words_data)
# Генерация словаря
words_label = get_words_label(words_data)
# Обучение классификатора наивного Байеса с использованием случайных 40 писем в качестве обучающей выборки
p_result, p_b = native_bayes_train(words_label, words_data[:40], class_types)
# Тестирование классификатора наивного Байеса с использованием оставшихся писем в качестве тестовой выборки
accurate = native_bayes_test(words_label, p_result, words_data[40:], p_b)
print(f"DONE! accurate = {(accurate * 100):.2f}%")
Полная программа приведена в приложении.
result True, classification = ham, label = ham; Qs: {'ham': -59.347845111308025, 'spam': -85.7843006553319}
result True, classification = spam, label = spam; Qs: {'ham': -36.34975776983966, 'spam': 5.109566958100539}
result True, classification = ham, label = ham; Qs: {'ham': -92.15951999754893, 'spam': -184.30347898520958}
result True, classification = spam, label = spam; Qs: {'ham': -57.07097136557958, 'spam': -53.66419688826986}
result True, classification = spam, label = spam; Qs: {'ham': -90.63426772205429, 'spam': 30.369671882623937}
result True, classification = spam, label = spam; Qs: {'ham': -90.63426772205429, 'spam': 30.369671882623937}
result True, classification = spam, label = spam; Qs: {'ham': -28.69504741287626, 'spam': -16.289914553986566}
result True, classification = spam, label = spam; Qs: {'ham': -111.28152808527354, 'spam': 32.34635005125606}
result True, classification = spam, label = spam; Qs: {'ham': -105.0581659869714, 'spam': 30.966905653462643}
result True, classification = spam, label = spam; Qs: {'ham': -90.63426772205429, 'spam': 30.369671882623937}
DONE! accurate = 100.00%
Точность классификации программы может достигать более $90%$.
В данной работе на основе теоретических знаний по курсу теории вероятностей и математической статистики был создан классификатор спам-почты на основе алгоритма наивного Байеса. Это демонстрирует богатые применения теории вероятностей.
import os
import re
import numpy as np
from functools import reduce
import random
def split_text(text: str):
# Разделение строки по специальным символам, то есть не буквам и не цифрам
tokens = re.split(r'\W+', text)
# Преобразование всех слов в нижний регистр, кроме одиночных букв (например, заглавной I), и исключение чисто числовых слов
return [tok.lower() for tok in tokens if len(tok) > 2 and not tok.isdigit()]
def get_words_data():
"""
Получение текстовых данных для обучения и форматирование их на уровне слов
:return: Полученные текстовые данные, список классов
"""
class_types = [r for r in os.listdir('email') if os.path.isdir(os.path.join('email', r))]
def read_data(filename_: str) -> str:
with open(filename_, 'r', encoding='gbk') as f:
return f.read()
words_data = []
for c in class_types:
for filename in os.listdir(os.path.join('email', c)):
file_data = read_data(os.path.join(f'email/{c}', filename))
words_data.append((c, split_text(file_data)))
return words_data, class_types
def get_words_label(words_data: list) -> list:
"""
Получение словаря для текущего набора данных
:param words_data: Полученные данные слов
:return: Словарь
"""
# Использование set для удаления дубликатов
words_label = set({})
for words in words_data:
words_label.update(words[1])
res = list(words_label)
res.sort()
return res
def get_words_vector(words, words_label: list) -> list:
"""
Получение векторного представления слова или списка слов
:param words: Слово или список слов
:param words_label: Словарь
:return: Векторное представление
"""
return [(1 if val == words else 0) if not isinstance(words, list)
else (1 if val in words else 0) for val in words_label]
def native_bayes_train(words_label: list, train_data: list, class_types: list, alpha: float = 1e-3):
"""
Обучение классификатора наивного Байеса
:param words_label: Словарь
:param train_data: Обучающий набор данных
:param class_types: Список классов
:param alpha: > 0 и очень малое число для Лапласовского сглаживания
:return: Результат обучения, вероятности различных классов
"""
# Инициализация с этим alpha для предотвращения появления NaN.
p_result = {c: np.array([alpha for _ in range(len(words_label))]) for c in class_types}
p_b = {c: alpha for c in class_types}
for data in train_data:
# Получение векторного представления слов
words_vector = np.array(get_words_vector(data[1], words_label))
# Запись данных в обучающую выборку
p_result[data[0]] += words_vector + alpha
# Запись вероятности соответствующего класса
p_b[data[0]] += 1 / len(train_data)
for k in p_result:
p_result[k] = np.log(p_result[k])
return p_result, p_b
def native_bayes_test(words_label: list, p_result: dict, test_data: list, p_b: dict, alpha: float = 1e-3) -> float:
"""
Тестирование классификатора наивного Байеса
:param words_label: Словарь
:param p_result: Результат обучения
:param test_data: Тестовый набор данных
:param p_b: Вероятности различных классов
:param alpha: > 0 и очень малое число для Лапласовского сглаживания
:return: Вероятность правильного тестирования
"""
accurate = 0
for data in test_data:
# Получение векторного представления слов
words_vector = np.array(get_words_vector(data[1], words_label))
# Вычисление относительных вероятностей
Qs = {key: np.log(p_b[key]) + sum(p_result[key] * words_vector) - np.log(sum(words_vector + alpha)) for key in
p_result}
# Выбор класса с максимальной относительной вероятностью
classification = reduce((lambda x, y: x if x[1] > y[1] else y), ((k, Qs[k]) for k in Qs))[0]
print(f"result {classification == data[0]}, classification = {classification}, label = {data[0]}; Qs: {Qs}")
# Запись точности
accurate += (1 if classification == data[0] else 0) / len(test_data)
return accurate
def main():
# Чтение обучающих и тестовых данных
words_data, class_types = get_words_data()
# Перемешивание обучающих данных
random.shuffle(words_data)
# Генерация словаря
words_label = get_words_label(words_data)
# Обучение классификатора наивного Байеса с использованием случайных 40 писем в качестве обучающей выборки
p_result, p_b = native_bayes_train(words_label, words_data[:40], class_types)
# Тестирование классификатора наивного Байеса с использованием оставшихся писем в качестве тестовой выборки
accurate = native_bayes_test(words_label, p_result, words_data[40:], p_b)
print(f"DONE! accurate = {(accurate * 100):.2f}%")
if __name__ == '__main__':
main()
Структура каталогов для выполнения программы:
│ bayes.py
└─ email/
├─ham
│ *.txt
└─spam
*.txt
https://github.com/Asia-Lee/Naive_Bayes
[^1]: Ван Юнгьи Тянь Боцин. Теория вероятностей и математическая статистика [M]. Второе издание. Пекин: Научное издательство Китая, 2005. [^2]: И Чжэнь. [EB/OL]. https://zhuanlan.zhihu.com/p/26262151. 2017年04月10日-2021年11月23日. [^3]: Чжэн Ваньтонг. [EB/OL]. https://blog.csdn.net/zhengwantong/article/details/72403808. 2017年05月17日-2021年11月23日.
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )