Лабораторная работа 1 По дисциплине: Технологии больших данных Тема: Ассоциативные правила Хилалов С. А. Группа: ип-19-6р Приняла: Тарасова Р. Н. Шымкент 2022 г

Алгоритм Apriori

1. 
   F_1 = \{F1​={ Часто встречающиеся 1-элементные наборы\};};
   
2. 
   \text{ для } (k=2, F_{k-1} \verb!<>! \varnothing, k\verb!++! ) для (k=2,Fk−1​<>∅,k++)
   
3. 
   \{{
   
4. 
   C_k = \{Ck​={ Генерация кандидатов \ k k на основе \ Apriorigen ( F_{k-1} ) \} Apriorigen(Fk−1​)}
   
5. 
   для всех транзакций t∈Dt∈D
   
6. 
   \{{
   
7. 
   C_t = subset(C_k,t)Ct​=subset(Ck​,t) // Удаление избыточных правил
   
8. 
   для всех кандидатов c \in C_tc∈Ct​
   
9. 
   c.count\verb!++!c.count++
   
10. 
    \}}
    
11. 
    F_k = [c \in C_k | c.count > = minsupp ]Fk​=[c∈Ck​∣c.count>=minsupp] // Отбор кандидатов
    
12. 
    \}}
    
13. 
    Результат \cup F_k∪Fk​
    

p.itemk−1​<q.itemk−1​
Удаление избыточных правил. На основании свойства анти-монотонности, следует удалить все наборы c C_kCk​, если хотя бы одно из его (k-1)(k−1) подмножеств не является часто встречающимся.
После генерации кандидатов следующей задачей является подсчет поддержки для каждого кандидата. Очевидно, что количество кандидатов может быть очень большим и нужен эффективный способ подсчета. Самый тривиальный способ – сравнить каждую транзакцию с каждым кандидатом. Но это далеко не лучшее решение.
Гораздо быстрее и эффективнее использовать подход, основанный на хранении кандидатов в хэш-дереве. Внутренние узлы дерева содержат хэш-таблицы с указателями на потомков, а листья – на кандидатов. Это дерево нам пригодится для быстрого подсчета поддержки для кандидатов.
Хэш-дерево строится каждый раз, когда формируются кандидаты. Первоначально дерево состоит только из корня, который является листом, и не содержит никаких кандидатов-наборов. Каждый раз когда формируется новый кандидат, он заносится в корень дерева, и так до тех пор, пока количество кандидатов в корне-листе не превысит некоего порога.
Как только количество кандидатов становится больше порога, корень преобразуется в хэш-таблицу, т.е. становится внутренним узлом, и для него создаются потомки-листья. И все примеры распределяются по узлам-потомкам согласно хэш-значениям элементов, входящих в набор, и т.д. Каждый новый кандидат хэшируется на внутренних узлах, пока он не достигнет первого узла-листа, где он и будет храниться, пока количество наборов опять же не превысит порога.
Хэш-дерево с кандидатами-наборами построено, теперь, используя хэш-дерево, легко подсчитать поддержку для каждого кандидата. Для этого нужно «пропустить» каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, т.е. C_k∩Ti=C_kCk​∩Ti=Ck​. На корневом уровне хэш-функция применяется к каждому элементу из транзакции.
Далее, на втором уровне, хэш-функция применяется ко вторым элементам и т.д. На kk-уровне хэшируется kk-элемент. И так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, тогда увеличиваем счетчик поддержки этого кандидата на единицу.
После того, как каждая транзакция из исходного набора данных «пропущена» через дерево, можно проверить удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, она нам пригодится при извлечении правил. Эти же действия применяются для нахождения (k+1)(k+1) -элементных наборов и т.д.
После того как найдены все часто встречающиеся наборы элементов, можно приступить непосредственно к генерации правил.
Извлечение правил – менее трудоемкая задача. Во-первых, для подсчета достоверности правила достаточно знать поддержку самого набора и множества, лежащего в условии правила. Например, имеется часто встречающийся набор \{ A, B, C \}{A,B,C} и требуется подсчитать достоверность для правила AB⇒CAB⇒C. Поддержка самого набора нам известна, но и его множество \{ A, B \}{A,B}, лежащее в условии правила, также является часто встречающимся в силу свойства анти-монотонности, и значит его поддержка нам известна. Тогда мы легко сможем подсчитать достоверность. Это избавляет нас от нежелательного просмотра базы транзакций, который потребовался в том случае если бы это поддержка была неизвестна.
Чтобы извлечь правило из часто встречающегося набора FF, следует найти все его непустые подмножества. И для каждого подмножества ss мы сможем сформулировать правило s ⇒ (F - s)s⇒(F−s), если достоверность правила conf(s ⇒ (F - s)) = supp(F)/supp(s)conf(s⇒(F−s))=supp(F)/supp(s) не меньше порога minconfminconf.
Заметим, что числитель остается постоянным. Тогда достоверность имеет минимальное значение, если знаменатель имеет максимальное значение, а это происходит в том случае, когда в условии правила имеется набор, состоящий из одного элемента. Все супермножества данного множества имеют меньшую или равную поддержку и, соответственно, большее значение достоверности. Это свойство может быть использовано при извлечении правил.
Если мы начнем извлекать правила, рассматривая сначала только один элемент в условии правила, и это правило имеет необходимую поддержку, тогда все правила, где в условии стоят супермножества этого элемента, также имеют значение достоверности выше заданного порога. Например, если правило A ⇒ BCDEA⇒BCDE удовлетворяет минимальному порогу достоверности minconfminconf, тогда AB ⇒ CDEAB⇒CDE также удовлетворяет.
Для того чтобы извлечь все правила используется рекурсивная процедура. Важное замечание: любое правило, составленное из часто встречающегося набора, должно содержать все элементы набора. Например, если набор состоит из элементов \{ A, B, C \}{A,B,C}, то правило A⇒BA⇒B не должно рассматриваться.

жүктеу/скачать 37.74 Kb.

Достарыңызбен бөлісу: