Высшая школа экономики

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

Кафедра

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

________________и автоматизированные системы________________

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

На тему:

Автоматическая кластеризация транзакционных данных с применением структур 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

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

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

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

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

Термин “транзакция” относится к подмножеству предметов из общей совокупности с переменным числом предметов (мощностью подмножества). Транзакциями являются записи в таблице, содержащие категориальные атрибуты и имеющие различную длину, в отличие от категориальных БД, где длина всех записей одинакова. В связи с этим транзакционные БД считаются менее упорядоченными, по сравнению с категориальными БД, что усложняет их кластеризацию. Похожие транзакции должны иметь общие предметы при определенном уровне поддержки частоты их встречаемости, не ниже заданного, называемого минимальной поддержкой. Этого трудно добиться на разреженных транзакционных данных с низкой встречаемостью одинаковых наборов предметов. Примером таких транзакций являются множества терминов в статьях или документах, когда близкие по смыслу текстовые источники содержат мало точно совпадающих терминов (ключевых слов), т.е. трудно выделить общую тему. Классическими примерами транзакций являются корзина покупок в магазине, профиль интересов клиента, множество симптомов пациента, множество характеристик образа и тому подобное.

Транзакционная или операционная база данных (Transaction database) представляет собой двумерную таблицу, которая состоит из номера транзакции (TID) и перечня покупок, приобретенных во время этой транзакции.

TID - уникальный идентификатор, определяющий каждую сделку или транзакцию.

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


TID	Приобретенные покупки
100	Хлеб, молоко, печенье
200	Молоко, сметана
300	Молоко, хлеб, сметана, печенье
400	Колбаса, сметана
500	Хлеб, молоко, печенье, сметана

Благодаря последним разработкам в области поиска информации, Web технологий и Data Mining, кластеризация транзакций играет важную роль и привлекает внимание во многих приложениях и областях, в которых ускоряет поиск ближайшего соседа. Например, кластеризация используется как важнейший метод во многих web приложениях; транзакционная кластеризация применяется в целевом маркетинге/рекламе, при обнаружении причин заболеваний, при поиске информации, основанном на содержании образа, при получении рекомендаций соединений для web пользователей, организации папок и закладок, создании информационных иерархий подобных Yahoo! и Infoseek и т.д.

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

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

Пример 1. Рассмотрим кластер из пяти транзакций

t1 = {a,e,h,k}, t2 = {a,c,f}, t3 = {a,b,c}, t4 = {b,c,i,j}, t5 = {b,e,g}.

Каждая транзакция представляет собой множество любимых боевиков пяти личностей. Из всех возможных 10 пар транзакций только две пары (t2, t3) и (t3, t4) имеют два общих боевика. Все другие пары имеют не более чем 1 общий боевик. Следовательно, парное подобие в этом кластере слабое. Однако можно заметить, что a,b,c являются типичными боевиками, так как два из них присутствуют в 3-х из пяти транзакций, т.е. вероятность любителей боевиков составляет 60%. Следовательно, эти типичные боевики можно использовать, чтобы характеризовать интересы этого кластера людей, в противоположность кластеру людей, интересующихся мелодрамами. Дело в том, что для большого числа боевиков и большого кластера людей, которые любят боевики, маловероятно, что каждый человек предпочитает те же боевики, что и другой человек в этом кластере. В связи с низкой парной похожестью внутри кластера необходимы другие критерии оценки похожести предметов в кластере, способные сгруппировать любителей боевиков и мелодрам в разные кластеры.
1.4 Кластеризация транзакций с использованием концепции часто встречающихся (“больших”) предметов

1.4.1 Подход, основанный на “больших” предметах и функциональный критерий кластеризации

