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

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

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

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

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

    (1)Увеличить размер кластера на 1 (2)Произвести обновление поддержки предметов в заданном кластере (3)Для каждого предмета в транзакции

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

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

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

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

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

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

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

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

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

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

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




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

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