поиск ассоциативных правил машинное обучение
Анализ рыночной корзины и ассоциативные правила
В продолжении темы о Data Mining поговорим о том, с чего все начиналось. А начиналось все с анализа рыночной корзины (market basket analysis).
Анализ рыночной корзины — процесс поиска наиболее типичных шаблонов покупок в супермаркетах. Он производится путем анализа баз данных транзакций с целью определения комбинаций товаров, связанных между собой. Иными словами, выполняется обнаружение товаров, наличие которых в транзакции влияет на вероятность появления других товаров или их комбинаций.
Результаты, полученные с помощью анализа рыночной корзины, позволяют оптимизировать ассортимент товаров и запасы, размещение их в торговых залах, увеличивать объемы продаж за счет предложения клиентам сопутствующих товаров. Например, если в результате анализа будет установлено, что совместная покупка макарон и кетчупа является типичным шаблоном, то разместив эти товары на одной и той же витрине можно «спровоцировать» покупателя на их совместное приобретение.
Ассоциативные правила
Для решения задачи анализа рыночной корзины используются ассоциативные правила вида «если… то. ». Например, «если клиент купил пиво, то он купит и чипсы». Каждая покупка именуется «транзакцией», на основании большего набора таких транзакций и строят исследования поведения клиента.
Ассоциативные правила являются очень простой и удобной формой записи знаний. Еще раз хочу уточнить, что информация о транзакциях является исходными данными, а вот полученные ассоциативные правила являются теми знаниями, которые помогли в 80-х большим супермаркетам сэкономить большие деньги.
Для характеристики правила используются некоторые метрики:
Правило X->Y имеет поддержку s (support), если s транзакций из D, содержат пересечение множеств X и Y. Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X->Y справедливо с достоверностью c (confidence), если c транзакций из D, содержащих X, также содержат Y, conf(X-> Y) = supp(X->Y)/supp(X ).
Как правило, очевидные правила имеют поддержку и достоверность высокую (60% и больше), но не являются знаниями де-факто. Основное внимание необходимо уделять правилам, имеющим поддержку 5-10%, именно они могут стать источником идеи промоакции или услуги.
Алгоритм Apriori
Основным алгоритмом, который применяется для получения ассоциативных правил, является алгоритм apriori. Его автором является Ракеш Агравал (Rakesh Agrawal, сейчас сотрудник Microsoft Research).
Алгоритм Apriori предназначен для поиска всех частых множеств признаков. Он является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх.
Алгоритм перебора следующий (источник): 
Основная особенность алгоритма — свойство антимонотонности (источник):
Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора <Хлеб, Масло, Молоко>будет всегда меньше или равна поддержке 2-элементных наборов <Хлеб, Масло>, <Хлеб, Молоко>, <Масло, Молоко>. Дело в том, что любая транзакция, содержащая <Хлеб, Масло, Молоко>, также должна содержать <Хлеб, Масло>, <Хлеб, Молоко>, <Масло, Молоко>, причем обратное не верно.
Благодаря этому свойству перебор не является «жадным» и позволяет обрабатывать большие массивы информации за секунды.
Классический алгоритм apriori уже был несколько раз модифицирован, работы по улучшению скорости ведутся и сейчас.
Методы поиска ассоциативных правил
В этой лекции мы подробно рассмотрим следующие вопросы:
Часто встречающиеся приложения с применением ассоциативных правил:
Введение в ассоциативные правила
Впервые задача поиска ассоциативных правил ( association rule mining) была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis ).
Транзакции являются достаточно характерными операциями, ими, например, могут описываться результаты посещений различных магазинов.
| TID | Приобретенные покупки |
|---|---|
| 100 | хлеб, молоко, печенье |
| 200 | Молоко, сметана |
| 300 | Молоко, хлеб, сметана, печенье |
| 400 | Колбаса, сметана |
| 500 | Хлеб, молоко, печенье, сметана |
На основе имеющейся базы данных нам нужно найти закономерности между событиями, то есть покупками.
Методы поиска ассоциативных правил
Пример решения задачи поиска ассоциативных правил
Рассмотрим процесс построения ассоциативных правил в аналитическом пакете Deductor.
Далее вызываем мастер обработки и выбираем метод » Ассоциативные правила «. На втором шаге мастера проверяем назначения исходных столбцов данных, они должны иметь тип » ID » и «элемент».
На следующем шаге для просмотра полученных результатов предлагается выбрать визуализаторы из списка; мы выберем такие: «Популярные наборы», «Правила», » Дерево правил», «Что-если». Рассмотрим, что они из себя представляют.
| N | Множество |  Поддержка | |
|---|---|---|---|
| % | Кол-во | ||
| 6 | ХЛЕБ И БУЛКИ | 54,55 | 24 |
| 3 | МАСЛО | 52,27 | 23 |
| 5 | СОКИ | 50,00 | 22 |
| 10 | МАСЛО И ХЛЕБ И БУЛКИ | 45,45 | 20 |
| 4 | МОЛОКО | 43,18 | 19 |
| 2 | КЕФИР | 31,82 | 14 |
| 1 | ЙОГУРТЫ | 31,82 | 14 |
| 12 | СОКИ И ХЛЕБ И БУЛКИ | 22,73 | 10 |
| 11 | МОЛОКО И ХЛЕБ И БУЛКИ | 22,73 | 10 |
| 8 | МАСЛО И МОЛОКО | 22,73 | 10 |
| 7 | ЙОГУРТЫ И КЕФИР | 22,73 | 10 |
| 13 | МАСЛО И МОЛОКО И ХЛЕБ И БУЛКИ | 20,45 | 9 |
| 9 | МАСЛО И СОКИ | 20,45 | 9 |
Визуализатор «Правила»
| N | Условие | Следствие | Поддержка | Достоверность, % | |
|---|---|---|---|---|---|
| % | Кол-во | ||||
| 1 | ЙОГУРТЫ | КЕФИР | 22,73 | 10 | 71,43 |
| 2 | КЕФИР | ЙОГУРТЫ | 22,73 | 10 | 71,43 |
| 3 | МАСЛО | МОЛОКО | 22,73 | 10 | 43,48 |
| 4 | МОЛОКО | МАСЛО | 22,73 | 10 | 52,63 |
| 5 | СОКИ | МАСЛО | 20,45 | 9 | 40,91 |
| 6 | МАСЛО | ХЛЕБ И БУЛКИ | 45,45 | 20 | 86,96 |
| 7 | ХЛЕБ И БУЛКИ | МАСЛО | 45,45 | 20 | 83,33 |
| 8 | МОЛОКО | ХЛЕБ И БУЛКИ | 22,73 | 10 | 52,63 |
| 9 | ХЛЕБ И БУЛКИ | МОЛОКО | 22,73 | 10 | 41,67 |
| 10 | СОКИ | ХЛЕБ И БУЛКИ | 22,73 | 10 | 45,45 |
| 11 | ХЛЕБ И БУЛКИ | СОКИ | 22,73 | 10 | 41,67 |
| 12 | МАСЛО И МОЛОКО | ХЛЕБ И БУЛКИ | 20,45 | 9 | 90,00 |
| 13 | МАСЛО И ХЛЕБ И БУЛКИ | МОЛОКО | 20,45 | 9 | 45,00 |
| 14 | МОЛОКО И ХЛЕБ И БУЛКИ | МАСЛО | 20,45 | 9 | 90,00 |
| 15 | МОЛОКО | МАСЛО И ХЛЕБ И БУЛКИ | 20,45 | 9 | 47,37 |
При большом количестве найденных правил и широком ассортименте товаров анализировать полученные правила достаточно сложно. Для удобства анализа таких наборов правил предлагаются визуализаторы «Дерево правил» и «Что-если».
Визуализатор «что-если» удобен, если нам необходимо ответить на вопрос, какие следствия могут получиться из данного условия.
Рассмотренный пример поиска ассоциативных правил является типичной иллюстрацией задачи анализа покупательской корзины. В результате ее решения определяются часто встречающиеся наборы товаров, а также наборы товаров, совместно приобретаемые покупателями. Найденные правила могут быть использованы для решения различных задач, в частности для размещения товаров на прилавках магазинов, предоставления скидок на пары товаров для повышения объема продаж и, следовательно, прибыли и других задач.
Введение в анализ ассоциативных правил
Объемы современных баз данных, которые весьма внушительны, вызвали устойчивый спрос на новые масштабируемые алгоритмы анализа данных. Одним из популярных методов обнаружения знаний стали алгоритмы поиска ассоциативных правил. Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила, служит утверждение, что покупатель, приобретающий «Хлеб», приобретет и «Молоко» с вероятностью 75%.
Внушительные объемы современных баз данных вызвали устойчивый спрос на новые масштабируемые алгоритмы анализа данных. Одним из популярных методов обнаружения знаний стали алгоритмы поиска ассоциативных правил.
Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила служит утверждение, что покупатель, приобретающий «Хлеб», приобретет и «Молоко» с вероятностью 75%. Первый алгоритм поиска ассоциативных правил был разработан в 1993 году сотрудниками исследовательского центра IBM Almaden и назывался AIS [1]. С этой пионерской работы возрос интерес к ассоциативным правилам. На середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появлялось по несколько алгоритмов.
Ассоциативные правила (Association Rules)
Впервые задача поиска ассоциативных правил была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).
Пусть имеется база данных, состоящая из покупательских транзакций. Каждая транзакция — это набор товаров, купленных покупателем за один визит. Такую транзакцию еще называют рыночной корзиной.
Покажем на конкретном примере: 75% транзакций, содержащих хлеб, также содержат молоко. 3% от общего числа всех транзакций содержат оба товара». 75% — это достоверность (confidence) правила, 3% это поддержка (support), или «Хлеб» «Молоко» с вероятностью 75%.
Задача нахождения ассоциативных правил разбивается на две подзадачи:
Один из первых алгоритмов, эффективно решающих подобный класс задач, — это алгоритм APriori [2]. Кроме него были разработаны и другие алгоритмы: DHP[5], Partition[6], DIC[7] и другие.
Значения для параметров минимальная поддержка и минимальная достоверность выбираются таким образом, чтобы ограничить количество найденных правил. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитикам или настолько очевидные, что нет никакого смысла проводить такой анализ.
С другой стороны, низкое значение поддержки ведет к генерации огромного количества правил, что, конечно, требует существенных вычислительных ресурсов. Тем не менее, большинство интересных правил находится именно при низком значении порога поддержки. Хотя слишком низкое значение поддержки ведет к генерации статистически необоснованных правил.
Поиск ассоциативных правил совсем не тривиальная задача, как может показаться на первый взгляд. Одна из проблем — алгоритмическая сложность при нахождении часто встречающихся наборов элементов, т.к. с ростом числа элементов в I (| I |) экспоненциально растет число потенциальных наборов элементов.
Обобщенные ассоциативные правила (Generalized Association Rules)
При поиске ассоциативных правил мы предполагали, что все анализируемые элементы однородны. Возвращаясь к анализу рыночной корзины, это товары, имеющие совершенно одинаковые атрибуты, за исключением названия. Однако не составит большого труда дополнить транзакцию информацией о том, в какую товарную группу входит товар и построить иерархию товаров. Приведем пример такой группировки (таксономии) в виде иерархической модели.
Пример иерахической модели
Пусть нам дана база транзакций D и известно в какие группы (таксоны) входят элементы. Тогда можно извлекать из данных правила, связывающие группы с группами, отдельные элементы с группами и т.д.
Например, если Покупатель купил товар из группы «Безалкогольные напитки», то он купит и товар из группы «Молочные продукты» или «Сок» «Молочные продукты». Эти правила носят название обобщенных ассоциативных правил.
Введение дополнительной информации о группировке элементов в виде иерархии даст следующие преимущества:
Для нахождения таких правил можно использовать любой из вышеназванных алгоритмов. Для этого каждую транзакцию нужно дополнить всеми предками каждого элемента, входящего в транзакцию. Однако, применение «в лоб» этих алгоритмов неизбежно приведет к следующим проблемам:
Для нахождения обобщенных ассоциативных правил желательно использование специализированного алгоритма[3], который устраняет вышеописанные проблемы и к тому же работает в 2-5 раз быстрее, чем стандартный APriori.
Группировать элементы можно не только по вхождению в определенную товарную группу, но и по другим характеристикам, например по цене (дешево, дорого), брэнду и т.д.
Численные ассоциативные правила (Quantitative Association Rules)
При поиске ассоциативных правил задача была существенно упрощена. По сути все сводилось к тому, присутствует в транзакции элемент или нет. Т.е. если рассматривать случай рыночной корзины, то мы рассматривали два состояния: куплен товар или нет, проигнорировав, например, информацию о том, сколько было куплено, кто купил, характеристики покупателя и т.д. И можно сказать, что рассматривали «булевские» ассоциативные правила. Если взять любую базу данных, каждая транзакция состоит из различных типов данных: числовых, категориальных и т.д. Для обработки таких записей и извлечения численных ассоциативных правил был предложен алгоритм поиска [4].
Пример численного ассоциативного правила: [Возраст: 30-35] и [Семейное положение: женат] [Месячный доход: 1000-1500 тугриков].
Помимо описанных выше ассоциативных правил существуют косвенные ассоциативные правила, ассоциативные правила c отрицанием, временные ассоциативные правила для событий связанных во времени и другие.
Как было сказано, задача поиска ассоциативных правил впервые была представлена для анализа рыночной корзины. Ассоциативные правила эффективно используются в сегментации покупателей по поведению при покупках, анализе предпочтений клиентов, планировании расположения товаров в супермаркетах, кросс-продажах, адресной рассылке. Однако, сфера применения этих алгоритмов не ограничивается лишь одной торговлей. Их также успешно применяют и в других областях: медицине, для анализа посещений веб-страниц (Web Mining), для анализа текста (Text Mining), для анализа данных по переписи населения[7], в анализе и прогнозировании сбоев телекоммуникационного оборудования и т.д.
Методы поиска ассоциативных правил
Часто встречающиеся шаблоны или образцы
Допустим, имеется транзакционная база данных D. Присвоим значениям товаров переменные (таблица 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 |
Рассмотрим набор товаров (Itemset), включающий, например, <Хлеб, молоко, печенье>. Выразим этот набор с помощью переменных:
Поддержка
Этот набор товаров встречается в нашей базе данных три раза, т.е. поддержка этого набора товаров равна 3:
Поддержку иногда также называют обеспечением набора.
Таким образом, набор представляет интерес, если его поддержка выше определенного пользователем минимального значения ( min support ). Эти наборы называют часто встречающимися (frequent).
Характеристики ассоциативных правил
Ассоциативное правило имеет вид: «Из события A следует событие B».
Основными характеристиками ассоциативного правила являются поддержка и достоверность правила.
Правило имеет поддержку s, если s% транзакций из всего набора содержат одновременно наборы элементов A и B или, другими словами, содержат оба товара.
Достоверность правила показывает, какова вероятность того, что из события A следует событие B.
Границы поддержки и достоверности ассоциативного правила
Если уровень достоверности слишком мал, то ценность правила вызывает серьезные сомнения. Например, правило с достоверностью в 3% только условно можно назвать правилом.