Добыча данных (data mining) - технология интеллектуального анализа информации с целью выявления скрытых закономерностей в виде значимых особенностей, корреляций и тенденций. Современные системы добычи данных используют основанные на методах искусственного интеллекта средства представления и интерпретации, что и позволяет обнаруживать растворенную в терабайтных хранилищах не очевидную, но весьма ценную информацию. Области применения технологий добычи данных столь разнообразны, что их можно перечислить лишь в терминах обобщенных категорий: торговля и маркетинг, банковское дело и страхование, производство и медицина, наука и социальная сфера - словом, все, что требует обоснованных решений на основе анализа больших массивов информации. Хотя по большому счету рынок соответствующих продуктов и технологий еще только формируется, тем не менее на нем уже присутствуют по крайней мере два десятка известных производителей. В их число входит и компания Silicon Graphics, чей продукт - MineSet отличается своеобычными особенностями как на концептуальном, так и на технологическом уровнях. Акцент при этом делается на уникальную процедуру визуальной интерпретации сложных взаимосвязей в многомерных данных.

Система MineSet представляет собой инструментарий для углубленного интеллектуального анализа данных на базе использования мощной визуальной парадигмы. Характерная особенность MineSet - комплексный подход, адаптирующий использование не одной, а нескольких взаимодополняющих стратегий добычи, анализа и интерпретации данных. Это дает пользователю возможность выбора наиболее подходящего инструмента или множества инструментов - в зависимости от решаемой задачи и от номенклатуры используемых программно-аппаратных средств. Архитектура MineSet имеет принципиально открытый характер - используя стандартизованный файловый формат, другие приложения могут поставлять данные для ввода, а также использовать результаты работы MineSet. Открытая архитектура системы - это и основа для будущего расширения, обладающая потенциалом для встраивания новых компонентов на основе концепции plug-in. В свою очередь, четко определенный интерфейс API позволяет инкорпорировать элементы MineSet в автономные приложения.

Концептуальная схема реализуемого в MineSet процесса добычи данных показана на рис. 1. Ресурсы находятся в информационном хранилище, построенном на основе реляционных СУБД: Oracle, Informix и Sybase, либо на "плоских" ASCII-файлах. Процесс анализа начинается с выборки некоторого подмножества данных для дальнейшего исследования, которые могут быть подвергнуты различным преобразованиям, создающим информационную модель в виде, наиболее подходящем для последующего изучения. Собственно процесс "понимания" созданной информационной модели носит принципиально итеративный и интерактивный характер и заключается в применении инструментов двух типов. Традиционные средства "аналитического data mining", опирающиеся на методы искусственного интеллекта с использованием машинного обучения, обеспечивают автоматическое обнаружение образцов (шаблонов) данных, интересных в каком-либо отношении, и построение моделей, используемых для дальнейшей интерпретации и прогнозирования. Фирменные средства визуального data mining дают на основе графического 3D-интерфейса наглядное представление и интерпретацию многомерной информации, что позволяет достичь более глубокого, в том числе интуитивного понимания модели. При этом есть возможность визуализировать как полученные на стадии аналитической добычи данных модели со сложными образцами, так и непосредственно исходные данные.

Picture 1(1x1)

Рис. 1.  Процесс data mining

Архитектура MineSet предполагает использование модели клиент-сервер (рис. 2), реализуемой на базе платформы SGI под ОС IRIX 5.3, 6.2 и выше. Если предполагается работа с информационными хранилищами большого объема, то рекомендуется применение серверов CHALLENGE или ORIGIN, хотя в принципе любую станцию SGI можно использовать не только с клиентской стороны, но и в качестве сервера. При наличии X-сервера, такого как Hummingbird Communications Exceed 3D, можно использовать и ПК. Возможен также и усеченный вариант применения MineSet без сервера - при условии, что визуальный data mining применяется к уже подготовленному каким-то образом клиентскому ASCII-файлу.

Picture 2(1x1)

Рис. 2. Архитектура MineSet

Сам набор инструментальных средств MineSet состоит из трех базовых компонентов:

  • централизованного управляющего модуля, включающего в себя графический интерфейс пользователя - Инструментальный Менеджер (Tool Manager), и базирующийся на сервере процесс DataMover;
  • модуля аналитического database mining, базирующегося на сервере и имеющего четыре интеллектуальных инструмента добычи данных;
  • модуля визуального data mining, находящегося на клиентской станции и состоящего из пяти инструментов, использующих различные визуальные метафоры.

1. Управляющий модуль

