EM-алгоритм — различия между версиями
(Поправил нерабочую ссылку на Определение) |
м (rollbackEdits.php mass rollback) |
||
(не показано 8 промежуточных версий 2 участников) | |||
Строка 12: | Строка 12: | ||
# Задачи с неполными данными. | # Задачи с неполными данными. | ||
− | # Задачи, в которых удобно вводить скрытые переменные для упрощения подсчета функции правдоподобия. Примером такой задачи может служить кластеризация | + | # Задачи, в которых удобно вводить скрытые переменные для упрощения подсчета функции правдоподобия. Примером такой задачи может служить кластеризация. |
== Основной алгоритм == | == Основной алгоритм == | ||
Строка 19: | Строка 19: | ||
Плотность распределения смеси имеет вид:<br/> | Плотность распределения смеси имеет вид:<br/> | ||
− | <tex>p(x) = \sum\limits_{j=1}^k w_j p_j(x)</tex><br/> | + | <tex>p(x) = \sum\limits_{j=1}^k w_j p_j(x)</tex>.<br/> |
Где <tex> \sum\limits_{j=1}^k w_j = 1; w_j \geq 0; p_j(x) = \phi(x;\theta_j)</tex> {{---}} функция правдоподобия <tex>j</tex>-ой компонеты смеси, <tex>w_j</tex> {{---}} априорная вероятность <tex>j</tex>-ой компоненты смеси.<br/> | Где <tex> \sum\limits_{j=1}^k w_j = 1; w_j \geq 0; p_j(x) = \phi(x;\theta_j)</tex> {{---}} функция правдоподобия <tex>j</tex>-ой компонеты смеси, <tex>w_j</tex> {{---}} априорная вероятность <tex>j</tex>-ой компоненты смеси.<br/> | ||
Перед нами стоит две задачи:<br/> | Перед нами стоит две задачи:<br/> | ||
− | # По заданной выборке <tex>X^m</tex> случайных и независимых наблюдений полученных из смеси <tex>p(x)</tex>, числу <tex>k</tex> и функции <tex>\phi</tex>, оценить вектор параметров <tex>\Theta = (w_1,..,w_k,\theta_1,..,\theta_k)</tex> | + | # По заданной выборке <tex>X^m</tex> случайных и независимых наблюдений полученных из смеси <tex>p(x)</tex>, числу <tex>k</tex> и функции <tex>\phi</tex>, оценить вектор параметров <tex>\Theta = (w_1,..,w_k,\theta_1,..,\theta_k)</tex>. |
− | # Найти <tex>k</tex> | + | # Найти <tex>k</tex>. |
=== Проблема === | === Проблема === | ||
Задачи подобного рода мы умеем решать, максимизируя логармиф правдоподобия:<br> | Задачи подобного рода мы умеем решать, максимизируя логармиф правдоподобия:<br> | ||
− | <tex> | + | <tex> Q(\Theta) = ln \prod\limits_{i=1}^mp(x_i) = \sum\limits_{i=1}^m ln\sum\limits_{j=1}^k w_j p_j(x_i; \theta_j) \longrightarrow \max\limits_{\Theta}</tex>.<br/> |
− | Но | + | Но проблeма в том, что мы не знаем как аналитически посчитать логарифм суммы. Тут нам и поможет алгоритм EM. |
=== Решение === | === Решение === | ||
− | Основная идея алгоритма EM заключается в том, что мы | + | Основная идея алгоритма EM заключается в том, что мы добавляем скрытые переменные такие, что:<br/> |
− | # Они могут быть выражены через <tex>\Theta</tex> | + | # Они могут быть выражены через <tex>\Theta</tex>. |
− | # Они помогают разбить сумму так: <tex>p (X, H|\Theta) = \prod\limits_{i=1}^k p (X|H, \Theta) p(H|\Theta)</tex>, где <tex>H</tex> - матрица скрытых переменных. | + | # Они помогают разбить сумму так: <tex>p (X, H|\Theta) = \prod\limits_{i=1}^k p (X|H, \Theta) p(H|\Theta)</tex>, где <tex>H</tex> {{---}} матрица скрытых переменных. |
Тогда алгоритм EM сводится к повторению шагов, указанных в [[#Определение|Определении]]. | Тогда алгоритм EM сводится к повторению шагов, указанных в [[#Определение|Определении]]. | ||
Строка 45: | Строка 45: | ||
=== E-шаг === | === E-шаг === | ||
− | <tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex> <br /> | + | <tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex>.<br /> |
− | Скрытые переменные представляют из себя матрицу <tex>H = (h_{ij})_{m \times k}</tex><br/> | + | Скрытые переменные представляют из себя матрицу <tex>H = (h_{ij})_{m \times k}</tex>,<br/> |
где <tex>h_{ij} = P(\theta_j | x_i)</tex> {{---}} вероятность того, что <tex>x_i</tex> пренадлежит <tex>j</tex>-ой компоненте.<br/> | где <tex>h_{ij} = P(\theta_j | x_i)</tex> {{---}} вероятность того, что <tex>x_i</tex> пренадлежит <tex>j</tex>-ой компоненте.<br/> | ||
По формуле Байеса справедливо равенство:<br /> | По формуле Байеса справедливо равенство:<br /> | ||
− | <tex> h_{ij} = \frac{w_jp_j(x_i)}{p (x_i)} = \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^k w_s p_s(x_i)}</tex><br/> | + | <tex> h_{ij} = \frac{w_jp_j(x_i)}{p (x_i)} = \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^k w_s p_s(x_i)}</tex>.<br/> |
− | Также <tex>\sum\limits_{j=1}^k h_{ij} = 1</tex><br/> | + | Также <tex>\sum\limits_{j=1}^k h_{ij} = 1</tex>.<br/> |
− | Таким образом, зная значения вектора параметров <tex>\Theta</tex>, мы легко можем пересчитать значения скрытых переменных<br/> | + | Таким образом, зная значения вектора параметров <tex>\Theta</tex>, мы легко можем пересчитать значения скрытых переменных.<br/> |
=== M-шаг === | === M-шаг === | ||
Строка 62: | Строка 62: | ||
|statement= | |statement= | ||
Если известны скрытые переменные, то задача минимизации <tex>Q(\Theta)</tex> сводится к <tex>k</tex> независимым подзадачам:<br/> | Если известны скрытые переменные, то задача минимизации <tex>Q(\Theta)</tex> сводится к <tex>k</tex> независимым подзадачам:<br/> | ||
− | <center><tex>\theta_j = \arg\max\limits_{\theta}\sum\limits_{i=1}^m h_{ij}*\ln\phi(x_i;\theta)</tex></center> | + | <center><tex>\theta_j = \arg\max\limits_{\theta}\sum\limits_{i=1}^m h_{ij}*\ln\phi(x_i;\theta)</tex>.</center> |
Оптимальные же веса считаются как:<br/> | Оптимальные же веса считаются как:<br/> | ||
− | <center><tex> w_j = \frac {1} {m} \sum\limits_{i=1}^m h_{ij}</tex></center> | + | <center><tex> w_j = \frac {1} {m} \sum\limits_{i=1}^m h_{ij}</tex>.</center> |
|proof= | |proof= | ||
Посчитаем логарифм правдоподобия:<br> | Посчитаем логарифм правдоподобия:<br> | ||
− | <tex> Q(\Theta) = \sum\limits_{i=1}^m ln\sum\limits_{j=1}^k w_j p_j(x_i; \theta_j) \longrightarrow \max\limits_{\Theta}</tex><br/> | + | <tex> Q(\Theta) = \sum\limits_{i=1}^m ln\sum\limits_{j=1}^k w_j p_j(x_i; \theta_j) \longrightarrow \max\limits_{\Theta}</tex>.<br/> |
При условии, что<tex> \sum\limits_{j=1}^k w_j = 1; w_j \geq 0</tex> имеет смысл рассматривать Лагранжиан задачи:<br/> | При условии, что<tex> \sum\limits_{j=1}^k w_j = 1; w_j \geq 0</tex> имеет смысл рассматривать Лагранжиан задачи:<br/> | ||
− | <tex> L(\Theta, X^m) = \sum\limits_{i=1}^m ln \biggl( \sum\limits_{j=1}^k w_j p_j(x_i) \biggr) - \lambda \biggl(\sum\limits_{j=1}^k w_j - 1 \biggr) </tex><br/> | + | <tex> L(\Theta, X^m) = \sum\limits_{i=1}^m ln \biggl( \sum\limits_{j=1}^k w_j p_j(x_i) \biggr) - \lambda \biggl(\sum\limits_{j=1}^k w_j - 1 \biggr) </tex>.<br/> |
Приравняв нулю производную Лагранжиана по <tex>w_j</tex>, получим:<br/> | Приравняв нулю производную Лагранжиана по <tex>w_j</tex>, получим:<br/> | ||
− | <tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{p_j(x_i)}{\sum\limits_{s=1}^kw_s p_s(x_i)} - \lambda = 0, j = 1..k</tex><br /> | + | <tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{p_j(x_i)}{\sum\limits_{s=1}^kw_s p_s(x_i)} - \lambda = 0, j = 1..k</tex>.<br/> |
− | Умножим на <tex>w_j</tex> и просуммируем уравнения для всех <tex>j</tex> <br /> | + | Умножим на <tex>w_j</tex> и просуммируем уравнения для всех <tex>j</tex>:<br /> |
− | <tex>\sum\limits_{j=1}^k \sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_s p_s(x_i)} = \lambda \sum\limits_{j=1}^kw_j</tex> <br /> | + | <tex>\sum\limits_{j=1}^k \sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_s p_s(x_i)} = \lambda \sum\limits_{j=1}^kw_j</tex>.<br /> |
− | А так как <tex>\sum\limits_{j=1}^k \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_sp_s(x_i)} = 1</tex> и <tex>\sum\limits_{j=1}^kw_j = 1</tex>, из чего следует <tex>\lambda = m</tex> <br /> | + | А так как <tex>\sum\limits_{j=1}^k \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_sp_s(x_i)} = 1</tex> и <tex>\sum\limits_{j=1}^kw_j = 1</tex>, из чего следует <tex>\lambda = m</tex>.<br /> |
− | <tex>w_j = \frac{1}{m}\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_sp_s(x_i)} = \frac{1}{m}\sum\limits_{i=1}^m h_{ij}</tex><br /> | + | <tex>w_j = \frac{1}{m}\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_sp_s(x_i)} = \frac{1}{m}\sum\limits_{i=1}^m h_{ij}</tex>.<br /> |
Приравняв к нулю производную Лагранжиана по <tex>\theta_j</tex>, схожим способом найдем:<br /> | Приравняв к нулю производную Лагранжиана по <tex>\theta_j</tex>, схожим способом найдем:<br /> | ||
Строка 87: | Строка 87: | ||
=== Критерий остановки === | === Критерий остановки === | ||
− | Алгоритм EM | + | Алгоритм EM выполняется до сходимости, но как нам определить, что сходимость наступила? Мы можем останавливаться, когда либо <tex>Q(\Theta)</tex>, либо <tex>H</tex> перестают сильно меняться. Но, обычно, удобней контролировать изменения значений скрытых переменных, так как они имеют смысл вероятностей и принимают значения из отрезка <tex>[0,1]</tex>. Поэтому один из возможных критериев остановки будет выглядеть так: <tex>\max\limits_{i,j} |h_{ij} - h_{ij}^{(0)}| > \delta</tex>. |
=== Псевдокод === | === Псевдокод === | ||
Строка 105: | Строка 105: | ||
Плюсы:<br/> | Плюсы:<br/> | ||
− | * Сходится в большинтсве случаев | + | * Сходится в большинтсве случаев. |
− | * Наиболее гибкое решение | + | * Наиболее гибкое решение. |
− | * Существуют простые модификации, позволяющие уменьшить чуствительность алгоритма к шуму в данных | + | * Существуют простые модификации, позволяющие уменьшить чуствительность алгоритма к шуму в данных. |
Минусы:<br/> | Минусы:<br/> | ||
− | * Чуствителен к начальному приближению. Могут быть ситуации, когда сойдемся к локальному экстремуму | + | * Чуствителен к начальному приближению. Могут быть ситуации, когда сойдемся к локальному экстремуму. |
− | * Число компонент <tex>k</tex> является гиперпараметром. | + | * Число компонент <tex>k</tex> является [[Настройка_гиперпараметров|гиперпараметром]]. |
== Модификации == | == Модификации == | ||
− | Базовый алгоритм EM является очень гибким для модификаций, позволяющих улучшить его работу. В этом разделе мы приведем краткое | + | Базовый алгоритм EM является очень гибким для модификаций, позволяющих улучшить его работу. В этом разделе мы приведем краткое описание некоторых из них. |
=== Generalized EM-algorithm === | === Generalized EM-algorithm === | ||
Строка 124: | Строка 124: | ||
=== Stochastic EM-algorithm === | === Stochastic EM-algorithm === | ||
− | Как уже было отмечено в [[#Плюсы_и_минусы|Плюсы и минусы]], базовый алгоритм чувствителен к начальному приближению и могут быть ситуации, когда алгоритм "застрянет" в | + | Как уже было отмечено в [[#Плюсы_и_минусы|Плюсы и минусы]], базовый алгоритм чувствителен к начальному приближению и могут быть ситуации, когда алгоритм "застрянет" в локальном экстремуме. Для того, чтобы предотвратить это, будем на каждой итерации алгоритма случайно "встряхивать" выборку. В этой модификации у нас добавляется шаг S, на котором мы и будем "встряхивать" выборку. И на шаге M мы будем решать уже задачу максимуму невзвешенного правдоподобия. Эта модификация хороша тем, что нечуствиетльная к начальном приблежению. |
== Пример. Разделение смеси Гауссиана == | == Пример. Разделение смеси Гауссиана == | ||
Строка 133: | Строка 133: | ||
<tex>\theta = (w_1,..,w_k;\;\mu_1,..,\mu_k;\;\sigma_1,..,\sigma_k)</tex> {{---}} вектор параметров, <br/> | <tex>\theta = (w_1,..,w_k;\;\mu_1,..,\mu_k;\;\sigma_1,..,\sigma_k)</tex> {{---}} вектор параметров, <br/> | ||
− | <tex>p_j(x) = N(x;\mu_j, \sigma_j) = \frac1{\sqrt{2\pi}\sigma_j} \exp \biggl(-\frac{(x - \mu_j)^2}{2\sigma_j^2}\biggr) </tex> - плотность распределения <br/> | + | <tex>p_j(x) = N(x;\mu_j, \sigma_j) = \frac1{\sqrt{2\pi}\sigma_j} \exp \biggl(-\frac{(x - \mu_j)^2}{2\sigma_j^2}\biggr) </tex> {{---}} плотность распределения.<br/> |
Посчитаем значения для каждого шага. <br/> | Посчитаем значения для каждого шага. <br/> | ||
Строка 139: | Строка 139: | ||
E-шаг: | E-шаг: | ||
− | : <tex> h_{ij} = \frac{w_j N(x_i, \mu_j, \sigma_j)}{\sum\limits_{s=1}^k w_s N(x_i, \mu_s, \sigma_s)} </tex> | + | : <tex> h_{ij} = \frac{w_j N(x_i, \mu_j, \sigma_j)}{\sum\limits_{s=1}^k w_s N(x_i, \mu_s, \sigma_s)}.</tex> |
M-шаг: | M-шаг: | ||
− | : <tex>w_j = \frac{1}{m} \sum\limits_{i=1}^m h_{ij}</tex> | + | : <tex>w_j = \frac{1}{m} \sum\limits_{i=1}^m h_{ij}.</tex> |
− | : <tex> \mu_j = \frac {1} {mw_j} \sum\limits_{i=1}^m h_{ij}x_i</tex> | + | : <tex> \mu_j = \frac {1} {mw_j} \sum\limits_{i=1}^m h_{ij}x_i.</tex> |
− | : <tex> \sigma_j^2 = \frac {1} {mw_j} \sum\limits_{i=1}^m h_{ij}(x_i - \mu_j)^2, j = 1..k</tex> | + | : <tex> \sigma_j^2 = \frac {1} {mw_j} \sum\limits_{i=1}^m h_{ij}(x_i - \mu_j)^2, j = 1..k.</tex> |
== Использование в задаче кластеризации == | == Использование в задаче кластеризации == | ||
Строка 151: | Строка 151: | ||
[[Файл:kmeans.jpg|right|thumb|200px|Пример работы k-means]] | [[Файл:kmeans.jpg|right|thumb|200px|Пример работы k-means]] | ||
− | Как уже упоминалось в [[#Определение|Определении]], алгоритм EM подходит для решения задачи кластеризации. И одной из его имплементаций для этой задачи является алгоритм <tex>k</tex>- | + | Как уже упоминалось в [[#Определение|Определении]], алгоритм EM подходит для решения задачи кластеризации. И одной из его имплементаций для этой задачи является алгоритм [[Алгоритм_k-Means|<tex>k</tex>-Means]]. В этом алгоритме в качестве скрытых переменных выступают метки классов объектов. Параметрами же являются центроиды искомых классов. Тогда на шаге E мы относим объекты к какому-то одному классу на основе расстояний до центроид. А на шаге M мы пересчитываем центроиды кластеров, исходя из полученной на шаге E разметке.<br/> |
− | Также стоит упомянуть алгоритм <tex>c</tex>-means. В нем качестве скрытых переменных выступают вероятности принадлежности объекта к классам. На шаге E мы пересчитывем вероятности принадлежности объектов, иходя из расстояния до центроид. Шаг M, идейно, остается без изменений. | + | Также стоит упомянуть алгоритм <tex>c</tex>-means<ref>[https://en.wikipedia.org/wiki/Fuzzy_clustering#Fuzzy_C-means_clustering C-means clustering, Wikipedia]</ref>. В нем качестве скрытых переменных выступают вероятности принадлежности объекта к классам. На шаге E мы пересчитывем вероятности принадлежности объектов, иходя из расстояния до центроид. Шаг M, идейно, остается без изменений. |
Строка 240: | Строка 240: | ||
*[[Кластеризация]] | *[[Кластеризация]] | ||
*[[Алгоритм_k-Means|Алгоритм k-Means]] | *[[Алгоритм_k-Means|Алгоритм k-Means]] | ||
+ | |||
+ | ==Примечания== | ||
+ | <references /> | ||
== Источники информации == | == Источники информации == | ||
Строка 249: | Строка 252: | ||
# [http://dendroid.sk/2011/05/09/k-means-clustering/ k-means] | # [http://dendroid.sk/2011/05/09/k-means-clustering/ k-means] | ||
− | [[Категория:Машинное обучение]] | + | [[Категория: Машинное обучение]] |
+ | [[Категория: Кластеризация]] |
Текущая версия на 19:36, 4 сентября 2022
Определение
Алгоритм EM (англ. expectation-maximization) — итеративный алгоритм поиска оценок максимума правдоподобия модели, в ситуации, когда она зависит от скрытых (ненаблюдаемых) переменных.
Алгоритм ищет параметры модели итеративно, каждая итерация состоит из двух шагов:
E (Expectation) шаг — поиск наиболее вероятных значений скрытых переменных.
M (Maximization) шаг — поиск наиболее вероятных значений параметров, для полученных на шаге E значений скрытых переменных.
EM алгоритм подходит для решения задач двух типов:
- Задачи с неполными данными.
- Задачи, в которых удобно вводить скрытые переменные для упрощения подсчета функции правдоподобия. Примером такой задачи может служить кластеризация.
Основной алгоритм
Постановка задачи
Плотность распределения смеси имеет вид:
.
Где — функция правдоподобия -ой компонеты смеси, — априорная вероятность -ой компоненты смеси.
Перед нами стоит две задачи:
- По заданной выборке случайных и независимых наблюдений полученных из смеси , числу и функции , оценить вектор параметров .
- Найти .
Проблема
Задачи подобного рода мы умеем решать, максимизируя логармиф правдоподобия:
.
Но проблeма в том, что мы не знаем как аналитически посчитать логарифм суммы. Тут нам и поможет алгоритм EM.
Решение
Основная идея алгоритма EM заключается в том, что мы добавляем скрытые переменные такие, что:
- Они могут быть выражены через .
- Они помогают разбить сумму так: , где — матрица скрытых переменных.
Тогда алгоритм EM сводится к повторению шагов, указанных в Определении.
E-шаг
Скрытые переменные представляют из себя матрицу
где — вероятность того, что пренадлежит -ой компоненте.
По формуле Байеса справедливо равенство:
.
Также
Таким образом, зная значения вектора параметров
M-шаг
Теорема: |
Если известны скрытые переменные, то задача минимизации сводится к независимым подзадачам:Оптимальные же веса считаются как: |
Доказательство: |
Посчитаем логарифм правдоподобия:
Приравняв к нулю производную Лагранжиана по |
Критерий остановки
Алгоритм EM выполняется до сходимости, но как нам определить, что сходимость наступила? Мы можем останавливаться, когда либо
, либо перестают сильно меняться. Но, обычно, удобней контролировать изменения значений скрытых переменных, так как они имеют смысл вероятностей и принимают значения из отрезка . Поэтому один из возможных критериев остановки будет выглядеть так: .Псевдокод
Input:Repeat E-step: for all i = 1..m; j = 1..k: M-step: for all j = 1..k: Until a stopping criterion is satisfied Return
Плюсы и минусы
Плюсы:
- Сходится в большинтсве случаев.
- Наиболее гибкое решение.
- Существуют простые модификации, позволяющие уменьшить чуствительность алгоритма к шуму в данных.
Минусы:
- Чуствителен к начальному приближению. Могут быть ситуации, когда сойдемся к локальному экстремуму.
- Число компонент гиперпараметром. является
Модификации
Базовый алгоритм EM является очень гибким для модификаций, позволяющих улучшить его работу. В этом разделе мы приведем краткое описание некоторых из них.
Generalized EM-algorithm
Осоновная идея этой модификации заключается в том, что на шаге M мы не будем пытаться найти наилучшее решение. Это применимо в случаях, когда максимизация
является сликшом дорогой, поэтому нам достаточно сделать лишь несколько итераций, для того, чтобы сместиться в сторону максимума значения . Эта модификация имеет неплохую сходимость.Stochastic EM-algorithm
Как уже было отмечено в Плюсы и минусы, базовый алгоритм чувствителен к начальному приближению и могут быть ситуации, когда алгоритм "застрянет" в локальном экстремуме. Для того, чтобы предотвратить это, будем на каждой итерации алгоритма случайно "встряхивать" выборку. В этой модификации у нас добавляется шаг S, на котором мы и будем "встряхивать" выборку. И на шаге M мы будем решать уже задачу максимуму невзвешенного правдоподобия. Эта модификация хороша тем, что нечуствиетльная к начальном приблежению.
Пример. Разделение смеси Гауссиана
Каноническим примером использования EM алгоритма является задача разделения смеси гауссиана. Данные у нас получены из нормального распределения. В этом случае параметрами функций ялвяются матожидание и дисперсия.
— плотность распределения.
Посчитаем значения для каждого шага.
E-шаг:
M-шаг:
Использование в задаче кластеризации
Как уже упоминалось в Определении, алгоритм EM подходит для решения задачи кластеризации. И одной из его имплементаций для этой задачи является алгоритм . В этом алгоритме в качестве скрытых переменных выступают метки классов объектов. Параметрами же являются центроиды искомых классов. Тогда на шаге E мы относим объекты к какому-то одному классу на основе расстояний до центроид. А на шаге M мы пересчитываем центроиды кластеров, исходя из полученной на шаге E разметке. -Means
Также стоит упомянуть алгоритм [1]. В нем качестве скрытых переменных выступают вероятности принадлежности объекта к классам. На шаге E мы пересчитывем вероятности принадлежности объектов, иходя из расстояния до центроид. Шаг M, идейно, остается без изменений.
-means
Реализация на python
В пакете sklearn алгоритм EM представлен объектом GaussianMixture. Проиллюстрируем его работу на примере задачи кластеризации и сравним его с алгоритмом
-means:import numpy as np import matplotlib.pyplot as plt from sklearn import cluster, datasets, mixture from sklearn.preprocessing import StandardScaler from itertools import cycle, islice np.random.seed(12) # Создаем datasets с использованием стандартных sklearn.datasets n_samples = 2000 random_state = 170 noisy_circles = datasets.make_circles(n_samples=n_samples, factor=.5, noise=.05) noisy_moons = datasets.make_moons(n_samples=n_samples, noise=.05) blobs = datasets.make_blobs(n_samples=n_samples, random_state=8) varied = datasets.make_blobs(n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=random_state) # Создаем анизатропно разделенные данные X, y = datasets.make_blobs(n_samples=n_samples, random_state=random_state) transformation = [[0.6, -0.6], [-0.4, 0.8]] X_aniso = np.dot(X, transformation) aniso = (X_aniso, y) # Выставляем параметры для matplotlib.pyplot plt.figure(figsize=(9 * 2 + 3, 12.5)) plt.subplots_adjust(left=.02, right=.98, bottom=.001, top=.96, wspace=.05, hspace=.01) plot_num = 1 defaul_n = 3 # Варьируем значение количества классов в зависимости от данных, ведь для нас это гиперпараметр datasets = [ (varied, defaul_n), (aniso, defaul_n), (blobs, defaul_n), (noisy_circles, 2)] for i_dataset, (dataset, n_cluster) in enumerate(datasets): X, y = dataset # Нормализация данных X = StandardScaler().fit_transform(X) # Непосредственно наш алгоритм - Gaussian Mixture gmm = mixture.GaussianMixture(n_components=n_cluster, covariance_type='full') # Для сравнения берем алгоритм - k-means two_means = cluster.KMeans(n_clusters=n_cluster) clustering_algorithms = { 'Real distribution': None, 'Gaussian Mixture': gmm, 'k-Means': two_means } for name, algorithm in clustering_algorithms: # Этап обучения if algorithm is not None: algorithm.fit(X) # Применяем алгоритм y_pred = y if algorithm is None else algorithm.predict(X) # Рисуем результаты plt.subplot(len(datasets), len(clustering_algorithms), plot_num) if i_dataset == 0: plt.title(name, size=18) colors = np.array(list(islice(cycle(['#377eb8', '#ff7f00', '#4daf4a']), int(max(y_pred) + 1)))) plt.scatter(X[:, 0], X[:, 1], s=10, color=colors[y_pred]) plt.xlim(-2.5, 2.5) plt.ylim(-2.5, 2.5) plt.xticks(()) plt.yticks(()) plot_num += 1 plt.show()
Как и следовало ожидать, алгоритм EM работает на некоторых данных лучше чем k-means, однако есть данные, с которыми он не справляется без дополнительных преобразований.
См. также
Примечания
Источники информации
- Материалы лекции про кластеризацию курса "Машинное обучение" университета ИТМО, 2019 год
- Математические методы обучения по прецедентам К. В. Воронцов
- Статья про EM-алгоритм на machinelearning.ru
- A Gentle Introduction to Expectation-Maximization
- k-means