Линейный дискриминантный анализ

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 18: Строка 18:
В этих предположениях оптимальное байесовске решение - относить точки ко второму классу если отношение правдоподобия ниже некоторого порогового знчения <tex>T</tex>: <br />
В этих предположениях оптимальное байесовске решение - относить точки ко второму классу если отношение правдоподобия ниже некоторого порогового знчения <tex>T</tex>: <br />
::<tex>(\vec{x}-\vec{\mu}_0)^T\Sigma_{y=0}^{-1}(\vec{x}-\vec{\mu}_0)+\ln{|\Sigma _{y=0}|}-(\vec{x}-\vec{\mu}_1)^T\Sigma _{y=1}^{-1}(\vec{x}-\vec{\mu}_1)\ln{|\Sigma_{y=0}|}<T</tex> <br />
::<tex>(\vec{x}-\vec{\mu}_0)^T\Sigma_{y=0}^{-1}(\vec{x}-\vec{\mu}_0)+\ln{|\Sigma _{y=0}|}-(\vec{x}-\vec{\mu}_1)^T\Sigma _{y=1}^{-1}(\vec{x}-\vec{\mu}_1)\ln{|\Sigma_{y=0}|}<T</tex> <br />
 +
Если не делается никаких дальнейших предположений, полученную задачу классификации называют квадратичным дискриминантным анализом (англ. quadratic discriminant analysis, QDA).
 +
В ЛДА делается дополнительное предположение о равенстве дисперсий (т.е. предполагается, что [[Ковариационная матрица|ковариационные матрицы]] равны: <tex>\Sigma_{y=0}=\Sigma_{y=1}=\Sigma</tex> и считается, что ковариационные матрицы имеют полный ранг.
 +
При этих предположениях задача упрощается и сводится к сравнению скалярного произведения с пороговым значением <br />
 +
::<tex>\vec{\omega}\cdot\vec{x}<c</tex> <br />
 +
для некоторой константы <tex>c</tex>, где <br />
 +
::<tex>\vec{\omega}=\Sigma^{-1}(\vec{\mu_1}-\vec{\mu_0})</tex>. <br />
 +
Это означает, что вероятность принадлежности нового наблюдения <tex>x</tex> к классу <tex>y</tex> зависит исключительно от линейной комбинации известных наблюдений.
-
{{UnderConstruction|[[Участник:Дорофеев Н.Ю.|Дорофеев Н.Ю.]] 23:33, 8 ноября 2008 (MSK)}}
+
== [[Линейный дискриминант Фишера]] ==
 +
 
 +
Зачастую понятия „линейный дискриминант Фишера“ и ЛДА используют в качестве синонимов, хотя в исходной статье Рональда Эйлмера Фишера ''Использование множественных мер в задачах таксономии'' (The use of multiple measurements in taxonomic problems, 1936) описывается несколько иной дискриминант и не принимаются некоторые характерные для ЛДА предположения, такие, как нормальность распределений или равенство дисперсий.
 +
 
 +
Предположим, что два наблюдаемых класса имеют средние <tex>\vec{\mu}_{y=0},\vec{\mu}_{y=1}</tex> и ковариационные матрицы <tex>\Sigma_{y=0},\Sigma_{y=1}</tex>.
 +
Тогда для линейной комбинации признаков <tex>\vec{\omega}\cdot\vec{x}</tex> средними будут <tex>\vec{\omega}\cdot\vec{\mu_{y=i}}</tex>, а ковариационные матрицы будут иметь вид <tex>\vec{\omega}^T\Sigma_{y=i}\vec{\omega}</tex> для <tex>i=0,1</tex>.
 +
Фишер взял за расстояние между этими распределениями величину, равную отношению межклассовой дисперсии к внутриклассовой: <br />
 +
::<tex>S=\frac{\sigma^2_{between}}{\sigma^2_{within}}=\frac{(\vec{\omega}\cdot\vec{\mu}_{y=1}-\vec{\omega}\cdot\vec{\mu}_{y=0})^2}{\vec{\omega}^T\Sigma_{y=1}\vec{\omega}+\vec{\omega}^T\Sigma_{y=0}\vec{\omega}}=\frac{(\vec{\omega}\cdot(\vec{\mu}_{y=1}-\vec{\mu}_{y=0}))^2}{\vec{\omega}^T(\Sigma_{y=1}+\Sigma_{y=0})\vec{\omega}}</tex> <br />
 +
Эта величина в некотором смысле характерезует соотношение сигнал-шум для разметки классов.
 +
Можно показать, что наилучшим образом классы разделимы при <br />
 +
<tex>\vec{\omega}=(\Sigma_{y=1}+\Sigma_{y=0})^{-1}(\vec{\mu}_{y=1}-\vec{\mu}_{y=0})</tex>. <br />
 +
Если выполняются предположения нормальности и равенства дисперсий, то полученное выше равенство эквивалентно ЛДА.
 +
 
 +
Обратим внимание, что вектор <tex>\vec{\omega}</tex> является вектором нормали к разделяющей гиперплоскости.
 +
Например в двумерном случае линия, наилучшим образом разделяющая два класса, перпендикулярна к <tex>\vec{\omega}</tex>.
 +
 
 +
В общем случае строятся проекции точек (образов данных в пространстве признаков) на <tex>\vec{\omega}</tex>.
 +
Однако, чтобы найти оптимаьно разделяющую данные гиперплоскость, требуется найти влияющую величину <tex>b</tex> из уравнения <tex>\vec{\omega}^T\mu_0+b=-(\vec{\omega}^T\mu_1+b)</tex>.
 +
 
 +
== ЛДА для случая многих классов ==
 +
 
 +
{{UnderConstruction|[[Участник:Дорофеев Н.Ю.|Дорофеев Н.Ю.]] 19:38, 11 ноября 2008 (MSK)}}
{{stub}}
{{stub}}

Версия 16:38, 11 ноября 2008

Содержание

Линейный дискриминантный анализ (ЛДА), а также связанный с ним линейный дискриминант Фишера — методы статистики и машинного обучения, применяемые для нахождения линейных комбинаций признаков, наилучшим образом разделяющих два или более класса объектов или событий. Полученная комбинация может быть использована в качестве линейного классификатора или для сокращения размерности пространства признаков перед последующей классификацией.

ЛДА тесно связан с дисперсионным анализом и регрессионным анализом, также пытающимися выразить какую-либо зависимую переменную через линейную комбинацию других признаков или измерений. В этих двух методах зависимая переменная — численная величина, а в ЛДА она является величиной номинальной (меткой класса). Помимо того, ЛДА имеет схожие черты с методом главных компонент и факторным анализом, которые ищут линейные комбинации величин, наилучшим образом описывающие данные.

Для использования ЛДА признаки должны быть непрерывными величинами, иначе следует использовать анализ соответствий (англ. Discriminant Correspondece Analysis).

Линейный дискриминантный анализ для случая двух классов

Для каждого образца объекта или события с известным классом y рассматривается набор наблюдений x (называемых ещё признаками, переменными или измерениями). Набор таких образцов называется обучающей выборкой (или набором обучения, обучением). Задачи классификации состоит в том, чтобы построить хороший прогноз класса y для всякого так же распределённого объекта (не обязательно содержащегося в обучающей выборке), имея только наблюдения x.

При ЛДА предполагается, что функции совместной плотности распределения вероятностей p(\vec{x}|y=1) и p(\vec{x}|y=0) - нормальны. В этих предположениях оптимальное байесовске решение - относить точки ко второму классу если отношение правдоподобия ниже некоторого порогового знчения T:

(\vec{x}-\vec{\mu}_0)^T\Sigma_{y=0}^{-1}(\vec{x}-\vec{\mu}_0)+\ln{|\Sigma _{y=0}|}-(\vec{x}-\vec{\mu}_1)^T\Sigma _{y=1}^{-1}(\vec{x}-\vec{\mu}_1)\ln{|\Sigma_{y=0}|}<T

Если не делается никаких дальнейших предположений, полученную задачу классификации называют квадратичным дискриминантным анализом (англ. quadratic discriminant analysis, QDA). В ЛДА делается дополнительное предположение о равенстве дисперсий (т.е. предполагается, что ковариационные матрицы равны: \Sigma_{y=0}=\Sigma_{y=1}=\Sigma и считается, что ковариационные матрицы имеют полный ранг. При этих предположениях задача упрощается и сводится к сравнению скалярного произведения с пороговым значением

\vec{\omega}\cdot\vec{x}<c

для некоторой константы c, где

\vec{\omega}=\Sigma^{-1}(\vec{\mu_1}-\vec{\mu_0}).

Это означает, что вероятность принадлежности нового наблюдения x к классу y зависит исключительно от линейной комбинации известных наблюдений.

Линейный дискриминант Фишера

Зачастую понятия „линейный дискриминант Фишера“ и ЛДА используют в качестве синонимов, хотя в исходной статье Рональда Эйлмера Фишера Использование множественных мер в задачах таксономии (The use of multiple measurements in taxonomic problems, 1936) описывается несколько иной дискриминант и не принимаются некоторые характерные для ЛДА предположения, такие, как нормальность распределений или равенство дисперсий.

Предположим, что два наблюдаемых класса имеют средние \vec{\mu}_{y=0},\vec{\mu}_{y=1} и ковариационные матрицы \Sigma_{y=0},\Sigma_{y=1}. Тогда для линейной комбинации признаков \vec{\omega}\cdot\vec{x} средними будут \vec{\omega}\cdot\vec{\mu_{y=i}}, а ковариационные матрицы будут иметь вид \vec{\omega}^T\Sigma_{y=i}\vec{\omega} для i=0,1. Фишер взял за расстояние между этими распределениями величину, равную отношению межклассовой дисперсии к внутриклассовой:

S=\frac{\sigma^2_{between}}{\sigma^2_{within}}=\frac{(\vec{\omega}\cdot\vec{\mu}_{y=1}-\vec{\omega}\cdot\vec{\mu}_{y=0})^2}{\vec{\omega}^T\Sigma_{y=1}\vec{\omega}+\vec{\omega}^T\Sigma_{y=0}\vec{\omega}}=\frac{(\vec{\omega}\cdot(\vec{\mu}_{y=1}-\vec{\mu}_{y=0}))^2}{\vec{\omega}^T(\Sigma_{y=1}+\Sigma_{y=0})\vec{\omega}}

Эта величина в некотором смысле характерезует соотношение сигнал-шум для разметки классов. Можно показать, что наилучшим образом классы разделимы при
\vec{\omega}=(\Sigma_{y=1}+\Sigma_{y=0})^{-1}(\vec{\mu}_{y=1}-\vec{\mu}_{y=0}).
Если выполняются предположения нормальности и равенства дисперсий, то полученное выше равенство эквивалентно ЛДА.

Обратим внимание, что вектор \vec{\omega} является вектором нормали к разделяющей гиперплоскости. Например в двумерном случае линия, наилучшим образом разделяющая два класса, перпендикулярна к \vec{\omega}.

В общем случае строятся проекции точек (образов данных в пространстве признаков) на \vec{\omega}. Однако, чтобы найти оптимаьно разделяющую данные гиперплоскость, требуется найти влияющую величину b из уравнения \vec{\omega}^T\mu_0+b=-(\vec{\omega}^T\mu_1+b).

ЛДА для случая многих классов

Статья в настоящий момент дорабатывается.
Дорофеев Н.Ю. 19:38, 11 ноября 2008 (MSK)


Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B8%D1%81%D0%BA%D1%80%D0%B8%D0%BC%D0%B8%D0%BD%D0%B0%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7»
Личные инструменты