Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

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

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

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

Предположим, что мы имеем множество n d-мерных выборок x1, …, xn, из которых n1 выборок относятся к подмножеству X1, соответствующему гипотезе H1, и n2 выборок относятся к подмножеству X2, соответствующему гипотезе H2. Если мы образуем линейную комбинацию компонент вектора x, получим скалярную величину doros208.wmf и соответствующее множество n выборок y1, …, yn, разделенное на подмножества Y1 и Y2. Геометрически, если doros209.wmf, каждая компонента yi есть проекция соответствующего xi на прямую в направлении doros210.wmf. В действительности величина doros211.wmf не имеет реального значения, поскольку она просто определяет масштаб y. Однако направление doros212.wmf имеет значение. Если мы вообразим, что выборки, помеченные H1, попадают более или менее в одну группу, а выборки, помеченные H2, попадают в другую, то мы хотим, чтобы проекции на прямой были хорошо разделены и не очень перемешаны. На рис. 1.2 показан выбор двух различных значений w для двумерного случая.

pic_2_2.wmf

Рис. 2.2. Выбор направления вектора W

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

doros213.wmf

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

doros214.wmf

Отсюда следует, что doros215.wmf и что мы можем сделать эту разность сколь угодно большой, масштабируя doros216.wmf.

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

doros217.wmf

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

doros220.wmf

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

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

doros221.wmf и doros222.wmf

Тогда

doros223.wmf

Отсюда

doros224.wmf

Аналогично

doros225.wmf

где doros226.wmf

Матрица Sw называется матрицей разброса внутри класса. Она пропорциональна ковариационной выборочной матрице для совокупности d-мерных данных. Она будет симметричной, положительно полуопределенной и, как правило, невырожденной, если n > d. SB называется матрицей разброса между классами. Она также симметричная и положительно полуопределенная, но из-за того, что она является внешним произведением двух векторов, ее ранг будет не больше 1. В частности, для любого doros227.wmf направление doros228.wmf совпадает с направлением doros229.wmf и SB – вполне вырожденная матрица.

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

doros230.wmf

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

doros232.wmf

что является обобщенной задачей определения собственного значения.

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

doros233.wmf

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

doros237.wmf (2.10.11)

Таким образом, мы получили линейный дискриминант Фишера – линейную функцию с максимальным отношением разброса между классами к разбросу внутри класса. Задача была преобразована из d-мерной в более приемлемую одномерную. Это отображение n-мерного множества на одномерное, и теоретически оно не может уменьшить минимально достижимый уровень ошибки.

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

doros239.wmf

где doros240.wmf

и w0 есть константа, включающая в себя w и априорные вероятности.

Если мы используем средние значения и ковариационную матрицу выборок для оценки µi и Σ, то получаем вектор в том же направлении, что и doros241.wmf, удовлетворяющий (1.10.11), который максимизирует J. Таким образом, для нормального случая с равными ковариациями оптимальным решающим правилом будет решение H1, если линейный дискриминант Фишера превышает некоторое пороговое значение, и решение H2 – в противном случае.


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074