|
|
| Строка 1: |
Строка 1: |
| - | {{TOCright}}
| |
| - | '''EM-алгоритм с последовательным добавлением компонент''' — общий метод нахождения функции плотности распределения объектов. Предполагается, что она имеет вид смеси <tex>k</tex> распределений.
| |
| - | В данной статье рассматривается гауссовское распредение выборки, количество гауссианов произвольно.
| |
| | | | |
| - | == Постановка задачи ==
| |
| - | Задана выборка <tex>\{(\mathbf{x}_i,y_i)\}_{i=1}^{\ell}</tex>, в которой <tex>X^{\ell}</tex> = <tex>\{\mathbf{x}_i\}_{i=1}^{\ell}</tex> - множество объектов, <tex>Y^{\ell}</tex> = <tex>\{\mathbf{y}_i\}_{i=1}^{\ell}</tex> - множество ответов. Предполагается, что объекты имеют плотность распределения <tex>p(x)</tex>, представимую в виде смеси <tex>k</tex> гауссиан с параметрами <tex>\mu</tex> и <tex>\Sigma</tex>.
| |
| - |
| |
| - | <center><tex>p(x) = \sum_{i=1}^k w_jp_j(x) = \sum_{i=1}^k w_jN(x;\mu_j,\Sigma_j)</tex></center>
| |
| - |
| |
| - | Задача разделения смеси заключается в том, чтобы, имея выборку <tex>X^m</tex> случайных и независимых наблюдений из смеси <tex>p(x)</tex> оценить вектор параметров <tex>\theta = (w_1,...,w_k,\mu_1,...,\mu_k,\Sigma_1,...,\Sigma_k)</tex> доставляющий максимум функции правдоподобия
| |
| - | <center><tex>Q(\Theta) = \ln\prod_{i=1}^mp(x_i|w,\mu,\Sigma) = \sum_{i=1}^m\ln\sum_{j=1}^kw_jp_j(x_i) \rightarrow max</tex></center>
| |
| - |
| |
| - | == Алгоритм отыскания оптимальных параметров ==
| |
| - | Оптимальные параметры отыскиваются последовательно с помощью EM-алгоритма. Идея заключается во введении вспомогательного вектора скрытых переменных <tex>G</tex>, обладающего двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров <tex>\Theta</tex>, с другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных.
| |
| - | EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вы-
| |
| - | числяется ожидаемое значение (expectation) вектора скрытых переменных <tex>G</tex> по те-
| |
| - | кущему приближению вектора параметров <tex>\Theta</tex>. На М-шаге решается задача максими-
| |
| - | зации правдоподобия (maximization) и находится следующее приближение вектора <tex>\Theta</tex>
| |
| - | по текущим значениям векторов <tex>G</tex> и <tex>\Theta</tex>.
| |
| - | Если число компонент смеси заранее не известно, то применяется EM-алгоритм с последовательным добавлением компонент. Если при каком-либо <tex>k</tex> число неправильно классифицированных объектов превышает допустимое, то <tex>k</tex> увеличивается и повторяется EM(<tex>X,k_{new}</tex>)
| |
| - | *'''Вход:'''
| |
| - | Выборка <tex>X^m = \{x_1,...,x_m\}</tex> ;
| |
| - | <tex>R</tex> - максимальный допустимый разброс правдоподобия объектов;
| |
| - | <tex>m_0</tex> - минимальная длина выборки, по которой можно восстановить плотность;
| |
| - | <tex>\delta</tex> - параметр критерия останова;
| |
| - | *'''Выход:'''
| |
| - | <tex>k</tex> - число компонент смеси;
| |
| - | <tex>\Theta = (w_j,\mu_j,\Sigma_j)_{j=1}^k</tex>
| |
| - | *Алгоритм
| |
| - | 1. начальное приближение - одна компонента:<br />
| |
| - | <tex>k:=1; \qquad w_1:=1; \qquad \mu_1=\frac{1}{w_1}\sum_{i=1}^m g_{i1}x_i; \qquad \Sigma_1 = \frac{1}{mw_1}\sum_{i=1}^m g_{i1}(x_i-\mu_j)(x_i-\mu_j)^{T}; </tex><br />
| |
| - | 2. для всех <tex>k:= 2,3,4... </tex><br />
| |
| - | 3. выделить объекты с низким правдоподобием <br />
| |
| - | <tex>U:= \{x_i \in X^m\ | ~ p(x_i) < \frac{max ~ p(x_j)}{R} \}</tex> <br />
| |
| - | 4. Если <tex>|U|<m_0</tex> то выход из цикла по <tex>k</tex><br />
| |
| - | 5. Начальное приближение для <tex>k</tex> компоненты: <br/>
| |
| - | <tex>w_k:=\frac{1}{m}|U|; \qquad \mu_k=\frac{1}{mw_k}\sum_{i=1}^m g_{ik}x_i; \qquad \Sigma_k = \frac{1}{mw_k}\sum_{i=1}^m g_{ik}(x_i-\mu_j)(x_i-\mu_j)^{T}; </tex><br/>
| |
| - | <tex>w_j:=w_j(1-w_k) \qquad j = 1,...,k-1;</tex><br/>
| |
| - | 6. <tex>EM(X^m,k,\Theta,\delta);</tex><br/>
| |
| - |
| |
| - | == Смотри также ==
| |
| - | * [[Метод ближайших соседей]]
| |
| - | * [[Многомерная случайная величина]]
| |
| - |
| |
| - | ==Литература==
| |
| - | *К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации
| |
| - |
| |
| - | [[Категория:Кластеризация данных]]
| |
| - | [[Категория:Популярные и обзорные статьи]]
| |
| - | [[Категория:Библиотеки алгоритмов]]
| |
