Алгоритмы ассоциации
Market Basket Analysis (BA) - метод анализа "корзины покупателя"
Название этого метода происходит от задачи определения вероятности, какие товары покупаются совместно. Однако реальная область его применения значительно шире. Например, продуктами можно считать страницы в Интернете, или те или иные характеристики клиента, или ответы респондентов в социологических и маркетинговых исследованиях и т.д. Алгоритм BA получает на вход бинарную матрицу, в которой строка - это одна корзина (кассовый чек, например), а столбцы заполнены логическими 0 и 1, обозначающими наличие или отсутствие данного признака (товара). На выходе формируются кластеры совместно встречаемых признаков с оценкой их вероятности и достоверности. Кроме этого, формируются ассоциативные направленные правила типа: если признак "А", то с такой-то вероятностью еще и признак "В" и еще признак "С". Алгоритм ВА в PolyAnalyst работает исключительно быстро и способен обрабатывать огромные массивы данных.
Transactional Basket Analysis (TB) - транзакционный анализ "корзины"
Transactional Basket Analysis - это модификация алгоритма BA, применяемый для анализа очень больших данных, что не редкость для этого типа задач. Он предполагает, что каждая запись в базе данных соответствует одной транзакции, а не одной корзине (набору купленных за одну операцию товаров). На основе этого алгоритма компания "Мегапьютер" создала отдельный продукт - X-SellAnalyst, предназначенный для on-line рекомендации продуктов в Интернет-магазинах.
Алгоритмы классификации
В пакете PolyAnalyst имеется богатый инструментарий для решения задач классификации, т.е. для нахождения правил отнесения записей к одному из двух или к одному из нескольких классов.
Classify (CL) - классификатор на основе нечеткой логики
Алгоритм CL предназначен для классификации записей на два класса. В основе его работы лежит построение так называемой функции принадлежности и нахождения порога разделения на классы. Функция принадлежности принимает значения от окрестности 0 до окрестности 1. Если возвращаемое значение функции для данной записи больше порога, то эта запись принадлежит к классу "1", если меньше, то классу "0" соответственно. Целевая переменная для этого модуля должна быть логического типа.
Discriminate (DS) - дискриминация
Данный алгоритм является модификацией алгоритма CL. Он предназначен для того, чтобы выяснить, чем данные из выбранной таблицы отличаются от остальных данных, включенных в проект, иными словами, для выделения специфических черт, характеризующих некоторое подмножество записей проекта. В отличие от алгоритма CL, он не требует задания целевой переменной, достаточно указать лишь таблицу, для которой требуется найти отличия.
Decision Tree (DT) - дерево решений
В системе PolyAnalyst реализован алгоритм, основанный на критерии максимизации взаимной информации (information gain). То есть для расщепления выбирается независимая переменная, несущая максимальную (в смысле Шеннона) информацию о зависимой переменной. Этот критерий имеет ясную интерпретацию и дает разумные результаты при самых разнообразных статистических параметрах изучаемых данных. Алгоритм DT является одним из самых быстрых в PolyAnalyst.
Decision Forest (DF) - леса решений
В случае, когда зависимая переменная может принимать большое количество разных значений, применение метода деревьев решений становится неэффективным. В такой ситуации в системе PolyAnalyst применяется метод, называемый лесом решений (decision forest). При этом строится совокупность деревьев решений - по одному для каждого различного значения зависимой переменной. Результатом прогноза, основанного на лесе решений, является то значение зависимой переменной, для которой соответствующее дерево дает наиболее вероятную оценку.
Алгоритмы кластеризации
Find Dependencies (FD) - N-мерный анализ распределений
Данный алгоритм обнаруживает в исходной таблице группы записей, для которых характерно наличие функциональной связи между целевой переменной и независимыми переменными, оценивает степень (силу) этой зависимости в терминах стандартной ошибки, определяет набор наиболее влияющих факторов, отсеивает отскочившие точки. Целевая переменная для FD должна быть числового типа, в то время как независимые переменные могут быть и числовыми, и категориями, и логическими.
Алгоритм работает очень быстро и способен обрабатывать большие объемы данных. Его можно использовать как препроцессор для алгоритмов FL, PN, LR, так как он уменьшает пространство поиска, а также как фильтр отскочивших точек или, в обратной постановке, как детектор исключений. FD создает правило табличного вида, однако, как и все правила PolyAnalyst, оно может быть вычислено для любой записи таблицы.
Find Clusters (FC) - N-мерный кластеризатор
Этот метод применяется тогда, когда надо выделить в некотором множестве данных компактные типичные подгруппы (кластеры), состоящие из близких по своим характеристикам записей. Алгоритм FC сам определяет набор переменных, для которых разбиение наиболее значимо. Результатом работы алгоритма является описание областей (диапазонов значений переменных), характеризующих каждый обнаруженный кластер, и разбиение исследуемой таблицы на подмножества, соответствующие кластерам. Если данные являются достаточно однородными по всем своим переменным и не содержат "сгущений" точек в каких-то областях, этот метод не даст результатов. Надо отметить, что минимальное число обнаруживаемых кластеров равно двум - сгущение точек только в одном месте в данном алгоритме не рассматривается как кластер. Кроме того, этот метод в большей степени, чем остальные, предъявляет требования к наличию достаточного количества записей в исследуемой таблице, а именно: минимальное количество записей в таблице, в которой может быть обнаружено N кластеров, равно (2N-1)4.
Аналитический инструментарий PolyAnalyst
Версия PolyAnalyst 4.6 включает 18 математических модулей, основанных на различных алгоритмах Data и Text Mining. Большинство из этих алгоритмов являются Know-How компании Мегапьютер и не имеют аналогов в других системах.
моделирование,прогнозирование,кластеризация,классификация,текстовый анализ.Ниже дается краткая характеристика математическим алгоритмам PolyAnalyst.
Архитектура системы
По своей природе PolyAnalyst является клиент-серверным приложением. Пользователь работает с клиентской программой PolyAnalyst Workplace. Математические модули выделены в серверную часть - PolyAnalyst Knowledge Server. Такая архитектура предоставляет естественную возможность для масштабирования системы: от однопользовательского варианта до корпоративного решения с несколькими серверами. PolyAnalyst написан на языке С++ с использованием спецификации Microsoft's COM (ActiveX). Эта спецификация устанавливает стандарт коммуникации между программными компонентами. Архитектура системы PolyAnalyst представлена на рис. 24.1.
Рис. 24.1. Архитектура системы PolyAnalyst
Математические модули (Exploration Engines) и многие другие компоненты PolyAnalyst выделены в отдельные динамические библиотеки и доступны из других приложений. Это дает возможность интегрировать математику PolyAnalyst в существующие ИС, например, в CRM- или ERP- системы.
Инструменты Data Mining. Система PolyAnalyst
Назначение системы. Система PolyAnalyst предназначена для автоматического и полуавтоматического анализа числовых баз данных и извлечения из сырых данных практически полезных знаний. PolyAnalyst находит многофакторные зависимости между переменными в базе данных, автоматически строит и тестирует многомерные нелинейные модели, выражающие найденные зависимости, выводит классификационные правила по обучающим примерам, находит в данных многомерные кластеры, строит алгоритмы решений. Разработчик системы PolyAnalyst - российская компания Megaputer Intelligence или "Мегапьютер" [105].
Эволюционное программирование
В данное время эволюционное программирование является наиболее молодой и одной из многообещающих технологий Data Mining. Основная идея метода состоит в формировании гипотез о зависимости целевой переменной от других переменных в виде автоматически синтезируемых специальным модулем программ на внутреннем языке программирования.
Использование универсального языка программирования теоретически позволяет выразить любую зависимость, причем вид этой зависимости заранее не известен.
Процесс производства внутренних программ организуется как эволюция в пространстве программ, в некотором роде напоминающая генетические алгоритмы. Когда система находит перспективную гипотезу, описывающую исследуемую зависимость достаточно хорошо по целому ряду критериев, в работу включается механизм так называемых "обобщенных преобразований" (GT-search). С помощью этого механизма в "хорошую" программу вводятся незначительные модификации, не ухудшающие ее качество, и производится отбор лучшей дочерней программы. К новой популяции затем опять применяются механизмы синтеза новых программ, и этот процесс рекурсивно повторяется. Таким образом, система создает некоторое число генетических линий программ, конкурирующих друг с другом по точности, статистической значимости и простоте выражения зависимости.
Специальный модуль непрерывно преобразует "лучшую" на данный момент программу с внутреннего представления во внешний язык PolyAnalyst - язык символьных правил (Symbolic Rule Language), понятный человеку: математические формулы, условные конструкции и так далее. Это позволяет пользователю уяснить суть полученной зависимости, контролировать процесс поиска, а также получать графическую визуализацию результатов. Контроль статистической значимости полученных результатов осуществляется комплексом эффективных и современных статистических методов, включая методы рандомизированного тестирования.
Модули для построения числовых моделей и прогноза числовых переменных
Модуль Find Laws (FL) - построитель моделей
Модуль FL - это сердце всей системы. Алгоритм предназначен для автоматического нахождения в данных нелинейных зависимостей (вид которых не задается пользователем) и представления результатов в виде математических формул, включающих в себя и блоки условий. Способность модуля FL автоматически строить большое многообразие математических конструкций делает его уникальным инструментом поиска знания в символьном виде. Алгоритм основан на технологии эволюционного, или как ее еще называют, генетического программирования, впервые реализованной в коммерческих программах компанией "Мегапьютер".
PolyNet Predictor (PN) - полиномиальная нейронная сеть
Работа этого алгоритма основана на построении иерархической структуры, подобной нейронной сети. При этом сложность этой сетевой структуры и другие ее параметры подбираются динамически на основе свойств анализируемых данных. Если создаваемая сетевая структура не является слишком сложной, то может быть построено эквивалентное ей выражение на языке символических правил системы. Если же сеть слишком большая, то правило не может быть показано, однако его можно вычислить, или - иными словами, применить к исходным или новым данным для построения прогноза. Данный алгоритм чрезвычайно эффективен в инженерных и научных задачах, когда требуется построить надежный прогноз для числовой переменной.
Stepwise Linear Regression (LR) - пошаговая многопараметрическая линейная регрессия
Линейная регрессия, как широко распространенный метод статистического исследования, включена во многие статистические пакеты и электронные таблицы. Однако, реализация этого модуля в системе PolyAnalyst имеет свои особенности, а именно: автоматический выбор наиболее значимых независимых переменных и тщательная оценка статистической значимости результатов. Нужно заметить, что в данном случае значимость отличается от значимости единичной регрессионной модели, так как в течение одного запуска данного вычислительного процесса может быть проверено большое число регрессионных моделей.
Алгоритм работает очень быстро и применим для построения линейных моделей на смешанных типах данных.
Memory based Reasoning (MR) - метод "ближайших соседей"
В системе PolyAnalyst используется модификация известного алгоритма "метод ближайших соседей".
Идея метода была рассмотрена нами ранее. Особенность и отличие реализации алгоритма "ближайших соседей" в системе PolyAnalyst от известных аналогов этого метода заключается в оптимизации меры близости и количества записей для усреднения на основе генетических алгоритмов. Алгоритм MR используется для предсказания значений числовых переменных и категориальных переменных, включая текстовые (string data type), а также для классификации на два или несколько классов.
Модули текстового анализа
В системе PolyAnalyst реализована интеграция инструментов Data Mining с методами анализа текстов на естественном языке - алгоритмов Text Mining. Иллюстрация работы модулей текстового анализа показана на рис. 24.3.
Рис. 24.3. Иллюстрация работы модулей текстового анализа
Text Analysis (ТА) - текстовый анализ
Text Analysis представляет собой средство формализации неструктурированных текстовых полей в базах данных. При этом текстовое поле представляется как набор булевых признаков, основанных на наличии и/или частоте данного слова, устойчивого словосочетания или понятия (с учетом отношений синонимии и "общее-частное") в данном тексте. Тем самым появляется возможность распространить на текстовые поля всю мощь алгоритмов Data Mining, реализованных в системе PolyAnalyst. Кроме того, этот метод может быть использован для лучшего понимания текстовой компоненты данных за счет автоматического выделения наиболее распространенных ключевых понятий.
Text Categorizer (TC) - каталогизатор текстов
Этот модуль позволяет автоматически создать иерархический древовидный каталог имеющихся текстов и пометить каждый узел этой древовидной структуры наиболее индикативным для относящихся к нему текстов. Это нужно для понимания тематической структуры анализируемой совокупности текстовых полей и для эффективной навигации по ней.
Link Terms (LT) - связь понятий
Этот модуль позволяет выявлять связи между понятиями, встречающимися в текстовых полях изучаемой базы данных, и представлять их в виде графа. Граф также может быть использован для выделения записей, реализующих выбранную связь.
В PolyAnalyst встроены алгоритмы работы с текстовыми данными двух видов:
Алгоритмы, извлекающие ключевые понятия и работающие с ними.Алгоритмы, сортирующие тексты на классы, которые определяются пользователем с помощью языка запросов.Первый вид алгоритмов работает только с текстами на английском языке - при этом используется специальный словарь понятий английского языка. Алгоритмы второго типа могут работать с текстами и на английском, и на русском языках.
Text OLAP (матрицы измерений) и Taxonomies (таксономии) - это похожие друг на друга методы категоризации текстов. В Text OLAP пользователь создает именованные столбцы (измерения), состоящие из текстовых запросов. Например: "[добыча] и [нефть] и не ([руда] или [уголь] или [газ])". В процессе работы алгоритма PolyAnalyst применяет каждое из условий к каждому документу в базе данных и в случае удовлетворения условия относит этот документ к соответствующей категории. После работы модуля пользователь может выбирать различные элементы матрицы измерений и просматривать на экране тексты, удовлетворяющие выбранным условиям. Найденные слова будут в этих документах подкрашены разным цветом.
Работа с таксономиями очень похожа на работу с Text OLAP, только здесь пользователь строит иерархическую структуру из таких же условий, как и в матрицах измерений. Система пытается соотнести каждый документ с узлами этого дерева. После работы модуля пользователь также может перемещаться по узлам наполненной таксономии, просматривая отфильтрованные документы с подкрашенными словами.
Матрицы измерений и таксономии дают возможность пользователю взглянуть на коллекцию его документов под самыми разными углами. Но это не все: на основе этих объектов можно делать и другие, более сложные методы анализа, (например, анализ связей (Link Analysis), который показывает, насколько связаны друг с другом различные категории текстов, описанные пользователем) или включать тексты как независимые сущности в другие методы линейного и нелинейного анализа. Все это приводит к плотной интеграции подходов Data Mining и Text Mining в единую концепцию анализа информации.
Общесистемные характеристики 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-запросов к внешним источникам данных. Это позволяет преодолеть ограничения памяти при исследовании больших массивов данных. Данный процесс продемонстрирован на рис. 24.4.
Рис. 24.4. In-place Data Mining
PolyAnalyst Scheduler - режим пакетной обработки
В PolyAnalyst предусмотрена возможность пакетного режима анализа данных. Для этого имеется специальный скриптовый язык, на котором программируется все аналитические действия и временная последовательность их выполнения, а также определяются наборы данных. Скрипт сохраняется в файле и автоматически инициализирует исследование в указанный момент времени на определенных данных.
Для реализации функции Scheduler в электронной лицензии должна быть включена соответствующая опция.
В таблице 24.1 описано семейство продуктов PolyAnalyst6: продукты и соответствующие конфигурации системы.
| 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 Workplace - лаборатория аналитика
Workplace - это клиентская часть программы, ее пользовательский интерфейс. Workplace представляет собой полнофункциональную среду для анализа данных, которая показана на рис. 24.2.
Рис. 24.2. Пользовательский интерфейс PolyAnalyst
Основные черты пользовательского интерфейса программы: развитые возможности манипулирования с данными, графика для представления данных и визуализации результатов, мастера создания объектов, сквозная логическая связь между объектами, язык символьных правил, интуитивное управление через drop-down и pop-up меню, подробная контекстная справка.
Единицей Data Mining исследования в PolyAnalyst является "проект". Проект объединяет в себе все объекты исследования, дерево проекта, графики, правила, отчеты и т.д. Проект сохраняется в файле внутреннего формата системы. Отчеты исследований представляются в формате HTML и доступны через Интернет.
Визуализация
В PolyAnalyst имеется богатый набор инструментов для графического представления и анализа данных и результатов исследований. Данные могут представляться в различных зрительных форматах: гистограммах , двумерных, псевдо- и реальных трехмерных графиках.
Найденные в процессе Data Mining зависимости могут быть представлены как интерактивные графики со слайдерами для изменения значений представленных на них переменных. Эта особенность позволяет пользователю графически моделировать результаты. Имеется набор специальных графиков, широко применяемых в бизнесе, - это так называемые Lift, Gain charts, которые используются для графической оценки качества классификационных моделей и выбора оптимального числа контактов. Кроме этого, в последнюю версию программы включен новый визуальный метод Data Mining: анализ связей.
Link Analysis (LA) - анализ связей
Модуль Link Analysis позволяет выявлять корреляционные и антикорреляционные связи между значениями категориальных и булевых полей и представлять их в виде графа Этот граф также может быть использован для выделения записей, реализующих выбранную связь.
Symbolic Rule Language (SRL) - язык символьных правил
SRL - это универсальный алгоритмический язык PolyAnalyst, который используется для символьного представления автоматически найденных системой в процессе Data Mining правил, а также для создания пользователем своих собственных правил. На языке SRL можно выразить широкий спектр математических конструкций, используя алгебраические операции, большой набор встроенных функций, операции с датами и временем, логические и условные конструкции. Для удобства написания выражений на SRL в программе предусмотрен мастер создания правил.
WebAnalyst
Помимо разработок PolyAnalyst и TextAnalyst, предназначенных соответственно для добычи данных и текстов (Data Mining и Text Mining), фирма Мегапьютер реализует третий продукт - WebAnalyst.
WebAnalyst - это корпоративный аналитический сервер, представляющий собой интегрированную платформу для хранения и обработки информации и адаптированный для работы с web-данными и для решения задач e-business.
WebAnalyst является масштабируемым сервером приложений с открытой архитектурой, который автоматизирует задачи сбора информации, ее преобразования, анализа и генерации персонализированного контента для потребителей. Кроме этого, клиентское приложение WebAnalyst предоставляет гибкий инструмент для визуального проектирования.
Обрабатывает данные из различных источников, таких как каналы передачи данных (HTTP), внешние базы данных и лог-файлы web-серверов.Хранит связанную информацию в собственной единой универсальной базе данных.Содержит набор встроенных аналитических инструментов и инструментов для работы с данными (модули WebAnalyst), предоставляет пользователю визуальное средство для разработки процедур обработки и анализа данных и для генерации контента.WebAnalyst уже включает в себя все математические модули для Data и Text Mining систем PolyAnalyst и TextAnalyst, а также специальную аналитическую математику.
WebAnalyst может быть полезен при решении следующих задач [106]:
регистрации взаимодействия посетителя с Web-сайтом;преобразовании и хранении аналитической информации;использовании собранных данных для изучения интересов посетителя и его предпочтений;анализе эффективности ресурсов сайта и его архитектуры;составлении отчетов для руководства;использовании полученной информации для персонифицированного диалога с каждым посетителем.В качестве "сырья" для своей работы WebAnalyst может использовать: информационные потоки от Web-серверов; базы данных информационного наполнения; базы данных клиентов, продуктов и транзакций; накопленные регистрационные файлы Web-серверов; другие внешние источники данных.
