Использование технологии анализа данных в интеллектуальных информационных системах

Аннотация

Арсеньев С.Б., Бритков В.Б., Маленкова Н.А. Использование технологии анализа данных в интеллектуальных информационных системах. В статье рассматриваются вопросы использования технологии добычи знаний Data Mining. Описываются основные этапы анализа данных в интеллектуальных системах с помощью этой технологии, от этапа приведения данных к форме, пригодной для применения конкретных реализаций методов Data Mining, решения проблем избыточности, неинформативности, чрезмерной корреляции данных, до непосредственного применения методов добычи знаний и верификации и проверки получившихся результатов. Исследуются некоторые алгоритмы Data Mining на примере реализации в пакете PolyAnalyst описываются их наиболее известные модификации, анализируются условия их применимости к данным разных типов и объемов, приводятся сложности алгоритмов.

Введение

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

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

Методы «добычи» знаний (data mining) позволяют уменьшить остроту проблемы. Используя продвинутые аналитические методы в области добычи знаний из исходных, «сырых», данных, многие организации увеличивают прибыль, повышают производительность, сокращают затраты и увеличивают удовлетворенность клиентов. Они уже активно используются при анализе рынка, маркетинге, прогнозе фондовых котировок и других бизнес-приложениях. Но в первую очередь эти методы сегодня должны заинтересовать коммерческие предприятия, развертывающие проекты на основе информационных хранилищ данных (Data Warehousing).

Попробуем дать сравнительную оценку возможностей анализа данных Человеком и компьютером. В то же время, физическое быстродействие отдельного биологического нейрона чрезвычайно низко по сравнению быстродействием современной вычислительной техники, оно на 8 порядков величины меньше быстродействия современного персонального компьютера и проигрывает суперкомпьютерам более десяти порядков величины. Соотношения объема и быстродействия памяти и определяют возможное использование искусственного интеллекта, систем KDD (Knowledge Discovery in Databases) – систем извлечения знаний из баз данных. Однако ни одна программа принципиально не в состоянии сегодня, ни и в ближайшей перспективе учесть многообразия различных факторов, как ассоциативное мышление человека. Как постановщик задачи Человек принципиально превосходит возможности компьютера.

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

Основные понятия и определения

Knowledge discovery in databases («обнаружение знаний в базах данных») – аналитический процесс исследования человеком большого объема информации с привлечением средств автоматизированного исследования данных с целью обнаружения скрытых в данных структур или зависимостей. Предполагается полное или частичное отсутствие априорных представлений о характере скрытых структур и зависимостей. KDD включает предварительное осмысление и неполную формулировку задачи (в терминах целевых переменных), преобразование данных к доступному для автоматизированного анализа формату и их предварительную обработку, обнаружение средствами автоматического исследования данных (data mining) скрытых структур или зависимостей, апробация обнаруженных моделей на новых, не использовавшихся для построения моделей данных и интерпретация человеком обнаруженных моделей.

Data mining («разработка данных») – исследование и обнаружение «машиной» (алгоритмами, средствами искусственного интеллекта) в сырых данных скрытых структур или зависимостей, которые:

– ранее не были известны;

– нетривиальны;

– практически полезны;

– доступны для интерпретации человеком [2].

В целом технологию data mining достаточно точно определяет Григорий Пиатецкий-Шапиро — один из основателей этого направления: data mining — это процесс обнаружения в сырых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности.

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

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

Основные этапы исследования данных с помощью методов KDD

Можно выделить следующие основные этапы исследования данных с помощью методов KDD:

1. Приведение данных к форме, пригодной для применения конкретных реализаций систем KDD. Для этого надо выработать четкий набор числовых или нечисловых параметров, характеризующих данную область. Выбор системы параметров производится человеком, хотя, значения параметров могут вычисляться автоматически. После выбора описывающих параметров данные могут быть представлены в виде прямоугольной таблицы, где каждая запись представляет собой отдельный объект или состояние объекта, а каждое поле – свойства или признаки всех исследуемых объектов. Практически все имеющиеся системы KDD работают только с подобными прямоугольными таблицами. Если же данные размещены в нескольких связанных между собой таблицах, то все равно необходимо привести их в прямоугольную форму.
2. Полученная прямоугольная таблица пока еще является слишком сырым материалом для применения методов KDD, и входящие в нее данные необходимо предварительно обработать, так как они могут быть в разных форматах, могут быть неполными или избыточными. В случае избыточности данных необходимо ограничить количество полей. Некоторые поля являются неинформативными: почти все записи имеют одинаковое значение поля, или наоборот, количество записей приблизительно равно количеству значений этого поля. Наконец, полей может быть очень много, и если мы все их включим в исследование, то это сильно увеличит время счета, поскольку практически для всех методов KDD характерна сильная зависимость времени счета от количества параметров, поэтому необходимо выбрать самые значимые для исследования. Но существует не только избыточность полей, но и избыточность записей. Зачастую в системах при очень большом количестве записей их выбирают случайным образом или берут каждую n-ю запись таблицы. Конечно, количество записей сильно зависит от метода анализа, но практика показывает, что в основном записей должно быть не менее 30 и не более нескольких сотен тысяч. Во многих системах к данным предъявляют строгое требование: для каждой записи должно быть известно значение каждого поля. В этом случае приходится восполнять недостающие значения. Наиболее очевидным является заполнение отсутствующих значений средним значением. Также любая реальная база данных обычно содержит ошибки, очень неточно определенные значения, записи, соответствующие каким-то редким, исключительным ситуациям, и другие дефекты, которые могут резко понизить эффективность методов KDD, применяемых на следующих этапах анализа. Такие записи необходимо отбросить.
   Еще одним этапом подготовки данных является их нормализация. Необходимо стараться приближать данные к нормальному или равномерному распределению. Часто используют следующий способ нормализации: пусть есть α – среднее и σ – дисперсия. Тогда x → (xα)/σ. Часто такое преобразование проводят перед подачей данных на вход нейросетей.

   Замечание: если в таблице есть категориальная переменная (не числовая), которая, например, может принимать три значения, то можно вместо нее включить 3 новых переменных, которые будут принимать значение 1 для своего значения и 0 для всех остальных.

3. Третий этап – это применение методов KDD. Сценарии этого применения могут быть самыми различными и включать сложную комбинацию разных методов, особенно если используемые методы позволяют проанализировать данные с разных точек зрения. Собственно этот этап исследования и принято называть data mining.
4. Верификация и проверка получившихся результатов. Очень простой и часто используемый способ заключается в том, что все имеющиеся данные, которые мы собираемся анализировать, мы разбиваем на две группы. Как правило, одна из них – большего размера, другая – меньшего. На большей группе мы, применяя те или иные методы KDD, получаем модели, зависимости, все, что требуется в нашей задаче, а на меньшей группе данных мы их проверяем. И по разнице в точности между тестовой группой и группой, использованной для обучения, мы можем судить, насколько адекватна, статистически значима построенная модель.
5. Последний этап – это интерпретация автоматически полученных знаний человеком в целях их использования для принятия решений, добавление получившихся правил и зависимостей в базы знаний и т.д.

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

Одной из систем, которая объединяет в себе все перечисленные компоненты, является пакет PolyAlalyst компании «Megaputer Intelligence» (www.megaputer.ru). В ее основу положена технология искусственного интеллекта Data Mining. При обработке исходных данных она позволяет обнаруживать многофакторные зависимости, которым придает затем вид функциональных выражений (класс функций в них практически произволен), можно также строить структурные и классификационные правила (по автоматически формируемым обучающим примерам). При этом анализу подвергаются исходные данные различных типов: действительные числа, логические и категориальные величины. Выводимые правила принимают вид либо функций, либо циклов, либо условных конструкций.

