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

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

Ключевые слова:

инфокоммуникационная сеть, многомерный анализ данных, 01ЛР, реквизит-признак, модель метаданных

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

Висков А.В.,

к.ф.-м.н., ведущий системный аналитик ЗАО "Ланит", viskov@lanit.ru

Фомин М.Б.,

к. ф.-м. н., доцент кафедры информационных

технологий РУДН,

mfomin@sci.pfu.edu.ru

Введение

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

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

1. Построение модели множества допустимых

сочетаний значении реквизитов-признаков

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

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

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

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

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

2. Методы анализа структуры множества сочетаний допустимых значений

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

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

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

п

КРП1 КРП2

Рис. 1. Обозначение связи “Ассоциация” между двумя КРП

Зависимость. Между двумя КРП (КРП1 и КРП2) существует зависимость, если значения КРП1 могут быть разбиты на две группы так, что в случае, если в некоторое сочетание из множества сочетаний допустимых значений входит значение из первой группы значений КРП1, то значением КРП2 в этом сочетании является одно из допустимых значений, а если в сочетание входит значение из второй группы значений КРП1, то КРП2 в этом сочетании принимает значение “не используется”.

Рис. 2. Обозначение связи “Зависимость” между двумя КРП

Между двумя КРП может существовать двойная или тройная связь: ассоциация и зависимость или ассоциация и двусторонняя зависимость. Определим эти связи следующим образом.

Между двумя КРП (КРП1 и КРП2) существует ассоциация и зависимость, если допустимые значения КРП2 могут быть разбиты на п групп, п>1, а допустимые значения КРП1 — на (п+1) группу так, что между первыми п группами КРП1 и группами КРП2 может быть установлено взаимно однозначное соответствие, проявляющееся в том, что в сочетания из множества сочетаний допустимых значений значения КРП1 и КРП2 могут входить только парами, взятыми из соответствующих друг другу групп значений, и если в сочетание из множества СДЗ входит

значение из (п+1)-й группы значений КРП1, то КРП2 в этом сочетании принимает значение “не используется”.

Между двумя КРП (КРП1 и КРП2) существует ассоциация и двусторонняя зависимость, если допустимые значения КРП1 и КРП2 могут быть разбиты на п групп,

п

КРП1 КРП2

Рис. 3. Обозначение связи “Ассоциация и Зависимость”

между двумя КРП

п>2, так, что между (п-1)-й группой КРП1 и (п-1)-й группой КРП2 может быть установлено взаимно однозначное соответствие, проявляющееся в том, что в сочетания из множества сочетаний допустимых значений значения КРП1 и КРП2 могут входить только парами, взятыми из соответствующих друг другу групп значений, и если в сочетание из множества СДЗ входит значение из п-й группы значений КРП1, то КРП2 в этом сочетании принимает значение “не используется”, а если в сочетание из множества СДЗ входит значение из п-й группы значений КРП2, то КРП1 в этом сочетании принимает значение “не используется”.

Рис. 4. Обозначение связи “Ассоциация и двусторонняя зависимость” между двумя КРП

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

3. Логический подход при описании сочетаний

значений реквизитов-признаков

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

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

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

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

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

• Объединение ПустогоПодмножества-1 с Подмножеством-2 дает Подмножество-2;

• Если первый элемент Подмножества-1 принадлежит Подмножеству-2, то результатом будет объединение Подмножества-1 без первого элемента и Подмножества-2;

• В Противном случае результатом будет Результи-рующееПодмножество, образованное первым элементом Подмножества-1 и остальными элементами, полученными Объединением Подмножества-1 без первого элемента и Подмножества-2.

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

В случае использования для описания подмножеств дерева сочетаний, требуется ввести дополнительный факт “Узел”, задав его предикатом Узел (ИндехУзла, ИндексПредка, Глубина, ЗначениеСочетания), где индексы формируют структуру дерева. Дерево сочетаний в

целом описывается списком узлов, а факты, соответствующие подмножествам сочетаний,- предикатом Подмножество (ИмяПодмножества, СписокУзлов). Как и в первом случае, теоретико-множественные операции, используемые в языке МДС, могут быть описаны набором правил. Предикат для операции объединения приобретает вид Объединение (СнисокУзловПодмножества-1, СписокУзловПодмножества-2, СписокУузлов Результата). Логика этого правила имеет следующий вид:

• Объединение ПустогоПодмножества-1 с Подмножеством-2 дает Подмножество-2.

• Если первый узел списка узлов Подмножества-1 с глубиной 1 не принадлежит списку узлов Подмножества-2 с глубиной 1, то результатом будет объединение узлов Подмножества-1, у которых предком на глубине 1 является первый Узел списка узлов Подмножества-1 со списком узлов Подмножества-2.

• Иначе происходит проверка на глубине 2 узлов Подмножества-1, у которых предком на глубине 1 является первый Узел списка узлов, на принадлежность списку узлов Подмножества-2 с глубиной 2.

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

Заключение

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

Литература

1. Асламов Е.Б., Висков A.B., Фомин М.Б. Свойства аналитических измерений // Вестник РУДН. Серия математика, информатика, физика. - 2007. -№1-2. — С.46-52.

2. Набебнн A.A. Логика и Пролог в дискретной математике. - М.: Изд-во МЭИ, 1996. - 452 с.

3. Журавлёв Ю.И., Рязанов В.В., Сенько О.В. Распознавание. Математические методы. Программная система. Практические применения. - М.: ФАЗИС, 2005. - 159 с.

Methods of a description of the permissible combination of detail-attribules when using multidimensional models in infocommunication systems

Viskov Alexy V., Senior System Analyst, Corporate Systems Department, New Information Technology Laboratory (LANIT), viskov@lanit.ru,

Fomin Maxim B., An associate professor, Information Technologies Department, Peoples' Friendship University of Russia, mfomin@sci.pfu.edu.ru

Abstract: At the organization of data analysis in infocommunication networks successful way of solving the problem can be the use of technology multidimensional data analysis. In this case the analytical space dimensions (measurements) are classified detail-attribute. They are given as a discrete set of values, which are organized in a hierarchical system. The hierarchy is described by a graph of measurement. In some cases, when analyzng the data it is necessary to describe the details of the compatibility of values of detail-attributes, connected with the subject area. Thus, at the level of metadata reflects the semantics of the subject area.

Keywords: infocommunication network, multidimensional data analysis, OLAP, detail-attribute, metadata model.