Участник:Platonova.Elena/Песочница
Материал из MachineLearning.
Строка 12: | Строка 12: | ||
'''Вход''': | '''Вход''': | ||
- | <tex> R, | + | <tex> R, M, Delta, L</tex> – общая длина выборки |
'''Выход''': | '''Выход''': | ||
Строка 33: | Строка 33: | ||
<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>\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) = \ | + | С учетом <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 | + | <center><tex>\frac{\partial}{\partial \theta_j}\sum_{i=1}^mg_{ij}(ln \theta_j - \theta_jx_i)=0</tex></center> |
- | \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> | |
- | \theta_{jy}=\frac{\sum_{i=1}^mg_{ij}}{\sum_{i=1}^my_ig_{ij}} | + | |
- | </tex | + | |
- | + | ||
==k-means (k ближайших соседей)== | ==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> ближайших соседей. | ||
Версия 10:18, 4 января 2010
Сравнение работы ЕМ-алгоритма и k-means для смесей с экспоненциальным распределением компонент. (само будет в заголовке)
Содержание |
Краткое описание исследуемых алгоритмов
ЕМ алгоритм
Основа EM-алгоритма - предположение, что исследуемое множество данных может быть представлено с помощью линейной комбинации распределений, а цель - оценка параметров распределения, которые максимизируют логарифмическую функцию правдоподобия, используемую в качестве меры качества модели.
Пусть рассматривается смесь из распределений, каждое описывается функцией правдоподобия
- априорная вероятность
-й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений
и отличаются только значениями параметра
Вход:
– общая длина выборки
Выход:
параметры распределения и весы компонент.
ОМП θ
для одно- и двумерного случая экспоненциального распределения.
Необходимо максимизировать
Из Лагранжиана следует:
j=1,...,k
j=1,...,k.
С учетом получаем ОМП
для экспоненциального закона:
В одномерном случае:
В двумерном случае:
k-means (k ближайших соседей)
Метод ближайших соседей - это метрический алгоритм классификации, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
Постановка задачи
Пусть - множество объектов;
- множество допустимых ответов. Задана обучающая выборка
. Задано множество объектов
.
Требуется найти множество ответов
для объектов
.
На множестве объектов задается некоторая функция расстояния, в данном случае
максимум модулей
Для произвольного объекта расположим
объекты обучающей выборки
в порядке возрастания расстояний до
:
где через обозначается
тот объект обучающей выборки, который является
-м соседом объекта
.
Аналогичное обозначение введём и для ответа на
-м соседе:
.
Таким образом, произвольный объект порождает свою перенумерацию выборки.
В наиболее общем виде алгоритм ближайших соседей есть
где — заданная весовая функция,
которая оценивает степень важности
-го соседа для классификации объекта
.
В рассматриваемом примере что соответствует методу
ближайших соседей.
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |