Методы поиска ассоциативных правил

Технологии обработки информации. Лекция 12. Методы поиска ассоциативных правил Красноярск, 2019 Содержание 1. 2. 3. 4. 2 Понятия ассоциативных правил. Существующие алгоритмы поиска ассоциативных правил. Часто встречающиеся наборы элементов. Применение задачи поиска ассоциативных правил для анализа покупательской корзины. Введение в ассоциативные правила Задача поиска ассоциативных правил (association rule mining) была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis). Рыночная корзина - это набор товаров, приобретенных покупателем в рамках одной отдельно взятой транзакции. Транзакция - это множество событий, которые произошли одновременно. Транзакционная или операционная база данных (Transaction database) представляет собой двумерную таблицу, которая состоит из номера транзакции (TID) и перечня покупок, приобретенных во время этой транзакции. TID - уникальный идентификатор, определяющий каждую сделку или транзакцию.      3 Приложения с применением ассоциативных правил Розничная торговля: определение товаров, которые стоит продвигать совместно; выбор местоположения товара в магазине; анализ потребительской корзины; прогнозирование спроса; Перекрестные продажи: если есть информация о том, что клиенты приобрели продукты A, Б и В, то какие из них вероятнее всего купят продукт Г? Маркетинг: поиск рыночных сегментов, тенденций покупательского поведения; Сегментация клиентов: выявление общих характеристик клиентов компании, выявление групп покупателей; оформление каталогов, анализ сбытовых кампаний фирмы, определение последовательностей покупок клиентов (какая покупка последует за покупкой товара А); анализ Web-логов.       4 Пример базы данных В таблице первая колонка (TID) определяет номер транзакции, во второй колонке таблицы приведены товары, приобретенные во время определенной транзакции.  5 TID Приобретенные покупки 100 хлеб, молоко, печенье 200 Молоко, сметана 300 Молоко, хлеб, сметана, печенье 400 Колбаса, сметана 500 Хлеб, молоко, печенье, сметана Присвоим значениям товаров переменные: Хлеб = a Молоко = b Печенье = c Сметана = d Колбаса = e Конфеты = f Характеристики ассоциативных правил Набор данных: abc={a,b,c}  Поддержка: SUP(abc)=3. min_sup=3, {Хлеб, молоко, печенье} - часто встречающийся шаблон.  Таблица 15.2. Часто встречающиеся наборы товаров Приобретенные Приобретенные 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 6 Характеристики ассоциативных правил При минимальном уровне поддержки, равной трем, набор товаров abc является часто встречающимся шаблоном.  Поддержкой называют количество или процент транзакций, содержащих определенный набор данных. Для данного набора товаров поддержка, выраженная в процентном отношении, равна 50%. SUP(abc)=(3/6)*100%=50%  Поддержку иногда также называют обеспечением набора. Таким образом, набор представляет интерес, если его поддержка выше определенного пользователем минимального значения (minsupport).   7 Эти наборы называют часто встречающимися (frequent). Характеристики ассоциативных правил Ассоциативное правило имеет вид: "Из события A следует событие B".  В результате такого вида анализа мы устанавливаем закономерность следующего вида: "Если в транзакции встретился набор товаров (или набор элементов) A, то можно сделать вывод, что в этой же транзакции должен появиться набор элементов B)"  Установление таких закономерностей дает нам возможность находить очень простые и понятные правила, называемые ассоциативными. Поддержка и достоверность. Достоверность правила показывает, какова вероятность того, что из события A следует событие B. Число транзакций, содержащих молоко, равно четырем, число транзакций, содержащих печенье, равно трем, достоверность правила равна (3/4)*100%, т.е. 75%.    8 Границы поддержки и достоверности ассоциативного правила При помощи использования алгоритмов поиска ассоциативных правил аналитик может получить все возможные правила вида "Из A следует B", с различными значениями поддержки и достоверности. Однако в большинстве случаев, количество правил необходимо ограничивать заранее установленными минимальными и максимальными значениями поддержки и достоверности.   9 Методы поиска ассоциативных правил Алгоритм AIS:  В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются "на лету", во время сканирования базы данных. Алгоритм SETM:  Создание этого алгоритма было мотивировано желанием использовать язык SQL для вычисления часто встречающихся наборов товаров. Алгоритм Apriori состоит из двух этапов:  формирование кандидатов;  подсчет кандидатов. 10 Алгоритм Apriori  Формирование кандидатов (candidate generation) - этап, на котором алгоритм, сканируя базу данных, создает множество i-элементных кандидатов (i - номер этапа).    На этом этапе поддержка кандидатов не рассчитывается. Подсчет кандидатов (candidate counting) - этап, на котором вычисляется поддержка каждого i-элементного кандидата. Здесь же осуществляется отсечение кандидатов, поддержка которых меньше минимума, установленного пользователем (min_sup). Оставшиеся i-элементные наборы называем часто встречающимися. 11 Пример поиска часто встречаемых элементов. Минимальная поддержка = 3. 12 Алгоритм Apriori     На первом этапе происходит формирование одноэлементных кандидатов. Далее алгоритм подсчитывает поддержку одноэлементных наборов. Далее происходит формирование двухэлементных кандидатов, подсчет их поддержки и отсечение наборов с уровнем поддержки, меньшим 3. алгоритм Apriori уменьшает количество кандидатов, отсекая – априори - тех, которые заведомо не могут стать часто встречающимися, на основе информации об отсеченных кандидатах на предыдущих этапах работы алгоритма. Алгоритм Apriori рассчитывает также поддержку наборов, которые не могут быть отсечены априори. 13 Разновидности алгоритма Apriori       Разновидности алгоритма Apriori, являющиеся его оптимизацией, предложены для сокращения количества сканирований базы данных, количества наборов-кандидатов или того и другого. AprioriTid база данных D не используется для подсчета поддержки кандидатов набора товаров после первого прохода AprioriHybrid. DHP алгоритм – данные кешируются в процесса анализа для более быстрой обработки данных. Partition алгоритм. Алгоритм DIC, Dynamic Itemset Counting. 14 Пример решения задачи поиска ассоциативных правил  Дана транзакционная база данных, необходимо найти наиболее часто встречающиеся наборы товаров и набор ассоциативных правил с определенными границами значений поддержки и доверия. 15 Пример решения задачи поиска ассоциативных правил  необходимо настроить параметры поиска правил, т.е. установить минимальные и максимальные характеристики поддержки и достоверности. 16 Визуализатор: "Популярные наборы" N Множество 6 3 5 10 4 2 1 12 11 8 7 13 ХЛЕБ И БУЛКИ МАСЛО СОКИ МАСЛО И ХЛЕБ И БУЛКИ МОЛОКО КЕФИР ЙОГУРТЫ СОКИ И ХЛЕБ И БУЛКИ МОЛОКО И ХЛЕБ И БУЛКИ МАСЛО И МОЛОКО ЙОГУРТЫ И КЕФИР МАСЛО И МОЛОКО И ХЛЕБ И БУЛКИ МАСЛО И СОКИ 9 17 Поддержка % Кол-во 54,55 24 52,27 23 50,00 22 45,45 20 43,18 19 31,82 14 31,82 14 22,73 10 22,73 10 22,73 10 22,73 10 20,45 9 20,45 9 Визуализатор "Правила"  Правила в данном визуализаторе размещены в виде списка. Каждое правило, представленное как "условие-следствие", характеризуется значением поддержки в абсолютном и процентном выражении, а также достоверностью. 18 N Условие 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ЙОГУРТЫ КЕФИР МАСЛО МОЛОКО СОКИ МАСЛО ХЛЕБ И БУЛКИ МОЛОКО ХЛЕБ И БУЛКИ СОКИ ХЛЕБ И БУЛКИ МАСЛО И МОЛОКО МАСЛО И ХЛЕБ И БУЛКИ МОЛОКО И ХЛЕБ И БУЛКИ МОЛОКО Поддержка Достоверн % Кол-во ость, % КЕФИР 22,73 10 71,43 ЙОГУРТЫ 22,73 10 71,43 МОЛОКО 22,73 10 43,48 МАСЛО 22,73 10 52,63 МАСЛО 20,45 9 40,91 ХЛЕБ И БУЛКИ 45,45 20 86,96 МАСЛО 45,45 20 83,33 ХЛЕБ И БУЛКИ 22,73 10 52,63 МОЛОКО 22,73 10 41,67 ХЛЕБ И БУЛКИ 22,73 10 45,45 СОКИ 22,73 10 41,67 ХЛЕБ И БУЛКИ 20,45 9 90,00 МОЛОКО 20,45 9 45,00 МАСЛО 20,45 9 90,00 МАСЛО И ХЛЕБ И БУЛКИ 20,45 9 47,37 Следствие Визуализатор "Что-если"  Визуализатор "что-если" удобен, если необходимо ответить на вопрос, какие следствия могут получиться из данного условия.  19 Например, выбрав условие "МОЛОКО", в левой части экрана получим три следствия "МАСЛО", "ХЛЕБ И БУЛКИ", "МАСЛО И ХЛЕБ И БУЛКИ", для которых указаны уровень поддержки и достоверности. Литература Обучение ассоциативным правилам, url: https://ru.wikipedia.org/wiki/Обучение_ассоциативным_правилам Ассоциативные правила, url: https://habr.com/ru/company/ods/blog/353502/ Введение в анализ ассоциативных правил, url: https://basegroup.ru/community/articles/intro 1. 2. 3. 20