Информативность и выбор признаков

Важность выбора признаков

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

Выбор признаков — это сложная задача. Первый этап — назначение характеристик на роль потенциально полезных признаков — выполняет эксперт. Наука здесь помочь не может. Математик не может указать врачу, какие именно параметры измерять у больного. Специалист в своей области знает, на что обратить внимание. Если область новая, набор признаков формируется по интуиции, с тем чтобы затем проверить, есть ли среди них информативные.

Далее наука может помочь. Этим занимается раздел анализа данных, связанный с выбором признаков: оценить информативность предъявленных характеристик и выбрать из них необходимые и достаточные.

Информативность — понятие относительное. Оно всегда рассматривается в контексте конкретной задачи. Например, из полного набора данных об экспрессии генов для диагностики одного заболевания выбирается одно небольшое подмножество генов, а для другого — совершенно иное.

Формально задача выглядит так: имеется исходный набор характеристик X и решающее правило D. Известно, что нужно отличать (алфавит образов), и есть представление о допустимых потерях. Потери возникают, с одной стороны, из-за ошибок распознавания при малоинформативных признаках, а с другой — из-за затрат памяти и машинного времени при их большом количестве. Задача сводится к поиску такой подсистемы признаков, которая минимизирует эти потери, обеспечивая компромисс между качеством и вычислительной сложностью.

Стратегии выбора признаков: фильтрация и селекция

Общая схема алгоритма выбора признаков включает два основных метода:

1. Фильтрация (Filter) — выбор подмножества из исходного набора признаков, отбрасывание остальных.
2. Селекция (Wrapper) — создание вторичных признаков из исходного множества первичных.

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

• Прямой (внутренний) — судят о качестве выбора признаков по тому, насколько хорошо распознаются объекты обучающей выборки в этом пространстве.
• Косвенный (внешний) — оцениваются общие характеристики распределения объектов в новом пространстве признаков (например, насколько оно способствует хорошему распознаванию).

В процессе работы предусмотрена обратная связь: если качество выбранных признаков не устраивает, происходит возврат к предыдущему этапу для формирования и оценки другого варианта.

Алгоритмы фильтрации

Одним из первых алгоритмов фильтрации является метод случайного поиска с адаптацией, разработанный Г.С. Лбовым в 1964 году.

Принцип его работы:

• Исходное множество признаков моделируется как вещественная ось, разделенная на N участков (по числу признаков).
• Случайным образом выбирается несколько признаков, и оценивается качество распознавания.
• Процедура повторяется несколько раз.
• На этапе адаптации определяется лучший и худший наборы.
• Участки оси, соответствующие признакам из лучшего набора, расширяются (увеличивая вероятность их повторного выбора), а из худшего — сужаются (уменьшая вероятность).
• Постепенно вероятность выбора "хороших" признаков растет, а "плохих" — падает, пока система не сойдется к стабильному набору.

Ключевой параметр — коэффициент адаптации. Он определяет, насколько сильно изменяются границы участков. При большой адаптации процесс сходится быстро, но может остановиться на неоптимальном решении. При мягкой адаптации сходимость медленнее, но итоговое качество выше. Этот алгоритм успешно используется до сих пор и является предшественником эволюционного программирования.

Другим классом являются жадные алгоритмы (greedy algorithms). Они последовательно, шаг за шагом, изменяют набор признаков, оставляя на каждом шаге лучший вариант.

• Алгоритм Delition (исключение) — метод Мэрила и Грина. Начинает с полного набора признаков. На каждом шаге временно исключает каждый признак, оценивает качество и навсегда удаляет тот, без которого качество лучше всего (самый слабый признак).
• Алгоритм Addition (добавление) — метод Барабаша. Начинает с пустого набора. Сначала выбирает самый информативный одиночный признак. Затем, перебирая все оставшиеся, добавляет к нему парный, дающий лучшее качество. Процесс продолжается до нужного размера набора.
• Алгоритм AD (Add-Delition) — гибридный итеративный алгоритм. Сначала добавляет признаки (Addition), затем проверяет, все ли они еще нужны, и исключает самые слабые (Delition). Стратегия «два шага вперед, шаг назад». Этот метод оказался наиболее эффективным, так как помогает избегать попадания в локальные экстремумы.

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

Алгоритм ФРИЗ-ГРАД и грануляция

Дальнейшее развитие метода — переход от манипулирования отдельными признаками к гранулам (granules). Гранула — это группа признаков (например, из двух или трех), которая рассматривается как единый вторичный признак.

Было решено ограничиться гранулами мощности не выше трех по двум причинам:

1. Резкое возрастание трудоемкости перебора при увеличении мощности.
2. На практике редко встречаются ситуации, где комбинация из четырех и более признаков принципиально меняет качество распознавания по сравнению с тройками.

Для борьбы с комбинаторным взрывом был применен двухэтапный подход:

1. Сначала оценивается информативность каждого признака по отдельности и отбирается небольшое подмножество наиболее ценных.
2. Затем только на этом подмножестве формируются гранулы мощности 1, 2 и 3, которые далее соревнуются между собой в рамках алгоритма AD.

Такой подход реализован в алгоритме ФРИЗ-ГРАД (гранулированный AD), который является основной рабочей программой для решения множества практических задач.

Критерии информативности

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

