4.10. ЛИНЕЙНЫЙ ДИСКРИМИНАНТ ФИШЕРА

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

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

Предположим, что мы имеем множество -мерных выборок в подмножестве помеченном в подмножестве помеченном Если мы образуем линейную комбинацию компонент вектора х, получим скалярную величину

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

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

Мерой разделения спроецированных точек служит разность средних значений выборки.

Рис. 4.6. Проекция выборок на прямую.

Если есть среднее значение -мерной выборки, заданное как

то среднее значение выборки для спроециройанных точек задается посредством

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

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

максимальна.

Чтобы получить J как явную функцию от w, определим матрицы разброса и посредством

и

Тогда

так что

Аналогично

где

Матрица называется матрицей разброса внутри класса. Она пропорциональна ковариационной выборочной матрице для совокупности -мерных данных. Она будет симметричной, положительно полуопределенной и, как правило, невырожденной, если называется матрицей разброса между классами. Она также

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

При помощи функцию критерия J можно представить в виде

Это выражение хорошо известно в математической физике как обобщенное частное Релея. Легко показать, что вектор w, который максимизирует У, должен удовлетворять соотношению

что является обобщенной задачей определения собственного значения. Если является невырожденной, мы можем получить обычную задачу определения собственного значения, написав

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

Таким образом, мы получили линейный дискриминант Фишера — линейную функцию с максимальным отношением разброса между классами к разбросу внутри класса. Задача была преобразована из -мерной в более приемлемую одномерную. Это отображение -мерного множества на одномерное, и теоретически оно не может уменьшить минимально достижимый уровень ошибки. В общем мы охотно жертвуем некоторыми теоретически достижимыми результатами ради преимущества работы в одномерном пространстве. Когда же условные плотности распределения являются многомерными нормальными с равными ковариационными матрицами , то даже не нужно ничем жертвовать. В этом случае мы вспоминаем, что граница оптимальных решений удовлетворяет уравнению

где

и есть константа, включающая в себя w и априорные вероятности. Если мы используем средние значения и ковариационную матрицу выборок для оценки и 2, то получаем вектор в том же направлении, что и w, удовлетворяющий (80), который максимизирует

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