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

Актуальность темы

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

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

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

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

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

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.

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