Data Mining - oт сырых данных к полезным решениям

Data Mining - oт сырых данных к полезным решениям

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

• Какие товары надо предлагать данному покупателю?
• Какова вероятность того, что данный сектор потенциальных клиентов отреагирует на рекламную кампанию?
• Можно ли выработать оптимальную стратегию игры на бирже?
• Как оценить риск выдачи кредита данному клиенту банка?
• Можно ли повысить качество медицинской диагностики?
• Как прогнозировать пиковые нагрузки в телефонных или энергетических сетях?
• В чем причины брака в производстве?

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

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

Система PolyAnalyst

Компания Мегапьютер производит и предлагает на рынке семейство продуктов для Data mining - PolyAnalyst On-line Tutor. Система PolyAnalyst предназначена для автоматического анализа числовых и текстовых данных с целью обнаружения в них ранее неизвестных, нетривиальных, практически полезных и доступных пониманию закономерностей, необходимых для принятия оптимальных решений в бизнесе и в других областях человеческой деятельности.

В настоящее время PolyAnalyst является одной из самых мощных систем Data Mining в мире, реализованных для Intel платформ и операционных систем Microsoft Windows. Аналогичные системы Data Mining таких ведущих производителей, как IBM (Intelligent Miner, Data Miner), Silicon Graphics (SGI Miner), Integral Solutions (Clementine), SAS Institute (SAS) работают на средних и больших машинах и стоят десятки и даже сотни тысяч долларов. Благодаря уникальной технологии "Эволюционного программирования", и другим инновационным математическим алгоритмам, PolyAnalyst сочетает в себе высочайшую производительность "больших систем" с низкой стоимостью, присущей программам для Windows.

PolyAnalyst - один из немногих коммерческих продуктов, в котором реализованы не только методы анализа числовых данных, но и алгоритмы Text Mining - анализа текстовой информации. В течение своей более, чем 10-летней истории, пакет непрерывно развивается, компания-производитель добавляет новую функциональность, новые математические модули, планируется портация системы на Unix платформы.

PolyAnalyst получил широкое распространение в мире. Более 500 инсталляций в 20 странах мира, среди пользователей системы внушительный список составляют крупнейшие мировые корпорации: Boeing, 3M, Chase Manhattan Bank, Dupont, Siemens и другие. PolyAnalyst - универсальная система Data Mining, она с успехом применяется в различных областях: в решении бизнес-задач (direct marketing, cross-selling, customer retention), в социологических исследованиях, в прикладных научных и инженерных задачах, в банковском деле, в страховании и медицине.

Архитектура системы

По своей природе, PolyAnalyst является клиент/серверным приложением. Пользователь работает с клиентской программой PolyAnalyst Workplace. Математические модули выделены в серверную часть - PolyAnalyst Knowledge Server. Такая архитектура предоставляет естественную возможность для масштабирования системы: от однопользовательского варианта до корпоративного решения с несколькими серверами. PolyAnalyst написан на языке С++ с использованием спецификации Microsoft's COM (ActiveX). Эта спецификация устанавливает стандарт коммуникации между программными компонентами. Математические модули (Exploration Engines) и многие другие компоненты PolyAnalyst выделены в отдельные динамические библиотеки и доступны из других приложений. Это дает возможность интегрировать математику PolyAnalyst в существующие ИС, например, в CRM или ERP системы.

Наверх

PolyAnalyst Workplace - лаборатория аналитика

Workplace - это клиентская часть программы, ее пользовательский интерфейс. Workplace представляет собой полнофункциональную среду для анализа данных. Развитые возможности манипулирования с данными, богатая графика для представления данных и визуализации результатов, мастера создания объектов, сквозная логическая связь между объектами, язык символьных правил, интуитивное управление через drop-down и pop-up меню, подробная контекстная справка - вот только несколько основных черт пользовательского интерфейса программы.

Единицей Data Mining исследования в PolyAnalyst является "проект". Проект объединяет в себе все объекты исследования, дерево проекта, графики, правила, отчеты итд. Проект сохраняется в файле внутреннего формата системы. Отчеты исследований представляются в формате HTML и доступны через Интернет.

Аналитический инструментарий PolyAnalyst

Версия PolyAnalyst 4.6 включает 18 математических модулей, основанных на различных алгоритмах Data и Text Mining. Большинство из этих алгоритмов являются Know-How компании Мегапьютер и не имеют аналогов в других системах. Алгоритмы анализа данных можно объединить в группы по их функциональному назначению: моделирование, прогнозирование, кластеризация, классификация, текстовый анализ. Ниже дается краткая характеристика математическим алгоритмам PolyAnalyst.

Модули для построения числовых моделей и прогноза числовых переменных

Модуль Find Laws (FL) - построитель моделей

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

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

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

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

Stepwise Linear Regression (LR) - пошаговая многопараметрическая линейная регрессия

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

Алгоритм работает очень быстро и применим для построения линейных моделей на смешенных типах данных.

Memory based reasoning (MR) - метод "ближайших соседей"

В системе PolyAnalyst используется модификация известного алгоритма "метод ближайших соседей". Идея метода очень проста; для предсказания значения целевой переменной для данной записи, в обучающей таблице с историческими данными, находятся "похожие" записи, для которых известны значения целевой переменной, и вычисляется среднее из этих значений, которое и считается прогнозом. На практике реализация этой идеи встречается с тремя основными трудностями: 1. что считать мерой близости записей?, 2. сколько записей брать для усреднения?, какой метод усреднения использовать, обычное или взвешенное усреднение? В системе PolyAnalyst оптимизация этих параметров производится на основе генетических алгоритмов. В этом и заключается отличие данной реализации алгоритма "ближайших соседей" от известных аналогов. Алгоритм MR используется для предсказания значений числовых переменных и категориальных переменных, включая текстовые (string data type), а также для классификации на два или несколько классов.

Алгоритмы кластеризации

Find Dependecies (FD) - N-мерный анализ распределений

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

Алгоритм работает очень быстро и способен обрабатывать большие объемы данных. Его можно использовать как препроцессор для алгоритмов FL, PN, LR, так как он уменьшает пространство поиска, а также как фильтр отскочивших точек или в обратной постановке, как детектор исключений. FD создает правило табличного вида, однако как и все правила PolyAnalyst оно может быть вычислено для любой записи таблицы.

Find Clusters (FC) - N-мерный кластеризатор

Этот метод применяется тогда, когда надо выделить в некотором множестве данных компактные типичные подгруппы (кластеры), состоящие из близких по своим характеристикам записей. Причем заранее может быть неизвестно какие переменные нужно использовать для такого разбиения. Алгоритм FC сам определяет набор переменных, для которых разбиение наиболее значимо. Результатом работы алгоритма является описание областей (диапазонов значений переменных), характеризующих каждый обнаруженный кластер и разбиение исследуемой таблицы на подмножества, соответствующие кластерам. Если данные являются достаточно однородными по всем своим переменным и не содержат "сгущений" точек в каких-то областях, этот метод не даст результатов. Надо отметить, что минимальное число обнаруживаемых кластеров равно двум - сгущение точек только в одном месте в данном алгоритме не рассматривается как кластер. Кроме того, этот метод в большей степени, чем остальные предъявляет требования к наличию достаточного количества записей в исследуемой таблице, а именно, минимальное количество записей в таблице, в которой может быть обнаружено N кластеров, равно (2N-1)4.

Алгоритмы классификации

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

Classify (CL) - классификатор на основе нечеткой логики

Алгоритм CL предназначен для классификации записей на два класса. В основе его работы лежит построение так называемой функции принадлежности и нахождения порога разделения на классы. Функция принадлежности принимает значения от окрестности 0 до окрестности 1. Если возвращаемое значение функции для данной записи больше порога, то эта запись принадлежит к классу "1", если меньше, то классу "0" соответственно. Целевая переменная для этого модуля должна быть логического типа.

Discriminate (DS) - Дикриминация

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

Decision Tree (DT) - дерево решений

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

