Модель МакКаллока-Питтса
Материал из MachineLearning.
Сравнение работы ЕМ-алгоритма и k-means для смесей с экспоненциальным распределением компонент. (будет в заголовке)
В статье приведены примеры классификации ЕМ-алгоритмом и методом k ближайших соседей двумерной смеси, компоненты которой имеют экспоненциальное распределение.
Содержание |
Краткое описание исследуемых алгоритмов
ЕМ алгоритм
Основа EM-алгоритма - предположение, что исследуемое множество данных может быть представлено с помощью линейной комбинации распределений, а цель - оценка параметров распределения, которые максимизируют логарифмическую функцию правдоподобия, используемую в качестве меры качества модели. Пусть рассматривается смесь из распределений, каждое описывается функцией правдоподобия
- априорная вероятность -й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений и отличаются только значениями параметра
Вывод формул для алгоритма
Вход:
– общая длина выборки
Выход:
параметры распределения и весы компонент.
Оценка максимального правдоподобия (ОМП) θ
для одно- и двумерного случая экспоненциального распределения.
Необходимо максимизировать
Из Лагранжиана следует:
j=1,...,k
j=1,...,k.
С учетом получаем ОМП для экспоненциального закона:
В одномерном случае:
В двумерном случае:
k-means (k ближайших соседей)
Метод ближайших соседей - это метрический алгоритм классификации, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
Постановка задачи
Пусть - множество объектов; - множество допустимых ответов. Задана обучающая выборка . Задано множество объектов . Требуется найти множество ответов для объектов .
На множестве объектов задается некоторая функция расстояния, в данном случае - максимум модулей
Для произвольного объекта расположим объекты обучающей выборки в порядке возрастания расстояний до :
где через обозначается тот объект обучающей выборки, который является -м соседом объекта . Аналогично для ответа на -м соседе: .
Таким образом, произвольный объект порождает свою перенумерацию выборки. В наиболее общем виде алгоритм ближайших соседей есть
где — заданная весовая функция, которая оценивает степень важности -го соседа для классификации объекта .
В рассматриваемом примере что соответствует методу ближайших соседей.
Примеры работы
Сравнение проводилось с использованием написанных на практикуме алгоритмов EM и k-means. На графиках, отображающих компоненты, показано по одной из-за большого разброса предельных значений классифицируемых объектов. Следует обратить внимание на интервал, содержащий всю выборку.
Пример №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%)
Литература
- К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации
- Королёв В.Ю. ЕМ-алгоритм, его модификации и их применение к задаче разделения смесей вероятностных распределений. Теоретический обзор. - М.: ИПИРАН, 2007
- http://en.wikipedia.org/wiki/Maximum_likelihood#Discrete_distribution.2C_finite_parameter_space
- http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html
- http://www.basegroup.ru/library/analysis/clusterization/em/
- http://fedc.wiwi.hu-berlin.de/xplore/ebooks/html/csa/node45.html
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |