Общедоступный номер: Data Club
Введение в правила ассоциации
Интеллектуальный анализ правил ассоциации позволяет нам обнаруживать взаимосвязь между элементами из наборов данных. Он имеет множество сценариев применения в нашей жизни. «Анализ покупательской корзины» — это распространенный сценарий, который можно обнаружить из записей транзакций потребителей. Отношения между продуктами и продуктами, а затем увеличить продажи за счет продаж в комплекте или связанных рекомендаций.
-
Поймите несколько важных понятий в правилах ассоциации: поддержка, уверенность, продвижение.
-
Как работает алгоритм Априори
-
Как на практике мы должны выполнять анализ правил ассоциации?
Важные понятия в правилах ассоциации
Позвольте мне привести пример покупок в супермаркете.Вот список товаров, купленных несколькими покупателями:
| номер заказа | покупать товары |
|---|---|
| 1 | молоко, хлеб, памперсы |
| 2 | Кола, хлеб, подгузники, пиво |
| 3 | молоко, подгузники, пиво, яйца |
| 4 | хлеб, молоко, памперсы, пиво |
| 5 | хлеб, молоко, подгузники, кола |
Служба поддержки
Поддержка – это процентное соотношение количества появлений комбинации продуктов к общему количеству появлений. Чем выше поддержка, тем выше частота комбинации.
Мы видим, что пиво встречается 3 раза, поэтому поддержка пива в 5 заказах составляет 3/5=0,6. Точно так же, если подгузник появляется 5 раз, то степень поддержки подгузника составляет 5/5=1. Поддержка как подгузников, так и пива составляет 3/6=0,6.
Уверенность
Это относится к вероятности покупки продукта B, когда вы покупаете продукт A.
Мы можем посмотреть на продукт выше, количество заказов на покупку пива одновременно с подгузниками равно 3, а количество заказов на покупку пива равно 3, тогда (подгузники -> пиво) уверенность = 3/3 = 1.
Посмотрим, количество заказов на покупку пива и подгузников одновременно равно 3, а количество заказов на покупку подгузников равно 5, тогда (пиво -> подгузники) достоверность = 3/5 = 0,6.
Поднимать
Степень улучшения представляет собой степень, в которой появление товара А увеличивает вероятность появления товара В. Поэтому, когда мы даем рекомендации по продукту, ключевым моментом является степень улучшения.
Давайте посмотрим на формулу подъема: [Ошибка загрузки изображения...(image-d64187-1614950318118)] Затем посчитаем, насколько подгузник улучшает пиво:
[Ошибка загрузки изображения...(image-79a01c-1614950318118)]
[Ошибка загрузки изображения...(image-632f09-1614950318118)]
[Ошибка загрузки изображения...(image-14a268-1614950318118)]
Как интерпретировать значение 1,67?
-
Степень подъема (A→B)>1: означает улучшение
-
Степень подъема (A→B)=1: означает отсутствие улучшения или снижения
-
Степень подъема (A→B)
На самом деле, глядя на приведенную выше формулу степени продвижения, мы можем понять, что чем больше раз AB появляется одновременно, чем меньше раз B появляется отдельно, тем больше степень поддержки, то есть появление B всегда сопровождается появление A. , то вероятность появления A против B увеличится!
Как работает априори
Давайте посмотрим, как работает классический априорный алгоритм правила ассоциации.
Алгоритм Apriori на самом деле представляет собой процесс поиска часто встречающихся наборов элементов, поэтому сначала нам нужно понять часто встречающиеся наборы элементов.
Частые наборы элементов — это наборы элементов с поддержкой, превышающей или равной минимальному порогу поддержки, поэтому элементы с меньшей поддержкой являются нечастыми наборами элементов, а наборы элементов, превышающие или равные минимальной поддержке, являются частыми наборами элементов.
Возьмем каштан:
Предположим, я случайным образом указываю, что минимальная поддержка равна 0,2. Во-первых, мы сначала вычисляем поддержку одного элемента:
| покупать товары | Служба поддержки |
|---|---|
| молоко | 4/5 |
| хлеб | 4/5 |
| подгузник | 5/5 |
| Кола | 2/5 |
| пиво | 3/5 |
| яйцо | 1/5 |
Поскольку минимальная поддержка равна 0,2, вы можете видеть, что яйцо продукта не соответствует минимальной поддержке и не принадлежит к набору частых элементов, поэтому наборы частых элементов отфильтрованных продуктов следующие:
| покупать товары | Служба поддержки |
|---|---|
| молоко | 4/5 |
| хлеб | 4/5 |
| подгузник | 5/5 |
| Кола | 2/5 |
| пиво | 3/5 |
Исходя из этого, мы комбинируем товары попарно, чтобы получить поддержку двух товаров:
| покупать товары | Служба поддержки |
|---|---|
| молоко, хлеб | 3/5 |
| молоко, подгузники | 4/5 |
| молоко, кола | 1/5 |
| молоко, пиво | 2/5 |
| хлеб, подгузники | 4/5 |
| хлеб, кола | 2/5 |
| хлеб, пиво | 2/5 |
| подгузники, кока-кола | 2/5 |
| подгузники, пиво | 3/5 |
| Кола, пиво | 1/5 |
После фильтрации данных выше минимальной поддержки (0,2)
| покупать товары | Служба поддержки |
|---|---|
| молоко, хлеб | 3/5 |
| молоко, подгузники | 4/5 |
| молоко, пиво | 2/5 |
| хлеб, подгузники | 4/5 |
| хлеб, кола | 2/5 |
| хлеб, пиво | 2/5 |
| подгузники, кока-кола | 2/5 |
| подгузники, пиво | 3/5 |
Исходя из этого, мы объединяем три товара, чтобы получить поддержку трех товаров:
| покупать товары | Служба поддержки |
|---|---|
| молоко, хлеб, подгузники | 3/5 |
| молоко, хлеб, кола | 1/5 |
| молоко, хлеб, пиво | 1/5 |
| хлеб, подгузники, кола | 1/5 |
| хлеб, подгузники, пиво | 2/5 |
| Подгузники, Кола, Пиво | 1/5 |
После фильтрации данных выше минимальной поддержки (0,2)
| покупать товары | Служба поддержки |
|---|---|
| молоко, хлеб, подгузники | 3/5 |
| хлеб, подгузники, пиво | 2/5 |
Исходя из этого, мы объединяем четыре товара, чтобы получить поддержку четырех товаров:
| покупать товары | Служба поддержки |
|---|---|
| молоко, хлеб, подгузники, кола | 1/5 |
| молоко, хлеб, памперсы, пиво | 1/5 |
| хлеб, подгузники, кола, пиво | 1/5 |
Если данные, превышающие минимальную поддержку (0,2), будут снова проверены, все данные будут удалены.Затем алгоритм завершается в это время, и последним результатом является частый элемент, который мы ищем, то есть {молоко, хлеб, подгузник}, {хлеб, подгузник}, пиво}.
Подытожим вышеописанный процесс априорного алгоритма:
-
K=1, рассчитать поддержку K наборов элементов
-
Отфильтровать наборы элементов меньше минимальной поддержки
-
Если набор элементов пуст, результатом, соответствующим набору элементов K-1, является окончательный результат.
-
В противном случае K=K+1, повторить шаги 1-3.
Мы видим, что Apriori имеет следующие недостатки в процессе расчета:
-
Может быть сгенерировано большое количество наборов кандидатов. Из-за способа перестановки и комбинирования объединяются все возможные наборы элементов.
-
Каждый расчет должен повторно сканировать набор данных, чтобы рассчитать поддержку для каждого набора элементов.
Это похоже на запрос «полного сканирования таблицы» в нашей базе данных, что является огромной тратой времени и операций ввода-вывода. В базе данных мы все знаем об использовании индексов для быстрого извлечения данных, так можно ли оптимизировать Apriori?
Улучшенный алгоритм Априори: алгоритм FP-роста
Алгоритм роста FP основан на априорном принципе, он находит часто встречающиеся наборы элементов, сохраняя набор данных в дереве FP, но не может найти правила ассоциации между данными. Алгоритму FP-роста нужно сканировать базу данных только дважды, в то время как априорному алгоритму необходимо сканировать набор данных один раз для каждого потенциально часто встречающегося набора элементов, поэтому априорный алгоритм эффективен. Алгоритм находит часто встречающиеся наборы элементов: (1) строит дерево FP; (2) извлекает часто встречающиеся наборы элементов из дерева FP.
Создать таблицу заголовков элементов
Концептуальное знание здесь не для того, чтобы компенсировать количество слов, давайте перейдем прямо к сухим товарам! Предположим, мы извлекаем часто встречающиеся элементы из следующих данных.
Сначала создайте таблицу заголовков элементов. Процесс этого шага заключается в том, чтобы сначала просмотреть набор данных и отсортировать отдельные элементы, которые соответствуют минимальной степени поддержки, от высокого к низкому. В этом процессе элементы, которые не соответствуют минимальной степени поддержки удаляются (при условии, что минимальная поддержка равна 0,2).
Построить дерево FP
Весь процесс требует повторного сканирования набора данных.Для каждого фрагмента данных создайте узлы в порядке поддержки от высокого к низкому (то есть результат сортировки в таблице заголовков элементов на первом шаге), если узел существует , он будет считать count+ 1, если он не существует, создайте его. При этом в процессе создания связанный список таблицы заголовков товаров необходимо обновлять.
Сначала отсортируйте исходные данные в соответствии с опорой, затем исходные данные изменятся следующим образом:
[Ошибка загрузки изображения... (image-add9e4-1614950318118)]
Затем мы вставляем каждую строку данных выше в дерево FP по порядку и отмечаем, что корневой узел дерева FP помечен как узел NULL.
Далее вставляем вторую строку данных.Поскольку первые данные второй строки данных также B, что совпадает с существующей древовидной структурой, то мы сохраняем положение B в исходной древовидной структуре без изменений, и добавляем 1 к count, а C и D — Добавить новые данные, то будет новая вилка дерева, и результат будет следующим:
И так далее, прочитайте следующие три строки данных в дереве FP.
Окончательные сгенерированные числа FP следующие:
Майнинг частых предметов на основе номеров FP
Наконец-то мы построили дерево FP, так как же увидеть это дерево? После получения дерева FP необходимо добывать наборы частых предметов один за другим для каждого частого предмета. Конкретный процесс таков: сначала получите префиксный путь часто встречающихся элементов, а затем используйте префиксный путь в качестве нового набора данных для построения условного дерева FP пути префикса. Затем для каждого частого элемента условного дерева FP получается префиксный путь и строится новое условное дерево FP. Повторяйте непрерывно, пока условное дерево FP не будет содержать только один частый элемент (я все равно не понял этого в первый раз, когда прочитал его).
Дерево FP просматривается снизу вверх, то есть, чтобы найти родительский узел по дочернему узлу, а затем мы это проиллюстрируем ~
Во-первых, мы рассмотрим часто встречающиеся термины, содержащие A:
Мы видим, что есть два дерева, содержащие A. Давайте сначала посмотрим на дерево 2, и мы можем получить путь {B:2,C:2}, где 2 определяется в соответствии с количеством вхождений A. Затем мы создаем дерево FP.Конкретный процесс создания такой же, как процесс создания дерева FP выше, как показано на следующем рисунке:
Обратите внимание, что в настоящее время таблица головных указателей содержит два элемента, поэтому для каждого элемента необходимо получить путь префикса, а путь префикса создается в условном дереве FP до тех пор, пока условное дерево FP не будет содержать только один элемент.
-
Для элемента B полученный путь префикса равен {}, тогда набор частых элементов возвращает {A:2,B:2};
-
Для элемента C получите путь префикса {B:2}, затем создайте путь префикса в условном дереве FP, как показано на следующем рисунке.
Обратите внимание, что условное дерево FP в настоящее время содержит только один элемент, поэтому возвращается часто используемый набор элементов {A:2,C:2,B:2}. Поскольку элемент C также является частым элементом, {A:2,C:2} также является частым набором элементов.
Кроме того, {A:2} сам по себе является частым набором элементов, поэтому наборы частых элементов, соответствующие A, следующие: {A:2},{A:2,C:2},{A:2,B:2},{ А:2,С:2,Б:2}.
Точно так же давайте посмотрим на дерево 1. Дерево 1 относительно простое, с одним путем {B:1}. Согласно описанному выше методу, мы получаем частые элементы этой ветви как {A:1,B:1},{ А:1}.
Подводя итог, мы видим, что обе ветви содержат часто встречающиеся элементы {A,B},{A}. На данный момент мы объединяем две ветви, чтобы получить часто встречающиеся элементы, содержащие A: {A:3},{A: 3 ,B:3},{A:2,C:2},{A:2,C:2,B:2}, мы используем количество вхождений для преобразования, то есть (A,): 3, (A , Б): 3, (А, В): 2, (А, Б, В): 2.
Точно так же, согласно описанному выше методу, мы можем найти, что частыми элементами, содержащими B, являются (D): 2, (C, D): 2, (B, D): 2, (B, C, D): 2, (В): 4, (Б, В): 4, (Б): 5.
Краткое изложение практики
Классический алгоритм, многие боги уже реализовали, мы можем использовать его напрямую, например, вышеприведенный алгоритм FP-GROWTH, ввести специальный пакет pyfpgrowth.
Код:
import pyfpgrowth as fp
itemsets = [['A','B'],['B','C','D'],['B','C'],['A','B','C'],['A','B','C','D']]
patterns = fp.find_frequent_patterns(itemsets, 2)
print(patterns)
{('D',): 2, ('C', 'D'): 2, ('B', 'D'): 2, ('B', 'C', 'D'): 2, ('A',): 3, ('A', 'B'): 3, ('A', 'C'): 2, ('A', 'B', 'C'): 2, ('C',): 4, ('B', 'C'): 4, ('B',): 5}
Людям очень сложно спросить о принципе алгоритма, и это можно сделать с помощью двух строк кода. Мы также смотрим на принцип, просто напишите (скопируйте) код напрямую. Приведу пример, помню, когда я учился в третьем классе начальной школы, была контрольная по математике, и учитель задал дополнительный вопрос:
Дополнительный вопрос (10 баллов): Найдите сумму 1+2+3+…+99+100. Подсказка: Обратитесь к формуле расчета площади трапеции.
Конечно, ученику младших классов на этот вопрос ответить несложно, но еще труднее ответить на него ученику третьего класса начальной школы. Однако я знаю формулу расчета трапеции:
梯形面积 = （上底+下底）×高÷2
Итак, согласно этому расчету
1+2+3+…+99+100 = (1 + 100)x100÷2
На самом деле принцип алгоритма один и тот же, после того, как мы его поймем, мы сможем использовать его логическим выводом, не обязательно в одном сценарии.