10. «Методы Data Mining: ассоциативные правила»

«Методы Data Mining: ассоциативные правила»

1. Определение. Основные понятия

2. Типы ассоциативных правил

3. Алгоритм Apriori

4. Применение ассоциативных правил

1. Определение. Основные понятия

Ассоциативные правила – метод Data Mining, основанный на поиске закономерностей между связанными событиями в базах данных.

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

Рыночная корзина - это набор товаров, приобретенных покупателем в рамках одной отдельно взятой транзакции.

Транзакция - это множество событий, которые произошли одновременно.

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

Анализ производится на основе транзакционной базы данных – двумерной таблицы, состоящей из идентификатора транзакции (TID) и перечня покупок, приобретенных во время этой транзакции (товар A, B, C и так далее).

Рассмотрим пример.

Допустим, у нас есть информация о покупках шести посетителей нашего магазина. Оформим ее в виде таблицы:

TID	Покупки
001	Хлеб, молоко, печенье
002	Молоко, сметана
003	Молоко, хлеб, сметана, печенье
004	Колбаса, сметана
005	Хлеб, молоко, печенье, сметана
006	Конфеты

Заменим наименования товаров на переменные:

Хлеб = a Молоко = b Печенье = c Сметана = d Колбаса = e Конфеты = f

Наша транзакционная база данных приняла вид:

TID	Покупки
001	a, b, c
002	b, d
003	b, a, d, c
004	e, d
005	a, b, c, d
006	f

Рассмотрим набор товаров (itemset), включающий, например, Хлеб, Молоко и Печенье. Данный набор встречается в нашей базе данных три раза, то есть поддержка этого набора товаров равна 3.

Поддержкой (support) называется количество или процент транзакций, содержащих определенный набор данных.

В нашем случае поддержка равна (3/6)*100% = 50%.

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

Все это нужно для установления закономерности вида «Если в транзакции встретился набор товаров А, то можно сделать вывод, что в этой же транзакции должен появиться набор товаров В». Грубо говоря: «Если посетитель купил Молоко, то высока вероятность, что он купит еще и Печенье». Данная закономерность и является ассоциативным правилом.

Характеристиками ассоциативного правила являются поддержка и достоверность.

Рассмотрим правило «из покупки молока следует покупка печенья».

Правило имеет поддержку s, если s% транзакций из всего набора содержат одновременно наборы элементов A и B или, другими словами, содержат оба товара.

Молоко - это товар A, печенье - это товар B. Поддержка правила "из покупки молока следует покупка печенья" равна 3, или 50%.

Достоверность (confidence) правила показывает, какова вероятность того, что из события A следует событие B.

Правило "Из A следует B" справедливо с достоверностью с, если c% транзакций из всего множества, содержащих набор элементов A, также содержат набор элементов B.

Число транзакций, содержащих молоко, равно четырем, число транзакций, содержащих печенье, равно трем, достоверность правила равна (3/4)*100%, т.е. 75%. Достоверность правила "из покупки молока следует покупка печенья" равна 75%, т.е. 75% транзакций, содержащих товар А, также содержат товар B.

При помощи использования алгоритмов поиска ассоциативных правил аналитик может получить все возможные правила вида "Из A следует B", с различными значениями поддержки и достоверности. Однако в большинстве случаев, количество правил необходимо ограничивать заранее установленными минимальными и максимальными значениями поддержки и достоверности.

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

Если уровень достоверности слишком мал, то ценность правила вызывает серьезные сомнения. Например, правило с достоверностью в 3% только условно можно назвать правилом.