Алгоритм Apriori

Алгоритм Apriori було запропоновано Агравалом і Срікантом в 1994 році. Apriori застосовується до баз даних транзакцій (наприклад, наборів товарів, куплених клієнтами, або відвідуваності вебсайту). Інші алгоритми розроблені для пошуку асоціативних правил у даних, які не містять транзакцій або не мають відміток часу (наприклад, ДНК-послідовність). Кожна транзакція розглядається як множина елементів. Маючи заданий поріг ${\displaystyle C}$, алгоритм Apriori ідентифікує множину елементів, які є підмножинами принаймні ${\displaystyle C}$ транзакцій в базі даних.

Апріорі використовує підхід «знизу вгору», за якого список частих підмножин розширюється по одному елементу за раз (крок, відомий як генерування кандидатів); відтак групи кандидатів перевіряються на основі наявних даних. Алгоритм завершує роботу, коли подальших успішних розширень знайти неможливо.

Apriori використовує пошук у ширину та структуру геш-дерева для ефективного підрахунку елементів-кандидатів множини. Він генерує множини елементів-кандидатів довжиною ${\displaystyle k}$ з множин довжиною ${\displaystyle k-1}$. Потім він відсікає кандидатів, які є нечастими підмножинами. Відповідно до леми низхідного змикання (англ. downward closure lemma), множина кандидатів містить усі множини елементів довжини ${\displaystyle k}$, які часто зустрічаються. Після цього він сканує базу даних транзакцій, щоб визначити множини елементів, які часто зустрічаються серед кандидатів.

Псевдокод для алгоритму наведено нижче для бази даних транзакцій ${\displaystyle T}$ і допоміжного порога ${\displaystyle \epsilon }$. Застосовується звичайна нотація теорії множин, хоча слід відзначити, що ${\displaystyle T}$ є мультимножиною. ${\displaystyle C_{k}}$ — це множина кандидатів для рівня ${\displaystyle k}$. З кожним кроком, як припускається, алгоритм генерує набори кандидатів з великих множин попереднього рівня, дотримуючись леми низхідного закриття. ${\displaystyle count[c]}$ звертається до поля структури даних, яка являє собою множину кандидатів ${\displaystyle c}$, спочатку вона приймається рівною нулю. Нижче випущено багато деталей, але зазвичай найважливішою частиною реалізації є структура даних, що використовується для зберігання множин кандидатів і підрахунку їх частоти.

${\displaystyle {\begin{aligned}&\mathrm {Apriori} (T,\epsilon )\\&\qquad L_{1}\gets \{\mathrm {large~1-itemsets} \}\\&\qquad k\gets 2\\&\qquad \mathrm {\textbf {while}} ~L_{k-1}\neq \ \emptyset \\&\qquad \qquad C_{k}\gets \{a\cup \{b\}\mid a\in L_{k-1}\land b\not \in a\}-\{c\mid \{s\mid s\subseteq c\land |s|=k-1\}\nsubseteq L_{k-1}\}\\&\qquad \qquad \mathrm {{\textbf {for}}~transactions} ~t\in T\\&\qquad \qquad \qquad C_{t}\gets \{c\mid c\in C_{k}\land c\subseteq t\}\\&\qquad \qquad \qquad \mathrm {{\textbf {for}}~candidates} ~c\in C_{t}\\&\qquad \qquad \qquad \qquad {\mathit {count}}[c]\gets {\mathit {count}}[c]+1\\&\qquad \qquad L_{k}\gets \{c\mid c\in C_{k}\land ~{\mathit {count}}[c]\geq \epsilon \}\\&\qquad \qquad k\gets k+1\\&\qquad \mathrm {\textbf {return}} ~\bigcup _{k}L_{k}\end{aligned}}}$

Алгоритм Apriori страждає від низкої ефективності та компромісів, що привело до виникнення інших алгоритмів. Утворення кандидата породжує велику кількість підмножин (алгоритм намагається завантажити в набір кандидатів якомога більше даних перед кожним скануванням). Пошук підмножин проходом від низу до верху (по суті обхід в ширину підмножини решітки) знаходить будь-яку максимальну підмножину S тільки після того, як будуть знайдено її ${\displaystyle 2^{|S|}-1}$ власних підмножин.

Алгоритм сканує базу даних дуже багато разів, що суттєво скорочує швидкодію. Тому, для того щоб алгоритм працював швидко, потрібно, щоб база постійно знаходилась у пам'яті.

Також часова та просторова складність алгоритму є дуже високими.

Пізніші алгоритми, такі як Max-Miner[2] намагаються визначити максимальні часті набори записів, не перераховуючи їх підмножини, і виконуючи «стрибки» в просторі пошуку, на відміну від чистого подходу з низу до верху.