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

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

Опираясь на концепцию строгих правил, Ракеш Агравал, Томаш Имелинский и Арун Свами ^[3] выдвинули ассоциативные правила для обнаружения закономерностей между продуктами в транзакциях большого размера для данных, записанных системами 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

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

Пусть дан набор $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$ .

В статье Агравала, Имелинского, Свами ^[4] правило определяется только между множеством и одиночным объектом $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} ()$ является множеством предусловий и потому становится более ограничивающим по мере расширения (в отличие от более охватывающего)^[5].

Доверие

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

Значение доверия правила $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$ соответственно.^[6]

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

Лифт

Лифт^[англ.] правила определяется как:

$\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, это означает, что объекты заменяют друг друга. Это означает, что наличие одного объекта имеет отрицательный эффект на присутствие второго объекта, и наоборот.

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

Уверенность

Уверенность правила определяется как $\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)

. Это называется свойством нисходящего замыкания^[4].

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

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

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

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

История

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

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

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

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

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

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

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

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

Алгоритмы

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

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

Алгоритм Apriori

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

Алгоритм Eclat

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

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

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

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

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

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

Другие

AprioriDP

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

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

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

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

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

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

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

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

Поиск OPUS

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

Предания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

↑ Piatetsky-Shapiro, 1991.
↑ How Does Association Learning Work? (неопр.) deepai.org. Дата обращения: 11 ноября 2018. Архивировано 17 февраля 2019 года.
↑ ¹ ² Agrawal, Imieliński, Swami, 1993, с. 207.
↑ ¹ ² ³ ⁴ Tan, Steinbach, Kumar, 2005.
↑ ¹ ² ³ Hahsler, 2005.
↑ ¹ ² Michael Hahsler (2015). A Probabilistic Comparison of Commonly Used Interest Measures for Association Rules. http://michael.hahsler.net/research/association_rules/measures.html Архивная копия от 2 августа 2018 на Wayback Machine
↑ Hipp, Güntzer, Nakhaeizadeh, 2000, с. 58.
↑ Pei, Han, Lakshmanan, 2001, с. 433-442.
↑ ¹ ² Agrawal, Srikant, 1994, с. 487-499.
↑ ¹ ² Zaki, 2000, с. 372–390.
↑ Hájek, Havel, Chytil, 1966, с. 293-308.
↑ Hájek, Feglar, Rauch, Coufal, 2004.
↑ Webb, 1989, с. 195–205.
↑ Omiecinski, 2003, с. 57-69.
↑ Aggarwal, Yu, 1998, с. 18-24.
↑ Brin, Motwani, Ullman, Tsur, 1997, с. 255-264.
↑ Piatetsky-Shapiro, 1991, с. 229-248.
↑ Brin, Motwani, Ullman, Tsur, 1997, с. 265-276.
↑ Tan, Kumar, Srivastava, 2004, с. 293-313.
↑ Webb, 2007, с. 1-33.
↑ Gionis, Mannila, Mielikäinen, Tsaparas, 2007.
↑ Zaki, Parthasarathy, Ogihara, Li, 1997.
↑ Zaki, Parthasarathy, Ogihara, Li, 1997, с. 343-373.
↑ HAN, PEI, YIN, MAO, 2000, с. 1–12.
↑ Witten, Frank, Hall: Data mining practical machine learning tools and techniques, 3rd edition
↑ Bhalodiya, Patel, Patel, 2013.
↑ Deng, Lv, 2014, с. 4505–4512.
↑ Deng, Wang, Jiang, 2012, с. 2008-2030.
↑ Deng, Wang, 2010, с. 733 – 744.
↑ Rauch, 1997, с. 47-57.
↑ Hájek, Havránek, 1978.
↑ Webb, 1995, с. 431-465.
↑ ¹ ² DSS News: Vol. 3, No. 23 (неопр.). Дата обращения: 11 ноября 2018. Архивировано 6 ноября 2018 года.
↑ Ramezani, Saraee, Nematbakhsh, 2014, с. 133-158.
↑ Shaheen, Shahbaz, Guergachi, 2013, с. 261-273.
↑ Webb, Butler, Newlands, 2003.
↑ Menzies, Hu, 2003, с. 18-25.
↑ Wong, Wang, 1997, с. 877–893.
↑ Liu, Paulsen, Sun, Wang, Nobel, Prins, 2006.
↑ Angiulli, Ianni, Palopoli, 2003, с. 217–249.
↑ Salleb-Aouissi, Vrain, Nortet, 2007, с. 1035–1040.
↑ Zaki, 2001, с. 31–60.
↑ Zimek, Assent, Vreeken, 2014, с. 403–423.
↑ King, Srinivasan, Dehaspe, 2001, с. 173–81.

Литература

Gregory Piatetsky-Shapiro. Discovery, analysis, and presentation of strong rules // Knowledge Discovery in Databases / Piatetsky-Shapiro, Gregory; and Frawley, William J.. — Cambridge, MA.: AAAI/MIT Press, 1991.
Michael Hahsler. Introduction to arules – A computational environment for mining association rules and frequent item sets // Journal of Statistical Software. — 2005.
Hipp J., Güntzer U., Nakhaeizadeh G. Algorithms for association rule mining --- a general survey and comparison // ACM SIGKDD Explorations Newsletter. — 2000. — Т. 2. — doi:10.1145/360402.360421.
Reza Ramezani, Mohamad Saraee, Mohammad Ali Nematbakhsh. MRAR: Mining Multi-Relation Association Rules // Journal of Computing and Security. — 2014. — Т. 1, № no. 2.
Agrawal R., Imieliński T., Swami A. Mining association rules between sets of items in large databases // Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. — 1993. — ISBN 0897915925. — doi:10.1145/170035.170072.
JIAWEI HAN, JIAN PEI, YIWEN YIN, RUNYING MAO. Mining Frequent Patterns Without Candidate Generation // Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. — 2000. — Т. SIGMOD '00. — С. 1–12. — doi:10.1145/342009.335372.
- JIAWEI HAN, JIAN PEI, YIWEN YIN, RUNYING MAO. Mining Frequent Patterns Without Candidate Generation // Data Mining and Knowledge Discovery. — 2004. — Вып. 8. — С. 53–87.
Edward R. Omiecinski. Alternative interest measures for mining associations in databases // IEEE Transactions on Knowledge and Data Engineering. — 2003. — Jan/Feb (т. 15, вып. 1).
Charu C. Aggarwal, Philip S. Yu. A new framework for itemset generation // PODS 98, Symposium on Principles of Database Systems, Seattle, WA, USA, 1998. — New York, NY, United States: ACM, 1998. — С. 18-24.
Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, Shalom Tsur. Dynamic itemset counting and implication rules for market basket data // SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997). — Tucson, Arizona, USA, 1997.
Petr Hájek, Ivan Havel, Metoděj Chytil. The GUHA method of automatic hypotheses determination // Computing. — 1966. — Вып. 1.
Petr Hájek, Tomas Feglar, Jan Rauch, David Coufal. The GUHA method, data preprocessing and mining // Database Support for Data Mining Applications. — Springer, 2004. — ISBN 978-3-540-22479-2.
Geoffrey Webb. A Machine Learning Approach to Student Modelling // Proceedings of the Third Australian Joint Conference on Artificial Intelligence (AI 89). — 1989.
Pang-Ning Tan, Vipin Kumar, Jaideep Srivastava. Selecting the right objective measure for association analysis // Information Systems. — 2004. — Т. 29, вып. 4.
Shaheen M., Shahbaz M., Guergachi A. Context Based Positive and Negative Spatio Temporal Association Rule Mining // Elsevier Knowledge-Based Systems. — 2013.
Jan Rauch. Logical calculi for knowledge discovery in databases // Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery. — Springer, 1997.
Petr Hájek, Tomáš Havránek. Mechanizing Hypothesis Formation: Mathematical Foundations for a General Theory. — Springer-Verlag, 1978. — ISBN 3-540-08738-9.
Geoffrey I. Webb. online access OPUS: An Efficient Admissible Algorithm for Unordered Search // Journal of Artificial Intelligence Research 3. — Menlo Park, CA: AAAI Press, 1995.
Roberto J. Bayardo Jr., Rakesh Agrawal, Dimitrios Gunopulos. Constraint-based rule mining in large, dense databases // Data Mining and Knowledge Discovery. — 2000. — Т. 4, вып. 2. — doi:10.1023/A:1009895914772.
Webb G.I., Butler S., Newlands D. On Detecting Differences Between Groups // KDD'03 Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — 2003.
Tim Menzies, Ying Hu. Data Mining for Very Busy People // IEEE Computer. — 2003. — Октябрь.
Andrew K.C. Wong, Yang Wang. High-order pattern discovery from discrete-valued data // IEEE Transactions on Knowledge and Data Engineering (TKDE). — 1997.
Fabrizio Angiulli, Giovambattista Ianni, Luigi Palopoli. On the complexity of inducing categorical and quantitative association rules // Theoretical Computer Science. — 2003. — Т. 314, вып. 1-2. — doi:10.1016/j.tcs.2003.12.017.
Ansaf Salleb-Aouissi, Christel Vrain, Cyril Nortet. QuantMiner: A Genetic Algorithm for Mining Quantitative Association Rules // International Joint Conference on Artificial Intelligence (IJCAI). — 2007.
Mohammed J. Zaki. SPADE: An Efficient Algorithm for Mining Frequent Sequences // Machine Learning Journal. — 2001. — Вып. 42.
Geoffrey I. Webb. Efficient Search for Association Rules // Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000) Boston, MA, New York, NY / Raghu Ramakrishnan, Sal Stolfo. — The Association for Computing Machinery, 2000.
Mohammed Javeed Zaki, Srinivasan Parthasarathy, M. Ogihara, Wei Li. New Algorithms for Fast Discovery of Association Rules // KDD. — 1997.
Arthur Zimek, Ira Assent, Jilles Vreeken. Frequent Pattern Mining Algorithms for Data Clustering. — 2014. — doi:10.1007/978-3-319-07821-2_16.
King R.D., Srinivasan A., Dehaspe L. Warmr: a data mining tool for chemical data. // J Comput Aided Mol Des. — 2001. — Февраль (т. 15, вып. 2). — PMID 11272703.
Geoffrey I. Webb. Discovering Significant Patterns // Machine Learning. — Netherlands: Springer, 2007. — Т. 68, вып. 1.
Aristides Gionis, Heikki Mannila, Taneli Mielikäinen, Panayiotis Tsaparas. Assessing Data Mining Results via Swap Randomization // ACM Transactions on Knowledge Discovery from Data (TKDD). — 2007. — Декабрь (т. 1, вып. 3). Article No. 14
Jinze Liu, Susan Paulsen, Xing Sun, Wei Wang, Andrew Nobel, Jin Prins. Mining approximate frequent itemsets in the presence of noise: Algorithm and analysis. // Proceedings of the 2006 SIAM International Conference on Data Mining. — 2006.
Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li. Parallel Algorithms for Discovery of Association Rules // Data Mining and Knowledge Discovery. — 1997. — Т. 1, вып. 4.
Deng Z. H., Lv S. L. Fast mining frequent itemsets using Nodesets // Expert Systems with Applications. — 2014. — Т. 41, вып. 10. — С. 4505–4512.
Deng Z. H., Wang Z., Jiang J. A New Algorithm for Fast Mining Frequent Itemsets Using N-Lists // SCIENCE CHINA Information Sciences. — 2012. — Т. 55, вып. 9. Архивировано 19 декабря 2013 года.