В системе PolyAnalyst, реализован алгоритм, основанный на критерии максимизации взаимной информации (information gain). То есть для расщепления выбирается независимая переменная, несущая максимальную (в смысле Шеннона) информацию о зависимой переменной. Этот критерий в отличие от многих критериев, применяемых в других системах Data Mining, имеет ясную интерпретацию и дает разумные результаты при самых разнообразных статистических параметрах изучаемых данных. Алгоритм DT является одним из самых быстрых в PolyAnalyst.

Decision Forest (DF) - леса решений

В случае, когда зависимая переменная может принимать большое количество разных значений, применение метода деревьев решений становится неэффективным. В такой ситуации в системе PolyAnalyst применяется метод, называемый лесом решений (decision forest). При этом строится совокупность деревьев решений - по одному для каждого различного значения зависимой переменной. Результатом прогноза, основанном на лесе решений, является то значение зависимой переменной, для которой соответствующее дерево дает наиболее вероятную оценку.

Алгоритмы ассоциации

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

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

Transactional Basket Analysis (TB) - транзакционный анализ "корзины"

Transactional Basket Analysis - это модификация алгоритма BA, применяемый для анализа очень больших данных, что не редкость для этого типа задач. Он предполагает, что каждая запись в базе данных соответствует одной транзакции, а не одной корзине (набору купленных за одну операцию товаров). На основе этого алгоритма компания "Мегапьютер" отдельный продукт - X-SellAnalyst, предназначенный для on-line рекомендации продуктов в Интернет магазинах.

Модули текстового анализа.

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

Text Analysis (ТА) - текстовый анализ

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

Text Categorizer (TC) - каталогизатор текстов

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

Link Terms (LT) - связь понятий

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

Визуализация

В PolyAnalyst имеется богатый набор инструментов для графического представления и анализа данных и результатов исследований. Данные могут представляться в различных зрительных форматах: гистограммах , двумерных, псевдо- и реальных трехмерных графиках.

Найденные в процессе Data Mining зависимости могут быть представлены как интерактивные графики со слайдерами для изменения значений представленных на них переменных. Эта особенность позволяет пользователю графически моделировать результаты. Имеется набор специальных графиков, широко применяемых в бизнесе, это так называемые Lift, Gain charts, которые используются для графической оценки качества классификационных моделей и выбора оптимального числа контактов (prospects). Кроме этого в последнюю версию программы включен новый визуальный метод Data Mining - анализ связей.

Link Analysis (LA) - анализ связей

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

Symbolic Rule Language (SRL) - язык символьных правил

SRL - это универсальный алгоритмический язык PolyAnalyst, который используется для символьного представления автоматически найденных системой в процессе Data Mining правил, а также для создания пользователем своих собственных правил. На языке SRL можно выразить широкий спектр математических конструкций, используя алгебраические операции, большой набор встроенных функций, операции с датами и временем, логические и условные конструкции. Для удобства написания выражений на SRL в программе предусмотрен маcтер создания правил.

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

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

Процесс производства внутренних программ организуется как эволюция в пространстве программ, в некотором роде напоминающая генетические алгоритмы. Когда система находит перспективную гипотезу, описывающую исследуемую зависимость достаточно хорошо по целому ряду критерий, в работу включается механизм так называемых "обобщенных преобразований" (GT-search). С помощью этого механизма в "хорошую" программу вводятся незначительные модификации, не ухудшающие ее качество, и производится отбор лучшей дочерней программы. К новой популяции затем опять применяются механизмы синтеза новых программ, и этот процесс рекурсивно повторяется. Таким образом, система создает некоторое число генетических линий программ, конкурирующих друг с другом по точности, статистической значимости и простоте выражения зависимости.

Специальный модуль непрерывно преобразует "лучшую" на данный момент программу с внутреннего представления во внешний язык PolyAnalyst - язык символьных правил (Symbolic Rule Language), понятный человеку: математические формулы, условные конструкции и так далее. Это позволяет пользователю понять суть полученной зависимости, контролировать процесс поиска, а также получать графическую визуализацию результатов. Контроль статистической значимости полученных результатов осуществляется целым комплексом эффективных и современных статистических методов, включая методы рандомизированного тестирования.

