🧺 Аналізатор кошика покупок — алгоритм Apriori наживо

Apriori — це класичний алгоритм (Агравал і Срікант, 1994) для видобування частих наборів товарів та асоціативних правил із даних транзакцій, таких як кошики покупок. Він будує часті набори товарів рівень за рівнем: спочатку підраховує окремі товари, потім пари, потім трійки і так далі, відкидаючи все, що нижче порогу мінімальної підтримки на кожному рівні, ще до того, як це буде використано для побудови більших кандидатів. Саме це порівневе відсіювання дозволяє алгоритму масштабуватися на великі каталоги товарів, ніколи не перебираючи явно кожну можливу комбінацію.

Підтримка(X) — це просто частка всіх транзакцій, що містять набір товарів X, тобто міра того, наскільки він поширений. Довіра(A→B) = підтримка(A∪B) / підтримка(A) — це умовна ймовірність того, що кошик містить B за умови, що він уже містить A. Lift(A→B) = довіра(A→B) / підтримка(B) порівнює цю умовну ймовірність із базовою частотою B: lift більший за 1 означає, що A робить B більш імовірним, ніж випадково, lift близький до 1 означає, що вони практично незалежні, а lift менший за 1 означає, що A насправді робить B менш імовірним.

Apriori спирається на властивість спадної замкненості: якщо набір товарів частий, кожна його підмножина також повинна бути частою, оскільки будь-яка транзакція, що містить повний набір, містить і кожну підмножину. Обернене твердження і є правилом відсіювання — якщо будь-яка (k−1)-підмножина кандидата-k-набору нечаста, то й сам кандидат не може бути частим, тож його відкидають ще до сканування жодної транзакції. Без цього відсіювання кількість кандидатів-наборів зростала б комбінаторно з розміром каталогу; з ним перевіряються лише комбінації, побудовані з уже частих частин.

Щойно знайдено частий набір товарів розміром два або більше, кожен спосіб розбити його на непорожній передумову A та залишковий наслідок B створює кандидатне правило A→B. Його підтримка — це просто підтримка самого набору товарів; його довіра та lift обчислюються з підтримок A і B, які вже були виміряні під час видобування. Далі правила фільтруються, щоб залишити лише ті, що відповідають порогу мінімальної довіри, оскільки частий набір товарів не гарантує, що якийсь конкретний його поділ є сильним прогностичним правилом.

Мінімальна підтримка контролює, наскільки далеко просувається порівневе зростання наборів товарів: підвищите її — і на кожному рівні виживають лише найсильніші, найпоширеніші комбінації, тож видобування зупиняється після одного-двох рівнів; знизите її — виживають рідкісніші комбінації, досліджуються глибші рівні, а час виконання та сама кількість кандидатів-наборів різко зростають. Мінімальна довіра застосовується згодом, суто як фільтр правил, виведених із уже знайдених наборів товарів — її підвищення відкидає слабкі чи випадкові розбиття A→B, залишаючи лише найбільш однобічні, прогностичні напрямки набору товарів.

Видобування справжнє. Симулятор генерує набір синтетичних транзакцій покупок зі справжньою структурою співпоявлення (певні товари навмисно зроблено ймовірнішими для появи разом), потім безпосередньо підраховує появи товарів і наборів товарів у цьому списку транзакцій, застосовує стандартну процедуру Apriori «об'єднання-потім-відсіювання» рівень за рівнем і обчислює довіру та lift із реально виміряних підтримок — нічого не заскриптовано і не підроблено. Переміщення повзунків повторно запускає весь алгоритм з нуля над тими самими транзакціями.