Участник:Александр Куваев/Алгоритм кластеризации, основанный на максимизации ожидания

Авторы описания: Куваев А.С. и Щенявская Е.В.

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

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

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

Решение этой задачи принципиально неоднозначно по следующим причинам:

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

По описанной выше причине существует большое число алгоритмов кластеризации, приводящих к различным разбиениям исходного множества объектов. На этой странице представлено описание одного из таких методов — EM-алгоритма. EM-алгоритм опирается на предположение о вероятностной природе данных: элементы выборки получены случайно и независимо из смеси распределений с фиксированным числом компонент [math]k[/math]. Таким образом, плотность распределения на множестве объектов имеет следующий вид:

[math]p(x)=\sum_{j=1}^{k}w_{j}p_{j}(x), \sum_{j=1}^{k}w_{j}=1, w_{j} \ge 0 [/math], где [math]p_{j}[/math] - плотность распределения [math]j[/math]-й компоненты смеси.

В дальнейшем будем предполагать, что [math]p_{j}[/math] имеют вид многомерных нормальных плотностей с произвольной матрицей ковариации: смеси нормальных распределений позволяют аппроксимировать произвольные непрерывные функции плотности с наперед заданной точностью. Результатом работы EM-алгоритма являются оценки априорных вероятностей компонент смеси [math]w_{j}[/math], а также оценки векторов математических ожиданий и матриц ковариации для каждой компоненты.

EM-алгоритм позволяет значительно упростить задачу максимизации правдоподобия выборки путем искусственного введения вспомогательной матрицы скрытых переменных [math]G[/math]. Алгоритм заключается в последовательном повторении шагов E(expectation) и M(maximization):

• На шаге E на основе текущего приближения параметров смеси по формуле Байеса вычисляются ожидаемые значения скрытых переменных [math]g_{ij}[/math] — апостериорные вероятности того, что [math]i[/math]-й объект принадлежит кластеру [math]j[/math].
• На шаге M решается задача максимизации правдоподобия для нахождения следующего приближения параметров смеси на основе текущего приближения и матрицы скрытых переменных.

Рисунок 1. Визуализация компонент смеси после некоторых итераций алгоритма в двумерном пространстве признаков. Для каждой компоненты эллипсами выделены доверительные области с уровнями доверия 0.9, 0.95 и 0.99.