Идём дальше в цикле статей Топ-10 data mining алгоритмов и рассматриваем полезный и интересный алгоритм Apriori (Априори).
Алгоритм Apriori ищет ассоциативные правила и применяется по отношению к базам данных, содержащим огромное количество транзакций.
Что такое ассоциативные правила? Изучение ассоциативных правил – это техника, применяемая в data mining для изучения соотношений и отношений между переменными базы данных.
Как выглядит пример использования алгоритма Apriori? Скажем, у нас есть база данных транзакций супермаркета. Вы можете представить себе базу данных как огромную таблицу, в которой каждая строка – это номер транзакции, а каждый столбик представляет собой отдельные покупки.
Хорошие новости:
Применяя алгоритм Apriori, мы можем определить товары, купленные вместе – то есть установить ассоциативные правила.
Что это дает нам:
Вы можете определить товары, которые часто покупают вместе. Основная задача маркетинга – заставить клиентов покупать больше. Связанные товары называются наборами.
Например:
Вы можете заметить, что чипсы, чипсы с соусом и газировка часто стоят на прилавках рядом. Это называется двухэлементным набором. Когда база данных достаточно большая, будет гораздо сложнее «увидеть» взаимосвязи, в особенности, когда вы имеете дело с трёхэлементными или более крупными наборами. Как раз для этого и создан алгоритм Apriori.
Как же работает алгоритм Apriori? Перед тем, как перейти к сути алгоритма, вам нужно определить 3 параметра:
- Во-первых, нужно установить размер набора. Вы хотите определить двухэлементный, трёхэлементный набор или какой-нибудь еще?
- Во-вторых, определить поддержку – это число транзакций, входящих в набор, разделенное на общее количество транзакций. Набор, который равен поддержке, является самым часто встречаемым набором.
- В-третьих, определить достоверность, то есть условную вероятность определенного товара оказаться в корзине с другими товарами. Пример: чипсы в вашем наборе имеют 67%-ную вероятность оказаться в одной корзине с газировкой.
Простой алгоритм Apriori состоит из трех шагов:
- Объединение. Просмотр базы данных и определение частоты вхождения отдельных товаров.
- Отсечение. Те наборы, которые удовлетворяют поддержке и достоверности, переходят на следующую итерацию с двухкомпонентными наборами,
- Повторение. Предыдущие два шага повторяются для каждой величины набора, пока не будет повторно получен ранее определенный размер.
Требует ли этот метод обучения или он самообучающийся? 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
1 2 3 4 5 |
install.packages(“arules”) library(arules) data("Adult") ## Mine association rules. rules |
Пример 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# загружаем необходимый пакет install.packages(“arules”) library(arules) # для визуализации предлагаем скачать и загрузить пакет для соответствующей визуализации library("arulesViz") # генерируем данные для примера patterns = random.patterns(nItems = 1000) summary(patterns) trans = random.transactions(nItems = 1000, nTrans = 1000, method = "agrawal", patterns = patterns) image(trans) # создаём правила data("AdultUCI") Adult = as(AdultUCI, "transactions") rules = apriori(Adult, parameter=list(support=0.01, confidence=0.5)) rules # инспектируем данные напрямую или с использованием графиков inspect(head(sort(rules, by="lift"),3)) plot(rules) head(quality(rules)) plot(rules, measure=c("support","lift"), shading="confidence") plot(rules, shading="order", control=list(main ="Two-key plot")) # когда у нас очень много ассоциаций, это затрудняем анализ. Потому мы можем обрезать их sel = plot(rules, measure=c("support","lift"), shading="confidence", interactive=TRUE) subrules = rules[quality(rules)$confidence > 0.8] subrules # вот несколько способов для построения графиков и даже 3D графиков plot(subrules, method="matrix", measure="lift") plot(subrules, method="matrix", measure="lift", control=list(reorder=TRUE)) plot(subrules, method="matrix3D", measure="lift") plot(subrules, method="matrix3D", measure="lift", control = list(reorder=TRUE)) plot(subrules, method="matrix", measure=c("lift", "confidence")) plot(subrules, method="matrix", measure=c("lift","confidence"), control = list(reorder=TRUE)) plot(rules, method="grouped") plot(rules, method="grouped", control=list(k=50)) sel = plot(rules, method="grouped", interactive=TRUE) # Теперь мы можем взять выборку из 30 самых важных правил и проверить их на значимые ассоциации subrules2 = head(sort(rules, by="lift"), 30) plot(subrules2, method="graph") plot(subrules2, method="graph", control=list(type="items")) plot(subrules2, method="paracoord") plot(subrules2, method="paracoord", control=list(reorder=TRUE)) oneRule = sample(rules, 1) inspect(oneRule) |
Аналогичную, но с несколько иным подходом, реализацию алгоритма 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 на Питоне.