Байесовский классификатор


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН
ЮЖНО-КАЗАХСТАНСКИЙ УНИВЕРСИТЕТ им. М. АУЕЗОВА
Кафедра: Вычислительная техника и программное обеспечение
СРО 3
Тема: Байесовский классификатор
Выполнил: - - Курбанбай Ж.
Группа: ИП-18-6ТК
Проверил(а): Тарасова Р.Н.
Шымкент 2020 г.
Содержание
Введение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..3
1. Байесовская классификация ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4
1.2. Общая структура байесовского классификатора ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4
2. Метод главных компонент ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
3. Программная реализация алгоритмов ... ... ... ... ... ... ... ... ... ... ... ... ... ... .6
3.1. Алгоритмы байесовской классификации ... ... ... ... ... .. ... ... ... ... ... ... ... .6
Заключение ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .8
Список использованной литературы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..9
Введение
В машинном обучении классификацию понимают как задачу определения класса для ранее не встречавшегося образца (объекта) на основе эмпирических данных, так называемых прецедентов, которые описывают исследуемые образцы и отражают присущие им свойства и закономерности. Существует зависимость между образцами и классами, но она неизвестна. Множество прецедентов, пар образец-класс, составляет обучающую выборку, по которой находится зависимость, то есть строится алгоритм, способный для любого образца выдать ответ, к какому классу тот принадлежит. Это пример обучения с учителем. Под учителем в данном случае понимается обучающая выборка. Примерами таких моделей, основанных на машинном обучении, являются байесовские классификаторы. В работе рассмотрены наивный байесовский классификатор [1,2] и оптимальный байесовский классификатор [3]. В байесовских классификаторах используется критерий, минимизирующий вероятность принятия ошибочного решения, поэтому байесовские алгоритмы являются статистически оптимальными [1,4]. Однако для этого алгоритмы требуют в идеале полного знания многомерных функций распределения наблюдаемых признаков для каждого класса. Необходимость такого знания обусловлена использованием формулы Байеса, которая лежит в основе байесовских методов принятия решения.
1 Байесовская классификация
В настоящее время статистические методы широко применяются для классификации текстов по признакам авторского, жанрового, гендерного и других стилей. Байесовская теория принятия решений составляет основу статистического подхода к задаче классификации объектов. Этот подход основан на предположении, что задача выбора решения сформулирована в терминах теории вероятностей и известны все представляющие интерес вероятностные величины. В основе байесовской классификации лежит правило Байеса. 1.1 Постановка задачи Рассмотрим обучающую выборку из 𝑛 объектов, каждый из которых принадлежит одному из 𝐾 классов и характеризуется набором 𝑚 числовых признаков 𝑎1, 𝑎2, ... 𝑎𝑚. Пусть имеется 𝑛𝑘 объектов 𝑘-ого класса, так что 𝑁 = ∑ 𝑛𝑘 𝐾 𝑘=1 . Значение 𝑗-ого признака 𝑖-ого объекта из 𝑘-ого класса обозначим 𝑥𝑖𝑗𝑘. Тогда этот объект можно охарактеризовать вектором-строкой 𝑥𝑖𝑘 = (𝑥𝑖1𝑘, ... , 𝑥𝑖𝑗𝑘, ... , 𝑥𝑖𝑚𝑘). Эту строку будем рассматривать как 𝑖-ю реализацию векторной случайной величины 𝜉k, подчиняющейся распределению вероятностей с плотностью 𝑝(𝑥1, ... , 𝑥𝑚𝑘), своей для каждого класса 𝑘 [3]. Пусть теперь наблюдается объект, для которого необходимо определить, к какому классу он относится. Объект характеризуется только набором 𝑚 числовых признаков 𝑥1, ... , 𝑥𝑚.
1.2 Общая структура байесовского классификатора
В основе классификатора лежит следующее правило. Классификатор вычисляет апостериорную вероятность 𝑃(𝑘𝑥) каждого класса 𝑘, которому 7 может принадлежать испытуемый объект, и относит этот объект к апостериорно наиболее вероятному классу 𝑘̂: 𝑘̂ = arg max 𝑘 ln 𝑃(𝑘𝑥1, ... , 𝑥𝑚) . Апостериорная вероятность вычисляется по формула Байеса: 𝑃(𝑘𝑥1, ... , 𝑥𝑚) = 𝑃(𝑘)𝑝(𝑥1, ... , 𝑥𝑚𝑘)𝑝(𝑘), где 𝑃(𝑘) - априорная вероятность того, что объект относится к 𝑘-ому классу, 𝑝(𝑘) и 𝑝(𝑥1, ... , 𝑥𝑚𝑘) - безусловная и условная многомерные плотности распределения вектора признаков, компоненты которого обычно статистически зависимы. Таким образом, байесовский классификатор предполагает, что многомерная совместная плотность распределения признаков известна для всех классов. Аналитическое представление многомерной плотности вероятности известно только для нормального распределения. Вместе с тем многомерная нормальная плотность распределения дает подходящую модель для одного важного случая, а именно когда значения векторов признаков 𝑥 для данного класса 𝑘 представляются непрерывнозначными, слегка искаженными версиями единственного типичного вектора, или вектора-прототипа, 𝜇𝑘. Именно этого ожидают, когда классификатор выбирается так, чтобы выделять те признаки, которые, будучи различными для образов, принадлежащих различным классам, были бы, возможно, более схожи для образов из одного и того же класса [1]. Многомерная нормальная плотность распределения в общем виде представляется выражением 𝑝(𝑥) = 1 (2𝜋) 𝑚 2 det 𝑅 1 2 𝑒 − 1 2 (𝑥−𝜇) 𝑇𝑅 −1(𝑥−𝜇) , 8 где u - 𝑚-компонентный вектор среднего значения, 𝑅 - ковариационная матрица размера 𝑚 x 𝑚, 𝑇 - знак транспонирования. Отметим, что если все недиагональные элементы равны нулю, то 𝑝(𝑥) сводится к произведению одномерных нормальных плотностей компонент вектора 𝑥. Поэтому для многомерного нормального распределения удаётся выразить в аналитически замкнутой форме (с точностью до несущественных слагаемых) алгоритм байесовской классификации: 𝑘̂ = arg max 𝑘 (ln 𝑃(𝑘) − 1 2 ln det𝑅𝑘 − 1 2 (𝑥𝑘 − 𝜇𝑘)𝑅𝑘 −1 (𝑥𝑘 − 𝜇𝑘) 𝑇 ) , (1) где 𝜇𝑘 - 𝑚-вектор-строка математических ожиданий значений признаков объектов класса 𝑘, 𝑅𝑘 - 𝑚 x 𝑚-матрица ковариаций векторов признаков класса 𝑘. Диагональные элементы матрицы образуют 𝑚-вектор 𝐷𝑘 дисперсий признаков объектов класса 𝑘.
2 Метод главных компонент
Как упоминалось ранее, при недостаточном объеме обучающей выборки оптимальный байесовский классификатор построить невозможно. Выходом из такой ситуации может стать уменьшение размерности признакового пространства до значения, допускающего возможность построения невырожденных ковариационных матриц. Уменьшить размерность признакового пространства позволяет известный в математической статистике метод главных компонент [8]. Признаковое пространство векторов 𝑥 размерности 𝑚 смешанного ансамбля объектов, объединяющего все классы, преобразуется в новое признаковое пространство векторов 𝑦 ... продолжение
ЮЖНО-КАЗАХСТАНСКИЙ УНИВЕРСИТЕТ им. М. АУЕЗОВА
Кафедра: Вычислительная техника и программное обеспечение
СРО 3
Тема: Байесовский классификатор
Выполнил: - - Курбанбай Ж.
Группа: ИП-18-6ТК
Проверил(а): Тарасова Р.Н.
Шымкент 2020 г.
Содержание
Введение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..3
1. Байесовская классификация ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4
1.2. Общая структура байесовского классификатора ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4
2. Метод главных компонент ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
3. Программная реализация алгоритмов ... ... ... ... ... ... ... ... ... ... ... ... ... ... .6
3.1. Алгоритмы байесовской классификации ... ... ... ... ... .. ... ... ... ... ... ... ... .6
Заключение ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .8
Список использованной литературы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..9
Введение
В машинном обучении классификацию понимают как задачу определения класса для ранее не встречавшегося образца (объекта) на основе эмпирических данных, так называемых прецедентов, которые описывают исследуемые образцы и отражают присущие им свойства и закономерности. Существует зависимость между образцами и классами, но она неизвестна. Множество прецедентов, пар образец-класс, составляет обучающую выборку, по которой находится зависимость, то есть строится алгоритм, способный для любого образца выдать ответ, к какому классу тот принадлежит. Это пример обучения с учителем. Под учителем в данном случае понимается обучающая выборка. Примерами таких моделей, основанных на машинном обучении, являются байесовские классификаторы. В работе рассмотрены наивный байесовский классификатор [1,2] и оптимальный байесовский классификатор [3]. В байесовских классификаторах используется критерий, минимизирующий вероятность принятия ошибочного решения, поэтому байесовские алгоритмы являются статистически оптимальными [1,4]. Однако для этого алгоритмы требуют в идеале полного знания многомерных функций распределения наблюдаемых признаков для каждого класса. Необходимость такого знания обусловлена использованием формулы Байеса, которая лежит в основе байесовских методов принятия решения.
1 Байесовская классификация
В настоящее время статистические методы широко применяются для классификации текстов по признакам авторского, жанрового, гендерного и других стилей. Байесовская теория принятия решений составляет основу статистического подхода к задаче классификации объектов. Этот подход основан на предположении, что задача выбора решения сформулирована в терминах теории вероятностей и известны все представляющие интерес вероятностные величины. В основе байесовской классификации лежит правило Байеса. 1.1 Постановка задачи Рассмотрим обучающую выборку из 𝑛 объектов, каждый из которых принадлежит одному из 𝐾 классов и характеризуется набором 𝑚 числовых признаков 𝑎1, 𝑎2, ... 𝑎𝑚. Пусть имеется 𝑛𝑘 объектов 𝑘-ого класса, так что 𝑁 = ∑ 𝑛𝑘 𝐾 𝑘=1 . Значение 𝑗-ого признака 𝑖-ого объекта из 𝑘-ого класса обозначим 𝑥𝑖𝑗𝑘. Тогда этот объект можно охарактеризовать вектором-строкой 𝑥𝑖𝑘 = (𝑥𝑖1𝑘, ... , 𝑥𝑖𝑗𝑘, ... , 𝑥𝑖𝑚𝑘). Эту строку будем рассматривать как 𝑖-ю реализацию векторной случайной величины 𝜉k, подчиняющейся распределению вероятностей с плотностью 𝑝(𝑥1, ... , 𝑥𝑚𝑘), своей для каждого класса 𝑘 [3]. Пусть теперь наблюдается объект, для которого необходимо определить, к какому классу он относится. Объект характеризуется только набором 𝑚 числовых признаков 𝑥1, ... , 𝑥𝑚.
1.2 Общая структура байесовского классификатора
В основе классификатора лежит следующее правило. Классификатор вычисляет апостериорную вероятность 𝑃(𝑘𝑥) каждого класса 𝑘, которому 7 может принадлежать испытуемый объект, и относит этот объект к апостериорно наиболее вероятному классу 𝑘̂: 𝑘̂ = arg max 𝑘 ln 𝑃(𝑘𝑥1, ... , 𝑥𝑚) . Апостериорная вероятность вычисляется по формула Байеса: 𝑃(𝑘𝑥1, ... , 𝑥𝑚) = 𝑃(𝑘)𝑝(𝑥1, ... , 𝑥𝑚𝑘)𝑝(𝑘), где 𝑃(𝑘) - априорная вероятность того, что объект относится к 𝑘-ому классу, 𝑝(𝑘) и 𝑝(𝑥1, ... , 𝑥𝑚𝑘) - безусловная и условная многомерные плотности распределения вектора признаков, компоненты которого обычно статистически зависимы. Таким образом, байесовский классификатор предполагает, что многомерная совместная плотность распределения признаков известна для всех классов. Аналитическое представление многомерной плотности вероятности известно только для нормального распределения. Вместе с тем многомерная нормальная плотность распределения дает подходящую модель для одного важного случая, а именно когда значения векторов признаков 𝑥 для данного класса 𝑘 представляются непрерывнозначными, слегка искаженными версиями единственного типичного вектора, или вектора-прототипа, 𝜇𝑘. Именно этого ожидают, когда классификатор выбирается так, чтобы выделять те признаки, которые, будучи различными для образов, принадлежащих различным классам, были бы, возможно, более схожи для образов из одного и того же класса [1]. Многомерная нормальная плотность распределения в общем виде представляется выражением 𝑝(𝑥) = 1 (2𝜋) 𝑚 2 det 𝑅 1 2 𝑒 − 1 2 (𝑥−𝜇) 𝑇𝑅 −1(𝑥−𝜇) , 8 где u - 𝑚-компонентный вектор среднего значения, 𝑅 - ковариационная матрица размера 𝑚 x 𝑚, 𝑇 - знак транспонирования. Отметим, что если все недиагональные элементы равны нулю, то 𝑝(𝑥) сводится к произведению одномерных нормальных плотностей компонент вектора 𝑥. Поэтому для многомерного нормального распределения удаётся выразить в аналитически замкнутой форме (с точностью до несущественных слагаемых) алгоритм байесовской классификации: 𝑘̂ = arg max 𝑘 (ln 𝑃(𝑘) − 1 2 ln det𝑅𝑘 − 1 2 (𝑥𝑘 − 𝜇𝑘)𝑅𝑘 −1 (𝑥𝑘 − 𝜇𝑘) 𝑇 ) , (1) где 𝜇𝑘 - 𝑚-вектор-строка математических ожиданий значений признаков объектов класса 𝑘, 𝑅𝑘 - 𝑚 x 𝑚-матрица ковариаций векторов признаков класса 𝑘. Диагональные элементы матрицы образуют 𝑚-вектор 𝐷𝑘 дисперсий признаков объектов класса 𝑘.
2 Метод главных компонент
Как упоминалось ранее, при недостаточном объеме обучающей выборки оптимальный байесовский классификатор построить невозможно. Выходом из такой ситуации может стать уменьшение размерности признакового пространства до значения, допускающего возможность построения невырожденных ковариационных матриц. Уменьшить размерность признакового пространства позволяет известный в математической статистике метод главных компонент [8]. Признаковое пространство векторов 𝑥 размерности 𝑚 смешанного ансамбля объектов, объединяющего все классы, преобразуется в новое признаковое пространство векторов 𝑦 ... продолжение
Похожие работы
Дисциплины
- Информатика
- Банковское дело
- Оценка бизнеса
- Бухгалтерское дело
- Валеология
- География
- Геология, Геофизика, Геодезия
- Религия
- Общая история
- Журналистика
- Таможенное дело
- История Казахстана
- Финансы
- Законодательство и Право, Криминалистика
- Маркетинг
- Культурология
- Медицина
- Менеджмент
- Нефть, Газ
- Искуство, музыка
- Педагогика
- Психология
- Страхование
- Налоги
- Политология
- Сертификация, стандартизация
- Социология, Демография
- Статистика
- Туризм
- Физика
- Философия
- Химия
- Делопроизводсто
- Экология, Охрана природы, Природопользование
- Экономика
- Литература
- Биология
- Мясо, молочно, вино-водочные продукты
- Земельный кадастр, Недвижимость
- Математика, Геометрия
- Государственное управление
- Архивное дело
- Полиграфия
- Горное дело
- Языковедение, Филология
- Исторические личности
- Автоматизация, Техника
- Экономическая география
- Международные отношения
- ОБЖ (Основы безопасности жизнедеятельности), Защита труда
Реферат
Курсовая работа
Дипломная работа
Материал
Диссертация
Практика
-
-
-
1‑10 стр.
11‑20 стр.
21‑30 стр.
31‑60 стр.
61+ стр.
Основное
Кол‑во стр.
Доп.
Поиск
Ничего не найдено :(
Недавно просмотренные работы
Просмотренные работы не найдены
Заказ
Антиплагиат
Просмотренные работы
ru
ru/