Обнаружение закономерностей в базах данных методами локальной геометрии
(Новая информационная технология)
Состояние вопроса
В настоящее время активно развивается рынок систем интеллектуального анализа данных — Data Mining (DM). По данным исследовательской компании Meta Group в 2000 г. его объем достигнет $800 млн.
Основные причины, способствующие распространению технологии Data Mining, следующие:
Методы DM условно разделяют на два класса:
Процедуры первого типа ограничены рамками заранее указанной гипотезы. Например, пользователь коммерческой базы данных предполагает, что факты продажи двух видов товара как-то связаны. В процессе анализа будут проверены исторические данные и сделан вывод, верна гипотеза или нет.
Проблема заключается в том, что другие возможные взаимосвязи выпадают из рассмотрения, если они изначально не очевидны для аналитика.
Системы DM второго класса самостоятельно исследуют информацию с целью обнаружения внутренних закономерностей. Полученные результаты нередко бывают неожиданными и могут привести к нетривиальным выводам. Особую ценность в обнаружении закономерностей имеют логические методы. Эти методы позволяют находить в данных логические правила, характерные для одной группы объектов (записей БД) и не характерные для других групп. Логические правила представляют собой цепочки конъюнкций:
IF{Ti(1) & Ti(2) & … & Ti(N)} THEN …,где:
С помощью логических правил решаются задачи прогнозирования, классификации, распознавания образов, сегментации БД, извлечения из данных «скрытых» знаний, интерпретации данных, установления ассоциаций в БД и др.
Логические методы работают в условиях разнородной информации. Их результаты эффективны и легко интерпретируются. Вместе с тем, главной проблемой логических методов обнаружения закономерностей является проблема перебора вариантов.
Известные методы либо искусственно ограничивают такой перебор (алгоритмы КОРА, ТЕМП), либо строят так называемые деревья решений (decision tree — методы CART, CHAID, ID3), дающие полезные результаты только в случае независимых признаков.
Предполагают, что проблему перебора можно попытаться решить путем распараллеливания символьной операции логического вывода. Но при этом отмечают, что совершенно не ясно, как осуществить такое распараллеливание. В настоящее время считается, что обнаружение цепочек конъюнкций уже для 70 бинарных признаков является нереальной задачей.
В то же время многие практические задачи включают сотни, тысячи и более таких признаков.
Характеристика новой технологии
Новая технология основывается на представлениях специальной локальной геометрии. В этой геометрии каждый объект существует в собственном локальном пространстве событий с индивидуальной метрикой. За счет свойств локальных пространств процедура поиска логических закономерностей в данных получает геометрическое истолкование.
Перебор вариантов при поиске логических закономерностей методами локальной геометрии практически отсутствует. Поиск осуществляется с помощью модифицированного аппарата линейной алгебры.
Технология дает возможность обнаруживать в данных цепочки конъюнкций, включающие десятки, сотни и тысячи совместно встречающихся событий, характерных для одной совокупности данных и не характерных для всех остальных. При этом достаточно производительности обычного персонального компьютера.
Существенным дополнением в новой технологии является использование приема «данные + шум». Этот прием заключается во введении в анализ специальных фальсификаторов — объектов, равномерно в вероятностном смысле распределенных в пространстве событий. Доля таких фальсификаторов может соответствовать и даже в два—три раза превышать долю исходной информации.
«Столкновение» данных с фальсификаторами способствует устойчивости найденных логических закономерностей. Результаты, полученные по новой технологии, выдаются в виде таблицы высказываний с указанием их характеристик (точности и полноты) и дендрограммы логических высказываний с описанием обобщающих понятий и метапонятий.
Таблица 1. Таблица высказываний
Здесь следует отметить принципиальный момент. В традиционных методах поиска логических закономерностей дерево решений (decision tree) является нисходящим и вырастает из какого либо отдельного признака. В данном случае дерево является восходящим от уже найденных логических закономерностей к более высоким уровням их обобщения.
В целом новая технология обнаружения закономерностей в базах данных имеет следующие преимущества:
Апробация
Технология обнаружения логических закономерностей методами локальной геометрии может быть рекомендована при решении следующих практических задач:
Предложения по совершенствованию и внедрению технологии
На настоящий момент технология обнаружения закономерностей в данных методами локальной геометрии реализована в полуавтоматическом варианте. Она представляет собой набор блоков обработки данных (от подготовки данных до получения результатов в виде таблиц и дендрограмм логических закономерностей), которые изолированно функционируют в разных программах — электронной таблице MS Excel и статистическом пакете STATGRAPHICS Plus for Windows.
Вместе с тем необходимые операции могут быть полностью автоматизированы и объединены в одном программном продукте. Этот программный продукт может найти применение в двух вариантах:
Здесь следует отметить прикладные области, где вероятно получение наиболее ценных результатов:
Отдельно следует отметить ценность приложения технологии обнаружения закономерностей в бизнесе. В литературе говорится о растущем интересе производителей и потребителей к этим задачам. Сообщается о резком росте прибылей клиентов за счет верно найденной, заранее неизвестной зависимости. Упоминается пример сети британских универсамов, где Data Mining применялся при анализе убытков от хищений товаров в торговых залах. Было обнаружено, что к наибольшим убыткам приводят хищения мелких «сопутствующих» товаров: ручек, батареек и т. п. Простой перенос прилавков с этими товарами ближе к расчетным узлам позволил снизить убытки на 1000 %.
Основные результаты опубликованы в книгах: