Цели и задачи анализа ассоциаций
Целью анализа ассоциаций является установление следующих зависимостей: если в транзакции встретился некоторый набор элементов X, то на основании этого можно сделать вывод о том, что другой набор элементов Y также же должен появиться в этой транзакции с определенной вероятностью. Установление таких зависимостей дает нам возможность находить очень простые и интуитивно понятные правила.
В общем случае, количество ассоциативных правил может быть очень большим и трудновоспринимаемым для человека. К тому же, не все из построенных правил несут в себе полезную информацию.
Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил X => Y, причем поддержка и достоверность этих правил должны быть выше некоторых наперед определенных порогов, называемых соответственно минимальной поддержкой (minsupport) и минимальной достоверностью (minconfidence).
Задача нахождения ассоциативных правил разбивается на две подзадачи [5]:
Нахождение всех наборов элементов, которые удовлетворяют порогу minsupport. Такие наборы элементов называются часто встречающимися (frequent itemsets).
Генерация правил из наборов элементов, найденных согласно п.1 с достоверностью, удовлетворяющей порогу minconfidence.
Значения для параметров минимальная поддержка и минимальная достоверность выбираются таким образом, чтобы ограничить количество найденных правил. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитикам или настолько очевидные, что нет никакого смысла проводить такой анализ. С другой стороны, низкое значение поддержки ведет к генерации огромного количества правил, что, конечно, требует существенных вычислительных ресурсов. Тем не менее, большинство интересных правил находится именно при низком значении порога поддержки. Хотя слишком низкое значение поддержки ведет к генерации статистически необоснованных правил.
Аналитик при поиске ассоциативных правил задает минимальные значения перечисленных величин. В результате те правила, которые не удовлетворяют этим условиям, отбрасываются и не включаются в решение задачи. С этой точки зрения нельзя объединять разные правила, хотя и имеющие общую смысловую нагрузку.
Например, следующие правила:
X = { a ,b } => Y = { c } , X= { a ,b }=> Y = { d } ,
нельзя объединить в одно:
X = { a,b } => Y = {c ,d } ,
т.к. достоверности их будут разные, следовательно, некоторые из них могут быть исключены, а некоторые – нет.
Поиск ассоциативных правил совсем не тривиальная задача, как может показаться на первый взгляд. Одна из проблем – алгоритмическая сложность при нахождении часто встречающих наборов элементов, т.к. с ростом числа элементов рыночной корзины экспоненциально растет число потенциальных наборов элементов.
Обобщенные ассоциативные правила
При поиске ассоциативных правил мы предполагали, что все анализируемые элементы однородны. Возвращаясь к анализу рыночной корзины, это товары, имеющие совершенно одинаковые атрибуты, за исключением названия. Однако не составит большого труда дополнить транзакцию информацией о том, в какую товарную группу входит товар и построить иерархию товаров. Приведем пример такой группировки (таксономии) в виде иерархической модели на рис 1.1.
Рисунок 1.1 — Иерархическая модель товарных групп
Пусть нам дана база транзакций и известно в какие группы (таксоны) входят элементы. Тогда можно извлекать из данных правила, связывающие группы с группами, отдельные элементы с группами и т. д. Правила, которые собирают несколько ассоциативных правил вместе, называются мультиуровневые или обобщенные ассоциативные правила (Multilevel or Generalized Association Rules). Например, если Покупатель купил товар из группы "Безалкогольные напитки", то он купит и товар из группы "Молочные продукты" или "Сок"->"Молочные продукты".
Введение дополнительной информации о группировке элементов в виде иерархии даст следующие преимущества [5]:
Это помогает установить ассоциативные правила не только между отдельными элементами, но и между различными уровнями иерархии (группами).
Отдельные элементы могут иметь недостаточную поддержку, но в целом группа может удовлетворять порогу minsupport.
Для нахождения таких правил каждую транзакцию нужно дополнить всеми предками каждого элемента, входящего в транзакцию. Однако, применение "в лоб" алгоритмов поиска ассоциаций неизбежно приведет к следующим проблемам:
Элементы на верхних уровнях иерархии стремятся к значительно большим значениям поддержки по сравнению с элементами на нижних уровнях.
С добавлением в транзакции групп увеличилось количество атрибутов и соответственно размерность входного пространства. Это усложняет задачу, а также ведет к генерации большего количества правил.
Появление избыточных правил, противоречащих определению обобщенного ассоциативного правила, например, "Сок"=>"Прохладительные напитки". Очевидно, что практическая ценность такого "открытия" нулевая при 100% достоверности. Следовательно, нужны специальные операторы, удаляющие подобные избыточные правила.
Для нахождения обобщенных ассоциативных правил желательно использование специализированного алгоритма[6], который устраняет вышеописанные проблемы и к тому же работает в 2-5 раз быстрее, чем стандартный алгоритм поиска ассоциаций Apriori [7].
Группировать элементы можно не только по вхождению в определенную товарную группу, но и по другим характеристикам, например по цене (дешево, дорого), брэнду и т.д.