ПРЕДСТАВЛЕНИЕ И ПРИМЕНЕНИЕ ЗНАНИЙ О КУБАХ-КОНЦЕПТАХ ДЛЯ ПОДДЕРЖКИ АДАПТИВНОГО МАНИПУЛИРОВАНИЯ ОБЪЕКТАМИ АНАЛИЗА OLAP

Полный текст

Повышение эффективности аналитической обработки больших объемов данных для принятия обоснованных решений требует развития средств адаптивного манипулирования объектами анализа в технологии OLAP (On-line analytical processing) [1-5]. Формирование каталога показателей дает возможность систематизировать объекты анализа, но не позволяет выполнять их совместную аналитическую обработку [2; 6]. Построение онтологии предметной области дает возможность оперировать всеми объектами, включенными в онтологию, но не позволяет оперативно формировать запросы в ходе аналитического эксперимента [7; 8]. В авторских работах [9; 10], построения интегральной аналитической модели предметной области предложен метод концептуального OLAP-моделирования, позволяющий строить интегральную OLAP-модель предметной области в виде решетки многомерных кубов на основе экспертных знаний об объектах анализа и возможности их совместной аналитической обработки [11; 12]. Для реализации оригинального метода разработаны алгоритмы поиска кубов-концептов на основе контекста предметной области и построения концептуальной решетки OLAP-кубов [5; 6]. С целью поддержки адаптивного манипулирования объектами анализа интегральной OLAP-модели актуальной становится задача определения оптимального куба-концепта на множестве всех объектов анализа предметной области. В работе предлагаются продукционная модель представления знаний о кубах-концептах, упорядоченных отношением Галуа в виде концептуальной решетки кубов, и алгоритм определения оптимального куба-концепта для частной аналитической задачи на множестве всех доступных объектов анализа. Разработанные средства представления и применения знаний о кубах-концептах позволяют осуществлять адаптивное манипулирование объектами анализа OLAP, что значительно повышает эффективность аналитической обработки многомерных данных и способствует обнаружению новых знаний для принятия решений. Интегральная аналитическая модель предметной области в виде концептуальной решетки OLAP-кубов. Интегральная аналитическая модель предметной области строится путем применения анализа формальных понятий к аналитическим объектам в терминах технологии OLAP. Основу интегральной OLAP-модели составляет множество объектов анализа, которые используются для построения OLAP-кубов: множество показателей F = {f1, f2, ..., fm} и множество измерений D = {dj, d2, ..., dn}. Между элементами множеств F и D определяется отношение сопоставимости R - возможность совместной аналитической обработки показателей и измерений. R с FxD, (f, dj) є R, если показатель f может быть проанализирован по измерению dj. Тройка (F, D, R), в соответствии с теорией анализа формальных понятий [13; 14], представляет собой формальный контекст K. Формальный контекст отражает знания эксперта об объектах анализа предметной области и о возможности их совместной аналитической обработки. На основе формального контекста K определяется множество концептов - OLAP-кубов (кубов-концептов) по признаку сопоставимости объектов анализа. Для произвольных X с F и Y с D определяется операция «штрих» следующим образом: X ' = {d є D | Vf є X, (fRd)}; Y ' = {f є F | Vd є Y (fRd)}. Пара (A, B), где A с F, B с D такие, что A = B' и B = A', называется кубом-концептом контекста K. Множество A состоит из показателей одинаковой размерности, которые могут быть проанализированы по всем измерениям из B. (A, B) - многомерный куб, полный относительно добавления показателей той же размерности и состава измерений. Множество показателей A представляет объем куба-концепта, а множество измерений B - содержание куба-концепта. Множество всех кубов-концептов частично упорядочено отношением Галуа: (Ab Bi) < (A2, B2), если Ai с A2 и B2 с B1 [15]. В этом случае, (A1, B1) - подкуб (A 2, B2), а (A2, B2) - надкуб (A 1, B1). Множество показателей надкуба включает множество показателей под-куба, а в свою очередь, множество измерений подкуба включает множество измерений надкуба. Упорядоченное отношением подкуб-надкуб множество всех кубов-концептов образует концептуальную решетку OLAP-кубов и представляет собой интегральную аналитическую модель. Модель представления знаний о концептах -OLAP-кубах Для поддержки адаптивного манипулирования объектами анализа интегральной OLAP-модели разработана продукционная модель представления знаний о кубах-концептах. Модель основана на свойствах концептуальной решетки, согласно которым: надкуб любого куба-концепта решетки содержит наибольший объем (множество показателей) и наименьшее содержание (множество измерений), а подкуб, наоборот - содержит наибольшее содержание и наименьший объем. То есть, при переходе по ребру решетки от подкуба к надкубу происходит расширение объема и сокращение содержания и аналогично, при переходе по ребру решетки от надкуба к подкубу происходит сокращение объема и расширение содержания. Таким образом, модель знаний, представляющая концептуальную решетку кубов, отражает отношения между кубами-концептами решетки и между объемом и содержанием кубов-концептов. Разработанная модель содержит правила вида: S:F:N: IF < (Acur = Asuper) & (P П X = 0) > > THEN < Acur “^Asub >; (1) S:D:N: IF < (Bcur = Bsub) & (Q n Y = 0) > > THEN < Bcur Bsuper >; (2) S:F:N: IF < Acur = A > THEN < Bcur -^B >; (3) S:D:N: IF < Bcur = B > THEN < Acur A >. (4) Здесь S - уникальное в базе знаний имя правила; F, D - указатель назначения, характеризующий зону действия правила для показателей и измерений соответственно; N - приоритет применения правила, указывающий на преимущественное применение правила при разрешении конфликтов; A cur - начальное множество показателей для процедуры логического вывода; Asub - объем (множество показателей) подкуба; Asuper -объем (множество показателей) надкуба; P - множество показателей, удаляемых из объема надкуба при переходе к подкубу; X - множество показателей, требуемых для аналитической обработки; Bcur - начальное множество измерений для процедуры логического вывода; Bsuper - содержание (множество измерений) надкуба; Bsub - содержание (множество измерений) подкуба; Q - множество измерений, удаляемых из подкуба при переходе к надкубу; Y - множество измерений, требуемых для аналитической обработки. Символ ^ обозначает переход от одного куба-концепта к другому. Правила (1) и (2) описывают переход по ребру концептуальной решетки. Правила типа (3) и (4) описывают отношение между множеством показателей и множеством измерений куба-концепта решетки. Правила типа (1) и (2) имеют более высокий приоритет по сравнению с правилами типа (3) и (4). Другими словами, приоритетным является переход от одного куба-концепта решетки к другому. В случае, если ни одно правило перехода не может быть выполнено, осуще 52 Математика, механика, информатика ствляется подстановка множеств показателей или измерений соответственно. Принципы поддержки адаптивного манипулирования объектами анализа на основе продукционной модели представления знаний. Интегральная аналитическая модель, построенная в виде концептуальной решетки OLAP-кубов, позволяет пользователю проводить аналитические эксперименты на множестве всех доступных объектов анализа предметной области [12]. Свойства концептуальной решетки позволяют определять дополнительные показатели и измерения, которые могут быть проанализированы вместе с выбранными пользователем объектами анализа. Поэтому поддержка адаптивного манипулирования объектами анализа заключается в формировании дополнительных показателей и измерений для оперативной аналитической обработки. Согласно свойствам концептуальной решетки, множество всех кубов-концептов, удовлетворяющих текущему запросу пользователя, представляет собой подрешетку интегральной модели. Куб-концепт под-решетки, расположенный на самом верхнем уровне содержит максимальный набор дополнительных показателей - максимальный куб-концепт для текущего запроса. В свою очередь, куб-концепт подрешетки, расположенный на самом нижнем уровне содержит максимальный набор дополнительных измерений -минимальный куб-концепт для текущего запроса. Таким образом, определение максимального и минимального кубов-концептов для текущего пользовательского запроса и формирование максимальных наборов дополнительных объектов анализа - основная задача логического вывода. Процедура определения дополнительных объектов анализа для текущего запроса соответствует прямой цепочке логического вывода и заключается в последовательном сравнении условий правила (антецедента) и выполнении соответствующих действий (консе-квента) [16]. Основными параметрами процедуры определения дополнительных объектов анализа являются текущий запрос пользователя, максимальный куб-концепт и минимальный куб-концепт. В начальный момент работы текущий запрос пользователя представляет собой пару (0, 0), максимальный куб-концепт - это куб-концепт, расположенный на самом верхнем уровне решетки кубов, минимальный куб-концепт - это куб-концепт, расположенный на самом нижнем уровне решетки кубов. При добавлении показателя в текущий запрос, начальное состояние определяется как множество показателей максимального куба-концепта подрешетки, соответствующей запросу на предыдущем шаге. В качестве входных параметров передаются множество требуемых показателей X и начальное множество показателей Acur. Результат вывода - множество измерений Bcur, определяющее содержание минимального куба-концепта подрешетки, соответствующей запросу на текущем шаге. При добавлении измерения в текущий запрос начальное состояние определяется как множество измерений минимального куба-концепта подрешетки, соответствующей за просу на предыдущем шаге. В качестве входных параметров передаются множество требуемых измерений Y и начальное множество измерений Bcur. Результат вывода - множество показателей Acur, определяющее объем максимального куба-концепта подрешетки, соответствующей запросу на текущем шаге. Алгоритм определения оптимального куба-концепта для частной аналитической задачи. Исходя из свойств концептуальной решетки и принципов поддержки адаптивного манипулирования объектами анализа, разработан алгоритм определения оптимального куба-концепта для частной аналитической задачи на множестве всех доступных объектов анализа предметной области. Блок-схема алгоритма представлена на рис. 1. Алгоритм заключается в последовательном добавлении объектов анализа в пользовательский запрос и определения объема и содержания оптимального куба-концепта на основе применения правил вывода. Работа алгоритма начинается с определения начального состояния переменных, участвующих в процессе поиска оптимального куба-концепта. Объем и содержание пользовательского запроса определяются как пустые множества. Содержание оптимального куба-концепта Xopt равно множеству показателей интегральной модели, объем оптимального куба-концепта Yopt равен множеству измерений интегральной модели. Asup и Bsup определяются как содержание и объем максимального куба-концепта решетки, который соответствует точной верхней границе множества кубов-концептов B(K) - sup(B(K)). Ainf и Binf определяются как содержание и объем минимального куба-концепта решетки, который соответствует точной нижней границе множества кубов-концептов B(K) -inf(B(K)). Затем алгоритм ожидает выбора объекта анализа пользователем. Если объект анализа не был выбран, то алгоритм прекращает свою работу. После выбора объекта анализа определяется его тип, путем проверки вхождения k в множество Xopt. Если выбранный объект принадлежит содержанию оптимального куба-концепта, то k добавляется к содержанию пользовательского запроса X, тип объекта анализа t для выбора правил определяется как ‘F’ и значение Ainf устанавливается равным Asup. Если выбранный объект принадлежит объему оптимального куба-концепта, то k добавляется к объему пользовательского запроса Y, тип объекта анализа t для выбора правил определяется как ‘D’ и значение Bsup устанавливается равным Binf. Если выбранный пользователем объект анализа не принадлежит оптимальному кубу-концепту, то алгоритм возвращается на этап выбора нового объекта анализа. Для выбора правил в соответствии с их приоритетом, определяется параметр n, принимающий значения 1 и 2. Затем в цикле по s, где s изменяется от 1 до мощности множества правил |L|, описывающих интегральную модель, происходит сначала выбор правила в соответствии с установленными значениями t и n, а затем проверка условий применимости правила и его выполнение. 53 Вестник СибГАУ. № 3(49). 2013 (X, Y) - запрос пользователя Xopt - содержание оптимального куба-концепта sup($(%)) - максимальный куб-концепт решетки <В(%) к - объект анализа, добавляемый пользователем в запрос ( конец j Рис. 1. Блок-схема алгоритма определения оптимального куба-концепта 54 Математика, механика, информатика dl d2 d3 d4 d5 d6 d7 d8 d9 d10 ч: о Г Автор Тип публикации Город Журнал База цитирования Грант Тип пособия Тип объекта интел. соб-ти Статус конференции f1 Число публикаций x x x x x x x f2 Число материалов конф-ий x x x x x x x x f3 Число учебных пособий x x x x x x f4 Число объектов интел. соб-ти x x x f5 Число конференций x x x x x Рис. 2. Фрагмент формального контекста научной деятельности организации При t =’D’ и n = 1 для проверки антецедента правила используется множество Bsup и объем пользовательского запроса Y. В случае выполнения условий антецедента значение Bsup меняется в соответствии с консеквентом правила и проверка правил начинается с начала цикла. При t =’D’ и n = 2 для проверки антецедента правила используется только множество Bsup. В случае выполнения условий антецедента значение Asup меняется в соответствии с консеквентом правила, содержание оптимального куба Xopt становится равным Asup, заканчивается проверка правил и алгоритм переходит на этап выбора нового объекта анализа. Таким образом, алгоритм обеспечивает поддержку построения пользовательского запроса для частной аналитической задачи в соответствии с интегральной OLAP-моделью и формирует оптимальный куб-концепт (Xopt, Yopt) на каждом шаге построения пользовательского запроса. Объем найденного оптимального куба-концепта соответствует нижнему кубу-концепту подрешетки кубов, удовлетворяющих пользовательскому запросу, и содержит максимальное количество измерений для совместной аналитической обработки с текущим запросом пользователя. Содержание найденного оптимального куба-концепта соответствует верхнему кубу-концепту подрешетки кубов, удовлетворяющих пользовательскому запросу, и содержит максимальное количество показателей для совместной аналитической обработки с текущим запросом пользователя. Адаптивное манипулирование объектами анализа на основе интегральной OLAP-модели научной деятельности организации. Рассмотрим реализацию принципов адаптивного манипулирования объектами анализа и работу алгоритма поиска оптимального куба-концепта для интегральной OLAP-модели научной деятельности организации. На рис. 2 представлен фрагмент формального контекста научной деятельности организации, строки которого соответствуют показателям, а столбцы -измерениям. Используя сокращенные обозначения, получим соответственно: F = {f1, f 2, f 3, f 4, f 5} и D = {d1, d2, d3, d4, d5, d6, d7, d8, d9, d10}. Отношение R записывается следующим образом: R = {f1, d1), (f1, d2), (f1, d3), (/1, d4), • ••, d10)}. На рис. 3 приведена концептуальная решетка OLAP-кубов, построенная в рамках рассматриваемого формального контекста и представляющая интегральную аналитическую модель научной деятельности. На рис. 4 проиллюстрировано соответствие подре-шетки запросу пользователя на каждом шаге логического вывода. di, d2, ds, d4, ds, de, dj, ds, dt).: dm Рис. 3. Концептуальная решетка OLAP-кубов научной деятельности организации Разработанные средства представления и применения знаний о кубах-концептах позволяют осуществлять адаптивное манипулирование объектами анализа предметной области. Возможность выявления аналитических зависимостей между объектами анализа позволяет значительно повысить эффективность аналитической обработки данных и способствует обнаружению новых знаний для принятия управленческих решений. 55 Вестник СибГАУ. № 3(49). 2013 Рис. 4. Соответствие подрешетки концептуальной OLAP-модели запросам пользователя: а) - (0, 0); b) - (f2, 0); c) - (£2, d7); d) - ({f1, f2}, d7); e) - ({f1, f2, f5}, d7); f) - ({f1, f2, f5}, {d6, d7})

Об авторах

А. В. Коробко

Институт вычислительного моделирования СО РАН

Email: lynx@icm.krasn.ru
660036, Красноярск, Академгородок, 50, стр. 44

Т. Г. Пенькова

Институт вычислительного моделирования СО РАН

660036, Красноярск, Академгородок, 50, стр. 44

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

Дополнительные файлы