Моделирование структуры данных методами теории решеток



Скачать 43.19 Kb.
Дата08.11.2012
Размер43.19 Kb.
ТипРешение
Лебедев В.Б. Моделирование структуры данных методами теории решеток. // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей Междунар. научно-техн. конф.– Пенза: ПДЗ, 2010. – С. 41-45.
МОДЕЛИРОВАНИЕ СТРУКТУРЫ ДАННЫХ
МЕТОДАМИ ТЕОРИИ РЕШЕТОК


В.Б. Лебедев

Пензенский государственный университет,
г. Пенза, Россия

Рассмотрены вопросы моделирования структуры данных с помощью решеток (дискретных структур). Показано, что для эффективного представления одной и той же структуры данных рационально использовать изоморфные решетки различных типов: решетки, образованные с помощью оператора замыкания, решетки кортежей множеств допустимых значений признаков данных и решетки множества характеристических векторов.
Lebedev V.B. Modeling of data structure by the method of lattice theory. The questions of data structure modeling with the help of lattice theory are considered. It is shown that for the effective representation of one and the same data structure it is reasonable to use isomorphic lattices of different types: lattices made with the help of closure operator, lattices of set sequences of admitted feature value and lattices of set of characteristic vector.
Решение задач анализа данных тесно связано с вопросами их эффективного представления. В работах [1, 3] показано, что применение метода комбинаторно-упорядоченного моделирования (КУМ) [1] позволяет повысить эффективность представления данных. При таком подходе используется понятие решетки (дискретной структуры), представляющей разновидность частично упорядоченного множества [2]. Решетка строится с помощью оператора замыкания специального вида. Рассматриваемый метод относится к методам дискретного анализа, основная идея которых заключается в том, что описательные характеристики данных, однозначно определяющие объект, представляются с помощью методов дискретной математики. Методология КУМ применялась, например, при анализе ассоциаций данных в технологиях добычи данных (Data Mining), при классификации образов в задачах распознавания, при решении задач управления в системах автоматизированного обучения и др. Во всех случаях обнаружено повышение эффективности представления данных (в частности, точности и полноты представления) по сравнению, например, с методами, основанными на статистическом анализе. Этот эффект объясняется особыми свойствами используемых решеток, в частности, взаимной однозначностью порождающего семейства множеств модели данных и ее решетки, построенной с помощью оператора замыкания. В данной работе показано, что для эффективного представления структур данных рационально использовать изоморфные решетки различных типов [3].

Например, основной тип решетки образуется с помощью оператора замыкания gif" name="object2" align=absmiddle width=112 height=29>, заданного на исходном порождающем семействе множеств (например, семействе атрибутов исходных данных), где , , [1]. Элементами решетки являются все замкнутые множества, удовлетворяющие условию . Решетка обладает рядом свойств, которые полезны при анализе данных, например, все множества порождающего семейства являются элементами решетки, а каждый коатом решетки есть элемент порождающего семейства множеств . Если элементы решетки имеют одинаковую мощность, то они являются несравнимыми. Второй тип решетки определяется кортежем семейства множеств допустимых значений признаков данных и порождающим семейством кортежей одноэлементных множеств значений этих признаков , задающим исходные данные, где и (если какой либо признак отсутствует, то полагают, что ) [3]. Изоморфизм решеток и определяет отображение , где . Третий тип решеток задает отображение , где (), и определяет изоморфизм [2]. Вектор называется характеристическим вектором подмножества , а множество характеристических векторов элементов решетки , сохраняющее отношение следования, образует решетку , изоморфную решеткам и .

Рассмотрим пример. Пусть задано порождающее семейство множеств , используя оператор замыкания , путем определения попарного пересечения множеств семейства с помощью алгоритма [1] построим решетку . Диаграмма Хассе этой решетки показана на рисунке, а (структурный нуль и структурная единица решетки для упрощения не показаны).

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


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


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

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

1. Лебедев В.Б. Анализ ассоциаций данных методом комбинаторно-упорядоченного моделирования // Известия высших учебных заведений. Поволжский регион. – 2005. – №5 (20). – С. 99 – 106.

2. Айгнер М. Комбинаторная теория. – М.: Мир, 1982. – 558 с.

3. Лебедев В.Б., Минаев В.Е. Построение изоморфных решёток в задаче дискретной классификации // Университетское образование: сб. статей XII Междунар. науч.-метод. конф. – Пенза: ПГУ, АНОО «ПДЗ», 2008. – С. 247 – 249.

4. Кофман А. Введение в прикладную комбинаторику / пер. с франц. – М.: Наука, 1975. – 479 с.

Похожие:

Моделирование структуры данных методами теории решеток iconЛабораторная работа №6 Моделирование непрерывно распределённых случайных величин специальными методами
Научиться моделировать значения непрерывно распределённой случайной величины различными методами и проводить статистический анализ...
Моделирование структуры данных методами теории решеток iconПрограмма дисциплины Теория решеток и ее использование при анализе текстов
Изучение курса «Теория решеток и ее использование при анализе текстов» требует предварительных знаний по элементарной теории множеств,...
Моделирование структуры данных методами теории решеток iconПовышение эффективности алгоритмов классификации образов на основе теории решеток
Лебедев В. Б. Повышение эффективности алгоритмов классификации образов на основе теории решеток. // Проблемы информатики в образовании,...
Моделирование структуры данных методами теории решеток iconМоделирование процессов обработки запросов к базе данных "библиотека" средствами теории масового обслуживания
Одной из задач при эксплуатации баз данных (БД) является настройка оборудования и соответствующего программного обеспечения, обеспечивающего...
Моделирование структуры данных методами теории решеток iconЗанятие №1 Лекция Структуры данных. Динамические структуры данных. Списки. Стеки. Очереди. Семинар
Реализация основных процедур по работе со списками на яп. Сравнение способов реализации стеков и очередей с помощью массивов и динамических...
Моделирование структуры данных методами теории решеток icon1. Понятие данных. Примитивы и структуры. Стандартные структуры данных. Данные
...
Моделирование структуры данных методами теории решеток iconПонятие модели данных
В классической теории баз данных, модель данных есть формальная теория представления и обработки данных в системе управления базами...
Моделирование структуры данных методами теории решеток iconТехнология программирования. Вопрос №5 Динамические структуры данных
Динамические структуры данных служат полезным дополнением к стандартным структурам, уже определенным в языке Pascal. Динамическими...
Моделирование структуры данных методами теории решеток iconЛабораторная работа №3 «Встроенные структуры данных»
Изучение базовых типов данных на примере языка Turbo-Рascal как структур данных (СД)
Моделирование структуры данных методами теории решеток iconСтруктуры данных
Этот материал посвящен описанию некоторых часто используемых на практике структур данных и способов эффективной реализации этих структур....
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org