CCC / LB1
.docМетодичні вказівки до виконання роботи.
Алгоритм Apriory.
Даний алгоритм був запропонований у 1994 році американськими вченими індійського походження Агравалом та Шрікантом. У його основі лежить поняття “частий набір” (frequent itemset). Асоціативні правила будуються не для усіх можливих сполучень товарів, а лише для тих, які зустрічаються в початковій базі даних достатньо часто.
Частим набором називається непуста множина товарів, підтримка якої не менша за певний, заданий наперед рівень, що має назву “мінімальна підтримка”. Алгоритм Apriory складається з двох послідовних процедур:
-
знаходження усіх частих наборів;
-
відсіювання з числа усіх можливих правил, що можуть бути задані на частих наборах, таких, що не задовольняють встановленим вимогам підтримки та достовірності.
В алгоритмі використовується правило анти монотонності: “Якщо певний набір не є частим, то додавання до нього одного або декількох предметів не зробить його частим”.
Таким чином, на першому етапі підраховуються кількості входжень в базу даних усіх предметів окремо. Якщо певні предмети зустрічаються рідше, ніж заданий рівень підтримки, вони в подальшому розгляді участі не беруть.
На
другому й наступних
тих
етапах множина кандидатів
формується як лінійна комбінація з
частих наборів
множини.
Формування
частих наборів продовжується до тих
пір, поки існує хоча б один частий набір
потужності
.
В залежності від складності предметної
області та вигляду типових транзакцій
(довжини чеку)
може сягати значень більше 10.
Після того, як
часті набори усіх без винятку рівнів
ідентифіковані й виписані, починається
генерація правил. До кожного частого
набору
рівнів від 2 до
знаходять всі можливі комбінації
.
Якщо при цьому
- не порожня підмножина вихідного
часткового набору, то правило
включається в якості кандидата до
перспективного переліку правил. У
кожного
правила перевіряється достовірність
та підтримка. Всі правила, що задовольняють
вимогам, заносяться до бази правил.
Докладніше роботу алгоритму проілюструє наступний приклад з овочевим магазином.
Множина транзакцій представлена у таблиці 1.1. використовуючи мінімальний рівень підтримки 25% та мінімальну достовірність 80%, створити базу асоціативних правил поведінки покупців.
Таблиця 1.1. Транзакції в овочевому магазині.
|
№ транзакції |
Предметні набори |
|
1 |
Капуста, перець, кукурудза |
|
2 |
Спаржа, кабачки, кукурудза |
|
3 |
Кукурудза, Помідори, квасоля, кабачки |
|
4 |
Перець, кукурудза, Помідори, квасоля |
|
5 |
Квасоля, спаржа, капуста |
|
6 |
Кабачки, спаржа, квасоля, Помідори |
|
7 |
Помідори, кукурудза |
|
8 |
Капуста, Помідори, перець |
|
9 |
Кабачки, спаржа, квасоля |
|
10 |
Квасоля, кукурудза |
|
11 |
Перець, капуста, квасоля, кабачки |
|
12 |
Спаржа, квасоля, кабачки |
|
13 |
Кабачки, кукурудза, спаржа, квасоля |
|
14 |
Кукурудза, перець, помідори, квасоля, капуста |
Користуючись
вищенаведеним алгоритмом, насамперед
перевіряємо, чи всі продукти відповідають
умовам “частих наборів”, тобто
перевіряємо підтримку наборів першого
рівня. Заданий рівень підтримки 25%
свідчить, що продукт має зустрічатися
в транзакціях не менше 5 разів
.
Для перевірки представимо транзакції у бінарній формі й підрахуємо кількість покупок кожного продукту (див. табл. 1.2).
Таблиця 1.2. Нормалізований вид множини транзакцій
|
№ транзак ции |
Яблоки |
Бананы |
Морковь |
Помидоры |
Салат |
Конфеты |
Персик |
Картофель |
Слива |
Лук |
|
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
2 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
3 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
4 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
5 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
|
6 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
7 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
8 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|
9 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|
|
10 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
11 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
|
12 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
|
|
13 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
14 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
|
15 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
16 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
17 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
18 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
19 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
20 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
Сумма |
14 |
3 |
5 |
7 |
8 |
15 |
7 |
13 |
2 |
12 |
|
Як видно з таблиці 1.2, всі набори першого рівня, крім бананів та слив, (окремі товари) є частими. Переходимо до другого рівня, генеруючи всі можливі пари товарів. Самі набори другого рівня та їх підтримка наведені у
таблиці 1.3.
|
Набір |
Кількість |
Набір |
Кількість |
Набір |
Кількість |
|||
|
Яблоки, морковь |
4 |
Персики, лук |
5 |
Салат, конфеты |
4 |
|||
|
Яблоки, помидоры |
5 |
Яблоки, лук |
8 |
Помидоры, лук |
4 |
|||
|
Яблоки, салат |
5 |
Морковь, картофель |
4 |
Салат, картофель |
4 |
|||
|
Яблоки, конфеты |
11 |
Картофель, лук |
6 |
Салат, лук |
5 |
|||
|
Яблоки, персики |
4 |
Помидоры, конфеты |
7 |
Конфеты, персики |
5 |
|||
|
Яблоки, картофель |
9 |
Помидоры, картофель |
4 |
Конфеты, картофель |
10 |
|||
|
Конфеты, лук |
8 |
Персики, картофель |
5 |
|
|
|||
Таблиця 1.3. Предметні набори з двох овочів
Всі інші набори овочів, які не представлені в таблиці, зустрічаються менше 4 разів.
Як видно з таблиці 1.3, за прийнятими критеріями підтримки частими є лише сім наборів з двох овочів:
{яблоки,
помидоры}; {яблоки, салат}; {яблоки,
конфеты}; {яблоки, картофель}; {яблоки,
лук}; {конфеты, лук}; {персики, лук};
{картофель, лук}; {помидоры, конфеты};
{персики, картофель}; {салат, лук}; {конфеты,
персики}; {конфеты, картофель}.
Далі
використовуємо отримані набори з двох
овочів для генерації множин з трьох
предметів
.
Для цього знаходимо всі об’єднання
множин рівня
,
що мають спільний перший елемент.
З огляду на отримані дані, множини третього порядку, які задовольняють поставленій умові представлені в таблиці 1.4.
Таблиця 1.4. Предметні набори з трьох овочів
|
Набір |
Кількість |
|
Яблоки, помидоры, конфеты |
5 |
|
Яблоки, конфеты, лук |
6 |
|
Яблоки, конфеты, картофель |
8 |
Подальше виділення чистих наборів сенсу не має. Таким чином, в розглянутій задачі виділено 20 однопредметних частих наборів, 13 – двох предметних та 3 – трьох предметних. Маючи їх всі, переходимо до генерації асоціативних правил.
Процедура генерації правил виконується послідовно для частих наборів усіх рівнів, починаючи з вищого і передбачає:
-
виділення в наборі
можливого часткового набору
; -
якщо
,
то записується асоціація вигляду
,
де
,
або точніше
; -
всі отримані правила оцінюються за підтримкою та достовірністю. Такі, що не задовольняють обраним критеріям, відкидаються.
-
Відповідно може бути записано шість варіантів правил:
Якщо {яблука}, то {помідори, цукерки};
Якщо {помідори}, то {яблука, цукерки};
Якщо {цукерки}, то {яблука, помідори};
Якщо {яблука, помідори}, то {цукерки};
Якщо {яблука, цукерки}, то {помідори};
Якщо {помідори, цукерки}, то {яблука}.
Якщо {яблука}, то {цукерки, цибуля};
Якщо {цукерки}, то {яблука, цибуля};
Якщо {цибуля}, то {яблука, цукерки};
Якщо {яблука, цукерки}, то {цибуля};
Якщо {яблука, цибуля}, то {цукерки};
Якщо {цукерки, цибуля}, то {яблука}.
Якщо {яблука}, то {цукерки, картопля};
Якщо {цукерки}, то {яблука, картопля};
Якщо {картопля}, то {яблука, цукерки};
Якщо {яблука, цукерки}, то {картопля};
Якщо {яблука, картопля}, то {цукерки};
Якщо {цукерки, картопля}, то {яблука}.
Підтримка – це відсоток рядків початкової бази даних, де одночасно зустрічаються як умова, так і наслідок.
Достовірність цього правила вимірюється як відношення частоти зустрічі усього набору до частоти умови.
Таблиця 1.5. Асоціативні правила із двома предметами в умові
|
Якщо умова, то наслідок |
Підтримка |
Достовірність |
|
Якщо {яблука}, то {помідори, цукерки} |
5/20=25% |
5/14=36% |
|
Якщо {помідори}, то {яблука, цукерки} |
5/20=25% |
5/7=71% |
|
Якщо {цукерки}, то {яблука, помідори} |
5/20=25% |
5/15=33% |
|
Якщо {яблука, помідори}, то {цукерки} |
5/20=25% |
5/5=100% |
|
Якщо {яблука, цукерки}, то {помідори} |
5/20=25% |
5/11=45% |
|
Якщо {помідори, цукерки}, то {яблука} |
5/20=25% |
5/7=71% |
|
Якщо {яблука}, то {цукерки, цибуля} |
6/20=30% |
6/14=43% |
|
Якщо {цукерки}, то {яблука, цибуля} |
6/20=30% |
6/15=40% |
|
Якщо {цибуля}, то {яблука, цукерки} |
6/20=30% |
6/12=50% |
|
Якщо {яблука, цукерки}, то {цибуля} |
6/20=30% |
6/11=55% |
|
Якщо {яблука, цибуля}, то {цукерки} |
6/20=30% |
6/8=75% |
|
Якщо {цукерки, цибуля}, то {яблука} |
6/20=30% |
6/8=75% |
|
Якщо {яблука}, то {цукерки, картопля} |
8/20=40% |
8/14=57% |
|
Якщо {цукерки}, то {яблука, картопля} |
8/20=40% |
8/15=53% |
|
Якщо {картопля}, то {яблука, цукерки} |
8/20=40% |
8/13=62% |
|
Якщо {яблука, цукерки}, то {картопля} |
8/20=40% |
8/11=73% |
|
Якщо {яблука, картопля}, то {цукерки} |
8/20=40% |
8/9=0,89% |
|
Якщо {цукерки, картопля}, то {яблука} |
8/20=40% |
8/10=80% |
Таблиця 1.6. Асоціативні правила з одним предметом в умові
|
Якщо умова, то наслідок |
Підтримка |
Достовірність |
|
||||||
|
Якщо {яблука}, то {морква} |
4/20=20% |
4/14=29% |
|
||||||
|
Якщо {морква}, то {яблука} |
4/20=20% |
4/5=80% |
|
||||||
|
Якщо {яблука}, то {помідори} |
5/20 =25% |
5/14=36% |
|
||||||
|
Якщо {помідори}, то {яблука} |
5/20=25% |
5/7=71% |
|
||||||
|
Якщо {яблука}, то {салат} |
5/20=25% |
5/14=36% |
|
||||||
|
Якщо {салат}, то {яблука} |
5/20=25% |
5/8=63% |
|
||||||
|
Якщо {яблука}, то {цукерки} |
11/20=55% |
11/14=79% |
|
||||||
|
Якщо {цукерки}, то {яблука} |
11/20=55% |
11/15=73% |
|
||||||
|
Якщо {яблука}, то {персик} |
4/20=20% |
4/14=29% |
|
||||||
|
Якщо {персик}, то {яблука} |
4/20=20% |
4/7=57% |
|
||||||
|
Якщо {яблука}, то {картопля} |
9/20=45% |
9/14=64% |
|
||||||
|
Якщо {картопля}, то {яблука) |
9/20=45% |
9/13=69% |
|
||||||
|
Якщо {яблука}, то {цибуля} |
8/20=40% |
8/14=57% |
|
||||||
|
Якщо {цибуля}, то {яблука} |
8/20=40% |
8/12=67% |
|
||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||
|
|
|
|
|||||||