Инструментальный Менеджер предоставляет интерактивный графический интерфейс, с помощью которого пользователь получает доступ ко всем возможностям и инструментам MineSet в рамках единой интегрированной среды. Прежде всего, Tool Manager позволяет установить связь с сервером и специфицировать базу или файл, содержащие исходные данные, а также определить дисциплину доступа и манипулирования данными. Для реляционных СУБД Oracle, Informix и Sybase, а также "плоских" ASCII-файлов реализована прямая встроенная процедура доступа; однако можно определять и произвольные SQL-запросы, что необходимо в том случае, если информационные хранилища реализованы каким-то иным способом. Набор преобразований, полезных при генерации входных файлов для каждого из инструментов аналитического и визуального анализа, весьма широк и, в частности, включает в себя:

  • агрегирование данных с генерацией индексированных массивов с использованием функций SUM, AVERAGE, MIN, MAX, COUNT;
  • добавление и удаление столбцов данных;
  • преобразование типов данных;
  • вычисление выражений и распределений.

В качестве иллюстрации приведем пример формирования файла с данными из базы, содержащей информацию о рождаемости в Нидерландах в период 1989-93 гг. Среди признаков данных: region - название штата, sqkm - его площадь, year - год, population - население штата в этот год, age - возраст матери и birthrate - статистика родов среди женщин этой возрастной категории. Прежде всего определяются признаки, которые далее используются как индексы для выборки записей - в этом качестве выступают year с выборкой по каждому году и age с выборкой за каждое четырехлетие. Затем создается, в частности, отсутствовавший в явном виде массив Pop.Density - плотность населения каждого штата на км2 за все годы в отдельности, а также массив sum_birthrate, содержащий агрегированные данные о совокупном показателе родов среди женщин данного возраста по всем четырехлетиям. Полученный входной файл и подвергается анализу.

Можно задействовать также средства протоколирования выполняемых преобразований. В конечном итоге Инструментальный Менеджер создает файлы конфигурации, задающие дисциплину работы для каждого из инструментов анализа. В частности, именно в соответствии с информацией, содержащейся в переданном на сервер файле конфигурации, процесс DataMover осуществляет доступ к данным, производит их выборку и преобразования, инициализирует работу запускаемых на сервере инструментов аналитического data mining и возвращает данные на клиентскую станцию для распределения их по визуальным инструментам. Последние запускаются на клиентской станции самим Инструментальным Менеджером, который - опять же через соответствующие файлы конфигурации - определяет, какие данные и как визуализируются каждым из визуальных инструментов. Наконец, есть возможность запоминать и восстанавливать как вновь полученные данные, так и ход управления сессией - ее сценарий.

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

2. Инструменты аналитического data mining

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

2.1. Генератор Ассоциативных Связей (Association Rule Generator)

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

1) Первое число, "предсказуемость" (predictability) правила, определяет, как часто X и Y появляются вместе в виде доли количества записей, в которых встречается X. Например, если некто покупает творог, то как часто при этом производится покупка сметаны.

2) Второе число, "распространенность" (prevalence) правила, показывает, как часто X и Y встречаются вместе в файле в виде доли от общего числа записей. И, если продолжить вышеприведенный пример, то как часто творог и сметана покупаются вместе.

3) Третье число - это "ожидаемая величина предсказуемости" (expected predictability), или частота присутствия элементов в правой части правил. Она показывает ту предсказуемость, которая сложилась при отсутствии взаимосвязи между элементами. Например, как часто покупалась бы сметана безотносительно к тому, покупался ли творог.

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

2.2. Генератор Дерева Решений (Decision Tree Inducer)

Назначение этого инструмента - генерация Классификатора Дерева Решений (Decision Tree Classifier) непосредственно из данных. Дерево Решений составляется из узлов и отрезков линий, соединяющих эти узлы. Существует два типа узлов: узлы решений (decision nodes) и концевые узлы. Узлы решений соответствуют ситуации, когда во время классификации требуется задать вопросы о записи. Если никаких вопросов задавать не нужно, то это соответствует концевому узлу.

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

MineSet может строить классификатор автоматически из обучающего множества (training set), состоящего из уже классифицированных записей в базе данных, для которых на основании описательных признаков определена метка. Сгенерированный однажды классификатор может быть использован для классификации дополнительных записей уже не из обучающего множества - иначе говоря, применен к данным, для которых существует неизвестная величина признака классифицируемого затем с использованием особого Дерева Решений. Этот процесс называется разметка (scoring). Так, применяя Классификатор для определения кредитоспособности клиента банка, можно получить дерево решений, показывающее, что если клиент имеет дом, автомобиль стоимостью от 15 до 25 тыс. долл. и если у него семья и двое детей, то ему можно выдавать кредит.

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

2.3. Генератор Свидетельств (Evidence Inducer)

