Модифицированный метод логического анализа данных для задач классификации

В настоящее время при решении задач распознавания образов, помимо
требования высокой точности, часто возникает необходимость в
интерпретируемости и обоснованности получаемых решений. Особенно
интерпретируемость и обоснованность являются ключевыми факторами при
решении тех практических задач, в которых потери от принятия неверного
решения могут быть велики. Поэтому система поддержки принятия решений,
используемая для таких задач, должна обосновывать возможные решения и
интерпретировать результат.
Для создания такой системы потребуются алгоритмы классификации
данных, которые помимо самого решения предоставляют в явном виде
решающее правило, то есть выявляют знания из имеющихся данных. Это
справедливо для логических алгоритмов классификации, принцип работы
которых состоит в выявлении закономерностей в данных и формализации их в
виде набора правил, т.е. набора закономерностей, описываемых простой
логической формулой.
Процесс формирования логических правил сопровождается решением
задач выбора наилучших альтернатив в соответствии с некоторым критерием. В
предлагаемом методе логического анализа данных формализация процесса
формирования логических правил осуществляется в виде ряда задач
комбинаторной оптимизации, что формирует гибкий и эффективный алгоритм
логического анализа для классификации данных. Объединив некоторое
количество закономерностей в композицию, получаем классификатор, который
решает поставленную задачу.
Однако в настоящее время существует ряд проблем, связанных с
применением метода логического анализа данных при решении практических
задач классификации. Одной из них является построение оптимизационных
моделей для формирования информативных закономерностей. При
рассмотрении данного вопроса, прежде всего, необходимо определиться с теми
критериями и ограничениями, которые лежат в основе этих оптимизационных
моделей. Другой проблемой исследуемого метода является построение
классификатора, который смог бы верно отнести новое наблюдение, т.е.
наблюдение, не принимавшее участие при его построении, к тому или иному
классу. Основной задачей на данном этапе метода является повышение
интерпретируемости классификатора и качества классификации новых
наблюдений, т. е. улучшение обобщающих способностей классификатора.
Таким образом, разработка модификаций для метода логического
анализа данных, позволяющих улучшить интерпретируемость и обобщающие
способности классификатора, является актуальной научно-технической
задачей.
Следует отметить, что большой вклад в развитие логических алгоритмов
классификации внесли следующие ученые: Ю. И. Журавлев, К. В. Рудаков, К.
В. Воронцов, Н. Г. Загоруйко, Г. С. Лбов, Е. В. Дюкова, О. В. Сенько,
В. И. Донской, P. L. Hammer, G. Alexe, S. Alexe, Y. Freund, R. E. Schapire.
Цель диссертационной работы состоит в повышении точности решения
задач классификации и улучшении интерпретируемости классификатора,
основанного на логических закономерностях.
Поставленная цель определила необходимость решения следующих
задач:
1. Провести анализ существующих логических алгоритмов
классификации, алгоритмов поиска информативных закономерностей для них,
и основных программных систем, решающих практические задачи
классификации.
2. Разработать алгоритмическую процедуру выбора базовых наблюдений
для формирования закономерностей в методе логического анализа данных.
3. Разработать алгоритмическую процедуру улучшения закономерностей
для повышения их информативности и усиления обобщающих способностей
классификатора, построенного на базе данных закономерностей.
4. Создать модель оптимизации для формирования закономерностей,
покрывающих существенно различные подмножества наблюдений обучающей
выборки в методе логического анализа данных.
5. Разработать алгоритмическую процедуру построения классификатора,
учитывающую информативность закономерностей, для метода логического
анализа данных.
6. Модифицировать метод логического анализа данных на основе
разработанных алгоритмических процедур.
7. Алгоритмизировать и реализовать метод логического анализа данных
в виде программной системы, провести его апробацию и сравнительный анализ
по точности с другими алгоритмами классификации на практических задачах.
Методы исследования. В диссертационной работе использовались
методы системного анализа, теория множеств, теория вероятностей,
комбинаторика, методы оптимизации.
Новые научные результаты, выносимые на защиту:
1. Разработана алгоритмическая процедура выбора базовых наблюдений
для формирования закономерностей, отличающаяся от известных
целенаправленным выбором базовых наблюдений, получаемых путем
применения алгоритма «k-средних» к множеству наблюдений обучающей
выборки, позволяющая сократить количество правил в классификаторе и
снизить трудоемкость его построения при сохранении высокой точности.
2. Разработана алгоритмическая процедура наращивания
закономерностей, полученных на базе оптимизационной модели с
максимальным покрытием наблюдений обучающейся выборки, позволяющая
повысить информативность правил, тем самым, способствуя увеличению
точности принимаемых классификатором решений.
3. Создана модель оптимизации для формирования закономерностей,
отличающаяся от известных наличием в целевой функции весового
коэффициента покрываемого наблюдения, а также возможностью захвата
наблюдений другого класса, позволяющая формировать правила, которые
выделяют существенно различные подмножества наблюдений обучающей
выборки.
4. Разработана алгоритмическая процедура построения классификатора
как композиции информативных закономерностей, отличающаяся от известных
совместным использованием критерия бустинга для оценки информативности
закономерностей и новой итеративной процедуры выбора порога
информативности, позволяющая сократить количество правил в
классификаторе при сохранении высокой точности.
5. Модифицирован метод логического анализа данных на основе
разработанных алгоритмических процедур, позволяющих повысить
интерпретируемость классификатора, сокращая количество правил в нем, и
сохранить при этом высокую точность при решении практических задач
классификации.
Теоретическая значимость результатов диссертационного исследования
состоит в разработке и исследовании модификаций для метода логического
анализа данных, основанных на создании оптимизационных моделей для
формирования информативных закономерностей и алгоритмических процедур
сокращения количества правил в классификаторе, что является существенным
вкладом в теорию интеллектуальных технологий и представления знаний,
практики их применения в системах обработки информации и
интеллектуального анализа данных.
Практическая значимость. На основе метода логического анализа
данных реализована программная система поддержки принятия решений,
которая позволяет, используя рекомендации по настройке ее параметров,
широкому кругу специалистов эффективно решать практические задачи
классификации.
Материалы диссертационного исследования и разработанная
программная система использованы для решения следующих практических
задач: классификация результатов радарного сканирования, выявление спама,
прогнозирование осложнений инфаркта миокарда.
Достоверность и обоснованность результатов диссертации
подтверждается: исследованием существующих логических алгоритмов
классификации и алгоритмов поиска информативных закономерностей для них,
корректным обоснованием постановок задач, результатами применения
предложенных моделей, методов и алгоритмических процедур, сравнительным
анализом по точности с существующими алгоритмами классификации на
практических задачах.
Реализация результатов работы. Диссертационная работа поддержана
Фондом содействия развития малых форм предприятий в научно-технической
сфере по программе «У.М.Н.И.К.» («Участник молодежного научно-
инновационного конкурса») в рамках НИОКР «Разработка программной
системы на базе логических алгоритмов классификации для решения задач
медицинской диагностики и прогнозирования» на 2011-2013 гг. Результаты
диссертации использовались в гранте Президента РФ МК-463.2010.9
«Комбинаторная оптимизация в задачах распознавания при диагностике и
прогнозировании». Разработанная программная система «Логические анализ
данных в задачах классификации» зарегистрирована в Реестре программ для
ЭВМ 17 марта 2011 г. (свидетельство № 2011612265).
Апробация работы. Основные положения и результаты диссертации
докладывались и обсуждались на XIV, XV Международной научной