Обобщенные ассоциативные правила

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

Рисунок 1.1 — Иерархическая модель товарных групп

Пусть нам дана база транзакций и известно в какие группы (таксоны) входят элементы. Тогда можно извлекать из данных правила, связывающие группы с группами, отдельные элементы с группами и т. д. Правила, которые собирают несколько ассоциативных правил вместе, называются мультиуровневые или обобщенные ассоциативные правила (Multilevel or Generalized Association Rules). Например, если Покупатель купил товар из группы "Безалкогольные напитки", то он купит и товар из группы "Молочные продукты" или "Сок"->"Молочные продукты".

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

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

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

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

a) Элементы на верхних уровнях иерархии стремятся к значительно большим значениям поддержки по сравнению с элементами на нижних уровнях.

b) С добавлением в транзакции групп увеличилось количество атрибутов и соответственно размерность входного пространства. Это усложняет задачу, а также ведет к генерации большего количества правил.

c) Появление избыточных правил, противоречащих определению обобщенного ассоциативного правила, например, "Сок"=>"Прохладительные напитки". Очевидно, что практическая ценность такого "открытия" нулевая при 100% достоверности. Следовательно, нужны специальные операторы, удаляющие подобные избыточные правила.

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

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

Другие виды ассоциативных правил

Среди булевых асссоциативных правил, которые сообщают только о наличии или отсутствии ассоциации, следует обратить внимание на использование моделей для поиска негативных ассоциативных правил [8]. Негативное (отрицательное) правило – это такое правило, которое предсказывает отсутствие набора Y: X => не Y. Использование таких правил увеличивает количество ассоциативных правил. Правда, на практике такие правила не всегда применимы. Например, правило: "если (вода, масло), то не (молоко)" мало полезно, т.к. слабо выражает поведение покупателя.

Более сложным типом правил являются количественные ассоциативные правила (Quantitative Association Rules). Этот тип правил ищется с применением количественных или категориальных атрибутов. Например, "покупатели, чей возраст находится между 30 и 35 годами с доходом более 75000 долларов в год покупают машины стоимостью более 20000 долларов".

Если взять любую базу данных, каждая транзакция состоит из различных типов данных: числовых, категориальных и т.д. Для обработки таких записей и извлечения численных ассоциативных правил был предложен алгоритм поиска [9].