Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Кондрашов ВСЕ.doc
Скачиваний:
9
Добавлен:
01.05.2025
Размер:
12 Мб
Скачать
☆

Задача ассоциации

Ассоциация - поиск закономерности между связанными событиями в наборе данных. Целью поиска ассоциативных правил (association rule) является нахождение закономерностей между связанными событиями в базах данных.

Можно привести ряд примеров бизнес-приложений, в которых применяются ассоциативные правила:

  • розничная торговля (определение товаров, которые стоит продвигать совместно; выбор местоположения товара в магазине; анализ потребительской корзины; прогнозирование спроса, тенденции покупательского поведения)

  • сегментация клиентов (выявление общих характеристик клиентов компании, выявление групп покупателей)

  • анализ Web-логов.

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

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

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

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

Полученные в результате анализа шаблоны включают перечень товаров и число транзакций, которые содержат данные наборы.

Пример транзакционной или операционной базы данных был приведен в разделе «Требования к СУБД и используемые данные». Она представляет собой двумерную таблицу, которая состоит из номера транзакции (TID) и перечня покупок, приобретенных во время этой транзакции.

TID

Приобретенные покупки

100

Хлеб, молоко, печенье

200

Молоко, сметана

300

Молоко, хлеб, сметана, печенье

400

Колбаса, сметана

500

Хлеб, молоко, печенье, сметана

На основе имеющейся базы данных можно найти закономерности между событиями (покупками).

Обозначим товары переменными (Хлеб = a, Молоко = b, Печенье = c, Сметана = d, Колбаса = e, Конфеты = f). Тогда транзакционная база данных примет вид:

TID

Приобретенные покупки

TID

Приобретенные покупки

100

Хлеб, молоко, печенье

100

a, b, c

200

Молоко, сметана

200

b, d

300

Молоко, хлеб, сметана, печенье

300

b, a, d, c

400

Колбаса, сметана

400

e, d

500

Хлеб, молоко, печенье, сметана

500

a, b, c, d

600

Конфеты

600

f

Основными характеристиками ассоциативного правила являются поддержка (обеспечение набора) и достоверность правила.

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

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

Выразим набор товаров {Хлеб, молоко, печенье} с помощью переменных: abc={a,b,c}

Этот набор товаров встречается в нашей базе данных три раза, т.е. поддержка этого набора товаров равна 3 (SUP(abc)=3). При минимальном уровне поддержки, равной трем, набор товаров abc является часто встречающимся шаблоном (min_sup=3, {Хлеб, молоко, печенье} - часто встречающийся шаблон).

Для данного набора товаров поддержка, выраженная в процентном отношении, равна 50% (SUP(abc)=(3/6)*100%=50%).

Таким образом, набор представляет интерес, если его поддержка выше определенного пользователем минимального значения (min support). Эти наборы называют часто встречающимися (frequent).

Ассоциативное правило имеет вид: "Из события A следует событие B".

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

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

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

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

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

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

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

Существуют различные алгоритмы поиска ассоциативных правил (AIS, SETM, Aprioriи др.).

Контрольные вопросы:

  1. Что такое ассоциация?

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

  3. Что такое транзакция?

  4. Какая структура транзакционной базы данных?

  5. Основные характеристики ассоциативного правила?

  6. Что такое поддержка правила?

  7. Что такое достоверность правила?

  8. Зачем заранее устанавливать минимальные и максимальные значения поддержки и достоверности?