автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Модель, метод и комплекс программ для решения задачи классификации с использованием генетических алгоритмов

На правах рукописи

00504ЬЗI о

Ржеуцкий Александр Викторович

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

05.13.18 — Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата технических наук

1 п ИЮП 2012

Санкт-Петербург — 2012

005046375

Работа выполнена на кафедре автоматики и вычислительной техники федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Вологодский государственный технический университет»

Научный руководитель: кандидат технических наук, доцент

Суконщиков Алексей Александрович

Официальные оппоненты: доктор технических наук,

профессор, заведующий кафедрой вычислительных систем и информатики Санкт-Петербургского государственного университета водных коммуникаций Марлей Владимир Евгеньевич

кандидат технических наук, инженер-программист филиала ОАО «Межрегиональная распределительная сетевая компания Северо-Запада» «Вологдаэнерго» Сергушичева Мария Александровна

Ведущая организация: федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Владимирский государственный университет»

Защита диссертации состоится 19 сентября 2012 г. в 15" часов на заседании диссертационного совета Д212.238.01 Санкт-Петербургского государственного электротехнического университета "ЛЭТИ" имени В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Профессора Попова, 5.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В.И.Ульянова (Ленина).

Автореферат разослан 11 июля 2012 г.

Ученый секретарь диссертационного совета

Щеголева Н.Л.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Современные корпоративные хранилища данных содержат огромные массивы информации, накопленной за длительный период эксплуатации информационных систем предприятий. Различные категории пользователей постепенно начинают осваивать открывшиеся возможности глубокого анализа накопленных данных как средства извлечения знаний, полезных для понимания причин тех или иных явлений в области деятельности и снижающих степень риска при принятии решений. В связи с потребностями практики мощный импульс развития получили вычислительные методы анализа данных с помощью обобщенных математических моделей, способных к обучению на основе совокупности фактов (прецедентов), накопленных в информационной системе. Данное направление, получившее название обучения по прецедентам (машинного обучения - machine learning), развивается в работах С.А. Айвазяна, П. Бартлетта, В.Н. Вапника, К.В. Воронцова, Ю.И. Журавлева, B.JI. Матросова, К.В. Рудакова, Р. Фишера, А.Я. Червоненкиса и др.

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

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

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

Объектом диссертационного исследования являются модели классификации в применении к системам анализа данных.

Предметом исследования являются методы и алгоритмы обучения моделей классификации и комплексы программ для решения задачи классификации.

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

Основные задачи исследования.

1. Определить критерии качества обученной модели классификации применительно к системам анализа данных.

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

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

4. Выполнить реализацию предложенного метода и алгоритмов в виде комплекса проблемно-ориентированных программ для проведения вычислительного эксперимента.

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

Научная новизна

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

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

3. Доказан линейный характер зависимости времени построения дерева классификации от размера обучающей выборки, что позволяет отнести разработанный генетический алгоритм к группе масштабируемых алгоритмов

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

4. Разработан комплекс проблемно-ориентированных программ для проведения вычислительного эксперимента на основе предложенного метода и алгоритмов.

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

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

На защиту выносятся следующие основные положения и результаты.

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

2. Структуры данных и алгоритмы для реализации основных генетических операторов, адаптированные с учетом специфики построения дерева классификации.

3. Общий алгоритм реализации предложенного метода построения дерева классификации, обладающий свойством масштабируемости.

4. Комплекс проблемно-ориентированных программ на основе предложенного метода для проведения вычислительного эксперимента

Внедренне результатов исследования. Теоретические и практические результаты диссертационной работы внедрены в программные продукты ООО «Логасофт». В настоящее время разработанное автором программное обеспечение апробировано в Департаменте финансов Вологодской области в составе системы электронного документооборота и в СЯМ-системе ООО «Бизнес-Софт», что подтверждено актами о внедрении.

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

Материалы работы использованы в Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы в рамках

проектов «Информационные системы в подготовке специалистов по направлению «Теплоэнергетика» (гос. контракт № П 740 от 12.08.2009), «Разработка методов формализации и верификации распределенных информационно-поисковых систем на основе сервис-ориентированной архитектуры» (гос. контракт № 2401 от 18.11.2009), «Методология построения интеллектуальных агентно-ориентированных учебных комплексов для многоуровневой подготовки специалистов технического профиля» (гос. контракт №02.740.11.0625 от 29.03.2010).

Апробация результатов исследования. Основные результаты работы докладывались и получили положительную оценку на следующих конференциях и семинарах: Всероссийская научно-практическая конференция «Информационно-телекоммуникационные технологии» (Москва, 2010г.), Международная конференция «Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта» (Вологда, 2007г.), Семинар вологодского отделения РАН по искусственному интеллекту (Вологда, 2010г.), Всероссийская научная конференция студентов и аспирантов «Молодые исследователи - регионам» (Вологда, 2006, 2007, 2008 гг.), Всероссийская конференция «Вузовская наука - региону» (Вологда, 2007, 2008, 2009 гг.), Ежегодные смотры - сессии аспирантов и молодых ученых по отраслям наук (Вологда, 2007 г.).

Публикации. П о материалам диссертационного исследования опубликовано 14 печатных работ, из них 4 статьи (3 статьи в ведущих рецензируемых научных журналах, одобренных ВАК), 10 работ - в трудах научно-технических конференций.

Структура диссертационной работы. Работа состоит из введения, четырех глав, заключения, библиографического списка и трех приложений. Основной текст работы изложен на 145 страницах, содержит 27 рисунков и 11 таблиц. Библиографический список включает 101 наименование.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

положения, выносимые на защиту.

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

Приведем формальную постановку задачи классификации данных. Пусть задано множество объектов X и множество К непересекающихся классов в некоторой системе классификации, причем каждому объекту х, может быть поставлен в соответствие класс к,.. Существует также решающая функция /■ X—>К (истинный классификатор), изначально неизвестная, но на конечном подмножестве объектов

6

{х1,х2,...,хц}сIX (не на всем множестве X) известны ее значения к,еК. Пары «объект-класс» (х„к) представляют собой прецеденты.

Совокупность известных пар называется обучающей выборкой X1*1.

Задача обучения по прецедентам заключается в том, чтобы восстановить зависимость / то есть построить алгоритм а (классификатор): X—>К, который бы наилучшим образом (в известном смысле) приближал решающую функцию Дх), причем не только на обучающей выборке, но и на всем множестве объектов X.

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

Анализ требований пользователей и выполненный обзор источников позволили систематизировать критерии качества. Выделены основные критерии, используемые в качестве целевой функции в оптимизационном процессе обучения модели (надежность, точность, обобщающая способность). В качестве дополнительных выделены критерии, значимые при выборе модели классификации (робастность, возможность отбора и ранжирования признаков объекта, интерпретируемость в терминах предметной области, универсальность и практичность) и алгоритма обучения модели (эффективность и масштабируемость^).

Основные критерии качества основаны на фундаментальном понятии надежности классификации, показателем которой является вероятность правильной классификации произвольного объекта хеХ или (чаще) вероятность ошибки при классификации произвольного объекта. Более общим показателем надежности классификации является функционал ожидаемого (среднего) риска

Функцией потерь Ь(к„ к¡) = > 0 назовем величину штрафа за ошибочное отнесение объекта класса К; к классу Кг Тогда функционал ожидаемого (среднего) риска <2(а) определяется как математическое ожидание функции потерь с учетом вероятностных характеристик пространства объектов-классов ХхК. При использовании бинарной функции потерь функционал среднего риска ()(а) есть вероятность ошибочной классификации при применении алгоритма а.

Вычисление Q(a) на практике затруднено в силу неизвестности вероятностных характеристик пространства объектов-классов, поэтому при решении прикладных задач для оценки качества классификации используются понятия точности и обобщающей способности, которые можно определить экспериментально.

Функционал качества алгоритма а, вычисленный по конечной выборке X14, называется эмпирическим риском:

В случае бинарной функции потерь функционал О вычисляется как отношение неверно классифицированных объектов к общему количеству объектов в обучающей выборке и называется частотой ошибок алгоритма а на выборке X .

Широко применяемый подход к обучению по прецедентам, называемый минимизацией эмпирического риска, заключается в том, чтобы найти в рамках заданной модели А алгоритм а, минимизирующий эмпирический риск £> на заданной обучающей выборке Xм:

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

Обобщающая способность алгоритма обучения определяется как результат сравнения точности классификации на обучающей и контрольной выборке. Любой алгоритм обучения по прецедентам должен иметь защиту от эффекта переобучения (оуегППт^, поэтому при анализе алгоритма обучения модели, наряду с точностью, определяется значение переобученное™, вычисляемое как разность функционала эмпирического риска на обучающей и контрольной выборке.

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

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

(2)

Вторая глава посвящена описанию предлагаемого метода построения деревьев классификации на основе генетического программирования.

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

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

Основная идея «жадных» алгоритмов построения деревьев классификации из обучающей выборки была сформулирована Р. Куинленом:

1. выбор критерия разделения выборки с целью поиска наиболее подходящего признака для формирования решающего правила в каждом узле дерева;

2. разделение выборки на две или более части, в соответствии со значениями признака, выбранного на основании критерия разделения;

3. рекурсия, начиная с шага 2. Образовавшиеся подмножества разделяются на более мелкие подмножества в соответствии с выбранным критерием до тех пор, пока в каждом из них не останутся объекты одного класса, либо не останется признаков, позволяющих эти объекты различить.

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

В некоторых алгоритмах (ID3 и С4.5) для выбора признака, на основе которого будет формироваться решающее правило, используется мера информативности подпространств признаков, которая основывается на энтропийном подходе и называется мерой информационного выигрыша или мерой энтропии. В соответствии с этим критерием, лучшим для разделения считается тот признак, который дает максимальную информацию о классах. Эта величина, называемая индексом Gain, определяется по формуле количества информации.

Gain{К | X) = И(К) - Я(К | X), (3)

где Н(К) - это энтропия множества К, Н(К\Х) - средняя условная энтропия множества К при известном множестве X. Величины Н(К) и Н(К\Х) определяются, соответственно, по формулам (4) и (5).

я (К) = -z ) • l°g2 Р(к.) (4)

I

Я(К|Х) = -£Р(*.)Я(К|д:.), (5)

/

где и Р(7У - это вероятности выбора того или иного значения из множества X и К соответственно, а Н(К\х,) - условная энтропия, если известно, что из X выбрано значение х,. При разделении выборки каждый раз выбирается тот атрибут, для которого значение Gain(K\X) максимально среди всех X.

Другой критерий разделения выборки, предложенный Брейманом (Breiman), реализован в алгоритме CART и называется индексом Gini. С помощью этого индекса признак выбирается на основании расстояний между распределениями классов.

Gmi(XN) = l-flPi1, (6)

i=i

где р. _ вероятность (относительная частота) класса i в выборке X .

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

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

Подобный подход уже был успешно применен И.П. Норенковым к задаче синтеза расписаний и назван методом комбинирования эвристик (НСМ — Heuristics Combination Method). В данном исследовании предлагается использовать НСМ для оптимального подбора эвристик при построении дерева классификации.

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

:признак, обладающий наибольшим значением индекса Оат(К|Х) (3); 52: признак, обладающий наибольшим значением индекса От^Х14) (6); 53: признак с наибольшим количеством различных значений в выборке; 54: признак с наименьшим количеством различных значений в выборке; 85: разделение выборки не производится (узел превращается в лист).

: генетическим:

: . .аПГОр1ЛТ*Л . ■ :■

скрещи мута вание, ция

формирование нового поколения

*

построение деревьев классификации по эвристикам

Ж

>1

отбор особей

<?гн

деревья эвристик (хромосомы)

Л.

деревья классификации

оценка точности классификации

Рисунок 1 - Схема, иллюстрирующая идею предлагаемого метода Хромосома в таком случае имеет древовидную структуру. Количество генов в ней совпадает с количеством узлов дерева, их значениями могут быть номера эвристик в диапазоне [1,5]. Общий алгоритм построения дерева представлен на рисунке 2.

Построение леревьез решений я лерезьев г-врнстнк (начальной лсттуляиин)

Рисунок 2 - Генетический алгоритм построения дерева классиккации

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

Чтобы обеспечить достаточное разнообразие особей, при формировании начальной популяции выполняется построение деревьев решений для каждой из эвристик [81:54]. Общий размер начальной популяции составляет 16 особей (4 вида эвристики для корня дерева комбинируются с 4 видами для его дочерних узлов).

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

1. Выбирается 2 хромосомы с одинаковыми генами, соответствующими корневому узлу дерева для рассматриваемого подмножества данных.

2. В каждой из родительских хромосом меняются местами значения генов, соответствующих первому и второму подчиненному узлу дерева.

Ограничениями оператора кроссовера являются необходимость совпадения эвристик для рассматриваемого узла дерева и количество дочерних узлов.

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

где /- количество пар одинаковых хромосом, п - размер популяции.

Алгоритм мутации состоит из следующих этапов:

1. Поиск в популяции пары хромосом с одинаковым значением эвристик во всех дочерних узлах.

2. Выбор из пары одной хромосомы для мутации (случайным образом).

3. Замена эвристики в корневом узле выбранной хромосомы (новый вид эвристики также выбирается случайным образом)

4. Если количество особей для мутации меньше к ив популяции остались одинаковые хромосомы, то возврат к шагу 1.

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

Работа алгоритма останавливается после выполнения всех этапов эволюции (для каждого узла, за исключением листьев). Дополнительно вводится ограничение на максимальную глубину дерева, а также на минимальное количество объектов в узле.

(7)

В третьей главе описаны особенности реализации, выполнена оценка временной сложности алгоритма и представлены результаты вычислительного эксперимента на тестовых данных, для которого было отобрано 7 различных наборов данных открытого репозитория UCI Machine Learning Repository.

Для повышения обобщающей способности (подавления эффекта переобучения) при построении дерева классификации принимаются следующие меры.

1. Ограничение по минимальному количеству случаев в узле. В случае, если размер образовавшихся подмножеств меньше определенного порога, разделение данных не происходит, а рассматриваемый узел превращается в лист.

2. Ограничение по максимальной глубине дерева. В случае если глубина дерева решений достигает максимума, дальнейшее разделение выборки не происходит.

3. Использование в генетическом алгоритме эвристики, связанной с прекращением дальнейшего разделения выборки (S5). Эта эвристика, наряду с другими, участвует в выполнении всех генетических операций.

4. Выделение тестовой и экзаменационной выборки данных заключается в разделении множества объектов X на три подмножества:

- обучающее множество (используется для построения деревьев решений);

- тестовое множество (для определения точности классификации полученных деревьев, необходимой для выполнения отбора особей в генетическом алгоритме);

- экзаменационное множество (для оценки точности полученного дерева классификации).

Результаты экспериментального сравнения точности классификации и обобщающей способности реализованного генетического алгоритма в сравнении с другими алгоритмами приведены в таблице 1. Представленные данные получены на тестовой задаче «Саг evaluation» из репозитория UCI Machine Learning Repository.

Таблица 1

Результаты сравнения алгоритмов для задачи «Саг evaluation»

Алгоритм классификации Средняя частота ошибок О(а.Х), % Среднеквадратичное отклонение &0(а.Х!, % Средняя переобу-ченность d>fX„, XJ, %

Дерево классификации: алгоритм CART 20,3 0,9 2,4

Дерево классификации: алгоритм С4.5 22,2 1,1 2,8

Дерево классификации: алгоритм, встроенный в платформу 1С:Предприятие 20,8 0,8 3,1

Дерево классификации: разработатый генетический алгоритм 16,6 0,6 0,9

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

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

Его временная сложность определяется затратами на формирование начальной

популяций и затратами на выполнение эволюции:

к

Т=РТ,+^ Т,, (8)

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

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

7? =Ррс ■2-Ты+Р-(1+рс-2)-рт-Тт,+Р-(1+рс ■2)-Тл, (9)

где рс - вероятность выполнения скрещивания для каждой особи (поскольку при этом образуется два потомка, вероятность в формуле тоже удваивается), рт - вероятность мутации особей в популяции (применяется не только для исходной популяции, но и для новых образовавшихся особей), Тс, - время скрещивания одной пары хромосом, Тт1 - время мутации одной хромосомы, Тш - время декодирования хромосомы для рассматриваемого подмножества данных.

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

Т,=0(Р-Тш) (Ю)

Время декодирования хромосомы вычисляется исходя из времени построения дерева решений и времени оценки его точности (проверки на тестовом множестве данных). Расчет временной сложности величины выполняется по формуле:

Т,1=0^сГМа) + 0(Ыи-01), (11)

где N„1 и Ы„ - размеры обучающего и тестового множества данных (для рассматриваемого узла дерева решений) соответственно, Ма - количество атрибутов в

выборке данных, Р, - глубина поддерева, построенного от рассматриваемого узла дерева решений (определяется исходя из общих ограничений по глубине). Количество атрибутов Ма — величина постоянная для всех узлов дерева решений. Глубина поддерева Ц зависит от общего ограничения максимальной глубины дерева решений, а также от уровня узла в иерархической структуре дерева. Для расчета общей временной сложности декодирования хромосом на всех этапах эволюции введем промежуточную величину в,, соответствующую временной сложности декодирования хромосом для всех узлов дерева эвристик, находящихся на одном уровне. Индекс / при этом может варьироваться в пределах [1,/)], где О — максимальная глубина дерева решений. Тогда временная сложность:

о

Т = П,+ч£Ч, (12)

1=1

где — время формирования начальной популяции.

Величина ¿2/ рассчитывается исходя из временной сложности декодирования всех хромосом, соответствующих узлам, находящимся на одном уровне дерева.

^ = (13)

м

где К] — количество узлов дерева решений, находящихся на уровне 1.

Подставив в (13) выражения для расчета 7}, получим оценку величины

к,

0='

к,

(14)

Поскольку Р, Ма и О/ являются постоянными величинами для всех узлов, находящихся на одном уровне дерева решений, их можно вынести за пределы оператора суммы. Переменные ^ и А',, в формуле (14) соответствуют размерам обучающего и тестового множества данных для отдельно взятого узла дерева решений, находящегося на уровне О;. Поскольку узлы дерева решений на одном уровне должны покрывать все множество исходных данных, суммы величин Ыщ и Л',, равняются общему размеру обучающего и тестового множества соответственно. Таким образом, формула (14) принимает вид.

П, = 0{Р^„-Ма)+0(Р-МгВ), (15)

где №„ и Л', - размеры обучающего и тестового множества для всей выборки исходных данных соответственно.

