2. Поиск ап(Ассоциативные правила)

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

Классический пример анализ связей среди различных типов товаров на складе, который подтверждает, что тот клиент, который покупает некоторый продукт (например, хлеб) обычно также покупает другой – молоко.

Предположим, что таблица 1 отображает информацию собранную ретейлерами. Таблица описывает композицию шести покупок, т.е. шести транзакций в терминах из 4 элементов: хлеб, масло, бисквиты и молоко. Значение равное единице означает, что соответствующий ему элемент включен (не включен) в транзакцию. Очень легко определить ассоциативное правило Bread&Butter => Milk, которое иллюстрирует тот факт: что когда клиент покупает хлеб и батон, то он так же покупает молоко. Однако, это правило имеет одно исключение в 5 транзакции и значит ретейлер не может полностью доверять данному заявлению.

Для измерения надежности\точности правила существуют два параметра Поддержка и Достоверность, которые интенсивно используются в данной области. Поддержка измеряет надежность, используя относительную частоту вхождения элемента в правиле. Достоверность измеряет точность правила, как коэффициент между поддержкой этого правила и относительной частотой вхождения элементов в левую часть правила. В нашем примере поддержка равна 3\6, а достоверность – 3\4.

Tran-id	Bread (хлеб)	Butter (масло)	Biscuits (бисквит)	Milk (молоко)
1	1	1	0	1
2	0	1	1	0
3	1	0	1	0
4	1	1	0	1
5	1	1	1	0
6	1	1	1	1

Таблица 1 – множество транзакций.

Разработчик ищет ассоциативные правила (АП) в наборах элементов с поддержкой больше чем порог minsupp, который фиксирует пользователь. С точки зрения Достоверности ассоциативного правила, отбирают те АП, для которых оно больше чем порог minconf.

2.1 Формальная модель.

Пусть множеств элементов (объектов) и множество транзакций в причем оба не пустые.

Определение 1. Ассоциативное правил (АП) это выражение , где , и .

Правило означает «каждая транзакция из , которая содержит , так же содержит ».

Как был сказано выше, обычно чтобы оценить ассоциативное правило измеряют Support(поддержка) и Confidence(достоверность), оба базируются на концепции поддержки множества элементов(itemset).

Определение 2. Поддержка множества элементов в отношении множества транзакций

,

то есть, вероятность того, что транзакция из содержит .

Определение 3. Support(Поддержка) ассоциативного правила в это

и

Confidence(достоверность)

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

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

Методы, используемые для добычи ассоциативных правил (АП) пытаются открыть те, чья поддержка и достоверность больше чем два определенных пользователем порога, называемых , соответственно. Такие правила называют «строгими правилами».