Участник:Platonova.Elena/Песочница

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
-
'''Сравнение работы ЕМ-алгоритма и k-means для смесей с экспоненциальным распределением компонент.''' (само будет в заголовке)
+
'''Сравнение работы ЕМ-алгоритма и k-means для смесей с экспоненциальным распределением компонент.''' (будет в заголовке)
 +
В статье приведены примеры классификации ЕМ-алгоритмом и методом k ближайших соседей двумерной смеси, компоненты которой имеют экспоненциальное распределение.
=='''Краткое описание исследуемых алгоритмов'''==
=='''Краткое описание исследуемых алгоритмов'''==
Строка 10: Строка 11:
<tex>w_j</tex> - априорная вероятность <tex>j</tex>-й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений <tex>\varphi(x; \theta)</tex> и отличаются только значениями параметра <tex>p_j(x) = \varphi(x; \theta_j)</tex>
<tex>w_j</tex> - априорная вероятность <tex>j</tex>-й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений <tex>\varphi(x; \theta)</tex> и отличаются только значениями параметра <tex>p_j(x) = \varphi(x; \theta_j)</tex>
 +
 +
 +
'''Вывод формул для алгоритма'''
 +
----
'''Вход''':
'''Вход''':
Строка 18: Строка 23:
<tex>\theta = (\omega_1, \omega_2, ..., \omega_k, \theta_1, \theta_2, ..., \theta_k)</tex> параметры распределения и весы компонент.
<tex>\theta = (\omega_1, \omega_2, ..., \omega_k, \theta_1, \theta_2, ..., \theta_k)</tex> параметры распределения и весы компонент.
-
'''ОМП θ'''
+
'''Оценка максимального правдоподобия (ОМП) θ'''
для одно- и двумерного случая экспоненциального распределения.
для одно- и двумерного случая экспоненциального распределения.
Строка 37: Строка 42:
<center><tex>\frac{\partial}{\partial \theta_j}\sum_{i=1}^mg_{ij}(ln \theta_j - \theta_jx_i)=0</tex></center>
<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_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>
<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>
Строка 50: Строка 55:
'''Постановка задачи'''
'''Постановка задачи'''
 +
 +
----
Пусть <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>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>.
Строка 73: Строка 80:
В рассматриваемом примере <tex>w(i,x) = [i\leq k] ,</tex> что соответствует методу <tex>k</tex> ближайших соседей.
В рассматриваемом примере <tex>w(i,x) = [i\leq k] ,</tex> что соответствует методу <tex>k</tex> ближайших соседей.
-
 
+
==Пример работы №1==
 +
Смесь из двух компонент - см. рис
{{Задание|Platonova.Elena|Константин Воронцов|7 января 2010}}
{{Задание|Platonova.Elena|Константин Воронцов|7 января 2010}}

Версия 11:51, 4 января 2010

Сравнение работы ЕМ-алгоритма и k-means для смесей с экспоненциальным распределением компонент. (будет в заголовке) В статье приведены примеры классификации ЕМ-алгоритмом и методом k ближайших соседей двумерной смеси, компоненты которой имеют экспоненциальное распределение.

Содержание

Краткое описание исследуемых алгоритмов

ЕМ алгоритм

Основа EM-алгоритма - предположение, что исследуемое множество данных может быть представлено с помощью линейной комбинации распределений, а цель - оценка параметров распределения, которые максимизируют логарифмическую функцию правдоподобия, используемую в качестве меры качества модели. Пусть рассматривается смесь из k распределений, каждое описывается функцией правдоподобия p_j(x)

p(x) = \sum_{i=1}^k w_jp_j(x)

w_j - априорная вероятность j-й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений \varphi(x; \theta) и отличаются только значениями параметра p_j(x) = \varphi(x; \theta_j)


Вывод формул для алгоритма

Вход:

R, M, Delta, L – общая длина выборки

Выход:

\theta = (\omega_1, \omega_2, ..., \omega_k, \theta_1, \theta_2, ..., \theta_k) параметры распределения и весы компонент.

Оценка максимального правдоподобия (ОМП) θ

для одно- и двумерного случая экспоненциального распределения.

Необходимо максимизировать

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

Из Лагранжиана следует:

\omega_j=\frac{1}m \sum_{i=1}^mg_{ij} j=1,...,k

\frac{\partial L}{\partial\theta_j}=\frac{\partial}{\partial\theta_j}\sum_{i=1}^mg_{ij}lnp_j(x_i)=0, j=1,...,k.

С учетом p_j(x)\equiv \varphi(x, \theta_j) = \theta_j \cdot exp{-\theta_j \cdot x} получаем ОМП \theta для экспоненциального закона:

\frac{\partial}{\partial \theta_j}\sum_{i=1}^mg_{ij}(ln \theta_j - \theta_jx_i)=0

В одномерном случае:

\theta_j=\frac{\sum_{i=1}^mg_{ij}}{\sum_{i=1}^mx_ig_{ij}}

В двумерном случае:

\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}}

k-means (k ближайших соседей)

Метод K ближайших соседей - это метрический алгоритм классификации, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.

Постановка задачи

Пусть X \in \mathbb{R}^n\ - множество объектов; Y - множество допустимых ответов. Задана обучающая выборка \{(x_i,y_i)\}_{i=1}^\ell. Задано множество объектов \ X^m =\{x_i\}_{i=1}^m. Требуется найти множество ответов \{y_i\}_{i=1}^m для объектов \{x_i\}_{i=1}^m.

На множестве объектов задается некоторая функция расстояния, в данном случае \rho(x,x') - максимум модулей

\rho(x,x') = \max_{i} |x_i-x'_i|;

Для произвольного объекта x\in X расположим объекты обучающей выборки x_i в порядке возрастания расстояний до x:

\rho(x,x_{1; x}) \leq \rho(x,x_{2; x}) \leq \cdots \leq \rho(x,x_{m; x}),

где через x_{i; x} обозначается тот объект обучающей выборки, который является i-м соседом объекта x. Аналогично для ответа на i-м соседе: y_{i; x}.

Таким образом, произвольный объект x порождает свою перенумерацию выборки. В наиболее общем виде алгоритм ближайших соседей есть

a(x) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; x}=y \bigr] w(i,x),

где w(i,x) — заданная весовая функция, которая оценивает степень важности i-го соседа для классификации объекта u.

В рассматриваемом примере w(i,x) = [i\leq k] , что соответствует методу k ближайших соседей.

Пример работы №1

Смесь из двух компонент - см. рис


Данная статья является непроверенным учебным заданием.
Студент: Участник:Platonova.Elena
Преподаватель: Участник:Константин Воронцов
Срок: 7 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Platonova.Elena/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»
Личные инструменты