Объемы современных баз данных, которые весьма внушительны, вызвали устойчивый спрос на новые масштабируемые алгоритмы анализа данных. Одним из популярных методов обнаружения знаний стали алгоритмы поиска ассоциативных правил. Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила, служит утверждение, что покупатель, приобретающий «Хлеб», приобретет и «Молоко» с вероятностью 75%.
Внушительные объемы современных баз данных вызвали устойчивый спрос на новые масштабируемые алгоритмы анализа данных. Одним из популярных методов обнаружения знаний стали алгоритмы поиска ассоциативных правил.
Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила служит утверждение, что покупатель, приобретающий «Хлеб», приобретет и «Молоко» с вероятностью 75%. Первый алгоритм поиска ассоциативных правил был разработан в 1993 году сотрудниками исследовательского центра IBM Almaden и назывался AIS [1]. С этой пионерской работы возрос интерес к ассоциативным правилам. На середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появлялось по несколько алгоритмов.
Впервые задача поиска ассоциативных правил была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).
Пусть имеется база данных, состоящая из покупательских транзакций. Каждая транзакция — это набор товаров, купленных покупателем за один визит. Такую транзакцию еще называют рыночной корзиной.
Определение 1. Пусть I = \{i_1,\,i_2,\,i_3,\,\dots,\,i_n\} — множество (набор) товаров, называемых элементами. Пусть D — множество транзакций, где каждая транзакция T — это набор элементов из I, T\subseteq I. Каждая транзакция представляет собой бинарный вектор, где t[k]=1, если i_k элемент присутствует в транзакции, иначе t[k]=0. Мы говорим, что транзакция T содержит X, некоторый набор элементов из I, если X\subset T. Ассоциативным правилом называется импликация X\Rightarrow Y, где X\subset I, Y\subset I и X\cap Y=\oslash. Правило X⇒Y имеет поддержку s (support), если s% транзакций из D, содержат X\cup Y, supp(X\Rightarrow Y) = supp(X\cup Y). Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X⇒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 также же должен появиться в этой транзакции. Установление таких зависимостей дает нам возможность находить очень простые и интуитивно понятные правила.
Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил XY, причем поддержка и достоверность этих правил должны быть выше некоторых наперед определенных порогов, называемых соответственно минимальной поддержкой (minsupport) и минимальной достоверностью (minconfidence).
Задача нахождения ассоциативных правил разбивается на две подзадачи:
Один из первых алгоритмов, эффективно решающих подобный класс задач, — это алгоритм APriori [2]. Кроме него были разработаны и другие алгоритмы: DHP[5], Partition[6], DIC[7] и другие.
Значения для параметров минимальная поддержка и минимальная достоверность выбираются таким образом, чтобы ограничить количество найденных правил. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитикам или настолько очевидные, что нет никакого смысла проводить такой анализ.
С другой стороны, низкое значение поддержки ведет к генерации огромного количества правил, что, конечно, требует существенных вычислительных ресурсов. Тем не менее, большинство интересных правил находится именно при низком значении порога поддержки. Хотя слишком низкое значение поддержки ведет к генерации статистически необоснованных правил.
Поиск ассоциативных правил совсем не тривиальная задача, как может показаться на первый взгляд. Одна из проблем — алгоритмическая сложность при нахождении часто встречающихся наборов элементов, т.к. с ростом числа элементов в I (| I |) экспоненциально растет число потенциальных наборов элементов.
При поиске ассоциативных правил мы предполагали, что все анализируемые элементы однородны. Возвращаясь к анализу рыночной корзины, это товары, имеющие совершенно одинаковые атрибуты, за исключением названия. Однако не составит большого труда дополнить транзакцию информацией о том, в какую товарную группу входит товар и построить иерархию товаров. Приведем пример такой группировки (таксономии) в виде иерархической модели.
Пример иерахической модели
Пусть нам дана база транзакций D и известно в какие группы (таксоны) входят элементы. Тогда можно извлекать из данных правила, связывающие группы с группами, отдельные элементы с группами и т.д.
Например, если Покупатель купил товар из группы «Безалкогольные напитки», то он купит и товар из группы «Молочные продукты» или «Сок» «Молочные продукты». Эти правила носят название обобщенных ассоциативных правил.
Определение 2. Обобщенным ассоциативным правилом называется импликация X \Rightarrow Y, где X \subset I, Y\subset I и X \cap Y=\oslash и где ни один из элементов, входящих в набор Y, не является предком ни одного элемента, входящего в X. Поддержка и достоверность подсчитываются так же, как и в случае ассоциативных правил (см. Определение 1).
Введение дополнительной информации о группировке элементов в виде иерархии даст следующие преимущества:
Для нахождения таких правил можно использовать любой из вышеназванных алгоритмов. Для этого каждую транзакцию нужно дополнить всеми предками каждого элемента, входящего в транзакцию. Однако, применение «в лоб» этих алгоритмов неизбежно приведет к следующим проблемам:
Для нахождения обобщенных ассоциативных правил желательно использование специализированного алгоритма[3], который устраняет вышеописанные проблемы и к тому же работает в 2-5 раз быстрее, чем стандартный APriori.
Группировать элементы можно не только по вхождению в определенную товарную группу, но и по другим характеристикам, например по цене (дешево, дорого), брэнду и т.д.
При поиске ассоциативных правил задача была существенно упрощена. По сути все сводилось к тому, присутствует в транзакции элемент или нет. Т.е. если рассматривать случай рыночной корзины, то мы рассматривали два состояния: куплен товар или нет, проигнорировав, например, информацию о том, сколько было куплено, кто купил, характеристики покупателя и т.д. И можно сказать, что рассматривали «булевские» ассоциативные правила. Если взять любую базу данных, каждая транзакция состоит из различных типов данных: числовых, категориальных и т.д. Для обработки таких записей и извлечения численных ассоциативных правил был предложен алгоритм поиска [4].
Пример численного ассоциативного правила: [Возраст: 30-35] и [Семейное положение: женат] [Месячный доход: 1000-1500 тугриков].
Помимо описанных выше ассоциативных правил существуют косвенные ассоциативные правила, ассоциативные правила c отрицанием, временные ассоциативные правила для событий связанных во времени и другие.
Как было сказано, задача поиска ассоциативных правил впервые была представлена для анализа рыночной корзины. Ассоциативные правила эффективно используются в сегментации покупателей по поведению при покупках, анализе предпочтений клиентов, планировании расположения товаров в супермаркетах, кросс-продажах, адресной рассылке. Однако, сфера применения этих алгоритмов не ограничивается лишь одной торговлей. Их также успешно применяют и в других областях: медицине, для анализа посещений веб-страниц (Web Mining), для анализа текста (Text Mining), для анализа данных по переписи населения[7], в анализе и прогнозировании сбоев телекоммуникационного оборудования и т.д.
Другие материалы по теме:
Выявление обобщенных ассоциативных правил
Apriori - масштабируемый алгоритм поиска ассоциативных правил
«Ситилинк» задействует Loginom в управлении товарными запасами
Поиск последовательных шаблонов| Часть 1