Этот инструмент непосредственно из данных выводит Классификатор Свидетельств (Evidence Classifier), который классифицирует данные, определяя вероятности, при которых может случиться некоторый заранее специфицированный результат при заданных значениях признака. Например, можно определить, что клиент банка, владеющий автомобилем стоимостью от 15 до 25 тыс. долл., с вероятностью 70% вернет кредит. При этом классификатор назначает условные вероятности уникальным величинам признака или диапазону величин для него. Также на основании распределения записей из обучающих данных (использованных для построения классификатора) вычисляется априорная вероятность. Во время классификации условные вероятности для известных величин признаков умножаются на априорные вероятности с тем, чтобы получить относительные вероятности. Самая высокая относительная вероятность для величины признака классификации определяет предсказанный класс.

При использовании вместе с Визуализатором Свидетельств (Evidence Visualizer) Классификатор Свидетельств может применяться к неклассифицированным данным и быть полезным для прогнозирующих сценариев типа "что если"; он способен также идентифицировать те признаки, которые обеспечивают сильное свидетельство за или против специфической классификации.

2.4. Утилита определения Значимости Признаков (Column Importance)

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

Значимость столбцов обеспечивает меру, называемую "чистота" (purity) - число в диапазоне от 0 до 100, которое показывает, насколько эти столбцы важны при классификации. Более того, можно получить "кумулятивную чистоту", показывающую, насколько значимы комбинации столбцов именно в связи друг с другом, что может повысить вероятность создания хорошей классификации. Например, признак "зарплата" может быть признан несколько менее значимым, чем "годовой доход"; однако в совокупности со "стоимостью дома" может оказаться более значимым, чем "годовой доход" в комбинации с "наличием собственного дома".

3. Инструменты визуального data mining

MineSet обеспечивает пять инструментов для визуального data mining, позволяющих выполнять интерактивное визуальное представление и исследование данных. Анимированные 3D-ландшафты, создающие максимальный эффект трехмерного пространства, позволяют сравнивать объекты различных размеров и цветов, распознавать значимые образцы, взаимосвязи и тренды. Средства визуализации обеспечивают резкое уменьшение размерности и сложности данных, конденсируя, быть может, миллионы записей данных в простые, легкие для понимания и манипулирования представления.

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

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

3.1. Ландшафтный Визуализатор (Map Visualizer)

Ландшафтный Визуализатор представляет собой графический интерфейс, отображающий данные в виде трехмерного ландшафта произвольно определенных и позиционированных форм - столбчатых диаграмм, каждая с индивидуальными высотой и цветом. Это позволяет наглядно показывать количественные и реляционные характеристики пространственно-ориентированных данных и быстро идентифицировать в них тренды, образцы, взаимосвязи и аномалии. На рис. 3 приведен пример визуализации входного файла с информацией о рождаемости в Нидерландах. При этом ранее в интерфейсе Инструментального Менеджера в окне "Visual Elements" высоте столбцов был поставлен в соответствие массив sum_birthrate, а на цвет столбцов отображен массив Pop.Density.

Picture 3(1x1)

Рисунок 3.
Ландшафтный Визуализатор: данные о рождаемости в Нидерландах.

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

Визуализатор включает мощные анимационные возможности, позволяющие аналитику наблюдать за развертыванием множества данных через одну или две независимые переменные, в описываемом примере - year и age. Для более глубокого проникновения в данные могут быть созданы и синхронно визуализированы несколько анимационных процессов. Возможно определять визуальное окно для анимации агрегированных данных, что позволяет идентифицировать суммарные тренды и точки интереса на очень высоком уровне абстракции. Для управления анимацией используются линейки прокрутки (sliders) - чтобы скользить по значениям переменных, поставленным им в соответствие; при этом можно наблюдать анимацию размеров и цветов столбцов, а следовательно - судить об изменении соответствующих им зависимых переменных. Управляющая анимацией панель также позволяет "прокладывать" путь для анимации в одном или двух измерениях. Затем можно двигаться вдоль этого пути как вперед, так и назад, наблюдая, как ведут себя тренды или аномалии, и одновременно генерировать анимационные презентационные ролики.

При работе доступны все операции навигации через ландшафт: панорамирование; вращение в 3D-пространстве; масштабирование с укрупнением интересующей области и др. Пользователь может выполнять операцию drill-down с целью получения детализированной информации о специфических областях данных и операцию drill-up - чтобы посмотреть, как некоторые локализованные данные встроены в окружающую их среду.

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

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

3.2. Визуализатор Дисперсии (Scatter Visualizer)

