7.9. ВЫБОР ПРИЗНАКОВ НА ОСНОВЕ МАКСИМИЗАЦИИ ДИВЕРГЕНЦИИ

Соответствующий подход к выделению признаков заключается в порождении множества признаков, свойства которых позволяют максимизировать меру различия между классами. Если выделено множество признаков, которое после применения с помощью соответствующего преобразования к двум или нескольким совокупностям образов обеспечит получение множества преобразованных образов, отличающееся более заметным разделением совокупностей образов различных классов, то такие признаки можно рассматривать как характеристики, выявляющие различия совокупностей. Эта задача рассмотрена с точки зрения использования матричного преобразования для получения таких преобразованных образов, которые обеспечивают максимизацию расстояния между множествами при сохранении постоянства внутримножественного расстояния или соответственно суммы расстояний между множествами и внутримножественных расстояний. Разделение классов, однако, можно оценивать не евклидовым расстоянием, а иными величинами. Более общим понятием расстояния является рассмотренная в § 7.8 дивергенция.

Рассмотрим две совокупности образов . характеризующиеся плотностями распределения соответственно. Дивергенция между этими двумя классами определяется как

Дивергенция должна быть использована в качестве функции критерия при порождении оптимального множества признаков. Как и в § 7.5, нам требуется матрица преобразования А, приводящая

к преобразованным образам меньшей размерности. Эти преобразованные образы определяются уравнением

где у есть -мерный вектор, есть n-мерный вектор и А — матрица размера строками которой являются линейно независимые векторы Дивергенция преобразованных образов определяется выражением

Допустим, что образы классов подчиняются нормальным распределениям соответственно. Из (7.5.6) и (7.5.9) следует, что векторы математического ожидания после преобразования определяются формулами

а ковариационные матрицы —

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

где

Так как след матрицы равен сумме ее характеристических чисел, то

где — характеристические числа матрицы .

Дифференциал от (7.9.8) есть

Поскольку характеристические числа матрицы то они удовлетворяют соотношению

или

где собственный вектор матрицы соответствующий характеристическому числу . Дифференциал от (7.9.11) равен

Так как матрицы — симметрические, то собственные векторы взаимно ортогональны относительно Можно определить полное множество собственных векторов и записать дифференциал как

где собственные векторы нормированны относительно С, т. е. .

Подстановка выражения (7.9.13) в (7.9.12) дает

Умножив (7.9.14) на и использовав условия

получим

Дифференциалы можно определить аналогично. Так как характеристическое число матрицы , то оно удовлетворяет соотношению

Дифференциал от (7.9.17) равен

Так как матрицы — симметрические, то все собственные векторы взаимно ортогональны относительно С. Отметим, однако, что ранг матрицы [8 (5] равен 1 и, следовательно, ранг матрицы также равен 1. Можно найти полное множество собственных векторов матрицы собственные векторы ортогональны относительно С, так что

Характеристические числа матрицы , соответствующие пополненным собственным векторам от, равны нулю. Итак, дифференциал можно представить как

Подставив (7.9.20) в (7.9.18) и упростив полученное выражение, получим

При выводе последней формулы мы воспользовались (7.9.17) и тем фактом, что характеристические числа, соответствующие собственным векторам равны нулю. Умножение (7.9.21) на и использование (7.9.19) приводит к

Аналогичным образом находим

После подстановки выражений (7.9.16), (7.9.22) и (7.9.23) в (7.9.9) получаем

Использование понятия следа матрицы позволяет преобразовать последнее выражение к виду

где

Поскольку значение произвольно, необходимое условие экстремальности состоит в равенстве матрицы пулю. Полученные результаты можно кратко сформулировать так.

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

где — характеристические числа и собственные векторы матрицы — характеристические числа и собственные векторы матриц и соответственно .

Ниже обсуждаются три частных случая.

Случай .

При равенстве ковариационных матриц уравнение (7.9.11) принимает вид

откуда следует, что . В таком случае (7.9.26) сводится к

Положив , вектор можно свести к скалярной величине выражение (7.9.28) при этом примет вид

С учетом формулы (7.9.17) можно показать, что

Следовательно,

и необходимое условие экстремальности дивергенции принимает вид

или

откуда следует, что а — собственный вектор матрицы и соответствующее характеристическое число равно Следовательно, для экстремальности дивергенции задаем А равным а — собственному вектору матрицы Соответствующая дивергенция равна

т. е. ненулевому характеристическому числу матриц . С учетом (7.9.6) получаем для преобразованных образов

т. е. согласно (7.9.30) эта величина равна ненулевому характеристическому числу матрицы . Следовательно, в данном частном случае переход от векторов к векторам у не приводит к потере информации, так как

Случай

Если векторы математического ожидания равны, то Таким образом, соотношение (7.9.26) приводится к

Если строками матрицы преобразования А служат собственные векторы матрицы нормированные относительно то можно показать, что

и

где характеристических чисел матрицы При этом (7.9.11) принимает вид

Следовательно,

и, кроме того,

причем 1 появляется в элементе. Это свойство собственного вектора приводит к

где а есть столбец матрицы А. Поэтому (7.9.36) принимает вид

Так как и вектор а удовлетворяет соотношению очевидно, что — нулевая матрица и условие экстремальности выполняется. Из (7.9.8) следует, что дивергенция принимает максимальное значение, если собственные векторы матрицы соответствующие характеристическим числам для которых выполняется условие

использованы в качестве строк матрицы преобразования А.

Случай 3. .

В общем случае решение уравнения вызывает существенно большие трудности. Воспользовавшись (7.9.25), получаем

Таким образом, вектор есть градиент дивергенции относительно векторов признаков .

Если, следовательно, увеличить А на , где — некоторый множитель, обеспечивающий сходимость, то дивер/енция увеличится. Можно воспользоваться методом наискорейшего подъема и решать следующую систему разностных уравнений:

где — порядковый номер шага итерации.

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

на рис. 7.1. Так как для этих образов выполняются условия и то воспользуемся результатами случая 1.

В § 7.5 было показано, что

следовательно,

Ковариационная матрица равна

а ее обратная матрица

В таком случае матрица есть

Ненулевое характеристическое число и соответствующий собственный вектор матрицы равны

Этот собственный вектор используется для формирования матрицы преобразования:

Применение преобразования к заданным образам приводит к следующим одномерным изображениям:

Эти образы отличают те же кластеризационные свойства, которые были обнаружены в § 7.5. Кроме того, очевидно, что преобразование не приводит к перекрытию любых двух образов, принадлежащих разным классам.