Переходим к следующему алгоритму в рамках «Топ-10 data mining алгоритмов», а именно к EM-алгоритму.

В data mining алгоритм максимизации ожидания (expectation-maximization (EM) обычно используется как кластерный алгоритм (наподобие алгоритма к-средних) для обнаружения знаний.

В математической статистике EM-алгоритм считается итерационным и используется для оценки максимального правдоподобия при вычислении параметров статистической модели со скрытыми переменными.

Вот несколько концепций, которые сделают все проще.

Что такое статистическая модель? Модель можно представить как что-то, описывающее известные данные. Например, оценки за экзамен могут соответствовать нормальному распределению, поэтому предположение, что оценки генерируются в соответствии с нормальным распределением, является моделью.

А что такое распределение? Распределение представляет вероятности появления всех измеримых результатов. Например, оценки за экзамен могут соответствовать нормальному распределению. Это нормальное распределение представляет все вероятности получения той или иной оценки.

Другими словами, распределение помогает понять, сколько человек, сдающих экзамен, получат ту или иную оценку.

А что такое параметры модели? Параметр описывает распределение, которое является частью модели. Например, нормальное распределение описывается средним арифметическим и дисперсией.

В примере с экзаменом распределение оценок (измеримые исходы) вписывается в нормальное распределение. Среднее арифметическое равняется 85, а дисперсия – 100.

Для того, чтобы описать нормальное распределение, вам нужны всего два параметра:

1. Среднее арифметическое
2. Дисперсия

А правдоподобие? Возвращаясь к примеру с нормальным распределением.… Предположим, что у нас есть множество оценок. Однако мы знаем не все, а только часть из них.

Вот в чем суть:

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

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

Вы вероятно думаете, что же такое вероятность?

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

Если сказать простыми словами, то мы оцениваем возможные исходы на основании параметров.

А в чем отличие между данными наблюдений и скрытыми данными? Данные наблюдений – это данные, которые вы пронаблюдали или зафиксировали. Скрытые данные – это отсутствующие данные. Есть множество причин, почему они могут отсутствовать (не зафиксированы, проигнорированы и так далее).

Вот в чем загвоздка:

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

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

А теперь хорошие новости:

Оценивая максимальное правдоподобие, EM-алгоритм создает отличную модель, которая назначает метки класса точкам данных – прямо как в кластеризации.

Как EM помогает в кластеризации? EM-алгоритм начинает с того, что пытается сделать вывод на основании параметров модели.

Затем следует итерационный трёхшаговый процесс:

1. E-шаг: На этом шаге на основании параметров модели вычисляются вероятность принадлежности каждой точки данных к кластеру.
2. М-шаг: Обновляет параметры модели в соответствии с кластерным распределением, проведенным на шаге E.
3. Предыдущие два шага повторяются до тех пор, пока параметры модели и кластерное распределение не уравняются.

Требует ли этот метод обучения или он самообучающийся? Поскольку мы не предоставляли алгоритму маркированные данные, то это самообучающийся метод.

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

Это делает EM отличным методом для кластеризации и создания моделей с параметрами. Зная кластеры и параметры модели можно предполагать, что содержит кластер и куда стоит отнести новые данные.

Хотя и у EM-алгоритма есть свои недостатки:

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

Где он используется? EM-алгоритм реализован в Weka. R имеет реализацию в пакете mclust. В scikit-learn есть реализация EM в модуле gmm.

Источник

Алгоритм EM (видео)

Реализация EM-алгоритма в R

Как отмечалось выше, для реализации EM-алгоритма в R создана библиотека mclust (ссылка выше). Кроме того, для данной библиотеки могут понадобиться дополнительные библиотеки. В примерах используется набор faithful.

Пример 1

Комментарий: This is performed through the technique called Bayesian Information Criterion (BIC) that varies the number of cluster from 1 to 9. The BIC is the value of the maximized loglikelihood measured with a penalty for the number of parameters in the model

Пример 2

Дополнение: To do further analysis on the same dataset, for example to see the results for a different set of models and/or different numbers of components, Mclust could be rerun. However this approach could involve unnecessary repetition of computations and could also take considerable time when the dataset is large or the process is to be repeated many times. An alternative approach is to split the analysis into several parts using function mclustBIC.

Пример 3

Дополнительные примеры можно найти здесь.

Реализация EM-алгоритма в Python

В Питоне алгоритм реализован в модуле gmm в рамках scikit-learn (ссылка есть выше). Параметры и описание составных частей можно найти там же. Рассмотрим пример.