Deng Z. H., Wang Z. A New Fast Vertical Method for Mining Frequent Patterns // International Journal of Computational Intelligence Systems. — 2010. — Т. 3, вып. 6.

Bhalodiya D., Patel K. M., Patel C. An Efficient way to Find Frequent Pattern with Dynamic Programming Approach // NIRMA UNIVERSITY INTERNATIONAL CONFERENCE ON ENGINEERING, NUiCONE-2013 28-30 NOVEMBER. — 2013.
Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Chapter 6. Association Analysis: Basic Concepts and Algorithms // Introduction to Data Mining. — Addison-Wesley, 2005. — ISBN 0-321-32136-7.
Jian Pei, Jiawei Han, Laks V. S. Lakshmanan. Mining frequent itemsets with convertible constraints // Proceedings of the 17th International Conference on Data Engineering, April 2–6, 2001, Heidelberg, Germany. — 2001.
Rakesh Agrawal, Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases // Proceedings of the 20th International Conference on Very Large Data Bases (VLDB) Santiago, Chile, September / Jorge B.Bocca; Matthias Jark; Carlo Zaniolo. — 1994. Архивная копия от 25 февраля 2015 на Wayback Machine
Zaki M. J. Scalable algorithms for association mining // IEEE Transactions on Knowledge and Data Engineering. — 2000. — Т. 12, вып. 3. — doi:10.1109/69.846291.

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

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

[_d677e273170d3e9c-1] Piatetsky-Shapiro, 1991.

[2] How Does Association Learning Work? (неопр.) deepai.org. Дата обращения: 11 ноября 2018. Архивировано 17 февраля 2019 года.

[_ca9e5fc54f1e8149-3] ¹ ² Agrawal, Imieliński, Swami, 1993, с. 207.

[_7a4f401d65f1b26a-4] ¹ ² ³ ⁴ Tan, Steinbach, Kumar, 2005.

[_d6bf1b947c42cfad-5] ¹ ² ³ Hahsler, 2005.

[michael.hahsler.net-6] ¹ ² Michael Hahsler (2015). A Probabilistic Comparison of Commonly Used Interest Measures for Association Rules. http://michael.hahsler.net/research/association_rules/measures.html Архивная копия от 2 августа 2018 на Wayback Machine

[_9b4d235ec9a9fca9-7] Hipp, Güntzer, Nakhaeizadeh, 2000, с. 58.

[_6a2acffc3f8ef874-8] Pei, Han, Lakshmanan, 2001, с. 433-442.

[_cb10c5a1b4867c5b-9] ¹ ² Agrawal, Srikant, 1994, с. 487-499.

[_f3dea3fbd1c9cee9-10] ¹ ² Zaki, 2000, с. 372–390.

[_67c70e10cddacbe8-11] Hájek, Havel, Chytil, 1966, с. 293-308.

[_8bf6cc9c381c30e3-12] Hájek, Feglar, Rauch, Coufal, 2004.

[_133f1f5542674ef9-13] Webb, 1989, с. 195–205.

[_b8d855724e81d7dd-14] Omiecinski, 2003, с. 57-69.

[_8cd5767918300552-15] Aggarwal, Yu, 1998, с. 18-24.

[_12742ca943474011-16] Brin, Motwani, Ullman, Tsur, 1997, с. 255-264.

[_5735aadc10680eb4-17] Piatetsky-Shapiro, 1991, с. 229-248.

[_af1a57262a760aad-18] Brin, Motwani, Ullman, Tsur, 1997, с. 265-276.

[_e49e9fa9e7dfb5dc-19] Tan, Kumar, Srivastava, 2004, с. 293-313.

[_83158a7911bfe510-20] Webb, 2007, с. 1-33.

[_e6192e2de5239884-21] Gionis, Mannila, Mielikäinen, Tsaparas, 2007.

[_9e709c99e664e9dc-22] Zaki, Parthasarathy, Ogihara, Li, 1997.

[_c49862f773194082-23] Zaki, Parthasarathy, Ogihara, Li, 1997, с. 343-373.

[_a61f484ee8795d14-24] HAN, PEI, YIN, MAO, 2000, с. 1–12.

[25] Witten, Frank, Hall: Data mining practical machine learning tools and techniques, 3rd edition

[_a59eda412c7fbff8-26] Bhalodiya, Patel, Patel, 2013.

[_cbee1f8301590b5b-27] Deng, Lv, 2014, с. 4505–4512.

[_f26376438b863192-28] Deng, Wang, Jiang, 2012, с. 2008-2030.

[_84f55a3cedf3421e-29] Deng, Wang, 2010, с. 733 – 744.

[_2c4963ad18f916a6-30] Rauch, 1997, с. 47-57.

[_b35bef4e02079ad5-31] Hájek, Havránek, 1978.

[_a3c851c7bf0bc277-32] Webb, 1995, с. 431-465.

[dss-33] ¹ ² DSS News: Vol. 3, No. 23 (неопр.). Дата обращения: 11 ноября 2018. Архивировано 6 ноября 2018 года.

[_4d29efac8eb85898-34] Ramezani, Saraee, Nematbakhsh, 2014, с. 133-158.

[_73c1e60b4b669bd9-35] Shaheen, Shahbaz, Guergachi, 2013, с. 261-273.

[_51ba4c1fdae3d6ee-36] Webb, Butler, Newlands, 2003.

[_711a3c684a0f661f-37] Menzies, Hu, 2003, с. 18-25.

[_7c984b3ae65c5e5e-38] Wong, Wang, 1997, с. 877–893.

[_4cd8209cc8998fb0-39] Liu, Paulsen, Sun, Wang, Nobel, Prins, 2006.

[_6e124de762040e86-40] Angiulli, Ianni, Palopoli, 2003, с. 217–249.

[_e097fc04c03408b4-41] Salleb-Aouissi, Vrain, Nortet, 2007, с. 1035–1040.

[_b363e56c3b6c00d2-42] Zaki, 2001, с. 31–60.

[_84f8114535ab7d53-43] Zimek, Assent, Vreeken, 2014, с. 403–423.

[_562504cbf8f7037c-44] King, Srinivasan, Dehaspe, 2001, с. 173–81.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]