Участник:Noite/EM-алгоритм кластеризации

EM-алгоритм
Последовательный алгоритм
Последовательная сложность	[math][/math]
Объём входных данных	[math]n * l + 1[/math]
Объём выходных данных	[math]n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math][/math]
Ширина ярусно-параллельной формы	[math][/math]

Автор описания: Зинченко Д.А.

Алгоритм кластеризации, основанный на максимизации ожидания (EM-алгоритм)

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

В задачах оптимизации EM-алгоритмом называют итеративную процедуру поиска численного значения экстремума какой-либо функции. В частности, в статистике этот алгоритм используется для оценки максимального правдоподобия. Впервые название EM-алгоритм было предложено в 1977 году [1], однако его идеи были описаны и раньше [2].

EM-алгоритм применяется для решения задач двух типов [2]:

1. Анализ неполных данных (данных с пропусками).

2. Оценка максимального правдоподобия в случае, если функцию правдоподобия трудно исследовать аналитически. В этом случае введение набора скрытых переменных может существенно упростить задачу.

Задача кластеризации относится к задачам второго типа. В данной статье рассматривается следующая постановка задачи кластеризации:

Дано множество объектов, каждый из которых представляет собой точку в n-мерном метрическом пространстве. Каждому измерению пространства соответствует некоторое свойство объекта. Необходимо разбить это множество на k подмножеств так, чтобы, чтобы элементы каждого подмножества существенно отличались по свойствам от элементов других подмножеств.

Использование алгоритма EM подразумевает следующее предположение об объектах: Пусть объекты, которые необходимо разбить на кластеры, появляются случайным образом и независимо друг от друга согласно вероятностному распределеию, равному смеси (линейной комбинации) распределений кластеров. При этом распределение каждого кластера является многомерным нормальным распределением с произвольной матрицей ковариации.

Тогда каждый объект принадлежит каждому кластеру, но с разной вероятностью. EM-алгоритм итеративно оценивает параметры распределений кластеров, максимизируя логарифмическую функцию максимального правдоподобия. После окончания работы алгоритма объект будет отнесен к кластеру, вероятность принадлежности которому максимальна. Вводимый набор скрытых переменных для каждого объекта - вероятности того, что объект принадлежит каждому из кластеров.

Итерация алгоритма состоит из двух последовательных шагов.

1 (Expectation). Вычисляются новые ожидаемые значения скрытых переменных.

2 (Maximization). Решается задача максимизации правдоподобия: По текущим значениям скрытых переменных обновляются параметры распределений для кластеров: математическое ожидание, дисперсия и вероятность появления объектов из кластера.

1.2 Математическое описание алгоритма

Используемые обозначения:

[math]N[/math] - количество объектов

[math]\gamma_{nk}[/math] - значения скрытых переменных

[math]N_{k}[/math] - количество элементов отнесенных к соответствующему кластеру

[math]x_{1},...,x_n[/math] - объекты

Параметры распределений:

[math]w_{1},...,w_{k}[/math] - вероятности появления объектов из кластеров (веса)

[math]\mu_{1},...,\mu_{k}[/math] - центры гауссиан кластеров

[math]\Sigma_{1},...,\Sigma_{k}[/math] - матрицы ковариации гауссиан кластеров

• В начале работы алгоритма задаются параметры начального приближения
• Далее итеративно выполняется следующая пара процедур:
  • E-шаг: используя текущее значение параметров [math]\pi_{1},...,\pi_{k};\mu_{1},...,\mu_{k};\Sigma_{1},...,\Sigma_{k}[/math], вычисляем значение вектора скрытых переменных [math]\gamma[/math]: [math]\gamma_{nk}=\frac{w_{k}p(x_{n}|\mu_{k},\Sigma_{k})}{\sum_{j=1}^K \pi_{j}p(x_{n}|\mu_{j},\Sigma_{j})}[/math].
  • М-шаг: переоценка параметров по текущим значениям скрытых переменных,

[math]\mu^{new}_{k}=\frac{1}{N_{k}}\sum_{n=1}^N \gamma_{nk}x_{n}[/math], [math]\Sigma^{new}_{k}=\frac{1}{N_{k}}\sum_{n=1}^N \gamma_{nk} (x_{n}-\mu_{k}^{new})(x_{n}-\mu_{k}^{new})^{T}[/math], [math]\pi_{k}^{new}=\frac{N_{k}}{N}[/math], [math]N_{k}=\sum_{n=1}^N \gamma_{nk}[/math].

Процедура останавливается после того, как норма разности векторов скрытых переменных на каждой итерации не будет превышать заданную константу, либо по прошествии заданного количества итераций.

1.3 Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является итерация - последовательное выполнение E и M шагов, обновляющих параметры распределений и скрытые переменные.

1.4 Макроструктура алгоритма

Как записано и в описании вычислительного ядра алгоритма, основную часть алгоритма составляют E и M шаги.

1.9 Входные и выходные данные алгоритма

Входные данные:

• Целое неотрицательное число [math]k[/math] - количество кластеров;
• Значения координат объектов [math]x_{i}[/math] - [math]n[/math] объектов с [math]m[/math] координатами каждый.

Объем входных данных:

• [math]n * m[/math] вещественных чисел (если координаты объектов - вещественные числа), [math]1[/math] целое неотрицательное число.

Выходные данные:

• Вектор длины [math]n[/math] - для каждого объекта указан номер кластера, к которому он отнесен.

Объем выходных данных:

• [math]n[/math] целых неотрицательных чисел.

1.10 Свойства алгоритма

EM-алгоритм обладает следующими преимуществами и недостатками:

Преимущества:

1. Слабо чувствителен к выбросам

2. Прост в реализации

3. Быстро сходится при удачном выборе начальных значений параметров.

Недостатки:

1. Неустойчив к выбору начальных значений параметров - от них зависит как скорость сходимости, так и результат работы: алгоритм может сойтись к локальному экстремуму функции правдоподобия, который может быть существенно ниже глобального.

2. Алгоритм не находит оптимальное количество кластеров. Количество кластеров, на которые нужно разбить множество объектов, является параметром алгоритма.

3. При большой размерности пространства объектов выдвинутое предположение о модели их распределения может быть некорректным.

2 Литература

[1] A. Dempster, N. Laird and D. Rubin. Maximum likelihood estimation from incomplete data. – Journal of the Royal Statistical Society, Series B, 1977, vol. 39, p. 1-38. [2] В.Ю.Королёв. ЕМ-алгоритм, его модификации и их применение к задаче разделения смесей вероятностных распределений.