Алгоритмы формирования интегральной OLAP-модели предметной области

V. I. Ivanchura, A. P. Prokopiev OPTIMIZATION OF A TRACKER SYSTEM OF AUTOMATIC CONTROL

The paper is devoted to theoretical and practical problems of a servo system of automatic control. The dynamical system of the working body with hydraulic stacker is considered. The task of development of a simulation model of automatic control system of the working body of the Stacker is considered with the use of Matlab & Simulink program. The results of the study are presented. The proposed method of modeling of adaptive systems of control of nonlinear dynamic objects, on the example of the tracker system of a stacker, with the account of dynamics of processes in the drive, in which the operating deviations decrease.

Keywords: automatic control, sensor system, structural and parametric optimization, system stability.

© Иванчура В. И., Прокопьев А. П., 2011

УДК 004.6

А. В. Коробко, Т. Г. Пенькова

АЛГОРИТМЫ ФОРМИРОВАНИЯ ИНТЕГРАЛЬНОЙ ОЬАР-МОДЕЛИ ПРЕДМЕТНОЙ ОБЛАСТИ*

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

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

Эффективность оперативной аналитической обработки данных на основе технологии OLAP (On-Line Analytical Processing) во многом определяется адекватностью модели предметной области [1]. Как правило, для оперативной аналитической обработки данных создается набор локальных OLAP-моделей, представляющий собой фрагментарную аналитическую модель предметной области [2-4]. С точки зрения теории и практики интересно построение интегральной аналитической модели, объединяющей множество частных OLAP-моделей, позволяющей манипулировать всеми аспектами и характеристиками анализируемого процесса и охватывающей максимальное число решаемых аналитических задач.

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

Существующие на сегодняшний день алгоритмы генерации формальных концептов подробно рассмотрены в работах [6-9]. Как правило, эти алгоритмы

разработаны без учета требований быстродействия и не ориентированы на обработку объектов OLAP-анализа.

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

Метод концептуального OLAP-моделирования предметной области. Метод концептуального OLAP-моделирования основан на интеграции технологии оперативной аналитической обработки многомерных данных и анализа формальных концептов [5; 10; 11].

Согласно предложенному методу, интегральная OLAP-модель предметной области представляет собой концептуальную решетку многомерных кубов. Основу интегральной модели составляет множество объектов оперативной аналитической обработки данных: множество показателей F = {/1,/2, • ••,/т} и множество измерений Б = {й?ь й?2, ..., ё„}. Количественные характеристики анализируемого процесса образуют множество показателей, аспекты анализа предметной области образуют множество измерений.

* Работа выполнена при финансовой поддержке гранта ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы» (ГК № 02.740.11.0621 от 29 марта 2010 г.).

Между элементами множеств Е и Б определяется отношение сопоставимости Я - возможность совместной аналитической обработки показателей и измерений; Я с Е х Б, /, й,) е Я, если показатель / может быть проанализирован по измерению й,. Тройка (Е, Б, Я), в соответствии с методами анализа формальных концептов [12], представляет собой формальный контекст К. Формальный контекст отражает знания эксперта об объектах анализа предметной области и о возможности их совместной аналитической обработки.

На основе формального контекста К определяется множество кубов-концептов по признаку сопоставимости объектов анализа.

Для произвольных X с Е и Г с Б определяется операция «штрих» следующим образом:

X' = {й е Б | V/е X(Яй)};

У' = /е Е | Vй е Г /Яй)}.

Пара (А, В), где А с Е, В с Б такие, что А = В' и В = А', называется кубом-концептом контекста К. Множество А состоит из показателей одинаковой размерности, которые могут быть проанализированы по всем измерениям из В. Пара (А, В) - многомерный куб, полный относительно добавления показателей той же размерности и состава измерений. Это означает, что невозможно включить в такой ОЬЛР-куб дополнительный показатель без уменьшения числа измерений, т. е. в рамках построенного формального контекста не существует других показателей, сопоставимых с тем же набором измерений. Множество показателей А представляет объем куба-концепта, а множество измерений В - содержание куба-концепта.

