Анализ рыночной корзины и ассоциативные правила

    В продолжении темы о 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


    Основным алгоритмом, который применяется для получения ассоциативных правил, является алгоритм apriori. Его автором является Ракеш Агравал (Rakesh Agrawal, сейчас сотрудник Microsoft Research).

    Алгоритм Apriori предназначен для поиска всех частых множеств признаков. Он является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх.

    Алгоритм перебора следующий (источник):
    image
    image

    Основная особенность алгоритма — свойство антимонотонности (источник):
    image

    Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора {Хлеб, Масло, Молоко} будет всегда меньше или равна поддержке 2-элементных наборов {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}. Дело в том, что любая транзакция, содержащая {Хлеб, Масло, Молоко}, также должна содержать {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}, причем обратное не верно.

    Благодаря этому свойству перебор не является «жадным» и позволяет обрабатывать большие массивы информации за секунды.
    Классический алгоритм apriori уже был несколько раз модифицирован, работы по улучшению скорости ведутся и сейчас.

    Кроме apriori используются и другие алгоритмы:
    • Eclat algorithm
    • FP-Growth algorithm
    • One-attribute-rule
    • Zero-attribute-rule
    Подробнее о них можно почитать здесь.

    Решение других задач


    Классическая задача анализа рыночной корзины трансформировалась в новые задачи, которые нужно решать в наше время, а именно:
    • анализ покупок с помощью кредитных карточек
    • анализ шаблонов телефонных звонков (telephone calling patterns)
    • и др., связанных с анализом и выявлением мошеннических операций в какой-то области

    Программные реализации



    Литература


    Поделиться публикацией

    Комментарии 11

      +2
      Вопрос раскрыт полностью. Отлично!
        0
        Большое спасибо!
        нашел на basegroup много полезной информации
          0
          А где практика применения?
            0
            Предыдущая статься этого блога:
            habrahabr.ru/blogs/data_mining/65647/
              0
              Вот тут в комментариях к статье, очень показательный пример.
              0
              а еще лучше услышать бы какие нибудь конкретные цифры об увеличении продаж после оптимизаций товарных полок…
              0
              Всем привет. Отличная статья. Как уже писал, отличный опыт ассоциативных правил (отсюда best offer) использует английский ритейл — Tesco. Для них многие фишки делает компания www.dunnhumby.com/
              Бизнес можно посмотреть там.
                0
                А не подскажете книги вообще по теме «Data Mining»
                  0
                  Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP

                  А.А. Барсегян, М.С. Куприянов, В.В. Степаненко, И.И. Холод. Методы и модели анализа данных: OLAP И Data Mining

                  Intuit.ru — курс Data Mining
                    0
                    спасибо
                      0
                      Чтобы не искать, прямая ссылка на курс Data Mining на intuit.ru.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое