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

EM-алгоритм кластеризации
Последовательный алгоритм
Последовательная сложность	$O(n * m^2 * k)$ - одна итерация
Объём входных данных	$n * m + 1$
Объём выходных данных	$n$
Параллельный алгоритм
Высота ярусно-параллельной формы
Ширина ярусно-параллельной формы

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

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

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

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

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

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

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

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

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

Использование алгоритма EM подразумевает следующее предположение об объектах:

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

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

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

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

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

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

$N$ - количество объектов, $K$ - количество кластеров, $M$ - количество параметров объекта

$\gamma_{n,k}$ - значения скрытых переменных

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

$x_{1},...,x_n$ - объекты

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

$w_{1},...,w_{k}$ - вероятности появления объектов из кластеров (веса кластеров), $\sum_{k=1}^Kw_{k}=1$

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

$\Sigma_{1},...,\Sigma_{k}$ - матрицы ковариации гауссиан кластеров, каждая матрица имеет размерность $M$x$M$

Смесь распределений:

$P(x) = \sum_{j=1}^Kw_jp(x|\mu_{j}, \Sigma_{j})$

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

$\ln P(x|w,\mu,\Sigma)= \sum_{n=1}^N \ln \{ \sum_{k=1}^K w_{k}p(x_{n}|\mu_{k},\Sigma_{k})\}$.

• В начале работы алгоритма задаются параметры начального приближения:

$w_{i} = 1/K, \mu_{i} = random(x_{j}), i=1..K, j=1..N$ $\Sigma_{j,j}^{k}=\frac{1}{NK}\sum_{i=1}^N(x_{i,j} - \mu_{k,j})^2, k=1..K, j=1..M$

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

• Далее итеративно выполняется следующая пара процедур:
  • E-шаг: используя текущее значение параметров $w_{1},...,w_{k};\mu_{1},...,\mu_{k};\Sigma^{1},...,\Sigma^{k}$, вычисляем значение вектора скрытых переменных $\gamma$:$\gamma_{n,k}=\frac{w_{k}p(x_{n}|\mu_{k},\Sigma^{k})}{\sum_{j=1}^K w_{j}p(x_{n}|\mu_{j},\Sigma^{j})},$ знаменатель дроби - нормировочный коэффициент$p(x|\mu,\Sigma)=\frac{1}{{(2\pi)}^{\frac{N}{2}}\sqrt{|\Sigma|}}exp\biggl\{-\frac{1}{2}{(x-\mu)}^T{\Sigma}^{-1}(x-\mu)\biggr\}$ - плотность $N$-мерного нормального распределения
  • М-шаг: переоценка параметров по текущим значениям скрытых переменных для $k = 1..K$:

$\mu^{new}_{k}=\frac{1}{N_{k}}\sum_{n=1}^N \gamma_{n,k}x_{n}$, $\Sigma_{new}^{k}=\frac{1}{N_{k}}\sum_{n=1}^N \gamma_{n,k} (x_{n}-\mu_{k}^{new})(x_{n}-\mu_{k}^{new})^{T}$, $w_{k}^{new}=\frac{N_{k}}{N}$, $N_{k}=\sum_{n=1}^N \gamma_{n,k}$.

В EM алгоритме используется один из следующих критериев остановки:

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

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

Вычислительное ядро алгоритма состоит из двух шагов, повторяющихся каждую итерацию:

• Обновление скрытых переменных на основе текущих параметров распределений
• Обновление параметров кластеров: весов, центров и матриц ковариации

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

Как записано в описании вычислительного ядра алгоритма, основную часть алгоритма составляют итеративно проводимые макрооперации: Expectation шаг - вычисление новых значений скрытых переменных, Maximization шаг - обновление параметров кластеров. Макроструктура алгоритма представлена на рисунке 1:

Рисунок 1: Макроструктура EM-алгоритма

1.5 Схема реализации последовательного алгоритма

Примерная схема реализации EM алгоритма с предварительной обработкой матриц ковариации:

// n - количество объектов

// m - количество координат объектов

// k - количество кластеров

Инициализировать веса и центры кластеров;
Инициализировать матрицы ковариации;

// Основной цикл
Пока условие остановки не выполнено
    // E-шаг
    В цикле для каждого кластера
        Вычислить определитель матрицы ковариации Sigma;
        Вычислить обратную матрицу матрице Sigma;
    В цикле для каждого объекта
        В цикле для каждого кластера
            Вычислить и запомнить p(x | mu, Sigma) для текущего объекта и кластера;
            Просуммировать вычисленные p(x | mu, Sigma);
        В цикле для каждого кластера
            Обновить скрытые переменные gamma;
    // M-шаг
    Обновить веса w;
    Обновить центры кластеров mu;
    Обновить матрицы ковариации Sigma;

1.6 Последовательная сложность алгоритма

Количество итераций алгоритма зависит от условия остановки, поэтому будем рассматривать сложность одной итерации.

Шаг E

Сложность вычисления определителя произвольной матрицы ковариации $\Sigma$ методом Гаусса - $O(m^3)$;

Сложность вычисления матрицы, обратной произвольной матрице ковариации $\Sigma$ методом Гаусса - $O(m^3)$;

Сложность предварительного вычисления определителей и обратных матриц матрицам ковариации - $O(k * m^3)$

С учетом заранее вычисленных определителей и обратных матриц сложность вычисления $p(x | \mu,\Sigma)$ составит: $O(m^2)$;

Суммарно сложность шага E составит $O(n * m^2 * k + k * m^3)$

Шаг M

Сложность обновления весов кластеров $O(k * n)$;

Сложность обновления центров кластеров $O(k * m * n)$;

Сложность обновления одной матрицы ковариации $O(n * m)$;

Сложность обновления всех матриц ковариации $O(k * m * n)$;

Суммарно сложность шага M алгоритма - $O(k * m * n)$;

Таким образом, сложность одной итерации EM алгоритма для псевдокода, указанного в предыдущем разделе, составит $O(k * m^2 * n + k * m^3 + k * m * n)$.

В предположении, что размерность объектов много меньше их количества $m \lt \lt n$ получим сложность итерации $O(k * m^2 * n)$.

Нетрудно заметить, что вычисление определителя и обратной матрицы к произвольной матрице ковариации составляет большУю часть работы шага E и существенно влияет на его сложность. Поэтому эти вычисления проведены заранее - вынесены за основной цикл шага E. Помимо этого сложность этих вычислений можно сократить еще сильнее, если ввести ограничения структуру матрицы ковариации $\Sigma$.

Наиболее часто используемым ограничением, позволяющим эффективно распараллеливать алгоритм, является предположение, что матрица ковариации имеет диагональную форму. Тогда вычисление её определителя и обратной матрицы имеет сложнось $O(m)$, а суммарная сложность шага E и сложность всей итерации составит $O(k * m * n)$.

1.7 Информационный граф

Макроструктура алгоритма представлена на рисунке 1 (см. раздел 1.4 статьи).

На рисунке 2 представлена схема вычислений E-шага алгоритма для одного объекта: для объекта $x_{i}$ и параметров $w_{j}, \mu_{j}, \Sigma_{j}, j=1..k$ по формулам раздела 1.2 вычисляются ненормированные значения скрытых переменных $g_{j}$, нормировочный коэффициент normСoeff, и получаются итоговые значения $\gamma_{i,j}$.

Рисунок 2: E-шаг EM алгоритма для одного объекта

На рисунке 3 представлена схема вычислений E-шага алгоритма для всех объектов: для объекта $x_{j}$ и параметров-векторов $w, \mu, \Sigma$ по формулам раздела 1.2 вычисляются значения скрытых переменных. $E_{i}, i=1..n$ - маркооперации, E-шаги для соответствующих объектов.

Рисунок 3: E-шаг EM алгоритма для всех объектов

На рисунке 4 представлена схема вычислений M-шага алгоритма для одного кластера: для объектов $x_{i}$ и скрытых переменных $\gamma_{i,j}$, соответствующих степени принадлежности этих объектов кластеру $j$, согласно формулам шага M раздела 1.2 вычисляется нормировочный коэффициент $N_{j}$ и параметры этого кластера: вес $w_{j}^{new}$, матрица ковариации $\Sigma_{j}^{new}$ и центр кластера $\mu_{j}^{new}$.

Рисунок 4: M-шаг EM алгоритма для одного кластера

На рисунке 5 представлена схема вычислений M-шага алгоритма для всех кластеров. $M_{j}, j=1..k$ соответствует макрооперации - M-шагу для соответствующего кластера и скрытых переменных.

Рисунок 5: M-шаг EM алгоритма для всех кластеров

1.8 Ресурс параллелизма алгоритма

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

Как правило количество кластеров, на которые нужно разбить объекты, несравнимо меньше количества объектов, поэтому распараллеливание в большинстве существующих реализаций происходит по объектам: обработка объектов по возможности равномерно распределяются по кластерам. Теоретически (если считать передачу данных между процессорами мгновенной) при наличии неограниченного числа процессоров сложность алгоритма составит $O(m^2 * k)$.

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

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

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

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

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

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

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

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

• $n$ целых неотрицательных чисел.

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

1.10.1 Преимущества и недостатки

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

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

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

Недостатки:

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

1.10.2 Влияние структуры матрицы ковариации на форму кластера

Рисунок 6: Влияние структуры матрицы ковариации на форму кластеров для двумерного случая. a) - матрицы ковариации являются диагональными, b) - матрицы ковариации произвольны.

Рисунок 6 наглядно показывает, что при диагональной форме матриц ковариации полуоси эллипса (в общем случае - эллипсоида), соответствующего распределению объектов, отнесенных кластеру, параллельны осям координат объектов. В противном случае полуоси могут располагаться произвольным образом.

1.10.3 Общие свойства

Вычислительная мощность EM алгоритма равна $m * k * it$, где $m$ - размерность объекта, $k$ - количество кластеров, а $it$ - количество итераций.

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

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

Многие статьи, в которых представлены параллельные реализации EM алгоритма, описывают помимо использующихся программных и аппаратных решений результаты проведенных экспериментов с данными. В качестве примера в этом разделе будут рассмотрены результаты эксперементов, проведенных со связующим программным обеспечением (middleware) FREERIDE (FRamework for Rapid Implementation of Datamining Engines), обеспечивающим возможность распараллеливания как для систем с общей памятью (в частности, симметричных мультипроцессорных систем), так и для систем с распределенной памятью.

Эксперименты проводились на кластере машин Pentium 700MHz связанных при помощи Myrinet LANai 7.0 на трех наборах данных:

а) 3.3 * 10^6 объектов

b) 6.2 * 10^6 объектов

c) 12.5 * 10^6 объектов

Объекты представляют собой координаты точек 10-мерного пространства.

Количество машин в кластере варьировалось от 1 до 8, при этом на каждой машине запускалось до четырех параллельных потоков.

Результаты экспериментов представлены на рисунках 7-9:

Рисунок 7: набор данных a)

Рисунок 8: набор данных b)

Рисунок 9: набор данных c)

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

Данный раздел считается незавершенным и может дополняться

2.7 Существующие реализации алгоритма

Примеры библиотек, содержащих последовательную реализацию EM-алгоритма, или отдельных реализаций:

1. OpenCV(C++) (github)
2. Matlab
3. Scikit learn (Python)
4. MLPack(C++)

Примеры библиотек, содержащих параллельную реализацию EM-алгоритма, или отдельных реализаций:

Здесь приводятся как конкретные реализации, так и статьи, описывающие подходы к реализациям распараллеливания EM-алгоритма

1. Apache Spark
2. Accord.NET Framework (C#)
3. статья Parallelizing EM Clustering Algorithm on a Cluster of SMPs
4. реализация с использованием CUDA
5. еще одна реализация с использованием CUDA
6. статья The Parallel EM Algorithm and its Applications in Computer Vision

3 Литература

[9] http://web.cse.ohio-state.edu/~agrawal/allpapers/europar04.pdf

[10] http://www.cs.kent.edu/~jin/Papers/JPDC08.pdf

[11] http://w01fe.com/berkeley/pubs/08-icml-em.pdf

[12] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.8470&rep=rep1&type=pdf

[13] https://arxiv.org/pdf/1606.02054.pdf