Множество всех кубов-концептов частично упорядочено отношением подкуб-надкуб: (А1, В1) < (А2, В2) если А1 с А2 и В2 с В1. В этом случае будем говорить, что (А1, В1) - подкуб (А2, В2), а (А2, В2) - надкуб (А1, В1). Множество показателей надкуба включает множество показателей подкуба, а, в свою очередь, множество измерений подкуба включает множество измерений надкуба. Упорядоченное отношением под-куб-надкуб множество всех кубов-концептов образует решетку ОЬЛР-кубов, которая представляет собой интегральную ОЬЛР-модель предметной области.

Для реализации метода концептуального ОЬЛР-моделирования разработаны алгоритмы поиска кубов-концептов на основе контекста предметной области и построения концептуальной решетки ОЬЛР-кубов.

Алгоритм поиска кубов-концептов на основе контекста предметной области. Алгоритм поиска кубов-концептов на основе контекста предметной области представляет собой итеративную реализацию метода Крайеса [6].

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

На первом шаге алгоритма множество кубов-концептов B (K) содержит точную верхнюю границу множества кубов-концептов (супремум) - куб-

концепт (F, 0), где F - множество всех показателей контекста K.

Затем путем перебора измерений dj из D определяется множество показателей {й,}', доступных для совместной аналитической обработки с каждым измерением dj, и сравнивается с объемом Ak куба-концепта (Ak, Bk) из B (K), где k = 1,|B (K)|, где |B (K)| - мощность множества B (K). При этом индекс j определяется, как max {j | dj e Bk} + 1 - следующий за максимальным индексом измерений из содержания Bk куба-концепта (Ak, Bk).

