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

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

Айман Мохамед Мофтах Кхамес Йоунес Бериша

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ ИЗВЛЕЧЕНИЯ ЗНАНИЙ ДЛЯ СОЗДАНИЯ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2005

Работа выполнена на кафедре Прикладной математики Московского энергетического института (Технического университета)

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

Вадим Николаевич Вагин

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

Марина Владимировна Фомина

Официальные оппоненты:

доктор технических наук профессор

Олег Петрович Кузнецов

кандидат физико-математических наук, профессор

Геральд Станиславович Плесневич

Ведущая организация РосНИИ информационных технологий

и систем автоматизированного проектирования (РосНИИ ИТ и АП)

Защита состоится <\01» апреля 2005 г. в 17 час. 30 мин. на заседании

диссершционного совета Д 212.157.01 при Московском энергетическом

институте (Техническом университете) по адресу: 111250, г. Москва, Красноказарменная ул.. 17 (ауд. Г-306).

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета).

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, г. Москва, Красноказарменная улица, д. 14. Ученый Совет МЭИ (ТУ).

Автореферат разослан « » 2005 г.

Ученый секретарь

диссертационного совета Д 212.157.01 кандидат технических наук профессор

И.И. Ладыгин

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

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

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

Настоящая диссертационная работа посвящена созданию алгоритмических и программных средств для поиска индуктивных закономерностей, неявно представленных в базах данных. Такой процесс, называемый обобщением, направлен на получение правил классификации, с помощью которых можно успешно распознавать объекты определенного класса. Над разработкой алгоритмов обобщения работали многие авторы, созданием подобных алгоритмов занимались известные ученые Р. Куинлан, Утгофф, Нуньес, Михальский, Финн, Вагин и другие. Созданные ими методы и алгоритмы внесли большой вклад в развитие систем машинного обучения; эти методы позволяют получать средства для эффективной классификации объектов, представленных множествами признаков. Однако, обработка реальных массивов, представленных в базах данных, которые часто содержат зашумленные и противоречивые данные, характеризуются большим размером и наличием избыточного множества признаков. Это снижает успешность применения этих алгоритмов. С другой стороны, массивы данных, содержащие шум, встречаются в целом ряде реальных ситуаций и задач. Для решения проблемы обработки данных, содержащих шум, необходимо было изучить модели шума, предложить способы поиска неизвестных или искаженных значений некоторых признаков, что должно повысить эффективность классических методов обобщения. Таким образом, исследование методов обобщения при наличии шума в массивах данных является актуальной задачей

Объектом исследования работы являются методы обобщения понятий. Предметом исследования - методы обобщения, связанные с обработкой неполкой и недостоверней информации.

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

Поставленная задача потребовала решения следующих проблем:

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

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

3) Исследование моделей шума и разработка моделей представления шума в обучающих множествах. Исследовались модели шума двух типов -отсутствие признака и искажение признака.

4) Разработка алгоритма обобщения, позволяющего обрабатывать обучающие выборки с неизвестными или искаженными значениями.

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

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

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

Научная новизна исследования состоит в следующем:

1. Созданы модели шума на множестве объектов, имеющих признаковое описание, для случаев отсутствия значения признака и искажения значения признака.

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

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

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

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

Практическая значимость работы заключается в создании программной системы обобщения понятий, реализующей разработанные алгоритмы дискретизации и выбора существенных признаков, а также модифицированную стратегию применения решающих правил. Практическая значимость раооты подтверждается внедрением полученных результатов в динамической экспертной системе оперативной диагностики состояния экологически опасных объектов и производств "ДИЭКС" в ОАО "ЦНИИКА". Имеется акт о внедрении.

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались на 9-й, 10-й и11-й научных конференциях аспирантов и студентов "Радиотехника, электроника, энергетика" в МЭИ (ТУ), г. Москва, международных форумах информатизации МФИ 2003, 2004.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы (75 наименования) и приложений. Диссертация содержит 216 страниц машинописного текста, включая 24 таблицы и 30 рисунков.

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

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

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

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

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

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

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

Одним из наиболее известных алгоритмов, формирующих правила классификации объектов в виде деревьев решений, является алгоритм Ш3. Алгоритмы ГО3 и С4.5 были введены Куинланом для построения индуктивных классификационных моделей, называемых деревьями решений, на основе данных, представленных в обучающем множестве. Обучающее множество содержит объекты, каждый из которых задан набором атрибутов, или признаков объекта. Один из атрибутов является решающим. На его основании конкретный объект относится к одному из классов.

В дереве решений, построенном алгоритмом ЮЗ. каждый узел соответствует конкретному атрибуту, а каждая дуга - возможному значению этого атрибута.

Построение дерева решений начинается с корня. В очередном узле дерева размещается наиболее информативный атрибут, среди атрибутов, которые ещё не рассматривались при построении пути от корня к данной вершине.

Как выбрать наиболее информативный атрибут? Пусть некоторый атрибут А принимает п возможных значений в заданной обучающей выборке. Если эти значения встречаются с вероятностями р\, р2, рг , мы имеем дискретное распределение Р = (р\, р..., р„); тогда передаваемая информация, или энтропия Р будет

Энтропия является мерой информативности для атрибута. Разбив множество примеров на основе значений некоторого атрибута Л на подмножества 5,. 5г, •..,

соответствующие значениям атрибута А, мы можем вычислить как

взвешенное среднее информации, необходимой для идентификации к пасса примера в каждом подмножестве:

Величина Сат(А, Я) = 1п/о{5!) - ¡п{о(А. 5) показывает количество информации, которое мы потучаем благодаря атрибуту А. Алгоритм ГО3 использует эт\7 величину для оценки информативности атрибута при построении решающих деревьев, что позволяет получать деревья минимальной высоты.

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

Далее алгоритм ЮЗ представлен на псевдокоде.

Алгоритм ЮЗ ( А: множество предсказывающих атрибутов, С : предсказываемый атрибут, 8 : обучающее множество ) Результат решающее дерево Начало

Если 8 = 0 То вернуть одну вершину со значением {ошибка} Если 8 состоит из примеров С одинаковым значением атрибута С То вернуть одну вершину со значением атрибута С Если А - 0 вернуть одну вершину со значением атрибута С, Наиболее частым среди примеров из 8

Пусть Б - атрибут с наибольшим значением прироста информативности gain(D,S) среди всех атрибутов из А. Пусть] = 1,2,...,т - значения атрибутаВ, а = 1,2,..., ш подмножества обучающих примеров, состоящие из примеров со значением ё, для атрибута Б.

Вернуть дерево с корнем,

помеченным Б и дугами, помеченными ..., , соединяющими корень с деревьями

ЮЗ (А\ Ш},с, Б,), ЮЗ (Аурьед,.... 103 (А\{Б}, С, 5т);

Конец

Для эффективной обработки атрибутов с непрерывными значениями используется модификация данного алгоритм С4.5. Рассмотрим, как в этом алгоритме обрабатываются атрибуты, имеющие непрерывные значения. Даже если некоторый атрибут А имеет непрерывную область определения, в обучающем множестве имеется лишь конечное множество значений ё < сЛ < ... < сп Для каждого значения с, мы разбиваем примеры на те, у которых значение А < С„ и те, у которых А > С,. Для каждого из возможных разбиений мы вычисляем Оа\п(Л, 8) и выбираем наиболее информативное разбиение

Проведен сравнительный онализ методов сокращения деревьев решений, полученных при построении алгоритмами 1Б3 и С 4.5 Сокращение по

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

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

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

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

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

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

Шум вызывает две проблемы сначала при построении правил, а затем при классификации объектов с использованием этих правил.

Рассмотрим постановку задачи внесения шума в обучающую выборку. Первоначально задана обучающая выборка К, не содержащая искаженных значений Наша цель - получить К' - выборку с шумом. Пусть среди атрибутов, характеризующих каждый объект из К. имеется информационный атрибут, а,, принимающий значения из множества допустимых значений Dom(a,)-{zi; z2, ... . Zk}. Предположим, при измерении значения атрибута (либо при передаче значения) а, были допущены ошибки.

Введём V(a,) - вероятность того, что значение атрибута а, для очередного объекта выборки получит значение N (неизвестно), либо было искажено. Величина V(a,) соответствует уровню шума в выборке по атрибуту а,.

Рассматриваются два типа шума.

1. Шум связан с исчезновением значений атрибутов. Для каждого атрибута а, область допустимых значений включает значение "неизвестно": Dom' fa,) =Dom (а,) U{iV}. Таким образом, примеры обучающей выборки К содержат некоторое количество признаков со значениями N (Notjcnown).

2. Шум связан с искажением некоторых значений атрибутов в обучающей выборке. При этом истинное значение заменяется на одно из допустимых, но ошибочных значений.

В соответствии с этим введём две модели шума.

Модель шума "Отсутствие значений"

Дано: К - обучающая выборка, а, - атрибут, Dorn(a,) - область допустимых значений атрибута. V - уровень шума по данному атрибуту.

Получить: ' К' - обучающую выборку, где Dom(a,)' = Dom(a,) u{N), вероятность появления значения N в поле атрибута a, p(N) =V.

Описание алгоритма внесения неизвестных значений дано ниже.

Процедура Внесение неизвестных значений | Входные данные

| входная выборка - (не содержит шума).

| х: входной атрибут, для которого выполняется внесение шума. I V: заданный уровень шума. ! Выход

Т\ множество входных данных, содержащее шум по атрибуту х, Начало

1. Положить Т равным 0. ! 2. Для каждого примера теЪ выполнить

2.1 .Получить г - случайное число в интервале [0, 1 ]. 2.2.Если г<С то 2'=1ки{х) иначе получить пример т' заменой | значения атрибута х в примере т на значение N (Мо1_кпсмп)\

приписать пример т' множеству: 7':=2'и{т'}. ! конец цикла

3. Вывести Т.

Конец алгоритма

Вычислительная сложность алгоритма составит 0^пк\ где п -- число примеров в обучаюшей выборке, к - число атркбутов у каждого примера. Данный алгоритм используется для внесения шума в атрибуты любого типа. Модель шума "Перемешивание значений"

Дано: К - ооучаюшая выборка, а, - атрибут. Цот(а,) - область допустимых значений атрибута. W - уровень шума по данному атрибуту.

Получить: К' - обучающую выборку, где Вот(а;)' = Вот(а,)= {2\, ъ^ ... , гч}, вероятность появления истинного значения в поле атрибута а, составляет С. вероятность появления любого из (д-1) ошибочных значений составляет

Поскольку одно из q значений в результате измерения обязательно будет получено, справедливо соотношение: С+(^-/)\¥=1.

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

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

2). Параметр х является дискретным и принимает q возможных значений.

3). Первоначальное множество примеров К (обучающая выборка), включающее атрибут х, не содержит шума.

Обозначим через X подмножество всех примеров множества К в текущем узле дерева решений.

Обозначим через Т разбиение всех примеров множества X по значениям атрибута х:

Формальное описание процедуры перемешивания дано ниже.

! Процедура перемешивания |

| Входные данные |

1 Ъ\ входная выборка - подмножество исходной обучающей выборки (не 1 содержит шума). !

х: входной атрибут, имеющий ц состояний, для которого выполняется I . ветвление. |

! С: уровень шума. \

! Выход |

Б: «беспорядочное» множество разбиения входных данных 2 по атрибуту I

!

, 8=8|и'82и... где 8к ={ое2|х=*4 } к-1,2,...д . |

! Начало ;

; 1. Положить каждое Б равным 0.

I 2. Пусть Т - множество верных разбиений, полученных при разбиении | множества Ъ на д частей для входного атрибута х. ! |_3. Для каждого разбиения ТкеТ выполнить______|

3 ! .Для каждого примера т. еТк выполнить 3 1.Ы1олучить г - случайное число в интервале [0. 1]. 3.1 ?.Если г'С то S '=S,'_'{Ti иначе ел}чайным образом выбрать S, j^k и приписать пример х этому множеству S:=S,'U{tJ.

Конец алгоритма

Сложность алгоритма внесения шума посредством случайного беспорядка составит OKn-q)d). где d - количество уровней дерева, п- число примеров в обучающей выборке, q- среднее число значений входных величин для каждого атрибута.

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

Дано О множество объектов, представленных в некоторой интеллектуальной системе.

Пусть V с О множество объектов системы, относящихся к определённому классу. W образует множество отрицательных

объектов относительно данного класса.

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

1. Пусть имеется обучающая выборка К'= Klt\jK'~, такая, что К cV

Пусть обьект о, входящий в обучающую выборку, представлен вектором признаков: о = ^ >ч-х2 . ..., хг, >. Для каждого признака х, область допустимых значений может включать значение "неизвестно":

Задаётся уровень шума V для указанных признаков. В соответствии с выбранным типом шума примеры К мог/т содержать некоторое количество признаков со значениями "неизвестно" (Л1), либо все значения признаков определены, но отличаются от истинных.

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

2. Пусть одним из способов получена логическая функция R - правило распознавания. Задана контрольная^ выборка

Необходимо для каждого у е Y получить значения логической функции R(y).

Значения признаков объекта у = <у у2, ..., у„ >

принадлежат Dom (у,) U {N}, где N соответствует значению " неизвестно ".

В соответствии с этим область значений функции R (yj образует множестве {True, False, Not known}:

Rfy) = False , если объект у е Y",

R(y) = Nut known, если распознавание не успешно.

Считая, что правило R(y) получено на основе обучающей выборки К, не содержащей объектов со значениями .V, и считая . что качество распознавания правилом R объектов, не содержащих зашумленных признаков, удовлетворительно, необходимо:

- исследовать зависимость эффективности распознавания от уровня шума в

заданных признаках;

- предложить методы улучшения для правила распознавания R, способные

повысить качество распознавания.

Построение дерева решений при наличии примеров с неизвестными значениями приведёт к многовариантным решениям, поэтому попытаемся найти возможность восстановить эти неизвестные значения. Для восстановления "потерянных" значений признаков предлагается использовать аналог метода "ближайшего соседа". Поскольку в предъявленной обучающей выборке К известно, к какому классу принадлежит объект X, можно восстановить потерянное значение признака по значениям признаков нескольких ближайших к нему объектов, принадлежащих тому же классу.

Чтобы применить метод ближайшего соседа, необходимо ввести метрику на векторах из /С.

Пусть имеются Х=<Х/, .. , х„> и Y=<yi, ... , у„> - объекты выборки fC. Определим расстояние между этими объектами по формуле

Для дискретных признаков Если одно из значений неизвестно, принимаем d(x, ->>,)=1 (предположительно, имеет место наихудший случай).

Для непрерывных признаков расстояние ¿/(х, — ) определяется на интервале

[О, 1] следующим образом: d(x, - у ) = —j

В случае, если одно из значений непрерывного признака неизвестно (y,-N),

rnax(jx,-am>J, |x,-a„J)

по известному значению х, определим «цх, - v, ) =-1—;-1—-■

Если оба значения признака неизвестны, также примем

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

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

Ниже приводится описание алгоритма по т агам. Алгоритм ВОССТАНОВЛЕНИЕ

Дано: Обучающая выборкал, содержащая неизвестные значения. Получить: Обучающую выборку К", не содержащую неизвестных значений начало К~ 0

Для всех объектов К. повторять нц

если ^содержит значение признака ал -А',

то Для всех (Те 1С) к (У не имеет значений N для признака ак) повторять

нц

вычислить Б(Х, У), определить множество №аг(Х) примеров, наиболее близких кХ; ¡Ыеаг^^р. кц

Для всех 2еКеаг(А) получить множество значений признака ак Определить на основе анализа объектов множества №аг(Х) неизвестное значение т*. Если успех

то присвоить т* к-му признаку объекта X.

иначе исключитьХиз обучающей выборки конец если

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

кц

Вывести множество К\ конец алгоритма

Рассмотрим подробно стратегию определения неизвестного значения т*. Множество №аг(А) содержит р примеров, для которых определены значения признака ал.

1. Признак \ - количественный. Определяем неизвестное значение как среднее арифметическое

2. Признак ак- качественный. Определить неизвестное значение т* как наиболее часто встречающееся среди примеров №аг(Х).

Введём понятие информационной системы по классу К. Информационная система, обозначаемая далее как 18{К), представляет информационную структуру, которая включает следующие данные:

- для дискретных признаков создаётся таблица частоты появления каждого из возможных значений признака в обучающей выборке;

- для непрерывных признаков определяется интервал (хтах, хтп), в который попадают все значения данного признака, представленные в обучающей выборке.

Информационная система !S(AT) характеризует обучающую выбсрку по классу fC О б о з н a/*T(k|i - множество значений, которые принимает признак х, на /Г. Очевидно, Д (х )cDom(x,). Тогда

ще для непрерывных гризнаков

is{\') = {< аI, па >| м е Д' (х,), пт - частота появчения значения ai в К*}. Информационная система IS(K) для обучающей выборки по классу К и множества Д"(х,)строятся аналогично.

Рассмотрим стратегию применения алгоритма ВОССТАНОВЛЕНИЕ при построении дерева решений. Основной особенностью этапа обучения является наличие в обучающей выборке решающего атрибута, на основе которого происходит разделение примеров на классы ВТ и К. В свете этого алгоритм восстановления неизвестных значений будет использоваться в следующей модификации.

Во-первых, при поиске ближайших соседей примера X будут использоваться только объекты, относящиеся к тому же классу, что и сам объект X. Во-вторых, В случае, если среди множества ближайших соседей объекта Хке удалось выбрать наиболее часто встречающееся значение для неизвестного признака, то неизвесгиому признаку присваивается значение, наиболее часю встречающееся среди примеров всей обучающей выборки по классу fC или К. Эти значения хранятся в информационной системе Будем использовать модификацию алгоритма ВОССТАНОВЛЕНИЕ, называемую далее ВОССТАНОВЛЕНИЕ 2. Этот алгоритм применяется длч обучающих выборок, имеющих решающий атрибут. Его особенности-

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

2. Перед началом работы алгоритма восстановления по классу fC и по классу А" строятся информационные системы IS(KT), IS(K'\ В случае, если среди множества ближайших соседей объекта X не удалось выбрать наиболее часто встречающееся значение для неизвестного дискретного признака, то неизвестному признаку присваивается значение, наиболее часто встречающееся среди примеров всей обучающей выборки по классу 1С или К.

Сложность приведённых выше алгоритмов составляет составляют 0(к-п2) Предложенные алгоритмы восстановления неизвестных значений используются далее для решения задач индуктивного формирования понятий. Предлагается алгоритм IDTUV (Induction of Decision Trees with restoring Unknown Values), который включает процедуру восстановления неизвестных значений при наличии в обучающей выборке примеров, содержащих шум Когда неизвестные значения атрибутов восстановлены, используется один из алгоритмов построения деревьев решений. Примеры, для которых не удалось восстановить неизвестные значения, удаляются из обучающей выборки. Ниже приводится псевдокод алгоритма IDTUV

Алгоритм ШТЦУ

Дано: К= К' С/ К" Получить ; дерево решений Т Начало

Получение К= К ^ К

Для всех информативных атрибутов К

Повторять

нц

Если имеется неизвестное значения атрибута то применить алгоритм ВОССТАНОВЛЕНИЕ

кц

Если

информативные атрибуты непрерывные значения то применить алгоритм С4.5 иначе применить алгоритм ГО3 конец если

вывести Т - дерево решений Конец IDTUV

Очевидно, вычислительная сложность алгоритма ГОТЦУ складывается из вычислительной сложности алгоритма ВОССТАНОВЛЕНИЕ и вычислительной сложности алгоритма ГО3 либо С4.5, поскольку два последних алгоритма выполняются альтернативно.

Для улучшения работы алгоритма ГОТЦУ предлагается использовать алгоритм сокращения дерева решений, предложенный Куинланом. Этот алгоритм формирует последовательность упрощенных деревьев и для его работы необходимо наличие тестового множества примеров. Алгоритм работает следующим образом: сначала полное дерево используется для классификации примеров тестового множества и для каждого узла дерева запоминается количество примеров каждого класса. Затем для каждого узла вычисляется количество ошибок, допущенных в процессе классификации и количество ошибок, которое было бы допущено, если бы соответствующее поддерево было редуцировано в лист Из всех узлов дерева выбирается тот, который дает наибольший выигрыш в количестве ошибок, и преобразуется в лист. Процесс повторяется до тех пор, пока не останется узлов, редукция которых уменьшает общее количество ошибок.

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

югиу

Структура программного комплекса

На рисунке представлена структура программного комплекса. Данная программа на основе обучающей выборки

- строит классификационную модель (решающее дерево);

- формирует продукционные правила, эквивалентные построенному дереву:

- по решающему дереву производит распознавание (классификацию) объектов.

Основные возможности программы

• Работа с атрибутами, имеющими как дискретные, так и непрерывные диапазоны.

• Определение решающего атрибута для объектов (по умолчанию решающим считается последний атрибут).

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

• Классификация новых объектов. При неполноте информации о классифицируемом объекте программа позволяет получить результат классификации объекта в виде множества пар вида (К:, т}), где К, -класс. т) - оценка достоверности принадлежности объекта классу Кг

• Сохранение построенного решающего дерева в файле с возможностью последующего использования его при распознавании объектов.

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

• Использование в качестве обучающего множества таблиц баз данных. При этом возможна обработка таблиц с числом объектов до 50 000 и количеством атрибутов до 20

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

Калифорнийского университета информатики и вычислительной техники UCI Machine Learning Repository

1. Данные «задач монахов» (Monk's problems).

2. Медицинские данные:

диагностика сердечных заболеваний (Heart)

3 Репозиторий данных проекта StatLog: Диагностика заболеваний диабетом (Diabetes). Австралийский кредит (Australian).

4 Другие наборы данных (из области биологии и судебно-следственной практики):

распознавание типов цветков ириса (Iris).

Первоначально эксперимент был проведён с перечисленными выборками без внесения шума в данные. Сравнение проводилось с такими известными алгоритмами обобщения, как ЮЗ. С4.5, CN2 и CART5. Результаты показали, что точность классификации алгоритма IDTUV при отсутствии шума в данных практически совпадает с точностью классификации алгоритмов ID3 и С4.5.

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

Для внесения искажений было предложено использовать наиболее информативный признак таблицы, который размещается в корне дерева решений. Очевидно, изменения значений именно такого признака способны наиболее существенно повлиять на результаты работы алгоритмов обобщения и классификации. Были рассмотрены и проанализированы ситуации наличия шума в 5%, 10% и 20% по выбранному признаку.

Первая группа опытов предназначалась для проверки того, как шум в обучающей выборке влияет на построение дерева решений. Опыты проводились по следующей схеме. В обучающую выборку программой NOISE вносится некоторое количество неизвестных значений. Затем производится восстановление таких значений по методу ближайшего соседа. На полученной обучающей выборке вновь строится дерево решений, которое необходимо сравнить с деревом, построенным на основе выборки без шума. Результаты показали, что при шуме в 5%, 10% и 20% по наиболее информативному признаку в 40% случаев получено полное совпадение дерева решений, построенного на зашумлённой выборке, с деревом решений, полученном на выборке без шума. В остальных случаях незначительные различия наблюдались на нижних уровнях дерева решений Это показывает высокую эффективность работы алгоритма ВОССТАНОВЛЕНИЕ.

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

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

Таблица 1. Влияние шума на точность классификации при отсутствии значений в тестовой выборке

Набор Точность классификации в выборке, %

данных Нет шума Шум 5% Шум 10% Шум 20%

Golf 90 89,74 88,3 86.74

Heart 98,15 97,38 96.6 93,07

Australian 86,% 84,86 84,76 81,26

Monks-1 78,88 77.86 76,91 74.29

Monks-3 95,29 93.71 92,9 90,5

Iris 98.36 95,63 93,44 89,62

Среднее 91,273 89,633 88.82 86,02

Из данных, приведённых в таблице 1, следует, что при шуме 20% точность классификации, которую обеспечил алгоритм IDTUV, снизилась только на 5.75% (в среднем по всем выборкам).

Таблица 2. Влияние шума на точность классификации при перемешивании значений в тестовой выборке

данных Нет шума Шум 5% Шум 10% Шум 20%

Golf 90 88 85 81

Heart 98,15 95.93 93,7 87,59

Australian 86,96 82,61 79,71 78,26

Monks-1 78,88 77,61 76,14 74,97

Monks-3 95,29 93,9 91,24 87,58

Iris 98,36 96,72 96 72 93,44

Среднее 91,273 89,13 87,09 83,8

Из таблицы 2 видно, что при самом высоком уровне шума 20% алгоритм IDTUV в среднем дал результат классификации 83,8%. Алгоритм ЮЗ при классификации примеров, содержащих 20% шума, дал точность классификации

67/о. Это показывает, что ошибки алгоритма TDTUV оказались в 2 раза ниже, чем у ЮЗ.

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

В заключении приведены основные результаты, полученные в диссертационной работе.

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

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

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

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

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

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

6. Введена метрика, позволяющая определять расстояние между объектами, содержащими неизвестные значения признаков. На основании этой метрики разработаны алгоритмы восстановления, позволяющие определить предполагаемое значение неизвестного признака методом "ближайшего соседа".

7. Предложен алгоритм IDTUV, позволяющий обрабатывать обучающие выборки, содержащие примеры с неизвестными или искажёнными значениями, на основе использования алгоритмов ID3 и С4.5 в сочетании с алгоритмами восстановления.

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

20

05. И ~ OS. /3

теоретические результаты и создана на основе предложенных алгоритмов.

9. Разработанные алгоритмы и программные средства применены в динамической экспертной системе оперативной диагностики состояния экологически опасных объектов и производств «ДИЭКС» для повышения точности технической диагностики и эффективности прогнозирования ресурса оборудования,

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

1. Айман Бериша. Алгоритмы обобщения в интеллектуальных системах // Радиоэлектроника, электротехника и энергетика: Тез. докл. девятой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. - Т.1. - М.: Изд. МЭИ, 2003.-С. 283 - 284.

2. Айман Бериша. Примененение алгоритмов обобщения в системах принятия решений // Международный форум информатизации - 2003: Труды международной конференции «Информационные средства и технологии». В 3-х т. - Т. 1 - М.: Янус-К, 2003. С. 143 - 146.

3. Айман Бериша, Сравнительный анализ алгоритмов обобщения, строящих деревья решений // Радиоэлектроника, электротехника и энергетика: Тез. докл. десятой международной научно-технической конференции студентов и аспирантов. В 3-х т, -Т.1.-М.: МЭИ, 2004. -С. 308-309.

4. Бериша A.M., Вагин В.Н., Использование алгоритма построения деревьев решений для зашумлённых данных // Доклады международного форума информатизации МФИ, 12-14 октября 2004.-М.: МИФИ, 2004. Том 1. -С. 171-174.

5. Бериша AM., Разработка алгоритмов для обобщения и классификации объектов с шумом // Доклады международного форума информатизации МФИ, 12-14 октября 2004. -М: МИФИ, 2004. Том 1. -С. 167-170.

6. Бериша А.М, Сравнение точности классификации разработанного алгоритма IDTUV С другими известными алгоритмами обобщения // Радиоэлектроника, электротехника и энергетика: Тез. докл. междунар. науч.-техн. конф. студентов и аспирантов. В 5-ти т. - Т.1. - М.: Изд. МЭИ, 2005. Том 1, С. 327-328

Подписано в печать 1.03.05 Зак. 65 Тир. 100 П.л. 1,25 Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д. 13

952

ВВЕДЕНИЕ.

ГЛАВА 1 Обзор систем обнаружения знаний и систем извлечения знаний.

1.1 Системы поддержки принятия решений.

1.2 Нерешенные проблемы баз данных.

1.3 Процесс обнаружения знаний.

1.4 Задачи обнаружения знаний.

1.5 методология обнаружения знаний.

1.6 Сравнение аналитических систем различного типа.

1.6.1 Предметно - ориентированные аналитические системы (технический анализ)

1.6.2 Статистические пакеты.

1.6.3 Нейронные сети.

1.6.4 CBR (системы рассуждения на основе аналогичных случаев).

1.6.5 Деревья решений.

1.6.6 Генетические алгоритмы.

1.6.7 Нелинейные регрессионные методы (методы группового учёта атрибутов).

1.7 Описание дерева решений.

1.8 Основные алгоритмы, использующие деревья решений.

1.8.1 Алгоритм ID3.

1.8.2 Определения.:.

1.8.3 Использование критерия прироста информативности Gain Ratio.

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

1.9 Методы сокращения решающих деревьев.

1.9.1 Сокращение, уменьшающее ошибки (Reduced Error Pruning).

1.9.2 Сокращение по пессимистической ошибке (Pessimistic Error Pruning ).

1.9.3 Сокращение по минимальной ошибке (Minimum Error Pruning).

1.9.4 Сокращение по критическому значению (Critical Error Pruning).

1.9.5 Сокращение, основанное на ошибках (Error-Based Pruning).

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

Глава 2 Индуктивное построение понятий при "зашумлённых" данных.

2.1 Признаковое описание объекта.

2.2 Проблемы, возникающие при работе с "зашумлёнными" данными.

2.2.1 Ограниченная информация.

2.2.2 Искажённая информация.

2.2.3 Большой размер баз данных.

2.2.4 Изменение баз данных со временем.

2.3 Проблема моделирования шума в данных.

2.3.1 Внесение шума в поле признака, содержащего дискретные значения.

2.3.2 Внесение шума в поле признака, содержащего непрерывные значения.

2.4 Анализ распределения значений для непрерывных признаков.

2.4.1 Оценка математического ожидания, дисперсии, функции распределения и плотности.

2.4.2 Распределения, отличные от равномерных.

2.5 Моделирование шума в обучающей выборке.

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

Глава 3 Методы построения деревьев решений при наличии шума во входных данных.

3.1 Постановка задачи индуктивного построения понятий при отсутствии шума и при наличии шума.

3.2 Алгоритм предсказания неизвестных значений по методу ближайшего соседа

3.3 Использование алгоритма восстановления неизвестных значений при построении дерева решений.

3.4 Описание работы алгоритмов ID3 и С4.5 в сочетании с алгоритмами восстановления.

3.5 Описание метода сокращения решающих деревьев.

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

Глава 4 Программная реализация разработанного метода.

4.1 Основные функции, выполняемые программой.

4.2 Структура программного комплекса.

4.3 Описание программы.

4.4 Эксперименты на тестовых данных.

4.4.1 Эксперименты на данных "задач монахов".

4.4.2 Медицинские данные.

4.4.3 Данные проекта StatLog.

4.4.4 Другие наборы данных.

4.5 Методы проверки.

4.5.1 Перекрестная проверка.

4.5.2 Проверка исключением одного примера.

4.5.3 Метод бутстрепа.

4.6 Методика проведения эксперимента по работе алгоритма IDTUV.

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

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

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

Настоящая диссертационная работа посвящена созданию алгоритмических и программных средств для поиска индуктивных закономерностей, неявно представленных в базах данных. Такой процесс, называемый обобщением, направлен на получение правил классификации, с помощью которых можно успешно распознавать объекты определенного класса. Над разработкой алгоритмов обобщения работали многие авторы, созданием подобных алгоритмов занимались известные ученые Р. Куинлан, Утгофф, Нуньес, Михальский, Финн, Вагин и другие. Созданные ими методы и алгоритмы внесли большой вклад в развитие систем машинного обучения; эти методы позволяют получать средства для эффективной классификации объектов, представленных множествами признаков. Однако, обработка реальных массивов, представленных в базах данных, которые часто содержат зашумленные и противоречивые данные, характеризуются большим размером и наличием избыточного множества признаков. Это снижает успешность применения этих алгоритмов. С другой стороны, массивы данных, содержащие шум, встречаются в целом ряде реальных ситуаций и задач. Для решения проблемы обработки данных, содержащих шум, необходимо было изучить модели шума, предложить способы поиска неизвестных или искаженных значений некоторых признаков, что должно повысить эффективность классических методов обобщения. Таким образом, исследование методов обобщения при наличии шума в массивах данных является актуальной задачей.

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

Поставленная задача потребовала решения следующих проблем:

1. Разработка моделей представления шума в обучающих множествах. При этом было проведено исследование моделей шума двух типов -отсутствие значений признака и искажение значений признака.

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

3. Моделирование средств для внесения шума в обучающую выборку на основе заданных параметров шума.

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

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

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

Научная новизна исследования.

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

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

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

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

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

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

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

Практическая значимость работы подтверждается внедрением полученных результатов в динамической экспертной системе оперативной диагностики состояния экологически опасных объектов и производств "ДИЭКС" в ОАО "ЦНИИКА". Имеется акт о внедрении.

Апробация работы. Основные положения и научные результаты диссертации докладывались на трех научно-технических конференциях МЭИ (ТУ) (2003, 2004, 2005 гг.), на международных форумах информатизации МФИ-2003, МФИ-2004 и МФИ-2005 (Международные конференции «Информационные средства и технологии» , г. Москва, 2003, 2004, 2005 гг.).

Публикации. Материалы по теме диссертационной работы опубликованы в 6 печатных работах.

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

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

В данной главе:

1. Была рассмотрена программная реализация системы на основе разработанной модификации алгоритма обобщения IDTUV, приведенной в главе 3. Система формирует обобщенное правило в виде дерева решений, а также производит распознавание тестовых объектов.

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

3. Были описаны проведенные эксперименты на тестовых наборах данных, в том числе на известной тестовой коллекции данных Калифорнийского университета информатики и вычислительной техники UCI Machine Learning Repository ([64]).

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

5. Эксперимент был проведен для модели шума "отсутствие значения признака" и "перемешивание значений признака". В обоих случаях алгоритм IDTUV показал точность классификации более высокую, чем алгоритмы ID3 и С4.5. Средняя точность классификации для модели шума "отсутствие значений" оказалась выше, чем для модели "перемешивание", что свидетельствует о высокой эффективности алгоритма ВОССТАНОВЛЕНИЕ.

ЗАКЛЮЧЕНИЕ

Перечислим основные результаты, полученные автором в процессе работы над диссертацией.

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

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

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

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

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

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

6. Предложен алгоритм IDTUV, позволяющий обрабатывать обучающие выборки, содержащие примеры с неизвестными или искажёнными значениями, на основе использования алгоритмов ID3 и С4.5 в сочетании с алгоритмами восстановления.

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

8. Полученные результаты моделирования показали, что алгоритм IDTUV в сочетании с алгоритмами восстановления позволяет повысить точность классификации примеров с отсутствующими значениями признаков в 3 - 4 раза по сравнению с классическими алгоритмами ID3 и С4.5.

Разработанные алгоритмы и программные средства применены в динамической экспертной системе оперативной диагностики состояния экологически опасных объектов и производств «ДИЭКС» в ОАО «ЦНИИКА», что позволило повысить точность технической диагностики оборудования сложных промышленных объектов благодаря возможности обработки зашумленных данных.

129

1. Вагин В. Н. Дедукция и обобщение в системах принятия решений. М.: Наука, 1988 384 с.

2. Alter, S.L. Decision Support Systems: Current Practice and Continuing Challenge.Addison-Wesley. 1980.

3. Вагин B.H., Загорянская A.A. Извлечение данных как наиболее важное приложение технологии информационных хранилищ. //Программные продукты и системы, 1, 2000. с.2-11.

4. Codd E.F. Providing OLAP (On-line Analytical Processing) to User-Analysts: An IT Mandate. Codd and Associates, 1993.

5. Вагин B.H. и др. Достоверный и правдоподобный вывод в интеллектуальных систеамх. -М.: ФИЗМАТЛИТ, 2004. -704 с.

6. Goil, Sanjay and Choudhary, Alok. Design and Implementation of a

7. Scalable Parallel System for Multidimensional Analysis and OLAP.13th International and 10th .i

8. Свинарев С. Десять требований Red Brick System. Комьютеруик-МОСКВА, 2, 1996. c.45.

9. Lu, J., Quaddus, M.A. and Williams, R. Developing a Knowledge-Based Multi-Objective Decision Support System. System Sciences. Proceedings of the 33rd Annual Hawaii International Conference 2000.

10. Fayyad,U., Data mining and knowledge Discovery: Making Sense Out of Data. IEEE Expert, v.l 1, no.5 PP. 20-25 October 1996.

11. Fayyad U., Piatetsky-Shapiro, Smith P. From Data mining to Knowledge Discovery: an Overview. In Advances in Knowledge Discovery and Data Mining. AAAI Press/The MIT Press., Cambridge, Mass., 1996. p 1-36.

12. Brands, Estelle and Gerritsen, Rob. Assocation and Sequencing. DBMS, Data Mining Solutions Supplement. Miller Freeman, Inc. 1998.

13. Silverman B. Density Estimation for Statistics and Data Analysis. New York:1. Chaptman and Hall.

14. Quinlan J.R. Discovery rules from large collections of examples: a Case Study // Expert Systems in the Microelectronic Ahe. Edinburg, 1979.

15. Гаврилова Т.А., Червинская K.P. Извлечение и структурирование знаний для экспертных систем. М.: Радио и связь, 1992, 199 с.

16. Д. Уотермен, Нейрокомпьютерная техника, М.: Радио и связь, 1993-е. 21-63.

17. Quinlan J.R. Induction of Decision Trees// Machine Learning, Vol.1, 1986. p. 81-106.

18. Quinlan J.R. Improved Use of Continuous Attributes in С 4.5. //Journal of Artifical Intelligence Reseach, Vol. 4, 1996. pp.77-90.

19. Utgoff P.E. Incremental induction of Decision Trees.// Machine Learning, Vol.4, 1989. pp. 161-186.

20. Nunez M. The Use of Background Knowledge in Decision Tree Induction.// Machine Learning, Vol. 6, 1991. pp.231-250.

21. A. Hutchinson. Algorithmic Learning, Clarendon Press, Oxford, 1994.

22. Heckerman D. Bayesian Networks for Knowledge Discovery. In Advances in Knowledge Discovery and Data Mining. AAAI Press/The MIT Press., Cambridge, Mass., 1996. p 273-306.

23. Heckerman D. Bayesian Networks for Data Mining. In Data mining and Knowledge Discovery. 1, 1997, p79-119.

24. Гладун В.П. Планирование решений. Киев: Наукова Думка, 1990. 168 с.

25. Нечёткие множества в моделях управления и искусственного интеллекта/под ред. Поспелова Д.А. -М.: Наука, 1986.-312 с.

26. Ни X. Knowledge Discovery in Databases: Attribute-Oriented Rough Set Approach. PhD thesis, Canada, Regina, University of Regina, 1995.

27. Michael Goebel and Le Gruenwald, "A survey of data mining and knowledge discovery software tools", ACM SIGKDD, Vol.1, Issue 1, Page20, June 1999.

28. Komorowski J., Pawlak Z., Polkowski L., Skowron A. Rough Sets: A Tutorial. / Rough Fuzzy Hybridization, Springer-Verlag, 1999.

29. Pawlak Z. Rough sets and intelligent data analysis / Information Sciences, Elsevier Science, Nov. 2002, vol. 147, iss. 1, pp. 1-12.

30. Буров К. Обнаружение знаний в хранилищах данных. Открытые системы № 05-06, 1999.

31. Мусаев А. Интеллектуальный анализ данных: Клондайк или Вавилон? //

32. Банковские технологии, 1998, ноябрь-декабрь. С. 79-82.

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

34. Quinlan J.R., Improved use of continuos of function in C4.5.

35. Journal of Artificial Intelligence Research, vol. 4, pp. 77-90, 1996.

36. Holsheimer M., Siebes A. Data mining: the search for knowledge in databases. / Technical Report CS-R9406, CWI, 1994.-78 p.

37. Айман Бериша. Алгоритмы обобщения в интеллектуальных системах // Радиоэлектроника, электротехника и энергетика. Тез. докл. девятой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. — Т.1. -М.: Изд. МЭИ, 2003.-С. 283 284.

38. Salvatore Ruggieri. Efficient С4.5, IEEE TRANSACTIONS AND DATA ENGINEERING. Vol. 14, No. 2, March / April 2002.

39. Айман Бериша. Примененение алгоритмов обобщения в системах принятия решений // Международный форум информатизации — 2003: Труды международной конференции «Информационные средства и технологии». В 3-х т. Т.1 - М.: Янус-К, 2003. С. 143 - 146.

40. Mingers J. An Empirical comparison of pruning methods fordecision tree induction. Machine Learning , Vol. 4, pp. 227-243, 1989.

41. Quinlan J. R. Simplifying Decision Trees. Int'l J. Man- Machine Studies, Vol 27, pp. 221-234. 1987.

42. Floriana Esposito, Donato Malerba, Giovanni Semeraro, IEEE, Acomparative analysis of methods for pruning decision tree, TRANSACTIONS ON PATTERN ANALYSIS & Machine Intelligence, vol. 19, No. 5, May 1997.

43. Niblett Т., Bratko I. Learning decision rules in noisy domains. Proceedings of Expert Systems 86. Cambridge University Press: Cambridge, 1986.

44. Vagin V.N., Fedotov A. A., Fomina M.V. Methods of Data Mining and Knowledge Generalization in Large Databases. Journal of Computer and Systems Sciences International, Vol.38 No.5, 1999. p. 714-727.

45. Федотов A.A., Фомина M.B. Система формирования обобщенных продукционных правил на основе анализа больших баз данных. // Сборник научных трудов Шестой национальной конференции по искусственному интеллекту КИИ-98. Том 1. Пущино, Россия. 1998. с. 287-292.

46. Дюк В., Самойленко A. Data Mining. -СПб: Питер, 2001. -368 с.

47. Kalapanidas Е., Avouris N., Craciun М., Neagu D. Machine Learning algoritms: a Study on Noise Serntivity.

48. Айвазян C.A., Бухштабер B.M., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Классификация и снижение размерности. —М.: Финансы и статистика, 1989. -128с.

49. Вентцель Е.С. Теория вероятностей. М.: Высш.шк., -576с. Физматлит, -1972 г.

50. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. -511с.

51. Бонгард М.М. Проблема узнавания М.: Наука, 1967. -320с.

52. Смородинский С.С., Батин Н.В. Алгоритмы и программные средства интеллектуальных систем принятия решений. Часть 2. -Минск: БГУИР, 1994, -68с.

53. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.-411 с.

54. Mookerjee V., Mannino М., Gilson R. Improving the Performance Stability of Inductive Expert Systems under Input Noise // Information Systems Research, Vol.6 N4 1995, p.328-356.

55. Hill D. Interviever, Respondent and Regional Office Effects, Measurement Errors in Surveys. Chapter 23, New-York, 1991, p.463-486.

56. Rao J., Thomas R. Chi-Squared Tests with Complex Survey Data Subject to Misclassiflcation Error, Measurement Errors in Surveys. Chapter 31, New-York, 1991, p.637-664.

57. Clark P., Niblctt T. Induction in Noisy Domains. In Proc. 2nd European Machine Learning Conferencc(EWSL-87), pp.11-30.

58. Бериша A.M., Вагин B.H., Использование алгоритма построениядеревьев решений для зашумлённых данных. // Доклады международного форума информатизации МФИ, 12-14 октября 2004.-М.: МИФИ, 2004. Том 1. -С. 171- 174.

59. Dixon P. Nearest Neighbor Methods. Dep. of Statistics, Iowa State University, 2001. 25p.

60. Вагин B.H., Гулидова В.Г., Фомина M.B. Распознавание состояний сложного объекта при неполной входной информации. Изв. АН СССР. Техн. кибернетика. № 5 1992. с. 120-132.

61. Бериша A.M., Разработка алгоритмов для обобщения и классификации объектов с шумом // Доклады международного форума информатизации МФИ, 12 14 октября 2004. -М.: МИФИ, 2004. Том 1. -С. 167-170.

62. Esposito F., Malcrba D., Semeraro G., Tamma V. the Effects of Pruning Methods on the Predictive Accuracy of Induced Decision Trees. In Appl. Stochastic. Models Bus. Ind. V. 15, 1999, pp.277-299.

63. Huo X. and all. A Graph-Based Tree Pruning Algorithm and Automatic Identification of Inadmiissibility. Technical Report. The Logistic Institute, Georgia tech., The Logistic Institute Asia Pacific, National university of Singapore, 2002, 20 p.

64. Hall L.O. and all. Error-Based Pruning of Decision Trees Grown on Very Large Data Sets Can Work. Int. Conference on Tools for Art. Intell., Nov.2002, pp.233-238.

65. Windcatt Т., Ardeshir G. An empirical comparison of pruning methods for ensemble classifiers. In IDA 2001. Springer-Verlag, Lecture notes in computer science, 2001.

66. C. J. Merz and P. M. Murphy. UCI Repository of Machine Learning Datasets, 1998. Information and Computer Science University of California, Irvine, С A 92697-3425, http://www.ics.uci.edu/ mlearn/MLRepository.html.

67. R. S. Michalski, L. Mozetic, J. Hong and N. Lavrac. The

68. Multipurpose Incremental Learning System AQ15 and Its Testing Applicationto Three Medical Domains, Proceedings of 1986 AAAI Conference, Philadelphia, PA, 1986, pp. 1041-1045.

69. D. Michie, D.J. Spiegelhalter, and C.C. Taylor, Machine Learning, Neural and Statistical Classification. Ellis Horwood, Chichester, UK, 1994.

70. Weiss S., Kulikowski C. Computer System that Learn, Morgan Kaufmann, 1991.

71. Efron and R. J. Tibshirani, An Introduction to the to the bootstrap. Chapman and Hall, New York, 1993.

72. Ron Kohavi, Brian Frasca. Useful Feature Subsets and Rough Set Reducts. In proceedings of the third international workshop on rough sets and soft computing. (RSSC'94). pp. 310-317, San Jose, California, 1994.

73. F. Zarndt, A comprehensive case study: An examination of machine learning and connectionist algorithms. M.Sc. Thesis, Dept. Comput. Sci., Brigham Young Univ., Provo, UT, 1995.

74. Ресурс Интернет: http://www.salford-systems.com/cart.php.

75. R.C. Holte. Very simple classification rules perform well on most commonlyused datasets // Machine Learning, Vol. 1, pp. 63--91, 1993.t