Лабораторная работа №12. Поиск ассициативных правил.

 

Цель работы. Изучить возможность поиска ассоциативных правил используя аналитическую  платформуDEDUCTOR

Теоретическая часть.  В последнее время растет интерес к методам «обнаружения знаний в базах данных». Большие объемы современных баз данных вызsвают спрос на новые алгоритмы распознавания и обработки данных. Одним из распространенных аналитических методов обработки данных является аффинитивный анализ (англ: affinityanalysis), название произошедшее от английского слова affinity – близость, сходство. Метод определяет взаимные связи между событиями, происходящие совместно. Одним  из применения аффинитивного анализа является анализ рыночной корзины (англ: marketbasketanalysis), цель которого – обнаружить ассоциации между различными данными, т.е. найти правила для количественного описания взаимной связи между двумя или более данными. Такие правила называются ассоциативными правилами (англ.: associationrules) и применяются в data mining. 

Примерами приложения ассоциативных правил могут быть следующие задачи: 

1.                  Обнаружение наборов товаров, которые в супермаркетах часто покупаются вместе или никогда не покупаются вместе. 

2.                  Определение доли клиентов, положительно относящихся к нововведениям в их обслуживании. 

3.                  Определение профиля посетителя веб-ресурса. 

4.                  Определение доли случаев, в которых новое лекарство показывает опасный побочный эффект. 

Базовым понятием в теории ассоциативных правил является транзакция. 

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

 Таблица 1. Пример набора транзакций.

№ транзакции Товары

1                    сливы, салат, помидоры 

2                    сельдерей, конфеты 

3                    конфеты

4                    яблоки, морковь, помидоры, картофель, конфеты 

5                    яблоки, апельсины, салат.конфеты, помидоры 

6                    персики, апельсины, сельдерей, помидоры 

7                    фасоль, салат, помидоры 

8                    апельсины, салат.помидоры 

9                    яблоки, сливы, морковь, помидоры, лук, конфеты 

10               яблоки, картофель 

 

        На практике  обрабатываются миллионы транзакций, в которых участвуют десятки и сотни различных продуктов. Данный пример ограничен 10 транзакциями, содержащими 13 видов продуктов, что достаточно для иллюстрации методики обнаружения ассоциативных правил. В большинстве случаев клиент приобретает не один товар, а некоторый набор товаров, называемых рыночной корзиной. Существует связь  между спросом на товары, которую может обнаружить ассоциативное правило, утверждающее, что покупатель, купивший молоко, с вероятностью 75% купит и хлеб. Такие связи сущетвуют и в других областях, например в медицинской или технической диагностике, выборе профессий и т.д.

Анализ рыночной корзины – это анализ наборов данных для определения комбинаций товаров, связанных между собой. Иными словами, производится поиск товаров, присутствие которых в транзакции влияет на вероятность наличия других товаров или комбинаций товаров [4]. 

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

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

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

Условие часто ограничивают содержанием только одного предмета. Правила обычно отображаются с помощью стрелок, направленных от условия к следствию, например, (помидоры) → (салат). Условие и следствие часто называются соответственно левосторонним (LHS – left-handside) и правосторонним (RHS – right-handside) компонентом ассоциативного правила. 

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

Обозначим Dкак базу данных транзакций, а Nкак число транзакций в этой базе. Каждая транзакция Diпредставляет собой некоторый набор предметов.

Зададим, что S(англ.: support) – поддержка, C (англ.: confidence) – достоверность. 

Поддержка ассоциативного правила – это число транзакций, содержащих как условие, так и следствие. 

Например, для ассоциации A→Bможно записать: 

 

 

Достоверность  ассоциативного правила- это мера точности правила, которая определяется как отношение количества транзакций, содержащих как условие, так и следствие, к количеству транзакций, содержащих только условие. 

Например, для ассоциации A→B можно записать:

 

 

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

Рассмотрим пример для вычисления поддержки и достоверности для ассоциаций из табл.1. Возьмем ассоциацию (салат) →(помидоры). Поскольку количество транзакций, содержащее как (салат), так и (помидоры), равно 4, а общее число транзакций 10, то поддержка данной ассоциации будет: 

S((салат)→ (помидоры)) = 4/10 = 0,4 .

Поскольку Поскольку количество транзакций, содержащее только (салат) как условие, равно 4, то достоверность данной ассоциации будет: 

С((салат) →(помидоры)) = 4/4 = 1. 

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

Рассмотрим ассоциацию (конфеты) →(помидоры), в которой содержатся, в общем-то, слабо совместимые в гастрономическом плане продукты (тот, кто планирует сделать растительное блюдо, вряд ли станет покупать конфеты, а покупатель, желающий приобрести что-нибудь к чаю, скорее всего, не станет покупать помидоры). Поддержка данной ассоциации S = 3/10 = 0,3 , а достоверностьС= 3/7 = 0,43. Таким образом, сравнительно невысокая достоверность данной ассоциации дает повод усомниться в том, что она является правилом. 

Аналитики могут отдавать предпочтение правилам, которые имеют только высокую поддержку или только высокую достоверность, либо, что является наиболее частым, оба эти показателя. Правила, для которых значения поддержки или достоверности превышают некоторый, заданный пользователем порог, называются сильными правилами (strongrules). Например, аналитика может интересовать, какие товары в супермаркете, покупаемые вместе, образуют ассоциации с минимальной поддержкой 20% и минимальной достоверностью 70 %. С другой стороны, при анализе с целью обнаружения мошенничеств, аналитику может потребоваться уменьшение поддержки до 1%, поскольку сравнительно небольшое число транзакций являются связанными с мошенничеством. 

Значимость ассоциативных правил 

        Методики поиска ассоциативных правил обнаруживают все ассоциации, которые удовлетворяют ограничениям на поддержку и достоверность, наложенные пользователем. Это часто приводит к необходимости рассмотреть десятки и сотни тысяч ассоциаций, что делает невозможным «ручную» обработку такого большого количества данных. Очевидно, что желательно уменьшить число правил таким образом, чтобы проанализировать только наиболее значимые правила. Часто значимость связана с разностью между поддержкой правила в целом и произведением поддержки только условия и поддержки только следствия. 

Выделяют объективные и субъективные меры значимости правил. Объективными являются такие меры, как поддержка и достоверность, которые могут применяться независимо от конкретного приложения. Субъективные меры связаны со специальной информацией, определяемой пользователем в контексте решаемой задачи. Такими субъективными мерами являются лифт (англ: lift) и левередж(от англ. leverage- плечо, рычаг). 

       Лифт – это отношение частоты появления условия в транзакциях, которые также содержат и следствие, к частоте появления следствия в целом. Лифт (оригинальное название - интерес) определяется следующим образом:  L(A→B) = C (A →B)/S(B).   Значения лифта большие, чем единица показывают, что условие более часто появляется в транзакциях, содержащих и следствие, чем в остальных. Можно сказать, что лифт является обобщенной мерой связи двух предметных наборов: при значениях лифта >1 связь положительная, при 1 она отсутствует, а при значениях <1 -отрицательная.  Другой мерой значимости правила является левередж(англ: leverage; предложена Г. Пятецким-Шапиро): 

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

L(А→В) = S(A →В) - S(A)S(B).

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

Генерация ассоциативных правил

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

Например, идентификатор транзакции – это номер чека или код клиента. А элемент - это наименование товара в чеке или услуга, заказанная клиентом.  Оба поля (идентификатор и элемент транзакции) должны быть дискретного вида. 

Пример решения конкретной задачи ассоциации из области розничной торговли:

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

-                      предложить рекламные акции типа «Каждому купившему товары A и B, товар C в подарок». 

Откройте программу DeductorStudio , используя ярлык на рабочем столе или через кнопку Пуск. 

Импортируйте данные из текстового файла transactions.txt в DeductorStudio. В файле данных имеются два столбцаТранзакция и Продукт, для которых нужно Тип поля нужно установить строковый.

 

 

После импорта к данному загруженному файлу применим обработчик Ассоциативные правила. Столбец Транзакция сделаем идентификатором транзакции, а столбецПродукт – ее элементом:

 

 

На следующем шаге мастера настроим параметры построения ассоциативных правил, что, по сути, есть параметры алгоритма apriori:

 

 

Здесь для изменения доступны следующие параметры. 

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

Минимальная и максимальная достоверность в % – в результирующий набор попадут только те ассоциативные правила, которые удовлетворяют условиям минимальной и максимальной достоверности. 

Максимальная мощность искомых часто встречающихся множеств – параметр ограничивает длину k-предметного набора. Например, при установке значения 4 шаг генерации популярных наборов будет остановлен после получения множества 4-предметных наборов. В конечном итоге это позволяет избежать появления длинных ассоциативных правил, которые трудно интерпретируются. 

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

Далее выбираем все доступные специализированные визуализаторы DataMining и визуализатор Таблица:

 

 

Все эти визуализаторы, кроме Что-если, отображают результаты работы алгоритма в различных формах. 

На вкладке Правила помимо самих ассоциативных правил приводятся их основные расчетные характеристики:

 

Поддержка, достоверность и лифт.

 

На вкладке Популярные наборы отображается множество найденных популярных предметных наборов в виде списка. Кнопка предлагает на выбор несколько вариантов сортировки списка, а кнопка * вызывает окно настройки фильтра множеств. Например, задав в фильтре минимальное значение поддержки 3% и отсортировав их по убыванию поддержки, получим 17 популярных наборов (на картинке изображено только 12):

 

 

Выявить наиболее популярные товарные наборы, состоящие из более, чем 1 предмета;

 

На вкладке Дерево правил предлагается еще один удобный способ отображения множества ассоциативных правил, которое строится либо по условию, либо по следствию. При построении дерева правил по условию, на первом (верхнем) уровне находятся узлы с условиями, а на втором уровне – узлы со следствием. В дереве, построенном по следствию, наоборот, на первом уровне располагаются узлы со следствием. 

Справа от дерева расположен список правил, построенный по выбранному узлу дерева, например по правилу №5:

предложить рекламные акции типа «Каждому купившему товары A и B, товар C в подарок». 

 

 

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

Сохраните сценарий под именем assosiation.ded. 

 

Вопросы:

1.                  Какой алгоритм генерации ассоциативных правил имеется в Deductor? 

2.                  Какие входные поля набора данных необходимы для запуска обработчика Ассоциативные правила в Deductor? 

3.                  Какие специализированные визуализаторы предлагаются к узлуобработчику Ассоциативные правила?