Как правило, множества данных слишком сложны, чтобы их можно было исчерпывающе представить в двух или трех измерениях. Предлагаемый инструмент - это средство для анализа поведения данных сразу во многих измерениях; при этом к обычной 3D-системе координат, в которой задаются "сущностные" переменные, добавляется два дополнительных измерения, ассоциированных с размером и цветом элементов данных, а также "динамические измерения", дающие возможность анимации на основе независимых переменных. При этом обеспечены все анимационные и навигационные возможности, присущие Ландшафтному Визуализатору.

Таким образом, можно исследовать данные в семи измерениях, что весьма помогает при обнаружении сегментации данных, их кластеризации и профилировании. Как и в других режимах, имеются возможности агрегирования данных. В трехмерном пространстве, дополненном координатной сеткой, можно ориентировать изображение для акцентирования определенного измерения или точки зрения. Можно масштабировать величины некоторых переменных для придания им большей значимости. Существует возможность фильтрации изображения, чтобы показывать только те сущности, которые удовлетворяют определенным критериям. На рис. 4 представлены данные о рождаемости в Нидерландах. Здесь с осями X, Y, Z ассоциированы признаки "штат", "плотность населения" и "рождаемость на 1000"; дополнительное цветовое измерение соответствует "населению" , а в качестве независимых переменных снова используются год и возраст матери.

Picture 4(1x1)

Рисунок 4.
Визуализатор Дисперсии: данные о рождаемости в Нидерландах.

3.3. Визуализатор Деревьев (Tree Visualizer)

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

Имеется также возможность отображения деревьев решений, выдаваемых Генератором Деревьев Решений. Визуализатор Деревьев показывает узлы классификации решений и концевые узлы вместе с ассоциированной с этими узлами информацией, что создает предпосылки для понимания алгоритма классификации и дальнейшего анализа Деревьев Решений. На рис. 5 представлены данные о продажах пива. Здесь имеются три уровня иерархии: категория пива; сорт пива; предлагаемый к продаже конкретный продукт (например упаковка из 12 банок). Каждый узел содержит семь столбцов, представляющих разные возрастные группы покупателей. Высота столбца - деньги (в долл.), потраченные представителями данной возрастной группы, а цвет - процент этой суммы, потраченный мужчинами и женщинами.

Picture 5(1x1)

Рисунок 5.
Визуализатор Деревьев: данные о продажах пива.

3.4. Визуализатор Правил (Rule Visualizer)

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

Правила представляются на покрытом сеткой ландшафте, причем элементы из левых частей правил располагаются на одной оси, а из правой - на другой. Признаки правил изображаются в точке сочленения в узлах сетки этих элементов в виде столбцов, дисков и меток. Сетку с 3D-правилами можно масштабировать, вращать и панорамировать. Визуальная фильтрация и опрос позволяют пользователю фокусироваться на выбранных правилах. На рис. 6 приведены данные, сгенерированные Генератором Ассоциативных Связей для продаж пищевых продуктов. Наименования продуктов располагаются на осях; высота столбцов в узлах сетки показывает распространенность (prevalence) соответствующего правила, а цвет столбцов свидетельствует о предсказуемости (predictability) правил.

Picture 6(1x1)

Рисунок 6.
Визуализатор Ассоциативных Связей: данные о совместных продажах продуктов.

3.5. Визуализатор Свидетельств (Evidence Visualizer)

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

Строки круговых 3D-диаграмм или столбцов представляют признаки, использованные классификатором. Каждая круговая диаграмма отражает вероятность того, что величина признака или диапазон величин подходят для классификации. По щелчку клавишей мыши на круговой диаграмме вероятности комбинируются с тем, чтобы представить вероятность полной классификации, основанную на известных величинах атрибутов для записей данных, которые должны быть классифицированы. Также могут быть созданы сценарии "что если". На рис. 7 представлены сгенерированные Генератором Свидетельств данные, показывающие, какие факторы влияют на получаемый наемным работникам годовой доход. Все записи разделены на два класса - лица с суммарным годовым доходом до 50 тыс. долл. и более. Круговая диаграмма представляет вероятность попадания работников в каждый из этих классов, что отображается соответственно желтым и красным цветом. Порядок следования признаков-атрибутов в общем списке факторов показывает их значимость: например, можно сделать вывод, что семейное положение оказывает на годовой доход более сильное влияние, чем пол; при этом видно, что большинство рабочих состоят в браке; женатые зарабатывают больше холостых; женщины в основном зарабатывают менее 50 тыс. долл. в год и т. д.

Picture 7(1x1)

Рис. 7. Визуализатор Свидетельств: данные о годовом доходе.

***

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

Валерий Аджиев -- Московский Государственный Инженерно-физический Институт (Москва).

Поделитесь материалом с коллегами и друзьями