Если сформированный объем {dj}' и объем Ak существующего куба-концепта не пересекаются ({d,}' n Ak = 0), то рассматривается следующее измерение. Если объемы совпадают ({d,}' n Ak = Ak), то содержание Bk куба-концепта (Ak, Bk) дополняется измерением dj и алгоритм переходит к рассмотрению следующего измерения. Процесс добавления измерений к содержанию ранее обнаруженного куба-концепта называется наполнением куба-концепта.

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

куб-концепт (^new^ Bnew), где Anew {dj} n Ak, Bnew dj

и алгоритм переходит к проверке уникальности найденного куба-концепта.

Для проверки уникальности куба-концепта, путем перебора dt из D определяется множество показателей {d,}', доступных для совместной аналитической обработки с каждым измерением d,, и сравнивается с объемом Anew потенциально нового куба-концепта. Индекс i = 1, j - 1 при условии, что d, <£ Bk.

Если все показатели Anew могут быть совместно проанализированы с измерением d,, то объем Anew найденного куба-концепта (Anew, Bnew) не является уникальным и алгоритм переходит к сравнению объема Ak куба-концепта (Ak, Bk) с множеством показателей {dj + i}'.

Если Anew содержит хотя бы один показатель, который не может быть совместно проанализирован с измерением d, то объем Anew найденного куба-концепта (Anew, Bnew) является уникальным относительно измерения di и алгоритм продолжает проверку уникальности объема потенциально нового куба-концепта относительно измерения d, + 1.

Уникальность объема Anew потенциально нового куба-концепта относительно всех проверенных измерений d, означает, что B (K) не содержит куба-концепта с таким набором показателей.

Далее для найденного уникального объема Anew определяется Bnew, как объединение содержания Bk и измерений d,. Проверенный новый куб-концепт (Anew, Bnew) добавляется в B (K) и алгоритм переходит к сравнению объема Ak куба-концепта (Ak, Bk) с множеством показателей {dj + 1}'.

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

В(К) - множество кубов-концептов контекста К F- множество показателей контекста К

Вп<™ - содержание нового куба-концепта

\ >1 /

\ 1 В(К}\ /

^ конец ^

Рис. 1. Алгоритм поиска кубов-концептов на основе контекста предметной области

Все кубы-концепты контекста К считаются полными только по завершении работы алгоритма.

Алгоритм построения концептуальной решетки OLAP-кубов. Алгоритм построения концептуальной

Таким образом, просматривая множество показате- решетки OLAP-кубов основан на алгоритме формиро-лей и измерений формального контекста предметной вания концептуальной решетки NEIGHBORS [7-9]

области, формируется множество кубов-концептов.

(рис. 2).

^ начало ^

L(K) =0

L(K) I В(К) х В(К) - решетка кубов

В(К) - множество кубов-концептов контекста К

Рис. 2. Алгоритм построения концептуальной решетки OLAP-кубов

Задача данного алгоритма заключается в формировании пар кубов-концептов, находящихся в отношении частичного порядка подкуб-надкуб. Множество пар кубов-концептов из В(К) х В(К), упорядоченное отношением подкуб-надкуб, образует решетку ОЬЛР-кубов Ь(К) с В(К) х В(К). Согласно методам анализа формальных концептов, свойства решетки такие, что если кубы-концепты X = (А*, Вх) и Г = (Ау, Ву) находятся в отношении подкуб-надкуб X < Г, то Ах с Ау и Ву с Вх. Исходя из данного свойства решетки, точная нижняя граница множества В(К) (инфимум) не имеет подкуба. Следовательно, алгоритм заключается в поиске надкубов для каждого куба-концепта (Ак, Вк) из множества В(К), начиная с ин-фимума и определении ближайшего надкуба, путем сопоставления объемов кубов-концептов.

На первом шаге алгоритма решетка кубов Ь(К) не содержит ни одной пары кубов-концептов из В(К) х В(К).

Затем для каждого куба-концепта (Ак, Вк) из множества В(К) определяется шш = Е\Ак - контрольное множество показателей для проверки степени близости текущего куба-концепта и его потенциального надкуба.

Путем перебора показателей / е Е, где /' = 1,|Е| при условии, что / г Ак, формируется потенциальный надкуб (Аир, Вир) по следующему принципу: Вир = (Аки/})', Аир = (Вир)'.

На следующем шаге с помощью контрольного множества шш проверяется степень близости найденного потенциального надкуба к текущему кубу-концепту. Если объем Аир потенциального надкуба помимо показателей из Ак и {/} содержит другие показатели из множества шт, то из контрольного множества исключается показатель /, найденный потенциальный надкуб не является ближайшим для куба-концепта (Ак, Вк) и алгоритм переходит к рассмотрению следующего показателя / + 1 е Е. Иначе, найденный куб-концепт (Аир, Вир) считается надкубом для (Ак, Вк) и пара ((Аир, Вир), (Ак, Вк)) добавляется в решетку Ь(К) и алгоритм переходит к рассмотрению следующего показателя / + 1 е Е.

После рассмотрения всех показателей / е Е алгоритм переходит к обработке следующего куба-концепта (Ак + 1, Вк + 1) из множества В(К).

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

При изменении контекста предметной области, связанного с добавлением (удалением) объектов анализа или добавлением (удалением) отношения сопоставимости между показателями и измерениями, выполняется адаптация концептуальной решетки кубов

по описанным выше алгоритмам поиска кубов-концептов и формирования решетки OLAP-кубов.

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

Исследование отчетных форм и решаемых аналитических задач позволяет эксперту сформировать множество терминов предметной области и на их основе определить объекты анализа:

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

- множество измерений - год; подразделение; тип пос обия; город; название журнала; тип публикации; тип патента; статус конференции; автор и т. д.

С учетом сопоставимости показателей и измерений построен формальный контекст научной деятельности, который отражает знания эксперта об объектах анализа и возможности их совместной аналитической обработки. В контексте определены следующие элементы множества F = {число публикаций, число проведенных конференций, число патентов, число статей, число учебных пособий} и элементы множества D = {год, подразделение, тип пособия, город, название журнала, тип публикации, тип патента, статус конференции, автор}. Используя сокращенные обозначения, получены соответственно: F = {1, f, f3, f4, f5} и D = {db d2, йз, d.4, d5, йб, dv, dg, d9}.

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

Концептуальная решетка OLAP-кубов, построенная с помощью разработанного алгоритма, представляет собой интегральную OLAP-модель научной деятельности организации (рис. 4).

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

fi

f*

ЧгС"0'1уйі,%¥*і>Й 4 KJXf Ий

ЧнДОМГМРМ

'-к Г. "С- L  ЛІ-Р1І

'4 к £ .г+я‘-+%і  і »::/"+>(

DL И 0] СИ m

ГПОМОЧИ rWCJ Hhbwpt

В Ё U

ІЇ 1Ї U El і:

Е Б  Z1 г:

р: Е П Я p:

17 И FI г

» D’ и m

Г гП riJTiff-fT.J

a u u a

u u и u

