Для решения задач интеллектуального анализа данных в отделе
Вычислительных методов прогнозирования
ВЦ РАН
разработано инструментальное средство ASDIEL,
Algorithmic Superpositions Description
and Investigation Environment and Language —
язык и среда для описания и исследования алгоритмических композиций.
Цель данного вводного обзора —
очертить класс задач, для решения которых это средство предназначено,
перечислить его основные особенности
и описать формальную модель данных, лежащую в его основе.
Система ASDIEL предназначена для решения задач распознавания,
прогнозирования и поиска скрытых закономерностей в неполных, неточных,
противоречивых и разнородных данных. В последние годы эти направления
получили общее название data mining или "интеллектуальный анализ данных".
Большое количество задач такого рода возникает при попытках использовать
для эффективного принятия решений огромные объемы сырой информации, накопленной
в банках данных.
Однократного анализа данных в таких задачах, как правило, не достаточно.
Обычно требуется получать выходную информацию регулярно,
причем без непосредственного участия аналитика.
Поэтому под "решением задачи" понимается уже не набор конкретных значений,
а алгоритм, способный выдавать эти значения при любой начальной информации,
то есть осуществлять отображение исходных данных в финальную информацию.
Именно на синтез таких алгоритмов и нацелена система ASDIEL.
От "интеллектуальных" алгоритмов требуется, чтобы они адаптировались
к новым исходным данным и самостоятельно находили в них разного рода
закономерности и зависимости.
Поэтому в ASDIEL особая роль отводится алгоритмам, способным обучаться
на прецедентах. Обучение осуществляется путем настройки параметров алгоритмов
по заданной обучающей информации. Тривиальным примером обучаемых алгоритмов
являются известные в математике классические методы
интерполяции и экстраполяции.
Модель данных ASDIEL основана на представлении всех исходных,
промежуточных и выходных данных в матричном виде.
Это достаточно общее представление, позволяющее охватить
широкий класс прикладных задач.
Для применения многих традиционных методов статистического анализа
и распознавания образов вполне достаточно двумерной матрицы
"объекты–признаки".
Модель данных ASDIEL обобщает этот случай на произвольное число
матриц произвольной размерности.
Поиск решения прикладной задачи с помощью ASDIEL заключается
в подборе композиции стандартных алгоритмов анализа и преобразования данных.
Стандартные алгоритмы выбираются из библиотеки, содержащей различные методы
аппроксимации, классификации, таксономии, статистического анализа,
оптимизации, и т. д.
Программа на языке ASDIEL описывает структуру композиции —
последовательность выполнения алгоритмов и состав данных
на входе и выходе каждого алгоритма.
Существенная особенность ASDIEL состоит в возможности построения
обучаемых алгоритмических композиций.
Как отдельные алгоритмы, так и композиции могут запускаться
в различных режимах, например, в режиме настройки или рабочего вычисления.
На практике структура искомой композиции, как правило, заранее
неизвестна и должна подбираться в ходе вычислительных экспериментов на
реальных данных. При этом описание композиции на языке ASDIEL следует
рассматривать как сценарий очередного эксперимента, и только по завершении
исследований — как запись решения поставленной задачи.
Кроме собственно языка, ASDIEL включает в себя интегрированную
среду, позволяющую разрабатывать и отлаживать алгоритмические композиции,
проводить серии численных экспериментов, отображать любые срезы данных
в виде таблиц и графиков. Средства языка охватывают все основные этапы
обработки данных в задачах обучения по прецедентам: импорт, предварительную
обработку, настройку, расчет, визуализацию и экспорт данных.
Сборка алгоритмов из готовых укрупненных модулей позволяет
достаточно быстро получать неплохие решения. Однако технологичность не
является единственным обоснованием для использования алгоритмических композиций.
Оно представляется естественным при решении задач распознавания, классификации
и прогнозирования в силу целого ряда обстоятельств.
-
Часто оказывается, что ни один из стандартных алгоритмов по отдельности
не дает результатов приемлемого качества.
В таких случаях можно применять методы алгебраического подхода,
суть которого состоит в построении корректирующей операции
над имеющимися эвристическими алгоритмами.
В результате возникает алгоритмическая композиция,
каждый элемент которой настраивается отдельно.
-
Если исходные данные разнотипные, неполные, неточные или косвенные,
в общий ход решения включаются алгоритмы предварительной обработки данных,
например:
-
в случае разнотипных признаков — приведение их к одной шкале;
-
в случае слишком обширного множества объектов — кластеризация объектов;
-
при наличии нетипичных объектов — оценивание и устранение выбросов;
-
в случае неполных или разреженных данных — выделение наиболее
информативной части данных или заполнение пропусков.
-
Некоторые алгоритмы, такие как АВО,
сами имеют достаточно сложную структуру, выбор которой не всегда следует
доверять численным методам. Исследователь должен иметь возможность задавать
отдельные ее части непосредственно или получать с помощью других алгоритмов.
Поэтому сложные многоступенчатые алгоритмы целесообразно разделять на
отдельные составляющие, предоставив исследователю возможность использовать
их по отдельности.
-
В конкретной задаче может понадобиться то или иное специальное преобразование
данных (например, математическая модель предметной области), которое
можно реализовать как отдельный алгоритм и применять его наряду с более
универсальными преобразованиями данных.
-
Наконец, при передаче данных от одного алгоритма другому часто приходится
выполнять различные вспомогательные преобразования, которые также подлежат
унификации и должны быть включены в библиотеку алгоритмов.
Построение композиции не ограничивается выбором нескольких
стандартных алгоритмов и последовательности их выполнения.
В нетривиальных прикладных задачах при формировании композиции
неизбежно возникает масса дополнительных вопросов,
специфичных для данной конкретной задачи, например:
-
какой алгоритм предпочесть для выполнения
того или иного преобразования данных?
-
как выделить из имеющегося множества объектов обучающую и контрольную
выборки?
-
как отсеять заведомо непоказательные или исключительные объекты?
-
какую функцию близости объектов предпочесть?
-
как оптимизировать состав признаков, подаваемых на вход того или иного
алгоритма?
-
какие функциональные преобразования повысят информативность признаков?
-
какие значения придать тем параметрам алгоритмов, которые не определяются
автоматически в результате обучения?
-
как организовать процедуру скользящего контроля для оптимизации этих
параметров и выбора лучшего алгоритма?
-
какой способ хранения промежуточных данных выбрать, чтобы прийти к
компромиссу между скоростью вычислений и размером требуемой памяти?
Эти и подобные им вопросы определяют структуру композиции.
Задать структуру — значит описать, какие алгоритмы
и в какой последовательности должны выполняться;
какие входные и выходные матрицы имеет каждый алгоритм;
с помощью каких функциональных выражений образуются новые признаки.
Поскольку композиция составляется из стандартных алгоритмов,
все специфические особенности решаемой задачи должны быть учтены
именно в ее структуре.
Формирование структуры является ключевым и наименее формализуемым
этапом поиска решения.
Специализированный язык является подходящим средством для
записи структурной информации указанного вида. Он позволяет свести ее
в одно компактное описание и упрощает проведение вычислительных экспериментов.
В то же время он скрывает от пользователя рутинные операции формирования
и хранения данных, реализацию и взаимодействие алгоритмов. Таким образом,
применение специализированного языка позволяет сосредоточиться
на содержательных сторонах решаемой задачи.
Решение задачи начинается с выделения нескольких упорядоченных
множеств, называемых наборами, которые в дальнейшем будут играть
роль размерностей в массивах данных. Если предполагается работать только
с признаковыми описаниями объектов, то достаточно определить только два
набора: объектов и признаков. В общем случае могут понадобиться также:
- набор пар объектов;
- набор моментов времени (в динамических задачах);
- набор функций над парами объектов (расстояния, отношения, и т. д.);
- набор свойств признаков (информативности, средние значения, и т. д.);
- набор функций над парами признаков (близости, корреляции, и т. д.);
- и т. д.
Затем некоторым декартовым произведениям введенных наборов
сопоставляются массивы, предназначенные для хранения и представления
данных. Команда языка USE позволяет определить
любое количество наборов и массивов.
Например, команда
USE F[S], M[S|S];
вводит
набор объектов S,
набор признаков F,
набор функций над парами объектов M,
определяет двумерный массив
F[S] "признаки – объекты"
и трехмерный массив
M[S|S] "функции – пары объектов"
(символ | используется в ASDIEL для разделения размерностей
и может интерпретироваться как знак декартова произведения).
В каждом массиве имеется одна выделенная размерность — набор
признаков, отвечающий за запись и считывание значений из массива.
То, каким образом значения вычисляются и хранятся,
зависит от способа генерации и способа хранения каждого конкретного признака.
Пользователь может существенно влиять на эффективность вычислений,
выбирая способ хранения промежуточных результатов.
Эффективное распределение памяти достигается за счет отказа
от хранения неиспользуемых или легко вычислимых ячеек массивов.
Возможны три способа генерации значений признака:
-
признак считывается из файла или базы данных,
либо записывается непосредственно внешней прикладной программой;
-
признак вычисляется алгоритмом;
-
признак вычисляется по заданному арифметическому выражению.
Возможны три способа хранения значений признака:
-
признак хранится в оперативной памяти с прямым доступом
(для двумерных массивов);
-
признак хранится в оперативной памяти с индексированным доступом
(для многомерных разреженных массивов);
-
признак вычисляется алгоритмом или выражением при каждом обращении,
память для хранения не отводится.
Таким образом фактически стирается различие между данными,
результатами алгоритмов и арифметическими выражениями.
Для пользователя языка все это — признаки,
с которыми он работает единообразно независимо
от способа хранения и генерации.
Язык ASDIEL является в значительной степени декларативным
благодаря тому, что для выделения подмассивов данных используются
не циклы, как в традиционных языках программирования,
а операции над упорядоченными множествами.
Ключевую роль при этом играет операция декартова произведения.
Например, чтобы выделить в массиве F[S]
подмассив, образованный множеством признаков {x, y, z} из F
и множеством первых ста объектов из S, пишут:
F{x,y,z} | S{#1..#100}.
ASDIEL позволяет формировать произвольные срезы данных
с помощью полного набора теоретико-множественных операций
(объединение, пересечение, дополнение, выборка, сортировка,
понижение размерности).
Подмассивы служат для описания входов и выходов алгоритмов.
Алгоритм считывает данные из входных подмассивов,
производит вычисления и заносит результаты в выходные подмассивы.
При этом важно, чтобы размерности подмассивов удовлетворяли
спецификации данного алгоритма.
Таким образом, пользователь получает возможность обращаться
с алгоритмами единообразно, как со стандартизованными "черными ящиками",
ничего не зная о их внутреннем устройстве.
Определение 1.
Алгоритмом в ASDIEL называется вычислимое отображение вида
(X1,
,Xm) ->
(Y1,
,Yn),
где
(X1,
,Xm)
— входные подмассивы,
(Y1,
,Yn)
— выходные подмассивы.
Композиция образуется, когда на вход одних алгоритмов подаются данные,
генерируемые другими алгоритмами.
Это основополагающий механизм, благодаря которому
все библиотечные алгоритмы свободно стыкуются друг с другом.
Определение 2.
Методом в ASDIEL называется совокупность
конечного множества алгоритмов и конечного множества параметров.
Любой алгоритм метода может свободно считывать и изменять значение любого
параметра метода.
Методы обучения по прецедентам имеют, как правило, два алгоритма —
настройки и вычисления.
Алгоритм настройки устанавливает значения параметров метода
и обычно вообще не имеет выходов.
Алгоритм вычисления использует настроенные значения параметров
при вычислении своих выходных подмассивов.
Композицию, как и отдельный алгоритм,
можно запускать в режиме настройки или в режиме вычисления.
Имеется возможность сохранить настроенную композицию как отдельную программу,
готовую к работе без предварительного обучения.
Введенные определения алгоритма и метода охватывают
обширный класс моделей алгоритмов.
Многие модели, активно используемые на практике,
легко описываются в терминологии ASDIEL.
Это позволяет создать мощную библиотеку методов
с единым интерфейсом и правилами применения.
В настоящее время библиотека ASDIEL постепенно пополняется новыми методами.
Разработан открытый документированный интерфейс,
позволяющий реализовать новые методы в виде динамических библиотек.
Язык ASDIEL предназначен в первую очередь для решения
задач интеллектуального анализа данных,
в которых структура искомого решения изначально не ясна
и требуется проведение исследований.
Ниже описан приблизительный ход решения такого рода задач и
то, каким образом язык ASDIEL используется на каждом из этапов.
Перебор гипотез осуществляется путем модификации
текущего текста программы,
а их проверка — с помощью встроенных средств визуализации данных.
В процессе построения композиции возможно итеративное возвращение
к предыдущим шагам.
-
Выяснение структуры входных и выходных данных.
Приведение всех данных к матричной форме представления.
На уровне ASDIEL это реализуется при описании всех наборов
и массивов командой USE
и загрузке данных командой IMPORT.
-
Формирование начальных гипотез о целесообразном ходе решения
и поиск наиболее простых решений.
На уровне ASDIEL это сводится к попыткам применения
отдельных библиотечных методов.
Если найти приемлемое решение таким способом не удается,
дальнейшие исследования нацеливаются на выявление причин,
по которым опробованные методы не дают качественных результатов.
-
Исходные данные могут оказаться
неполными, неточными, разнородными, слишком обширными
или сложно структурированными.
Тогда в ASDIEL-программу между загрузкой данных
и применением основных методов вставляются
необходимые методы предварительной обработки данных.
-
Допустим, что все опробованные модели алгоритмов
оказались неадекватными на имеющейся прецедентной информации.
-
Один из выходов состоит в поиске функциональных преобразований
признаков, способных повысить их информативность.
При этом формулируются и проверяются различные гипотезы
модельного характера о виде этих преобразований.
ASDIEL позволяет создавать новые признаки
с помощью арифметических выражений над имеющимися признаками.
-
Возможно, для решения задачи придется разработать
совершенно новый метод, основанный на модельных или
эвристических соображениях, специфичных для данной конкретной задачи.
Отметим, что ASDIEL поддерживает только алгоритмическую форму
представления знаний о предметной области.
Новый метод или группа методов реализуется
в виде отдельной динамической библиотеки.
-
Еще один путь — попытаться изменить "рабочее пространство".
Например, если исходная задача формулировалась
в терминах описаний объектов, то, возможно,
стоит перейти к метрическому описанию и работать
с функциями близости объектов.
На уровне ASDIEL это означает переход
от 2-мерного массива объектов к 3-мерному массиву
пар объектов и использование принципиально иного класса методов.
-
Если в ходе экспериментов удалось получить несколько различных моделей,
каждая из которых не обладает необходимым качеством,
то можно попытаться применить идеологию алгебраического подхода
— построить корректирующую операцию, взяв эти модели
в качестве базисных.
-
Тестирование построенной композиции на контрольной выборке
или скользящем контролем.
Язык ASDIEL позволяет описать несколько режимов выполнения
одной и той же композиции:
настройка,
рабочее вычисление,
тестирование, и т. д.
-
Возможна ситуация, когда полученный алгоритм
дает хорошие результаты на обучающей информации,
и неадекватные — на контрольной выборке.
Обычно это свидетельствует о чрезмерной усложненности найденного решения.
Возможно, стоит попытаться удалить лишние звенья композиции
или вставить в композицию методы поиска информативных признаков.
-
Завершение исследований:
настройка, отладка и проверка качества композиции.
Отработка способов визуализации или экспорта выходных данных
с помощью команд CHART, TABLE, PRINT.
-
Сохранение настроенной композиции в виде отдельной программы.
Использование полученного алгоритма для обработки данных
в прикладных программах реализуется через обращение к ядру ASDIEL.
Описанный выше цикл исследований конечно же не универсален,
тем не менее, он достаточно типичен при решении прикладных задач.
Набор средств, предоставляемых ASDIEL, существенно упрощает
проведение такого рода исследований и делает их более технологичными.