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

Опираясь на концепцию строгих правил, Ракеш Агравал, Томаш Имелинский и Арун Свами выдвинули ассоциативные правила для обнаружения закономерностей между продуктами в транзакциях большого размера для данных, записанных системами POS-терминалов в супермаркетах. Например, правило {лук, картофель} => {гамбургер}, найденное в данных о продажах супермаркета, могло бы означать, что, если покупатель покупает лук и картофель вместе, он, скорее всего, купит также и гамбургер. Такого рода информация может быть использована как базис для решений о маркетинговых действиях, например, стимулирующему ценообразованию или размещению продукции.

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

Определение + Пример базы данных с 5 транзакциями и 5 элементами ID транзакции молоко хлеб масло пиво памперсы111000200100300011411100501000

Следуя исходному определению Агравала, Имелинского и Свами задача поиска ассоциативных правил ставится следующим образом:

Пусть дан набор из двоичных атрибутов, называемых объектами.

Пусть дан набор транзакций, называемый базой данных.

Каждая транзакция в имеет уникальный ID (номер) транзакции и состоит из подмножества объектов из .

Правило определяется как импликация вида:

, где .

В статье Агравала, Имелинского, Свами правило определяется только между множеством и одиночным объектом для .

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

Чтобы проиллюстрировать концепцию, используем маленький пример из области супермаркета. Множество объектов I — это молоко, хлеб, масло, пиво, памперсы, и в таблице выше показана маленькая база данных, содержащая объекты, в которой значение 1 означает наличие объекта в соответствующей транзакции, а значение 0 означает отсутствие объекта в транзакции.

Примером правила для супермаркета может служить {масло, хлеб} => {молоко}, что означает, что, если куплены масло и хлеб, покупатель также купит и молоко.

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

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

Пусть будет набором объектов, будет ассоциативным правилом, а — набором транзакций данной базы данных.

Поддержка Поддержка — это показатель, насколько часто набор объектов обнаруживается в базе данных.

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

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

Доверие Доверие — это показатель, насколько часто правило оказывается верным.

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

Доверие определяется как:

Например, правило {масло, хлеб} => {молоко} имеет доверие в базе данных, что означает, что для 100% транзакций, содержащих масло и хлеб, правило верно (в 100 % случаев, когда покупается масло и хлеб, молоко покупается также).

Заметим, что означает поддержку объектов в X и Y. Это несколько запутывает, поскольку мы обычно думаем в терминах вероятности событий, а не терминах набора объектов. Мы можем переписать как вероятность , где и являются событиями, что транзакция содержит наборы и соответственно.Michael Hahsler (2015). A Probabilistic Comparison of Commonly Used Interest Measures for Association Rules. http://michael.hahsler.net/research/association_rules/measures.html

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

Лифт правила определяется как:

или отношение наблюдаемой поддержки к математическому ожиданию события, если бы X и Y были бы независимы. Например, правило {молоко, хлеб} => {масло} имеет лифт .

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

Если лифт > 1, это позволяет нам знать степень, насколько события связаны друг с другом, и делает эти правила потенциально полезными для предсказания следствия в будущих наборах данных.

Если лифт < 1, это означает, что объекты заменяют друг друга. Это означает, что наличие одного объекта имеет отрицательный эффект на присутствие второго объекта, и наоборот.

Значение лифта принимает во внимание как доверие правила, так и общие данные.

Уверенность Уверенность правила определяется как .

Например, правило {молоко, хлеб} => {масло} имеет уверенность и может пониматься как отношение ожидаемой частоты, что X встречается без Y (говоря иначе, частота, что правило даёт неправильное предсказание), если бы X и Y были бы независимыми, и наблюдаемой частоты неверных предсказаний. В этом примере значение уверенности 1,2 показывает, что правило {молоко, хлеб} => {масло} будет неверным на 20 % чаще (в 1,2 раз чаще), если ассоциация между X и Y была чистой случайностью.

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

