К дипломной работе
Скачать 0.82 Mb.
|
3.3. Программная реализация алгоритма LargeItemМодернизация обобщенного алгоритма кластеризации состоит в использовании вместо обычных бинарных деревьев сбалансированных бинарных деревьев(B+ tree). Данная модернизация позволяет отказаться от использования Hash таблиц, как это показано в алгоритме, представленном в п. 1.4.6. Это возможно за счет того, что в B+ деревьях нет необходимости использовать внешние индексные ключи, а также навигация и поиск по дереву сделаны проще (за счет возможность последовательного доступа к ключам). Таким образом, обобщенный и модернизированный алгоритм обновления числа “больших” представлен на рисунке 19: (1)Увеличить размер кластера на 1 (2)Произвести обновление поддержки предметов в заданном кластере (3)Для каждого предмета в транзакции (4) Произвести поиск по дереву (5) Если предмет найден – увеличить поддержку предмета в кластере (6) В противном случае внести предмет в дерево и присвоить поддержку 1 (7)Произвести проверку больших и малых предметов в кластере (8)Если поддержка предмета не менялась (9)увеличить число больших предметов в кластере (10)Иначе – уменьшить число больших предметов в кластере (11) Произвести взвешивание дерева Рис. 19 Для подсчета количества больших и малых предметов в кластерах используется аналог хэш-таблицы. В ней каждому кластеру ставится в соответствие количество больших и малых предметов в нем. Также в этой таблице хранится информация о том, какие это предметы. Именно на основе этой таблицы и формируется конечный результат программы кластеризации, выводимый пользователю. 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. 2) Имеется 2 транзакции по 5 предметов. Один предмет общий. Если не объединять их в один кластер, то получим 2 кластера с суммой больших предметов 10, но один предмет общий и малых нет. Получим штраф 0+10-1=9. При объединении все предметы, кроме одного становятся малыми, т.е штраф за малые 8. Больших предметов 1, но т.к в кластере он повторен, то и число повторов необходимо вычесть. Получается, что общий штраф не меняется и составит 8. Как видно – объединение транзакций выгодно. 3)Тот же случай, что и в пункте 2, но общих предметов в транзакциях два. Из расчета получаем, что при образовании 2 кластеров – общий штраф 8 (10-2=8). При объединении все предметы, кроме двух в каждой транзакции становятся малыми, т.е штраф за малые предметы – 16. Больших предметов 2, при этом каждый повторяется дважды. Т.о общий штраф получается 16. Это еще одно подтверждение выгодности объединения транзакций с общими предметами в один кластер. Проверим выгодность добавления транзакций с общими предметами в кластер. 1) Допустим, имеется кластер, содержащий две транзакции по 10 предметов с 2 общими предметами. Добавляем транзакцию с 10 элементами, в которой нет общих с кластером предметов. Если образовать 2 кластера, то число больших предметов в первом кластере не изменится и так и будет равно 2. В новом кластере число больших предметов станет 10. Т.о число малых предметов в первом кластере – 16, а общий штраф будет равен – 28. При добавлении транзакции в существующий кластер количество малых предметов увеличится на 10 и станет 26 (16+10=26).Общий штраф будет равен 28 (26+2=28). Т.о в данном случае объединение не дает выгоды. 2) Проверим аналогичный случай, но в добавляемой транзакции один предмет является общим с кластером. Если не объединять транзакцию и существующий кластер в новый кластер, то число больших предметов будет равно 3+10-1 (поскольку 1 предмет является общим). Малых предметов в первом кластере 16. Общий штраф составляет 28 (3+10-1+16=28). При объединении транзакции и кластера в новый кластер общее число малых предметов составит 15+9=24. Число больших предметов 3, но т.к один является общим, при конечном расчета штрафа будем отнимать единицу. Общий штраф в данном случае будет равен 24+3-1=26. Видно, что объединение дает выгоду. Из всего вышеперечисленного можно сделать простой вывод – наличие общих предметов в транзакциях стимулирует их объединение в один кластер. Теперь рассмотрим принцип работы алгоритма на тестовом примере. Основными этапами работы алгоритма является:
Разберем эти этапы более подробно. 3.3.2.1 Первичный проход по базе транзакций и их объединение в кластеры Предположим, что на начальном этапе имеется гипотетическая база, состоящая из девяти транзакций. Обозначим их цифрами от 1 до 9.  Рис. 21 Транзакции 1-9 Будем поочередно брать каждую транзакций и сравнивать со следующими, пока не дойдем до момента, когда в двух рассматриваемых транзакциях будем иметь один или несколько одинаковых элементов (Рис. 22).  Рис. 22 Транзакции 2, 4-9 и новообразованный кластер (1,3) Данная пара транзакций объединяется в кластер и для нее будет составлено бинарное дерево, таблица учета предметов, а также данные о количестве транзакций в новообразованном кластере будут добавлены в специальную таблицу (для каждого нового кластера добавляется новая строка таблицы). Ниже приведен произвольный пример структуры такой таблицы.
Рис. 23 Таблица учета количества транзакций в кластере (до удаления) Как мы видим выше, в процессе выполнения программы, может возникнуть случай, когда количество транзакций в кластере становится равным 0 или 1 (случаи, когда так происходит будут описаны ниже). В таких случаях необходимо удалить данные строки из таблицы, и провести перенумерацию оставшихся кластеров (Рисунок 24).
Рис. 24 Таблица учета количества транзакций в кластере (после удаления) Смысл существования данной таблицы состоит в следующем. Т.к пользователь имеет возможность вводить «минимальную поддержку», то необходимо рассчитывать ее для каждого кластера. Минимальная поддержка необходима для разделения элементов кластера на большие и малые предметы и рассчитывается она исходя из количества транзакций в кластере. Именно произведение минимальной поддержки и количества транзакций в кластере и является делителем бинарного дерева на левую и правую ветвь. Рассмотрим механизм построения бинарного дерева для новообразованного кластера. Бинарное дерево строится на основе таблицы учета предметов и делителя бинарного дерева, расчет которого описан выше. Таблица учета предметов в кластере состоит из двух столбцов. В левом находится имя предмета, а в правом число раз, сколько данный предмет содержится в данном кластере. Листьями в бинарном дереве являются списки элементов транзакций, для которых количество нахождения раз в кластере равно. Например, имеем кластер, состоящий из двух транзакций ([a, b, c, d, e] , [c, d, e, f]). Также имеем минимальную поддержку 70%, введенную пользователем. Предмет считается большим, если существует в 2х транзакциях (0,7*2 = 1,4 округляем в большую сторону). Таблица учета предметов будет выглядеть таким образом:
|
Похожие:
 | Во время выполнения дипломной работы студент развивает навыки ведения самостоятельной научно-исследовательской работы, овладевает... |  | Прошу разрешить мне изменить тему дипломной (курсовой) работы с «Развитие познавательного интереса младших школьников во внеклассной... |
| О выпускной квалификационной (дипломной) работе дипломированного специалиста, обучающегося на факультете физической культуры ниу... | | Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования |
| Правила оформления дипломной работы (подготовлены на основе Положения о выпускной квалификационной работе). 15 | | Выполнение дипломной работы является заключительным этапом обучения студентов. Дипломная работа представляет собой самостоятельную... |
| Исторические этапы становления туроператорской деятельности в России и зарубежных странах | | В дипломной работе будет рассмотрена тема «Документационное обеспечение деятельности государственного учреждения (на примере гу со... |
| Настоящее положение разработано в соответствии с положением об итоговой государственной аттестации выпускников гбоу впо вгма им.... | | Особое внимание уделено выбору темы и организации выполнения дипломной работы, ее плану и структуре; подготовке дипломной работы... |