Использование префиксных деревьев при построении систем анализа данных

• Автор: Гудков, Андрей Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 154 с. : ил.

Оглавление
Введение.

Глава 1 Направления решения задачи анализа данных

1.1. Классификация аналитических систем

1.2. Реализации интерактивного анализа данных

1.3. Алгоритмы агрегирования куба.

1.4. Алгоритмы поиска частых наборов и ассоциативных правил.

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

1.6. План работы и полученные результаты

Глава 2 Алгоритмы перестроек префиксного дерева для реализации интерактивного анализа данных, агрегирования куба и поиска частых наборов

2.1. Формальная постановка задач

2.2. Структура данных префиксное дерево.
2.3. Алгоритм выполнения запросов
2.4. Алгоритм агрегирования куба с помощью перестроек префиксного дерева .
2.5. Алгоритм поиска частых наборов с помощью перестроек префиксного дерева
Глава 3 Организация просмотра ассоциативных правил
3.1. Меры правил
3.2. Алгоритмы поиска интересных ассоциативных правил.
3.3. Внешний вид отчта о просматриваемых правилах
3.4. Алгоритм интерактивного просмотра правил в виде сводной таблицы
Глава 4 Теоретический анализ алгоритмов.
4.1. Задача о среднем числе разных элементов
4.2. Сложность задач.
4.3. Объм префиксного дерева
4.4. Время построения префиксного дерева.
4.5. Время подъма уровня префиксного дерева.
4.6. Время работы алгоритма интерактивного анализа данных
4.7. Время работы алгоритма агрегирования куба.
4.8. Время работы алгоритмов поиска частых наборов
Глава 5 Экспериментальный анализ алгоритмов.
5.1. Алгоритмы интерактивного анализа данных
5.2. Алгоритмы агрегирования куба.
5.3. Алгоритмы поиска частых наборов
5.4. Меры интереса правил.
Заключение
Список использованных источников


Для наиболее распространённых видов гражданского бизнеса (банковское дело, биржевые операции, системы резервирования билетов или мест в гостиницах) не требуются массивные расчёты (кроме авиа- и автомобилестроения). Для них главное - сбор, падёжное хранение и оперативная обработка больших объёмов информации. Решение этой проблемы является основной целью информационных систем. Предназначены для сбора, хранения и обработки информации. Поэтому в основе лежит среда хранения и доступа к данным. Ориентируются на конечного пользователя (клерка), который может быть далёк от мира компьютеров. Поэтому должен быть простой, удобный, легко осваиваемый интерфейс. Системы обработки и системы анализа данных. Основное отличие заключается в целях применения этих систем. Классификация аналитических систем но способам храпения данных. Различные способы хранения данных в аналитических системах обсуждаются в [7, 9, , , , , , , , , ]. Дубликат оперативных систем. Анализ осуществляется на основе дублированных данных оперативной системы, которые обновляются по мерс необходимости. Это позволяет убрать нагрузку на оперативную систему, но остальные проблемы остаются нерешёнными. Независимые витрины данных. Для каждой аналитической задачи создаётся свой независимый отдельный источник данных - витрина, в которую загружаются данные из источников и которая используется для целей анализа. Позволяет преодолеть все недостатки, присущие реализации на основе оперативных систем, при этом сохраняя простоту разработки и внедрения. Хранилища данных. Создаётся единый источник аналитических данных для всей организации - хранилище данных. Оно пополняется из источников данных, и к нему обращаются все приложения. Все данные хранятся в одном месте в единой структуре, что позволяет оптимизировать затраты на хранение и создать единую картину организации. Недостатками являются сложность разработки и внедрения, а также доступа отдельных пользователей. Хранилища и витрины данных. В дополнение к единому хранилищу данных предприятия создаются также специализированные витрины данных. Витрины данных заполняются из хранилища. При этом существует единая картина организации и эффективный доступ пользователей, но появляется избыточность данных и дополнительные расходы на хранение, а также сохраняется сложность разработки и внедрения. Классификация аналитических систем но способам анализа данных. Статические системы (или информационные системы руководителя) представляют собой предопределённое множество отчётов, которые с заданной периодичностью предоставляются аналитику. Такие системы просто реализуются. Основным недостатком таких систем является отсутствие гибкости. Часто при просмотре отчётов у аналитика возникает ряд дополнительных вопросов. Если они не были учтены при проектировании системы, то для получения ответов запрос должен быть формально описан и передан программисту, и время ожидания может занять часы и даже дни. Динамические системы предназначены для ответов на неожиданные запросы к данным. Прозрачность (transparency). Пользователь не должен знать, где конкретно хранятся данные. Доступность (accessibility). Система должна осуществлять доступ ко всем необходимым источникам данных, согласовывать их форматы и предоставлять конечный отчёт пользователю. Допустимая скорость запросов (consistent reporting performance). Скорость выполнения запросов не должна существенно зависеть от сложности запроса и размера базы данных. В [] был сформулирован более простой набор требований в виде теста FASMI (Fast Analysis of Shared Multidimensional Information, или быстрый анализ разделяемой многомерной информации). Здесь под анализом понимается возможность формирования произвольных запросов, а под информацией доступ ко всем источникам данных, необходимым для анализа. Требования к динамическим системам анализа данных обсуждаются также в [7, ,, ,,,]. Основой оперативной аналитической обработки данных является многомерное концептуальное представление, или многомерная модель данных. Она описывается в [7,8,,,,,,,,,,,].