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

Кузьмич, Роман Иванович

ВВЕДЕНИЕ ………………………………………………………………………………………………. 4

1 АНАЛИЗ ЛОГИЧЕСКИХ АЛГОРИТМОВ КЛАССИФИКАЦИИ ……………… 10

1.1 Основные понятия логических алгоритмов классификации ………………. 10

1.2 Алгоритмы поиска закономерностей в форме конъюнкций ……………….. 13

1.3 Анализ основных логических алгоритмов классификации и способов их
построения ………………………………………………………………………………………….. 18

1.3.1 Решающие списки …………………………………………………………………… 18
1.3.2 Решающие деревья ………………………………………………………………….. 21
1.3.3 Алгоритмы простого и взвешенного голосования правил …………… 28
1.4 Анализ программных систем для решения задач классификации ………. 35

Выводы ………………………………………………………………………………………………. 42

2 МЕТОД ЛОГИЧЕСКОГО АНАЛИЗА ДАННЫХ И ЕГО МОДИФИКАЦИИ 44

2.1 Описание подхода ………………………………………………………………………….. 44

2.2 Бинаризация признаков …………………………………………………………………… 45

2.3 Построение опорного множества …………………………………………………….. 48

2.4 Формирование закономерностей ……………………………………………………… 51

2.5 Построение классификатора ……………………………………………………………. 55

2.6 Модификации для метода логического анализа данных ……………………. 57

2.7 Решение задач псевдобулевой оптимизации …………………………………….. 64

Выводы ………………………………………………………………………………………………. 68

3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНЫЕ
ИССЛЕДОВАНИЯ НА ПРАКТИЧЕСКИХ ЗАДАЧАХ ……………………………….. 71

3.1 Программная реализация метода логического анализа данных и
особенности использования программной системы ……………………………….. 71
3.2 Результаты экспериментальных исследований метода логического
анализа данных и разработанных для него модификаций на практических
задачах классификации ………………………………………………………………………… 77

3.3 Настройка параметров метода логического анализа данных с учетом
специфики решаемых задач ………………………………………………………………….. 93

3.4 Сравнительный анализ метода логического анализа данных с другими
алгоритмами классификации на практических задачах …………………………… 96

Выводы …………………………………………………………………………………………….. 105

ЗАКЛЮЧЕНИЕ ……………………………………………………………………………………… 107

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ……………………………………. 109

ПРИЛОЖЕНИЕ А (Справочное) Названия полей базы данных и расшифровка
их значений ……………………………………………………………………………………………. 122

ПРИЛОЖЕНИЕ Б (Справочное) Признаки с нулевой и максимальной
важностью для задачи прогнозирования осложнений инфаркта миокарда ….. 130

В настоящее время при решении задач распознавания образов, помимо
требования высокой точности, часто возникает необходимость в
интерпретируемости и обоснованности получаемых решений. Особенно
интерпретируемость и обоснованность являются ключевыми факторами при
решении тех практических задач, в которых потери от принятия неверного
решения могут быть велики. Поэтому система поддержки принятия решений,
используемая для таких задач, должна обосновывать возможные решения и
интерпретировать результат.
Для создания такой системы потребуются алгоритмы классификации
данных, которые помимо самого решения предоставляют в явном виде
решающее правило, то есть выявляют знания из имеющихся данных. Это
справедливо для логических алгоритмов классификации, принцип работы
которых состоит в выявлении закономерностей в данных и формализации их в
виде набора правил, т.е. набора закономерностей, описываемых простой
логической формулой.
Процесс формирования логических правил сопровождается решением
задач выбора наилучших альтернатив в соответствии с некоторым критерием. В
предлагаемом методе логического анализа данных формализация процесса
формирования логических правил осуществляется в виде ряда задач
комбинаторной оптимизации, что формирует гибкий и эффективный алгоритм
логического анализа для классификации данных. Объединив некоторое
количество закономерностей в композицию, получаем классификатор, который
решает поставленную задачу.
Однако в настоящее время существует ряд проблем, связанных с
применением метода логического анализа данных при решении практических
задач классификации. Одной из них является построение оптимизационных
моделей для формирования информативных закономерностей. При
рассмотрении данного вопроса, прежде всего, необходимо определиться с теми
критериями и ограничениями, которые лежат в основе этих оптимизационных
моделей. Другой проблемой исследуемого метода является построение
классификатора, который смог бы верно отнести новое наблюдение, т.е.
наблюдение, не принимавшее участие при его построении, к тому или иному
классу. Основной задачей на данном этапе метода является повышение
интерпретируемости классификатора и качества классификации новых
наблюдений, т. е. улучшение обобщающих способностей классификатора.
Таким образом, разработка модификаций для метода логического
анализа данных, позволяющих улучшить интерпретируемость и обобщающие
способности классификатора, является актуальной научно-технической
задачей.
Следует отметить, что большой вклад в развитие логических алгоритмов
классификации внесли следующие ученые: Ю. И. Журавлев, К. В. Рудаков, К.
В. Воронцов, Н. Г. Загоруйко, Г. С. Лбов, Е. В. Дюкова, О. В. Сенько,
В. И. Донской, 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 Международной научной

