К дипломной работе

Скачать 0.82 Mb.

Название	К дипломной работе
страница	1/11
Тип	Диплом

filling-form.ru > Туризм > Диплом

1 2 3 4 5 6 7 8 9 10 11

МОСКОВСКИЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ НАЦИОНАЛЬНОГО ИССЛЕДОВАТЕЛЬСКОГО УНИВЕРСИТЕТА “ВЫСШАЯ ШКОЛА ЭКОНОМИКИ”

Кафедра

_______________Информационные технологии__________________

________________и автоматизированные системы________________
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к дипломной работе
На тему:

Автоматическая кластеризация транзакционных данных с применением структур B+ деревьев.
Студент _Пикулев Егор Владиславович_______________________________
Руководитель проекта _Подлесных Валерий Григорьевич________________
Допущен к защите _________________________ 2013 г.

КОНСУЛЬТАНТ РАБОТЫ:
Специальная часть _Подлесных Валерий Григорьевич__________________

Зав. кафедрой _Тумковский Сергей Ростиславович_________________

МОСКВА, 2013 г.

АННОТАЦИЯ

В дипломной работе на тему «Автоматическая кластеризация транзакционных данных с применением структур B+ деревьев»:

Приведены принципы работы различных алгоритмов кластеризации
Предложено использовать B+ деревья в кластеризации транзакционных данных
Изучена структура представления информации в виде таблиц транзакционных данных
Разработано и реализовано приложение для создания тестовых баз данных
Модернизирован существующий алгоритм кластеризации транзакционных данных
Реализован модернизированный алгоритм кластеризация транзакционных данных с применением структур B+ деревьев
Протестирован модернизированный алгоритм

ОГЛАВЛЕНИЕ………………………………………………………………………….3

ВВЕДЕНИЕ……………………………………………………………………………...4

1.ПРЕДСТАВЛЕНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ………………………………..6

1.1 Понятие Data Mining………………………………………………………...6

1.2 Кластеризация………………………………………………………………..8

1.2.1 Классификация алгоритмов кластеризации………………………….9

1.2.2 Сравнение алгоритмов…………………………………………………..9

1.3 Понятие транзакций и проблема их кластеризации………………….11

1.4 Кластеризация транзакций с использованием концепции часто встречающихся (“больших”) предметов…………………………………………...13

2. ПОСТАНОВКА ЗАДАЧИ…………………………………………………………23

2.1 Цель и задачи работы……………………………………………………...23

2.2 Двоичное дерево поиска…………………………………………………...23

2.3 B+ дерево…………………………………………………………………….29

3. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ……………………….31

3.1. Структура хранения транзакций в базах данных…………………….31

3.2. Создание тестовых баз данных транзакций…………………………..34

3.3. Программная реализация алгоритма LargeItem…………………….39

3.4. Настройка Java.…………………………………………………………...48

4. ТЕСТИРОВАНИЕ………………………………………………………………….49

4.1 Масштабируемость………………………………………………………...49

4.2. Deductor Studio 5.1………………………………………………………...50

ЗАКЛЮЧЕНИЕ………………………………………………………………………..58

СПИСОК ЛИТЕРАТУРЫ……………………………………………………………59

Приложение 1 Установка и настройка программного обеспечения для работы с приложениями «GeneratorDB», «LargeItem»……………………………………....60

Приложение 2 Код приложения «GeneratorDB»…………………………………..68

Приложение 3 Код приложения «LagreItem»……………………………………....85

ВВЕДЕНИЕ

В наше время все большее количество компаний, стремясь к повышению эффективности и прибыльности бизнеса пользуются цифровыми (автоматизированными) способами обработки данных и записи их в БД. Это несет в себе как огромные преимущества, так и рождает определенные проблемы, связанные с объемом полученных данных, а именно: при колоссальном увеличении объема полученной информации усложняется ее обработка и анализ, делать выводы по полученным данным становится все сложнее, и вероятность того, что некоторые детали могут быть упущены неумолимо растет. Данная проблема явилась причиной развития различных подходом и методов, позволяющие проводить автоматический анализ данных. Для решения данных вопросов существуют математические методы, которые и образуют направление Data Mining. Термин Data Mining часто переводится как добыча данных, извлечение информации, раскопка данных, интеллектуальный анализ данных, средства поиска закономерностей, извлечение знаний, анализ шаблонов, Понятие «обнаружение знаний в базах данных» (Knowledge Discovering Databases, KDD) можно считать синонимом Data Mining. Data Mining - мультидисциплинарная область, возникшая и развивающаяся на базе таких наук как прикладная статистика, распознавание образов, искусственный интеллект, теория баз данных и так далее. Понятие Data Mining, появившееся в 1978 году, приобрело высокую популярность в современной трактовке примерно с первой половины 1990-х годов. До этого времени обработка и анализ данных осуществлялся в рамках прикладной статистики, при этом в основном решались задачи обработки небольших баз данных. Информация, найденная в процессе применения методов Data Mining, должна быть нетривиальной и ранее неизвестной. Знания должны описывать новые связи между свойствами, предсказывать значение одних признаков на основе других. Найденные знания должны быть применимы и на новых данных с некоторой степенью достоверности. Полезность заключается в том, чтобы эти знания могли принести определенную выгоду при их применении. Поставленные задачи зачастую требуют, чтобы полученные знания были в понятном для пользователя-нематематика виде. Например проще всего воспринимаются логически конструкции типа «если... то...». Алгоритмы, используемый в Data Minig, требуют большого количества вычислений. Раньше это явилось сдерживающим фактором широкого практического применения. Однако сегодняшний рост производительности современных процессоров снял остроту этой проблемы. Теперь за приемлемое время можно провести качественный анализ сотен тысяч миллионов записей.

1.ПРЕДСТАВЛЕНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 Понятие Data Mining

Средства Data Mining включают в себя очень широкий класс различных технологий и инструментов. Средства Data Mining на рынке предлагаются как средства извлечения новых знаний из данных (discovery-driven data mining), так и слегка модифицированные статистические пакеты, предназначенные для проверки гипотез (verification-driven data mining).

Важное положение Data Mining — нетривиальность разыскиваемых шаблонов. Это означает, что найденные шаблоны должны отражать неочевидные, неожиданные (unexpected) регулярности в данных, составляющие так называемые скрытые знания об отношениях. К обществу пришло понимание того, что сырые данные (raw data) содержат глубинный пласт знаний об отношениях, при грамотной “раскопке” которого могут быть обнаружены настоящие самородки.

В целом технологию Data Mining определяют как процесс обнаружения в данных:

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

Специалисты и раньше решали подобные задачи («поиск закономерностей», «индуктивный вывод» и т. п.). Но только сейчас общество в целом созрело для понимания практической важности и широты этих задач. Во-первых, как было сказано, в связи с развитием технологий записи и хранения данных сегодня на людей обрушились колоссальные потоки информационной руды в самых различных областях, которые без продуктивного анализа и извлечения новых знаний никому не нужны. И, во-вторых, средства и методы обработки данных стали доступными и удобными, а их результаты понятными широкому кругу пользователей, знакомых с данной предметной областью, а не только математикам-статистикам.

Выделяют пять стандартных типов закономерностей, которые позволяют выявлять методы Data Mining:

ассоциация;
последовательность;
классификация;
кластеризация;
прогнозирование.

Ассоциация наблюдается в данных, когда несколько событий связаны друг с другом и происходят при этом одновременно. Например, исследование, проведенное в супермаркете, может показать, что 65% купивших кукурузные чипсы берут также и «кока-колу», а при наличии скидки за такой комплект «колу» приобретают в 85% случаев. Располагая сведениями о подобной ассоциации, менеджерам легко оценить, насколько действенна предоставляемая скидка.

Закономерность типа «последовательность» предполагает наличие в данных цепочки связанных друг с другом и распределенных во времени событий. Так, например, после покупки дома в 45% случаев в течение месяца приобретается и новая кухонная плита, а в пределах двух недель 60% новоселов обзаводятся холодильником.

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

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

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

Произведем более глубокое исследование понятия кластеризация.
1.2 Кластеризация

Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. Главное отличие кластеризации от классификации состоит в том, что перечень групп четко не задан и определяется в процессе работы алгоритма.

Применение кластерного анализа в общем виде сводится к следующим этапам:

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

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

Существует две основные классификации алгоритмов кластеризации:

Иерархические и плоские.
Иерархические алгоритмы (также называемые алгоритмами таксономии) строят не одно разбиение выборки на непересекающиеся кластеры, а систему вложенных разбиений. Т.о. на выходе мы получаем дерево кластеров, корнем которого является вся выборка, а листьями — наиболее мелкие кластера.
Плоские алгоритмы строят одно разбиение объектов на кластеры.
Четкие и нечеткие.
Четкие (или непересекающиеся) алгоритмы каждому объекту выборки ставят в соответствие номер кластера, т.е. каждый объект принадлежит только одному кластеру. Нечеткие (или пересекающиеся) алгоритмы каждому объекту ставят в соответствие набор вещественных значений, показывающих степень отношения объекта к кластерам. Т.е. каждый объект относится к каждому кластеру с некоторой вероятностью.

1.2.2 Сравнение алгоритмов

Вычислительная сложность алгоритмов

Алгоритм кластеризации	Вычислительная сложность
Иерархический	O(n2)
k-средних	O(nkl), где k – число кластеров, l – число итераций
c-средних
Выделение связных компонент	зависит от алгоритма
Минимальное покрывающее дерево	O(n2 log n)
Послойная кластеризация	O(max(n, m)), где m < n(n-1)/2

Сравнительная таблица алгоритмов

Алгоритм кластеризации	Форма кластеров	Входные данные	Результаты
Иерархический	Произвольная	Число кластеров или порог расстояния для усечения иерархии	Бинарное дерево кластеров
k-средних	Гиперсфера	Число кластеров
c-средних	Гиперсфера	Число кластеров, степень нечеткости	Центры кластеров, матрица принадлежности
Выделение связных компонент	Произвольная	Порог расстояния R	Древовидная структура кластеров
Минимальное покрывающее дерево	Произвольная	Число кластеров или порог расстояния для удаления ребер	Древовидная структура кластеров
Послойная кластеризация	Произвольная	Последовательность порогов расстояния	Древовидная структура кластеров с разными уровнями иерархии

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