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

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

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

Версия 09:23, 5 января 2010

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

Предположим, что обучающая выборка удовлетворяет помимо базовых гипотез байесовского классификатора также следующим гипотезам:

Классы распределены по нормальному закону
Матрицы ковариаций классов равны

Такой случай соответствует наилучшему разделению классов по дискриминанту Фишера (в первоначальном значении). Тогда статистический подход приводит к линейному дискриминанту, и именно этот алгоритм классификации в настоящее время часто понимается под термином линейный дискриминант Фишера.

Введение

При некоторых общих предположениях байесовский классификатор сводится к формуле:

$a(x) = \mathrm{arg}\max_{y\in Y} \lambda_{y} P_y p_y(x)$ ,

где $Y$ - множество ответов (классов), $x$ принадлежит множеству объектов $X , P_y$ - априорная вероятность класса $y , p_y(x)$ - функция правдоподобия класса $y , \lambda_{y}$ - весовой коэффициент (цена ошибки на объекте класса $y$ ).

При выдвижении всех указанных выше гипотез, кроме гипотезы о равенстве матриц ковариаций, данная формула принимает вид:

$a(x) = \mathrm{arg}\max_{y\in Y} (\ln(\lambda_{y} P_y) - \frac{1}{2}(x - \mu_y)^T \Sigma^{-1}_{y} (x - \mu_y) - \frac{1}{2}\ln(det{\Sigma^{-1}_{y}})- \frac{n}{2}\ln(2\pi))$ ,

где $\mu_y = \frac{1}{l_y} \sum^{l}_{\stackrel{i=1}{y_i = y}}x_i$ $\Sigma_y = \frac{1}{l_y} \sum^{l}_{\stackrel{i=1}{y_i = y}}(x_i - \mu_y)(x_i - \mu_y)^T$ - приближения вектора математического ожидания и матрицы ковариации класса $y$ , полученные как оценки максимума правдоподобия, $l$ - длина обучающей выборки, $l_y$ - количество объектов класса $y$ в обучающей выборке, $x \in R^n$ .

Данный алгоритм классификации является квадратичным дискриминантом. Он имеет ряд недостатков, одним из самых существенных из которых является плохая обусловленность или вырожденность матрицы ковариаций $\Sigma_y$ при малом количестве обучающих элементов класса $y$ , вследствие чего при обращении данной матрицы $\Sigma^{-1}_{y}$ может получиться сильно искаженный результат, и весь алгоритм классификации окажется неустойчивым, будет работать плохо (возможна также ситуация, при которой обратная матрица $\Sigma^{-1}_{y}$ вообще не будет существовать). Линейный дискриминант Фишера решает данную проблему.

Основная идея алгоритма

При принятии гипотезы о равенстве между собой ковариационных матриц алгоритм классификации принимает вид: $a(x) = \mathrm{arg}\max_{y\in Y} (\ln(\lambda_{y} P_y) - \frac{1}{2}\mu_{y}^{T} \Sigma^{-1} \mu_y + x^T \Sigma^{-1} \mu_y)$ ,

или $a(x) = \mathrm{arg}\max_{y\in Y} (\beta_y + x^T\alpha_y)$

Простота классификации линейным дискриминантом Фишера - одно из достоинств алгоритма: в случае с двумя классами в двумерном признаковом пространстве разделяющей поверхностью будет прямая. Если классов больше двух, то разделяющая поверхность будет кусочно-лиинейной. Но главным преимуществом алгоритма по сравнению с квадратичным дискриминантом является уменьшение эффекта плохой обусловленности ковариационной матрицы при недостаточных данных.

При малых $l_y$ приближения $\Sigma_y = \frac{1}{l_y} \sum^{l}_{\stackrel{i=1}{y_i = y}}(x_i - \mu_y)(x_i - \mu_y)^T$ дадут плохой результат, поэтому даже в тех задачах, где заведомо известно, что классы имеют различные формы, иногда бывает выгодно воспользоваться эвристикой дискриминанта Фишера и считать матрицы ковариаций всех классов одинаковыми. Это позволит вычислить некоторую "среднюю" матрицу ковариаций, используя всю выборку:

$\Sigma = \frac{1}{l} \sum^{l}_{i=1}(x_i - \mu_{y_i})(x_i - \mu_{y_i})^T$ , использование которой в большинстве случаев сделает алгоритм классификации более устойчивым.

Выводы

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

Процесс классификации линейным дискриминантом Фишера можно описать следующей схемой:

Обучение
- Оценивание математических ожиданий $\mu_y$
- Вычисление общей ковариационной матрицы $\Sigma$ и ее обращение
Классификация
- Использование формулы $a(x) = \mathrm{arg}\max_{y\in Y} (\ln(\lambda_{y} P_y) - \frac{1}{2}\mu_{y}^{T} \Sigma^{-1} \mu_y + x^T \Sigma^{-1} \mu_y)$

Ссылки

Wikipedia: Linear discriminant analysis

Литература

К.В.Воронцов Лекции по статистическим (байесовским) алгоритмам классификации

Fisher, R.A. The Use of Multiple Measurements in Taxonomic Problems // Annals of Eugenics. — 1936 T. 7. — С. 179-188.

Данная статья является непроверенным учебным заданием.

Студент: Участник:OVSemenov

Преподаватель: Участник:Константин Воронцов

Срок: 7 января 2010

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

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

Источник — «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%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0»

Категория: Непроверенные учебные задания

@@ Строка 57: / Строка 57: @@
 == Литература ==
-# К.В.Воронцов Лекции по статистическим (байесовским) алгоритмам классификации
+* К.В.Воронцов [http://www.machinelearning.ru/wiki/images/e/ed/Voron-ML-Bayes.pdf Лекции по статистическим (байесовским) алгоритмам классификации]
+*{{книга
+|автор        = Fisher, R.A.
+|часть        = [http://www.library.adelaide.edu.au/digitised/fisher/138.pdf The Use of Multiple Measurements in Taxonomic Problems]
+|заглавие     = Annals of Eugenics
+|год          = 1936
+|том          = 7
+|страницы     = 179-188
+|ссылка       = http://en.wikipedia.org/wiki/Annals_of_Eugenics
+}}
 {{Задание|OVSemenov|Константин Воронцов|7 января 2010}}

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

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

Версия 09:23, 5 января 2010

Содержание

Введение

Основная идея алгоритма

Выводы

Ссылки

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты