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

Тема 5. Ассоциативные правила. Мотивировка

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

Определение

Аффинитивный анализ (affinity analysis) — набор методов интеллектуального анализа данных, направленный на поиск и исследование взаимной связи (ассоциаций) между событиями, происходящими совместно, и количественную оценку таких связей. Целью анализа является обнаружение ассоциации между различными событиями, то есть обнаружение правила для количественного описания взаимной связи между двумя или более событиями. Такие правила называются ассоциативными (association rules).

Базовым понятием в теории ассоциативных правил является транзакция  — некоторое множество событий, происходящих совместно. Обычно рассматривается не одна транзакция, а множество транзакций :[pic 1][pic 2]

,[pic 3]

где  – количество транзакций.[pic 4]

Набор всех событий (предметный набор), которые могут встретиться в транзакциях, задан множеством :[pic 5]

,[pic 6]

где  – количество элементарных событий.[pic 7]

Пусть в нашем магазине имеется множество товаров . Пусть  – множество транзакций, где каждая транзакция  – это множество товаров, купленных пользователем за одно посещение магазина. Каждая транзакция имеет уникальный id. В нашем случае, под транзакцией можно понимать чек. Пусть, например, в нашем магазине имеются следующие товары: молоко, кофе, хлеб, масло. Тогда . Если покупатель купил молоко и кофе, то он совершил транзакцию . [pic 8][pic 9][pic 10][pic 11][pic 12]

Под ассоциативным правилом понимается импликация (следование) , где  (т.е.  - какие-то множества из , которые не пересекаются между собой). Таким образом, любое правило состоит из двух различных наборов объектов  и , где под  подразумевается условие правила, а под  — следствие правила.[pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20]

Мы можем построить следующее ассоциативное правило: . Данной записью мы сказали, что если покупатель купил молоко и кофе, то он купил и масло. Т.е. данное правило устанавливает некую зависимость между покупкой молока, кофе, масла. Понятно, что мы безосновательно составили данное правило и на практике необходимо проверить действительно ли наша конструкция является ассоциативным правилом, можно ли доверять этому правилу и нужно ли вообще рассматривать это правило, поскольку оно может возникать крайне редко.[pic 21]

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

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

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