Участник:Sergey Lavrushkin/EM-алгоритм кластеризации: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 4: Строка 4:
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
 +
EM–алгоритм - алгоритм кластеризации, заключающийся в максимизации правдоподобия. Его название происходит от слов "expectation-maximization", что переводится как "ожидание-максимизация". Это связано с тем, что каждая итерация содержит два шага – вычисление математических ожиданий (expectation) и максимизацию (maximisation). Алгоритм основан на методике итеративного вычисления оценок максимального правдоподобия, предложенной в 1977 г. (A. P. Demster, N. M. Laird, D. B. Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm).
 +
В основе идеи EM-алгоритма лежит предположение, что исследуемое множество данных может быть смоделировано с помощью линейной комбинации многомерных нормальных распределений, а целью является оценка параметров распределения, которые максимизируют логарифмическую функцию правдоподобия, используемую в качестве меры качества модели. Иными словами, предполагается, что данные в каждом кластере подчиняются определенному закону распределения, а именно, нормальному распределению. С учетом этого предположения можно определить параметры - математическое ожидание и дисперсию, которые соответствуют закону распределения элементов в кластере, наилучшим образом ``подходящему'' к наблюдаемым данным.
 +
Таким образом, предполагается, что любое наблюдение принадлежит ко всем кластерам, но с разной вероятностью. Тогда задача будет заключаться в ``подгонке'' распределений смеси к данным, а затем в определении вероятностей принадлежности наблюдения к каждому кластеру. Наблюдение должно быть отнесено к тому кластеру, для которого данная вероятность выше.
 +
Алгоритм EM основан на вычислении расстояний. Он может рассматриваться как обобщение кластеризации на основе анализа смеси вероятностных распределений. В процессе работы алгоритма происходит итеративное улучшение решения, а остановка осуществляется в момент, когда достигается требуемый уровень точности модели. Мерой в данном случае является монотонно увеличивающаяся статистическая величина, называемая логарифмическим правдоподобием.
 +
=== Преимущества и недостатки алгоритма ===
 +
Среди преимуществ EM-алгоритма можно выделить следующие:
 +
\begin{itemize}
 +
\item Мощная статистическая основа.
 +
\item Линейное увеличение сложности при росте объема данных.
 +
\item Устойчивость к шумам и пропускам в данных.
 +
\item Возможность построения желаемого числа кластеров.
 +
\item Быстрая сходимость при удачной инициализации.
 +
\end{itemize}
 +
Однако алгоритм имеет и ряд недостатков. Во-первых, предположение о нормальности всех измерений данных не всегда выполняется. Во-вторых, при неудачной инициализации сходимость алгоритма может оказаться медленной. Кроме этого, алгоритм может остановиться в локальном минимуме и дать квазиоптимальное решение.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===

Версия 01:02, 12 октября 2016

Автор статьи: Сергей Лаврушкин (группа 620)

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

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

EM–алгоритм - алгоритм кластеризации, заключающийся в максимизации правдоподобия. Его название происходит от слов "expectation-maximization", что переводится как "ожидание-максимизация". Это связано с тем, что каждая итерация содержит два шага – вычисление математических ожиданий (expectation) и максимизацию (maximisation). Алгоритм основан на методике итеративного вычисления оценок максимального правдоподобия, предложенной в 1977 г. (A. P. Demster, N. M. Laird, D. B. Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm). В основе идеи EM-алгоритма лежит предположение, что исследуемое множество данных может быть смоделировано с помощью линейной комбинации многомерных нормальных распределений, а целью является оценка параметров распределения, которые максимизируют логарифмическую функцию правдоподобия, используемую в качестве меры качества модели. Иными словами, предполагается, что данные в каждом кластере подчиняются определенному закону распределения, а именно, нормальному распределению. С учетом этого предположения можно определить параметры - математическое ожидание и дисперсию, которые соответствуют закону распределения элементов в кластере, наилучшим образом ``подходящему к наблюдаемым данным. Таким образом, предполагается, что любое наблюдение принадлежит ко всем кластерам, но с разной вероятностью. Тогда задача будет заключаться в ``подгонке распределений смеси к данным, а затем в определении вероятностей принадлежности наблюдения к каждому кластеру. Наблюдение должно быть отнесено к тому кластеру, для которого данная вероятность выше. Алгоритм EM основан на вычислении расстояний. Он может рассматриваться как обобщение кластеризации на основе анализа смеси вероятностных распределений. В процессе работы алгоритма происходит итеративное улучшение решения, а остановка осуществляется в момент, когда достигается требуемый уровень точности модели. Мерой в данном случае является монотонно увеличивающаяся статистическая величина, называемая логарифмическим правдоподобием.

1.2 Преимущества и недостатки алгоритма

Среди преимуществ EM-алгоритма можно выделить следующие: \begin{itemize} \item Мощная статистическая основа. \item Линейное увеличение сложности при росте объема данных. \item Устойчивость к шумам и пропускам в данных. \item Возможность построения желаемого числа кластеров. \item Быстрая сходимость при удачной инициализации. \end{itemize} Однако алгоритм имеет и ряд недостатков. Во-первых, предположение о нормальности всех измерений данных не всегда выполняется. Во-вторых, при неудачной инициализации сходимость алгоритма может оказаться медленной. Кроме этого, алгоритм может остановиться в локальном минимуме и дать квазиоптимальное решение.

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература