Выбор признаков Лекция 4

Проклятие размерности Выбор признаков Выбор признаков Генерация признаков Генерация признаков Формирование новой системы признаков, сохраняющей максимум информации о выборке Формирование новой системы признаков, сохраняющей максимум информации о выборке Метод главных компонент Метод главных компонент Метод независимых компонен Метод независимых компонен

Выбор признаков Что исключаем? Что исключаем? Дублирующие признаки Дублирующие признаки Шумовые признаки Шумовые признаки Критерии выбора признаков Критерии выбора признаков Внешние Внешние OLO, CV OLO, CV Внутренние Внутренние Критерий Фишера Критерий Фишера Методы перебора признаков Методы перебора признаков Жадные алгоритмы Жадные алгоритмы Ad, Del, GRAD Ad, Del, GRAD Поиск в глубину и в ширину Поиск в глубину и в ширину Метод ветвей и границ, МГУА Метод ветвей и границ, МГУА Стохастический поиск Стохастический поиск Генетический алгоритм, СПА Генетический алгоритм, СПА

Критерии выбора признаков Вероятность ошибки Вероятность ошибки E r = E r = Расстояние между распределениям Расстояние между распределениям расстояние Махаланобиса J M =( ) T -1 ( ) расстояние Махаланобиса J M =( ) T -1 ( ) Мера энтропии Мера энтропии J E =- (p 1j *logp 1j +p 2j *logp 2j ) J E =- (p 1j *logp 1j +p 2j *logp 2j ) j Мера Фишера Мера Фишера J F =( ) 2 /(S 1 2 +S 2 2 ) J F =( ) 2 /(S 1 2 +S 2 2 ) Компактность в широком смысле Компактность в широком смысле

Компактность Существует множество нечетких, интуитивных определений. Существует множество нечетких, интуитивных определений. Невычурность границ Невычурность границ Простота форм Простота форм Пример удачной формализации: профиль компактности Пример удачной формализации: профиль компактности

Addition x1x1 F1F1 x2x2 F2F2 xixi FiFi xNxN FNFN Вычисление функционала качества

Deletion x1x1 F1F1 x2x2 F2F2 xixi FiFi xNxN FNFN

AdDel,Grad Чередование этапов Add и Del дают AdDel и DelAd Чередование этапов Add и Del дают AdDel и DelAd Использование вместо единичных признаков гранул признаков небольшой размерности Использование вместо единичных признаков гранул признаков небольшой размерности гранулы размерности 2 и 3 можно формировать полным перебором гранулы размерности 2 и 3 можно формировать полным перебором полезно в случае, если несколько признаков информативны только вместе полезно в случае, если несколько признаков информативны только вместе

Метод ветвей и границ Наращиваются только ветки, перспективные с точки зрения критерия Q Наращиваются только ветки, перспективные с точки зрения критерия Q Q*> Q Q*> Q

Случайный поиск с адаптацией Признаки выбираются случайно Признаки выбираются случайно Вероятность выбора признаков попадающих в «хорошие» системы увеличивается Вероятность выбора признаков попадающих в «хорошие» системы увеличивается Вероятность выбора признаков, попадающих в «плохие» системы уменьшается Вероятность выбора признаков, попадающих в «плохие» системы уменьшается Процесс останавливается после стабилизации качества систем Процесс останавливается после стабилизации качества систем х1х1 х5х5 х4х4 х2х2 х3х3