Пользовательский интерфейс обеспечивает доступ ко всем возможностям

системы и управляет процессами извлечения знаний и принятием решений. Качество обнаружения знаний во многом зависит от участии пользователя. Первичная подготовка данных осуществляется в блоке перевода данных во внутреннее представление, учитывающие особенности алгоритмов извлечения знаний. Блок обнаружения знаний основан на алгоритме CLS [6], который выявляет скрытые закономерности в данных. Эти закономерности формируются в виде деревьев решений и сохраняются в базе знаний в форме продукционных правил. Извлечённые знания могут пополнять существующую базу знаний некоторой экспертной системы или сразу использоваться для выработки рекомендаций по достижению поставленных целей.

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

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

Оценка эффективности алгоритма выполнялась на интеллектуальном анализе медицинских данных небольшого объёма - 74 записи. Из них были выявлены знания в количестве 9 продукций. Для увеличения практической значимости разрабатываемой системы (EasyGetKnowledge) намечается расширить ориентацию алгоритма извлечения на базы данных различного формата.

2.1.1 Алгоритм построения деревьев решений для системы автоматизированного извлечения знаний

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

R(DX1, …, DXn, DY1, ..,DYm) = {< x1, …, xn, y1, …, ym>¦xi Є DXi,

yj Є DYj, I = 1..n, j = 1..m8P(x1, …, xn, y1, …,ym) }, (2.1)

где xi -значения входных атрибутов Xi из домена DXi;

yi -значения выходных атрибутов Yi из домена DYi;

P(x1,…,xn,y1,…,ym)- предикат, описывающий условия отображения конкретной предметной области в кортежи значений атрибутов < x1,…,xn,y1,…,ym>.

Необходимо сформировать отображение в виде набора правил:

{X1,X2,..,Xn}-> {Y1,Y2,…,Ym} (2.2)

ставящих каждому входному набору значений {xi=DXi, i=1..n} в соответствие некоторый набор целевых значений {yj=DYj, j=1..m}. Полученные функциональные зависимости:

Yj = Fj(X1,X2,….,Xn), j=1..m (2.3)

должны быть верны для кортежей отношения (1) и могут быть использованы при нахождении выходных атрибутов Yj для новых значений входных атрибутов Xi (i=1..n).

Для автоматизированного извлечения знаний использовался метод CART (classification and regression trees) из класса методов деревьев решений. Данный подход является самым распространенным в настоящее время способом выявления, структурирования и графического представления логических закономерностей в данных. Его преимущества заключаются в следующем[33]:

• быстрый процесс обнаружения знаний;

• генерация правил в предметных областях, в которых трудно формализуются знания;

• извлечение правил на естественном языке;

• создание интуитивно понятной классификационной модели предметной области;

• прогноз с высокой точностью, сопоставимой с другими методами (статистическими и нейросетевыми);

• построение непараметрических моделей.

Хорошая эволюция и достигнутый уровень формализации методов послужили основанием использовать процедуру CART, как лучший из этого класса, в блоке извлечения знаний. В данном алгоритме можно выделить три операции, от реализации которых зависит его трудоёмкость и качество обнаружения знаний: сортировка источника данных при формировании множества условий U для атрибутов числового типа, вычисление критерия Gini [33] при разбиении узлов бинарного дерева, перемещение в таблице значительных объёмов информации при делении узла.

Покажем вычислительные затраты при классификации одного узла дерева. Пусть узлу, для которого осуществляется классификация, соответствует M объектов (строк) сводной таблицы. Каждая строка таблицы рассматривается как один пример обучающей выборки. Параметром N обозначим количество атрибутов таблицы без учёта целевого атрибута. Предположим, что в базе данных содержатся только атрибуты категорийного типа, имеющие в среднем Ncp значений.

Для определения необходимости последующего деления узла потребуется

M проверок. Рассмотрим случай, когда из узла порождаются узлы-потомки. В этом случае для каждого атрибута формируются 2Ncp-1-1 возможных условий ui принадлежит U (|U|=2Ncp-1-1) (2.4), которые определяют варианты разбиения узла. Эта операция реализуется M проверками. Отбор наилучшего варианта разбиения узла дерева проводится по наибольшей классифицирующей силе, вычисляемой по критерию Gini :

(2.4)

Из формулы (2.4) видно, что её вычислительная сложность состоит из суммы следующих операций: подсчёт элементов li, ri класса i (i=1..Ncp) в множествах L и R и вычисление индекса Gini. Подсчёт объектов каждого класса занимает M операций, а вычисление индекса Gini выполняется за 2•Ncp+2 операций. Следовательно, классификация узла по условию ui и отбор наилучшего разбиения занимает в целом 2M + 2Ncp операций. Тогда для каждого категорийного атрибута потребуется (2M + 2Ncp)•( 2Ncp-1-1) операций. А так как таблица имеет N атрибутов, то классификация одного узла без учёта разделения будет занимать (2M + 2Ncp)•(2Ncp-1-1)•N +M условных операций. На примере таблицы, содержащей 1000 строк, 10 категорийных атрибутов с 5 возможными значениями, разбиение корневого узла дерева потребует приблизительно 300 000 условных операций, что значительно меньше полного перебора.

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

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

2.1.2 Интеллектуальный анализ данных Data Mining

Data Mining переводится как "добыча" или "раскопка данных". Нередко рядом с Data Mining встречаются слова "обнаружение знаний в базах данных" (knowledge discovery in databases) и "интеллектуальный анализ данных". Их можно считать синонимами Data Mining. Возникновение всех указанных терминов связано с новым витком в развитии средств и методов обработки данных.

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

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

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

Специфика современных требований к такой переработке следующие:

• Данные имеют неограниченный объем

• Данные являются разнородными (количественными, качественными,

текстовыми)

• Результаты должны быть конкретны и понятны

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

Традиционная математическая статистика, долгое время претендовавшая на роль основного инструмента анализа данных, откровенно спасовала перед лицом возникших проблем. Главная причина - концепция усреднения по выборке, приводящая к операциям над фиктивными величинами (типа средней температуры пациентов по больнице, средней высоты дома на улице, состоящей из дворцов и лачуг и т.п.). Методы математической статистики оказались полезными главным образом для проверки заранее сформулированных гипотез (verification-driven data mining) и для "грубого" разведочного анализа, составляющего основу оперативной аналитической обработки данных (online analytical processing, OLAP).

В основу современной технологии Data Mining (discovery-driven data mining) положена концепция шаблонов (паттернов), отражающих фрагменты многоаспектных взаимоотношений в данных. Эти шаблоны представляют собой закономерности, свойственные подвыборкам данных, которые могут быть компактно выражены в понятной человеку форме. Поиск шаблонов производится методами, не ограниченными рамками априорных предположений о структуре выборке и виде распределений значений анализируемых показателей. Примеры заданий на такой поиск при использовании Data Mining приведены в табл. 2.1.

Таблица 2.1 - Примеры формулировок задач при использовании методов OLAP и Data Mining [34]

Важное положение Data Mining - нетривиальность разыскиваемых шаблонов. Это означает, что найденные шаблоны должны отражать неочевидные, неожиданные (unexpected) регулярности в данных, составляющие

так называемые скрытые знания (hidden knowledge). К обществу пришло понимание, что сырые данные (raw data) содержат глубинный пласт знаний, при грамотной раскопке которого могут быть обнаружены настоящие самородки (рис. 2.2).

В целом технологию Data Mining достаточно точно определяет Григорий Пиатецкий-Шапиро - один из основателей этого направления:

Data Mining - это процесс обнаружения в сырых данных

ь ранее неизвестных

ь нетривиальных

ь практически полезных

ь и доступных интерпретации знаний,

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

ь человеческой деятельности.

Сфера применения Data Mining ничем не ограничена - она везде, где имеются какие-либо данные. Но в первую очередь методы Data Mining сегодня, мягко говоря, заинтриговали коммерческие предприятия, развертывающие проекты на основе информационных хранилищ данных (Data Warehousing). Опыт многих таких предприятий показывает, что отдача от использования Data Mining может достигать 1000%. Например, известны сообщения об экономическом эффекте, в 10-70 раз превысившем первоначальные затраты от 350 до 750 тыс. дол.[35]. Известны сведения о проекте в 20 млн. дол., который окупился всего за 4 месяца. Другой пример - годовая экономия 700 тыс. дол. за счет внедрения Data Mining в сети универсамов в Великобритании.

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

2.1.3 Приложения Data Mining

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11