6.14. Группировка и уменьшение размерности

Так как большая размерность является камнем преткновения для многих процедур распознавания образов, были предложены многочисленные методы уменьшения размерности. В противоположность процедурам, которые мы только что рассматривали, большинство этих методов обеспечивает функциональное отображение, так что можно определить отображение произвольного вектора признаков. Классическими процедурами являются анализ главных компонент и факторный анализ, оба из которых уменьшают размерность путем формирования линейных комбинаций признаков¹⁴. Если мы рассматриваем задачу как задачу удаления или объединения (т. е. группирования) признаков с сильной корреляцией, то ясно, что методы группировки применимы к этой задаче. В терминах матриц данных, где п строк представляют d-мерные выборки, под обычной группировкой нужно понимать группировку строк—при этом для представления данных используется меньшее число центров групп,— в то время как под уменьшением размерности нужно понимать группировку столбцов—при этом для представления данных используются комбинированные признаки.

Рассмотрим простую модификацию иерархической группировки для уменьшения размерности. Вместо матрицы размераnn расстояний между выборками мы рассмотрим матрицу корреляций R=[_ij] размера dd, где коэффициент корреляции _ij относится к ковариациям (или ковариациям выборок) как

Так как 0≤ ρ²_ij ≤l, причем для некоррелированных признаков ρ²_ij=0, а для полностью коррелированных признаков ρ²_ij=1, то ρ²_ij играет роль функции подобия для признаков. Два признака, для которых ρ²_ij велико, хорошие кандидаты на объединение в один признак; таким образом, размерность снижается на единицу. Повторение этого процесса приводит к следующей иерархической процедуре:

Процедура: Иерархическое Уменьшение Размерности

1. Пусть =d и F_i={x_i}, i=1, ... , d.

Цикл: 2. Если =d', останов.

3. Вычислить матрицу корреляций и найти наиболее коррелированную пару групп признаков, скажем F_i и F_j.

4. Объединить F_i и F_j., стереть F_j и уменьшить на единицу.

5. Перейти к Цикл.

Вероятно, самым простым способом слияния двух групп признаков является их усреднение. (Это предполагает, что признаки были масштабированы так, что их числовые значения сравнимы.) Имея такое определение нового признака, несложно определить матрицу корреляции для групп признаков. Возможны различные модифика­ции такого подхода, но мы их не будем рассматривать.

С точки зрения классификации образов из всех способов уменьшения размерности наибольшей критики заслуживает то, что все они связаны с достоверным представлением данных. Наибольшее внимание обычно уделяется тем признакам или группам признаков, которые обладают наибольшей изменчивостью. Но для классификации нам нужно разделение, а не представление. Грубо говоря, наиболее интересны те признаки, для которых разница между средними значениями классов велика по сравнению со стандартным отклонением, а не те, для которых велики стандартные отклонения. Короче говоря, нас интересует нечто подобное методу множественного дискриминантного анализа, описанному в гл. 4.

Растет количество теоретических работ по методам уменьшения размерности для классификации образов. Некоторые из этих мето­дов стремятся сформировать новые признаки на основе линейных комбинаций старых. Другие из них стремятся создать меньшее подмножество первоначальных признаков. Основная проблема этой теории состоит в том, что деление распознавания образов на извлечение признаков, а затем классификацию теоретически является искусственным. Полностью оптимальный выделитель признаков не может быть чем бы то ни было иным, как оптимальным классификатором. Только тогда, когда накладываются ограничения на классификатор или на размер множества выборок, можно сформулировать нетривиальную (и очень сложную) задачу. В литературе можно найти различные способы преодоления этой проблемы при некоторых обстоятельствах, и мы отметим несколько отправных точек для такой литературы. Обычно более продуктивен путь, когда знание области действия задачи позволяет получить более информативные признаки. В части II этой книги мы займемся систематическим изучением способов извлечения признаков из визуальных данных и более общей задачей анализа зрительных сцен.