Методика расширения возможностей визуального OLAP-анализа

Авторы: Волович Михаил Евгеньевич, Зизганов Илья Сергеевич

.

Рубрика: Технические науки

Страницы: 85-93

Объём: 0,55

Опубликовано в: «Наука без границ» № 4 (21), апрель 2018

Скачать электронную версию журнала

Библиографическое описание: Волович М. Е., Зизганов И. С. Методика расширения возможностей визуального OLAP-анализа // Наука без границ. 2018. № 4 (21). С. 85-93.

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

Введение

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

Подходы к сокращению размерности входных данных

В настоящее время существует большое количество подходов к решению задачи сокращения размерности входных данных. Методы решения основаны на статистических оценках, корреляционном анализе и других математических подходах, которые позволяют оценить степень взаимосвязи данных с целями анализа. Goudarzvand S. в [3] исследует возможность обнаружения скрытых закономерностей в данных с использованием алгоритмов поиска ассоциативных правил и иерархических алгоритмов кластеризации. Buda T. S., Murphy J., Kristiansen M. Towards в [5] предлагают инструмент для анализа зависимостей в реляционной базе данных. Chakravorty A. в [4] рассматривает использование алгоритма G-means и предлагается представлять каждый набор данных через его центроид, что в результате приводит к значительному сокращению избыточности данных. Сокращение объема данных достигает в данном случае 90 %. В [1, 6, 10] рассматриваются методы: Singular Value Decomposition (SVD), Principal Component Analysis (PCA), Self-Organizing Map (SOM), FastICA. В [7] авторы предлагают использовать автоассоциативную сеть. В [8] авторы Янцен Д. Д., Цымблер М. Л. предлагают алгоритм репрезентативного сэмплинга. Бондарев А. Е., Галактионов В. А. в [9] предлагают построение технологической цепочки алгоритмов обработки многомерного объема данных.

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

Предлагаемая методика выявления скрытых взаимосвязей в реляционных структурах данных

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

  1. Строится представление, описывающее исходную реляционную модель данных;
  2. Алгоритм на основе формулы (3) оценивает энтропию входящих в представление таблиц;
  3. Алгоритм ранжирует таблицы по убыванию в зависимости от информационного содержания и исключает из модели те, у которых информационное содержание ниже установленного порога значимости, тем самым выделяя и исключая из модели малозначимые признаки;
  4. На следующем шаге алгоритм кластеризует данные и строит зависимость количества кластеров от размерности пространства кластеризации, которая способствует быстрому выявлению избыточных признаков;
  5. Лицо, принимающее решение (ЛПР), исключает избыточные признаки, оставляя те из них, которые, по его мнению, отвечают целям анализа. На основе отобранных признаков алгоритм строит таблицу. Из нее ЛПР отбирает признаки, которые будут являться индексами массива – измерениями (dimensions) OLAP-куба, и признаки, которые будут являться значениям элементов массива – мерами (measures) OLAP-куба. Далее построенная таблица передается в алгоритм кластеризации K-means;
  6. K-means кластеризует данные пространства Rm, компонентами векторов которого являются меры (measures), отобранные ЛПР на предыдущем шаге. В результате формируется структура кластеров, которая после загрузки в OLAP-куб, становиться его дополнительным измерением.

Созданное измерение позволяет проводить drill-up/drill-down операции по иерархиям измерений и формировать дополнительные срезы куба, основанные на информации, содержащейся в структуре кластеров. Использование дополнительного измерения добавляет новые возможности для проведения OLAP-анализа и повышает качественный уровень системы в целом.

Сокращение незначащих признаков на основе информационного содержания реляционной модели

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

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

Формула Шеннона,     (1)

где n – множество возможных событий;
pi – вероятность i-го события.

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

Расчет средней энтропии,        (2)

где n – множество значений признака;
pi – вероятность i-го значения признака.

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

Реляционная модель данных,                   (3)

где  – количество признаков;
n – множество значений признака;
pi – вероятность i-го значения признака.

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

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

Сокращение избыточных признаков с использованием методов неиерархической кластеризации

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

Алгоритм                (4)

где – вектор признакового пространства;
n – размерность вектора.

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

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

Формирование дополнительного измерения OLAP-куба с использованием алгоритмов неирерхической кластеризации

Следующим шагом перед процессингом в гиперкуб является кластеризация данных в пространстве, составленном из признаков, выбранных в качестве мер (measures). В результате это дает формирование нового измерения (dimension) OLAP-куба, которое будет являться дополнительным критерием для последующего анализа. Подобного результата невозможно добиться при работе с OLAP-кубом посредством формирования срезов. В качестве алгоритма кластеризации реализована одна из разновидностей K-means, обеспечивающая наибольшее быстродействие [11, 14, 15]. Объекты подмножеств предполагают их представление в виде точек m-мерного пространства Rm. В алгоритме используется евклидово расстояние ( ):

Алгоритм                            (5)

где  – вектор пространства Rm;
m – размерность вектора.

Задача выбора начальных центроидов решается с использованием алгоритма, созданного Дэвидом Артуром и Сергеем Вассильвитским [12].

При оценке качества кластеризации используется индекс оценки силуэта (Silhouette index), основанной на силуэтной статистике, введенной Кауфманом и Руссо [13,16]. Значение индекса делится на три интервала:

  • низкое качество: от -1 до 0,2;
  • среднее качество: от 0,2 до 0,5;
  • хорошее качество: от 0,5 до 1.

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

Анализ результатов

