Задача поиска ассоциативных правил

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

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

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

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

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

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

Определение 1. Пусть $I = $ — множество (набор) товаров, называемых элементами. Пусть 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 справедливо с достоверностью (conf >

Покажем на конкретном примере: «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.

Как уже упоминалось в первом разделе курса, ассоциация — одна из задач Data Mining . Целью поиска ассоциативных правил ( association rule ) является нахождение закономерностей между связанными событиями в базах данных.

В этой лекции мы подробно рассмотрим следующие вопросы:

  • Что такое ассоциативные правила ?
  • Какие существуют алгоритмы поиска ассоциативных правил ?
  • Что такое часто встречающиеся наборы товаров?
  • Применение задачи поиска ассоциативных правил ?

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

Часто встречающиеся приложения с применением ассоциативных правил:

  • розничная торговля: определение товаров, которые стоит продвигать совместно; выбор местоположения товара в магазине; анализ потребительской корзины; прогнозирование спроса;
  • перекрестные продажи: если есть информация о том, что клиенты приобрели продукты A, Б и В, то какие из них вероятнее всего купят продукт Г?
  • маркетинг: поиск рыночных сегментов, тенденций покупательского поведения;
  • сегментация клиентов: выявление общих характеристик клиентов компании, выявление групп покупателей;
  • оформление каталогов, анализ сбытовых кампаний фирмы, определение последовательностей покупок клиентов (какая покупка последует за покупкой товара А);
  • анализ Web-логов.

Приведем простой пример ассоциативного правила : покупатель , приобретающий банку краски, приобретет кисточку для краски с вероятностью 50%.

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

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

Рыночная корзина — это набор товаров, приобретенных покупателем в рамках одной отдельно взятой транзакции .

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

Транзакция — это множество событий , которые произошли одновременно.

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

Полученные в результате анализа шаблоны включают перечень товаров и число транзакций , которые содержат данные наборы.

Транзакционная или операционная база данных ( Transaction database ) представляет собой двумерную таблицу, которая состоит из номера транзакции ( TID ) и перечня покупок, приобретенных во время этой транзакции .

T >идентификатор , определяющий каждую сделку или транзакцию .

Пример транзакционной базы данных , состоящей из покупательских транзакций , приведен в таблице 15.1. В таблице первая колонка ( TID ) определяет номер транзакции , во второй колонке таблицы приведены товары, приобретенные во время определенной транзакции .

Таблица 15.1. Транзакционная база данных
TID Приобретенные покупки
100 хлеб, молоко, печенье
200 Молоко, сметана
300 Молоко, хлеб, сметана, печенье
400 Колбаса, сметана
500 Хлеб, молоко, печенье, сметана

На основе имеющейся базы данных нам нужно найти закономерности между событиями, то есть покупками.

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

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

Ассоциативное правило состоит из двух наборов предметов, называемых условие (англ: antecedent) и следствие (англ: consequent), записываемых в виде XY , что читается «из X следует Y». Таким образом, ассоциативное правило формулируется в виде «Если условие, то следствие».

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

Читайте также:  Как в ворде сделать сложение столбиком

Ассоциативные правила описывают связь между наборами предметов, соответствующим условию и следствию. Эта связь характеризуется двумя показателями — поддержкой (s) и достоверностью(с).

Правило «Из Х следует Y» имеет поддержку s, если s % транзакций из всего набора содержат наборы элементов Х и Y.

Достоверность правила показывает, какова вероятность того, что из X

следует Y. Правило «Из X следует Y» справедливо с достоверностью с,

если c % транзакций из всего множества, содержащих набор элементов X,

также содержат набор элементов Y.

Покажем на конкретном примере: пусть 75 % транзакций, содержащих хлеб, также содержат молоко, а 3 % от общего числа всех транзакций содержат оба товара. 75 % — это достоверность правила, а 3 % — это поддержка.

Лифт (L) — это отношение частоты появления условия в транзакциях, которые также содержат и следствие, к частоте появления следствия в целом. Значения лифта большие, чем единица, показывают, что условие более часто появляется в транзакциях, содержащих и следствие, чем в остальных. Можно сказать, что лифт является обобщенной мерой связи двух предметных наборов: при значениях лифта >1 связь положительная, при 1 она отсутствует, а при значениях

Другой мерой значимости правила является левередж — это разность между наблюдаемой частотой, с которой условие и следствие появляются совместно (т.е. поддержкой ассоциации), и произведением частот появления (поддержек) условия и следствия по отдельности.

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

Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил вида «Из X следует Y», причем поддержка и достоверность этих правил должны находиться в рамках некоторых, наперед заданных, границ, называемых соответственно минимальной и максимальной поддержкой и минимальной и максимальной достоверностью.

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

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

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

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

Таким образом, алгоритм a prioriвключает два этапа:

— поиск популярных наборов;

— формулировка ассоциативных правил, удовлетворяющих заданным ограничениям по уровням поддержки и достоверности.

В Deductor Studio для решения задач ассоциации используется обработчик Ассоциативные правила. В нем реализован алгоритм a priori. Обработчик требует на входе два поля: идентификатор транзакции и элемент транзакции.

Не нашли то, что искали? Воспользуйтесь поиском:

Оцените статью
Adblock detector