Подставив выражение для в формулу (12), и, исключив из нее время формирования начальной популяции (оно пренебрежимо мало по сравнению с временем выполнения эволюции), получим оценку временной сложности.

Т = 0(Р-Ыо-Ма-£>) + <9| Р-Ы,-¿А) (16)

Значение О/ соответствует максимальной глубине поддерева, построенному от узла дерева решений, находящемся на уровне I. Для первого уровня (корень дерева

15

решений) О, = Д, что соответствует максимальному ограничению по глубине, устанавливаемому пользователем. По мере продвижения от корня к листу дерева величина Д, уменьшается на 1. Следовательно, сумма всех О, равна £> ■(£> +1)/2.

Общая временная сложность генетического алгоритма определяется исходя из временной сложности построения деревьев решений и временной сложности оценки их точности. Первая величина линейно зависит от размера популяции Р, размера обучающего множества Ит количества атрибутов Ма и максимальной глубины дерева решений Л. Вторая величина имеет квадратичную зависимость от глубины Б и линейную зависимость от размера популяции Р и размера тестового множества А',.

Т = 0(Р-Ы<,-Ма-0) + 0(Р-М1 П2) (17)

Учитывая, что величины Р, Ма и Д обычно на несколько порядков меньше размера выборки данных, а величины Ыа и N. определяются, исходя из общего размера обучающей выборки Ы, можно принять

