Вход
Регистрация

Введение в анализ ассоциативных правил

Пятачок, я все понял! Это неправильные пчелы, совсем неправильные. И, наверное, они делают неправильный мед.
Винни Пух

В последнее время неуклонно растет интерес к методам "обнаружения знаний в базах данных" (knowledge discovery in databases). Объемы современных баз данных, которые весьма внушительны, вызвали устойчивый спрос на новые масштабируемые алгоритмы анализа данных. Одним из популярных методов обнаружения знаний стали алгоритмы поиска ассоциативных правил.

Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила, служит утверждение, что покупатель, приобретающий "Хлеб", приобретет и "Молоко" с вероятностью 75%. Первый алгоритм поиска ассоциативных правил, называвшийся AIS [1] был разработан в 1993 году сотрудниками исследовательского центра IBM Almaden. С этой пионерской работы возрос интерес к ассоциативным правилам; на середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появлялось по несколько алгоритмов.

Ассоциативные правила (Association Rules)

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

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

Определение 1. Пусть $I = \{i_1,\,i_2,\,i_3,\,\dots,\,i_n\}$ - множество (набор) товаров, называемых элементами. Пусть D - множество транзакций, где каждая транзакция T – это набор элементов из I, T$\subseteq$ I. Каждая транзакция представляет собой бинарный вектор, где t[k]=1, если ik элемент присутствует в транзакции, иначе t[k]=0. Мы говорим, что транзакция T содержит X, некоторый набор элементов из I, если X$\subset$T. Ассоциативным правилом называется импликация X$\Rightarrow$Y, где X$\subset$I, Y$\subset$I и X$\cap$Y=$\oslash$. Правило X$\Rightarrow$Y имеет поддержку s (support), если s% транзакций из D, содержат X$\cup$Y, supp(X$\Rightarrow$Y) = supp(X$\cup$Y). Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X$\Rightarrow$Y справедливо с достоверностью (confidence) c, если c% транзакций из D, содержащих X, также содержат Y, conf(X$\Rightarrow$Y) = supp(X$\cup$Y)/supp(X ).

Покажем на конкретном примере: "75% транзакций, содержащих хлеб, также содержат молоко. 3% от общего числа всех транзакций содержат оба товара". 75% - это достоверность (confidence) правила, 3% это поддержка (support), или "Хлеб" "Молоко" с вероятностью 75%.

Другими словами, целью анализа является установление следующих зависимостей: если в транзакции встретился некоторый набор элементов X, то на основании этого можно сделать вывод о том, что другой набор элементов Y также же должен появиться в этой транзакции. Установление таких зависимостей дает нам возможность находить очень простые и интуитивно понятные правила.

Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил X Y, причем поддержка и достоверность этих правил должны быть выше некоторых наперед определенных порогов, называемых соответственно минимальной поддержкой (minsupport) и минимальной достоверностью (minconfidence).

Задача нахождения ассоциативных правил разбивается на две подзадачи:

  1. Нахождение всех наборов элементов, которые удовлетворяют порогу minsupport. Такие наборы элементов называются часто встречающимися.
  2. Генерация правил из наборов элементов, найденных согласно п.1. с достоверностью, удовлетворяющей порогу minconfidence.

Один из первых алгоритмов, эффективно решающих подобный класс задач, – это алгоритм APriori [2]. Кроме этого алгоритма в последнее время был разработан ряд других алгоритмов: DHP[5], Partition[6], DIC[7] и другие.

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

Поиск ассоциативных правил совсем не тривиальная задача, как может показаться на первый взгляд. Одна из проблем - алгоритмическая сложность при нахождении часто встречающих наборов элементов, т.к. с ростом числа элементов в I (| I |) экспоненциально растет число потенциальных наборов элементов.

Обобщенные ассоциативные правила (Generalized Association Rules)

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

Пусть нам дана база транзакций D и известно в какие группы (таксоны) входят элементы. Тогда можно извлекать из данных правила, связывающие группы с группами, отдельные элементы с группами и т.д.

Например, если Покупатель купил товар из группы "Безалкогольные напитки", то он купит и товар из группы "Молочные продукты" или "Сок" "Молочные продукты". Эти правила носят название обобщенных ассоциативных правил.

Определение 2. Обобщенным ассоциативным правилом называется импликация X $\Rightarrow$ Y, где X $\subset$ I, Y$\subset$I и X $\cap$Y=$\oslash$ и где ни один из элементов, входящих в набор Y, не является предком ни одного элемента, входящего в X. Поддержка и достоверность подсчитываются так же, как и в случае ассоциативных правил (см. Определение 1).

