Технологии интеллектуального анализа данных : учебное пособие

148 стья – на кандидатов. Это дерево используется при быстром под- счете поддержки для кандидатов. Хэш-дерево строится каждый раз, когда формируются кан- дидаты. Первоначально дерево состоит только из корня, который является листом, и не содержит никаких кандидатов-наборов. Каж- дый раз, когда формируется новый кандидат, он заносится в корень дерева, и так до тех пор, пока количество кандидатов в корне-листе не превысит некоего порога. Как только это происходит, корень преобразуется в хэш-таблицу, т.е. становится внутренним узлом, и для него создаются потомки-листья. Все кандидаты распределяют- ся по узлам-потомкам согласно хэш-значениям элементов, входя- щих в набор. Каждый новый кандидат хэшируется на внутренних узлах, пока не достигнет первого узла-листа, где он и будет хра- ниться, пока количество наборов не превысит порога. После того как хэш-дерево с кандидатами-наборами по- строено, легко подсчитать поддержку для каждого кандидата. Для этого нужно «пропустить» каждую транзакцию через дерево и уве- личить счетчики для тех кандидатов, чьи элементы также содер- жатся и в транзакции: С k  Т i = С k . На корневом уровне хэш- функция применяется к каждому объекту из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым объектам и т.д. На k -м уровне хэшируется k -элемент и так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, увеличиваем счет- чик поддержки этого кандидата на единицу. После того как каждая транзакция из исходного набора дан- ных «пропущена» через дерево, можно проверить, удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора,