Обучение ассоциативным правилам

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

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

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

Определение

Пример базы данных с 5 транзакциями и 5 элементами

ID транзакции	молоко	хлеб	масло	пиво	памперсы
1	1	1	0	0	0
2	0	0	1	0	0
3	0	0	0	1	1
4	1	1	1	0	0
5	0	1	0	0	0

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

Пусть дан набор $I=\{i_{1},i_{2},\ldots ,i_{n}\}$ из $n$ двоичных атрибутов, называемых объектами.

Пусть дан набор $D=\{t_{1},t_{2},\ldots ,t_{m}\}$ транзакций, называемый базой данных.

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

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

$X\Rightarrow Y$, где $X,Y\subseteq I$.

В статье Агравала, Имелинского, Свами правило определяется только между множеством и одиночным объектом $X\Rightarrow i_{j}$ для $i_{j}\in I$.

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

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

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

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

Полезные концепции

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

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

Поддержка

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

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

$\mathrm {supp} (X)={\frac {|\{t\in T;X\subseteq t\}|}{|T|}}$

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

Доверие

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

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

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

$\mathrm {conf} (X\Rightarrow Y)=\mathrm {supp} (X\cup Y)/\mathrm {supp} (X)$

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

Заметим, что $\mathrm {supp} (X\cup Y)$ означает поддержку объектов в X и Y. Это несколько запутывает, поскольку мы обычно думаем в терминах вероятности событий, а не терминах набора объектов. Мы можем переписать $\mathrm {supp} (X\cup Y)$ как вероятность $P(E_{X}\cap E_{Y})$, где $E_{X}$ и $E_{Y}$ являются событиями, что транзакция содержит наборы $X$ и $Y$ соответственно.

Доверие можно понимать как оценку условной вероятности $P(E_{Y}|E_{X})$, вероятности нахождения правой части правила в транзакциях при условии, что транзакции содержат левую часть правила.

Лифт

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

$\mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}$

или отношение наблюдаемой поддержки к математическому ожиданию события, если бы X и Y были бы независимы. Например, правило {молоко, хлеб} => {масло} имеет лифт ${\frac {0{,}2}{0{,}4\times 0{,}4}}=1{,}25$.

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

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

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

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

Уверенность

Уверенность правила определяется как $\mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}$.

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

Процесс

Решётка частоты наборов, где цвет прямоугольника показывает, как много транзакций содержит комбинацию объектов. Заметим, что нижние уровни решётки могут содержать минимальный набор объектов родителя. Например. {ac} может содержать как максимум $min(a,c)$. Это называется свойством нисходящего замыкания.

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

1. Минимальный порог поддержки используется для поиска всех частых наборов объектов в базе данных.
2. Ограничение минимального доверия применяется к этим наборам для формирования правила.

Второй шаг прост и ясен, а первый шаг требует большего внимания.

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

История

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

В начале (примерно) 1989 года для поиска минимальной поддержки и доверия для поиска всех ассоциативных правил использовалась система «Характеристическое моделирование» (англ. Feature Based Modeling), которая находит все правила со значениями $\mathrm {supp} (X)$ и $\mathrm {conf} (X\Rightarrow Y)$, которые больше заданных пользователем границ.

Альтернативные меры интересности

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

• Полное доверие (англ. All-confidence)
• Коллективная мощь (англ. Collective strength)
• Убеждённость (англ. Conviction)
• Рычаг (англ. Leverage)
• Лифт (первоначально назывался интересом)

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

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

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

Алгоритмы

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

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

Алгоритм Apriori

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

Алгоритм Eclat

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

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

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

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

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

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

Другие

AprioriDP

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

Основанный на контексте алгоритм поиска ассоциативных правил

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

Алгоритмы на основе множества узлов

FIN, PrePost и PPV — это три алгоритма, основанные на множествах узлов. Они используют узлы в кодировании FP-дерева для представления наборов объектов и поддерживают стратегию поиска в глубину для обнаружения часто встречающихся наборов объектов с помощью «пересечения» наборов узлов.

Процедура ASSOC метода GUHA

GUHA — это общий метод анализа данных, который имеет теоретические основы.

Процедура ASSOC является методом GUHA, который ищет общие ассоциативные правила, используя быстрые операции над битовыми строками. Ассоциативные правила, выявленные этим методом, более общие, чем полученные методом Apriori, например, «объекты» могут быть связаны как конъюнкцией, так и дизъюнкцией и связь между левой частью и правой частью правила не ограничена установкой минимальных значений поддержки и доверия как в методе Apriori — может быть использована произвольная комбинация мер интересности.

