Размещено на http://www.allbest.ru/

Введение

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

Для решения данных вопросов существуют математические методы, которые и образуют направление 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	Древовидная структура кластеров
Минимальное покрывающее дерево	Произвольная	Число кластеров или порог расстояния для удаления ребер	Древовидная структура кластеров
Послойная кластеризация	Произвольная	Последовательность порогов расстояния	Древовидная структура кластеров с разными уровнями иерархии

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

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) предмет является “большим” в кластере Ci, если его поддержка в кластере не меньше чем и*|Ci|; в противном случае предмет является “малым” в кластере Ci. Понятно, что большие предметы являются популярными предметами в кластере, которые вносят похожесть в кластер, в то время как малые предметы вносят непохожесть в кластер. Примем, что Largei означает множество больших предметов в Ci, и Smalli означает множество малых предметов в этом кластере. Рассмотрим кластеризацию C = {C1,…Ck}. Чтобы минимизировать стоимость С, имеются два компонента: внутри кластерная и между кластерная стоимости.

1.4.2 Внутри кластерная стоимость (непохожесть)

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

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

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

, (1*)

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

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

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

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

Вес w > 1 увеличивает долю штрафа за внутри кластерную непохожесть, а вес w < 1 делает акцент на штрафе за похожесть кластеров между собой. По умолчанию w = 1.

1.4.4 Цель кластеризации

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

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

1.4.5 Обобщенный алгоритм кластеризации

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

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

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

1. while not end of the file do

2. read the next transaction < t, -- >;

3. allocation t to an existing or new cluster Ci to minimize Cost(C);

4. write <t, Ci >;

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

5. repeat

6. not_moved = true;

7. while not end of the file do

8. read the next transaction < t, Ci > ;

9. move t to an existing non-singleton cluster Cj to minimize Cost(C);

10. if Ci ? Cj then

11. write < t, Cj >;

12. not_moved = false;

13. eliminate any empty cluster;

14. until not_moved;

Рис. 5 Обобщенный алгоритм кластеризации

1.4.6 Обновление значения функционального критерия

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

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

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

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

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

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

1. Отыскать Hashi для входа < e, tree_addr >. Допустим, что < sup, hash_addr > является листовым входом в Btreei, на который указывает tree_addr.

2. Увеличить поддержку sup на 1 в < sup, hash_addr >.

3. Переместить < sup, hash_addr > направо, чтобы пройти все листовые входы

< sup', hash_addr' > при условии sup' < sup.

4. Для каждого входа < sup', hash_addr' >, перемещенного в (с), обновить адреса в дереве, содержащем соответствующие входы в Hashi.

5. Обновить предыдущие входные индексы в < sup, hash_addr > чтобы отразить изменение поддержки, если необходимо.

Когда транзакция t присоединяется к кластеру Ci, MinSupi, поддержка каждого предмета, содержащегося в транзакции, увеличивается на 1. Допустим, что OldMinSupi и MinSupi обозначают минимальную поддержку для Ci перед и после присоединения транзакции к кластеру.

1.4.7 Обновление числа “больших” предметов

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

1. |Ci| ++; /* размер кластера увеличивается на 1*/

2. OldMinSupi = MinSupi;

3. MinSupi = и * |Ci|;

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

4. foreach item e in t do /* для каждого предмета е в транзакции t выполнить */;

5. look up Hashi for e /* отыскать Hashi для предмета е */;

6. if e is found then /* если е найден, то */;

7. Inc(Ci, e) /* */

8. else

9. insert e into Hashi and Btreei with sup = 1

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

10. if MinSupi = = OldMinSupi then

11. search Btreei for the items e with sup = MinSupi;

12. foreach returned item e do /*для каждого возвращенного предмета е выполнить*/

13. if e is in t then |Largei| ++; /* если е находится в t, то увеличить число больших предметов в кластере Ci на 1*/;

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

14. if MinSupi = = OldMinSupi + 1 then

15. search Btreei for the items e with sup = OldMinSupi;

16. foreach item e returned do /* для каждого возвращенного предмета е выполнить */

17. if e is not in t then |Largei| - -; /*если е нет в t, то уменьшить число больших предметов в кластере на 1 */;

Малые предметы становятся большими: малый предмет е становится большим, если (а) 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]] < key[X] ? key[right[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<X, рекурсивно искать ключ K в левом поддереве Т.

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

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

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

Алгоритм:

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

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

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

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

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

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

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

Алгоритм:

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

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

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

(4)Если K<X, рекурсивно удалить 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, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.

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

Операция "разбиение дерева по ключу" позволяет разбить одно дерево поиска на два: с ключами <K0 и ?K0.

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

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

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

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



Рис. 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 после удаления, но при этом худший дисбаланс может оказаться до 2 раз (самый длинный путь в 2 раза длиннее самого короткого).

АВЛ-дерево требует <= 2 поворотов после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более, чем на 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+ деревья имеют возможность последовательного доступа к ключам.

3. Разработка программного обеспечения

Для разработки программного обеспечения использован язык Java. Разработка проводилась в среде Eclipse Ganymede 3.2. В качестве СУБД для тестирования приложения использован MySQL 5.1

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

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

Для примера возьмем 4 транзакции:

1: Вода, Мясо, Хлеб

2: Молоко

3: Сметана, Мясо, Макароны, Вода

4: Хлеб, Молоко

В основном, для хранения данных используются реляционные базы данных (Oracle, DB2,MySql и другие). В реляционных базах данные хранятся в таблицах. Одной из структур хранения транзакций покупок может быть разделение данных на 2 таблицы:

· Таблица товаров

· Таблица транзакций

Рассмотрим таблицу товаров

Id	Name
10	Молоко
20	Хлеб
30	Мясо
40	Макароны
50	Сметана
60	Вода

В таблице товаров хранится список всех товаров, присутствующих в базе.

Таблица состоит из 2 столбцов. В столбце "Id" хранится уникальный иденти-фикатор товара, первичный ключ. Столбец "Name" содержит наименование товара.

Tid	Element
1	60
1	30
1	20
2	10
3	50
3	30
3	40
3	60
4	20
4	10

Таблица транзакций (Рисунок 11) также состоит из 2 столбцов. В столбце "Tid" находятся номера транзакций (их также можно назвать идентификаторами транзакций). Столбец "Element" содержит идентификатор одного из товаров, купленного в эту транзакцию. Таким образом, первая транзакция из нашего примера (Вода, Мясо, Хлеб) представлена в таблице транзакций тремя записями. Вторая транзакция, состоящая из одного товара, представлена одной записью и т.д.

Как видно из вышесказанного, названия товаров не хранятся в таблице транзакций, для них заведена специальная таблица. Вместо названий товаров таблице транзакций хранятся первичные ключи товаров (то есть ссылки на эти товары).

Данный способ представления данных дает следующие преимущества:

· Экономия памяти - наименование товара, как правило, занимает больше памяти, чем его идентификатор.

· Упрощение модификации товара - при изменении наименования товара, достаточно, изменить значение столбца "Name" в таблице товаров для данного товара. Таблицу транзакций изменять не надо, так как в ней хранятся только идентификаторы товаров.

· Упрощение модификации транзакции - поскольку транзакции хранятся поэлементно, то при удалении товара из транзакции или добавлении товара в транзакцию, происходит добавление или удаление записи в таблице транзакций.

Для сравнения рассмотрим другие способы представления.

Tid	Elements
1	60,30,20
2	10
3	50,30,40,60
4	20,10

В таблице транзакций на рисунке 12 столбец "Elements", содержащий идентификаторы товаров, является многозначным. При удалении товара из транзакции придется удалять идентификатор товара из cтроки, это более трудоемкая операция, чем удаление одной записи из таблицы транзакций на рисунке 11.

Tid	Молоко	Хлеб	Мясо	Макароны	Сметана	Вода
1	0	1	1	0	0	1
2	1	0	0	0	0	0
3	0	0	1	1	1	1
4	1	1	0	0	0	0

В таблице транзакций на рисунке 13 для каждого товара есть свой столбец. Каждая транзакция является отдельной записью, номер транзакции хранится в столбце "Tid". Если товар присутствует в транзакции, то значение столбца товара для данной транзакции равно 1, иначе 0. Данный способ представления нежизнеспособен, поскольку число столбцов не фиксировано, и при удалении или добавлении товара придется удалять или добавлять столбец, это приведет к пересчету всей таблицы.

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

Для создания тестовых баз было разработано приложение "GeneratorDB", способное генерировать случайным образом заданное число транзакций с заранее заданными элементами, минимальным и максимальным числом элементов в транзакции. За основу при разработке была взята программа-генератор из диплома Анваера А.Е. "Разработка алгоритма извлечения ассоциативных правил из множества категориальных данных" за 2008 год.

Процесс создания баз данных с помощью этого приложения можно разделить на 2 этапа:

1. Настройка параметров для набора, генерирование этого набора и отображение его на экране.

2. Создание базы данных и записи в нее сгенерированных набора.

Рассмотрим интерфейс приложения "GeneratorDB" на рисунке 14.

Процесс работы с данным приложением довольно прост. Пользователь задает параметры набора, который хочет сгенерировать, и нажимает кнопку "Добавить случайные транзакции". Сгенерированный набор отображается пользователю. Пользователь может редактировать сгенерированный набор. Далее пользователь может задать новые параметры и добавить к первому набору еще случайных транзакций. После того как окончательный набор транзакций сгенерирован, пользователь указывает имя ODBC драйвера, имя базы и нажимает кнопку "Записать" для создания базы данных транзакций (Подробно об установке ODBC драйвера и настройке подключения описано в приложении 1).

Рассмотрим элементы управления приложением "GeneratorDB" более подробно:

В верхней части программы находятся 4 поля:

Количество элементов - в этом поле указывается количество элементов из списка товаров, которые будут принимать участие в генерации.

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

Рисунок 14 Приложение "GeneratorDB"

Количество элементов в транзакции минимальное/максимальное - от этих параметров зависит плотность базы. Чем больше максимальное и минимальное количество элементов в транзакции, тем плотнее база.

Рисунок 15 Панель продуктов приложения "GeneratorDB"

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

Например, запись "1.а(0)" обозначает, что продукт называется "a", имеет порядковый номер 1 и, при записи в базу в таблицу товаров, будет иметь идентификатор "1". За названием продукта в скобках находится счетчик продукта, равный количеству данных продуктов, присутствующих в сгенерированном наборе транзакций.

С помощью кнопки "Добавить продукт" можно добавить новый продукт в список.

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

Кнопка "Удалить" удаляет продукт из списка, эта кнопка доступна только, если продукт отсутствует в сгенерированном наборе.

Кнопка "Редактировать" позволяет изменять имя продукта из списка, эта кнопка доступна только, если продукт отсутствует в сгенерированном наборе.

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

1. Алфавит - шаблон состоит из 26 продуктов, каждый элемент шаблона

является буквой английского алфавита. Этот шаблон стоит в программе

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

находится данные 26 продуктов.

2. 1000 элементов - шаблон состоит из тысячи продуктов. Названия

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

"e1" до "e1000".

3. Магазин - шаблон состоит из 20 продуктов. В этом шаблоне присутствуют названия продуктов (пепси, хлеб, молоко и т.д). Для тестирования реалистичность названий продуктов не является принципиальной.

Сменить шаблон можно с помощью кнопки "Шаблоны". После нажатия на эту кнопку пользователю предлагается список шаблонов для выбора (рисунок 4.3).

Рисунок 16 Диалоговое окно выбора шаблонов

Сгенерированные транзакции отражаются в таблице на панели транзакций (Рисунок 17). Таблица транзакций состоит из 2 колонок. Колонка "TID" содержит номер транзакции. Колонка "Product" отображает один из продуктов входящий в данную транзакцию. Таким образом, если посмотреть на рисунок 4.4, мы увидим, что транзакция 1 состоит из одного элемента -"w" и занимает в таблице одну запись. А транзакция 2, напротив, из 7 элементов-(b,c,g,l,m,n,o), и занимает в таблице 7 записей.

Для наглядности представления транзакций можно воспользоваться кнопкой "Скомпоновать". При нажатии на эту кнопку все продукты сгруппируются по транзакциям. Результат работы этой кнопки можно увидеть на рисунке 4.5. Другие кнопки:

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

Кнопка "Удалить запись" - удаляет 1 запись из набора. Кнопка доступна только в режиме отображения транзакций, показанном на рисунке 17.

Кнопка "Добавить случайные транзакции" - генерирует и добавляет набор случайные транзакции в соответствии с заданными параметрами (количество элементов, транзакций и т.д.).

"Случайное место" - взведение данного флага означает, что при генерации транзакции будут добавляться в случайное место уже сгенерированного набора. Иначе транзакции будут добавляться в конец набора.

Рисунок 17 Панель транзакций

В правом нижнем углу окна приложения "GeneratorDB" (Рисунок 14) находится панель создания базы данных. Данная панель состоит из 2 полей и одной кнопки:

· ODBC драйвер - В это поле пользователь вводит название подключения к ODBC драйверу.

Имя базы - В это поле пользователь вводит имя новой базы.

Кнопка "Записать" начинает запись данных в новую базу. Эта операция является самой трудоемкой в данном приложении, поэтому и занимает много времени. Для примера: база в 40000 транзакций у меня создается около 30-35 минут.

Созданная генератором база содержит 2 таблицы: "Tovars" и "Trans", которые имеют строение, аналогичное строению таблице товаров и таблице транзакций из пункта 3.1

С помощью приложения "GeneratorDB" можно создать необходимые для тестирования базы.

Рисунок 18 Группировка продуктов с помощью кнопки "Скомпоновать"

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

Модернизация обобщенного алгоритма кластеризации состоит в использовании вместо обычных бинарных деревьев сбалансированных бинарных деревьев(B+ tree).

Данная модернизация позволяет отказаться от использования Hash таблиц, как это показано в алгоритме, представленном в п. 1.4.6.

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

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

(1)Увеличить размер кластера на 1

(2)Произвести обновление поддержки предметов в заданном кластере

(3)Для каждого предмета в транзакции

(4) Произвести поиск по дереву

(5) Если предмет найден - увеличить поддержку предмета в кластере

(6) В противном случае внести предмет в дерево и присвоить поддержку 1

(7)Произвести проверку больших и малых предметов в кластере

(8)Если поддержка предмета не менялась

(9)увеличить число больших предметов в кластере

(10)Иначе - уменьшить число больших предметов в кластере

(11) Произвести взвешивание дерева

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

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

3.3.1 Интерфейс программы

Для запуска кластеризации пользователю нужно ввести 4 параметра:

а) Название ODBC драйвера с созданным подключением. Как создать

такое подключение, говорится в приложении 1.

б) Название базы.

в) Коэффициент минимальной поддержки в процентах.

г) Путь к конечной базе в виде текстового файла с расширением .txt (например, с:\klaster.txt).

При нажатии на кнопку "Кластеризовать", при корректно заполненных полях, описанных выше, результат кластеризации будет записан в текстовый файл.

В выходном файле (Рисунок 20) имеется 3 столбца:

· Номер транзакции, а также предметы в данной транзакции

· Номер кластера, к которому принадлежит данная транзакции

· "Большие предметы" принадлежащие данному кластеру

Рис.19 Приложение LargeItem

Рис.20 Выходной файл приложения

3.3.2 Пример работы алгоритма и проверка функционального критерия

Для начала проверим правильность расчета штрафа(costC) за неправильную кластеризацию. При начальной стадии кластеризации возникает вопрос, как формируются кластеры, будет ли вторая транзакция присоединена к первой, образовав кластер из 2 транзакция, или образуется 2 кластера.

Рассмотрим несколько возможных случаев:

1)Имеется 2 транзакции по 5 предметов. Общих транзакций нет.

Если поместить их в разные кластеры, то получим 2 кластера, в каждом из которых все предметы большие, независимо от поддержки. Таким образом сумма больших предметов по кластерам равна 10.