Т = 0(Ю (18)

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

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

Реализация комплекса программ для проведения вычислительного эксперимента была выполнена на платформе «1С:Предприятие 8» в виде отдельной конфигурации, учитывая существенный спрос на аналитическую поддержку деятельности со стороны предприятий, автоматизированных на платформе 1С, а также наличие накопленных массивов данных в их информационных системах, что позволило провести эксперимент на реальных данных. Структура комплекса показана на рисунке 3, его программные блоки можно использовать в готовом виде в составе реальных систем анализа данных в различных сферах деятельности.

Рисунок 3 - Структура комплекса программдля выполнения вычислительного эксперимента

16

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

В диссертации представлено три практических задачи, при решении которых был использован комплекс программ: анализ бизнес-процессов продаж программных продуктов в CRM-системе ООО «Бизнес-Софт», анализ исполнительской дисциплины сотрудников в системе электронного документооборота, классификация учебных задач по уровню сложности в системе электронного обучения.

В качестве примера представим решение первой задачи. В процессе начальной настройки модели было отобрано 12 признаков бизнес-процесса, способных в той или иной степени повлиять на результат продажи. В качестве целевого атрибута (класса) был выбран признак, принимающий одно из двух значений: «Продажа» или «Отказ клиента». В результате был построен классификатор для прогнозирования успешности бизнес-процесса с частотой ошибок не более 12%. Внедрение классифицирующей подсистемы в ООО «Бизнес-Софт» позволило выявить основные факторы, влияющие на эффективность продаж программных продуктов, а также устранить нежелательные причины, приводящие к отсеиванию клиентов на той или иной стадии взаимодействия с ними.

В заключении формулируются основные результаты работы.

В приложениях приведены блок-схема алгоритма и пример дерева решений.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработаны алгоритмы для реализации основных генетических операторов и общий алгоритм построения дерева классификации.

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

4. Разработан комплекс проблемно-ориентированных программ для проведения вычислительного эксперимента, выполнена его реализация в виде отдельной конфигурации на платформе 1С: Предприятие.

5. Проведен вычислительный эксперимент на данных репозитория UCI Machine Learning Repository и на реальных данных информационных систем предприятий. Экспериментальное исследование подтвердило достоверность и эффективность результатов, полученных в работе.

17

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК России:

1. Ржеуцкий A.B. Применение эволюционных алгоритмов в задачах обучения по прецедентам / A.B. Ржеуцкий // Системы управления и информационные технологии. № 1.2(39), 2010.-С. 264-268

2. Ржеуцкий A.B. Метод построения дерева классификации на основе генетического алгоритма комбинирования эвристик / A.B. Ржеуцкий, С.Ю. Ржеуцкая // Системы управления и информационные технологии. № 2(44), 2011. - С. 62-66

3. Ржеуцкий A.B. Эволюционный алгоритм построения дерева решений /A.B. Ржеуцкий, A.A. Суконщжов / /Программные продукты и системы. № 3, 2011. - С.22-26

Другие статьи и материалы конференций:

4. Ржеуцкий A.B. Применение эволюционного алгоритма классификации данных в интеллектуальных учебных комплексах / A.B. Ржеуцкий // Проведение научных исследований в области информационно-телекоммуникационных технологий: Материалы всероссийской конференции. - М:, 2010. - С.73-75

5. Ржеуцкий A.B. Мастер анализа данных в информационных системах на основе 1С: Предприятие / A.B. Ржеуцкий, А.Н. Швецов // Молодежь и высокие технологии: Материалы всероссийской студенческой олимпиады (Конкурс компьютерных программ). - Вологда: ВоГТУ, 2007. - С.402-404

6. Ржеуцкий A.B. Расширение возможностей анализа данных в информационных системах на основе 1С: Предприятие / A.B. Ржеуцкий, С.Ю. Ржеуцкая // Вузовская наука -регионам: Материалы Всероссийской научной конференции. - Вологда: ВоГТУ, 2007. - Т.2 -С.270-274

7. Ржеуцкий A.B. Программная реализация методов анализа данных в системе 1С Предприятие 8.0 / A.B. Ржеуцкий, A.A. Суконщиков // Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта: Материалы 4-й международной научно-технической конференции. - Вологда: ВоГТУ, 2007, с 101-105

8. Ржеуцкий A.B. Методы анализа данных и прогнозирования в системах поддержки принятия решений / A.B. Ржеуцкий, A.A. Суконщиков // Материалы Ежегодных смотров -сессий аспирантов и молодых ученых по отраслям наук. Научные направления: «Технические науки», «Экономические науки». - Вологда: ВоГТУ, 2007, С67-72

9. Ржеуцкий A.B. Использование деревьев решений на основе искусственных нейронных сетей в задачах прогнозирования / A.B. Ржеуцкий, A.A. Суконщиков // Вузовская наука - регионам: Материалы шестой всероссийской научно-технической конференции. -Вологда: ВоГТУ, 2008. - Т. 1 - С.239-241

10. Ржеуцкий A.B. Средства наглядного представления нейронных сетей для решения задач прогнозирования / A.B. Ржеуцкий, A.A. Суконщиков // Молодые исследователи -регионам' Материалы всероссийской научно-технической конференции студентов и аспирантов.-Вологда: ВоГТУ,2008,- Т. 1-С.413-416

11. Ржеуцкий A.B. Интеграция САПР в информационные системы производственного планирования и управления / A.B. Ржеуцкий // Развитие деревянного домостроения в Вологодской области. Проблемы и практические решения: Материалы межрегиональной научно-практической конференции 29 мая 2008 года. - Вологда: Издательский центр ВИРО, 2008,- С.90-95

12. Ржеуцкий A.B. Расчет стоимости разработки программного продукта с использованием конструктивной модели анализа / A.B. Ржеуцкий, A.A. Суконщиков // Вузовская наука - региону: Материалы седьмой всероссийской научно-технической конференции. - Вологда: ВоГТУ, 2009. - Т. 1, С. 265-267

13. Ржеуцкий A.B. Построение оптимального дерева решений в задаче классификации данных / A.B. Ржеуцкий, А.А.Суконщиков, И.А. Кузнецова // Информационные технологии моделирования и управления, №6(58), 2009 -С.301-305

14. Ржеуцкий A.B. Масштабируемый алгоритм построения деревьев классификации / А.В.Ржеуцкий, С.Ю. Ржеуцкая // Нейроинформатика и общество: труды научной конференции / Под ред. B.J1. Дунина-Барковскош, А.Н. Швецова. - Вологда: ВоГТУ. - 2011. С.50-59.

Подписано в печать 9.07.2012 г. Формат 60x84/16. Печать офсетная. Бумага офисная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ №2SZ ■

Отпечатано: РИО ВоГТУ, г. Вологда, ул. Ленина, д. 15

Введение.

1. Анализ существующих подходов к решению задачи классификации на основе обучения по прецедентам. Постановка задачи исследования.

1.1. Содержательная постановка задачи классификации на основе обучения по прецедентам.

1.2. Формальная постановка задачи классификации.

1.3. Оценка качества классификатора.

1.4. Сравнительный анализ основных моделей классификации.

1.5. Генетические алгоритмы в задачах машинного обучения.

1.6. Постановка задачи исследования.

Выводы по главе 1.

2. Разработка метода и эффективных алгоритмов построения деревьев классификации на основе генетического программирования.

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

2.1.1. Алгоритм ID3.

2.1.2. Алгоритм С4.5.

2.1.3. Алгоритм CART.

2.1.4. Результаты анализа классического метода и алгоритмов построения деревьев классификации.

2.2. Предлагаемый метод построения деревьев классификации на основе применения генетического алгоритма комбинирования эвристик.

2.2.1. Виды эвристик, используемые при построении дерева классификации.

2.2.2. Выбор представления дерева классификации в виде особи генетического алгоритма.

2.2.3. Общее описание алгоритма.

2.2.4. Формирование начальной популяции.

2.2.5. Оператор кроссовера.

2.2.6. Оператор мутации.

2.2.7. Выполнение эволюции особей. Переход к новому этапу.

2.3. Используемые структуры данных.

Выводы по главе 2.

3. Реализация и анализ алгоритмов построения деревьев классификации. Вычислительный эксперимент на тестовых данных.

3.1. Особенности реализации алгоритмов.

3.1.1. Борьба с переобучением. Выделение тестовой и экзаменационной выборки данных.

3.1.2. Использование скользящего контроля для оценки точности классификации.

3.1.3. Обработка числовых значений целевых атрибутов. Дискретизация данных.

3.2. Анализ вычислительной сложности алгоритма.

3.2.1. Асимптотическая оценка вычислительной сложности алгоритма.

3.2.2. Экспериментальное исследование времени исполнения алгоритма.

3.3. Экспериментальное сравнение реализованных алгоритмов с известными алгоритмами классификации на основе нейронных сетей.

3.3.1. Подбор оптимальной архитектуры нейронный сети. Классификация данных с дискретными значениями целевого атрибута.

3.3.2. Сравнение результатов классификации при наличии пропущенных данных.

3.3.3. Сравнение результатов классификации с числовыми значениями атрибутов.

Выводы по главе 3.

4. Комплекс проблемно-ориентированных программ для проведения вычислительного эксперимента. Прикладные результаты работы.

4.1. Разработка структуры комплекса проблемно-ориентированных программ для проведения вычислительного эксперимента.

4.1.1. Методика построения и использования классификационной модели.

4.1.2. Структура системы анализа данных с использованием подсистемы классификации.

4.1.3. Структура комплекса программ для проведения вычислительного эксперимента.

4.2. Применение результатов работы для анализа данных в CRM-системе предприятия.

4.2.1. Описание предметной области.

4.2.2. Постановка задачи классификации, определение входных величин.

4.2.3. Сравнение результатов с известными алгоритмами классификации.

4.3. Применение результатов работы для анализа исполнительской дисциплины сотрудников в системе электронного документооборота.

4.3.1. Описание предметной области.

4.3.2. Постановка задачи классификации, определение входных атрибутов.

4.3.3. Сравнение результатов с известными алгоритмами классификации.

4.4. Применение результатов работы для классификации учебных задач по их сложности в системе электронного обучения.

4.4.1. Описание предметной области.

4.4.2. Постановка задачи классификации, определение входных атрибутов.

4.4.3. Сравнение результатов с известными алгоритмами классификации.

Выводы по главе 4.

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

На современном этапе одним из основных направлений развития систем анализа данных является разработка новых вычислительных методов и алгоритмов анализа с помощью обобщенных математических моделей, способных к обучению на основе совокупности фактов (прецедентов), зафиксированных в информационной системе предприятия. Данное направление, получившее название обучения по прецедентам (машинного обучения - machine learning), развивается в работах С.А. Айвазяна, П. Бартлетта, В.Н. Вапника, К.В. Воронцова, Ю.И. Журавлева, B.JI. Матросова, К.В. Рудакова, Р. Фишера, А.Я. Червоненкиса и др. [1, 6, 7, 11, 37]

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

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

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

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

Объектом диссертационного исследования являются модели классификации в применении к системам анализа данных.

Предметом исследования являются методы и алгоритмы обучения моделей классификации и комплексы программ для решения задачи классификации.

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

Основные задачи исследования.

1. Определить критерии качества обученной модели классификации применительно к системам анализа данных.

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

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

4. Выполнить реализацию предложенного метода и алгоритмов в виде комплекса проблемно-ориентированных программ для проведения вычислительного эксперимента.

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

Научная новизна

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

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

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

4. Разработан комплекс проблемно-ориентированных программ для проведения вычислительного эксперимента на основе предложенного метода и алгоритмов.

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

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

На защиту выносятся следующие основные положения и результаты.

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

2. Структуры данных и алгоритмы для реализации основных генетических операторов, адаптированные с учетом специфики построения дерева классификации.

3. Общий алгоритм реализации предложенного метода построения дерева классификации, обладающий свойством масштабируемости.

4. Комплекс проблемно-ориентированных программ на основе предложенного метода для проведения вычислительного эксперимента.

Внедрение результатов исследования. Теоретические и практические результаты диссертационной работы внедрены в программные продукты ООО «Логасофт». В настоящее время разработанное автором программное обеспечение апробировано в Департаменте финансов Вологодской области в составе системы электронного документооборота и в СЯМ-системе ООО «Бизнес-софт», что подтверждено актами о внедрении.

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

Материалы работы использованы в Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 20092013 годы в рамках проектов «Информационные системы в подготовке специалистов по направлению «Теплоэнергетика», «Разработка методов формализации и верификации распределенных информационно-поисковых систем на основе сервис-ориентированной архитектуры», «Методология построения интеллектуальных агентно-ориентированных учебных комплексов для многоуровневой подготовки специалистов технического профиля».

Апробация результатов исследования. Результаты работы докладывались и получили положительную оценку на следующих конференциях: Всероссийская научно-практическая конференция «Информационно-телекоммуникационные технологии» (Москва, 2010г.), Международная конференция «Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта» (Вологда, 2007г.), Семинар вологодского отделения РАН по искусственному интеллекту (Вологда, 2010г.), Всероссийская научная конференция студентов и аспирантов «Молодые исследователи - регионам» (Вологда, 2006, 2007, 2008 гг.), Всероссийская конференция «Вузовская наука - региону» (Вологда, 2007, 2008, 2009 гг.).

Публикации. По материалам диссертационного исследования опубликовано 14 печатных работ, из них три в журналах, рекомендованных ВАК.

Структура диссертационной работы. Работа состоит из введения, четырех глав, заключения, библиографического списка и трех приложений. Текст изложен на 145 страницах, содержит 27 рисунков и 11 таблиц. Библиографический список включает 101 наименование.

Основные результаты диссертационного исследования состоят в следующем.

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

2. Разработаны алгоритмы для реализации основных генетических операторов и общий алгоритм построения дерева классификации.

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

4. Разработан комплекс проблемно-ориентированных программ для проведения вычислительного эксперимента, выполнена era реализация в виде отдельной конфигурации на платформе 1С: Предприятие.

5. Проведен вычислительный эксперимент на данных репозитория UCI Machine Learning Repository и на реальных данных информационных систем предприятий. Экспериментальное исследование подтвердило достоверность и эффективность результатов, полученных в работе.

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

Заключение

1. Айвазян С.А. Прикладная статистика в задачах и упражнениях / С .А. Айвазян, B.C. Мхитарян. М.: ЮНИТИ-ДАНА, 2001. - 270 с.

2. Анализ данных и процессов: учеб. пособие / A.A. Барсегян, М.С. Куприянов, И.И. Холод, М.Д. Тесс, С.И. Елизаров. 3-е издание перераб. и доп. - СПб.: БХВ-Петербург, 2009. - 512 с

3. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Воронеж: ВГТУ, 1995

4. Божич В.И. Генетический алгоритм обучения двухслойного персептрона для задачи классификации образов / ВИ. Божич, Р.Н. Кононенко // Программные продукты и системы, 2002, №1.

5. Валиахметова Ю.И. Мультиметодная технология моделирования ортогональной упаковки и размещения прямоугольно-ориентированных заготовок. Автореферат дисс. на соиск. уч. степ. канд. техн. наук спец. 05.13.18-Уфа, 2008, 19 с.

6. Вапник В.Н. О равномерной сходимости частот появления событий к их вероятностям /В.Н. Вапник, А.Я. Червоненкис // Теория вероятностей и ее применения, 1971, Т. 16, № 2. С. 264-280.

7. Вапник В.Н. Теория распознавания образов. /В.Н. Вапник, А.Я. Червоненкис М.: Наука, 1974. - 415 с.

8. Вежневец В. Оценка качества работы классификаторов. Электронный ресурс. / В. Вежневец // Компьютерная графика и мультимедиа. Выпуск №4(1)/2006. Режим доступа: http://cgm.computergraphics.ru/content/view/106

9. Венцель Е.С. Теория вероятностей. / Е.С. Венцель М.: Высшая школа, 2002. - 575 с.

10. Ю.Ветров Д.П., Кропотов Д.А. Алгоритмы выбора моделей и построения коллективных решений в задачах классификации, основанные на принципе устойчивости. М: Комкнига, 2006. 112 с.е

11. П.Воронцов K.B. Комбинаторная теория надежности обучения по прецедентам. Дис. док. физ.-мат. наук: 05-13-17. Вычислительный центр РАН, 2010.- 271 с.

12. Воронцов К.В., Инякин A.C., Лисица A.B. Система эмпирического измерения качества алгоритмов классификации // Докл. всеросс. конф. Математические методы распознавания образов-13. М.: МАКС Пресс, 2007. - С. 577-580.

13. Воронцов К.В. Комбинаторный подход к проблеме переобучения // Докл. всеросс. конф. Математические методы распознавания образов-14. -М.: МАКС Пресс, 2009. С. 18-21.

14. Галушкин А.И., Фомин Ю.И. Нейронные сети как линейные последовательные машины. М.: Изд-во МАИ, 1991.

15. Гил л Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир,1985

16. Гитис Л.Х. Статистическая классификация и кластерный анализ / Л.Х. Гитис. М. : МГГУ, 2003. - 157 с.

17. Гладков Л. А. Генетические алгоритмы./ Л.А. Гладков, В.В. Курейчик, В.М. Курейчик М.: Физматлит. 2006.

18. Горбань А.Н. Обучение нейронных сетей. М.: изд. СССР-США СП "ParaGraph", 1990. 160 с.

19. Гуров С.И. Оценка надежности алгоритмов классификации./ С.И. Гуров М.: Издательский отдел ф-та ВМиК МГУ, 2002 - 45 с.

20. Деревья решений //BaseGroup Labs. Технологии анализа данных Электронный ресурс. Режим доступа: http://www.basegroup.ru/library/analysis/tree/

21. Дюк В. Data Mining интеллектуальный анализ данных Электронный ресурс./ Режим доступа: http://www.interface.ru/fset.asp?Url=/oracle/dmiad.htm

22. Ежов A.A. Нейрокомпьютинг и его применение в экономике и бизнесе./ A.A. Ежов, С.А. Шумский. М: 1998. 71 с.

23. Ивахненко А. Г., Юрачковский Ю. П. Моделирование сложных систем по экспериментальным данным. М.: Радио и связь, 1987 120 с.

24. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах. — Открытые системы, № 4, 1997, с. 41-44.

25. Кнут, Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы/ Д. Кнут; Пер. с англ. М.: Изд-во "Вильяме", 2000 - 720 с.

26. Компания NeuroProject. Каталог программных продуктов Электронный ресурс. Режим доступа: http://www.neuroproject.ru/catalogue.php

27. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО: Ьином, 2004 960 е.

28. Круглов В.В Искусственные нейронные сети. Теория и практика / В.В. Круглов, В.В. Борисов М.: Горячая линия - Телеком, 2001 - 382 с.

29. Куликов A.B. Исследование и разработка алгоритмов обобщения на основе теории приближенных множеств / A.B. Куликов. Автореферат дисс.на соиск. уч. степени канд. техн. наук спец. 05.13.11 М., 2004 - 21 с.

30. Лабоцкий В.В. Управление знаниями: технологии, методы и средства представления, извлечения и измерения знаний Минск: БГЭУ, 2006.

31. Лбов Г.С., Старцева Н. Г. Логические решающие функции и вопросы статистической устойчивости решений. Новосибирск: Изд-во ИМ СО РАН, 1999.-211 с.

32. МакКаллок У.С., Питтс В. Логическое исчисление идей, относящихся к нервной активности // Нейрокомпьютер, 1992. №|3, 4. С. 4053.

33. Машинное обучение (курс лекций, К.В.Воронцов) Электронный ресурс. / Режим доступа: http://www.MachineLearning.ru.

34. Медведев B.C., Потемкин В.Г Нейронные сети. Matlab 6 Диалог-МИФИ. 2002, 496 стр

35. Методы классификации и прогнозирования Электронный ресурс. /Data Mining. Designed by Anton Grebenschikov, 2009. Режим доступа: http://kpi.ua/do/work/RGRyDATAMINING/main.html

36. Минский M., Пайперт С. Персептроны. M.: Мир, 1971.

37. Неделько В.М. Критерий оценки качества решающей функции по эмпирическому риску в задаче классификации // Искусственный интеллект. Научно-теоретический журнал. Донецк, 2000, № 2.С. 172-178

38. Норенков И.П. Генетические методы структурного синтеза проектных // Информационные технологии, 1998. № 1.С. 9-13

39. Норенков И. П. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Информационные технологии, 1999, №2.

40. Носов Д.А., Ржеуцкая С.Ю. Применение генетического алгоритма комбинирования эвристик в задаче одномерной упаковки

41. Орлов А.И. Нечисловая статистика Электронный ресурс. /А.И. Орлов М.: МЗ-Пресс, 2004.-Режим доступа: http://www.aup.ru/books/ml62

42. Паклин Н.Б., Орешков В.И. Бизнес-аналитика: от данных к знаниям (+ CD): учеб. пособие. — 2-е изд., перераб. и доп.— СПб.: Питер, 2010. — 704 с.

43. Паклин Н.Б. Обучаем нейронную сеть генетическим алгоритмом. Электронный ресурс. Режим доступа: http://paklin.newmail.ru/mater/genenet.html

44. Пытьев Ю.П. Возможность. Элементы теории и применения. М.: Эдиториал УРСС, 2000. 192 с.

45. Ржеуцкий A.B. Применение эволюционных алгоритмов в задачах обучения по прецедентам / A.B. Ржеуцкий // Системы управления и информационные технологии. № 1.2(39), 2010. С. 264-268

46. Ржеуцкий A.B. Метод построения дерева классификации на основе генетического алгоритма комбинирования эвристик / A.B. Ржеуцкий, A.A. Суконщиков // Системы управления и информационные технологии. № 2(44), 2011.-С. 62-66

47. Ржеуцкий A.B. Расширение возможностей анализа данных в информационных системах на основе 1С: Предприятие / A.B. Ржеуцкий, С.Ю. Ржеуцкая // Вузовская наука регионам: Материалы Всероссийской научной конференции. - Вологда: ВоГТУ, 2007. - Т.2 - С.270-274

48. Ржеуцкий A.B. Масштабируемый алгоритм построения деревьев классификации / А.В.Ржеуцкий, С.Ю. Ржеуцкая //Нейроинформатика и общество: труды научной конференции / Под ред. B.JI. Дунина-Барковского, А.Н. Швецова. Вологда: ВоГТУ. - 2011. С. - 50-60.

49. Ржеуцкий A.B. Эволюционный алгоритм построения дерева решений / A.B. Ржеуцкий, A.A. Суконщиков // Программные продукты и системы. № 3, 2011. С. 22-26

50. Ржеуцкий A.B., Суконщиков A.A. Расчет стоимости разработки программного продукта с использованием конструктивной модели анализа

51. Текст. / A.B. Ржеуцкий // Вузовская наука региону: Материалы седьмой всероссийской научно-технической конференции. В 2-х т. - Вологда: ВоГТУ, 2009. - Т.1, С. 265-267.

52. Ржеуцкий A.B. Построение оптимального дерева решений в задаче классификации данных Текст. / A.B. Ржеуцкий, A.A.Суконщиков, И.А. Кузнецова // Информационные технологии моделирования и управления, №6(58), 2009 С.301-305

53. Родионов П.Е., Методика извлечения знаний в задачах анализа рядов динамики с использованием нейронных сетей, дис. к.т.н. СПБ, СПбГЭТУ , 2000, 132 с.

54. Сараев А.Д., Щербина O.A. Системный анализ и современные информационные технологии //Труды Крымской Академии наук. — Симферополь: СОНАТ, 2006. — С. 47-59

55. Симанков B.C. Адаптивное управление сложными системами на основе теории распознавания образов: Монография (научное издание) / В. С. Симанков, Е. В. Луценко. Техн. ун-т Кубан. гос. технол. ун-та. Краснодар, 1999.-318 с.

56. Скобцов Ю.А. Основы эволюционных вычислений. Донецк: ДонНТУ, 2008. 326 с.

57. Терехов С.А. Технологические аспекты обучения нейросетевых машин. / С.А. Терехов // Лекция для VIII научно-технической конференции «Нейроинформатика-2006». М.:, МИФИ, 2006. - 49 с.

58. Терехов С.А. Ансамбли нейросетевых моделей. Гениальные комитеты умных машин. / С.А. Терехов // Лекция для школы-семинара "Современные проблемы нейроинформатики", М.:, МИФИ, 2007. 36 с.

59. Трауб Д., Васильковскии Г., Вожьняковский X. Информация, неопределённость, сложность: Пер. с англ. М.: Мир, 1988. 184с

60. Щавелёв JI.В. Способы аналитической обработки данных для поддержки принятия решений // СУБД. 1998. № 4-5 С.41-44.

61. Asuncion A., Newman D. UCI machine learning repository: Tech. rep.: University of California, Irvine, School of Information and Computer Sciences, 2007. http://www.ics.uci.edu/Dmlearn/MLRepository.html.

62. L. Breiman, J.H. Friedman, R.A. Olshen, and C.T. Stone. Classification and Regression Trees. Wadsworth, Belmont, California, 1984. 368 p.

63. B.Chandra, S.Mazumdar, V.Arena, N.Parimi. Elegant Decision Tree Algorithm for Classification in Data Mining. Электронный ресурс. Режим доступа:http://www.masters.donntu.edu.ua/2007/fvti/taran/library/libarticlel0.htm

64. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning // Adison-Wesley Publ., 1989. 432 p.

65. Gramer N.L. A representation for the adaptive generation of simple sequential programs. Proceedings of an inter, conf. on genetic algorithms and their applications. N.J.: Lawrence Erlbaum, 1985. pp. 183-187

66. Gregory Piatetsky-Shapiro. Machine Learning, Data Mining, and Knowledge Discovery: The Third Generation (Extended Abstract). ISMIS 1997. -pp. 48-49

67. De Jong K. On using genetic algorithms to search program spaces// Proc. of the second inter, conf. on genetic algorithms. N.J.: Lawrence Erlbaum, 1987. -pp. 210-216

68. Fujiku C., Dickinson J. Using the genetic algorithm to generate LISP source code to solve the prisoners dilemma. Proceedings of the second inter, conf. on genetic algorithms. N.J.: Lawrence Erlbaum, 1987. pp. 236-240.

69. Hill Climbing. Электронный ресурс. Режим доступа: http://en.wikipedia.org/wiki/Hillclimbing

70. Holland J. P. Adaptation in Natural and Artificial Systems. University of Michigan, 1975. 96 p

71. Hunt E.B., Marin, J., Stone, P.J. Experiments in induction // New York: Academic Press, 1966. 247 p

72. Keit M.J., Martin M.C. Genetic Programming in С++. Cambridge: MA:MIT Press, 1994. pp. 285-310.

73. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing // Science. 1983. Vol. 220, no. 4598. Pp. 671-680.

74. Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection // IJCAI.1995.Pp. 1137-1145. http://citeseer.nj.nec.com/kohavi95study.html.

75. Koza J. Genetic Evolution and Co-EVolution of Computer Programs / Proceedings of Second Conference on Artificial Life. Redwood City, CA: Addison-Wesley. 1992. pp. 603-629.

76. Koza J. Genetic programming. On the Programming of Computers by Means of Natural Selection. MA: The MIT Press, 1998. 609 p.

77. Koza J. R. Future Work and Practical Applications of Genetic Programming. Handbook of Evolutionary Computation. Bristol: IOP Publishing Ltd, 1997.-pp. 1-6

78. Kutin S., Niyogi P. Almost-everywhere algorithmic stability and generalization error: Tech. Rep. TR-2002-03: University of Chicago, 2002. Электронный ресурс. Режим доступа: http://citeseer.nj.nec.com/kutin02almosteverywhere.html

79. Lankhorst М. М. A Genetic Algorithm for the Induction of Nondeterministic Pushdown Automata. Computing Science Report. University of Groningen Department of Computing Science. 1995. pp. 741-746.

80. Linton R. Adapting binary fitness functions in genetic algorithms / Proceedings of the 42nd annual Southeast regional conference. NY: ACM Press. 2004, pp. 391-395.

81. Lucas S. M. Evolving Finite State Transducers: Some Initial Explorations / Genetic Programming: 6th European Conference (EuroGP'03). Berlin: Springer. 2003, pp. 130-141.

82. Miller В., Goldberg M. Genetic algorithms, tournament selection, and the effects of noise // Complex Systems. 1995. V. 9,1. 3, pp. 193-212.

83. O'Reilly U.-M. An analysis of genetic programming. Diss., Carleton Uni. Ottawa, 1995.

84. Power D. J. «What is a DSS?» // The On-Line Executive Journal for Data-Intensive Decision Support, 1997. v. 1. N3 pp. 223-232.

85. J. Ross Quinlan. C4.5: Programs for Machine learning. Morgan Kaufmann Publishers 1993. pp. 236-243

86. J. Shafer, R. Agrawal, and M. Mehta SPRINT: A Scalable Parallel Classifier for Data Mining, Proc. 22nd Int'l Conf. Very Large Data Bases, Morgan Kaufmann, San Francisco, 1996, pp. 544-555

87. Thieranf R.J. Decision Support Systems for Effective Planing and Control. Englewood Cliffs, N.J: Prentice Hall, Inc, 1982. - 235 p.

88. Tonella P. Evolutionary testing of classes // ISSTA. 2004. Pp. 119—128.

89. Turban, E. Decision support and expert systems: management support systems. Englewood Cliffs, N.J.: Prentice Hall, 1995. — 887 p.