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

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

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

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

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

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

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

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

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

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

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

Manual entries

This article is intended for personal use only.

Скачать ALGLIB