Система включает набор математических модулей, называемых Машинами исследований (Exploration engines). В последней версии программы 4.5, выпущенной компанией «Мегапьютер» в 2000 году имеется 10 машин исследований – это:

– Поиск законов (FL – Find Laws) – эволюционное программирование

– Поиск зависимостей (FD – Find Dependencies) – универсальный препроцессор

– Классификация (CL – Classify) – на основе функции принадлежности

– Деревья решений (DT – DecisionTree) – классификация на основе деревьев решений

– Кластеризация (FC – Cluster) – многомерный кластеризатор

– PolyNet Predictor (PN) – полиномиальная нейронная сеть

– Множественная линейная регрессия (LR – Linear Regression)

– Метод "ближайшего соседа" (MB) – гибрид алгоритма Nearest Neighbor и генетических алгоритмов

– Basket Analysis (BA) – метод корзины покупателя

– Общая статистика (SS – Summary Statistics) – модуль суммарной статистики

Кластеризация

Методы кластерного анализа позволяют разделить изучаемую совокупность объектов на группы «схожих» объектов, называемых кластерами. Кластеризация в чем-то аналогична классификации, но отличается от нее тем, что для проведения анализа не требуется иметь выделенную целевую переменную. Ее удобно использовать на начальных этапах исследования, когда о данных мало что известно. Для этапа кластеризации характерно отсутствие каких-либо различий как между переменными, так и между записями. Напротив, ищутся группы наиболее близких, похожих записей. Методы автоматического разбиения на кластеры редко используются сами по себе, просто для получения групп схожих объектов. Анализ только начинается с разбиения на кластеры. Коли уж кластеры обнаружены, естественно использовать другие методы data mining, чтобы попытаться установить, а что означает такое разбиение на кластеры, чем оно вызвано.

Существует большое число методов кластеризации. Из них наибольшее распространение получили различные модификации метода K-средних. Идея метода такова. Зададим число K – число кластеров, на которые мы хотим разбить записи. Выберем K произвольных исходных центров – точек в пространстве всех переменных. Не очень критично, какие именно это будут центры, процедура выбора исходных точек отразится, главным образом, только на времени счета. Например, это могут быть первые K (различных) записей исследуемой базы данных. А дальше будем итерационно проводить одну и ту же операцию, состоящую из двух шагов.

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

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

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

Оценка качества прогноза

Из обучающей выборки по одной убираются записи. Затем для извлеченной записи делается прогноз на основе остальной выборки. Таким образом, мы получаем задачу оптимизации: получить минимальную ошибку предсказания на основе набора параметров (M, N_neigb, W). Для решения данной задачи оптимизации используются генетические алгоритмы.

Пусть мы имеем N параметров, по которым проводится оптимизация. Для каждого параметра N_i есть его оценка C. Назовем набор этих N параметров – хромосомой, а их значения – генами. Вначале мы случайно генерируем разнообразные наборы значений генов (по законам равномерного или нормального распределения), и получаем таким образом M хромосом. Далее начинается процесс генерации нового поколения хромосом. При этом существуют 3 вида генерации:

1. Элитизм. Берется некоторый процент хромосом (оценка происходит на основе критерия C) и переносится в новое поколение.
2. Мутация. Берутся случайные хромосомы и в них случайным образом меняются значения генов.
3. Скрещивание. Берут 2 случайные хромосомы и из них формируют новую, случайно выбирая часть генов из одной хромосомы, а часть из другой.

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

В нашем случае применение генетических алгоритмов наиболее оправдано, так как они не создают нового правила, не зависят от предположений о распределении, хорошо обрабатывает любые изменения в данных, однако время работы его квадратично по количеству записей, и поэтому его нельзя применять к большому объему данных. В этом случае необходимо сделать выборку из данных (порядка 2-3 тысяч записей), на которой метод отработает быстро, при этом надежность метода снижается, т.е. увеличивается вероятность упустить максимум.

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

Применительно к нашей задаче: критерий C – стандартная ошибка, хромосома – набор признаков (M,N,W). Для каждого такого набора может быть вычислена своя ошибка. Необходимо с помощью генерации поколений найти такой набор, для которого стандартная ошибка минимальна, т.е. критерий C = F(C₁,...,C_n) = F (B₁,...,B_M,N_neigb,W), где B_i – означает, используем ли мы i-ю запись для предсказания, или нет. На основании данного критерия С для каждой записи мы находим предсказание значения целевой переменной, сравниваем его с реальным значением и находим стандартную ошибку.

Таким образом, нашу задачу можно сформулировать так: есть набор параметров (M,N,W) который получается с помощью генетических алгоритмов, ему соответствует своя ошибка

Необходимо найти такой набор этих параметров, для которого ошибка err будет минимальной.

Заключение

Средства data mining предполагают оказание помощи организациям в нахождении скрытых зависимостей в данных. Получаемые модели можно использовать как для предсказания будущих значений, так и для описания текущего состояния. Результат применения методов нахождения нового знания может проявляться в широком спектре, от увеличения доходов, до уменьшения расходов. Эти исследования в настоящее время широко распространяются на различные области человеческой деятельности (медицина, управление в чрезвычайных ситуациях, промышленные предприятия). Однако, системы, реализующие алгоритмы добычи знаний из данных не могут полностью заменить аналитиков, которые хорошо понимают деловую область, сами данные, общий характер используемых аналитических методов и обладают способностью интерпретировать полученные результаты.

Список использованной литературы

1. Киселев М.В. «Алгоритмы Data Mining». Курс лекций. Компания «Мегапьютер». 2001.
2. Арсеньев С.Б. «Извлечение знаний из медицинских баз данных». Компания «Мегапьютер».
3. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах. — Открытые системы, № 4, 1997.
4. Дюк В.А. Обработка данных на ПК в примерах. – СПб: Питер, 1997.
5. Дюк В.А. «От данных к знаниям – новые возможности обработки баз данных». Санкт-Петербургский институт информатики и автоматизации Российской Академии Наук.
6. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? – Tandem Computers Inc., 1996.
7. Буров К. «Обнаружение знаний в хранилищах данных». – Открытые системы, № 5–6, 1999.
8. Геловани В.А., Бритков В.Б. Интеллектуальные методы в задачах анализа больших объемов информации для поддержки принятия решений. Проблемы управления безопасностью сложных систем: Материалы IХ международной конференции-М.: ИПУ РАН, 2001 г.
9. Arseniev S., Kiselev M., Ananyan S Regressionj-Nased Classification Methods and thier comparison with Decision Tree Algorithms – in Lectures Notes in Artificial Intelligence Springer 1263, 1997, 134-144.
10. Arseniev S., Kiselev M., Joseph Quinlan, Mark Bloom Combination of statistical data preprocessing program ARNAVAC and symbolic knowledge discovery system PolyAnalyst for prediction of right ventricular support with left ventricular assist - Proceedings of ESCTAIC-95, Palermo, 18–23 September, 1995, p.D7
11. Arseniev S., Kiselev M., Vanina L., Knyazev A. Application of Machine Discovery System PolyAnalyst to Modeling Electron Density Distribution in Ionospheric Region D Accepted for publication in Proceedings of IUGG-95 Conference; IASPEI/SEG Symposium (S13): «Application of Artificial Intelligence Computing in Geophysics»; July 12, 1995, Boulder, Colorado, USA
12. Arseniev S., Kiselev M., Classen B. Patient Ventillation Management Expert Rules derived from Ulm University Clinic Using PolyAnalyst – Knowledge Discovery System Proceedings of ECML-95 Workshop on Statistics, Machine Learning and Knowledge Discovery in Databaes, Heraklion, Greece, pp 199–203.