авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |

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

-- [ Страница 1 ] --

На правах рукописи

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

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

при построении систем анализа данных

Специальность 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. Выполнение запроса с помощью префиксного дерева выполняется в два шага. Вначале производится перестановка уровней для приведения дерева к виду, когда сверху располагаются заданные в запросе измерения в заданном порядке (в случае отображения на сводную таблицу вначале идут строковые измерения, а потом столбцовые). Затем производится обход верхних уровней и отображение результата на таблицу.

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



Pages:   || 2 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.