Прямой (внутренний) критерий — это тестовое распознавание. Обучающая выборка делится на две части: собственно обучающую и тестовую. Решающее правило строится на обучающей части, а качество проверяется на тестовой. Распространенный вариант — кросс-валидация (cross-validation) или метод скользящего контроля (leave-one-out), когда тестовым объектом по очереди выступает каждый элемент выборки. Этот метод используется практически всеми, но имеет недостатки.

Косвенные (внешние) критерии оценивают свойства распределения данных.

• Критерий Фишера (Fisher) — информативность тем выше, чем больше расстояние между математическими ожиданиями классов и меньше дисперсии. Эффективен для нормальных законов распределения, что на практике выполняется не всегда.
• Энтропийный критерий — также является косвенной мерой информативности.
• Фриз-компактность — это косвенный критерий, основанный на концепции столпов (эталонов, прецедентов). Каждый эталон формирует вокруг себя кластер из объектов обучающей выборки, которые на него похожи больше, чем на другие эталоны. Фриз-компактность — это суммарная мера сходства объектов со своими эталонами по всем кластерам. Чем компактнее и удаленнее друг от друга кластеры, тем выше значение этого критерия.

Сравнение показало преимущество фриз-компактности перед кросс-валидацией. В экспериментах с добавлением шума кросс-валидация показывала неадекватно высокие и нестабильные результаты, в то время как фриз-компактность вела себя предсказуемо, а главное — ее оценка на обучающей выборке гораздо лучше коррелировала с качеством распознавания на новых, контрольных данных. Кросс-валидация может давать 100% точность на обучающих данных, даже когда классы находятся близко, в то время как фриз-компактность более чувствительна к реальной разделимости классов.

Практические результаты

Описанные методы (ФРИЗ-ГРАД, критерий фриз-компактности, метод распознавания на основе столпов) были проверены на сложных практических задачах.

Задача распознавания двух видов заболеваний крови (ALL и AML).
Исходные данные: 38 объектов для обучения (27 и 11), 7129 признаков. Контрольная выборка — 34 объекта. Лучшие опубликованные результаты (с использованием метода опорных векторов) давали 33 правильных ответа из 34. Метод ФРИЗ-ГРАД сгенерировал 30 различных подпространств признаков, 27 из которых дали 100% результат (34 из 34). При этом вычисления занимали 15-20 секунд. Сравнение на одинаковых признаках показало, что и метод принятия решения (столпы) также дает преимущество, обеспечивая 33 против 30 правильных ответов у метода опорных векторов.

Сравнение с мировыми методами.
Шотландские ученые из Эдинбургского университета провели масштабное сравнение 10 популярных методов выбора признаков и 4 типов решающих правил (итого 40 комбинаций) на 9 сложных генетических задачах. Из их результатов были выбраны лучшие (мировые рекорды) и сравнены с методом ФРИЗ-ГРАД. Средняя ошибка мировых рекордов составила ~15%, в то время как у ФРИЗ-ГРАД — ~6% (в 2.5 раза меньше).

При анализе рейтинга отдельных методов по сумме мест во всех задачах, ФРИЗ-ГРАД получил 12 штрафных баллов, в то время как лучший из сравниваемых методов (эмпирический байесовский риск) — 32. Аналогично, метод распознавания на основе столпов получил 9 баллов против 19 у метода опорных векторов (SVM).

Это подтверждает, что разработанный подход не уступает, а во многом превосходит лучшие из опубликованных методов. Кроме того, метод является человеко-ориентированным. Результаты легко интерпретируются: объяснение строится на ссылке на эталонные объекты, что гораздо понятнее для экспертов (например, врачей), чем сложные нелинейные уравнения. Поэтому весь подход назван когнитивным анализом данных.

Краткие итоги

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

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

Идея грануляции признаков (ФРИЗ-ГРАД) — логичное развитие, учитывающее, что информативность может быть эмерджентным свойством комбинации признаков, а не их отдельных качеств. Практическое ограничение мощности гранул до трех является обоснованным компромиссом между вычислительной реализуемостью и потенциальной полезностью. Это решение подчеркивает необходимость учета «проклятия размерности» на всех этапах.

Дискуссия о критериях информативности раскрывает важную методологическую ловушку. Доминирующая кросс-валидация, будучи прямым методом, может давать чрезмерно оптимистичные оценки, не отражающие реальную обобщающую способность. Использование косвенного критерия — фриз-компактности — представляет собой смену парадигмы: вместо оценки конкретных ошибок алгоритма оценивается структурное качество самого пространства признаков (компактность классов). Это приводит к выбору более устойчивых и надежных подпространств, что подтверждается экспериментами с зашумлением.

Практические результаты не просто валидируют теоретические выкладки, но демонстрируют качественный скачок. Сокращение ошибок в 2.5 раза по сравнению с «мировыми рекордами» на сложных генетических данных — это не инкрементное улучшение, а смена уровня эффективности. Важно, что это достигается не за счет усложнения моделей, а за счет более умного выбора данных для них. Высокая интерпретируемость подхода, основанного на эталонах, делает его применимым в критически важных областях, где требуется не просто точный, но и понятный человеку результат. Когнитивный анализ данных позиционируется не как очередной алгоритм, а как целостная методология, объединяющая отбор признаков и построение решающих правил с ориентацией на человеческое восприятие.