Анализ ассоциаций

Одним из популярных методов интеллектуального анализа являются алгоритмы поиска ассоциативных правил, которые позволяют находить закономерности между связанными событиями. Примером такого правила, служит утверждение, что покупатель, приобретающий товар «А», приобретет и товар «B» с вероятностью 75%.

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

Пусть имеется база данных, состоящая из покупательских транзакций. Каждая транзакция - это набор товаров, купленных покупателем за один визит. Пусть I = {i₁, i₂, i₃, ...i_n} - набор товаров, называемых элементами. Пусть D - множество транзакций, где каждая транзакция T - это набор элементов из I, T I. Каждая транзакция представляет собой бинарный вектор, где t[k]=1, если i_k элемент присутствует в транзакции, иначе t[k]=0. Транзакция T содержит X, некоторый набор элементов из I, если X T. Ассоциативным правилом называется импликация X Y, где X I, Y I и X Y = . Правило X Y имеет поддержку s, если s% транзакций из D, содержат X Y, s(X Y) = s(X Y). Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X Y справедливо с достоверностью c, если c% транзакций из D, содержащих X, также содержат Y, c(X Y) = s(X Y)/s(X).

Для примера рассмотрим утверждение: «75% транзакций, содержащих хлеб, также содержат молоко. 3% от общего числа всех транзакций содержат оба товара». 75% - это уровень доверия, 3% - это поддержка.

Другими словами, целью анализа является установление следующих зависимостей: если в транзакции встретился некоторый набор элементов X, то на основании этого можно сделать вывод о том, что другой набор элементов Y также же должен появиться в этой транзакции. Установление таких зависимостей дает нам возможность находить очень простые и интуитивно понятные правила.

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

Задача нахождения ассоциативных правил разбивается на две подзадачи:

Нахождение всех наборов элементов, которые удовлетворяют порогу поддержки. Такие наборы элементов называются часто встречающимися.
Генерация правил из наборов элементов, найденных согласно п.1. с достоверностью, удовлетворяющей порогу достоверности.

Значения для параметров минимальная поддержка и минимальная достоверность выбираются таким образом, чтобы ограничить количество найденных правил. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитикам или настолько очевидные, что нет никакого смысла проводить такой анализ. С другой стороны, низкое значение поддержки ведет к генерации огромного количества правил, что, конечно, требует существенных вычислительных ресурсов. Тем не менее, большинство интересных правил находится именно при низком значении порога поддержки. Хотя слишком низкое значение поддержки ведет к генерации статистически необоснованных правил.

См. также:

Библиотека методов и моделей | Анализ ассоциаций | ISmAssociationRules