Содержание к диссертации
Введение
1. Анализ существующих подходов к решению задачи классификации на основе обучения по прецедентам. Постановка задачи исследования 12
1.1. Содержательная постановка задачи классификации на основе обучения по прецедентам 12
1.2. Формальная постановка задачи классификации 17
1.3. Оценка качества классификатора 22
1.4. Сравнительный анализ основных моделей классификации 31
1.5. Генетические алгоритмы в задачах машинного обучения 42
1.6. Постановка задачи исследования 45
Выводы по главе 1 47
2. Разработка метода и эффективных алгоритмов построения деревьев классификации на основе генетического программирования 49
2.1. Анализ существующих алгоритмов построения деревьев
классификации как основы для предлагаемого генетического алгоритма.. 49
2.1.1. Алгоритм ID3 51
2.1.2. Алгоритм C4.5 53
2.1.3. Алгоритм CART 54
2.1.4. Результаты анализа классического метода и алгоритмов построения деревьев классификации 57
2.2. Предлагаемый метод построения деревьев классификации на основе применения генетического алгоритма комбинирования эвристик 58
2.2.1. Виды эвристик, используемые при построении дерева классификации 60
2.2.2. Выбор представления дерева классификации в виде особи генетического алгоритма 61
2.2.3. Общее описание алгоритма 62
2.2.4. Формирование начальной популяции 63
2.2.5. Оператор кроссовера 65
2.2.6. Оператор мутации 67
2.2.7. Выполнение эволюции особей. Переход к новому этапу 68
2.3. Используемые структуры данных 72
Выводы по главе 2 74
3. Реализация и анализ алгоритмов построения деревьев классификации. Вычислительный эксперимент на тестовых данных 75
3.1. Особенности реализации алгоритмов 75
3.1.1. Борьба с переобучением. Выделение тестовой и экзаменационной выборки данных 75
3.1.2. Использование скользящего контроля для оценки точности классификации 79
3.1.3. Обработка числовых значений целевых атрибутов. Дискретизация данных 84
3.2. Анализ вычислительной сложности алгоритма 88
3.2.1. Асимптотическая оценка вычислительной сложности алгоритма 89
3.2.2. Экспериментальное исследование времени исполнения алгоритма 93
3.3. Экспериментальное сравнение реализованных алгоритмов с
известными алгоритмами классификации на основе нейронных сетей 94
3.3.1. Подбор оптимальной архитектуры нейронный сети. Классификация данных с дискретными значениями целевого атрибута. 94
3.3.2. Сравнение результатов классификации при наличии пропущенных данных 97
3.3.3. Сравнение результатов классификации с числовыми значениями атрибутов 99
Выводы по главе 3 104
4. Комплекс проблемно-ориентированных программ для проведения вычислительного эксперимента. Прикладные результаты работы 106
4.1. Разработка структуры комплекса проблемно-ориентированных программ для проведения вычислительного эксперимента 106
4.1.1. Методика построения и использования классификационной модели 106
4.1.2. Структура системы анализа данных с использованием подсистемы классификации 109
4.1.3. Структура комплекса программ для проведения вычислительного эксперимента 111
4.2. Применение результатов работы для анализа данных в CRM-системе предприятия 114
4.2.1. Описание предметной области 115
4.2.2. Постановка задачи классификации, определение входных величин 118
4.2.3. Сравнение результатов с известными алгоритмами классификации 120
4.3. Применение результатов работы для анализа исполнительской дисциплины сотрудников в системе электронного документооборота 122
4.3.1. Описание предметной области 122
4.3.2. Постановка задачи классификации, определение входных атрибутов 124
4.3.3. Сравнение результатов с известными алгоритмами классификации 126
4.4. Применение результатов работы для классификации учебных задач по их сложности в системе электронного обучения 127
4.4.1. Описание предметной области 128
4.4.2. Постановка задачи классификации, определение входных атрибутов 129
4.4.3. Сравнение результатов с известными алгоритмами классификации 132
Выводы по главе 4 134
Заключение 135
Список использованных источников 136
Приложения 135
- Формальная постановка задачи классификации
- Предлагаемый метод построения деревьев классификации на основе применения генетического алгоритма комбинирования эвристик
- Использование скользящего контроля для оценки точности классификации
- Структура комплекса программ для проведения вычислительного эксперимента
Введение к работе
Актуальность темы. Современные корпоративные хранилища данных содержат огромные массивы информации, накопленной за длительный период эксплуатации информационных систем предприятий. Различные категории пользователей постепенно начинают осваивать открывшиеся возможности глубокого анализа накопленных данных как средства извлечения знаний, полезных для понимания причин тех или иных явлений в области деятельности и снижающих степень риска при принятии решений. В связи с потребностями практики мощный импульс развития получили вычислительные методы анализа данных с помощью обобщенных математических моделей, способных к обучению на основе совокупности фактов (прецедентов), накопленных в информационной системе. Данное направление, получившее название обучения по прецедентам (машинного обучения – machine learning), развивается в работах С.А. Айвазяна, П. Бартлетта, В.Н. Вапника, К.В. Воронцова, Ю.И. Журавлева, В.Л. Матросова, К.В. Рудакова, Р. Фишера, А.Я. Червоненкиса и др.
В диссертационном исследовании решается одна из основных задач обучения по прецедентам – классификация объектов на основе известной совокупности их признаков (термин «объект» понимается широко, означая любой предмет, понятие или событие, имеющее признаковое описание). Задача состоит в отнесении объекта к одному из заранее заданных, непересекающихся классов, при этом правила классификации извлекаются из обучающей выборки, содержащей аналогичные, но уже классифицированные объекты, на этапе обучения модели классификации. Подсистема классификации является одной из основных составляющих системы анализа данных предприятия, однако внедрение моделей и методов классификации как средства анализа деятельности происходит с большой осторожностью и определенной степенью недоверия со стороны аналитиков предметной области, что во многом объясняется недостаточной проработанностью теоретических и, особенно, прикладных вопросов в данной области.
Одной из самых востребованных на практике является модель классификации на основе деревьев решений, которая представляет собой иерархическую структуру правил классификации. Данная модель, интерпретируемая в терминах предметной области и обладающая способностью к отбору существенных признаков классифицируемых объектов, предоставляет аналитику нетривиальные знания, извлеченные из накопленных данных. Однако используемые в настоящее время «жадные» алгоритмы обучения этой модели не позволяют решать оптимизационную задачу построения дерева классификации с высокой точностью. Перспективным направлением повышения точности классификационной модели при приемлемых затратах времени на ее обучение является генетическое программирование. Генетические алгоритмы успешно используются при обучении других моделей, однако сведений об их применении к построению деревьев классификации в
доступных источниках информации не имеется. Исходя из изложенного, актуальным является исследование теоретических и прикладных аспектов эффективного применения генетического программирования для решения задачи классификации данных на основе модели деревьев решений.
Объектом диссертационного исследования являются модели классификации в применении к системам анализа данных.
Предметом исследования являются методы и алгоритмы обучения моделей классификации и комплексы программ для решения задачи классификации.
Цель диссертационного исследования заключается в разработке метода, алгоритмов и комплекса программ для решения задачи классификации данных, позволяющих повысить качество обученной модели классификации за счет применения генетического программирования на этапе обучения.
Основные задачи исследования.
-
Определить критерии качества обученной модели классификации применительно к системам анализа данных.
-
Разработать вычислительный метод обучения модели классификации на основе деревьев решений, позволяющий повысить качество обученной модели за счет применения генетических алгоритмов.
-
В рамках предложенного метода разработать эффективные алгоритмы реализации генетических операторов и общий алгоритм построения дерева, обладающий свойством масштабируемости.
-
Выполнить реализацию предложенного метода и алгоритмов в виде комплекса проблемно-ориентированных программ для проведения вычислительного эксперимента.
Методы исследования. Методологической базой исследования явились работы по теории машинного обучения и генетического программирования. В работе использовался математический аппарат теории вероятности и статистического анализа в приложении к задаче классификации, методы анализа алгоритмов.
Научная новизна
-
Предложен метод построения деревьев классификации, основанный на применении генетического алгоритма комбинирования эвристик, позволяющий более точно решить оптимизационную задачу формирования структуры дерева, чем известные на настоящий момент методы, следовательно, способный извлекать из обучающей выборки наиболее полные и точные правила классификации.
-
Разработаны эффективные алгоритмы генетических операторов в рамках предложенного метода, обеспечившие повышение точности и обобщающей способности обученной модели классификации.
-
Доказан линейный характер зависимости времени построения дерева классификации от размера обучающей выборки, что позволяет отнести разработанный генетический алгоритм к группе масштабируемых алгоритмов
машинного обучения, предоставляющих возможность эффективной обработки динамично растущих информационных массивов корпоративных хранилищ данных.
4. Разработан комплекс проблемно-ориентированных программ для проведения вычислительного эксперимента на основе предложенного метода и алгоритмов.
Обоснованность и достоверность полученных результатов обеспечивается корректностью применяемого математического аппарата, строгими доказательствами предложенных утверждений; результатами вычислительного эксперимента на тестовых и реальных задачах.
Практическая значимость исследования заключается в разработанном автором программном обеспечении, позволяющем с высокой точностью решать задачи классификации в автоматизированных системах на платформе 1С: Предприятие. Предложенный метод и алгоритмы позволяют повысить точность и обобщающую способность классификационной модели по сравнению со стандартным инструментальным средством построения деревьев классификации, встроенным в платформу 1С: Предприятие, при сохранении всех преимуществ данной модели.
На защиту выносятся следующие основные положения и результаты.
-
Вычислительный метод построения дерева классификации, основанный на применении генетического алгоритма комбинирования эвристик, позволяющий повысить точность и обобщающую способность обученной модели классификации
-
Структуры данных и алгоритмы для реализации основных генетических операторов, адаптированные с учетом специфики построения дерева классификации.
-
Общий алгоритм реализации предложенного метода построения дерева классификации, обладающий свойством масштабируемости.
4. Комплекс проблемно-ориентированных программ на основе предложенного
метода для проведения вычислительного эксперимента.
Внедрение результатов исследования. Теоретические и практические результаты диссертационной работы внедрены в программные продукты ООО «Логасофт». В настоящее время разработанное автором программное обеспечение апробировано в Департаменте финансов Вологодской области в составе системы электронного документооборота и в CRM-системе ООО «Бизнес-Софт», что подтверждено актами о внедрении.
Результаты работы используются в учебном процессе кафедры автоматики и вычислительной техники Вологодского государственного технического университета при преподавании дисциплин «Структуры и алгоритмы обработки данных» и «Программирование и основы алгоритмизации». Разработанная автором подсистема классификации учебных заданий по уровню сложности внедрена в систему электронного обучения кафедры автоматики и вычислительной техники, что подтверждено актом о внедрении.
Материалы работы использованы в Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 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 наименование.
Формальная постановка задачи классификации
Формальная математическая постановка задачи обучения по прецедентам и, в частности, задачи классификации, представлена в [2, 11, 12, 20]. Приведем данную постановку, уточнив некоторые технические детали, которые позволят рассматривать ее не как абстрактную математическую проблему, а прикладную задачу анализа ретроспективных данных [2, 49].
Пусть задано множество объектов X и множество К непересекающихся классов в некоторой, определенное заранее, системе классификации, причем каждому объекту сможет быть поставлен в соответствие класс kL. Уточним, что все объекты множества X имеют одинаковое признаковое описание и представлены в виде вектора признаков.
Существует также решающая функция Х К (истинный классификатор), изначально неизвестная, но на конечном подмножестве объектов {xhx2,...,xN} =X (не на всем множестве X) известны ее значения kt єК. Пары «объект-класс» (хиЩ, которые представляют собой прецеденты, зафиксированы в хранилище данных. Совокупность известных пар fatyN называется обучающей выборкой XN .
Задача обучения по прецедентам заключается в том, чтобы восстановить зависимость/, то есть построить алгоритм a (классификатор): Х К, который бы наилучшим образом (в известном смысле) приближал решающую функцию/ / причем не только на обучающей выборке, но и на всем множестве объектов X.
Более строгой и общей является вероятностная постановка задачи классификации [12, 20], поскольку множество объектов-классов ХхК, вообще говоря, имеет вероятностную природу и утверждение о существовании функции/ X— К можно подвергнуть сомнению, поскольку/ в строгом смысле не является функцией. В нашем исследовании вероятностная постановка задачи классификации имеет существенное значение. В ее основе лежит гипотеза о репрезентативности обучающей выборки, которая формулируется следующим образом [20].
Гипотеза 1.1. На пространстве объектов-классов ХхК задана (обычно неизвестная) плотность распределения вероятностей р(х,к) = Р(к)р(х\к) и любой набор классифицированных объектов является реализацией независимой выборки N случайных величин из генеральной совокупности.
Выборки, удовлетворяющие гипотезе репрезентативности, называются простыми или случайными одинаково распределенными. Вероятности появления объектов каждого из классов Р(к) называются априорными вероятностями классов. Плотности распределения р(х\к) называются функциями правдоподобия классов. Здесь и далее заглавной буквой Р обозначаются вероятности, а прописной р - плотности распределения вероятностей. Вероятностная постановка задачи классификации разделяется на две независимые подзадачи [12]. Задача 1.1. Имеется простая выборка fatyN из неизвестного распределения/? , ) = Р(к)р(х\к). Требуется построить эмпирические оценки априорных вероятностей Р(к) и функций правдоподобия р(х\к) для каждого из классов к а К. Задача 1.2. По известным плотностям распределения р(х,к) и априорным вероятностям Р(к) всех классов fcK. построить алгоритм а(х), минимизирующий вероятность ошибочной классификации. Более строго -алгоритм а(х) должен оптимизировать некоторый функционал качества классификации. Следует отметить, что по трудоемкости задача определения статистических характеристик обучающей выборки превосходит непосредственно задачу классификации, при этом она требует обучающих выборок больших размеров. Постановка задачи классификации имеет простую геометрическую интерпретацию [26] при принятии гипотезы компактности (гипотеза 1.2). Гипотеза 1.2. Объектам, принадлежащим одному классу, в многомерном геометрическом пространстве признаков соответствуют обособленные множества точек, обладающие свойствами хорошей отделимости. А именно: 1. множества объектов различных классов соприкасаются либо в сравнительно небольшом числе точек, либо вообще не соприкасаются; 2. границы классов имеют сравнительно плавную форму - не изрезаны, и у классов отсутствуют глубокие выступы в пределы других классов. В результате различные классы при выполнении гипотезы компактности могут быть разделены достаточно простыми гиперповерхностями. На рисунке 1.3 показаны объекты двух классов в двумерном признаковом пространстве (точки, принадлежащие разным классам, для наглядности показаны в виде окружностей и прямоугольников), обладающие свойствами линейной разделимости, и три разные разделяющие гиперплоскости (в двумерном пространстве это прямые линии). Существуют также другие подходы к постановке задачи классификации, в частности, теория возможности Пытьева [48] и теоретико-множественный подход Трауба и Васильковского [70]. Вне зависимости от способа формализации задачи классификации, общепринятый подход к построению алгоритма а(х) сводится к подбору параметров некоторой, заранее выбранной, модели, иными словами, с помощью обучаюшей выборки выполняется подгонка (fitting) модели под реальную задачу. Введем несколько формальных определений. Определение 1.1. Моделью алгоритмов называется параметрическое семейство отображений A= $ ,0]0с0 , где :ХК - некоторая фиксированная функция, 0 - множество допустимых значений параметров в, называемое пространством параметров. Процесс подбора оптимальных значений параметров в по обучающей выборке XN называют настройкой или обучением модели А.
Предлагаемый метод построения деревьев классификации на основе применения генетического алгоритма комбинирования эвристик
Для повышения точности классификации процесс построения дерева решений предлагается трансформировать в задачу поиска и использования оптимальной последовательности эвристик, применяемых в подзадачах разделения выборки данных в узлах дерева. При этом для решения задачи поиска оптимальной последовательности эвристик возможно применение генетического программирования [49].
Подобный подход уже был успешно применен И.П. Норенковым к задачам синтеза расписаний [42,43] и назван методом комбинирования эвристик (НСМ — Heuristics Combination Method). Имеются работы, в которых рассматривается применение НСМ к задачам оптимальной упаковки и раскроя [5, 44]. К задаче построения деревьев классифиации данный метод применяется впервые.
Главная особенность метода комбинирования эвристик заключается в том, что аллелями служат не значения проектных параметров, а имена эвристик, используемых для определения этих значений. Выполнение условий допустимости переносится в сами эвристики, что делает генетический алгоритм инвариантным к различным задачам (в связи с этой особенностью и возникла идея расширить круг задач, решаемых данным методом, построением деревьев классификации).
Другими словами, в НСМ i-й ген соответствует i-й подзадаче, а i-й аллель есть номер (имя) процедуры (эвристики), реализующей локальную целевую функцию и ограничения i-й подзадачи. В НСМ для каждой подзадачи должно быть сформулировано несколько альтернативных постановок (процедур), именно среди них генетический алгоритм и будет выбирать члены последовательности, приближаясь к оптимальной последовательности эвристик.
Основная идея построения дерева классификации на основе HCM схематично изображена на рисунке 2.1. Схема выполнения генетического алгоритма Из данной схемы понятно, что генетический алгоритм применяется не непосредственно к формированию структуры дерева классификации, но формирует дерево, содержащее оптимальную последовательность эвристик, которые затем используются в процессе построения дерева классификации, структура которого также получается оптимальной (с минимальным значением эмпирического риска). Виды эвристик, используемые при построении дерева классификации Для определения наиболее подходящих эвристик, используемых при формировании узлов дерева классификации, необходимо проанализировать существующие на сегодняшний день критерии разделения данных, используемые в алгоритмах классификации. Одним из наиболее распространенных криериев разделения является индекс Gain(KX), используемый в таких алгоритмах, как ID3 и C4.5 [26, 39]. На основании меры энтропии выбирается атрибут, дающий максимальную информацию о классах. Другим критерием, успешно используемом в алгоритме CART, является индекс Gini(XN), основанный на вычислении расстояний между классами [74] . Помимо перечисленных критериев, в некоторых случаях оказывается эффективен выбор атрибута по количеству различных значений в выборке. Разделение по атрибуту, содержащему максимальное количество различных значений в выборке, зачастую оказывается эффективным для числовых атрибутов. В этом случае в качестве значения разделения можно использовать математическое ожидание множества X. Разделение по атрибуту, содержащему минимальное количество значений в выборке, также иногда оказывается эффективнее предложенных критериев, особенно если речь идет о дискретных (номинальных) атрибутах. Значение разделения в таком случае можно выбрать, также исходя из распределения значений в выборке. Перечисленные критерии разделения можно рассматривать в качестве эвристик, используемых при выполнении генетического поиска. Для борьбы с переобучением предлагается использовать еще один вид эвристики, который связан с остановкой процесса разделения выборки и превращением узла в лист. В этом случае отпадает необходимость использования специфических механизмов отсечения узлов дерева, реализованных в отдельно взятых алгоритмах. Таким образом, в соответствии с предлагаемым алгоритмом, в каждой подзадаче исходной задачи, связанной с разделением выборки, выбирается критерий разделения по одной из следующих эвристик: S1: выбирается атрибут, обладающий наибольшим значением индекса Gain(KX), в соответствие с формулой (2.1); S2: выбирается атрибут, обладающий наибольшим значением индекса Gini(XN), в соответствие с формулой (2.8); S3: выбирается атрибут, содержащий наибольшее количество различных значений в выборке данных; S4: выбирается атрибут, содержащий наименьшее количество различных значений в выборке данных; S5: разделение выборки не производится (узел превращается в лист). При таком подходе процесс построения дерева классификации сводится к нахождению оптимальной последовательности эвристик S1-S5.
Использование скользящего контроля для оценки точности классификации
Скользящий контроль (кросс-проверка, кросс-валидация) является стандартной методикой оценки точности классификации [6, 7, 39, 86]. Фиксируется некоторое множество разбиений исходной выборки на обучающую и экзаменационную подвыборки. Для каждого разбиения выполняется построение модели классификации по обучающей подвыборке, затем оценивается ее средняя ошибка на объектах экзаменационной подвыборки.
Доказано, что если выборки независимы, то средняя ошибка скользящего контроля дает несмещенную оценку вероятности ошибки при классификации [6,7].
Как было показано ранее, обучающую подвыборку целесообразно разделить на 2 множества: обучающее и тестовое. Поскольку оба множества используются при построении модели классификации (на основании тестового множества происходит отбор особей в популяции), то для применения скользящего контроля необходимо рассматривать разбиения исходной выборки не на две, а на три подвыборки: обучающую, тестовую и экзаменационную.
Одним из главных недостатков скользящего контроля является высокая вычислительная сложность. Для вычисления функционала полного скользящего контроля (complete cross-validation) необходимо рассмотреть все возможные разбиения исходной выборки и рассчитать математическое ожидание частоты ошибок на экзаменационной подвыборке. Очевидно, что даже при небольшом размере исходной выборки число таких разбиений будет слишком велико. Поэтому на практике обычно используют случайные разбиения, количество которых определяется, исходя из допустимых затрат времени. Такой подход позволяет получить оценку, максимально приближенную к функционалу полного скользящего контроля, а также рассчитать дисперсию данной величины с целью оценки разброса значений частоты ошибок на различных разбиениях.
Пусть для оценки скользящего контроля используется N различных разбиений обучающей выборки. Обозначим максимальное значение погрешности среди всех разбиений как 0 , минимальное - как ( ш. Также примем, что все рабиения случайны, независимы и равновероятны (гипотеза 1.1). Как показано в [36], значение величины Q(a,X) для случайного разбиения с вероятностью п = не превосходит (/ Это означает, что для получения верхней оценки Q(a,X) с надежностью более 95% достаточно рассмотреть 20 различных разбиений выборки (N=20). На практике использование верхней оценки (j часто оказывается недостаточно, поскольку она может оказаться смещенной относительно среднего значения. Вместо этого обычно рассчитывают доверительный интервал, задающий погрешность средней величины Q(a,X) для произвольного количества разбиений выборки. Как показано в [36], значение величины 0(а,X) для случайного разбиения с вероятностью TJ = - не выходит за пределы интервала [(2 ,(2 ]. Это означает, что для получения двухсторонней оценки Q(a,X) с надежностью более 95% достаточно рассмотреть 40 различных разбиений выборки (N=40). Для оценки ширины доверительного интервала были произведены эксперименты на 3 тестовых задачах из репозитория UCI. Для каждого из 40 случайных разбиений выполнялось построение дерева классификации и рассчитывалось значение Q(a,X) и переобученность 3ju(Xо, X к , определяемая как разность частоты ошибок классификации на обучающей и контрольной выборке данных. При этом рассматривались различные варианты соотношений обучающего и тестового множеств с целью определения пропорции, дающей наименьшую оценку скользящего контроля и ширину доверительного интервала. В качестве примера приведем ниже результаты, полученные на задаче «Car evaluation», содержащей данные по оценке качества автомобилей. Обучающая выборка состоит из достаточно большого числа прецедентов (1728), что позволяет объективно определить точность классификации при различных пропорциях ее разделения. Кроме того, множество классов K содержит лишь 4 различные значения. Это обуславливает предрасположенность данных к обобщению, что, в свою очередь, делает эффект переобучения наиболее заметным. Состав атрибутов, а также их возможных значений в выборке данных, приведен ниже. 1. Buying price – стоимость покупки автомобиля: а) v-hight – очень высокая; б) hight – высокая; в) med – средняя; г) low – низкая. 2. Price of the maintenance – стоимоть обслуживания автомобиля: а) v-hight – очень высокая; б) hight – высокая; в) med – средняя; г) low – низкая. 3. Number of doors – количество дверей: а) 2; б) 3; в) 4; г) 5-more (5 и более). 4. Capacity in terms of persons to carry – количество мест: а) 2; в) 4; г) more (более 4). 5. The size of luggage boot – размер багажника: а) small – маленький; б) med – средний; в) big – большой. 6. Estimated safety of the car – уровень безопасности автомобиля: а) low – низкий; б) med – средний; в) high – высокий. 7. Car acceptability – качество (приемлемость) автомобиля: а) unacc – не приемлемый; б) acc – приемлемый; в) good – хороший; г) v-good – очень хороший. Результаты экспериментального сравнения точности классификации и обобщающей способности реализованного генетического алгоритма в сравнении с другими алгоритмами приведены в таблице 3.1.
Структура комплекса программ для проведения вычислительного эксперимента
Реализация комплекса программ для проведения вычислительного эксперимента была выполнена на платформе «1С:Предприятие 8» (в дальнейшем будем называть ее «1С») с учетом возможности практического использования отдельных блоков комплекса для решения реальных практических задач и принимая во внимание, что в информационных системах на платформе 1С уже накоплены информационные массивы для проведения вычислительного эксперимента на реальных данных.
Основное преимущество платформы «1С» заключается в возможности конфигурирования и настройки любого прикладного решения в соответствии с решаемой задачей. Структура данных в сочетании с механизмами их взаимодействия, а также набором интерфейсов и ролей пользователей описывается в виде совокупности объектов, каждый из которых отражает определенный аспект рассматриваемой предметной области и может быть представлен в виде одной или нескольких таблиц базы данных. Совокупность таких объектов называется конфигурацией. Последняя может быть сохранена на диск в виде отдельного файла, содержащего полное описание функциональности прикладного решения и не включающего при этом данные таблиц информационной базы.
Платформа «1С» включает в себя гибкие возможности по работе с конфигурациями, одной из которых является механизм их сравнения и объединения. При этом подразумевается, что существующие в текущей конфигурации объекты будут сопоставлены с объектами новой конфигурации, загружаемой из сохраненного файла. Результат объединения зависит не только от структуры сравниваемых конфигураций, но и от выбора пользователя, выполняющего данную операцию. Для каждого объекта возможны следующие варианты: 1. Объект присутствует в обеих конфигурациях. В случае нахождения отличий на усмотрение пользователя происходит замещение объекта. Для модулей, написанных на встроенном языке 1С, при этом дополнительно предусмотрен режим объединения процедур и функций, а также содержащихся в них строк. 2. Объект присутствует только в текущей конфигурации. Удаление объекта не происходит, данные в информационной базе сохраняются. 3. Объект присутствует только в загружаемой конфигурации. На усмотрение пользователя он может быть добавлен в текущую конфигурацию. Таким образом, процесс сравнения и объединения можно упрощенно рассматривать как возможность добавления в текущую конфигурацию новых объектов без изменения существующих. Для этого необходимо лишь отсутствие общих объектов, присутствующих одновременно в текущей и в загружаемой конфигурациях. Такой подход открывает широкие возможности для создания универсальных подсистем, которые могут быть легко внедрены в любое прикладное решение на платформе «1С». Кроме того, возможности системы «1С» позволяют создавать общие интерфейсы, представляющие собой определенные разделы меню и кнопки панели инструментов, которые автоматически включаются в состав существующего пользовательского интерфейса. Это еще раз подтверждает отсутствие необходимости изменять существующие объекты конфигурации, в том числе и интерфейсы пользователей. С точки зрения решаемой задачи, для создания программного комплекса необходимо разработать конфигурацию, состоящую из следующих объектов. 1. База прецедентов. Содержит информацию о решаемой задаче и обучающую выборку. Реализуется в системе «1С» в виде объекта «Справочник». 113 2. Блок подготовки исходных данных. Осуществляет выборку данных из разных таблиц, с использованием специального конструктора запроса. Также поддерживается ручной ввод и загрузка из текстового файла. Реализуется в системе «1С» в виде объекта «Обработка». 3. Блоки обучения по прецедентам. Позволяют пользователю выбрать используемый алгоритм обучения (в том числе разработанный генетический алгоритм), указать признаки, которые необходимо использовать для классификации (в том числе выбрать целевой атрибут – класс объекта), а также основные настройки для формируемого дерева классификации (максимальная глубина, минимальное количество случаев в узле и т.д.). Реализуется в системе «1С» в виде объекта «Обработка». 4. База моделей. Содержит сохраненные в информационной базе деревья классификации применительно к решаемым задачам из базы прецедентов. Реализуется в системе «1С» в виде объекта «Справочник». 5. Блок классификации. Наглядно отображает полученное дерево классификации в виде печатной формы с целью удобства интерпретации полученной модели специалистом-аналитиком предметной области. Поддерживает возможность интерактивного ввода входных атрибутов и получения результата классификации (целевого атрибута) на основании модели. Реализуется в системе «1С» в виде объекта «Обработка». 6. База резульататов классификации. Реализуется в системе «1С» в виде объекта «Документ» для сохранения результатов классификации на основании модели. 7. Интерфейс пользователя, обеспечивающий доступ к созданным объектам через главное меню программы.