Эксперименты проводились с использованием следующей платформы: двух ядерный процессор Intel™Core™i5-2410M 2.3GHz; объем оперативной памяти 16 Гб; СУБД Oracle 11.2.0.3. Собранная статистика по таблицам базы данных приводится в табл. 1.

Таблица 1

Таблицы реляционной модели

Таблица

Количество строк

Средняя длина строки

Количество столбцов

MODELPRODUCTS

113

28

5

PRODTRANSACTIONS

202696

42

9

PRODUCTORDERS

72591

50

10

PRODUCTS

504

98

24

PRODUCTVENDORS

460

34

9

SCRAPREASONS

16

33

3

SUBCATEGORYS

37

24

4

VENDORS

104

55

8

В экспериментах используются данные, представленные реляционной моделью на рис. 1:

Реляционная модель данных

Рис. 1. Реляционная модель данных

При установленном пороге значимости 20 % алгоритм выявил 4 таблицы с наибольшим информационным содержанием, результаты приводятся в табл. 2:

Таблица 2

Таблицы с наибольшим информационным содержанием

Таблица

Оценка полного информационного содержания по формуле (3), результаты расчетов приведены на рис. 2:

Оценка полного информационного содержания

Рис. 2. Оценка полного информационного содержания 

Из 72 признаков было сокращено 20 малозначимых. Время выполнения алгоритма для данного набора данных составило 12,594 секунды.

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

Влияние размерности вектора кластеризации

Рис. 3. Влияние размерности вектора кластеризации на время выполнения 

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

Зависимость количества кластеров

Рис. 4. Зависимость количества кластеров от размерности вектора кластеризации 

Очевидно, что часть признаков, находящихся в интервалах: [1-3], [11-15], [19-37] могут быть рекомендованы к удалению, т. к. это не повлечет за собой изменения информационной насыщенности экспериментальной модели.

На следующем шаге, после сокращения избыточных признаков, алгоритм K-means в процессе работы выявил 3 кластера (табл. 3). Общее количество обработанных записей 11 136, время работы алгоритма 11,922 секунд. Время работы алгоритма оценки индекса силуэта (Silhouette index) составило 1,609 секунды. Чем ближе значение индекса оценки силуэта к 1, тем лучше данное решение распределяет объекты по кластерам, в данном случае индекс равен 0,85 и находится в интервале от 0,5 до 1, что является хорошим результатом разбиения: good separation quality: 0,85 > 0.5 

Таблица 3

Выявленные алгоритмом K-means кластеры

Номер кластера

Центройд

Количество записей

1

132,9334289

9519

2

6519,789474

38

3

1015,815104

1579 

Заключение

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

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

Список литературы

  1. Sembiring R. W., Sembiring S., Zain J. M. An efficient dimensional reduction method for data clustering //Bulletin of Mathematics. 2018. Vol. 4. No. 01. Pp. 43-58.
  2. Чумак О. В. Энтропии и фракталы в анализе данных. М.–Ижевск: НИЦ «Регулярная и хаотическая динамика», Институт компьютерных исследований. 2011.
  3. Goudarzvand S. et al. Extracting Knowledge in Data Warehouses using Fuzzy AprioriTid // Rae. 2015. Vol. 1. No. 1. P. 1.
  4. Chakravorty A. et al. A Distributed Gaussian-Means clustering algorithm for forecasting domestic energy usage // Smart Computing (SMARTCOMP), 2014 International Conference on. IEEE, 2014. Pp. 229-236.
  5. Buda T. S., Murphy J., Kristiansen M. Towards realistic sampling: generating dependencies in a relational database. 2013.
  6. Shlens J. A tutorial on principal component analysis // arXiv preprint arXiv:1404.1100. 2014.
  7. Аджемов С. С., Терешонок М. В., Чиров Д. С. Снижение размерности признакового пространства в задачах идентификации излучающих объектов по данным радиомониторинга с использованием искусственных нейронных сетей // T-Comm-Телекоммуникации и Транспорт. 2008. № 6.
  8. Янцен Д. Д., Цымблер М. Л. Алгоритм репрезентативного сэмплинга для параллельных реляционных систем баз данных // Научный сервис в сети Интернет: многообразие суперкомпьютерных миров. 2014. С. 32-40.
  9. Бондарев А. Е., Галактионов В. А. Визуальный анализ кластерных структур в многомерных объемах данных // Научная визуализация. 2016. Т. 8. №. 3. С. 1-24.
  10. Орлов А. И., Луценко Е. В. Методы снижения размерности пространства статистических данных // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. 2016. № 119.
  11. Мандель И. Д. Кластерный анализ. М. : Финансы и статистика, 1988.
  12. Arthur D., Vassilvitskii S. k-means++: The advantages of careful seeding //Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. – Society for Industrial and Applied Mathematics, 2007. Pp. 1027-1035.
  13. Kaufman L., Rousseeuw P. J. Finding groups in data: an introduction to cluster analysis. John Wiley & Sons, 2009. Vol. 344.
  14. Нейский И. М. Классификация и сравнение методов кластеризации // ББК 32.813 И 76 Составитель: Ю.Н. Филиппович. 2006. С. 130.
  15. Jain A. K., Murty M. N., Flynn P. J. Data clustering: a review //ACM computing surveys (CSUR). 1999. Vol. 31. No. 3. Pp. 264-323.
  16. Сивоголовко Е. В. Методы оценки качества чёткой кластеризации // Компьютерные инструменты в образовании. 2011. №. 4. С. 14-31.

 

Материал поступил в редакцию 20.04.2018
© Волович М. Е., Зизганов И. С., 2018