Анализ правил ассоциации и априорный алгоритм

Интеллектуальный анализ ассоциативных правил является широко используемым методом интеллектуального анализа данных, обычно относящимся кПроцесс обнаружения частых закономерностей и ассоциаций элементов или объектов из транзакционных, реляционных и других наборов данных.. Этот метод обычно используется при анализе потребительской корзины. Впервые он был использован для обнаружения связи между различными товарами в базе данных продаж супермаркета.пиво и подгузникиэтого абзаца.

Было замечено, что многие клиенты также покупают пиво, когда покупают подгузники, поэтому супермаркеты могут увеличить продажи, поместив подгузники и пиво вместе, а размещение картофельных чипсов посередине увеличит продажи всех трех товаров одновременно.

Тогда это явление натолкнет на некоторые размышления о том, какие продукты клиенты, скорее всего, купят одновременно?

Базовые концепты

Прежде чем описывать процесс алгоритма, давайте введем некоторые основные понятия.Прежде всего, у нас есть транзакционная база данных:

Изучаемый объект называется товаром, а в контексте приложения для анализа покупательской корзины каждый товар, приобретенный покупателем, называется товаром.
Сбор всех предметов: I={ $i_1$ , $i_2$ , ... $i_m$ }
за транзакцию $t_i$ Набор соответствующих элементов является подмножеством I
Любое подмножество I называется набором элементов: x = { $i_{j1}, i_{j2}...i_{jp}$ }
База данных транзакций D представляет собой набор транзакций, D={ $t_1$ , $t_2$ ..., $t_m$ }
Количество элементов, содержащихся в каждом наборе элементов, становится длиной набора элементов, а набор элементов длины k называется k-наборами элементов.
Количество раз, когда набор элементов X появляется в базе данных D, называется частотой и обозначается как count(X).

служба поддержки

Поддержка набора элементов X относится к доле записей в наборе данных, содержащих этот набор элементов.

support(X) = count(X)/|D|

Если указана минимальная поддержка minsup, support(X) >= minsup, то X вызываетсячастые наборы предметов, можно также сказать, что X встречается часто.

уверенность / достоверность

Уверенность/достоверность определяется для правила ассоциации, такого как X->Y, которое относится к доле транзакций, содержащих X, которые содержат Y.

conf(X \rightarrow Y) = |XY|/|X| = sup(XY)/sup(X)

Априорный алгоритм

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

Найти все часто встречающиеся наборы: все наборы с поддержкой >= minsupport
1. Подсчитайте поддержку каждого набора кандидатов k-элементов и найдите частые наборы k-элементов: $L_k$
2. Используйте частые наборы из k элементов для создания наборов кандидатов из k + 1 элемента: $C_{k+1}$ , k=k+1
Создайте возможные правила ассоциации из каждого частого набора

Вот пример, минимальная поддержка minsup=2

apriori算法举例

Поток алгоритма, описанный в тексте:

Сканируем TDB, вычисляем поддержку для каждого кандидата, чтобы получить таблицу C1
Сравните степень поддержки и минимальную степень поддержки каждой пост-опции в C и получите одномерный максимальный набор элементов L1.
Получите набор кандидатов C2 из L1
L2 получается сравнением носителя из C2
Получить C3 из L2
Получите трехмерный набор предметов L3 из C3.

В соответствии с описанным выше процессом мы также обнаружим, что цикл генерирует слишком много комбинаций при создании наборов кандидатов на каждом этапе алгоритма.Мы можем выполнить сокращение, изучив свойства правил ассоциации.

Подмножество любого частого набора должно быть частым
Априорное правило отсечения: если есть несколько наборов элементов, которые встречаются редко, то любые надмножества этих наборов элементов являются нечастыми, потому что нет необходимости генерировать и тестировать

Как показано на рисунке, АВ нечастый, то и все суперсеты, обведенные красным пунктирным кружком, тоже нечастые, поэтому их можно отсечь. Таким образом, метод создания набора кандидатов можно резюмировать следующим образом:

Гипотетические наборы предметов $L_k$ Товары заказаны

Сочетание двух $L_k$ Генерация набора элементов $C_{k+1}$
обрезать

Создание правил ассоциации

Предыдущее закончило, как генерировать частые наборы элементов, давайте поговорим о том, как генерировать правила ассоциации, существующий частый набор элементов L, генерировать каждый неэфирный набор S, если S удовлетворяет минимальной достоверности:

confidence((l-s) \rightarrow s) = \frac{sup(l)}{sup(l-s)} >= minconf

Затем выведите правило ассоциации (l-s)->s.

关联规则示例

Как показано на рисунке, минимальная достоверность minconf=80%, для частого набора элементов BCE получаются следующие правила ассоциации, из которых более 80% составляют правила BC->E и CE-

Поднимать

Теперь мы освоили алгоритм поиска часто встречающихся наборов элементов и правил ассоциации, так как же нам определить, что рассчитанные поддержка и достоверность верны? Теперь пример такой:

提升度示例

Интуитивно нет никакой связи между игрой в баскетбол и употреблением овсянки, но по результатам приведенных выше расчетов поддержка и достоверность правила игры в баскетбол -> употребление овсянки довольно высоки. Это показывает, что поддержка и уверенность иногда не обязательно точно отражают корреляцию между данными. Затем вводится новая концепция Lift.

lift = \frac{P(A \cup B)}{P(A)P(B)} = \frac{conf(A \rightarrow B)}{sup(B)}

Если подъем > 1, это означает, что А имеет улучшение по сравнению с В, в противном случае улучшения нет.

Теперь априорный алгоритм можно свести к четырем шагам:

Установить минсуп и минконф
найти частые наборы предметов
Найдите правила conf>minconf на основе частых наборов элементов
Подсчитайте степень улучшения правил, найденных на предыдущем шаге, и выберите те, которые имеют наивысшую степень улучшения.

Поскольку априорный алгоритм может генерировать большое количество наборов кандидатов, появился новый алгоритм, алгоритм FP-роста. Он основан на Apriori, но использует расширенные структуры данных, чтобы уменьшить количество сканирований и значительно ускорить алгоритм. Алгоритму FP-роста требуется всего два раза сканировать базу данных, в то время как априорный алгоритм сканирует набор данных для каждого потенциально частого набора элементов, чтобы определить, является ли данный шаблон частым, поэтому алгоритм FP-роста быстрее, чем априорный алгоритм. Этот алгоритм будет подробно рассмотрен позже. Вышеизложенное является базовыми знаниями об алгоритме Априори. Я потрачу время, чтобы написать простую реализацию кода алгоритма Априори. Вот флаг~