Вячеслав Дюк
Санкт-Петербургский институт информатики и автоматизации РАН
v_duke@spiiras.nw.ru

Data Mining - состояние проблемы, новые решения

1. Что такое Data Mining?
2. Кому это нужно?
   2.1. Некоторые бизнес-приложения Data Mining
   2.2. Специальные приложения
3. Типы закономерностей
4. Классы систем интеллектуального анализа данных
   4.1. Предметно-ориентированные аналитические системы
   4.2. Статистические пакеты
   4.3. Нейронные сети
   4.4. Системы рассуждений на основе аналогичных случаев
   4.5. Деревья решений (decision trees)
   4.6. Эволюционное программирование
   4.7. Генетические алгоритмы
   4.8. Алгоритмы ограниченного перебора
5. Резюме
Продолжение следует
Представление новой технологии Deep Data Mining

1. Что такое Data Mining?

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

Цель Data Mining состоит в выявлении скрытых правил и закономерностей в наборах данных. Дело в том, что человеческий разум сам по себе не приспособлен для  восприятия больших массивов разнородной информации. Человек к тому же не способен улавливать более двух-трех взаимосвязей даже в небольших выборках. Но и традиционная математическая статистика, долгое время претендовавшая на роль основного инструмента анализа данных, также нередко пасует при решении задач из реальной сложной жизни. Она оперирует усредненными характеристиками выборки, которые часто являются фиктивными величинами (типа средней температуры пациентов по больнице, средней высоты дома на улице, состоящей из дворцов и лачуг и т.п.). Поэтому методы математической статистики оказываются полезными главным образом для проверки заранее сформулированных гипотез (verification-driven data mining).

Современные технологии Data Mining (discovery-driven data mining) перелопачивают информацию с целью автоматического поиска шаблонов (паттернов), характерных для каких-либо фрагментов неоднородных многомерных данных. В отличие от оперативной аналитической обработки данных (online analytical processing, OLAP) в Data Mining бремя формулировки гипотез и выявления необычных (unexpected) шаблонов переложено с человека на компьютер.
   Таблица 1. Примеры формулировок задач при использовании методов OLAP и Data Mining [2]

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

 2. Кому это нужно?

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

2.1. Некоторые бизнес-приложения Data Mining

Розничная торговля

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

• анализ покупательской корзины (анализ сходства) предназначен для выявления товаров, которые покупатели стремятся приобретать вместе. Знание покупательской корзины необходимо для улучшения рекламы, выработки стратегии создания запасов товаров и способов их раскладки в торговых залах.
• исследование временных шаблонов помогает торговым предприятиям принимать решения о создании товарных запасов. Оно дает ответы на вопросы типа "Если сегодня покупатель приобрел видеокамеру, то через какое время он вероятнее всего купит новые батарейки и пленку?"
• создание прогнозирующих моделей дает возможность торговым предприятиям узнавать характер потребностей различных категорий клиентов с определенным поведением, например, покупающих товары известных дизайнеров или посещающих распродажи. Эти знания нужны для разработки точно направленных, экономичных мероприятий по продвижению товаров.

Банковское дело

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

• выявление мошенничества с кредитными карточками. Путем анализа прошлых транзакций, которые впоследствии оказались мошенническими, банк способен выявить некоторые стереотипы такого мошенничества. Например, можно установить, что одним из предупреждающих сигналов служат многочисленные транзакции в магазинах бытовой электроники в течение короткого периода времени. Полученное знание банк может использовать в своих действующих системах, не разрешая подтверждение транзакции, совпадающей со стереотипом мошенничества, без предварительной беседы с покупателем.
• сегментация клиентов. Разбивая клиентов на различные категории, банки могут сделать свою маркетинговую политику более целенаправленной и результативной, предлагая различные виды услуг разным группам клиентов. Например, банк может предлагать одну совместную (affinity) карточку клиентам, которые часто путешествуют, и другую — клиентам, которые всегда вовремя оплачивают свои счета за покупки по кредитным карточкам. Сегментацию полезно также использовать для определения, какие конкретно отделения с наибольшей вероятностью получат прибыль от отдельных рекламных акций.
• прогнозирование изменений клиентуры. Data Mining помогает банкам строить прогнозные модели ценности своих клиентов, и соответственным образом обслуживать каждую категорию. Для этого банк выясняет характер потребностей своих сегодняшних прибыльных клиентов и с помощью методов Data Mining определяет общие черты, которыми они обладали несколько лет назад. Затем он выявляет клиентов, имеющих эти черты сегодня, считая их вероятными прибыльными клиентами в ближайшем будущем. Банк может включить указанных клиентов в целевые программы удерживания клиентов, например, предлагая специальные сделки или вводя штрафные санкции за отказ от дальнейших услуг.

Телекоммуникации

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

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

Страхование

Страховые компании в течение многих лет накапливают большие объемы данных. Здесь большое поле деятельности для методов Data Mining:

• выявление мошенничества. Страховые компании могут снизить уровень мошенничества, отыскивая определенные стереотипы в заявлениях о выплате страхового возмещения, характеризующих взаимоотношения между юристами, врачами и заявителями в случаях, когда требуемая сумма достаточно высока, например при возмещении ущерба;
• разработка продуктов. Data Mining даст возможность выявить наиболее выгодные комбинации категорий клиентов, вариантов полисов и их покрытия. Знание таких комбинаций необходимо для разработки новых продуктов и более точной "настройки" существующих продуктов для продажи в будущем;
• анализ риска. Путем выявления сочетаний факторов, связанных с оплаченными заявлениями, страховщики могут уменьшить свои потери по обязательствам. Известен случай, когда в США крупная страховая компания проверила заявления, по которым были выплачены значительные суммы за последние два года. При этом обнаружилось, что суммы, выплаченные по заявлениям людей, состоящих в браке, вдвое превышает суммы по заявлениям одиноких людей. Компания отреагировала на это новое знание пересмотром своей общей политики предоставления скидок семейным клиентам.

Другие приложения в бизнесе

Data Mining  может применяться во множестве других областей:

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

2.2. Специальные приложения

• Медицина
  Известно много экспертных систем для постановки медицинских диагнозов. Они построены главным образом на основе правил, описывающих сочетания различных симптомов различных заболеваний. С помощью таких правил узнают не только, чем болен пациент, но и как нужно его лечить. Правила помогают выбирать средства медикаментозного воздействия, определять показания — противопоказания, ориентироваться в лечебных процедурах, создавать условия наиболее эффективного лечения, предсказывать исходы назначенного курса лечения и т. п. Технологии Data Mining позволяют обнаруживать в медицинских данных указаные правила.

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

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

Можно привести еще много примеров различных областей знания, где методы Data Mining играют ведущую роль. Особенность этих областей заключается в их сложной системной организации. Они относятся главным образом к надкибернетическому уровню организации систем [3], закономерности которого не могут быть достаточно точно описаны на языке статистических или иных аналитических математических моделей [4]. Данные в указанных областях неоднородны, гетерогенны, нестационарны и часто отличаются высокой размерностью.

 3. Типы закономерностей

Выделяют пять стандартных типов закономерностей, которые позволяют выявлять  методы Data Mining:

• ассоциация
• последовательность
• классификация
• кластеризация
• прогнозирование

Ассоциация имеет место в том случае, если несколько событий связаны друг с другом. Например, исследование, проведенное в супермаркете, может показать, что 65% купивших кукурузные чипсы берут также и "кока-колу", а при наличии скидки за такой комплект "колу" приобретают в 85% случаев. Располагая сведениями о подобной ассоциации, менеджерам легко оценить, насколько действенна предоставляемая скидка.

Если существует цепочка связанных во времени событий, то говорят о последовательности. Так, например, после покупки дома в 45% случаев в течение месяца приобретается и новая кухонная плита, а в пределах двух недель 60% новоселов обзаводятся холодильником.

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

Кластеризация отличается от классификации тем, что сами группы заранее не заданы. С помощью кластеризации средства Data Mining самостоятельно выделяют различные однородные группы данных.

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

 4. Классы систем интеллектуального анализа данных

В основу предлагаемой классификации положена работа [5].

4.1. Предметно-ориентированные аналитические системы

Предметно-ориентированные аналитические системы очень разнообразны. Наиболее широкий подкласс таких систем, получивший распространение в области исследования финансовых ранков, носит название "технический анализ". Он представляет собой совокупность нескольких десятков методов прогноза динамики цен и выбора оптимальной структуры инвестиционного портфеля, основанных на различных эмпирических моделях динамики рынка. Эти методы могут быть весьма просты ( например, методы, использующие вычитание трендового значения), но могут иметь достаточно оригинальную математическую основу (например, теорию фракталов) . Поскольку чаще всего теория "зашита" в эти системы, а не выводится на основании истории рынка, то требования статистической значимости выводимых моделей и возможности их интерпретации для них не имеют смысла. На рынке имеется  множество программ этого класса. Как правило, они довольно дешевы (обычно $300–1000).

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

Хотя последние версии почти всех известных статистических пакетов включают наряду с традиционными статистическими методами также элементы Data Mining, основное внимание в них уделяется все же классическим методикам — корреляционному, регрессионному, факторному анализу и другим. Самый последний детальный обзор пакетов для статистического анализа приведен на странице  http://is1.cemi.rssi.ru/ruswin/index.htm. Недостатком систем этого класса считают требование к специальной подготовке пользователя. Также отмечают, что  мощные современные статистические пакеты являются слишком "тяжеловесными" для массового применения в финансах и бизнесе. К тому же часто эти системы весьма дороги — от $1000 до $8000.
Есть еще более серьезный принципиальный недостаток статистических пакетов, ограничивающий их применение в Data Mining. Большинство методов, входящих в состав пакетов опираются на статистическую парадигму, в которой главными фигурантами служат усредненные характеристики выборки. А эти характеристики при исследовании реальных сложных жизненных феноменов часто являются фиктивными величинами. В следующих разделах будут специально более подробно обсуждены эти вопросы.
В качестве примеров наиболее мощных и распространенных статистических пакетов можно назвать SAS (компания SAS Institute), SPSS (SPSS), STATGRAPICS, STATISTICA, STADIA и другие.
 

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

Это большой класс  систем,  архитектура которых пытается имитировать построение нервной ткани из нейронов. В одной из наиболее распространенных архитектур, многослойном перцептроне с обратным распространением ошибки, эмулируется работа нейронов в составе иерархической сети, где каждый нейрон более высокого уровня соединен своими входами с выходами нейронов нижележащего слоя. На нейроны самого нижнего слоя подаются значения входных параметров, на основе которых нужно принимать какие-то решения, прогнозировать развитие ситуации и т. д. Эти значения рассматриваются как сигналы, передающиеся в вышележащий слой, ослабляясь или усиливаясь в зависимости от числовых значений (весов), приписываемых межнейронным связям. В результате на выходе нейрона самого верхнего слоя вырабатывается некоторое значение, которое рассматривается как ответ, реакция всей сети на введенные значения входных параметров. Для того чтобы сеть можно было применять в дальнейшем, ее прежде надо "натренировать" на полученных ранее данных, для которых известны и значения входных параметров, и правильные ответы на них. Эта тренировка состоит в подборе весов межнейронных связей, обеспечивающих наибольшую близость ответов сети к известным правильным ответам.
Основным недостатком нейросетевой парадигмы является необходимость иметь очень большой объем обучающей выборки. Другой существенный недостаток заключается в том, что даже натренированная нейронная сеть представляет собой черный ящик. Знания, зафиксированные как веса нескольких сотен межнейронных связей, совершенно не поддаются анализу и интерпретации человеком (известные попытки дать интерпретацию структуре настроенной нейросети выглядят неубедительными – система “KINOsuite-PR”).
Примеры нейросетевых систем — BrainMaker (CSS), NeuroShell (Ward Systems Group), OWL (HyperLogic). Стоимость их довольно значительна: $1500–8000.

4.4. Системы рассуждений на основе аналогичных случаев

Идея систем case based reasoning — CBR — на первый взгляд крайне проста. Для того чтобы сделать прогноз на будущее или выбрать правильное решение, эти системы находят в прошлом близкие аналоги наличной ситуации и выбирают тот же ответ, который был для них правильным. Поэтому этот метод еще называют методом "ближайшего соседа" (nearest neighbour).
Системы CBR показывают очень хорошие результаты в самых разнообразных задачах. Главным их минусом считают то, что они вообще не создают каких-либо моделей или правил, обобщающих предыдущий опыт, — в выборе решения они основываются на всем массиве доступных исторических данных, поэтому невозможно сказать, на основе каких конкретно факторов CBR системы строят свои ответы.
Другой минус заключается в произволе, который допускают системы CBR при выборе меры "близости". От этой меры самым решительным образом зависит объем множества прецедентов, которые нужно хранить в памяти для достижения удовлетворительной классификации или прогноза.
Примеры систем, использующих CBR, — KATE tools (Acknosoft, Франция), Pattern Recognition Workbench (Unica, США).

4.5. Деревья решений (decision trees)

Деревья решения являются одним из наиболее популярных подходов к решению задач Data Mining. Они создают иерархическую структуру классифицирующих правил типа "ЕСЛИ... ТО...", имеющую вид дерева (это похоже на определитель видов из ботаники или зоологии). Для того чтобы решить, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Вопросы имеют вид "значение параметра A больше x?". Если ответ положительный, осуществляется переход к правому узлу следующего уровня, если отрицательный — то к левому узлу; затем снова следует вопрос, связанный с соответствующим узлом.
Популярность подхода связана с наглядностью и понятностью. Но очень остро для деревьев решений стоит проблема значимости. Дело в том, что отдельным узлам на каждом новом построенном уровне дерева соответствует все меньшее и меньшее число записей данных — дерево дробит данные на большое количество частных случаев. Чем больше этих частных случаев, чем меньше обучающих примеров попадает в каждый такой частный случай, тем менее уверенной становится их классификация. Если построенное дерево слишком "кустистое" — состоит из неоправданно большого числа мелких веточек — оно не будет давать статистически обоснованных ответов. Как показывает практика, в большинстве систем, использующих деревья решений, эта проблема не находит удовлетворительного решения. Кроме того, общеизвестно, и это легко показать, что деревья решений дают полезные результаты только в случае независимых признаков. В противном случае они лишь создают иллюзию логического вывода.
Довольно много систем используют этот метод. Самыми распространенными являются See5/С5.0 (RuleQuest, Австралия), Clementine (Integral Solutions, Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США). Стоимость этих систем варьируется от 1 до 10 тыс. долл.

4.6. Эволюционное программирование

Проиллюстрируем современное состояние данного подхода на примере системы PolyAnalyst. В данной системе гипотезы о виде зависимости целевой переменной от других переменных формулируются в виде программ на некотором внутреннем языке программирования. Процесс построения программ строится как эволюция в мире программ (этим подход немного похож на генетические алгоритмы). Когда система находит программу, достаточно точно выражающую искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построенных таким образом дочерних программ те, которые повышают точность. Таким образом система "выращивает" несколько генетических линий программ, которые конкурируют между собой в точности выражения искомой зависимости. Специальный транслирующий модуль системы PolyAnalyst переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и пр.), делая их легкодоступными. Для того чтобы сделать полученные результаты еще понятнее для пользователя-нематематика, имеется богатый арсенал разнообразных средств визуализации обнаруживаемых зависимостей. Для контроля статистической значимости выводимых зависимостей применяется набор современных методов, например рандомизированное тестирование.
Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в форме функций какого-то определенного вида. Например, в одном из наиболее удачных алгоритмов этого типа — методе группового учета аргументов (МГУА) зависимость ищут в форме полиномов. В настоящее время из продающихся в России систем МГУА реализован в системе NeuroShell компании Ward Systems Group.

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

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

Генетические алгоритмы имеют ряд недостатков. Критерий отбора хромосом и сама процедура являются эвристическими и далеко не гарантируют нахождения “лучшего” решения. Как и в реальной жизни, эволюцию может “заклинить” на какой-либо непродуктивной ветви. И, наоборот, можно привести примеры, как два неперспективных родителя, которые будут исключены из эволюции генетическим алгоритмом, оказываются способными произвести высокоэффективного потомка. Это особенно становится заметно при решении высокоразмерных задач со сложными внутренними связями.

Примером может служить система GeneHunter фирмы Ward Systems Group. Его стоимость — около $1000.

4.8. Алгоритмы ограниченного перебора

Алгоритмы ограниченного перебора были предложены в середине 60-х годов М.М. Бонгардом для поиска логических закономерностей в данных. С тех пор они продемонстрировали свою эффективность при решении множества задач из самых различных областей.

Эти алгоритмы вычисляют частоты комбинаций простых логических событий в подгруппах данных. Примеры простых логических событий: X = a; X < a; X > a; a < X < b и др., где X — какой либо параметр, “a” и “b” — константы. Ограничением служит длина комбинации простых логических событий (у М. Бонгарда она была равна 3). На основании анализа вычисленных частот делается заключение о полезности той или иной комбинации для установления ассоциации в данных, для классификации, прогнозирования и пр.

Наиболее ярким современным представителем этого подхода является система WizWhy предприятия WizSoft. Хотя автор системы Абрахам Мейдан не раскрывает специфику алгоритма, положенного в основу работы WizWhy, по результатам тщательного тестирования системы были сделаны выводы о наличии здесь ограниченного перебора  (изучались результаты, зависимости времени их получения от числа анализируемых параметров и др.).

Автор WizWhy утверждает, что его система обнаруживает ВСЕ логические правила IF ... THEN в данных. На самом деле это, конечно, не так. Во-первых, максимальная длина комбинации в правиле IF ... THEN в системе WizWhy равна 6, и, во-вторых, с самого начала работы алгоритма производится эвристический поиск простых логических событий, на которых потом строится весь дальнейший анализ. Поняв эти особенности WizWhy, нетрудно было предложить простейшую тестовую задачу, которую система не смогла вообще решить. Другой момент — система выдает решение за приемлемое время только для сравнительно небольшой размерности данных (не более 20).

Тем не менее, система WizWhy является на сегодняшний день одним из лидеров на рынке продуктов Data Mining. Это не лишено оснований. Система постоянно демонстрирует более высокие показатели при решении практических задач, чем все остальные алгоритмы. Стоимость системы около $ 4000, количество продаж — 30000.

5. Резюме

Рынок систем Data Mining активно развивается. В этом развитиии принимают участие практически все крупнейшие корпорации (см. например http://www.kdnuggets.com). В частности, Microsoft непосредственно руководит большим сектором данного рынка (издает специальный журнал, проводит конференции, разрабатывает собственные продукты).

На рынке систем Data Mining выделяются два направления: 1) массовый продукт для бизнес-приложений; 2) инструменты для проведения уникальных исследований (генетика, химия, медицина и пр.). Стоимость массового продукта от $1000 до $10000. Количество инсталляций массовых продуктов, по-видимому, может достигать десятков тысяч.

Среди систем Data Mining можно различить два самостоятельных обширных класса: 1) нейросетевые алгоритмы; 2) алгоритмы поиска IF ... THEN логических правил.

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

С помощью логических правил IF ... THEN решаются задачи прогнозирования, классификации, распознавания образов, сегментации БД, извлечения из данных “скрытых” знаний, интерпретации данных, установления ассоциаций в БД и др. Логические методы работают в условиях разнородной информации. Их результаты эффективны и легко интерпретируются.

Главной и проблемой логических методов обнаружения закономерностей является проблема перебора вариантов за приемлемое время. Известные методы либо искусственно ограничивают такой перебор (алгоритмы КОРА, WizWhy), либо строят деревья решений (алгоритмы CART, CHAID, ID3, See5, Sipina и др.), дающие полезные результаты только в случае независимых признаков.

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

Вышесказанное подтверждает актуальность разработки новых подходов и алгоритмов Data Mining в классе IF ... THEN правил. Основные требования к новым подходам:

1) способность находить логические правила неограниченной сложности в данных высокой размерности;
2) умение обобщать найденные логические правила и осуществлять поиск их оптимальной композиции.

Продолжение следует

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

Представление новой технологии Deep Data Mining

• Новая технология Deep Data Mining (DDM) основывается на представлениях специальной локальной геометрии. В этой геометрии каждый объект существует в собственном локальном пространстве событий с индивидуальной метрикой. За счет свойств локальных пространств процедура поиска логических закономерностей в данных получает геометрическое истолкование.
• Перебор вариантов при поиске логических закономерностей методами локальной геометрии практически отсутствует. Поиск осуществляется с помощью модифицированного аппарата линейной алгебры.
• Технология DDM дает возможность обнаруживать в данных IF ... THEN правила, включающие десятки, сотни и тысячи совместно встречающихся логических событий, характерных для одной совокупности данных и не характерных для всех остальных. Эффективность результатов близка к потенциально возможной эффективности поиска правил путем полного перебора
• Существенным дополнением в новой технологии DDM является использование приема “данные + шум”. Этот прием заключается во введении в анализ специальных фальсификаторов — объектов, равномерно в вероятностном смысле распределенных в пространстве событий. Доля таких фальсификаторов может соответствовать и даже в два—три раза превышать долю исходной информации. “Столкновение” данных с фальсификаторами способствует устойчивости найденных логических закономерностей.
• Результаты, полученные по новой технологии DDM, выдаются в виде таблицы IF ... THEN правил с указанием их характеристик (точности и полноты) и дендрограммы полученных правил с описанием обобщающих понятий и метапонятий.

В целом новая технология DDM для обнаружения закономерностей в базах данных имеет следующие преимущества:

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

Отмеченные преимущества подтверждаются результами сравнительного тестирования совместно с наиболее популярными системами – лидерами в области Data Mining.

Литература

1. Н. Кречетов. Продукты для интеллектуального анализа данных. - Рынок программных средств, N14-15_97, c.32-39.
2. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? - Tandem Computers Inc., 1996.
3. Boulding K. E. General Systems Theory - The Skeleton of Science//Management Science, 2, 1956.
4. Гик Дж., ван. Прикладная общая теория систем. - М.: Мир, 1981.
5. М.Киселев, Е.Соломатин. Средства добычи знаний в бизнесе и финансах. - Открытые системы, № 4, 1997, с.41-44.