Модель МакКаллока-Питтса
Материал из MachineLearning.
Сравнение работы ЕМ-алгоритма и k-means для смесей с экспоненциальным распределением компонент. (будет в заголовке)
В статье приведены примеры классификации ЕМ-алгоритмом и методом k ближайших соседей двумерной смеси, компоненты которой имеют экспоненциальное распределение.
Содержание |
Краткое описание исследуемых алгоритмов
ЕМ алгоритм
Основа EM-алгоритма - предположение, что исследуемое множество данных может быть представлено с помощью линейной комбинации распределений, а цель - оценка параметров распределения, которые максимизируют логарифмическую функцию правдоподобия, используемую в качестве меры качества модели. Пусть рассматривается смесь из распределений, каждое описывается функцией правдоподобия
- априорная вероятность -й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений и отличаются только значениями параметра
Вывод формул для алгоритма
Вход:
– общая длина выборки
Выход:
параметры распределения и весы компонент.
Оценка максимального правдоподобия (ОМП) θ
для одно- и двумерного случая экспоненциального распределения.
Необходимо максимизировать
Из Лагранжиана следует:
j=1,...,k
j=1,...,k.
С учетом получаем ОМП для экспоненциального закона:
В одномерном случае:
В двумерном случае:
k-means (k ближайших соседей)
Метод ближайших соседей - это метрический алгоритм классификации, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
Постановка задачи
Пусть - множество объектов; - множество допустимых ответов. Задана обучающая выборка . Задано множество объектов . Требуется найти множество ответов для объектов .
На множестве объектов задается некоторая функция расстояния, в данном случае - максимум модулей
Для произвольного объекта расположим объекты обучающей выборки в порядке возрастания расстояний до :
где через обозначается тот объект обучающей выборки, который является -м соседом объекта . Аналогично для ответа на -м соседе: .
Таким образом, произвольный объект порождает свою перенумерацию выборки. В наиболее общем виде алгоритм ближайших соседей есть
где — заданная весовая функция, которая оценивает степень важности -го соседа для классификации объекта .
В рассматриваемом примере что соответствует методу ближайших соседей.
Примеры работы
На графиках, отображающих компоненты, показано по одной из-за большого разброса предельных значений классифицируемых объектов. Следует обратить внимание на интервал, содержащий всю выборку.
Пример №1 (две компоненты)
Смесь из двух компонент по 500 элементов.
В результате работы ЕМ-алгоритма с последовательным добавлением компонент с параметрами R = 30, M = 20, Delta = 0,001 восстанавливается ,
Количество ошибок при классификации:
ЕМ 1 из 500 (0.2%)
k-means (k=1) 0 из 500
k-means (k=5) 1 из 500 (0.2%)
Пример №2 (три компоненты)
Смесь из трех компонент по 500 элементов
В результате работы ЕМ-алгоритма с последовательным добавлением компонент с параметрами R = 30, M = 40, Delta = 0,001 восстанавливается
,
,
Количество ошибок при классификации:
ЕМ 6 из 500 (1.2%)
k-means (k=1) 12 из 500 (2.2%)
k-means (k=5) 18 из 500 (3.6%)
Пример №3 (четыре компоненты)
Смесь из четырех компонент по 500 элементов. Добавлена компонента с
В результате работы ЕМ-алгоритма с последовательным добавлением компонент с параметрами R = 15, M = 30, Delta = 0,001 восстанавливается
,
,
,
Количество ошибок при классификации:
ЕМ 37 из 500 (7.4%)
k-means (k=1) 9 из 500 (1.8%)
k-means (k=5) 26 из 500 (5.2%)
Пример №4 (пять компонент)
Смесь из пяти компонент по 500 элементов. Добавили компоненту с
В результате работы ЕМ-алгоритма с последовательным добавлением компонент с параметрами R = 7, M = 20, Delta = 0,001 восстанавливается
,
,
,
,
,
Количество ошибок при классификации:
ЕМ 243 из 500 (48.6%)
k-means (k=1) 35 из 500 (7%)
k-means (k=5) 22 из 500 (4.2%)
Литература
- К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |