Алгоритм Априори
Это подход "генерация и тестирование кандидатов" для частого анализа шаблонов в наборах данных. Вам нужно запомнить две вещи.
Принцип априорной обрезки - Если какой-либо набор элементов встречается нечасто, его набор не должен создаваться / тестироваться.
Свойство Apriori - Данное (k+1)-itemset является кандидатом (k+1)-itemset, только если все его подмножества k-itemset являются частыми.
Теперь приведем алгоритм априори в 4 этапа.
- Первоначально, сканируйте базу данных / набор данных один раз, чтобы получить частые
1-itemset.
- Генерирование длина
k+1 кандидат наборов из длины k частые наборы элементов.
- Проверка кандидатов в базе данных / наборе данных.
- Завершается, когда не может быть сгенерировано ни одного частого или возможного набора.
Решенный пример
Предположим, существует следующая база данных транзакций с 4 транзакциями, включая их идентификаторы транзакций и предметы, купленные с ними. Предположим, что минимальная поддержка - min_sup - 2. Термин «поддержка» - это количество транзакций, в которых присутствует / включен определенный набор элементов.
Транзакция DB
tid | items
-------------
10 | A,C,D
20 | B,C,E
30 | A,B,C,E
40 | B,E
Теперь давайте создадим кандидата 1-itemsets при первом сканировании БД. Он просто называется набором C_1 следующим образом.
itemset | sup
-------------
{A} | 2
{B} | 3
{C} | 3
{D} | 1
{E} | 3
Если мы проверим это с min_sup, мы увидим, что {D} не удовлетворяет min_sup из 2. Таким образом, он не будет включен в частый 1-itemset, который мы просто называем набором L_1 следующим образом.
itemset | sup
-------------
{A} | 2
{B} | 3
{C} | 3
{E} | 3
Теперь давайте просканируем БД во второй раз и сгенерируем кандидата 2-itemsets, который мы просто называем набором C_2 следующим образом.
itemset | sup
-------------
{A,B} | 1
{A,C} | 2
{A,E} | 1
{B,C} | 2
{B,E} | 3
{C,E} | 2
Как видите, наборы {A,B} и {A,E} не удовлетворяют min_sup из 2 и, следовательно, они не будут включены в частые 2-itemset, L_2
itemset | sup
-------------
{A,C} | 2
{B,C} | 2
{B,E} | 3
{C,E} | 2
Теперь давайте сделаем 3-е сканирование БД и получим кандидата 3-itemsets, C_3 следующим образом.
itemset | sup
-------------
{A,B,C} | 1
{A,B,E} | 1
{A,C,E} | 1
{B,C,E} | 2
Вы можете видеть, что {A,B,C}, {A,B,E} и {A,C,E} не удовлетворяют min_sup из 2. Поэтому они не будут включены в частые 3-itemset, L_3 следующим образом.
itemset | sup
-------------
{B,C,E} | 2
Теперь, наконец, мы можем вычислить значения support (supp), confidence (conf) и lift (interestingness value) Правил ассоциации / корреляции , которые могут быть сгенерированы набором элементов {B,C,E}, следующим образом.
Rule | supp | conf | lift
-------------------------------------------
B -> C & E | 50% | 66.67% | 1.33
E -> B & C | 50% | 66.67% | 1.33
C -> E & B | 50% | 66.67% | 1.77
B & C -> E | 50% | 100% | 1.33
E & B -> C | 50% | 66.67% | 1.77
C & E -> B | 50% | 100% | 1.33