< Участник:Platonova.Elena(Различия между версиями)
|
|
| (9 промежуточных версий не показаны.) |
| Строка 1: |
Строка 1: |
| - | '''Сравнение работы ЕМ-алгоритма и k-means для смесей с экспоненциальным распределением компонент.''' (само будет в заголовке)
| |
| | | | |
| - | =='''Краткое описание исследуемых алгоритмов'''==
| |
| - | ==ЕМ алгоритм==
| |
| - | Основа EM-алгоритма - предположение, что исследуемое множество данных может быть представлено с помощью линейной комбинации распределений, а цель - оценка параметров распределения, которые максимизируют логарифмическую функцию правдоподобия, используемую в качестве меры качества модели.
| |
| - | Пусть рассматривается смесь из <tex>k</tex> распределений, каждое описывается функцией правдоподобия <tex>p_j(x)</tex>
| |
| - |
| |
| - | <center><tex>p(x) = \sum_{i=1}^k w_jp_j(x)</tex></center>
| |
| - |
| |
| - | <tex>w_j</tex> - априорная вероятность <tex>j</tex>-й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений <tex>\varphi(x; \theta)</tex> и отличаются только значениями параметра <tex>p_j(x) = \varphi(x; \theta_j)</tex>
| |
| - |
| |
| - | '''Вход''':
| |
| - |
| |
| - | <tex> R, M, Delta, L</tex> – общая длина выборки
| |
| - |
| |
| - | '''Выход''':
| |
| - |
| |
| - | <tex>\theta = (\omega_1, \omega_2, ..., \omega_k, \theta_1, \theta_2, ..., \theta_k)</tex> параметры распределения и весы компонент.
| |
| - |
| |
| - | '''ОМП θ'''
| |
| - |
| |
| - | для одно- и двумерного случая экспоненциального распределения.
| |
| - |
| |
| - | Необходимо максимизировать
| |
| - |
| |
| - | <center><tex>Q(\Theta) = ln\prod_{i=1}^m p(x_i)=\sum_{i=1}^mln\sum_{j=1}^k\omega_jp_j(x_i) \rightarrow ma\limits_{\Theta}x</tex></center>
| |
| - |
| |
| - | Из Лагранжиана следует:
| |
| - |
| |
| - | <tex>
| |
| - | \omega_j=\frac{1}m \sum_{i=1}^mg_{ij} </tex> j=1,...,k
| |
| - |
| |
| - | <tex>\frac{\partial L}{\partial\theta_j}=\frac{\partial}{\partial\theta_j}\sum_{i=1}^mg_{ij}lnp_j(x_i)=0,</tex> j=1,...,k.
| |
| - |
| |
| - | С учетом <tex>p_j(x)\equiv \varphi(x, \theta_j) = \theta_j \cdot exp{-\theta_j \cdot x}</tex> получаем ОМП <tex>\theta </tex> для экспоненциального закона:
| |
| - |
| |
| - | <center><tex>\frac{\partial}{\partial \theta_j}\sum_{i=1}^mg_{ij}(ln \theta_j - \theta_jx_i)=0</tex></center>
| |
| - |
| |
| - | В одномерном случае:
| |
| - | <tex>\theta_j=\frac{\sum_{i=1}^mg_{ij}}{\sum_{i=1}^mx_ig_{ij}}</tex>
| |
| - |
| |
| - | В двумерном случае:
| |
| - | <tex>\theta_{jx}=\frac{\sum_{i=1}^mg_{ij}}{\sum_{i=1}^mx_ig_{ij}}\\\theta_{jy}=\frac{\sum_{i=1}^mg_{ij}}{\sum_{i=1}^my_ig_{ij}}</tex>
| |
| - |
| |
| - | ==k-means (k ближайших соседей)==
| |
| - |
| |
| - | Метод <tex>K</tex> ближайших соседей - это [[Метрический классификатор|метрический алгоритм классификации]], основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты [[выборка|обучающей выборки]].
| |
| - |
| |
| - | ==Постановка задачи==
| |
| - | Пусть <tex>X \in \mathbb{R}^n\</tex> - множество объектов; <tex>Y</tex> - множество допустимых ответов. Задана обучающая выборка <tex>\{(x_i,y_i)\}_{i=1}^\ell</tex>. Задано множество объектов <tex>\ X^m =\{x_i\}_{i=1}^m</tex>.
| |
| - | Требуется найти множество ответов <tex>\{y_i\}_{i=1}^m</tex> для объектов <tex>\{x_i\}_{i=1}^m</tex>.
| |
| - |
| |
| - | На множестве объектов задается некоторая функция расстояния, в данном случае <tex>\rho(x,x').</tex>
| |
| - | максимум модулей
| |
| - | <center><tex>\rho(x,x') = \max_{i} |x_i-x'_i|;</tex></center>
| |
| - |
| |
| - | Для произвольного объекта <tex>x\in X</tex> расположим
| |
| - | объекты обучающей выборки <tex>x_i</tex> в порядке возрастания расстояний до <tex>x</tex>:
| |
| - | ::<tex>\rho(x,x_{1; x}) \leq \rho(x,x_{2; x}) \leq \cdots \leq \rho(x,x_{m; x}),</tex>
| |
| - | где через <tex>x_{i; x}</tex> обозначается
| |
| - | тот объект обучающей выборки, который является <tex>i</tex>-м соседом объекта <tex>x</tex>.
| |
| - | Аналогичное обозначение введём и для ответа на <tex>i</tex>-м соседе:
| |
| - | <tex>y_{i; x}</tex>.
| |
| - |
| |
| - | Таким образом, произвольный объект <tex>x</tex> порождает свою перенумерацию выборки.
| |
| - | В наиболее общем виде [[алгоритм]] ближайших соседей есть
| |
| - | ::<tex>a(x) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; x}=y \bigr] w(i,x),</tex>
| |
| - | где <tex>w(i,x)</tex> — заданная ''весовая функция'',
| |
| - | которая оценивает степень важности <tex>i</tex>-го соседа для классификации объекта <tex>u</tex>.
| |
| - |
| |
| - | В рассматриваемом примере <tex>w(i,x) = [i\leq k] ,</tex> что соответствует методу <tex>k</tex> ближайших соседей.
| |
| - |
| |
| - |
| |
| - |
| |
| - |
| |
| - |
| |
| - | {{Задание|Platonova.Elena|Константин Воронцов|7 января 2010}}
| |