a [J a

и n П и

и n П 0

ГЬ«Ь--*іТь itflrtiWiH I ^TWrt*Tta иХттвпЗц| I Г*г. #4 ГЬ ДЛХ P#m>1

і Concepts

F1;F2; F3; F4; F5; D1;D2;

F5; D1; D2; D3; D4; DG; D9;

F2; F4; F5; D1;D2;D4;

F4; D1;D2;D4;D5;D6;D9;

FI: F4: F5; D1;D2;D6;D9;

F3; D1;D2;D7;D9;

F2; D1;D2;D4;D8; =

F1;F3; F4; F5; D1;D2;D9;

V

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

Рис. 4. Решетка кубов-концептов научной деятельности организации

Библиографические ссылки

1. Codd E. F., Codd S. B., Salley C. T. Providing OLAP. On-line Analytical Processing to User-Analists: An IT Mandate. Ann Arbor, Mich. : E. F. Codd & Associates, 1993.

2. Горелов Б. А., Горелов Б. Б. Разработка модели данных для целей оперативной аналитической обра-

ботки финансовой информации университета // Унив. управление. 2002. № 4(23). С. 33-46.

3. Ноженкова Л. Ф., Шайдуров В. В. ОЬЛР-техно-логии оперативной информационно-аналитической поддержки организационного управления // Ин-форм. технологии и вычисл. системы. 2010. № 2. С. 15-27.

4. Palaniappan S. Ling C. Clinical Decision Support Using OLAP With Data Mining II Intern. J. of Computer Science and Network Security. 200В. Vol. В. № 9. P. 290-29б.

5. Коробко А. В., Пенькова Т. Г. Метод концептуального OLAP-моделирования на основе формального концептуального анализа II Вестник СибГАУ. 2010. № 4 (30). C. 74-79.

6. Krajca P., Outrata J., Vychodil V. Parallel Recursive Algorithm for FCA II Proc. of the Sixth Intern. Conf. on Concept Lattice and their Applicatons. Olomouc, 200В. P. 71-В2.

7. Lindig C. Fast concept analysis II Proc. of the Intern. Conf. on Conceptual Structures (ICCS). Aachen : Shaker Verlag, 2000.

8. Concept Lattices : Second Intern. Conf. on Formal Concept Analysis / P. Eklund. Sydney, 2004. P. 23-26.

9. Kuznetsov S. O., Obiedkov S. A. Comparing Performance of Algorithms for Generating Concept Lattices // J. of Experimental and Theoretical Intelligence. 2002. Vol. 14. P. 189-216.

10. Korobko A., Penkova T. On-line analytical processing based on Formal concept analysis // Procedia Computer Science. 2010. Vol. 1. № 1. P. 2305-2311.

11. Penkova T.G., Korobko A.V. Constructing the integral OLAP-model based on Formal Concept Analysis // Proc. of the 34th Intern. Convention. Opatija, 2011. P. 225-229.

12. Wille R. Restructuring Lattice Theory: an approach based on hierarchies of concept. Dordrecht ; Boston : Reidel, 1982. P. 445-70.

A. V. Korobko, T. G. Penkova

ALGORITHMS OF COMPOSITION OF THE INTEGRAL OLAP-MODEL IN OBJECT DOMAIN

The algorithms of composition of an integral OLAP-model based on the search of cube-concepts and composition of concept lattice of OLAP- cubes are described. Suggested algorithms are supplemented for integral OLAP- model of scientific activity of an organization.

Keywords: integral OLAP-model, on-line analytical data processing, formal conceptual analysis.

© Коробко А. В., Пенькова Т. Г., 2011

УДК 681.142.2

В. А. Кравченко, П. Б. Могнонов, Д. Н. Чимитов ПРЕДСТАВЛЕНИЕ ЗНАНИЙ В ФУНКЦИОНАЛЬНЫХ ГРАММАТИКАХ

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

Ключевые слова: контекстно-ориентированное программирование, объектно-ориентированное программирование, структура данных.

Рассмотрим вопрос о формализации языка с точки зрения формирования понятий на основе анализа отношений между различными объектами.

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

Согласно данному подходу, любое предложение естественного языка, а также любая программа на

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

При этом оба представления являются эквивалентными и выражают одни и те же зависимости элементов текста.

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