Цели и задачи анализа ассоциаций

Анализ ассоциаций

Одним из основных типов закономерностей, которые позволяют выявлять методы интеллектуального анализа данных, является ассоциация.

Ассоциация – закономерно возникающая связь между отдельными событиями, фактами, предметами или явлениями, отражёнными в реальности. При наличии ассоциативной связи между явлениями A и B возникновение явления A закономерным образом влечёт появление явления B.

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

Анализ рыночной корзины

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

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

Продавца интересуют ассоциации между различными товарами, которые покупатель складывает в корзину. Например, интерес может представлять вопрос, какова вероятность того, что покупатель, купивший хлеб, приобетет с ним и молоко? Какие товары обычно покупаются вместе?

Такая информация может помочь продавцам выработать маркетинговую или рекламную стратегию. Например, это поможет:

• эффективно расположить товары на территории супермаркета;

• разработать систему скидок на одни товары для того, чтобы стимулировать продажи других товаров;

• выбрать идею рекламы на товар, используя то, что этот товар обычно используется совместно с другим товаром.

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

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

Во многие учебники по бизнес-аналитике вошёл пример, когда система поиска ассоциативных правил обнаружила неочевидную закономерность: вечером перед выходными днями возрастают совместные продажи памперсов и пива. Разместив дорогие сорта пива рядом с памперсами, менеджеры смогли увеличить продажи в масштабах всей розничной сети, что окупило внедрение системы анализа данных. Позже маркетологи и социологи предложили разумное объяснение данному явлению, однако обнаружено оно было именно путём анализа данных.

Ассоциативные правила

В простейшей форме ассоциативные правила сообщают только о наличии или отсутствии ассоциации, что отражено в их названии – булевые ассоциативные правила (Boolean Association Rule) [3]. На примере корзины потребителя, "покупатели, которые приобретают снятое молоко так же приобретают масло с низким уровнем жира" – типичное булевое ассоциативное правило. Т.е. если рассматривать случай рыночной корзины, то мы рассматривали два состояния: куплен товар или нет, проигнорировав, например, информацию о том, сколько было куплено, кто купил, характеристики покупателя и т.д. Основным достоинством ассоциативных правил является их лёгкое восприятие человеком и простая интерпретация языками программирования. Однако, они не всегда полезны.

Выделяют три вида правил [4]:

а) полезные правила – содержат действительную информацию, которая ранее была неизвестна, но имеет логическое объяснение. Такие правила могут быть использованы для принятия решений, приносящих выгоду;

б) тривиальные правила – содержат действительную и легко объяснимую информацию, которая уже известна. Такие правила не могут принести пользу, т.к. отражают или известные законы в исследуемой области, или результаты прошлой деятельности. Иногда такие правила могут использоваться для проверки выполнения решений, принятых на основании предыдущего анализа;

в) непонятные правила – содержат информацию, которая не может быть объяснена. Такие правила могут быть получены на основе аномальных значений, или сугубо скрытых знаний. Напрямую такие правила нельзя использовать для принятия решений, т.к. их необъяснимость может привести к непредсказуемым результатам. Для лучшего понимания требуется дополнительный анализ.

Цели и задачи анализа ассоциаций

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

В общем случае, количество ассоциативных правил может быть очень большим и трудновоспринимаемым для человека. К тому же, не все из построенных правил несут в себе полезную информацию.

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

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

1. Нахождение всех наборов элементов, которые удовлетворяют порогу minsupport. Такие наборы элементов называются часто встречающимися (frequent itemsets).

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

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

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

Например, следующие правила:

X = { a ,b } => Y = { c } , X= { a ,b }=> Y = { d } ,

нельзя объединить в одно:

X = { a,b } => Y = {c ,d } ,

т.к. достоверности их будут разные, следовательно, некоторые из них могут быть исключены, а некоторые – нет.

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