Поиск OPUS

OPUS является эффективным алгоритмом для обнаружения правил, который, в отличие от многих альтернатив, не требует ограничения ни монотонности, ни антимонотонности, таких как в минимуме поддержки. Поиск OPUS является базовой технологий в популярной системе поиска ассоциаций Magnum Opus.

Предания

Есть знаменитая история об обнаружении ассоциативных правил, это история «пиво и памперсы». Якобы некоторый просмотр поведения покупателей в супермаркете обнаружил, что покупатели (видимо, молодые люди), покупающие памперсы, часто также покупают пиво. Эта короткая история стала популярной как пример того, что неожиданные ассоциативные правила могут быть найдены в повседневных данных. Существует много мнений, насколько история истинна. Дэниел Пауэрс сказал:

В 1992 году Томас Блишок, управляющий консалтинговой группы розничных продаж в корпорации Teradata, подготовил анализ 1,2 миллиона «рыночных корзин» (то есть, покупок, сделанных одним покупателем) из примерно 25 магазинов аптекарских товаров «Osco». Были разработаны запросы к базе данных, чтобы обнаружить свойства корзин. Анализ «показал, что в интервале с 17:00 до 19:00 покупатели покупают пиво и памперсы». Управляющие аптек «Osco» НЕ использовали для получения связи пива и памперсов размещение продуктов ближе друг к другу на полках.

Другие типы обнаружения ассоциативных правил

Мультиассоциативные правила (англ. Multi-Relation Association Rules, MRAR), это ассоциативные правила, в которых каждый объект может иметь несколько связей. Эти связи показывают косвенные связи между сущностями. Рассмотрим следующее мультиассоциативное правило, в котором первый член состоит из трёх отношений живёт в, рядом и влажный: «Двое, кто живут в месте, которое находится рядом с городом с влажным климатом, и моложе 20 лет => их состояние здоровья хорошее». Такие ассоциативные правила могут быть получены из данных RDBMS или семантических данных интернета.

Основанные на контексте ассоциативные правила являются видом ассоциативных правил. Утверждается, что эти правила более точны в анализе ассоциативных правил и работают путём рассмотрения скрытой переменной, названной контекстной переменной, которая меняет конечный набор ассоциативных правил в зависимости от значений контекстных переменных. Например, ориентация на покупательную корзину в анализе рыночной корзины отражает странные результаты в начале месяца. Это может быть вызвано контекстом, таким как выдача зарплаты в начале месяца.

Контрастное обучение (англ. Contrast set learning) является видом ассоциативного обучения. Контрастное обучение использует правила, которые существенно отличаются в их распределении по подмножествам.

Взвешенное обучение классам (англ. Weighted class learning) является другим видом ассоциативного обучения, в котором веса могут быть назначены классам, чтобы перевести фокус на конкретные спорные вопросы для результатов исследования данных.

Обнаружение шаблонов высокого порядка (англ. High-order pattern discovery) способствует извлечению шаблонов высокого порядка или ассоциативных событий, свойственных данным сложного реального мира .

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

Приближённый анализ часто встречающихся наборов (англ. Approximate Frequent Itemset mining) является ослабленной версией анализа часто встречающихся наборов, в которой допускается, чтобы некоторые из объектов в некоторых строках были равны 0.

Обобщённые ассоциативные правила (англ. Generalized Association Riles) — иерархическая классификация

Количественные ассоциативные правила (англ. Quantitative Association Rules) — категориальные и количественные данные.

Интервальные ассоциативные правила (англ. Interval Data Association Rules) — содержат данные, разбитые на интервалы, например, возраст с интервалом в 5 лет.

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

Кластеризация подпространства (англ. Subspace Clustering), специфичный вид кластеризации данных высокой размерности, во многих вариантах также основывается на свойстве нисходящего замыкания для специфичных моделей кластеров.

Warmr поставляется как часть комплекта ACE для анализа данных. Система позволяет обучение ассоциативным правилам для реляционных правил первого порядка.

См. также

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

Библиография

• Extensive Bibliography on Association Rules by J.M. Luna
• Annotated Bibliography on Association Rules by M. Hahsler
• Statsoft Electronic Statistics Textbook: Association Rules (недоступная ссылка) by Dell Software