Алгоритм Apriori

Идём дальше в цикле статей Топ-10 data mining алгоритмов и рассматриваем полезный и интересный алгоритм Apriori (Априори).

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

Что такое ассоциативные правила? Изучение ассоциативных правил – это техника, применяемая в data mining для изучения соотношений и отношений между переменными базы данных.

Как выглядит пример использования алгоритма Apriori? Скажем, у нас есть база данных транзакций супермаркета. Вы можете представить себе базу данных как огромную таблицу, в которой каждая строка – это номер транзакции, а каждый столбик представляет собой отдельные покупки.

Хорошие новости:

Применяя алгоритм Apriori, мы можем определить товары, купленные вместе – то есть установить ассоциативные правила.

Что это дает нам:

Вы можете определить товары, которые часто покупают вместе. Основная задача маркетинга – заставить клиентов покупать больше. Связанные товары называются наборами.

Например:

Вы можете заметить, что чипсы, чипсы с соусом и газировка часто стоят на прилавках рядом. Это называется двухэлементным набором. Когда база данных достаточно большая, будет гораздо сложнее «увидеть» взаимосвязи, в особенности, когда вы имеете дело с трёхэлементными или более крупными наборами. Как раз для этого и создан алгоритм Apriori.

Как же работает алгоритм Apriori? Перед тем, как перейти к сути алгоритма, вам нужно определить 3 параметра:

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

Простой алгоритм Apriori состоит из трех шагов:

  1. Объединение. Просмотр базы данных и определение частоты вхождения отдельных товаров.
  2. Отсечение. Те наборы, которые удовлетворяют поддержке и достоверности, переходят на следующую итерацию с двухкомпонентными наборами,
  3. Повторение. Предыдущие два шага повторяются для каждой величины набора, пока не будет повторно получен ранее определенный размер.

Требует ли этот метод обучения или он самообучающийся? Apriori обычно рассматривается как самообучающийся алгоритм, поэтому его часто применяют для поиска интересных шаблонов и отношений.

Еще кое-что…

Существует модификация алгоритма Apriori, способная проводить классификацию маркированных данных

Почему именно Apriori? Он прост, понятен, легкореализуем и имеет множество модификаций.

С другой стороны…

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

Где он используется? Существует огромное количество реализаций Apriori. Одни из самых популярных – это ARtool, Weka и Orange.

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

алгоритм априори

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

Пакет: arules

Общий вид:

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.)
Пример 1

Пример 2

Аналогичную, но с несколько иным подходом, реализацию алгоритма Apriori для базы Adult пакета Arules можно найти здесь (там же дано описание функции более подробно). Ещё примеры доступны тут.

Реализация алгоритма Apriori в Python

apriori.py доступен на github.

Дополнительные комментарии:

To run the program with dataset provided and default values for minSupport = 0.15 and minConfidence = 0.6

python apriori.py -f INTEGRATED-DATASET.csv

To run program with dataset

python apriori.py -f INTEGRATED-DATASET.csv -s 0.17 -c 0.68

Best results are obtained for the following values of support and confidence:

Support : Between 0.1 and 0.2

Confidence : Between 0.5 and 0.7

И ещё одна реализация Apriori на Питоне.

Data Scientist # 1

Машинное обучение, большие данные, наука о данных, анализ данных, цифровой маркетинг, искусственный интеллект, нейронные сети, глубокое обучение, data science, data scientist, machine learning, artificial intelligence, big data, deep learning

Данные — новый актив!

Эффективно управлять можно только тем, что можно измерить.
Copyright © 2016-2021 Data Scientist. Все права защищены.