Правила ассоциации: Работа априорного алгоритма
Оба алгоритма можно скачать с GitHub, в папке Datasets есть файлы для тестирования. В конце сообщения находится полный текст статьи (на испанском языке).
Интеллектуальный анализ данных состоит из анализа объемов данных с помощью различных инструментов или методов, которые облегчают этот процесс, таких как, например, априорный алгоритм, FP-Growth, aprioriTID, aprioriHybrid, Eclat, правила Top-k и т. Д. Сегодня применимость интеллектуальный анализ данных можно увидеть во многих областях, таких как медицина, биология или коммерческие предприятия.
Правила ассоциации
Правила ассоциации показывают корреляции, обнаруженные в результате анализа большого набора транзакций. Эти правила представлены антецедентом X и последующим Y.
Наиболее распространенные методы получения этих правил используют два параметра: поддержка и доверие. Первый рассчитывается для набора транзакций T и указывает, какой процент транзакций содержит X.
Поддержка = (количество транзакций, содержащих X) / (общее количество транзакций)
Второй указывает, какой процент транзакций, содержащих X, также содержит Y, и определяется следующим образом:
Доверие = Поддержка (X U Y) / Поддержка (X)
Каждое правило указывает, что если X удовлетворено, существует определенная вероятность, определяемая его уверенностью в том, что Y также удовлетворяется.
Алгоритм априори
Код Github:
Алгоритм обнаруживает все возможные правила от поддержки и минимального доверия. Он разделен на две основные части. Первый состоит из получения наборов часто используемых элементов (наборов элементов), а второй — в генерации правил.
Пример
Алгоритм FP-Growth (Альтернатива)
Код Github
Подобно априорному алгоритму, он генерирует все возможные правила и состоит из двух частей: идентификации часто используемых элементов и другой характеристики генерации правил, использующих доверие и поддержку в качестве пороговых значений. Разница FPGrowth в генерации наборов часто встречающихся элементов основана на построении дерева.
Это дерево построено из часто встречающихся элементов (то есть тех, которые превышают минимально установленную поддержку), так что те, которые имеют самую высокую частоту будет расположен в верхней части дерева, при этом каждая ветвь создается путем прохождения набора транзакций с частыми элементами, уже упорядоченными по убыванию.
Полный текст статьи на испанском языке
Наборы данных собираются следующим образом:
На следующем рисунке видно, как при изменении обоих параметров (Trust и Support) количество сгенерированных правил уменьшится в обоих случаях. Когда один из параметров увеличивается, количество правил будет меньше из-за характеристик априорного алгоритма. Вариация поддержки оказывает большее влияние, генерируя гораздо меньшее количество правил, чем если бы степень достоверности была различной.
Производительность алгоритмов по количеству сгенерированных правил варьируется в зависимости от поддержки.
Выводы
Априорный алгоритм генерации ассоциативных правил не имеет возможности принимать решения относительно выходных данных, сгенерированных на основе области, в которой они находятся, то есть они возвращают как можно больше, и это наблюдается в огромном количестве правила, которые генерируются в этом посте. Вот почему это было бы хорошей альтернативой для адаптации решения к конкретным потребностям бизнеса.
Поддержка ассоциативного правила (Association Rule Support)
Показатель, характеризующий качество ассоциативного правила. Определяется как отношение числа транзакций, в которых появляется как условие A , так и следствие B правила, к общему числу транзакций базы данных N :
Значение поддержки меняется от 0 (когда условие и следствие не встречаются вместе ни в одной транзакции) до 1 (когда условие и следствие во всех транзакциях появляются совместно). Иногда поддержку выражают в процентах (0 — 100%).
В общем случае поддержка является мерой надежности, с которой ассоциативное правило выражает ассоциативную связь между условием и следствием. Если поддержка S > 0,8, то связь сильная, а само правило заслуживает доверия. В случае, когда 0,5 < S < 0,8, ассоциативная связь средняя, а правило следует использовать с осторожностью. При S < 0,5 связь слабая, а ассоциативное правило является сомнительным.
Кроме этого, поддержка используется в качестве параметра алгоритмов поиска ассоциативных правил на основе частых предметных наборов (например, алгоритм Apriori). Задается значение минимальной поддержки (обычно, достаточно большое). Затем ищутся все предметные наборы, поддержка которых (отношение числа транзакций, где присутствует набор, к общему их числу) превышает минимальную. Такие предметные наборы называют частыми, или популярными, и на их множестве производится дальнейший поиск ассоциативных правил.
Следует отметить, что поддержка не является исчерпывающей характеристикой «силы» ассоциативного правила, поскольку не учитывает, сколько раз условие и следствие появляются в транзакциях независимо друг от друга. Поэтому для оценки правил вместе с поддержкой используют другую меру — достоверность.
В Loginom существует отдельный обработчик ассоциативные правила, который выявляет ассоциативные правила в транзакционных данных.
Подробнее о преимуществах ассоциативных правил в поиске закономерностей между связанными событиями можно узнать в статье «Введение в анализ ассоциативных правил». А в статье «Выявление обобщенных ассоциативных правил» приведены два метода вычисления обобщенных ассоциативных правил: базовый и улучшенный алгоритмы.
Анализ рыночной корзины и ассоциативные правила
В продолжении темы о Data Mining поговорим о том, с чего все начиналось. А начиналось все с анализа рыночной корзины (market basket analysis).
Анализ рыночной корзины — процесс поиска наиболее типичных шаблонов покупок в супермаркетах. Он производится путем анализа баз данных транзакций с целью определения комбинаций товаров, связанных между собой. Иными словами, выполняется обнаружение товаров, наличие которых в транзакции влияет на вероятность появления других товаров или их комбинаций.
Результаты, полученные с помощью анализа рыночной корзины, позволяют оптимизировать ассортимент товаров и запасы, размещение их в торговых залах, увеличивать объемы продаж за счет предложения клиентам сопутствующих товаров. Например, если в результате анализа будет установлено, что совместная покупка макарон и кетчупа является типичным шаблоном, то разместив эти товары на одной и той же витрине можно «спровоцировать» покупателя на их совместное приобретение.
Ассоциативные правила
Для решения задачи анализа рыночной корзины используются ассоциативные правила вида «если… то. ». Например, «если клиент купил пиво, то он купит и чипсы». Каждая покупка именуется «транзакцией», на основании большего набора таких транзакций и строят исследования поведения клиента.
Ассоциативные правила являются очень простой и удобной формой записи знаний. Еще раз хочу уточнить, что информация о транзакциях является исходными данными, а вот полученные ассоциативные правила являются теми знаниями, которые помогли в 80-х большим супермаркетам сэкономить большие деньги.
Для характеристики правила используются некоторые метрики:
Правило X->Y имеет поддержку s (support), если s транзакций из D, содержат пересечение множеств X и Y. Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X->Y справедливо с достоверностью c (confidence), если c транзакций из D, содержащих X, также содержат Y, conf(X-> Y) = supp(X->Y)/supp(X ).
Например: «75% транзакций, содержащих хлеб, также содержат молоко. 3% от общего числа всех транзакций содержат оба товара». 75% – это достоверность (confidence) правила, 3% — это поддержка (support), или «Хлеб» -> «Молоко» с вероятностью 75% и поддержкой 3%.
Как правило, очевидные правила имеют поддержку и достоверность высокую (60% и больше), но не являются знаниями де-факто. Основное внимание необходимо уделять правилам, имеющим поддержку 5-10%, именно они могут стать источником идеи промоакции или услуги.
Алгоритм Apriori
Основным алгоритмом, который применяется для получения ассоциативных правил, является алгоритм apriori. Его автором является Ракеш Агравал (Rakesh Agrawal, сейчас сотрудник Microsoft Research).
Алгоритм Apriori предназначен для поиска всех частых множеств признаков. Он является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх.
Алгоритм перебора следующий (источник):
Основная особенность алгоритма — свойство антимонотонности (источник):
Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора <Хлеб, Масло, Молоко>будет всегда меньше или равна поддержке 2-элементных наборов <Хлеб, Масло>, <Хлеб, Молоко>, <Масло, Молоко>. Дело в том, что любая транзакция, содержащая <Хлеб, Масло, Молоко>, также должна содержать <Хлеб, Масло>, <Хлеб, Молоко>, <Масло, Молоко>, причем обратное не верно.
Благодаря этому свойству перебор не является «жадным» и позволяет обрабатывать большие массивы информации за секунды.
Классический алгоритм apriori уже был несколько раз модифицирован, работы по улучшению скорости ведутся и сейчас.
Лабораторная работа_№6
Изучение процесса построения ассоциативных моделей на основе алгоритма поиска ассоциативных правил Apriori в аналитической платформе Deductor.
Теоретическая часть. Одним из популярных методов Data Mining является аффинитивный анализ (от анг. Affinity — «близость», «сходство»). В основе метода лежит исследование связи между событиями, которые происходят совместно, а цель — найти правила для количественного описания взаимной связи между двумя или более событиями. Такие правила называются ассоциативными правилами (АП) . Примерами приложения ассоциативных правил могут быть следующие задачи:
— выявление наборов товаров, которые в супермаркетах часто покупаются вместе;
— определение технических неисправностей, появляющихся совместно;
— определение профиля посетителей веб-ресурса и т.д.
Базовым понятием в теории АП является транзакция — некоторое множество событий, происходящих совместно, например, приобретение набора товаров в супермаркете по одному чеку. В подавляющем большинстве случаев клиент покупает не один товар, а набор товаров, который называется рыночной корзиной. Аналогично, диагностика автомобиля на СТО обычно выявляет несколько неисправностей, которые также могут быть связаны друг с другом. При этом возникает вопрос: является ли покупка одного товара в корзине, следствием или причиной покупки другого, то есть связаны ли данные события? Или является ли появление одной неисправности следствием появления другой. Эти связи обнаруживают и количественно описывают ассоциативные правила. Например, может быть обнаружено АП, утверждающее, что клиент, купивший молоко, с вероятностью 75 % купит и хлеб.
Анализ рыночной корзины — это анализ транзакционных наборов данных для определения комбинаций событий, связанных между собой. Иными словами, производится поиск событий, присутствие которых в транзакции влияет на вероятность наличия других событий или их комбинаций. Например, событием является покупка товара или обнаружение неисправности. Зная устойчивые комбинации товаров покупаемых совместно, можно оптимизировать ассортимент товаров. Зная типичные наборы неисправностей, можно оптимизировать ремонт и обслуживание техники.
Рассмотрим пример. Кассовые аппараты в супермаркетах позволяют собирать информацию о покупках и сохранять в транзакционных БД, в которых может производиться поиск АП. В табл. 1 в каждой строке указывается комбинация продуктов, приобретенных за одну покупку. Хотя на практике приходится иметь дело с миллионами транзакций, в которых участвуют десятки и сотни различных продуктов, пример ограничен 10 транзакциями, содержащими 13 видов продуктов: чтобы проиллюстрировать методику обнаружения ассоциативных правил, этого достаточно.
Сливы, салат, помидоры
Яблоки, морковь, помидоры, картофель, конфеты
Яблоки, апельсины, салат, конфеты, помидоры
Персики, апельсины, сельдерей, помидоры
Фасоль, салат, помидоры
Апельсины, салат, морковь, помидоры, конфеты
Яблоки, бананы, сливы, морковь, помидоры, лук, конфеты
Визуальный анализ таблицы показывает, что все четыре транзакции, в которых фигурирует салат, также включают помидоры и что четыре из семи транзакций, содержащих помидоры, также содержат салат. Салат и помидоры в большинстве случаев покупаются вместе. АП позволяют обнаруживать и количественно описывать такие совпадения.
АП состоит из двух наборов предметов, называемых условие (antecedent) и следствие (consequent), записываемых в виде X Y, что читается следующим образом: «Из X следует Y». Таким образом, ассоциативное правило формулируется в виде: «Если условие, то следствие». Правила обычно отображаются с помощью стрелок, направленных от условия к следствию, например, помидоры салат.
АП количественно описывают связь между наборами предметов, соответствующими условию и следствию. Эта связь характеризуется двумя показателями — поддержкой (support) и достоверностью (confidence). Обозначим БД транзакций как D, а число транзакций в ней N. Каждая транзакция Di представляет собой набор предметов.
Поддержка ассоциативного правила S — это число транзакций, которые содержат как условие, так и следствие. Например, для ассоциации A B можно записать:
,
т.е. число транзакций, в которых появляются предметы A и B, отнесенное к общему числу транзакций. Достоверностью ассоциативного правила A B является:
,
т.е. число транзакций, в которых появляются предметы A и B, отнесенное к числу транзакций, содержащих только A.
Если поддержка и достоверность достаточно высоки, можно с большой вероятностью утверждать, что любая будущая транзакция, которая включает условие, будет также содержать и следствие. Вычислим поддержку и достоверность для ассоциаций из табл. 1. Рассмотрим ассоциацию салат помидоры. Поскольку количество транзакций, содержащих как салат, так и помидоры, равно 4, а общее число транзакций — 10, то поддержка данной ассоциации будет:
S(салат помидоры) = 4 / 10 = 0,4.
Поскольку количество транзакций, содержащих только салат (условие), равно 4, то достоверность данной ассоциации будет:
С(салат помидоры) = 4 / 4 = 1.
Иными словами, все наблюдения, содержащие салат, также содержат и помидоры, из чего делаем вывод о том, что данная ассоциация может рассматриваться как АП. Теперь рассмотрим ассоциацию конфеты помидоры, в которой содержатся, в общем-то, слабо совместимые в гастрономическом плане продукты: тот, кто решил приготовить растительное блюдо, вряд ли станет покупать конфеты, а тот, кто желает приобрести что-нибудь к чаю, скорее всего, не станет покупать помидоры. Поддержка данной ассоциации: S = 3 / 10 = 0,3, а достоверность: С = 3 / 7 = 0,43. Таким образом, сравнительно невысокая достоверность данной ассоциации дает повод усомниться в том, что она является правилом.
Правила, для которых значения поддержки или достоверности превышают определенный, заданный пользователем порог, называются сильными правилами (strong rules). Например, аналитика может интересовать, какие товары, покупаемые вместе в супермаркете, образуют ассоциации с минимальной поддержкой 20 % и минимальной достоверностью 70 %.
Значимость ассоциативных правил. Методики поиска АП обнаруживают все ассоциации, которые удовлетворяют ограничениям на поддержку и достоверность. Это приводит к необходимости рассматривать десятки и сотни тысяч ассоциаций, что делает невозможным обработку такого количества данных вручную. Число правил желательно уменьшить таким образом, чтобы проанализировать только наиболее значимые из них. Значимость часто вычисляется как разность между поддержкой правила в целом и произведением поддержки только условия и поддержки только следствия.
Если условие и следствие независимы, то поддержка правила примерно соответствует произведению поддержек условия и следствия, то есть SAB SASB. Это значит, что хотя условие и следствие часто встречаются вместе, не менее часто они встречаются и по отдельности. Например, если товар A встречался в 70 транзакциях из 100, а товар B — в 80 и в 50 транзакциях из 100 они встречаются вместе, то несмотря на высокую поддержку (SAB = 0,5) это не обязательно правило. Просто эти товары покупаются независимо друг от друга, но в силу их популярности часто встречаются в одной транзакции. Поскольку произведение поддержек условия и следствия SASB = 0,7 0,8 = 0,56, то есть отличается от SAB = 0,5 всего на 0,06, предположение о независимости товаров A и B достаточно обоснованно.
Однако если условие и следствие независимы, то правило вряд ли представляет интерес независимо от того, насколько высоки его поддержка и достоверность. Например, если статистика дорожно-транспортных происшествий показывает, что из 100 аварий в 80 участвуют автомобили марки ВАЗ, то, на первый взгляд, это выглядит как правило «если авария, то ВАЗ». Но если учесть, что парк автомобилей ВАЗ составляет, скажем, 80 % от общего числа легковых автомобилей, то такое правило вряд ли можно назвать значимым.
По этой причине при поиске ассоциативных правил используются дополнительные показатели, позволяющие оценить значимость правила. Можно выделить объективные и субъективные меры значимости правил. Объективными являются такие меры, как поддержка и достоверность, которые могут применяться независимо от конкретного приложения. Субъективные меры связаны со специальной информацией, определяемой пользователем в контексте решаемой задачи. Такими субъективными мерами являются лифт (lift) и левередж (от англ. leverage — плечо, рычаг).
Лифт (оригинальное название — интерес) вычисляется следующим образом:
L(A B) = C(A B) / S(B),
т.е. отношение частоты появления условия в транзакциях, которые также содержат и следствие, к частоте появления следствия в целом. Значения лифта большие, чем единица, показывают, что условие чаще появляется в транзакциях, содержащих следствие, чем в остальных. Можно сказать, что лифт является обобщенной мерой связи двух предметных наборов: при значениях лифта > 1 связь положительная, при 1 она отсутствует, а при значениях < 1 — отрицательная.
Рассмотрим ассоциацию помидоры салат из табл. 1.
S(салат) = 4/10 = 0,4; С(помидоры салат) = 4/7 = 0,57.
Следовательно, L(помидоры салат) = 0,57/0,4 = 1,425.
Теперь рассмотрим ассоциацию помидоры конфеты.
S(конфеты) = 0,6; С(помидоры конфеты) = 4/7 =0,57.
Тогда L(помидоры конфеты) = 0,57/0,6 = 0,95.
Большее значение лифта для первой ассоциации показывает, что помидоры больше влияют на частоту покупок салата, чем конфет.
Поиск АП. В процессе поиска АП может производиться обнаружение всех ассоциаций, поддержка и достоверность для которых превышают заданный минимум. Простейший алгоритм поиска рассматривает все возможные комбинации условий и следствий, оценивает для них поддержку и достоверность, а затем исключает все ассоциации, которые не удовлетворяют заданным ограничениям. Число возможных ассоциаций с увеличением числа предметов растет экспоненциально. Если в БД транзакций присутствует k предметов и все ассоциации являются бинарными (то есть содержат по одному предмету в условии и следствии), то потребуется проанализировать k 2k –1 ассоциаций. Поскольку реальные БД транзакций, рассматриваемые при анализе рыночной корзины, обычно содержат тысячи предметов, вычислительные затраты при поиске АП огромны. Например, если рассматривать выборку, содержащую всего 100 предметов, то количество ассоциаций, образуемых этими предметами, составит 1002 99 = 6,4 10 31 . Поиск АП путем вычисления поддержки и достоверности для всех возможных ассоциаций и сравнения их с заданным пороговым значением малоэффективен из-за больших вычислительных затрат.
Поэтому в процессе генерации АП широко используются методики, позволяющие уменьшить количество ассоциаций, которое требуется проанализировать. Одной из наиболее распространенных является методика, основанная на обнаружении так называемых популярных наборов, когда анализируются только те ассоциации, которые встречаются достаточно часто. На этой концепции основан известный алгоритм поиска ассоциативных правил Apriori.
В основе алгоритма a лежит понятие популярных наборов (frequent itemset), которые также можно назвать частыми предметными наборами, часто встречающимися множествами (соответственно, они связаны с понятием частоты ). Под частотой понимается простое количество транзакций, в которых содержится данный предметный набор. Тогда популярными наборами будут те из них, которые встречаются чаще, чем в заданном числе транзакций.
Популярный предметный набор —набор с поддержкой больше заданного порога либо равной ему. Этот порог называется минимальной поддержкой. Методика поиска ассоциативных правил с использованием популярных наборов состоит из двух шагов.
— cследует найти популярные наборы.
— на их основе необходимо сгенерировать АП, удовлетворяющие условиям минимальной поддержки и достоверности.
Чтобы сократить пространство поиска, алгоритм использует свойство антимонотонности, которое утверждает, что если предметный набор Z не является частым, то добавление некоторого нового предмета A к набору Z не делает его более частым. Другими словами, если Z не является популярным набором, то и набор Z A также не будет являться таковым. Данное полезное свойство позволяет значительно уменьшить пространство поиска АП.