Алгоритм Apriori

Apriori^[1] — алгоритм глибинного аналізу даних щодо частих одиниць у множинах і машинного навчання щодо асоціативних правил, що застосовується переважно до баз даних транзакцій. Алгоритм ідентифікує елементи/одиниці, що часто повторюються у базі, і розширює їх список до все більших множин з дотриманням правила достатньої частотності. Визначені алгоритмом множини частих одиниць можна використати для визначення правил асоціювання, по яких стають помітними загальні тенденції в базі даних.

Це знаходить застосування в таких областях, як аналіз ринкового кошика^[en]. Одиницями при цьому є пропоновані товари, а покупка являє собою транзакцію, яка містить куплені предмети (одиниці). Алгоритм при цьому визначає кореляції такого виду:

Якщо хтось купує шампунь і лосьйон для гоління, у 90 % випадків купується також і піна для гоління.

Дані, що надаються до аналізу, складаються з таблиці транзакцій (на рядках), в якій перераховуються будь-які бінарні одиниці (у колонках). Алгоритм Apriori знаходить співвідношення між множинами одиниць, які зустрічаються у великій частині транзакцій. Правила асоціювання, які отримуються в результаті, мають форму ${\displaystyle A\rightarrow B}$; при цьому ${\displaystyle A}$ і ${\displaystyle B}$ є множинами одиниць, а правило стверджує, що коли у великій частині транзакцій зустрічається множина одиниць ${\displaystyle A}$, то там часто зустрічається і множина одиниць ${\displaystyle B}$.

Опис алгоритму

Алгоритм 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}}}$

Приклади

Приклад 1

Розглянемо таку базу даних, де кожен рядок являє собою транзакцію, а кожна клітина — окремий елемент транзакції:

alpha	beta	epsilon
alpha	beta	theta	a
alpha	beta	epsilon	a
alpha	beta	theta	b

З цієї бази можна визначити такі асоціативні правила:

1. 100 % множин, що містять alpha, також містять beta.
2. 50 % множин, що містять alpha, beta, також містять epsilon.
3. 50 % множин, що містять alpha, beta, також мають theta.

ми можемо проілюструвати це за допомогою різних прикладів.

Приклад 2

Припустимо, що великий супермаркет відстежує дані про продажі у блоці складського обліку (SKU) для кожного елемента: кожний елемент, наприклад, «масло» або «хліб», визначається числовим значення в SKU. Супермаркет має базу даних транзакцій, де кожна транзакція це набір артикулів, які були куплені разом.

Нехай база даних угод складається з наступних наборів:

Набір

{1,2,3,4}

{1,2,4}

{1,2}

{2,3,4}

{2,3}

{3,4}

{2,4}

Ми будемо використовувати Apriori, щоб визначити часті набори товарів цієї бази даних. Для цього будемо говорити, що набір товарів частий, якщо він з'являється, принаймні, у 3 транзакціях бази даних: значення 3 є пороговим значенням (англ. support threshold).

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

Набір	Затребуваність
{1}	3
{2}	6
{3}	4
{4}	5

Всі набори елементів розміром 1 мають затребуваність, принаймні, 3, тому вони більш часті.

Наступним кроком є створення списку всіх пар частих елементів.

Наприклад, щодо пари {1,2}: перша таблиця з прикладу 2 показує, що пункти 1 і 2 з'являються разом в трьох наборах. Тому ми говоримо, що пункт {1,2} має затребуваність три.

Набір	Затребуваність
{1,2}	3
{1,3}	1
{1,4}	2
{2,3}	3
{2,4}	4
{3,4}	3

Пари {1,2}, {2,3}, {2,4} і {3,4} всі відповідають або перевищують мінімальну затребуваність 3, так що вони часті. Пари {1,3} і {1,4} не є частими. Тепер, тому що {1,3} і {1,4} не часті, будь-який більший набір, який містить {1,3} або {1,4} не може бути частим. Таким чином, ми можемо скоротити набори: тепер ми будемо шукати часті трійки в базі даних, але ми вже можемо виключити всі трійки, які містять одну з цих двох пар:

Набір	Затребуваність
{2,3,4}	2

в даному прикладі, немає частих трійок — {2,3,4} нижче мінімального порогу, і інші трійки були виключені, тому що вони були наборами пар, які вже були нижче затребуваності.

Таким чином, ми визначили часті набори елементів в базі даних, а також показали, як деякі елементи не були підраховані, тому що про одну з їх підмножин вже було відомо, що вона нижче порогового значення.

Обмеження

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

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

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

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

Посилання

1. Rakesh Agrawal and Ramakrishnan Srikant Fast algorithms for mining association rules in large databases [Архівовано 25 лютого 2015 у Wayback Machine.]. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487—499, Santiago, Chile, September 1994.
2. Bayardo Jr, Roberto J. (1998). Efficiently mining long patterns from databases (PDF). ACM SIGMOD Record. 27 (2). Архів оригіналу (PDF) за 23 березня 2016. Процитовано 27 травня 2017.