Алгоритм apriori, data science

Йдемо далі в циклі статей Топ-10 data mining алгоритмів і розглядаємо корисний і цікавий алгоритм Apriori (Апріорі).

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

Що таке асоціативні правила? Вивчення асоціативних правил - це техніка, що застосовується в data mining для вивчення співвідношень і відносин між змінними бази даних.

Як виглядає приклад використання алгоритму Apriori? Скажімо, у нас є база даних транзакцій супермаркету. Ви можете уявити собі базу даних як величезну таблицю, в якій кожен рядок - це номер транзакції, а кожен стовпчик представляє собою окремі покупки.

Застосовуючи алгоритм Apriori, ми можемо визначити товари, куплені разом - тобто встановити асоціативні правила.

Що це дає нам:

Ви можете визначити товари, які часто купують разом. Основне завдання маркетингу - змусити клієнтів купувати більше. Пов'язані товари називаються наборами.

Ви можете помітити, що чіпси, чіпси з соусом і газована вода часто стоять на прилавках поруч. Це називається двоелементною набором. Коли база даних досить велика, буде набагато складніше «побачити» взаємозв'язку, особливо, коли ви маєте справу з трьохелементна або більшими наборами. Якраз для цього і створений алгоритм Apriori.

Як же працює алгоритм Apriori? Перед тим, як перейти до суті алгоритму, вам потрібно визначити 3 параметра:

1. По-перше, потрібно встановити розмір набору. Ви хочете визначити двоелементний, трьохелементна набір або який-небудь ще?
2. По-друге, визначити підтримку - це число транзакцій, що входять в набір, розділене на загальну кількість транзакцій. Набір, який дорівнює підтримки, є самим поширеним набором.
3. По-третє, визначити достовірність. тобто умовну ймовірність певного товару виявитися в кошику з іншими товарами. Приклад: чіпси в вашому наборі мають 67% -ву ймовірність опинитися в одному кошику з газованою водою.

Простий алгоритм Apriori складається з трьох кроків:

Чи потребує цей метод навчання або він самонавчальний? Apriori зазвичай розглядається як самонавчальний алгоритм, тому його часто застосовують для пошуку цікавих шаблонів і відносин.

Існує модифікація алгоритму Apriori, здатна проводити класифікацію маркованих даних

Чому саме Apriori? Він простий, зрозумілий, легкореалізуем і має безліч модифікацій.

З іншого боку…

В процесі роботи алгоритм може бути досить ресурсомісткі; обчислення можуть зайняти досить багато часу.

Де він використовується? Існує величезна кількість реалізацій Apriori. Одні з найпопулярніших - це ARtool. Weka і Orange.

Псевдокод алгоритму Apriori

Реалізація алгоритму Apriori в R

apriori (data, parameter = NULL, appearance = NULL, control = NULL)

• data
  object of class transactions or any data structure which can be coerced into transactions (e.g. a binary matrix or data.frame).
• parameter
  object of class APparameter or named list. The default behavior is to mine rules with support 0.1, confidence 0.8, and maxlen 10.
• appearance
  object of class APappearance or named list. With this argument item appearance can be restricted (implements rule templates). By default all items can appear unrestricted.
• control
  object of class APcontrol or named list. Controls the algorithmic performance of the mining algorithm (item sorting, etc.)