Реализация интерактивного анализа данных. Алгоритмы поиска частых наборов и ассоциативных правил. Агрегирование куба с помощью перестроек префиксного дерева. Положение систем анализа данных среди информационных систем. Степень участия человека в анализе.
Аннотация к работе
С помощью систем анализа данных могут быть решены следующие задачи: сбор всех необходимых для анализа данных в одном месте с согласованием форматов и удалением ошибок, интерактивный просмотр этих данных аналитиком, автоматическое извлечение закономерностей из данных. Основным требованием к системам OLAP является скорость выполнения запросов, так как анализ должен проходить в интерактивном режиме. Предложенные в литературе алгоритмы OLAP основаны на дисковых структурах данных или структурах данных в оперативной памяти. Предложенный в диссертации алгоритм перестроек префиксного дерева существенно уменьшает требования к объему данных по сравнению с другими алгоритмами в оперативной памяти, вместе с тем сохраняя высокую скорость работы. Предложенный в диссертации алгоритм перестроек префиксного дерева обладает минимальными требованиями к памяти среди остальных алгоритмов и может обрабатывать большие объемы данных без выхода на диск, что позволяет ускорить вычисления.Задача агрегирования куба состоит в вычислении всех агрегатных данных по заданным исходным данным, что соответствует одновременному выполнению агрегатных запросов для всех подмножеств множества измерений, или подкубов. Задача поиска правил разбивается на два шага: поиск частых наборов, или наборов, удовлетворяющих порогу поддержки, и извлечение правил, удовлетворяющих порогу доверия, из частых наборов. Префиксное дерево строится для заданного порядка измерений, так что на каждом уровне хранятся элементы одного измерения, а каждый путь соответствует записи таблицы. Вначале в план добавляется подсчет частот комбинаций уровня i, затем строится план для номеров (i 1,…,j), в план добавляется последовательность подъемов уровней i 1,…,j для переноса уровня i после уровня j, строится план для номеров (i,…,j-1). Алгоритмы PTI3 и PTI4 предварительно приводят префиксное дерево к такому виду, когда в нем хранятся только частые элементы, а затем работают как алгоритмы PTI1 и PTI2.
План
Краткое содержание работы
Список литературы
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.