Содержание к диссертации
Введение
ГЛАВА 1 Обзор систем обнаружения знаний и систем извлечения знаний 11
1.1 Системы поддержки принятия решений 11
1.2 Нерешенные проблемы баз данных 13
1.3 Процесс обнаружения знаний 16
1.4 Задачи обнаружения знаний 17
1.5 Методология обнаружения знаний 19
1.6 Сравнение аналитических систем различного типа 24
1.6.1 Предметно-ориентированные аналитические системы (технический анализ) 24
1.6.2 Статистические пакеты 25
1.6.3 Нейронные сети 25
1.6.4 CBR (системы рассуждения на основе аналогичных случаев) 25
1.6.5 Деревья решений 26
1.6.6 Генетические алгоритмы 26
1.6.7 Нелинейные регрессионные методы (методы группового учёта атрибутов) 27
1.7 Описание дерева решений 27
1.8 Основные алгоритмы, использующие деревья решений 30
1.8.1 Алгоритм ЮЗ 30
1.8.2 Определения ; 33
1.8.3 Использование критерия прироста информативности Gain Ratio 35
1.8.4 Алгоритм С4.5 37
1.9 Методы сокращения решающих деревьев 39
1.9.1 Сокращение, уменьшающее ошибки (Reduced Error Pruning) 40
1.9.2 Сокращение по пессимистической ошибке (Pessimistic Error Pruning ) 41
1.9.3 Сокращение по минимальной ошибке (Minimum Error Pruning) 43
1.9.4 Сокращение по критическому значению (Critical Error Pruning) 44
1.9.5 Сокращение, основанное на ошибках (Error-Based Pruning) 45
1.10 Выводы по главе 1 47
Глава 2 Индуктивное построение понятий при "зашумленных" данных 48
2.1 Признаковое описание объекта 48
2.2 Проблемы, возникающие при работе с "зашумлёнными" данными 49
2.2.1 Ограниченная информация 50
2.2.2 Искажённая информация 51
2.2.3 Большой размер баз данных 52
2.2.4 Изменение баз данных со временем 53
2.3 Проблема моделирования шума в данных 54
2.3.1 Внесение шума в поле признака, содержащего дискретные значения 55
2.3.2 Внесение шума в поле признака, содержащего непрерывные значения 56
2.4 Анализ распределения значений для непрерывных признаков 57
2.4.1 Оценка математического ожидания, дисперсии, функции распределения и плотности 57
2.4.2 Распределения, отличные от равномерных 61
2.5 Моделирование шума в обучающей выборке 68
2.6 Выводы по главе 2 78
Глава 3 Методы построения деревьев решений при наличии шума во входных данных 79
3.1 Постановка задачи индуктивного построения понятий при отсутствии шума и при наличии шума 79
3.2 Алгоритм предсказания неизвестных значений по методу ближайшего соседа 83
3.3 Использование алгоритма восстановления неизвестных значений при построении дерева решений 90
3.4 Описание работы алгоритмов ID3 и С4.5 в сочетании с алгоритмами восстановления 97
3.5 Описание метода сокращения решающих деревьев 100
3.6 Выводы по главе 3 104
Глава 4 Программная реализация разработанного метода 105
4.1 Основные функции, выполняемые программой 105
4.2 Структура программного комплекса 106
4.3 Описание программы 107
4.4 Эксперименты на тестовых данных 113
4.4.1 Эксперименты на данных "задач монахов" 114
4.4.2 Медицинские данные 115
4.4.3 Данные проекта StatLog 116
4.4.4 Другие наборы данных 117
4.5 Методы проверки 118
4.5.1 Перекрестная проверка 119
4.5.2 Проверка исключением одного примера 119
4.5.3 Метод бутстрена 120
4.6 Методика проведения эксперимента по работе алгоритма IDTUV 121
4.7 Выводы по главе 4 126
Заключение 127
Список литературы
- Нелинейные регрессионные методы (методы группового учёта атрибутов)
- Проблема моделирования шума в данных
- Использование алгоритма восстановления неизвестных значений при построении дерева решений
- Эксперименты на данных "задач монахов"
Введение к работе
Актуальность темы исследований. Обнаружение знаний в базах данных является стремительно увеличивающейся областью, развитие которой подстегивается большим интересом к настоятельным практическим, социальным и экономическим нуждам. Бурное развитие методов электронного сопровождения данных позволяет назвать настоящее время "информационной эрой" - эрой мощных систем баз данных, предназначенных для сбора и сопровождения информации, такие системы используются сейчас фактически во всех больших и средних компаниях. Каждый год вес больше различных операций фиксируются на компьютере, включая данные о самих операциях, их действии и выполнении. Все такие данные содержат ценную информацию, которая могла бы использоваться в целях улучшения деловых решений и достижения успеха в различных экономических и научных сферах.
Современные базы данных содержат так много данных, что практически невозможно вручную проанализировать их для извлечения ценной информации, помогающей принимать важные решения. Во многих случаях описание поведения сложных систем содержит сотни независимых атрибутов, которые необходимо анализировать, чтобы наиболее точно смоделировать поведение системы. Отсюда следует, что люди нуждаются в помощи интеллектуальных систем для повышения своих аналитических возможностей.
Настоящая диссертационная работа посвящена созданию алгоритмических и программных средств для поиска индуктивных закономерностей, неявно представленных в базах данных. Такой процесс, называемый обобщением, направлен на получение правил классификации, с помощью которых можно успешно распознавать объекты определенного класса. Над разработкой алгоритмов обобщения работали многие авторы,
созданием подобных алгоритмов занимались известные ученые Р. Куинлан, Утгофф, Нуньес, Михальский, Финн, Вагин и другие. Созданные ими методы и алгоритмы внесли большой вклад в развитие систем машинного обучения; эти методы позволяют получать средства для эффективной классификации объектов, представленных множествами признаков. Однако, обработка реальных массивов, представленных в базах данных, которые часто содержат зашумленные и противоречивые данные, характеризуются большим размером и наличием избыточного множества признаков. Это снижает успешность применения этих алгоритмов. С другой стороны, массивы данных, содержащие шум, встречаются в целом ряде реальных ситуаций и задач. Для решения проблемы обработки данных, содержащих шум, необходимо было изучить модели шума, предложить способы поиска неизвестных или искаженных значений некоторых признаков, что должно повысить эффективность классических методов обобщения. Таким образом, исследование методов обобщения при наличии шума в массивах данных является актуальной задачей.
Цель работы заключается в разработке алгоритмов обобщения данных, способных давать удовлетворительные результаты не только на "чистых" обучающих множествах, но и на обучающих выборках, содержащих шум.
Поставленная задача потребовала решения следующих проблем:
Разработка моделей представления шума в обучающих множествах. При этом было проведено исследование моделей шума двух типов — отсутствие значений признака и искажение значений признака.
Разработка алгоритмов восстановления отсутствующих значений в обучающем множестве на основе метода "ближайшего соседа". Использование методов восстановления на этапе построения дерева решений и на этапе классификации тестовых примеров.
Моделирование средств для внесения шума в обучающую выборку на основе заданных параметров шума.
Разработка и программная реализация системы обобщения для работы с зашумленными данными на основе созданной модификации алгоритма построения дерева решений.
Методика проведения исследований. Для достижения целей работы были использованы следующие методы исследования: методы математической логики и дискретной математики, математической статистики, машинного обучения, методы анализа математической сложности алгоритмов.
Достоверность научных результатов подтверждена теоретическими выкладками, данными компьютерного моделирования, результатами экспериментов, а также сравнением полученных результатов с результатами, приведенными в научной литературе. Научная новизна исследования.
Дан обзор аналитических систем различного типа, решающих проблему извлечения скрытых закономерностей из больших массивов данных. Обоснован выбор решающих деревьев в качестве основного алгоритмического подхода для построения эффективной системы обобщения данных.
Созданы модели шума в множестве объектов, имеющих признаковое описание, для случая отсутствия значения признака и искажения значения признака.
Введено понятие информационной системы по заданному классу, которая хранит сведения о свойствах информативных признаков объектов обучающей выборки.
Введена метрика, позволяющая определять расстояние между объектами, представленными в виде набора признаков.
На основании введенной метрики разработаны алгоритмы восстановления неизвестных значений признаков в обучающей выборке на этапе построения дерева решений и на этапе выполнения классификации.
Разработан эффективный алгоритм обобщения и классификации объектов, представленных в обучающих выборках с шумом.
Практическая значимость. Результаты диссертационной работы отражены в созданной программной системе, выполняющей обобщение понятий на основе обучающих выборок с шумом. В данной системе реализованы предложенные автором алгоритмы восстановления неизвестных значений, дискретизации непрерывных признаков, классификации примеров с шумом на полученном дереве решений.
Практическая значимость работы подтверждается внедрением полученных результатов в динамической экспертной системе оперативной диагностики состояния экологически опасных объектов и производств "ДИЭКС" в ОАО "ЦНИИКА". Имеется акт о внедрении.
Апробация работы. Основные положения и научные результаты диссертации докладывались на трех научно-технических конференциях МЭИ (ТУ) (2003, 2004, 2005 гг.), на международных форумах информатизации МФИ-2003, МФИ-2004 и МФИ-2005 (Международные конференции «Информационные средства и технологии» , г. Москва, 2003,2004, 2005 гг.).
Публикации. Материалы по теме диссертационной работы опубликованы в 6 печатных работах.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы, приложений.
В первой главе дается анализ общих принципов организации систем поддержки принятия решений и систем обнаружения знаний в базах данных. Выделены основные этапы процесса обнаружения знаний в базах данных и показано место и роль этапа индуктивного анализа данных (Data mining) в общем процессе обнаружения знаний.
Выделяются следующие группы методов решения задач анализа данных: статистические методы, вывод, основанный на прецедентах, нейронные сети, деревья решений, индуктивные правила, байесовские доверительные сети, генетические алгоритмы, нечеткие множества, приближенные множества. На основе анализа этих методов обоснован выбор деревьев решений как способа построения классификационных схем.
Среди различных вариантов алгоритмов построения деревьев решений на основе вычисления информационных оценок для признаков выбираются базовые алгоритмы ID3 и С 4.5. Дается анализ методов сокращения деревьев решений, полученных при построении алгоритмом ID3.
В главе 2 рассмотрены проблемы, связанные с использованием баз данных в качестве обучающего множества. Исследуются модели шума в обучающей выборке. Для непрерывных параметров предложен метод дискретизации. Для моделирования шума в обучающей выборке предлагаются алгоритмы внесения шума в исходную обучающую выборку.
В третьей главе дана постановка задачи обобщения при неполной информации в обучающем множестве. Для случая обучения при неполной информации введено понятие информационной системы, которая хранит сведения о свойствах информативных признаков объектов предъявленной обучающей выборки. Введена метрика, позволяющая определять расстояние между объектами, содержащими неизвестные значения признаков. На основании этой метрики разработаны алгоритмы восстановления, позволяющие определить предполагаемое значение неизвестного признака методом "ближайшего соседа".
Предложен алгоритм IDTUV, позволяющий обрабатывать обучающие выборки, содержащие примеры с неизвестными или искаженными значениями, на основе использования алгоритмов ID3 и С4.5 в сочетании с алгоритмами восстановления.
В четвертой главе рассматривается программная реализация системы на основе разработанной модификации алгоритма обобщения, приведенной в главе 3. При этом обобщение и классификация могут проводиться на неполной информации об объектах, что может выражаться в отсутствии ряда значений атрибутов для части объектов. Описаны структура, основные функции и возможности реализованного программного комплекса. Представлено описание пользовательского интерфейса, приведены примеры работы программы и описаны проведенные эксперименты на тестовых наборах данных, в том числе на известной тестовой коллекции данных Калифорнийского университета информатики и вычислительной техники UCI Machine Learning Repository. Описана методика проведения эксперимента, подтверждающего успешность методов восстановления зашумленных значений в обучающих множествах.
Нелинейные регрессионные методы (методы группового учёта атрибутов)
Основное внимание в работе уделяется деревьям решений, которые помогают получить решение для классификации возникшей проблемы. Поскольку они удобны для использования, конечные модели легки в понимании. Теория решающих деревьев базируется на информационных оценках; решающие деревья используются при решении классификационных задач и представляют собой процедуру определения класса для предъявленного примера. Каждый узел дерева определяет или имя класса, или специфическую проверку, разделяющую пространство примеров, приписанных узлу, в соответствии с возможными результатами проверки. Каждое подмножество, возникшее в результате такого разделения, соответствует классификации субпроблемы для подпространства примеров, которое получено на поддереве. Дерево решений можно представить как стратегию «дробления и продвижения вперед» для объекта, подлежащего классификации. Формально можно определить дерево решений как граф, не содержащий циклов, в котором каждая вершина - это: 1. конечный узел, взвешенный именем класса, или 2. промежуточный узел, содержащий проверку значений атрибута, с дальнейшим расщеплением на поддеревья, для каждого допустимого значения атрибута.
Например, алгоритм ID3 (см. [16]), который будет подробно рассмотрен ниже, строит дерево решений на основе множества примеров, для которых известен результат классификации, начиная с корневого узла (вершина дерева) вниз к конечным узлам (листьям). На каждом этапе построения информационная связь между классификационным и исследуемым атрибутами используется для выбора атрибута, на основании которого происходит ветвление в данной точке.
Информационная связь между классификационным атрибутом и исследуемым атрибутом называется также приростом информации (information gain), и определяется на основе частоты появления значений признаков атрибута в тестовом множестве примеров. Дерево решений это особая форма теста, который предписывает определенные проверки на каждом шаге анализа.
В общем, деревья решений представляют собой дизъюнкцию конъюнкций ограничений для значений атрибутов примеров. Каждый путь от корпя дерева к конечной вершине (листу) соответствует конъюнкции проверок условий на значения атрибутов, а дерево в целом представляет дизъюнкцию таких конъюнкций. Точнее, решающие деревья классифицируют примеры путем сортировки их с помощью дерева от корневого узла к одному из конечных узлов (листьев), в которых выполняется классификация примера. Каждый узел в дереве решений определяет проверку значения некоторого атрибута примера, а каждое ветвление, выходящее из этого узла, соответствует одному из возможных значений этого атрибута (рис. 1.2).
Классификация примера начинается с корня дерева решений, где выполняется проверка атрибута, приписанного данному узлу (тест для данного атрибута), затем, выбирается путь для движения вниз по одной из ветвей дерева в соответствии со значением атрибута. Процесс повторяется в узле, которым заканчивается выбранная ветвь, и так далее, до тех пор, пока не будет достигнут конечный узел (лист). Конечному узлу приписан один из возможных ответов (решение).
Миру присуща простота. Следовательно, наименьшим деревом решений, полученным на основе множества примеров, будет то дерево, которое наиболее пригодно для корректной идентификации неизвестных объектов.
Существует множество различных алгоритмов, формирующих правила классификации объектов в виде деревьев решений. Рассмотрим один из наиболее известных алгоритмов этого типа - алгоритм ID3. ID3 является полезным обучающим алгоритмом для построения понятий, поскольку он способен эффективно строить дерево решений, успешно решая таким образом задачу обобщения. Размеры построенного обучающим алгоритмом дерева зависят от того, какая версия алгоритма была использована: инкремснтная или не инкрементная. Алгоритмы ID3 и С4.5 (см. [16, 32]), были введены Куинланом для построения индуктивных классификационных моделей, называемых деревьями решений, на основе данных, представленных в обучающем множестве.
Пусть задано множество записей. Все записи имеют одинаковую структуру и содержат одинаковое количество пар «атрибут- значение атрибута». Один из атрибутов позволяет определить категорию (класс) каждой конкретной записи. Проблема состоит в нахождении решающего дерева, способного на основании ответов на вопросы о значениях прочих атрибутов, называемых информативными, корректно предсказать значение класса. Обычно атрибут, задающий класс, принимает только бинарные значения { (rue , false }, либо их эквивалент. В некоторых случаях одно из таких значений означает неудачу (см. [33]).
Большинство обучающих систем имеют дело с множеством предварительно классифицированных примеров, где каждый пример задан вектором значений атрибутов, и ищут связь между значениями атрибутов и классами. Все признаки, описывающие примеры, можно разбить на непрерывные (числовые значения) и дискретные, имеющие неупорядоченное множество допустимых значений. Алгоритм С4.5 относится к классу алгоритмов, строящих классификационные правила в виде деревьев решений. Главное достоинство алгоритма С4.5 заключается в возможности эффективно обрабатывать атрибуты с непрерывными значениями (см. [32, 33, 34, 35]).
Для дискретных атрибутов, как было показано выше, прирост информации зависит от разделения примеров множества Т на подмножества с различными значениями выбранного атрибута. Для непрерывных атрибутов прирост информации зависит от разделения Т на два подмножества, а именно, по значению атрибута «не больше, чем» и значению «больше чем» для некоторого порогового значения. Это пороговое значение определяется посредством вычисления прироста информации (Gain ratio) для возможных значений непрерывного атрибута.
Для каждого значения v прирост информации вычисляется при рассмотрении разбиения высшего уровня. Значение v , для которого прирост информации максимален, становится локальным порогом, и прирост информации для атрибута рассматривается как выигрыш. Алгоритм С4.5 рассматривает коэффициент gain ratio от разделения {Т/, Тг"}. При ветвлении в узле по атрибуту А возникают 2 новые ветви, соответствующие подмножествам {Ті" , T2V}. Процесс продолжается итеративно, так же, как в алгоритме ШЗ. Поскольку построенное решающее дерево может быть большим и неудобочитаемым, в алгоритме С4.5 предлагается использовать стратегию упрощения дерева, путем сокращения его ветвей в соответствии с заданным уровнем сложности.
Как само решающее дерево, так и его упрощенная версия оцениваются путем расчета доли случаев ошибочной классификации по данному дереву. Такая оценка строится при использовании для классификации тестового множества, то есть множества примеров, которые не рассматривались при построении самого дерева решений. Алгоритм С 4.5 является расширением базового алгоритма ID3. В общем, оба алгоритма эффективны и получают обобщение в виде набора правил. Однако, С4.5 работает лучше, чем ID3, поскольку выполняется исключение всех необязательных условий, кроме того, С 4.5 имеет ряд преимуществ по сравнению с ID3: 1. Введение числовых (непрерывных) атрибутов. 2. Номинальные (дискретные) значения единственного атрибута можно группировать, чтобы выполнять более сложные проверки. 3. Последующее сокращение после индуктивного построения дерева, основанное на использовании тестового множества, позволяет повысить точность классификации. 4. С4.5 может работать с неполной информацией (в примерах, предъявленных для классификации, значения некоторых атрибутов могут отсутствовать) [34].
Проблема моделирования шума в данных
Базы данных постоянно обновляются. Информация добавляется, изменяется или удаляется- Следовательно, знания, извлеченные из базы данных ранее, уже не соответствуют содержащимся в ней данным. Очевидно, что обучающаяся система должна адаптироваться к подобным изменениям. Необходимо также учесть, что свежая информация более ценна, чем старая.
Каждый раз при изменении базы данных мы можем либо конструировать систему правил с пуля, либо использовать инкрелгентное обучение (incremental learning), когда знания, полученные на предыдущих этапах, используются для построения новых знаний.
Базы данных создаются из расчета требований конкретных приложений, а не специально для машинного обучения. 2. Информация, содержащаяся в базах данных, как правило, неполна.
Свойства объектов, необходимые для корректной классификации, не обязательно представлены в базе данных. 3- Отдельные значения могут содержать ошибки или вовсе отсутствовать. 4. Базы данных очень велики, 5. Базы данных изменяются со временем. От того, насколько система извлечения знаний сможет справиться с этими проблемами, зависит успех ее практического применения (см.[44]),
Основой для работы алгоритмов индуктивного формирования понятий являются обучающие выборки. Понятие обучающей выборки было введено в главе 1. Для проверки эффективности работы алгоритмов различного типа с зашумленными данными необходимо использовать выборки, содержащие шум, и выборки, не содержащие шума.
Шум возникает при преобразовании истинных входных величин в процессе измерения и пересылки данных. Ошибки измерения полагаем независимыми от времени измерения и от истинного значения измеряемой величины. Учитываются те шумы, которые связаны с искажением значения входного параметра, используемого системой, а именно - некорректное измерение входного параметра, - неверное описание значения параметра экспертом, - использование испорченных измерительных приборов, - потеря данных при хранении и пересылке информации.
Обсудим проблему внесения шума в обучающую выборку. 23.1 Внесение шума в поле признака, содержащего дискретные значения.
Первоначально задана обучающая выборка К не содержащая искаженных значений. Пусть среди атрибутов, характеризующих каждый объект из К, имеется информационный атрибут, a-v, принимающий значения из множества допустимых значений Dom(ai)={zi, Z2, ... , Zk}. Это атрибут качественный, он имеет дискретное множество разрешенных значений Нашей задачей будет внесение искажений в объекты выборки К по атрибуту а,, причём любой объект из К может "пострадать" от шума. Введём V(as) - вероятность того, что значение атрибута а, для очередного объекта выборки будет искажён. Величина V(ai) соответствует уровню шума в выборке по атрибуту а;. Например, если ввести V(a;)=0,i, то в среднем каждый десятый пример выборки К будет иметь изменённое значение для атрибута а;.
1, Шум связан с исчезновением значений атрибутов. Для каждого атрибута щ область допустимых значений включает значение "неизвестно": Dom1 (at) -Dom (a,) U {N}. Таким образом, примеры обучающей выборки 1С содержат некоторое количество признаков со значениями N. В этом случае будем использовать специально введённое значение N, понимая его как Notjcnown (значение атрибута неизвестно)(см.[45]).
2, Шум связан с искажением некоторых значений атрибутов в обучающей выборке. При этом истинное значение заменяется на одно из допустимых, но ошибочных значений из Dom (aj).
Первоначально задана обучающая выборка /Г, не содержащая искаженных значений. Пусть среди атрибутов, характеризующих каждый объект из К, имеется информационный атрибут, а;, для которого область допустимых значений определяется интервалом ( zmax). Это атрибут непрерывного типа, поэтому искажение значений такого атрибута при измерении (пересылке) приведет к тому, что именно такое, искажённое значение будет представлено в обучающей выборке К.
Для атрибута непрерывного типа можно применять две модели шума, введённые выше.
Наиболее простым является внесение шума первого типа. Пусть
величина V(aj) определяет вероятность того, что пример подвергается воздействию шума. Влияние шума на пример заключается в за.мене значения атрибута на значение N.
Моделирование шума второго типа должно заключаться во внесении новых значений в поле атрибута а\ . Пусть величина V(aO как и раньше определяет вероятность того, что пример подвергается воздействию шума. Для непрерывного атрибута необходимо определить z\ - новое значение, отличающееся от точного значения zt на величину А[. Чтобы определить величину АІ, необходимо выдвинуть предположение о характере распределения значений признака. Основой для выдвижения такого предположения должен стать анализ всех точных значений признака а; э встречающихся в обучающей выборке Кш На основе анализа всех значений признака а] в обучающей выборке можно получить одно из следующих решений: - значения атрибута распределяются равномерно в пределах заданного интервала; значения атрибута распределены по нормальному закону относительно некоторого, наиболее вероятного значения; - значения атрибута группируются вокруг нескольких наиболее "ожидаемых" значений.
В каждом из таких случаев будет введена своя функция расчёта величины Ді на основе известного значения ъ\. Обозначим обучающую выборку, полученную после внесения шума, как АГ.
В этом разделе мы рассмотрим статистические методы анализа распределения значений непрерывных признаков. Рассматриваемые методы используют оценки математического ожидания, дисперсии, построение функции распределения и плотности. Далее мы рассмотрим методы группировки значений непрерывных атрибутов.
Использование алгоритма восстановления неизвестных значений при построении дерева решений
Рассмотрим стратегию применения алгоритма ВОССТАНОВЛЕНИЕ при построении дерева решений. Основной особенностью этана обучения является наличие в обучающей выборке решающего атрибута, на основе которого происходит разделение примеров на классы ЯҐ и К. В свете этого алгоритм восстановления неизвестных значений будет использоваться в следующей модификации. Во-первых, при поиске ближайших соседей примера X будут использоваться только объекты, относящиеся к тому же классу, что и сам объект X Во-вторых, перед началом работы алгоритма восстановления для дискретных признаков составим таблицу частоты появления каждого значения признака в обучающей выборке отдельно по классу К и по классу К. В случае, если среди множества ближайших соседей объекта Хне удалось
выбрать наиболее часто встречающееся значение для неизвестного признака, то неизвестному признаку присваивается значение, наиболее часто встречающееся среди примеров всей обучающей выборки по классу К или К . Аналогичный подход был использован в [48].
Введём понятие информационной системы по классу К. Информационная система, обозначаемая далее как IS(A ), представляет информационную структуру, которая включает следующие данные: - для дискретных признаков создаётся таблица частоты появления каждого из возможных значений признака в обучающей выборке; - для непрерывных признаков определяется интервал (xmas, хтіП), в который попадают все значения данного признака, представленные в обучающей выборке.
Алгоритм ID3 (induction of decision trees), разработанный P. Куинланом (см, [16]), формирует решающие деревья на основе примеров. Каждый пример имеет одинаковый набор атрибутов (признаков), которые можно рассматривать как качественные признаки- Этот алгоритм относится к алгоритмам обучения с учителем, соответственно, обучающая выборка, необходимая для его работы, содержит положительные и отрицательные примеры формируемого понятия, В соответствии с терминологией автора назовем признаки, или атрибуты которые задают свойства каждого примера обучающей выборки, предсказывающими атрибутами. Такие признаки могут быть бинарными, количественными либо качественными. Единственный признак, который для каждого примера задает, принадлежит ли он формируемому понятию, или нет, назовем целевым,, или предсказываемым атрибутом. Этот атрибут является бинарным и также входит в обучающую выборку-Алгоритм строит такое решающее дерево, в котором с казвдым узлом ассоциирован атрибут, являющийся наиболее информативным среди всех атрибутов, еще не рассмотренных на пути от корня дерева. В качестве меры информативности обычно используется теоретико-информационное понятие энтропии, хотя возможны и другие подходы.
Псевдокод для алгоритма ID3 и примеры его работы были даны ранее в главе 1. Рассмотрим оценку вычислительной сложности алгоритма ID3. Единственная трудоемкая операция, выполняемая на одном шаге алгоритма, это выбор атрибута D с максимальным значением Gain(D7 S). При этом количество альтернатив и размер biji од множества обучающих примеров сужаются с увеличением глубины рекурсивной вложенности. Па уровне / они составляют соответственно к-1 и nlb\ где п - количество примеров. Для того, чтобы вычислить Gain{D9 S) достаточно одного просмотра множества примеров, поэтому общее число операций составит. Подставив это выражение в сумму, определяющую общую сложность, и выполнив очевидные преобразования, получим
Рассмотрим, как обрабатываются атрибуты, имеющие непрерывные значения. Даже если некоторый атрибут А имеет непрерывную область определения, в обучающем множестве имеется лишь конечное множество значений Сі Сі .,. с„. Для каждого значения с; мы разбиваем примеры на те, у которых значение А Cj, и те, у которых А с;. Для каждого из возможных разбиений мы вычисляем Gain(A, S) и выбираем наиболее информативное разбиение. Так было получено разбиение по значению 75 для атрибута Влажность в примере с игрой в гольф из главы 1. Алгоритм, реализующий обработку непрерывных атрибутов, предложен Куинланом под названием С4.5 и также был рассмотрен выше (глава 1).
Рассмотрим возможность использования алгоритма
ВОССТАНОВЛЕНИЕ, который был предложен выше, для решения задач индуктивного формирования понятий- Предлагается алгоритм IDTUV, который включает процедуру восстановления неизвестных значений при наличии в обучающей выборке примеров, содержащих шум. Когда неизвестные значения атрибутов восстановлены, используется один из алгоритмов построения деревьев решений. Примеры, для которых не удалось восстановить неизвестные значения, удаляются из обучающей выборки. Ниже приводится псевдокод алгоритма IDTUV.
Эксперименты на данных "задач монахов"
В этом разделе мы изложим результаты экспериментов на данных задач монахов (См.[65]). Первая задача монахов состоит в том, чтобы в результате обучения получить классифицирующее правило, которое позволяет описать понятие, представленное в дизъюнктивной нормальной форме. Целевое понятие может быть представлено как простое выражение: [х2 = 1] v [х4 = х5] = Л/1, которое можно интерпретировать следующим образом: «если для неизвестного объекта атрибут х2 принимает значение I или атрибуты х4 и х5 принимают одинаковое значение (неважно, какое именно), то вне зависимости от значений других атрибутов следует классифицировать этот объект как принадлежащий понятию М\». В данном случае для оценки ошибки классификации был применен метод «обучения и проверки». Обучающее множество состояло из 124 примеров (62 положительных и 62 отрицательных), что составляет 30% от полного пространства примеров (432 объекта). Множество тестовых примеров включало вес возможные примеры (216 положительных и столько же отрицательных). Каждый объект характеризуется шестью условными атрибутами (области значений которых дискретны и включают малое число значений) и одним решающим атрибутом (с двумя классами решения).
Вторая задача монахов связана с обучением понятию, которое можно описать с помощью следующего высказывания: «Если ровно два атрибута из шести для некоторого объекта принимают первое значение, то классифицировать этот объект как принадлежащий классу Л/2». Обучающее множество состояло из 169 примеров (105 положительных и 64 отрицательных), что составляет 40% от полного пространства примеров. Множество тестовых примеров включало все возможные примеры (190 положительных и 242 отрицательных). Каждый объект характеризуется шестью условными атрибутами (области значений которых дискретны и
Третья задача монахов заключается в том, чтобы описать понятие, которое задастся с помощью следующего выражения: [х2 Ф 4] & [х5 — 1 v 2] v [jtl = 1] & [х2 — 3] Л/3. Обучающее множество состояло из 122 примеров (62 положительных и 60 отрицательных), что составляет 30% от полного пространства примеров. Множество тестовых примеров включало все возможные примеры (204 положительных и 228 отрицательных). Каждый объект характеризуется шестью условными атрибутами (области значений которых дискретны и включают малое число значений) и одним решающим атрибутом (с двумя классами рсшеним). Следует отметить, что обучающее множество этой задачи содержит шум.
Медицинские данные (относящиеся к сердечным заболеваниям и гепатиту) входящие в коллекцию UCI Machine Learning Repository и используемые в наших тестах, были получены из медицинского центра института онкологии города Любляна ( См. [67]),
Диагностика сердечных заболевании (Heart). База данных содержит результаты медицинских наблюдений за 270 пациентами разного возраста. Данные описываются 13 условными атрибутами (6 качественными и 7 количественными); возраст пациента, пол пациента, тип боли в груди, давление крови в состоянии покоя, содержание холестерина в сыворотке крови, уровень сахара в крови, результат электрокардиографии, число ударов сердца в минуту, была ли перенесена ангина и другими. Решающий атрибут указывает на наличие или отсутствие порока сердца.
В наших экспериментах мы использовали данные проекта StatLog, основанного Европейским сообществом в рамках программы ESPRIT (См, [68]). Этот проект посвящен сравнению алгоритмов машинного обучения на данных крупномасштабных приложений в области классификации, прогнозирования и управления. Часть из этих данных общедоступна (См. [64]), В этом разделе мы рассматриваем два набора данных из этого проекта и сравним результаты разработанного алгоритма с результатами систем, которые применялись в рамках проекта StatLog.
Диагностика заболеваний диабетом (Diabetes) у женщин из индейских племен Pima. База данных содержит результаты медицинских наблюдений за 768 женщинами старше 21 года, кровей индейцев племени Pima, проживающих около Финикса (штат Аризона). Наблюдения проведены по критериям Всемирной Организации Здоровья (World Health Organization) и выполнены американским Институтом диабета и заболеваний почечно-пищеваритсльного тракта. Данные описываются одним решающим атрибутом, указывающим на наличие или отсутствие диабета, и 8 условными атрибутами (непрерывными, с большим числом значений).
Австралийский кредит (Australian), Эти данные касаются применения кредитных карт. Цель состоит в том, чтобы сформировать правило для оценки полезности использования кредитных карт. Интерпретация этих данных трудна, поскольку атрибуты и классы были закодированы, чтобы сохранить конфиденциальность. Этот набор данных интересен, потому что в нем имеется хорошее сочетание атрибутов: качественных с малым числом значЬн й и непрерывных с большим количеством значений. Данные состоят из 690 объектов и описываются с помощью 13 условных атрибутов и одного решающего атрибута (с 2 классами решения).
При оценке точности классификации для этих наборов данных применялись методы 10-кратной перекрестной проверки и бутсірепа с шестью парами выборок. Работа предложенных алгоритмов была рассмотрена на данных из области биологии, демографии и судебно-следственной практики ([64]). Распознавание типов цветков ириса (Iris). В данной задаче требуется построить классификацию типов цветков ириса (Iris Setosa, Iris Versicolour, Iris Virginica) no 4 размерам их пестиков и тычинок. Все условные атрибуты являются количественными. База данных содержит по 50 примеров каждого класса (всего 150 примеров).
Наиболее простой способ оценить, насколько хорошо возможная решающая функция (такая как система решающих правил или дерево решений) работает па тестовом множестве - это проверить её па тестовом множестве. Обучение на тестовых данных увеличивает множество обучения и, как следствие, приводит к улучшению обобщения. Другой методикой является разбиение обучающего множества, т.е. использование двух третей
При перекрестной проверке обучающее множество делится на к непересекающихся подмножеств равных размеров: Uv...tUk. Для каждого
подмножества Ui проводится обучение на объединении всех остальных подмножеств и далее опытным путем определяется коэффициент погрешности г; на U-. (Коэффициент погрешности — это отношение числа ошибок классификации, сделанных в Л, к количеству примеров в С/.).
Тогда для классификационной модели, обученной на всех примерах U9 величина коэффициента погрешности, которую можно ожидать на новых примерах, будет равняться среднему арифметическому всех s,
Метод бутстрепа был предложен Эфроном и подробно изложен в [70]. Предположим, чго обучающее множество состоит из п примеров. Метод бутстрепа состоит в создании к выборок путем взятия по п примеров в каждую (возможно, с повторами), где к - внешний параметр. В каждую выборку примеры выбиршотся из исходного обучающего множества независимо друг от друга. Таким образом, в каждой выборке, практически наверняка, будут повторы. Для каждого примера обучающего множества вероятность не быть выбранным после того, как уже были взяты п примеров, равна (1 — 1/л)" &е 1 & 0,368, поэтому приблизительно 0.632« примеров обучающего множества войдут в каждую из выборок. Пусть є" -коэффициент погрешности классификации, когда классифицирующее правило было построено на выборке Ul и проверено на неизвестных примерах (т.е. на примерах, не вошедших в эту выборку), количество которых примерно 0.368л. Пусть гГ - коэффициент погрешности, когда обучение и проверка проведены на одной и той же выборке Uf..
