OLAP.ru   Rambler's Top100
Вы находитесь на страницах старой версии сайта. Перейдите на новую версию OLAP.ru
  
Поиск по сайту
Новости
Основы OLAP
Продукты
Business Objects/ Crystal Decisions
Каталог
OLAP в жизни
Тенденции
Download
Яndex
 
 
 
TopList
 

Методы представления информации в разреженных гиперкубах данных

Заботнев Максим Сергеевич,
научный сотрудник ФГНУ "Госинформобр"

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

Введение

Рассматриваемая задача возникла в ходе создания комплекса технологических и программных средств, в разработке которых автор принимал участие на протяжении нескольких лет, начиная с 2000г. Целью создания комплекса являлась разработка технологии сбора первичных данных о состоянии образовательных ресурсов России по большому числу территориально распределенных объектов, а также обеспечение поддержки принятия управленческих решений на основе анализа собранных данных. В качестве основы создания аналитической части комплекса использовалась технология оперативной аналитической обработки данных - OLAP[1-3].

Практика разработки и внедрения территориально распределенных систем сбора данных показала, что в силу различных причин сбор первичных данных осуществляется лишь частично. Это приводит к необходимости использования многомерных баз данных с частичной или слабой заполненностью. При этом создаваемые многомерные кубы данных (гиперкубы) имеют низкую плотность заполнения данными, т. е., следуя терминологии [4], являются разреженными. Использование традиционных средств работы с такими гиперкубами приводит к возникновению, как минимум, двух проблем:

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

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

В ряде научных трудов, в т. ч. отечественных специалистов [5-10], изложены теоретические основы работы с базами данных с неполной информацией. Однако техническая реализация подобных подходов применительно к многомерным базам данных находится в стадии становления. В большинстве руководств по созданию информационных систем, ориентированных на анализ данных, вопросы представления информации в разреженных гиперкубах данных также обходятся стороной. Между тем, методы работы с плотными и разреженными гиперкубами данных должны существенно различаться. Таким образом, разработка альтернативных методов поиска и агрегации данных, позволяющих решить вышеуказанные проблемы, является актуальной задачей.

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

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

Перейдем к формальному описанию многомерной модели данных.

Модель данных

Основными понятиями многомерной модели данных являются:

  • Гиперкуб данных (Data Hypercube)
  • Измерение (Dimension)
  • Метки (Memders)
  • Ячейка (Cell)
  • Мера (Measure)

Гиперкуб данных содержит одно или более измерений и представляет собой упорядоченный набор ячеек (Рис. 1). Каждая ячейка определяется одним и только одним набором значений измерений - меток. Ячейка может содержать данные - меру или быть пустой.

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

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


Рис. 1. Гиперкуб данных

Итак, пусть - множество измерений гиперкуба.
- множество меток измерения ,
- множество меток гиперкуба,
- множество фиксированных измерений,
- множество фиксированных меток.

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

Каждой ячейке гиперкуба данных соответствует единственно возможный набор меток измерений . Ячейка может быть пустой (не содержать данных) или содержать значение показателя - меру.

Множество мер гиперкуба обозначим как . Рассмотрим операции манипулирования данными в гиперкубе данных.

Операции манипулирования данными

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

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

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

Операция "Вращения". Изменение порядка представления (визуализации) измерений называется Вращением (Rotate). Вращение обеспечивает возможность визуализации данных в форме, наиболее комфортной для их восприятия.

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

Операции "свертки и детализации" осуществляются благодаря наличию иерархической структуры измерений. Значения измерений (метки) могут объединяться в иерархии, состоящие из одного или нескольких уровней (levels). Например, метки измерения "Время" естественно объединяются в иерархию с уровнями: год, квартал, месяц, день. Далее будет показано, что операции свертки и детализации принципиально не отличаются от операции построения среза гиперкуба данных, однако их выделяют для описания работы с агрегированными данными. Наличие иерархической структуры измерений позволяет осуществлять агрегацию данных.

Агрегация данных

Агрегация данных - суть получение значений, соответствующих меткам некоторого уровня иерархического измерения D на основе значений уровня .

Рассмотрим иерархическое измерение D с L уровнями (Рис. 2). Первичные данные (факты) соответствуют нижнему уровню иерархии ().


Рис. 2. Агрегация гиперкуба данных. Одномерное представление.

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

Обобщая, получим формулы вычисления агрегатов по методу суммирования на остальных уровнях иерархии: ,

Ось измерения D, первоначально содержащая метки, соответствующие нижнему уровню иерархии (), может быть дополнена метками, соответствующими уровням иерархии, начиная с . Таким образом, различие между метками, соответствующими первичным данным и метками, соответствующим агрегатам является условным.

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

Количество агрегатов для одного измерения . Рассмотрим случай двух измерений (Рис. 3).


Рис. 3. Агрегация гиперкуба данных. Двумерное представление.

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

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

Обобщая на случай произвольного числа измерений D, получим: , где - кол-во меток i-го уровня иерархии измерения , а - кол-во уровней иерархии измерения j.

Разреженный гиперкуб данных

Наполнение гиперкуба данными при недостаточном количестве исходных данных приводит к образованию пустых ячеек. Гиперкубы данных с большим количеством пустых ячеек называют разреженными.

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

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

Заметим, что при оператор принимает значение 0, если ячейка, соответствующая множеству пуста и 1 в противном случае. Степень разреженности гиперкуба в целом: ,

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

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

Бинарное представление

Для вычисления значения оператора может быть использована модель бинарного представления гиперкуба данных (Рис. 4).


Рис. 4. Бинарное представление гиперкуба данных

Бинарное представление гиперкуба данных представляет собой гиперкуб , структура которого в точности повторяет структуру гиперкуба данных . Однако вместо значений, содержащихся в ячейках гиперкуба данных , ячейки бинарного гиперкуба содержат: 1 - если соответствующая ячейка содержит числовое значение,
0 - если соответствующая ячейка пуста.

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

Значение оператора может быть вычислено как сумма значений бинарного гиперкуба : ,

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

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

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

Выборка данных

Процесс построения запроса на выборку данных из гиперкуба данных может быть представлен в виде модели сетевого графа.

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


Рис. 5. Построение запроса

Множество ребер графа V представляет собой набор пар вершин . Ребро графа , таким образом, соединяет j-ю вершину слоя - c k-й вершиной слоя - .

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

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

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

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

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

Карта заполненности гиперкуба данных


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

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

Одномерная проекция

На рис. 6 представлен пример одномерной проекции бинарного представления разреженного гиперкуба данных в виде картограммы. Цветовая градация территориальных объектов соответствует количеству данных в гиперкубе. В качестве измерения для построения проекции выбрана ось территориальных объектов.


Рис. 6. Одномерная картографическая проекция бинарного представления разреженного гиперкуба данных

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

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


Рис. 7. Одномерная проекция бинарного представления гиперкуба данных.

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

Двумерная проекция

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


Рис. 8. Двумерная карта заполненности

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

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

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

Трехмерная проекция

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

Рис. 9. Трехмерная карта заполненности

На рис. 9 представлены примеры трехмерных карт заполненности многомерной базы данных, включающей следующие измерения:

  • территориальные объекты (субъекты федерации) (OY);
  • показатели (OX);
  • время (года) (OZ);
  • тип местоположения учебных заведений (городское/сельское)

Ось Х соответствует показателям, ось Y - территориальным объектам, ось Z - времени. Цвет и размер графического примитива - шарика соответствует наличию данных по четвертому измерению: большой зеленый шарик показывает наличие данных, соответствующих всем меткам измерения, шарик меньшего размера - только одной метке, отсутствие шарика - отсутствие данных.

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

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

Обеспечение доступа к данным


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

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

Оценка эффективности пошагового конструктора запросов

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

Эффективность работы пошагового конструктора запросов может быть оценена как величина, обратная среднему времени результативного запроса: , ,

где - время, затраченное на фиксацию метки j-го измерения при формировании i-го запроса, - время отклика системы на i-й запрос, N - число сформированных запросов, R - число результативных запросов, n -число измерений гиперкуба данных.

Принимая и усредняя по , получим .

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


Рис. 10. Эффективность пошагового конструктора запросов

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

Оптимизация пошагового конструктора запросов

Работа пошагового конструктора запросов может быть представлена в виде модели сетевого графа (рис. 5). Сопоставим каждой вершине графа число , где и - множества фиксированных измерений и меток соответственно. Множества и соответствуют пути пользователя w к вершине . Таким образом, вершине графа может быть сопоставлено несколько значений , в зависимости от множества ранее фиксированных меток , т.е. пути, которым пользователь попал в вершину .

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

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

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

Рассмотрим процесс формирования запроса с помощью модели сетевого графа . Начальная вершина графа соответствует началу процедуры формирования запроса и отсутствию фиксированных меток. Сопоставим начальной вершине графа число - значение оператора , где . Случай является тривиальным (гиперкуб не содержит данных). Вершинам первого слоя сопоставим значения , где . Таким образом, вершины первого слоя графа будут содержать значения оператора , соответствующие меткам . Отметим, что для некоторых значений число может принимать значение 0. Это означает, что данной метке соответствуют лишь пустые ячейки гиперкуба данных и путь, идущий через эту вершину ложен. Отбросим вершины со значением , предоставив пользователю для фиксации множества допустимых значений T,P, являющихся подмножествами множеств возможных значений для фиксации D,M.

На первом шаге формирования запроса пользователь фиксирует метку измерения , перемещаясь, таким образом, в вершину графа , соответствующую фиксированной метке . Сопоставим вершинам второго слоя графа значения оператора , где , .

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

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


Рис. 11. Алгоритм оптимизации формирования пользовательского запроса.

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

Агрегация разреженного гиперкуба данных


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

Агрегация данных является одним из ключевых понятий технологии OLAP. Именно формирование агрегативов (предварительное или динамическое) делает возможным проведение операций углубления (Drill-down) и свертки (Roll-up) при проведении анализа данных. Существует несколько традиционных методов агрегации (табл. 1).


