Размещено на http://www.allbest.ru/

[Введите текст]

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

ИСПОЛЬЗОВАНИЕ ПРЕФИКСНЫХ ДЕРЕВЬЕВ ПРИ ПОСТРОЕНИИ СИСТЕМ АНАЛИЗА ДАННЫХ

Гудков Андрей Сергеевич

Специальность 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

Москва - 2006

Работа выполнена на кафедре управляющих и информационных систем Московского физико-технического института (государственного университета).

Научный руководитель: кандидат физико-математических наук,

Доцент БОНДАРЕНКО Александр Викторович

Официальные оппоненты: доктор физико-математических наук,

Профессор СТОЛЯРОВ Лев Николаевич

кандидат физико-математических наук

СЕМИН Николай Николаевич

Ведущая организация: Институт прикладной математики

имени М.В.Келдыша

Российской академии наук (ИПМ РАН)

Защита диссертации состоится «1» декабря 2006 года в 12 ч. 30 мин. на заседании диссертационного совета K212.156.02 в Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская область, г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан «31» октября 2006 года

Ученый секретарь

диссертационного совета

K212.156.02

к. ф.-м. н.

О. С. Федько

Общая характеристика работы

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

В литературе активно исследуются три основных технологии систем анализа данных: хранилища данных, оперативная аналитическая обработка данных (Online Analytical Processing, или сокращённо OLAP), интеллектуальный анализ данных (Data Mining).

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

Если объёмы данных очень велики, то предагрегация может значительно ускорить выполнение запросов. Также агрегирование может применяться для ответа на запросы пользователя с одновременным требованием просмотра многих агрегатных данных (например, при отображении сводной таблицы). Первые алгоритмы агрегирования куба основываются на существенном использовании диска и являются достаточно медленными. Алгоритмы MemoryCube и BUC компактно используют оперативную память для проведения вычислений, но их планы выполнения являются неоптимальными. Предложенный в диссертации алгоритм перестроек префиксного дерева предлагает более быстрое выполнение по сравнению с заявленными алгоритмами при тех же объёмах обрабатываемых данных.

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

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

Цели работы. Основными целями диссертационной работы являются:

1. Разработка эффективных алгоритмов реализации интерактивного анализа данных, автоматического поиска частых наборов и правил в данных, основанных на использовании префиксного дерева.

2. Разработка алгоритмов удобного просмотра извлечённых правил.

3. Анализ разработанных алгоритмов.

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

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

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

Разработанный алгоритм интерактивного анализа данных внедрён в автоматизированной информационной системе “Консул ЗУ” в МИД РФ.

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

· XLVIII и XLIX научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2005, 2006)

· XIII международной научной конференции студентов, аспирантов и молодых учёных “Ломоносов”, (Москва, МГУ, 2006),

а также на научных семинарах кафедры управляющих и информационных систем МФТИ и 3500 отделения ГосНИИ авиационных систем в 2002-2006 гг.

Публикации. Основные положения работы отражены в 6 публикациях.

Структура и объём диссертации. Диссертация состоит из введения, пяти глав, заключения и списка использованных источников. Объём работы составляет 154 страницы. Список использованных источников содержит 101 наименование.

Краткое содержание работы

В главе 1 проводится обзор основных направлений решения задачи анализа данных. Рассмотрено положение систем анализа данных среди информационных систем и их классификация по способу хранения данных, способу анализа данных и степени участия человека в анализе данных. Поставлены основные задачи диссертации: реализация ответов на запросы интерактивного анализа данных (OLAP), агрегирование куба, поиск частых наборов и ассоциативных правил, эффективный просмотр ассоциативных правил. Для каждой задачи проведён обзор существующих подходов к решению. префиксный дерево ассоциативный информационный

1.1. Классификация аналитических систем. По целям компьютерные системы можно разделить на вычислительные, ориентированные на вычисления, и информационные, ориентированные на сбор и хранение данных. Последние делятся на оперативные и аналитические системы, целями которых являются соответственно оперативная обработка и анализ данных. Системы анализа данных классифицируются по способам хранения данных, способам анализа данных и степени участия человека в анализе. В каждом из этих направлений с развитием аналитических систем были предложены новые технологии: независимое хранение аналитических данных в технологиях хранилищ и витрин данных, динамический анализ данных на основе многомерной модели в технологии OLAP (Online Analytical Processing, или оперативная аналитическая обработка данных), автоматическое извлечение закономерностей из данных в технологии Data Mining (добыча данных, или интеллектуальный анализ данных). Одним из важных направлений Data Mining является извлечение правил из данных.

В диссертации предложены подходы к решению следующих основных задач в рамках рассмотренных технологий:

1. Реализация ответов на запросы интерактивного анализа данных (OLAP).

2. Агрегирование куба.

3. Поиск частых наборов и ассоциативных правил.

4. Эффективный просмотр ассоциативных правил.

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

Два наиболее популярных метода реализации OLAP - это реляционный OLAP (ROLAP), где данные хранятся в виде таблиц в реляционной базе данных специальной структуры, и многомерный OLAP (MOLAP), где данные хранятся в специальных структурах данных, реализующих многомерный массив. Кроме того, существует множество индексных структур, которые могут применяться как для ускорения программ ROLAP, так и самостоятельно. В качестве индексов могут использоваться многомерные массивы, инвертированные списки, битовые индексы, иерархические индексы, специальные многомерные индексы. Для ответов на запросы нужно не только выбрать удовлетворяющие ограничениям данные, но и произвести агрегацию. Для ускорения ответов на запросы часто используется частичная материализация агрегатных данных. Хранение данных во время работы программы может осуществляться на диске или в оперативной памяти.

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

Алгоритмы выполнения отдельного агрегатного запроса делятся на две группы: основанные на сортировке и основанные на хешировании. Алгоритмы агрегирования куба являются обобщениями этих алгоритмов с применением ряда оптимизаций: разделение сортировок и разбиений между подкубами, одновременное вычисление нескольких подкубов, вычисление по родительскому подкубу вместо исходного отношения. В работе рассматриваются алгоритмы PipeSort, PipeHash, Overlap, ArrayCube, PartitionedCube, MemoryCube, BUC. Для сравнения с разработанным алгоритмом используется алгоритм MemoryCube. Он выполняет вычисления над таблицей в оперативной памяти с помощью сортировок. План сортировок разработан таким образом, что число сортировок минимально.

1.4. Алгоритмы поиска частых наборов и ассоциативных правил. Ассоциативное правило - это выражение вида ab, где a и b - множества значений атрибутов базы данных. Обычно поиск правил осуществляется с ограничениями по поддержке и доверию. Поддержкой правила называется число записей базы, где встречаются левая и правая часть правила одновременно. Доверием правила называется отношение поддержки левой и правой частей к поддержке левой части. Доверие характеризует точность правила. Задача поиска правил разбивается на два шага: поиск частых наборов, или наборов, удовлетворяющих порогу поддержки, и извлечение правил, удовлетворяющих порогу доверия, из частых наборов. Наиболее трудоёмкой является первая задача.

В работе рассматриваются алгоритмы поиска частых наборов для баз транзакций и баз данных. Сравнительный анализ проводится с алгоритмами Apriori и FP-Growth. Наивный алгоритм генерирует все возможные комбинации и считает для них частоту за один проход по базе, после чего выделяет частые наборы. При этом число комбинаций очень велико. Алгоритм Apriori уменьшает число комбинаций с помощью свойства антимонотонности: если набор является частым, то все его поднаборы также являются частыми. Отсюда следует, что если набор является редким, то все его расширения также являются редкими, и их можно не рассматривать. Для наибольшей эффективности отсечения с помощью этого свойства на каждом шаге должны рассматриваться комбинации-кандидаты одинаковой длины. Алгоритм FP-Growth использует другую стратегию. Вместо генерации наборов-кандидатов строится компактное представление базы данных в виде структуры данных FP-дерева. Далее частые наборы извлекаются из этой структуры.

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

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

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

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

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

В диссертации решаются следующие задачи:

1. Ответы на запросы интерактивного анализа данных. По базе данных и запросу получить отчёт с промежуточными итогами или сводную таблицу.

2. Агрегирование куба. По базе данных получить все значения агрегированного куба.