Введение дополнительной информации о группировке элементов в виде иерархии даст следующие преимущества:

  1. Это помогает установить ассоциативные правила не только между отдельными элементами, но и между различными уровнями иерархии (группами).
  2. Отдельные элементы могут иметь недостаточную поддержку, но в целом группа может удовлетворять порогу minsupport.

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

  1. Элементы на верхних уровнях иерархии стремятся к значительно большим значениям поддержки по сравнению с элементами на нижних уровнях.
  2. С добавлением в транзакции групп увеличилось количество атрибутов и соответственно размерность входного пространства. Это усложняет задачу, а также ведет к генерации большего количества правил.
  3. Появление избыточных правил, противоречащих определению обобщенного ассоциативного правила, например, "Сок" "Прохладительные напитки". Очевидно, что практическая ценность такого "открытия" нулевая при 100% достоверности. Следовательно, нужны специальные операторы, удаляющие подобные избыточные правила.

Для нахождения обобщенных ассоциативных правил желательно использование специализированного алгоритма[3], который устраняет вышеописанные проблемы и к тому же работает в 2-5 раз быстрее, чем стандартный APriori.

Группировать элементы можно не только по вхождению в определенную товарную группу, но и по другим характеристикам, например по цене (дешево, дорого), брэнду и т.д.

Численные ассоциативные правила (Quantitative Association Rules)

При поиске ассоциативных правил задача была существенно упрощена. По сути все сводилось к тому, присутствует в транзакции элемент или нет. Т.е. если рассматривать случай рыночной корзины, то мы рассматривали два состояния: куплен товар или нет, проигнорировав, например, информацию о том, сколько было куплено, кто купил, характеристики покупателя и т.д. И можно сказать, что рассматривали "булевские" ассоциативные правила. Если взять любую базу данных, каждая транзакция состоит из различных типов данных: числовых, категориальных и т.д. Для обработки таких записей и извлечения численных ассоциативных правил был предложен алгоритм поиска [4].

Пример численного ассоциативного правила: [Возраст: 30-35] и [Семейное положение: женат] [Месячный доход: 1000-1500 тугриков].

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

Как было сказано, задача поиска ассоциативных правил впервые была представлена для анализа рыночной корзины. Ассоциативные правила эффективно используются в сегментации покупателей по поведению при покупках, анализе предпочтений клиентов, планировании расположения товаров в супермаркетах, кросс-маркетинге, адресной рассылке. Однако, сфера применения этих алгоритмов не ограничивается лишь одной торговлей. Их также успешно применяют и в других областях: медицине, для анализа посещений веб-страниц (Web Mining), для анализа текста (Text Mining), для анализа данных по переписи населения[7], в анализе и прогнозировании сбоев телекоммуникационного оборудования и т.д.

В следующей статье из цикла статей посвященных "Ассоциативным правилам" мы опишем принципы работы алгоритма APriori.

Литература
  • R. Agrawal, T. Imielinski, A. Swami. 1993. Mining Associations between Sets of Items in Massive Databases. In Proc. of the 1993 ACM-SIGMOD Int’l Conf. on Management of Data, 207-216.
  • R. Agrawal, R. Srikant. "Fast Discovery of Association Rules", In Proc. of the 20th International Conference on VLDB, Santiago, Chile, September 1994.
  • R. Srikant, R. Agrawal. "Mining Generalized Association Rules", In Proc. of the 21th International Conference on VLDB, Zurich, Switzerland, 1995.
  • R. Srikant, R. Agrawal. "Mining quantitative association rules in large relational tables". In Proceedings of the ACM SIGMOD Conference on Management of Data, Montreal, Canada, June 1996.
  • A. Savasere, E. Omiecinski, and S. Navathe, "An Efficient Algorithm for Mining Association Rules in Large Databases", In Proc. 21st Int’l Conf. Very Large Data Bases, Morgan Kaufmann, San Francisco, 1995.
  • J.S. Park, M.-S. Chen, and S.Y. Philip, "An Effective HashBased Algorithm for Mining Association Rules", In Proc. ACM SIGMOD Int’l Conf. Management of Data, ACM Press, New York, 1995.
  • S. Brin et al., "Dynamic Itemset Counting and Implication Rules for Market Basket Data", In Proc. ACM SIGMOD Int’l Conf. Management of Data, ACM Press, New York, 1997.
  • J. Hipp, U. Guntzer, and G. Nakaeizadeh. Algorithms for Association Rule Mining – A General Survey and Comparison. In Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000.