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

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

(Различия между версиями)

Версия 20:55, 9 января 2010

Содержание

1 Линейный дискриминантный анализ для случая двух классов
2 Линейный дискриминант Фишера
3 ЛДА для случая многих классов
4 Использование на практике
5 Применения
- 5.1 Распознавание лиц
- 5.2 Маркетинг
6 См. также
7 Ссылки
8 Литература

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

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

Для использования ЛДА признаки должны быть непрерывными величинами, иначе следует использовать анализ соответствий (англ. 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)$ .

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

В случае, когда классов больше двух, рассуждения, использованные при выведении линейного дискриминанта Фишера, могут быть дополнены для поиска подпространства, содержащего все объекты класса. Предположим, что каждый из $C$ классов имеет среднее $\mu_i$ и одну и ту же ковариационную матрицу $\Sigma$ . Тогда межклассовое рассеяние может быть задано, как ковариация средних:

$\Sigma_b=\frac{1}{C}\sum_{i=1}^C (\mu_i-\mu)(\mu_i-\mu)^T$ ,

где $\mu$ — среднее по всем классам. Расстояние между классами в направлении $\vec{\omega}$ в этом случае:

$S=\frac{\vec{\omega}^T\Sigma_b\vec{\omega}}{\vec{\omega}^T\Sigma\vec{\omega}}=\frac{\vec{\omega}^T(\Sigma_b\Sigma^{-1})\Sigma\vec{\omega}}{\vec{\omega}^T\Sigma\vec{\omega}}$ .

Это означает, что, когда $\vec{\omega}$ — собственный вектор матрицы $\Sigma_b\Sigma^{-1}$ , расстояние будет равно соответствующему собственному значению. Т.к. ранг $\Sigma_b$ не превосходит $C-1$ , эти ненулевые собственные векторы задают искомое векторное подпространство. Основное применение этих векторов - генерация признаков, как, например, в методе главных компонент. Собственные векторы, соответствующие малым собственным значениям, крайне чувствительны к изменениям данных обучения и зачастую требуется регуляризация, которая будет описанна в следующем разделе.

Другие обобщения ЛДА на случай нескольких классов решают более общую задачу с гетероскедастическими распределениями. Один из таких методов — гетероскедастический ЛДА (см., например, HLDA).

Если требуется классификация, а не сокращение числа размерностей, существует немало альтернативных методов. Например, можно отделить друг от друга все классы, а затем применить ЛДА или линейный дискриминант Фишера для классификации каждой выделенной области. Типичный пример такого метода — „один против всех“, когда точки одного класса отделяются от всех остальных точек (можно множество всех точек, не входящих в первый класс, считать вторым классом), а затем применяется ЛДА. Тогда построив $C$ классификаторов (по одному для каждого класса) мы решим задачу. Другой принятый метод — попарная классификация, при который новый классификатор создаётся для всякой пары классов (всего получается $C(C-1)$ классификаторов), а затем они комбинируются.

Использование на практике

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

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

$C_{new}=C+\sigma^2I$ ,

где $I$ —- единичная матрица, а величина $\sigma$ , называемая в данном случае регуляризующим параметром, —- количество добавленных шумов. Значение $\sigma$ обычно определяют методом скользящего контроля. Новая ковариационная матрица всегда обратима и может быть использована в вычислениях.

ЛДА может быть обобщён на случай множественного дискриминантного анализа, где $c$ становится качественной переменной с $N$ возможными значениями вместо двух. Если условные плотности распределения $p(\vec{x}|c=i)$ нормальны и матрицы ковариации одинаковы, достаточной статистикой для $P(c|\vec{x})$ будут значения $N$ проекций, образующих подпространство, натянутое на $N$ средних и афинно спроектированное с помощью обратной ковариацонной матрицы. Эти проекции могут быть найдены, решая обобщённую задачу на собственные значения, где в качестве числителя выступает ковариационная матрица, получающаяся при рассмотрении в векторов средних качестве образцов, а в качестве знаменателя — общая ковариационная матрица.

Применения

Помимо примеров, которые будут приведены ниже, ЛДА применяется в маркетинговых исследованиях, управлении производством товара, позиционировании.

Распознавание лиц

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

Маркетинг

В маркетинге дискриминантный анализ часто используется для определения факторов, которые бы различали различные типы покупателей и/или товаров на основании опросов или других форм сбора данных. Использование дискриминантного анализа в маркетинге обычно описывается следующими шагами:

Сформулировать задачу и собрать данные. Определить наиболее существенные признаки, по которым покупатели оценивают товар в данной категории. Использовать количественные методы маркетинговых исследований (такие, как опросы) для сбора данных у среза потенциальных покупателей касательно их предпочтений по признакам товаров. Сбор информации обычно осуществляется специалистами по маркетинговым исследованиям. В опросе от респондента требуется оценить по пятибальной (семибальной, десятибальной) шкале по ряду параметров, выбираемых исследователем. Они могут включать в себя: простота использования, вес, точность, сочность цвета, цена или размер. Набор признаков зависит от объекта исследования. Одни и те же вопросы задаются всем участникам опроса. Данные для различных продуктов кодируются и вводятся в статистическую систему, например R, SPSS, или SAS (в факторном анализе первый шаг совпадает).
Оценить коэффициенты дискриминантной функции и определить статистические значимость и состоятельность. Выбрать подходящий метод дискриминантного анализа. Прямый методы оценивают дискриминантную функцию таким образом, чтобы все признаки оценивались одновременно. Пошаговый метод вводит признаки последовательно. Двуклассовые методы следует использовать, когда у зависимой переменной только два состояния. Метод множественных дискриминант используется, когда зависимая величина имет три или более качественных состояния. Для проверки значимости в SPSS используется лямбда Уилкса (Wilk's Lambda) или F-стат в SAS. Наиболее распространённый метод оценки состоятельности, заключается в разделении имеющихся данных на оценочные данные и проверочные или отложенные данные. Оценочные данные используются для построения дискриминантной функции. Отложенные данные используются для построения матрицы классификации, в которой указывается количество правильно и неправильно классифицированных объектов. Доля правильной классификации называется коэффициентом попадания.
Изобразить двумерную картину, определить размерности, интерпретировать результаты. Статистическая программа (или подходящий модуль) отметит результаты. В двумерном пространстве будет отображён каждый объект. Расстояние между продуктами характеризует степень различия между ними. Размерности должны быть определены исследователем. Это требует субъективных суждений и зачастую является непростой задачей.

См. также

Ссылки

Wikipedia: Linear discriminant analysis

Литература

Fisher, R.A. The Use of Multiple Measurements in Taxonomic Problems // Annals of Eugenics. — 1936 T. 7. — С. 179-188.
R.O. Duda, P.E. Hart, D.H. Stork Pattern Classification (2nd ed.) // Wiley Interscience. — 2000.

Источник — «http://poligon.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»

Категории: Байесовская теория классификации | Линейные классификаторы

@@ Строка 27: / Строка 27: @@
 == Линейный дискриминант Фишера ==
+{{main|линейный дискриминант Фишера}}
 Зачастую понятия [[линейный дискриминант Фишера]] и ЛДА используют в качестве синонимов, хотя в исходной статье Рональда Эйлмера Фишера ''Использование множественных мер в задачах таксономии'' (The use of multiple measurements in taxonomic problems, 1936) описывается несколько иной дискриминант и не принимаются некоторые характерные для ЛДА предположения, такие, как нормальность распределений или равенство дисперсий.