Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

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

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

Следует отметить, что под общим названием ЛДА объединено несколько схожих методов, различающихся требованиями к свойствам выборки. Ниже рассмотрен один из этих методов, предъявляющий к выборке лишь два требования: 1) размер выборки должен превосходить число переменных, и 2) классы могут пересекаться, но их центры должны быть удалены друг от друга.

Содержание

    1 Линейный дискриминантный анализ Фишера
    2 Границы применимости
    3 Manual entries

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

На картинке справа приведен пример задачи, решаемой алгоритмом Фишера.

В двухмерном пространстве независимых переменных имеются два класса. Области, занимаемые классами, имеют вид длинных параллельных эллипсов (отмечены зеленым и синим цветами). Центр первого класса расположен в точке (0, 0), центр второго - в точке (1, 1).

Простейшее решение - провести прямую, соединяющую центроиды классов (красная стрелка) и проецировать точки на неё - не подходит, так как при этом классы практически полностью перекрываются. Как же найти линейную комбинацию переменных, оптимальным способом разделяющую классы? Решение, предлагаемое Фишером, состоит в том, чтобы найти ось, проекция на которую максимизирует величину J(w) - отношение общей дисперсии выборки к сумме дисперсий внутри отдельных классов:

(здесь суммирование по c обозначает суммирование внутри классов, μ - среднее выборки, μ - среднее класса c). Числитель этой дроби показывает, насколько широка проекция выборки на ось, а знаменатель - насколько компактно упакованы отдельные классы в рамках выборки в целом. Интуитивно понятно, что образы лучше всего разделены, когда каждый класс в отдельности имеет минимальную дисперсию при максимальной дисперсии выборки в целом. Таким образом, задача построения оптимальной линейной комбинации сведена к задаче поиска минимума функции J(w). Благодаря линейности числителя и знаменателя эта задача может быть сведена к задаче поиска собственных значений симметричной матрицы.

Результатом работы алгоритма является N-мерный вектор, максимизирующий J(w), а также N-1 дополнительных векторов, образующих вместе с первым полный базис и упорядоченных по убыванию J(w) (эти векторы могут использоваться, если нам требуется найти не одну ось, а подпространство, минимизирующее J(w)). В примере выше вектор, соответствующий максимуму J(w) схематично изображен зеленым цветом. Можно видеть, что максимум информации несет первая компонента вектора, причем изображение схематичное, в реальности угол между вектором и осью x ещё меньше, т.е. практически множества разделяются с использованием только первой компоненты.

Границы применимости

Можно отметить, что в приведенном примере классы не перекрываются, однако в ряде случаев алгоритм может успешно работать и с перекрывающимися классами. Перекрытие границ классов не играет большой роли, пока их центроиды находятся достаточно далеко друг от друга, чтобы дисперсия существенно менялась в зависимости от того, считаем мы её по выборке в целом или внутри классов. В предельном случае, когда центры классов совпадают, т.е. μ, числитель и знаменатель J(w) совпадут и вся дробь будет тождественно равна 1, что не позволит нам найти оптимальное w. На практике это будет выражаться в том, что вектор w будет "дрожать", указывая в разные стороны в зависимости от случайных корреляций, возникающих из-за конечного размера выборки.

Manual entries

C++ lda subpackage   
C# lda subpackage   

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.