Общесистемные характеристики PolyAnalyst

Типы данных

PolyAnalyst работает с разными типами данных. Это - числа, булевы переменные (yes/no), категориальные переменные, текстовые строки, даты, а также свободный английский текст.

Доступ к данным

PolyAnalyst может получать исходные данные из различных источников. Это: текстовые файлы с разделителем запятая (.csv), файлы Microsoft Excel 97/2000, любая ODBC- совместимая СУБД, SAS data files, Oracle Express, IBM Visual Warehouse.

Поддержка OLE DB for Data Mining

Версия 4.6 PolyAnalyst поддерживает спецификацию Microsoft OLE DB for Data Mining (Version 1.0). При выполнении исследований для большинства математических модулей (LR, FD, CL, FC, DT, DF, FL,PN, BA, TB) можно создавать так называемые "Mining Models" (MM). После завершения анализа эти модели можно применять к внешним данным через стандартные интерфейсы OLE DB или ADO из других программ или скриптов поддерживающих создание ADO или COM-объектов. Применение модели осуществляется при помощи выполнения SQL-команд (Расширение SQL for DM). Mining Models можно также экспортировать в PMML.

В дальнейших планах развития программы намечается обеспечить интеграцию "PolyAnalyst DataMining Provider" с Microsoft Analysis Services(в составе SQL Server 2000 )

In-place Data Mining

PolyAnalyst поддерживает запуск исследований на внешних данных через OLE DB интерфейсы при без загрузки этих данных в проект PA. При выполнении исследования PolyAnalyst получает данные порциями через выполнение SQL запросов к внешним источникам данных. Это позволяет преодолеть ограничения памяти при исследовании больших массивов данных.

PolyAnalyst Scheduler - режим пакетной обработки

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

Семейство продуктов PolyAnalyst

Продукт	Конфигурация системы
Локальные продукты
PolyAnalyst 4.6, однопользовательская версия	Математические модули: FL, FD, PN, FC, BA, ТВ, MB, CL, DS, DT, DF, LR, LA, TA, TC, LT, SS. Пакетная обработка, поддержка OLE DB. Платформа - MS Windows NT/2000/XP
PolyAnalyst 3.5 Professional (русс.)	Математические модули: FL, FD, PN, FC, CL, DS, LR, SS. Платформа - MS Windows NT/2000/XP
PolyAnalyst 3.5 Power (русс.)	Математические модули: FD, PN, FC, CL, DS, LR, SS. Платформа - MS Windows 98/NT/2000/XP
PolyAnalyst 3.5 Lite - студенческая версия (русс.)	Математические модули: FD, FC, CL, DS, LR, SS. Платформа - MS Windows 98/NT/2000/XP
Сетевые продукты
PolyAnalyst Knowledge Server 4.6, сетевая версия	Математические модули: FL, FD, PN, FC, BA, ТВ, MB, CL, DS, DT, DF, LR, LA, TA, TC, LT, SS. Пакетная обработка, поддержка OLE DB, In-Place Data Mining.Серверная часть-MS Windows NT/2000/XP server, клиентская часть - MS Windows 98/NT/2000/XP. Клиент/серверная версия системы
Средства разработки
PolyAnalyst COM - SDK для создания собственных приложений для Data Mining	Набор COM-объектов, библиотеки, документация для разработчиков

Схема лицензирования PolyAnalyst

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

С 2003 года для российских заказчиков действуют специальных цены на однопользовательскую (stand-alone) версию системы, которые значительно ниже мировых. Эта акция компании-производителя направлена на продвижение технологий Data Mining на отечественный рынок. Мегапьютер также проводит активную образовательную программу, в рамках которой для образовательных учреждений действуют дополнительные скидки.

PolyAnalyst COM SDK - средство разработки, а также клиент/серверная конфигурация системы - PolyAnalyst Knowledge Server лицензируются на отдельных условиях.