Поддержка предмета в кластере Ci есть относительное число транзакций в этом кластере, которые содержат этот предмет. Примем, что |S| означает число элементов в множестве S. Для определяемой пользователем минимальной поддержки θ (0
1.4.2 Внутри кластерная стоимость (непохожесть)

На этот компонент возлагается ответственность за внутри кластерную непохожесть, измеряемую общим числом “малых” предметов, которое будет возрастать при увеличении кластера, так как при этом уменьшается число общих больших предметов и соответственно растет число малых:

Intra(C) = | ki=1 Smalli| (1)

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

, (1*)

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

1.4.3 Между кластерная стоимость (похожесть)

На этот компонент возлагается ответственность за похожесть между кластерами. Поскольку именно большие предметы вносят похожесть в кластер, каждый кластер должен иметь минимально возможное перекрытие по большим предметам с другими кластерами. Это перекрытие определяется выражением:

Функция штрафует (Inter (C) ) кластеры с одинаковыми или перекрывающимися большими предметами за счет увеличения первой суммы и уменьшения объединения, исключающего дублирование. Функция Inter(C) ограничивает дублирование больших предметов в различных кластерах и создание похожих кластеров. Если сложить два компонента вместе, то можно ввести вес w их относительной важности. Тогда функциональный критерий, штрафующий за неправильную кластеризацию, примет вид:

Вес w > 1 увеличивает долю штрафа за внутри кластерную непохожесть, а вес w
1.4.4 Цель кластеризации

Для заданной коллекции транзакций и при заданном уровне минимальной поддержки найти такую кластеризацию С, которая отвечает минимуму ее стоимости Cost(C) (минимальному штрафу).

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

Пример. Рассмотрим 6 транзакций:

t₁={a,b,c}, t₂={a,b,c,d}, t₃={a,b,c,e}, t₄={a,b,f} t₅={d,g,h}, t₆={d,g,i}

Рассмотрим кластеризацию С с одним кластером С₁ = {t₁,t₂,t₃,t₄,t₅,t₆}. Предположим, что пользователь установил минимальную поддержку 60%. Большие предметы должны содержаться, по меньшей мере, в 4 транзакциях (6*60%). В четырех транзакциях содержатся только {a,b}, поэтому |Large₁| = 2. Остальные предметы являются малыми Small₁ ={c,d,e,f,g,h,i}, и по формуле (32) Intra(C₁) = 7. Между кластерная похожесть Inter(C₁) = 2 – 2 = 0 по формуле из пункта 1.4.3. Таким образом при w = 1, получаем Cost(C₁) = 7. Как видно, штраф накладывается за большое число малых предметов, что является неизбежным следствием уменьшения числа больших предметов при чрезмерном укрупнении кластера. Одного кластера мало.

Рассмотрим второй вариант кластеризации C₂ с двумя кластерами {C₁ = {t₁,t₂,t₃,t₄}, C₂ = {t₅,t₆}}. Для кластера С₁ большие предметы должны содержаться по меньшей мере в 4*60%  3-х транзакциях. Такими предметами для транзакций в С₁ являются {a,b,c}, т.е. |Large₁| = 3. Small₁ = {d,e,f} и |Small₁| = 3. Подобно этому, Large₂ = {d,g}, |Large₂| = 2, Small₂ = {h,i}, |Small₂| = 2. Поскольку все малые предметы в кластерах С₁ и С₂ различные, их объединение приводит к простому суммированию малых предметов Intra (C₂) = 3 + 2 = 5). Inter(C₂) = (3 + 2) – (3 + 2) = 0. Cost(C₂) = 5 + 0 = 5. Кластеризация С₂ лучше, чем С₁ за счет уменьшения штрафа за сумму малых предметов при нулевом штрафе за одинаковые большие предметы, поскольку таковых нет.

Рассмотрим кластеризацию C₃ = {C₁ = {t₁,t₂}, C₂ = {t₃,t₄}, C₃ = {t₅,t₆}}. Общими большими предметами в кластере С₁ являются {a,b,c}, т.е. Large₁ = {a,b,c}, |Large₁| = 3. Small₁ = {d}, Large₂ = {a,b}, Small₂ = {c,e,f}, Large₃ = {d,g}, Small₃ = {h,i}. Intra(C₃) = 1 +3 + 2 = 6 (суммируются малые предметы по трем кластерам, поскольку нет повторов). Inter(C₃) = 7 – 5 = 2. Здесь 7 = 3 + 2 + 2 – это простая сумма больших предметов в 3-х кластерах с повтором предметов {a,b}; 5 - это объединение больших предметов по трем кластерам, исключающее повторы предметов а и b, что дает {a,b,c,d,g} с числом элементов 5; Стоимость Cost(C₃) = 6 + 2 = 8. В сравнении с С₂ расщепление {t₁,t₂,t₃,t₄} на два кластера С₁ и С₂ увеличивает стоимость, поскольку приводит к их большей внутри кластерной непохожести (6 против 5) и между кластерной похожести (2 против 0), за что и налагается штраф.

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

Значение Cost(C) отражает правильность выбора пользователем минимальной поддержки. Однако этот критерий не рекомендуется использовать для выбора минимальной поддержки. Действительно, при минимальной поддержке 1/n, где n – число транзакций, группирование всех транзакций в один кластер даст Cost(C) = 0 (оба слагаемых равны 0). Очевидно, это нельзя интерпретировать как лучшее решение.
1.4.5 Обобщенный алгоритм кластеризации

Коллекция транзакций хранится в файле на диске. Алгоритм читает каждую транзакцию t последовательно и присоединяет t к существующему кластеру, или создает t как новый кластер, тот который минимизирует стоимость для текущей кластеризации. Идентификатор кластера каждой транзакции записывается обратно в файл. Это называется фазой размещения. В фазе усовершенствования алгоритм читает каждую транзакцию t (в том же порядке как в фазе размещения), перемещает t в существующий не одиночный кластер (возможно, оставляет там, где она есть), чтобы минимизировать Cost(C). После каждого перемещения идентификатор кластера у транзакции обновляется, и любой пустой кластер немедленно уничтожается. Если ни одна транзакция не перемещается при проходе по всем транзакциям, фаза усовершенствования оканчивается. В противном случае начинается новый проход. Существенно, что при добавлении каждой транзакции минимизируется глобальный критерий стоимости Cost(C). Ключевым шагом является нахождение адреса кластера для размещения или перемещения транзакции. Этот вопрос обсуждается ниже.

Парадигма следования фазы усовершенствования за фазой размещения заимствована из алгоритмов k-средних и k-мод. Однако в предлагаемом алгоритме имеются важные отличия. Во-первых, не требуется предварительно определять число k кластеров. Вместо этого кластеры создаются и уничтожаются динамически на основе критерия стоимости. Во-вторых, адрес кластера транзакции определяется не по расстоянию до ближайшего кластера или до его моды/центроида, а путем расчета стоимости Cost(C), являющейся не локальным, а глобальным критерием качества.

/* Фаза размещения транзакций */

while not end of the file do
read the next transaction , -- >;
allocation t to an existing or new cluster C_i to minimize Cost(C);
write _i >;

/* Фаза улучшения кластеризации */

repeat
not_moved = true;
while not end of the file do
read the next transaction i > ;
move t to an existing non-singleton cluster C_j to minimize Cost(C);
if C_i ≠ C_j then
write j >;
not_moved = false;
eliminate any empty cluster;
until not_moved;

Рис. 5 Обобщенный алгоритм кластеризации
1.4.6 Обновление значения функционального критерия

Допустим, что MinSup_i = θ * |C_i|. Поддержка данного предмета в C_i характеризует число транзакций в этом кластере, которые содержат этот предмет. Поэтому предмет является большим в кластере C_i, если и только если его поддержка в этом кластере больше или равна MinSup_i. Для каждого кластера C_i необходимо сохранять две структуры данных в памяти: хэш-таблицу Hash_i и бинарное дерево Btree_i. Эти структуры являются стандартными методами индексации для больших БД.

Hash_i: Хэш-таблица для C_i с предметами в виде их индексных ключей. Для каждого предмета e в C_i имеется вход в форме в Hash_i, где tree_addr есть адрес соответствующего листового входа для e в Btree_i (см. ниже). Hash_i обеспечивает доступ к пути, чтобы вставлять, удалять или обновлять поддержку данного предмета.

Btree_i: Это бинарное дерево B-tree с поддержкой предметов в C_i в виде индексных ключей. Для каждого предмета e в C_i имеется листовой вход в форме в Btree_i, где sup есть поддержка e в C_i, а hash_addr есть адрес соответствующего входа для e в Hash_i. Btree_i обеспечивает доступ к пути для нахождения всех предметов, имеющих данную поддержку.

Минимальная поддержка MinSup_i разделяет листовые входы Btree_i на входы для больших предметов Large_i (в правом поддереве) и входы для малых предметов Small_i (в левом поддереве). Особый интерес вызывают предметы, находящиеся вблизи границы раздела: малые предметы, имеющие поддержку (MinSup_i – 1), и большие предметы, имеющие поддержку MinSup_i. Когда транзакция помещается в кластер или перемещается в другой кластер, поддержка некоторых предметов будет увеличиваться или уменьшаться на 1. Следовательно, эти предметы могут пересекать границу. Эффективное сохранение следа таких изменений является главной задачей сопровождения. Во-первых, мы определяем две операции.

Мы определяем Inc(C_i, e) как операцию, которая увеличивает поддержку данного предмета e в C_i на 1.

Некоторые шаги включают в себя следующее содержание:

Отыскать Hash_i для входа . Допустим, что является листовым входом в Btree_i, на который указывает tree_addr.
Увеличить поддержку sup на 1 в .
Переместить направо, чтобы пройти все листовые входы

при условии sup’

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

Когда транзакция t присоединяется к кластеру C_i, MinSup_i, поддержка каждого предмета, содержащегося в транзакции, увеличивается на 1. Допустим, что OldMinSup_i и MinSup_i обозначают минимальную поддержку для C_i перед и после присоединения транзакции к кластеру.
1.4.7 Обновление числа “больших” предметов

Алгоритм для обновления дан на рис.6. Для каждого предмета е в t отыскивается Hash_i. Если е найдено хэше кластера, то увеличиваем на 1 его sup в Btree_i. Если е не найдено, то вставляем е с sup = 1 в Hash_i и Btree_i. Это показано в строках (4) – (9).

|C_i| ++; /* размер кластера увеличивается на 1*/
OldMinSup_i = MinSup_i;
MinSup_i = θ * |C_i|;

/* обновление поддержки предметов в t */

foreach item e in t do /* для каждого предмета е в транзакции t выполнить */;
look up Hash_i for e /* отыскать Hash_i для предмета е */;
if e is found then /* если е найден, то */;
Inc(C_i, e) /* */
else
insert e into Hash_i and Btree_i with sup = 1

/* малые предметы становятся большими */

if MinSup_i = = OldMinSup_i then
search Btree_i for the items e with sup = MinSup_i;
foreach returned item e do /*для каждого возвращенного предмета е выполнить*/
if e is in t then |Large_i| ++; /* если е находится в t, то увеличить число больших предметов в кластере C_i на 1*/;

/* большие предметы становятся малыми */

if MinSup_i = = OldMinSup_i + 1 then
search Btree_i for the items e with sup = OldMinSup_i;
foreach item e returned do /* для каждого возвращенного предмета е выполнить */
if e is not in t then |Large_i| - -; /*если е нет в t, то уменьшить число больших предметов в кластере на 1 */;

Рис. 6 Обновление числа больших предметов при добавлении транзакции в кластер

Малые предметы становятся большими: малый предмет е становится большим, если (а) MinSupi = OldMinSupi, (b) е находится в t, и (с) sup = MinSupi. Этот случай отслеживается в строках (10) – (13).

Большие предметы становятся малыми: большой предмет становится малым, если (а) MinSupi = OldMinSupi + 1, (b) е не находится в t, и (с) sup = OldMinSupi. Этот случай отслеживается в строках (14) – (17).

Для обновления числа элементов в множествах |ki=1Smalli| и |ki=1Largei|

используются две хэш-таблицы LargeHash и SmallHash, чтобы сохранять число кластеров с большими и малыми предметами. Когда малый предмет е становится большим в кластере, его число в SmallHash уменьшается на 1, а его число в LargeHash увеличивается на 1, т.е. эти числа изменяются согласованно. Как только это число достигает 0 в хэш-таблице, соответствующая ячейка удаляется из этой таблицы. Как только новый предмет е добавляется в кластер, новая ячейка с начальным значением 1 вставляется в LargeHash или SmallHash, в зависимости от того, является ли е большим или малым предметом в этом кластере. Когда транзакция t присоединяется к кластеру, изменение числа |ki=1Smalli| (или |ki=1Largei| соответственно) заключается в числе новых вставляемых ячеек минус число ячеек, удаляемых в SmallHash (или LargeHash, соответственно).

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

Подобные рассуждения применимы к случаю удаления транзакции из кластера.

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

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

Цель работы – предложить усовершенствованный метод реализации классического алгоритма LargeItem в части удобства и быстроты поиска кластерных наборов в транзакционных БД большого объема (порядка 100000 транзакций и более). Использовать для этого рекурсивные структуры данных в виде сбалансированного бинарного дерева В+.

Исходя из предложенной цели работы, можно сформулировать следующие задачи дипломной работы:

1) Изучить принцип работы алгоритма LargeItem в первоначальном варианте.

2) Модернизировать алгоритм кластеризации с учетом применения B+ деревьев в его работе.

3) Разработать и протестировать генератор баз данных, используя за основу существующий генератор из работы Кызылов А. В. «Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата» за 2009 год.

4) Реализовать разработанный модернизированный алгоритм на языке Java с применение библиотек для работы со сбалансированными двоичными деревьями поиска.

5) Оценить эффективность предложенного решения на тестовых примерах.

Первоначально произведем разбор таких понятий как двоичное дерево поиска, а также сбалансированное дерево поиска.

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

Рис. 7 Пример двоичного дерева поиска

Двоичное дерево поиска ( binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

Оба поддерева — левое и правое, являются двоичными деревьями поиска.
У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X.

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

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

Для целей реализации двоичное дерево поиска можно определить так:

Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) - ссылки на родительский элемент.
Данные (data) обладают ключом (key), на котором определена операция сравнения "меньше". В конкретных реализациях это может быть пара (key, value) - (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.
Для любого узла X выполняются свойства дерева поиска: key[left[X]]

Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам.

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

Двоичное дерево поиска применяется для построения более абстрактных структур, таких как множества, мультимножества, ассоциативные массивы.
2.2.1 Основные операции в двоичном дереве поиска

Базовый интерфейс двоичного дерева поиска состоит из трех операций:

FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.
INSERT(K,V) — добавление в дерево пары (key, value) = (K, V).
REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

Поиск элемента (FIND)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

Алгоритм:

(1)Если дерево пусто, сообщить, что узел не найден, и остановиться.

(2)Иначе сравнить K со значением ключа корневого узла X.

(3)Если K=X, выдать ссылку на этот узел и остановиться.

(4)Если K>X, рекурсивно искать ключ K в правом поддереве Т.

(5)Если K

Добавление элемента (INSERT)

Дано: дерево Т и пара (K,V).

Задача: добавить пару (K, V) в дерево Т.

Алгоритм:

(1)Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.

(2)Иначе сравнить K с ключом корневого узла X.

(3)Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.

(4)Если K

Удаление узла (REMOVE)

Дано: дерево Т с корнем n и ключом K.

Задача: удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм:

(1)Если дерево T пусто, остановиться;

(2)Иначе сравнить K с ключом X корневого узла n.

(3)Если K>X, рекурсивно удалить K из правого поддерева Т;

(4)Если K

(5)Если K=X, то необходимо рассмотреть три случая.

(6)Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;

(7)Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;

(8)Если оба ребёнка присутствуют, то

(9)найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);

(10)скопируем данные (кроме ссылок на дочерние элементы) из m в n;

(11)рекурсивно удалим узел m.

Обход дерева (TRAVERSE)

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f. Эта функция обычно работает только с парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

INFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).
PREFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).
POSTFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).

INFIX_TRAVERSE:

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм:

(1)Если дерево пусто, остановиться.

(2)Иначе

(3)Рекурсивно обойти левое поддерево Т.

(4)Применить функцию f к корневому узлу.

(5)Рекурсивно обойти правое поддерево Т.

В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.

Разбиение дерева по ключу

Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами

Балансировка дерева

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

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

Для балансировки дерева применяется операция "поворот дерева". Поворот направо выглядит так:

Рис. 8

было Left(A) = L, Right(A) = B, Left(B) = C, Right(B) = R
поворот меняет местами A и B, получая Left(A) = L, Right(A) = C, Left(B) = A, Right(B) = R
также меняется в узле Parent(A) ссылка, ранее указывавшая на A, после поворота она указывает на B.

Поворот направо выглядит так же, достаточно заменить в вышеприведенном примере все Left на Right и обратно.

Достаточно очевидно, что поворот не нарушает упорядоченность дерева, и оказывает предсказуемое (+1 или -1) влияние на глубины всех затронутых поддеревьев.

Для принятия решения о том, какие именно повороты нужно совершать после добавления или удаления, используются такие алгоритмы, как «красно-чёрное дерево» и АВЛ.

Оба они требуют дополнительной информации в узлах – 1 бит у красно-черного или знаковое число у АВЛ.

Красно-черное дерево требует

АВЛ-дерево требует
2.3 B+ дерево

Рис. 9

Пример B+ дерева, связывающего ключи 1-7 с данными d1-d7. Связи (выделены красным) позволяют быстро обходить дерево в порядке возрастания ключей.

B+ дерево — структура данных, представляет собой сбалансированное дерево поиска. Является модификацией B-дерева, истинные значения ключей которого содержатся только в листьях, а во внутренних узлах — ключи-разделители, содержащие диапазон изменения ключей для поддеревьев.

2.3.1 Построение

При построении B+ дерева, его временами приходится перестраивать. Это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от k до 2k, где k — степень дерева. При попытке вставить в узел (2k+1)-й ключ возникает необходимость разделить этот узел. В качестве ключа-разделителя сформированных ветвей выступает (k+1)-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+ дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей k. Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.

2.3.2 Свойства:

В B+ дереве легко реализуется независимость программы от структуры информационной записи.
Поиск обязательно заканчивается в листе.
Удаление ключа имеет преимущество — удаление всегда происходит из листа.
Другие операции выполняются аналогично B-деревьям.
B+ деревья требуют больше памяти для представления чем B-деревья.
B+ деревья имеют возможность последовательного доступа к ключам.

следующая страница >>