Нахождение всех частых наборов в базе данных затруднительно, поскольку вовлекает поиск всех возможных наборов (комбинаций объектов). Множество возможных наборов является булеаном над и имеет размер (за исключением пустого множества, которое не является допустимым набором). Хотя размер булеана растёт экспоненциально от числа объектов в , эффективный поиск возможен с помощью свойства нисходящего замыкания поддержки (называемого также антимонотонностью), которое гарантирует, что для часто встречающегося набора все его поднаборы также часто встречаются, а потому не может быть нечастых поднаборов у часто встречающегося набора. Используя это свойство, эффективные алгоритмы (например, Apriori и Eclat) могут найти все часто встречающиеся наборы.

История Концепция ассоциативного правила стала популярной благодаря статье 1993 года Агравала, Имелинского, Свами, на которую, согласно Google Scholar, к августу 2015 насчитывалось более 18.000 ссылок, и она является одной из наиболее цитируемых статей в области Data Mining (поиска закономерностей в базах данных). Однако то, что ныне называется «ассоциативными правилами» было введено ещё в статье 1966 года о системе GUHA, общем методе анализа данных, разработанном Петром Гайеком с сотрудниками.

В начале (примерно) 1989 года для поиска минимальной поддержки и доверия для поиска всех ассоциативных правил использовалась система «Характеристическое моделирование» (), которая находит все правила со значениями и , которые больше заданных пользователем границ.

Альтернативные меры интересности Кроме доверия, были предложены и другие меры интересности для правил. Некоторые популярные меры:

Полное доверие () Коллективная мощь () Убеждённость () Рычаг () Лифт (первоначально назывался интересом)

Несколько других мер представили и сравнили Тан, Кумар и Сривастана, а также Хаслер. Поиск техник, которые могут моделировать, что пользователю известно (и использовать это в качестве меры интересности) в настоящее время является активным трендом исследований под названием «Субъективная интересность».

Статистически обоснованные ассоциации

Одним из ограничений стандартного подхода к обнаружению ассоциаций является то, что при поиске в большом числе возможных ассоциаций набора объектов, которые могут быть ассоциированными, есть большой риск нахождения большого числа случайных ассоциаций. Это наборы объектов, которые оказываются вместе с неожиданной частотой в данных, но чисто случайно. Например, предположим, что мы рассматриваем набор из 10.000 объектов и ищем правило, содержащее два объекта в левой части и один объект в правой части. Имеется примерно 1.000.000.000.000 таких правил. Если мы применим статистический тест независимости с уровнем 0,05 это означает, что имеется только 5 % шанса принять правило при отсутствии ассоциации. Если мы предполагаем, что нет никаких ассоциаций, мы должны, тем не менее, ожидать нахождения 50.000.000.000 правил. Статистически обоснованное обнаружение ассоциаций контролирует этот риск, в большинстве случаев сокращая риск нахождения любой случайной ассоциации для заданного пользователем уровня значимости.

Алгоритмы

Было предложено много алгоритмов для генерации ассоциативных правил.

Несколько алгоритмов хорошо известны, это Apriori, Eclat и FP-Growth, но они делают только половину работы, поскольку они предназначены для отыскания часто встречающихся наборов объектов. Нужно сделать ещё один шаг после того, как часто встречающиеся наборы найдены в базе данных.

Алгоритм Apriori

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

Алгоритм Eclat

Алгоритм Eclat (или ECLAT, от Equivalence Class Transformation = Преобразование Классов Эквивалентности) является алгоритмом поиска в глубину, основанном на пересечении множеств. Алгоритм пригоден как для последовательного, так и параллельного выполнения со свойствами локального улучшения.

Алгоритм FP-роста

Алгоритм FP предназначен для выявления часто встречающихся шаблонов.

При первом проходе алгоритм подсчитывает встречаемость объектов (пары атрибут-значение) в наборах и запоминает их в «таблице заголовков». При втором проходе алгоритм строит структуру FP-дерева путём вставки экземпляров. Объекты в каждом экземпляре должны быть упорядочены по убыванию их частоты встречаемости в наборе, так что дерево может быть обработано быстро. Объекты в каждом экземпляре, которые не достигают минимального порога, отбрасываются. Если много экземпляров имеют общими большинство часто встречаемых объектов, FP-дерево обеспечивает высокое сжатие близко к корню дерева.

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