В ходе выполнения диссертационной работы получены следующие
результаты:
1. Проведен анализ существующих логических алгоритмов
классификации, алгоритмов поиска информативных закономерностей для них,
и основных программных систем, решающих практические задачи
классификации. Отмечено, что для классификации наиболее приемлем
алгоритм, основанный на голосовании правил.
2. Разработана алгоритмическая процедура выбора базовых наблюдений
для формирования закономерностей, отличающаяся от известных
целенаправленным выбором базовых наблюдений, получаемых путем
применения алгоритма «k-средних» к множеству наблюдений обучающей
выборки.
3. Разработана алгоритмическая процедура наращивания
закономерностей, полученных на базе оптимизационной модели с
максимальным покрытием наблюдений обучающей выборки.
4. Создана модель оптимизации для формирования закономерностей,
отличающаяся от известных наличием в целевой функции весового
коэффициента покрываемого наблюдения, а также возможностью захвата
наблюдений другого класса.
5. Разработана алгоритмическая процедура построения классификатора
как композиции информативных закономерностей, отличающаяся от известных
совместным использованием критерия бустинга для оценки информативности
закономерностей и новой итеративной процедуры выбора порога
информативности.
6. Модифицирован метод логического анализа данных на основе
разработанных алгоритмических процедур, при использовании которых
повышается интерпретируемость классификатора и качество классификации
новых наблюдений, т. е. улучшаются обобщающие способности
классификатора.
7. В результате решения практических задач эмпирически проверена
пригодность оптимизационных моделей для формирования информативных
закономерностей и эффективность разработанных алгоритмических процедур
для метода логического анализа данных.
8. Проведено сравнение по точности метода логического анализа данных
с другими алгоритмами классификации на практических задачах. В результате
метод показал лучшие результаты по точности решения предложенных задач.
Таким образом, в диссертационной работе разработаны, исследованы и
проверены на практических задачах модификации для метода логического
анализа данных, основанные на создании оптимизационных моделей для
формирования информативных закономерностей и алгоритмических процедур
сокращения количества правил в классификаторе при сохранении высокой
точности, что является вкладом в теорию и практику интеллектуального
анализа данных.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

    Нажимая на кнопку, я соглашаюсь на обработку персональных данных и с правилами пользования Платформой

    Помогаем с подготовкой сопроводительных документов

    Совместно разработаем индивидуальный план и выберем тему работы Подробнее
    Помощь в подготовке к кандидатскому экзамену и допуске к нему Подробнее
    Поможем в написании научных статей для публикации в журналах ВАК Подробнее
    Структурируем работу и напишем автореферат Подробнее

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Логик Ф. кандидат наук, доцент
    4.9 (826 отзывов)
    Я - кандидат философских наук, доцент кафедры философии СГЮА. Занимаюсь написанием различного рода работ (научные статьи, курсовые, дипломные работы, магистерские дисс... Читать все
    Я - кандидат философских наук, доцент кафедры философии СГЮА. Занимаюсь написанием различного рода работ (научные статьи, курсовые, дипломные работы, магистерские диссертации, рефераты, контрольные) уже много лет. Качество работ гарантирую.
    #Кандидатские #Магистерские
    1486 Выполненных работ
    Петр П. кандидат наук
    4.2 (25 отзывов)
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт напис... Читать все
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт написания магистерских диссертаций. Направление - связь, телекоммуникации, информационная безопасность, информационные технологии, экономика. Пишу научные статьи уровня ВАК и РИНЦ. Работаю техническим директором интернет-провайдера, имею опыт работы ведущим сотрудником отдела информационной безопасности филиала одного из крупнейших банков. Образование - высшее профессиональное (в 2006 году окончил военную Академию связи в г. Санкт-Петербурге), послевузовское профессиональное (в 2018 году окончил аспирантуру Уральского федерального университета). Защитил диссертацию на соискание степени "кандидат технических наук" в 2020 году. В качестве хобби преподаю. Дисциплины - сети ЭВМ и телекоммуникации, информационная безопасность объектов критической информационной инфраструктуры.
    #Кандидатские #Магистерские
    33 Выполненных работы
    Шиленок В. КГМУ 2017, Лечебный , выпускник
    5 (20 отзывов)
    Здравствуйте) Имею сертификат специалиста (врач-лечебник). На данный момент являюсь ординатором(терапия, кардио), одновременно работаю диагностом. Занимаюсь диссертац... Читать все
    Здравствуйте) Имею сертификат специалиста (врач-лечебник). На данный момент являюсь ординатором(терапия, кардио), одновременно работаю диагностом. Занимаюсь диссертационной работ. Помогу в медицинских науках и прикладных (хим,био,эколог)
    #Кандидатские #Магистерские
    13 Выполненных работ
    Татьяна П.
    4.2 (6 отзывов)
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки ... Читать все
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки в одном из крупнейших университетов Германии.
    #Кандидатские #Магистерские
    9 Выполненных работ
    Дмитрий Л. КНЭУ 2015, Экономики и управления, выпускник
    4.8 (2878 отзывов)
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    #Кандидатские #Магистерские
    5125 Выполненных работ
    Мария Б. преподаватель, кандидат наук
    5 (22 отзыва)
    Окончила специалитет по направлению "Прикладная информатика в экономике", магистратуру по направлению "Торговое дело". Защитила кандидатскую диссертацию по специальнос... Читать все
    Окончила специалитет по направлению "Прикладная информатика в экономике", магистратуру по направлению "Торговое дело". Защитила кандидатскую диссертацию по специальности "Экономика и управление народным хозяйством". Автор научных статей.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Татьяна М. кандидат наук
    5 (285 отзывов)
    Специализируюсь на правовых дипломных работах, магистерских и кандидатских диссертациях
    Специализируюсь на правовых дипломных работах, магистерских и кандидатских диссертациях
    #Кандидатские #Магистерские
    495 Выполненных работ
    Глеб С. преподаватель, кандидат наук, доцент
    5 (158 отзывов)
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной с... Читать все
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной специальности 12.00.14 административное право, административный процесс.
    #Кандидатские #Магистерские
    216 Выполненных работ
    Дарья С. Томский государственный университет 2010, Юридический, в...
    4.8 (13 отзывов)
    Практикую гражданское, семейное право. Преподаю указанные дисциплины в ВУЗе. Выполняла работы на заказ в течение двух лет. Обучалась в аспирантуре, подготовила диссерт... Читать все
    Практикую гражданское, семейное право. Преподаю указанные дисциплины в ВУЗе. Выполняла работы на заказ в течение двух лет. Обучалась в аспирантуре, подготовила диссертационное исследование, которое сейчас находится на рассмотрении в совете.
    #Кандидатские #Магистерские
    18 Выполненных работ

    Другие учебные работы по предмету