Рис. 12. Иерархическое измерение

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

SUMСуммирование детализированных данных
WSUMВзвешенная сумма
MIN (MAX)Минимальное (максимальное) значение
AVERAGEСреднее значение
WAVERAGEВзвешенное среднее
Таблица 1. Методы агрегации

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

На рис. 13 представлена картограмма некоторого показателя, характеризующего уровень информатизации образования субъектов федерации, входящих в состав Приволжского федерального округа РФ. Цветовая подкраска соответствует величине показателя, белый цвет обозначает отсутствие данных по данному показателю ("белые пятна"). Значения показателя, являются, таким образом, первичными данными на уровне субъектов федерации в иерархическом измерении территориальных объектов. Представим, что нам необходимо произвести агрегацию первичных данных по измерению территориальных объектов и получить значение показателя для следующего уровня иерархии - федерального округа.


Рис. 13. Информатизация Приволжского федерального округа

Использование стандартных методов агрегации в этом случае приводит к весьма сомнительным результатам. Так, например, применение метода суммирования является невозможным в силу отсутствия данных по 7 объектам из 14, и полученный результат будет весьма далек от действительности. Возможно применение метода вычисления среднего значения, однако использование полученного результата в процессе анализа будет не вполне корректным.

При решении серьезных аналитических задач аналитику важно знать не только значение показателя, но и то, насколько он может доверять полученному значению. Вычисление агрегатива по методу среднего значения при наличии первичных данных по всем значениям нижнего уровня в иерархии дает 100%-ную достоверность, т. к. нет причин полагать, что это среднее значение могло быть чем-либо искажено. В нашем же случае достоверность полученного результата можно оценить лишь как 50% (наличие данных по 7-ми объектам из 14).

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

Опишем предлагаемый метод формально. Пусть мы имеем иерархическое измерение с N уровнями. Первичные данные соответствуют нижнему уровню иерархии (). Сопоставим каждой i-ой метке нижнего уровня иерархии величину , характеризующую степень достоверности фактов следующим образом (рис.14):
=1, в случае если существует факт , соответствующий этой метке и
=0, если такового факта не существует.


Рис. 14. Агрегация разреженного гиперкуба данных

Вычисление агрегата на следующем уровне иерархии () производится по формуле: , где - количество фактов, соответствующих меткам, являющимся дочерними по отношению к метке j.

Вычисление уровня достоверности , соответствующего агрегату , производится по формуле: , где - количество меток, являющихся дочерними по отношению к метке j.

Обобщая, получим формулы вычисления агрегативов на остальных уровнях иерархии:
, ,

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

Заключение


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

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

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

Программные средства выполнены в виде набора компонент, реализованных на платформе Java 2, которые могут быть использованы как по отдельности, так и в рамках единой информационной системы, а также быть интегрированы в другие информационные системы для обеспечения и поддержки необходимого функционала. Ознакомиться с компонентами можно на сайте автора: http://olap.iot.ru.

В качестве перспектив рассмотренных методов можно отметить следующие:

  • интеграция предложенных методов с системами добычи и интеллектуального анализа данных (Data Mining);
  • развитие методов визуального представления гиперкубов данных для создания графических интерфейсов к многомерным базам данных и использования систем виртуальной реальности.

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

Литература


  1. Гусева Т.И., Заботнев М.С., Кузнецов Ю.М., Кулагин В.П., Симонов А.В. и др. под общ. ред. С.И. Маслова. Информатизация образования: направления, средства, технологии. - Москва, Издательство МЭИ, 2004. - 868 с.
  2. Заботнев М.С.. Многомерная модель представления данных по образовательной статистике // Телематика -2003. Труды Х Всероссийской научно-методической конференции. - Санкт-Петербург, 2003. - с. 245-246.
  3. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа данных: OLAP и Data Mining - СПб.: БХВ-Петрбург, 2004. - 336 с.
  4. Когаловский М.Р. Энциклопедия технологий баз данных. - М.: Финансы и статистика, 2002.-800с.
  5. Lipski W. Jr. On Databases with Incomplete Information. - Journal of the ACM, 1981. v. 28, No. 1.
  6. Pawlak Z. Rough Sets.- ICS PAS Reports, Warszawa, 1981, No. 431.
  7. Нариньяни А. С. Средства моделирования неполноты данных в аппарате представления знаний.- В кн.: Представление знаний и моделирование процесса понимания. Новосибирск: ВЦ СО АН СССР, 1980.
  8. Цаленко М.Ш. Моделирование семантики в базах данных. - М.: Наука. Гл. ред. физ-мат. лит., 1989. - 288 с. - (Проблемы искусственного интеллекта).
  9. Калиниченко Л.А., Рывкин В.М. Машины баз данных и знаний. М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 226 с.
  10. Бениаминов Е.М. Алгебраические методы в теории баз данных и представлении знаний. - М.: Научный мир, 2003, 184 с.

 Обсудить на форуме   Написать вебмастеру 

© 2001 Interface Ltd