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

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

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

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

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

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

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

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

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

    - Номер транзакции, а также предметы в данной транзакции - Номер кластера, к которому принадлежит данная транзакции - "Большие предметы" принадлежащие данному кластеру
приложение largeitem

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

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

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

Для начала проверим правильность расчета штрафа(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.

Видно, что объединение дает выгоду.

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

Теперь рассмотрим принцип работы алгоритма на тестовом примере.

Основными этапами работы алгоритма является:

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

Разберем эти этапы более подробно.

Первичный проход по базе транзакций и их объединение в кластеры

Предположим, что на начальном этапе имеется гипотетическая база, состоящая из девяти транзакций. Обозначим их цифрами от 1 до 9.

транзакции 1-9

Рис. 21 Транзакции 1-9

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

транзакции 2, 4-9 и новообразованный кластер (1,3)

Рис. 22 Транзакции 2, 4-9 и новообразованный кластер (1,3)

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

Номер кластера

Количество транзакций

1

3

2

4

3

1

4

0

5

2

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

Номер кластера

Количество транзакций

1

3

2

4

3

2

Смысл существования данной таблицы состоит в следующем. Т. к пользователь имеет возможность вводить "минимальную поддержку", то необходимо рассчитывать ее для каждого кластера. Минимальная поддержка необходима для разделения элементов кластера на большие и малые предметы и рассчитывается она исходя из количества транзакций в кластере. Именно произведение минимальной поддержки и количества транзакций в кластере и является делителем бинарного дерева на левую и правую ветвь.

Рассмотрим механизм построения бинарного дерева для новообразованного кластера.

Бинарное дерево строится на основе таблицы учета предметов и делителя бинарного дерева, расчет которого описан выше.

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

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

Например, имеем кластер, состоящий из двух транзакций ([a, b, c, d, e] , [c, d, e, f]). Также имеем минимальную поддержку 70%, введенную пользователем.

Предмет считается большим, если существует в 2х транзакциях (0,7*2 = 1,4 округляем в большую сторону).

Таблица учета предметов будет выглядеть таким образом:

A

1

B

1

C

2

D

2

E

2

F

1

На основе данной таблицы строится бинарное дерево (Рисунок 25).

Рис. 25

Расчет штрафа за неправильную кластеризацию происходит на основе данных таблицы и дерева. Так, для данного кластера штраф будет равен 3.

При прохождении первичной кластеризации может возникнуть случай, когда одна транзакция имеет общие предметы с несколькими другими. Например, транзакция 1 будет иметь общие предметы как с транзакцией 3, так и с транзакцией 7. В таком случае происходит построение двух предварительных кластеров и сравнение их штрафов за неправильную кластеризацию. Соответственно, более удачным кластером будет являться тот кластер, у которого данный штраф будет ниже. Тогда, худший кластер удаляется, т. е удаляется дерево для этого кластера, таблица предмета учета предметов для данного кластера, а также запись о нем в таблице учета количества транзакций в кластере. В случае, если транзакция не имеет общих предметов ни с одной из существующих транзакций, то из нее образуется кластер, содержащий только эту транзакцию. Что произойдет с этими кластерами будет описано позднее.

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

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

кластеры до вторичной кластеризации

Рис. 26 Кластеры до вторичной кластеризации

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

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

Рассмотрим пример образования нового кластера на основе двух уже существующих.

Например, попытаемся объединить ранее рассмотренный кластер ([a, b, c, d, e] , [c, d, e, f]), состоящий из двух транзакций и новый кластер ([c, d, l, z], [y, l, z]), также состоящий из двух транзакций. Для нового кластера таблица учета предметов будет иметь следующий вид:

A

1

B

1

C

3

D

3

E

2

F

1

L

2

Y

1

Z

1

Также, в связи с добавлением новых элементов, будет перестроено бинарное дерево (Рисунок 27).

Рис. 27

В данном случае частота встречаемости больших предметов будет не менее 3х (0,7*4 = 2,8 округляем в большую сторону). Рассчитаем штраф для новообразованного кластера, а также для двух кластеров отдельно.

В новом кластере количество "больших предметов" 2, остальные 7 являются "малыми". Следовательно, по формуле, штраф в данном случае будет равен 7.

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

Кластер ([a, b, c, d, e] , [c, d, e, f]) имеет 3 "больших" и 3 "малых" предмета, кластер ([c, d, l, z], [y, l, z]) - 2 "больших" и 3 "малых". Исходя из этих значений, получаем штраф равный 11, что еще раз доказывает, что даже один общий предмет стимулирует объединение в общий кластер.

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

Настройка Java

Для программ, написанных на языке Java, по умолчанию выделяется 128Mb оперативной памяти. Для обработки некоторых наборов данных этого количества памяти недостаточно. Что бы увеличить количество выделяемой памяти при запуске из командной строки Windows надо добавить параметр - Xmx256m, где 256 - это количество выделяемой памяти. Так же можно поставить 512 и 1024 в зависимости от размера набора данных.

Похожие статьи




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

Предыдущая | Следующая