В продолжении темы о Data Mining поговорим о том, с чего все начиналось. А начиналось все с анализа рыночной корзины (market basket analysis).
Из глоссария BaseGroup:
Анализ рыночной корзины — процесс поиска наиболее типичных шаблонов покупок в супермаркетах. Он производится путем анализа баз данных транзакций с целью определения комбинаций товаров, связанных между собой. Иными словами, выполняется обнаружение товаров, наличие которых в транзакции влияет на вероятность появления других товаров или их комбинаций.
Результаты, полученные с помощью анализа рыночной корзины, позволяют оптимизировать ассортимент товаров и запасы, размещение их в торговых залах, увеличивать объемы продаж за счет предложения клиентам сопутствующих товаров. Например, если в результате анализа будет установлено, что совместная покупка макарон и кетчупа является типичным шаблоном, то разместив эти товары на одной и той же витрине можно «спровоцировать» покупателя на их совместное приобретение.
Для решения задачи анализа рыночной корзины используются ассоциативные правила вида «если… то...». Например, «если клиент купил пиво, то он купит и чипсы». Каждая покупка именуется «транзакцией», на основании большего набора таких транзакций и строят исследования поведения клиента.
Ассоциативные правила являются очень простой и удобной формой записи знаний. Еще раз хочу уточнить, что информация о транзакциях является исходными данными, а вот полученные ассоциативные правила являются теми знаниями, которые помогли в 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 ).
Например: «75% транзакций, содержащих хлеб, также содержат молоко. 3% от общего числа всех транзакций содержат оба товара». 75% – это достоверность (confidence) правила, 3% — это поддержка (support), или «Хлеб» -> «Молоко» с вероятностью 75% и поддержкой 3%.
Как правило, очевидные правила имеют поддержку и достоверность высокую (60% и больше), но не являются знаниями де-факто. Основное внимание необходимо уделять правилам, имеющим поддержку 5-10%, именно они могут стать источником идеи промоакции или услуги.
Основным алгоритмом, который применяется для получения ассоциативных правил, является алгоритм apriori. Его автором является Ракеш Агравал (Rakesh Agrawal, сейчас сотрудник Microsoft Research).
Алгоритм Apriori предназначен для поиска всех частых множеств признаков. Он является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх.
Алгоритм перебора следующий (источник):
Основная особенность алгоритма — свойство антимонотонности (источник):
Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора {Хлеб, Масло, Молоко} будет всегда меньше или равна поддержке 2-элементных наборов {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}. Дело в том, что любая транзакция, содержащая {Хлеб, Масло, Молоко}, также должна содержать {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}, причем обратное не верно.
Благодаря этому свойству перебор не является «жадным» и позволяет обрабатывать большие массивы информации за секунды.
Классический алгоритм apriori уже был несколько раз модифицирован, работы по улучшению скорости ведутся и сейчас.
Кроме apriori используются и другие алгоритмы:
Классическая задача анализа рыночной корзины трансформировалась в новые задачи, которые нужно решать в наше время, а именно:
Из глоссария BaseGroup:
Анализ рыночной корзины — процесс поиска наиболее типичных шаблонов покупок в супермаркетах. Он производится путем анализа баз данных транзакций с целью определения комбинаций товаров, связанных между собой. Иными словами, выполняется обнаружение товаров, наличие которых в транзакции влияет на вероятность появления других товаров или их комбинаций.
Результаты, полученные с помощью анализа рыночной корзины, позволяют оптимизировать ассортимент товаров и запасы, размещение их в торговых залах, увеличивать объемы продаж за счет предложения клиентам сопутствующих товаров. Например, если в результате анализа будет установлено, что совместная покупка макарон и кетчупа является типичным шаблоном, то разместив эти товары на одной и той же витрине можно «спровоцировать» покупателя на их совместное приобретение.
Ассоциативные правила
Для решения задачи анализа рыночной корзины используются ассоциативные правила вида «если… то...». Например, «если клиент купил пиво, то он купит и чипсы». Каждая покупка именуется «транзакцией», на основании большего набора таких транзакций и строят исследования поведения клиента.
Ассоциативные правила являются очень простой и удобной формой записи знаний. Еще раз хочу уточнить, что информация о транзакциях является исходными данными, а вот полученные ассоциативные правила являются теми знаниями, которые помогли в 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 ).
Например: «75% транзакций, содержащих хлеб, также содержат молоко. 3% от общего числа всех транзакций содержат оба товара». 75% – это достоверность (confidence) правила, 3% — это поддержка (support), или «Хлеб» -> «Молоко» с вероятностью 75% и поддержкой 3%.
Как правило, очевидные правила имеют поддержку и достоверность высокую (60% и больше), но не являются знаниями де-факто. Основное внимание необходимо уделять правилам, имеющим поддержку 5-10%, именно они могут стать источником идеи промоакции или услуги.
Алгоритм Apriori
Основным алгоритмом, который применяется для получения ассоциативных правил, является алгоритм apriori. Его автором является Ракеш Агравал (Rakesh Agrawal, сейчас сотрудник Microsoft Research).
Алгоритм Apriori предназначен для поиска всех частых множеств признаков. Он является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх.
Алгоритм перебора следующий (источник):
Основная особенность алгоритма — свойство антимонотонности (источник):
Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора {Хлеб, Масло, Молоко} будет всегда меньше или равна поддержке 2-элементных наборов {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}. Дело в том, что любая транзакция, содержащая {Хлеб, Масло, Молоко}, также должна содержать {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}, причем обратное не верно.
Благодаря этому свойству перебор не является «жадным» и позволяет обрабатывать большие массивы информации за секунды.
Классический алгоритм apriori уже был несколько раз модифицирован, работы по улучшению скорости ведутся и сейчас.
Кроме apriori используются и другие алгоритмы:
- Eclat algorithm
- FP-Growth algorithm
- One-attribute-rule
- Zero-attribute-rule
Решение других задач
Классическая задача анализа рыночной корзины трансформировалась в новые задачи, которые нужно решать в наше время, а именно:
- анализ покупок с помощью кредитных карточек
- анализ шаблонов телефонных звонков (telephone calling patterns)
- и др., связанных с анализом и выявлением мошеннических операций в какой-то области
Программные реализации
- Реализация на C#
- Несколько реализаций на codeplex: Data Mining Source Code
Литература
- Apriori — масштабируемый алгоритм поиска ассоциативных правил
- Agrawal R, Imielinski T, Swami AN. «Mining Association Rules between Sets of Items in Large Databases.» SIGMOD. June 1993, 22(2):207-16
- Market Basket Analysis
- Apriori algorithm
- Apriori algorithm source code
- Data Mining Source Code на codeplex
