Одна из ключевых проблем, встречающихся при распознавании образов, заключается в так называемом «проклятии размерности». Процедуры, выполняемые аналитически в пространствах признаков небольшой размерности, могут стать совершенно неприменимыми в пространствах с числом признаков, равным нескольким десяткам. Были разработаны различные методы уменьшения размерности пространства признаков в надежде получить задачу, поддающуюся решению.
Можно уменьшить размерность с d измерений до одного, просто проецируя d-мерные данные на прямую. Если выборки образуют хорошо разделенные компактные группы в d-пространстве, проекция на произвольную прямую обычно смешивает выборки из всех классов. Однако, вращая эту прямую, мы можем найти такую ориентацию, при которой спроецированные выборки будут хорошо разделены. Именно это является целью классического дискриминантного анализа.
Предположим, что мы имеем множество n d-мерных выборок x1, …, xn, из которых n1 выборок относятся к подмножеству X1, соответствующему гипотезе H1, и n2 выборок относятся к подмножеству X2, соответствующему гипотезе H2. Если мы образуем линейную комбинацию компонент вектора x, получим скалярную величину и соответствующее множество n выборок y1, …, yn, разделенное на подмножества Y1 и Y2. Геометрически, если
, каждая компонента yi есть проекция соответствующего xi на прямую в направлении
. В действительности величина
не имеет реального значения, поскольку она просто определяет масштаб y. Однако направление
имеет значение. Если мы вообразим, что выборки, помеченные H1, попадают более или менее в одну группу, а выборки, помеченные H2, попадают в другую, то мы хотим, чтобы проекции на прямой были хорошо разделены и не очень перемешаны. На рис. 1.2 показан выбор двух различных значений w для двумерного случая.
Рис. 2.2. Выбор направления вектора W
Мерой разделения спроецированных точек служит разность средних значений выборки. Если mi есть среднее значение d-мерной выборки, заданное как
то среднее значение выборки для спроецированных точек задается посредством
Отсюда следует, что и что мы можем сделать эту разность сколь угодно большой, масштабируя
.
Чтобы получить хорошее разделение спроецированных данных, необходимо, чтобы разность между средними значениями была велика относительно некоторого показателя стандартных отклонений для каждого класса. Вместо получения дисперсий выборок определим разброс для спроецированных выборок, помеченных Hi, посредством
Таким образом, является оценкой дисперсии совокупности данных, где
называется полным разбросом внутри класса спроецированных выборок. Линейный дискриминант Фишера тогда определяется как такая линейная разделяющая функция wtx, для которой функция критерия
максимальна.
Чтобы получить J как явную функцию от w, определим матрицы разброса Si и Sw посредством
и
Тогда
Отсюда
Аналогично
где
Матрица Sw называется матрицей разброса внутри класса. Она пропорциональна ковариационной выборочной матрице для совокупности d-мерных данных. Она будет симметричной, положительно полуопределенной и, как правило, невырожденной, если n > d. SB называется матрицей разброса между классами. Она также симметричная и положительно полуопределенная, но из-за того, что она является внешним произведением двух векторов, ее ранг будет не больше 1. В частности, для любого направление
совпадает с направлением
и SB – вполне вырожденная матрица.
При помощи SB и Sw функцию критерия J можно представить в виде
Это выражение хорошо известно в математической физике как обобщенное частное Релея. Легко показать, что вектор , который максимизирует J, должен удовлетворять соотношению
что является обобщенной задачей определения собственного значения.
Если SW является невырожденной, мы можем получить обычную задачу определения собственного значения, написав
В нашем частном случае не нужно находить собственные значения и собственные векторы из-за того, что направление SB
всегда совпадает с направлением
. Поскольку масштабный множитель для w несуществен, мы можем сразу написать решение
(2.10.11)
Таким образом, мы получили линейный дискриминант Фишера – линейную функцию с максимальным отношением разброса между классами к разбросу внутри класса. Задача была преобразована из d-мерной в более приемлемую одномерную. Это отображение n-мерного множества на одномерное, и теоретически оно не может уменьшить минимально достижимый уровень ошибки.
Когда условные плотности распределения являются многомерными нормальными с равными ковариационными матрицами Σ, то даже не нужно ничем жертвовать. В этом случае мы вспоминаем, что граница оптимальных решений удовлетворяет уравнению
где
и w0 есть константа, включающая в себя w и априорные вероятности.
Если мы используем средние значения и ковариационную матрицу выборок для оценки µi и Σ, то получаем вектор в том же направлении, что и , удовлетворяющий (1.10.11), который максимизирует J. Таким образом, для нормального случая с равными ковариациями оптимальным решающим правилом будет решение H1, если линейный дискриминант Фишера превышает некоторое пороговое значение, и решение H2 – в противном случае.