3. Поиск частых наборов. По базе данных и порогу частоты s получить все значения агрегированного куба, большие или равные s.

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

Префиксное дерево строится из исходной таблицы за один проход. В процессе прохода каждая строка таблицы по очереди вставляется в дерево.

В алгоритмах используется перестройка уровней дерева. Любая перестройка дерева может быть сведена к перестановке двух соседних уровней. Эта операция называется подъёмом уровня и является основной операцией в выполнении запросов префиксным деревом. Пусть осуществляется подъём уровня k, k=2,…,m. Подъём осуществляется независимо для поддерева каждого узла уровня k2. Для разных элементов уровня k этого поддерева создаются узлы с суммарной частотой и заносятся на уровень k1 вместо старых узлов. Для каждого узла уровня k меняется элемент на элемент родительского узла, и меняется родительский узел на узел с тем же старым элементом.

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

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

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

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

2.4. Алгоритм агрегирования куба с помощью перестроек префиксного дерева. В работе предложен следующий алгоритм агрегирования куба на основе перестроек префиксного дерева, названный PrefixTreeCubing. Алгоритм выполняется в два шага: построение плана вычислений и выполнение плана вычислений. План вычислений содержит два типа операций: подъём заданного уровня и подсчёт частот комбинаций для заданного уровня. План вычислений строится с помощью следующей рекурсивной процедуры, входом которой является последовательность номеров (i,…,j). Вначале в план добавляется подсчёт частот комбинаций уровня i, затем строится план для номеров (i+1,…,j), в план добавляется последовательность подъёмов уровней i+1,…,j для переноса уровня i после уровня j, строится план для номеров (i,…,j1). В начальный момент для построения плана добавляется подсчёт общей частоты и вызывается рекурсивная функция для последовательности (1,…,m), где m - число измерений. На шаге выполнения плана последовательно производятся подсчёты частот комбинаций и подъёмы заданных уровней.

2.5. Алгоритм поиска частых наборов с помощью перестроек префиксного дерева. Для поиска частых наборов предложено 4 алгоритма, основанных на перестройках префиксного дерева: PTI1, PTI2, PTI3, PTI4.

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

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

Алгоритмы PTI3 и PTI4 предварительно приводят префиксное дерево к такому виду, когда в нём хранятся только частые элементы, а затем работают как алгоритмы PTI1 и PTI2. Это позволяет уменьшить объём дерева и соответственно ускорить работу.

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

Рассмотрим правило вида ab. Меры делятся на 4 группы: точность, статистическая обоснованность, неожиданность (интерес) и полезность. В качестве меры точности в основном используется условная вероятность . Основная мера интереса заключается в сравнении точности правила с вероятностью правой части . Данная мера не учитывает структуры левой части правила. Одна из возможностей учёта - мера Она эффективно отсекает правила, но может давать некорректные результаты. Более обоснованным является сравнение ожидаемой и реальной точности правила. В работе представлен ряд мер предсказания точности на основе различных схем компенсации влияния факторов, например, мера компенсации, где ожидаемая точность равна

.

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

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

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

Теорема 4.1 (о среднем числе разных элементов). Пусть имеется m-элементное множество, из которого делается выбор с возвращением n элементов. Тогда

1. Среднее число разных элементов для заданных значений m,n

.

2. Среднее число элементов, встречающихся больше или равно s раз, для заданных значений m,n

.

Теорема 4.2 (о сложности задач). Пусть

1. m - число измерений, n - число записей, p₁,…,p_m - число разных значений измерений 1,…,m.

Тогда

1. Минимальное число разных записей равно 1, максимальное равно min(n,p₁…p_m), среднее равно K_ср(p₁…p_m,n).

2. Минимальное число ненулевых ячеек полного агрегированного куба равно 2^m, максимальное равно , среднее равно . При p₁=…=p_m=p максимальное и среднее значения принимают вид и соответственно.

3. Минимальное число частых комбинаций при заданном пороге частоты s равно , максимальное равно , среднее равно . При p₁=…=p_m=p минимальное, максимальное и среднее значения принимают вид , и соответственно. Здесь n\s обозначает целочисленное деление n на s, E(k₁,k₂)=1, если k₁>k₂, и 0 в противном случае.

Теорема 4.3 (о числе узлов префиксного дерева). Пусть

1. m - число измерений, n - число записей, p₁,…,p_m - число разных значений измерений 1,…,m.

2. Префиксное дерево построено в порядке измерений (1,…,m).

Тогда

1. Минимальное число узлов префиксного дерева на уровне i равно 1, максимальное равно min(n,p₁…p_i), среднее равно K_ср(p₁…p_i,n).

2. Минимальное число узлов префиксного дерева равно m+1, максимальное равно , среднее равно .

Теорема 4.4 (о времени построения префиксного дерева). Пусть

1. m - число измерений, n - число записей, p₁,…,p_m - число разных значений измерений 1,…,m.

2. Если префиксное дерево строится в порядке измерений (1,…,m) с помощью последовательной вставки записей, то

2.1. Количество добавлений узлов равно N_nodes.

2.2. Количество операций сложения равно (m+1)nN_nodes.

2.3. Количество операций сравнения равно O(mn) при использовании хеш-таблиц для хранения узлов, O((p₁+…+p_m)n) при использовании списков.

3. Если префиксное дерево строится в порядке измерений (1,…,m) из отсортированной в том же порядке измерений таблицы, то

3.1. Количество добавлений узлов равно N_nodes.

3.2. Количество операций сложения равно n1.

3.3. Количество операций сравнения равно mn.

Здесь N_nodes - число узлов префиксного дерева.

Теорема 4.5 (о времени подъёма уровня префиксного дерева). Пусть

1. m - число измерений, n - число записей, p₁,…,p_m - число разных значений измерений 1,…,m.

2. Префиксное дерево построено в порядке измерений (1,…,m).

3. Осуществляется подъём уровня i, i{2,…,m}.

Тогда число созданий узлов равно nb, число удалений узлов равно na, число сложений равно nabnb, число сравнений равно O(nab). Здесь na - число узлов префиксного дерева на уровне i1 до подъёма уровня i, nb - число узлов префиксного дерева на уровне i1 после подъёма уровня i, nab - число узлов префиксного дерева на уровне i.

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

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

Теорема 4.6 (о числе перестроек уровней в алгоритме интерактивного анализа данных).

1. Пусть префиксное дерево имеет порядок уровней (1,…,m).

2. Если задан запрос на перестановку измерения i после измерения j, i,j{1,…,m}, то

2.1. Минимальное число подъёмов уровней равно 0, максимальное равно m1, среднее равно .

2.2. Минимальное число подъёмов уровня k,2km, равно 0, максимальное равно 1, среднее равно .

3. Если задан запрос на приведение префиксного дерева к порядку уровней (i₁,…,i_m), то

3.1. Минимальное число подъёмов уровней равно 0, максимальное равно , среднее равно .

3.2. Минимальное число подъёмов уровня k,2km, равно 0, максимальное равно mk+1, среднее равно .

Теорема 4.7 (о времени работы алгоритма поиска всех наборов). Для алгоритма PrefixTreeCubing справедливы следующие формулы для числа подсчётов и подъёмов уровней.

1. Число подсчётов уровней N_c(m)=2^m.

2. Число подсчётов на уровне i N_c(m,i)=,i=0,…,m.

3. Число подъёмов уровней N_r(m)=2^mm1.

4. Число подсчётов на уровне i N_r(m,i)=1, i=1,…,m.

Они являются оптимальными среди всех алгоритмов поиска всех наборов с помощью перестроек префиксного дерева

Теорема 4.8 (о времени работы алгоритмов поиска частых наборов).

1. Для алгоритма PTI1 справедливы следующие оценки.

1.1. Число подсчётов и подъёмов уровней совпадает с соответствующим числом для алгоритма PrefixTreeCubing.

1.2. Число просматриваемых узлов при подсчёте комбинаций на уровне i меньше соответствующего числа для алгоритма PrefixTreeCubing и определяется формулой K_{ср_пр}(p₁…p_i1,p_i,n,s), где

.

1.3. Число обрабатываемых узлов уровня i при подъёме уровня i равно числу узлов на уровне i.

2. Для алгоритма PTI2 справедливы следующие оценки.

2.1. Число подсчётов уровней совпадает с соответствующим числом для алгоритма PrefixTreeCubing.

2.2. Число подъёмов уровней в два раза больше соответствующего числа для алгоритма PrefixTreeCubing.

2.3. Число просматриваемых узлов при подсчёте комбинаций на уровне i меньше соответствующего числа для алгоритма PrefixTreeCubing и определяется формулой K_{ср_пр}(p₁…p_i1,p_i,n,s).

2.4. Число обрабатываемых узлов уровня i при подъёме уровня i меньше соответствующего числа для алгоритма PrefixTreeCubing и определяется формулой K_{ср_пр}(p₁…p_i2,p_i-1p_i,n,s).

3. Для алгоритмов PTI3 и PTI4 справедлива следующая оценка. Среднее число узлов на уровне i получаемого после первого шага префиксного дерева с частыми элементами определяется формулой K_{ср_чэ}(p₁,…,p_i,n,s), где

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

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

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

5.2. Алгоритмы агрегирования куба. Для проведения экспериментов по эффективности алгоритмы PrefixTreeCubing и MemoryCube были реализованы в виде программы на языке Delphi7. Эксперименты проводились на случайно сгенерированных данных для двух распределений значений измерений: равномерного и распределения Зипфа с показателем 1, а также на реальных данных. Для алгоритма MemoryCube эксперименты проведены для двух случаев: непосредственное выполнение на заданной таблице и выполнение после предварительного объединения одинаковых записей. Алгоритм на основе префиксного дерева показал в несколько раз большую скорость выполнения запросов при сравнимом объёме занимаемой памяти.

5.3. Алгоритмы поиска частых наборов. Для проведения экспериментов по эффективности были реализованы в виде программы на языке Delphi7 четыре варианта алгоритма PrefixTreeIceberg и алгоритмы Apriori и FP-Growth. Эксперименты проводились на случайно сгенерированных данных для двух распределений значений измерений: равномерного и распределения Зипфа с показателем 1, а также на реальных данных. В среднем наилучшие результаты показал алгоритм PTI3.

5.4. Меры интереса правил. Для сравнения эффективности мер сравнивалось количество правильно предсказанных правил для различных наборов реальных данных. Мера SuperInterest и меры предсказания показали высокую эффективность по сравнению с простой мерой интереса.

В заключении приведены основные результаты работы.

Основные результаты работы

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

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

3. Введено несколько мер ценности ассоциативных правил, учитывающих их специфику, и разработан алгоритм поиска интересных ассоциативных правил с учётом этих мер.

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

5. Разработан комплекс программ для предложенных и ряда известных алгоритмов. Проведено экспериментальное сравнение их эффективности.

Список публикаций по теме диссертации

1. Бондаренко А.В., Галактионов В.А., Горемычкин В.И., Гудков А.С., Стриковский И.И. Реализация интерактивного анализа данных с помощью префиксного дерева: Препринт / ИПМ. - М., 2005. - №61. - 34 с.

2. Гудков А.С. Агрегирование куба с помощью префиксного дерева. // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLVIII научной конференции. / МФТИ. - М. - Долгопрудный, 2005. - С.92-93.

3. Гудков А.С. Поиск частых комбинаций в базах данных. // Материалы XIII Международной конференции студентов, аспирантов и молодых учёных "Ломоносов", секция "Вычислительная математика и кибернетика". - М., 2006. - С.19-20.

4. Бондаренко А.В., Гудков А.С. Поиск частых и разных комбинаций с помощью перестроек префиксного дерева. // Процессы и методы обработки информации: Сб.ст. / МФТИ. - М., 2006. - С.69-78.

5. Бондаренко А.В., Гудков А.С. Интерактивный анализ ассоциативных правил в базе данных. // Вестник компьютерных и информационных технологий. - 2006. - №10. - С.42-45.

6. Гудков А.С. Меры интереса ассоциативных правил, основанные на предсказании точности. // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLIX научной конференции. / МФТИ. - М. - Долгопрудный, 2006. - С.84-85.

Размещено на Allbest.ru

...