Участник:Александр Куваев/Алгоритм кластеризации, основанный на максимизации ожидания
Авторы описания: Куваев А.С. и Щенявская Е.В.
Свойства и структура алгоритмов
Общее описание алгоритма
Задача кластеризации заключается в разбиении входного множества объектов на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались друг от друга.
Решение этой задачи принципиально неоднозначно по следующим причинам:
- результат кластеризации зависит от способа задания меры сходства объектов выборки
- не существует однозначно наилучшего критерия качества кластеризации
- число кластеров, как правило, неизвестно заранее и задается из некоторых априорных соображений (хотя существуют алгоритмы, способные определять число кластеров автоматически)
По описанной выше причине существует большое число алгоритмов кластеризации, приводящих к различным разбиениям исходного множества объектов. На этой странице представлено описание одного из таких методов — EM-алгоритма. EM-алгоритм опирается на предположение о вероятностной природе данных: элементы выборки получены случайно и независимо из смеси распределений с фиксированным числом компонент [math]\displaystyle{ k }[/math]. Таким образом, плотность распределения на множестве объектов имеет следующий вид:
[math]\displaystyle{ p(x)=\sum_{j=1}^{k}w_{j}p_{j}(x), \sum_{j=1}^{k}w_{j}=1, w_{j} \ge 0 }[/math], где [math]\displaystyle{ p_{j} }[/math] - плотность распределения [math]\displaystyle{ j }[/math]-й компоненты смеси.
Везде в дальнейшем будем предполагать, что [math]\displaystyle{ p_{j} }[/math] имеют вид многомерных нормальных плотностей с произвольной матрицей ковариации: смеси нормальных распределений позволяют аппроксимировать произвольные непрерывные функции плотности с наперед заданной точностью. Результатом работы EM-алгоритма являются оценки априорных вероятностей компонент смеси [math]\displaystyle{ w_{j} }[/math], а также оценки векторов математических ожиданий и матриц ковариации для каждой компоненты.
EM-алгоритм позволяет значительно упростить задачу максимизации правдоподобия выборки путем искусственного введения вспомогательной матрицы скрытых переменных [math]\displaystyle{ G }[/math]. Алгоритм заключается в последовательном повторении шагов E(expectation) и M(maximization):
- На шаге E на основе текущего приближения параметров смеси по формуле Байеса вычисляются ожидаемые значения скрытых переменных [math]\displaystyle{ g_{ij} }[/math] — апостериорные вероятности того, что [math]\displaystyle{ i }[/math]-й объект принадлежит кластеру [math]\displaystyle{ j }[/math].
- На шаге M решается задача максимизации правдоподобия для нахождения следующего приближения параметров смеси на основе текущего приближения и матрицы скрытых переменных, при этом решение этой задачи выписывается в явном виде.
Математическое описание алгоритма
Пусть заданы [math]\displaystyle{ l }[/math] объектов [math]\displaystyle{ x_{1},...,x_{l} }[/math], каждый из которых описывается [math]\displaystyle{ n }[/math] числовыми признаками. Таким образом, определена матрица объектов-признаков [math]\displaystyle{ X \in \R^{l \times n} }[/math]. Предполагается, что объекты выбраны случайно и независимо из смеси [math]\displaystyle{ n }[/math]-мерных нормальных распределений с фиксированным числом компонент [math]\displaystyle{ k }[/math]. Плотность распределения на множестве объектов имеет вид:
[math]\displaystyle{ p(x)=\sum_{j=1}^{k}w_{j}p_{j}(x), \sum_{j=1}^{k}w_{j}=1, w_{j} \ge 0 }[/math], где [math]\displaystyle{ p_{j} }[/math] - плотность распределения [math]\displaystyle{ j }[/math]-й компоненты смеси.
Каждая компонента смеси описывается [math]\displaystyle{ n }[/math]-мерным вектором математических ожиданий [math]\displaystyle{ \mu_{j} }[/math] и матрицей ковариации [math]\displaystyle{ \Sigma_{j} }[/math] порядка [math]\displaystyle{ n }[/math], [math]\displaystyle{ j = 1...k }[/math].
Исходные данные: матрица объектов-признаков [math]\displaystyle{ X }[/math], число кластеров [math]\displaystyle{ k }[/math], максимальное число итераций [math]\displaystyle{ imax }[/math].
Вычисляемые данные: набор оценок весов, математических ожиданий и ковариационных матриц компонент смеси [math]\displaystyle{ \theta = (w_{1},...,w_{k}; \; \mu_{1},...,\mu_{k}; \; \Sigma_{1},...,\Sigma_{k}) }[/math].