Изучение правил ассоциации

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

Основываясь на концепции строгих правил, Ракеш Агравал , Томаш Имелински и Арун Свами ^[2] ввели правила ассоциации для обнаружения закономерностей между продуктами в данных о крупных транзакциях, зарегистрированных системами точек продаж (POS) в супермаркетах. Например, правило, найденное в данных о продажах супермаркета, будет указывать, что если клиент покупает лук и картофель вместе, он, скорее всего, также купит мясо для гамбургера. Такая информация может быть использована в качестве основы для принятия решений о маркетинговых мероприятиях, таких как, например, рекламное ценообразование или размещение продукта .${\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \}}$

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

Сам алгоритм ассоциативных правил состоит из различных параметров, которые могут затруднить его выполнение для тех, кто не имеет определенного опыта в интеллектуальном анализе данных, при этом многие правила сложны для понимания. ^[3]

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

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

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

Каждая транзакция в D имеет уникальный идентификатор транзакции и содержит подмножество элементов в I.

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

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

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

Каждое правило состоит из двух различных наборов элементов, также известных как itemsets , X и Y , где X называется антецедентом или левой стороной (LHS), а Y консеквентом или правой стороной (RHS). Антецедент — это элемент, который можно найти в данных, в то время как консеквент — это элемент, найденный при объединении с антецедентом. Утверждение часто читается как if X then Y , где антецедент ( X ) — это if , а консеквент ( Y ) — это then . Это просто подразумевает, что в теории, всякий раз, когда X встречается в наборе данных, то Y тоже будет.${\displaystyle X\Rightarrow Y}$

Правила ассоциации создаются путем поиска данных для частых моделей if-then и использования определенного критерия в разделе Support и Confidence для определения наиболее важных отношений. Support — это свидетельство того, как часто элемент появляется в приведенных данных, поскольку Confidence определяется тем, сколько раз утверждения if-then оказываются истинными. Однако есть третий критерий, который можно использовать, он называется Lift и его можно использовать для сравнения ожидаемой Confidence и фактической Confidence. Lift покажет, сколько раз утверждение if-then, как ожидается, окажется истинным.

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

Существует множество различных методов добычи данных, которые вы можете использовать для поиска определенной аналитики и результатов, например, есть анализ классификации, кластерный анализ и регрессионный анализ. ^[4] Какой метод вы должны использовать, зависит от того, что вы ищете с вашими данными. Правила ассоциации в основном используются для поиска аналитики и прогнозирования поведения клиентов. Для анализа классификации он, скорее всего, будет использоваться для постановки вопросов, принятия решений и прогнозирования поведения. ^[5] Анализ кластеризации в основном используется, когда нет предположений о вероятных связях в данных. ^[5] Регрессионный анализ используется, когда вы хотите предсказать значение непрерывной зависимой величины из ряда независимых переменных. ^[5]

Преимущества

Использование правил ассоциации дает множество преимуществ, например, поиск закономерности, которая помогает понять корреляции и совпадения между наборами данных. Очень хорошим примером из реального мира, в котором используются правила ассоциации, может быть медицина. Медицина использует правила ассоциации для диагностики пациентов. При диагностике пациентов необходимо учитывать множество переменных, поскольку многие заболевания имеют схожие симптомы. Используя правила ассоциации, врачи могут определить условную вероятность заболевания, сравнивая взаимосвязи симптомов с прошлыми случаями. ^[6]

Недостатки

Однако правила ассоциации также приводят к множеству различных недостатков, таких как поиск соответствующих параметров и пороговых значений для алгоритма добычи данных. Но есть и недостаток в наличии большого количества обнаруженных правил. Причина в том, что это не гарантирует, что правила будут найдены релевантными, но также может привести к низкой производительности алгоритма. Иногда реализованные алгоритмы будут содержать слишком много переменных и параметров. Для тех, кто не имеет хорошего представления об добыче данных, это может вызвать трудности с ее пониманием. ^[7]

Пороги

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

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

Порог поддержки — 30%, порог уверенности — 50%.

Таблица слева — это исходные неорганизованные данные, а таблица справа организована по пороговым значениям. В этом случае элемент C лучше пороговых значений как для Поддержки, так и для Уверенности, поэтому он первый. Элемент A — второй, потому что его пороговые значения точны. Элемент D достиг порогового значения для Поддержки, но не для Уверенности. Элемент B не достиг порогового значения ни для Поддержки, ни для Уверенности, поэтому он последний.

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

Для иллюстрации концепций мы используем небольшой пример из области супермаркета. Таблица 2 показывает небольшую базу данных, содержащую элементы, где в каждой записи значение 1 означает наличие элемента в соответствующей транзакции, а значение 0 представляет отсутствие элемента в этой транзакции. Набор элементов — .${\displaystyle I=\{\mathrm {milk,bread,butter,beer,diapers,eggs,fruit} \}}$

Примером правила для супермаркета может служить следующее: если покупаются масло и хлеб, покупатели также покупают молоко.${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$

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

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

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

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

В нашем примере поддержку можно проще объяснить, записав ^[12] , где A и B — это отдельные наборы элементов, которые встречаются в транзакции одновременно.${\displaystyle {\text{support}}=P(A\cup B)={\frac {({\text{number of transactions containing }}A{\text{ and }}B)}{\text{ (total number of transactions)}}}}$

Используя Таблицу 2 в качестве примера, набор элементов имеет поддержку 1/5=0,2, поскольку он встречается в 20% всех транзакций (1 из 5 транзакций). Аргумент поддержки X — это набор предварительных условий, и, таким образом, он становится более ограничительным по мере роста (вместо того, чтобы быть более инклюзивным). ^[13]${\displaystyle X=\{\mathrm {beer,diapers} \}}$

Более того, набор элементов имеет поддержку 1/5=0,2, поскольку он также появляется в 20% всех транзакций.${\displaystyle Y=\{\mathrm {milk,bread,butter} \}}$

При использовании антецедентов и консеквентов это позволяет майнеру данных определить поддержку нескольких товаров, покупаемых вместе, по сравнению со всем набором данных. Например, Таблица 2 показывает, что если покупается молоко, то покупается хлеб, имеет поддержку 0,4 или 40%. Это потому, что в 2 из 5 транзакций покупается как молоко, так и хлеб. В меньших наборах данных, таких как этот пример, сложнее увидеть сильную корреляцию, когда выборок мало, но когда набор данных становится больше, поддержку можно использовать для поиска корреляции между двумя или более товарами в примере с супермаркетом.

Минимальные пороговые значения поддержки полезны для определения того, какие наборы элементов предпочтительны или интересны.

Если мы установим порог поддержки ≥0,4 в Таблице 3, то будет удален, поскольку он не соответствует минимальному порогу 0,4. Минимальный порог используется для удаления образцов, где нет достаточно сильной поддержки или уверенности, чтобы считать образец важным или интересным в наборе данных.${\displaystyle \{\mathrm {milk} \}\Rightarrow \{\mathrm {eggs} \}}$

Другой способ поиска интересных образцов — найти значение (поддержка)×(уверенность); это позволяет исследователю данных увидеть образцы, в которых поддержка и уверенность достаточно высоки, чтобы быть выделенными в наборе данных, и побудить более внимательно рассмотреть образец, чтобы найти больше информации о связи между элементами.

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

Поддержка X относительно T определяется как доля транзакций в наборе данных, содержащих набор элементов X. Обозначая транзакцию как , где i — уникальный идентификатор транзакции, а t — ее набор элементов, поддержка может быть записана как:${\displaystyle (i,t)}$

${\displaystyle \mathrm {support\,of\,X} ={\frac {|\{(i,t)\in T:X\subseteq t\}|}{|T|}}}$

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

Уверенность — это процент всех транзакций, удовлетворяющих X , которые также удовлетворяют Y. ^[14 ]

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

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

Обычно его изображают так:

${\displaystyle \mathrm {conf} (X\Rightarrow Y)=P(Y|X)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)}}={\frac {{\text{number of transactions containing }}X{\text{ and }}Y}{{\text{number of transactions containing }}X}}}$

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

Например, в таблице 2 показано правило , имеющее достоверность в наборе данных, что означает, что каждый раз, когда клиент покупает масло и хлеб, он также покупает молоко. Этот конкретный пример демонстрирует, что правило верно в 100% случаев для транзакций, содержащих как масло, так и хлеб. Однако правило имеет достоверность . Это говорит о том, что яйца покупаются в 67% случаев, когда приносятся фрукты. В этом конкретном наборе данных фрукты покупаются в общей сложности 3 раза, причем два из этих случаев состоят из покупок яиц.${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$${\displaystyle {\frac {1/5}{1/5}}={\frac {0.2}{0.2}}=1.0}$${\displaystyle \{\mathrm {fruit} \}\Rightarrow \{\mathrm {eggs} \}}$${\displaystyle {\frac {2/5}{3/5}}={\frac {0.4}{0.6}}=0.67}$

Для больших наборов данных минимальный порог или процентное отсечение для достоверности может быть полезным для определения взаимосвязей элементов. При применении этого метода к некоторым данным в Таблице 2 информация, которая не соответствует требованиям, удаляется. Таблица 4 показывает примеры правил ассоциации, где минимальный порог для достоверности составляет 0,5 (50%). Любые данные, которые не имеют достоверности не менее 0,5, опускаются. Создание порогов позволяет сделать связь между элементами сильнее по мере дальнейшего исследования данных, подчеркивая те, которые встречаются чаще всего. Таблица использует информацию об достоверности из Таблицы 3 для реализации столбца Поддержка × Достоверность, где выделяется связь между элементами через их как достоверность, так и поддержку, а не только одну концепцию. Ранжирование правил по Поддержке × Достоверность умножает достоверность конкретного правила на его поддержку и часто применяется для более глубокого понимания взаимосвязи между элементами.

В целом, использование уверенности в извлечении правил ассоциации — отличный способ повысить осведомленность об отношениях данных. Его наибольшее преимущество заключается в выделении взаимосвязи между отдельными элементами в наборе, поскольку он сравнивает совместные появления элементов с общей встречаемостью антецедента в конкретном правиле. Однако уверенность не является оптимальным методом для каждой концепции извлечения правил ассоциации. Недостатком его использования является то, что он не предлагает множественных различных точек зрения на ассоциации. В отличие от поддержки, например, уверенность не обеспечивает перспективу взаимосвязей между определенными элементами по сравнению со всем набором данных, поэтому, хотя молоко и хлеб, например, могут встречаться в 100% случаев для уверенности, они имеют поддержку только 0,4 (40%). Вот почему важно рассматривать другие точки зрения, такие как Поддержка × Уверенность, вместо того, чтобы полагаться исключительно на одну концепцию непрерывно для определения взаимосвязей.

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

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

или отношение наблюдаемой поддержки к ожидаемой, если бы X и Y были независимы .

Например, правило имеет подъем .${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$${\displaystyle {\frac {0.2}{0.4\times 0.4}}=1.25}$

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

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

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

Ценность лифта в том, что он учитывает как поддержку правила, так и общий набор данных. ^[13]

[переделать]

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

Например, правило имеет убежденность , и может быть интерпретировано как отношение ожидаемой частоты того, что X встречается без Y (то есть частоты того, что правило делает неверный прогноз), если X и Y были бы независимы, деленное на наблюдаемую частоту неверных прогнозов. В этом примере значение убежденности 1,2 показывает, что правило будет неверным на 20% чаще (в 1,2 раза чаще), если бы связь между X и Y была чисто случайной.${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$${\displaystyle {\frac {1-0.4}{1-0.5}}=1.2}$${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$

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

• Всеуверенность ^[17]
• Коллективная сила ^[18]
• Кредитное плечо ^[19]

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

Концепция правил ассоциации была популяризирована, в частности, благодаря статье 1993 года Агравала и др. ^[2] , которая по состоянию на апрель 2021 года получила более 23 790 ссылок по данным Google Scholar и, таким образом, является одной из самых цитируемых статей в области интеллектуального анализа данных. Однако то, что сейчас называется «правилами ассоциации», было введено уже в статье 1966 года ^[22] о GUHA, общем методе интеллектуального анализа данных, разработанном Петром Гаеком и др. ^[23]

Ранним (около 1989 г.) применением минимальной поддержки и уверенности для поиска всех правил ассоциации является фреймворк Feature Based Modeling, который находил все правила с ограничениями, определенными пользователем, и превышающими их. ^[24]${\displaystyle \mathrm {supp} (X)}$${\displaystyle \mathrm {conf} (X\Rightarrow Y)}$

Одним из ограничений стандартного подхода к обнаружению ассоциаций является то, что при поиске огромного количества возможных ассоциаций для поиска наборов элементов, которые кажутся связанными, существует большой риск обнаружения множества ложных ассоциаций. Это наборы элементов, которые встречаются в данных с неожиданной частотой, но делают это только случайно. Например, предположим, что мы рассматриваем набор из 10 000 элементов и ищем правила, содержащие два элемента в левой части и 1 элемент в правой части. Существует приблизительно 1 000 000 000 000 таких правил. Если мы применим статистический тест на независимость с уровнем значимости 0,05, это означает, что существует только 5% вероятность принятия правила, если нет никакой ассоциации. Если мы предположим, что нет никаких ассоциаций, мы тем не менее должны ожидать найти 50 000 000 000 правил. Статистически обоснованное обнаружение ассоциаций ^{[25] [26]} контролирует этот риск, в большинстве случаев снижая риск обнаружения любых ложных ассоциаций до указанного пользователем уровня значимости.

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

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

Apriori был дан Р. Агравалом и Р. Шрикантом в 1994 году для добычи частых наборов элементов и обучения правилам ассоциации. Он осуществляется путем идентификации частых отдельных элементов в базе данных и их распространения на все большие и большие наборы элементов, пока эти наборы элементов появляются достаточно часто. Название алгоритма — Apriori, потому что он использует предварительные знания о свойствах частых наборов элементов.

Обзор: Apriori использует подход «снизу вверх», при котором частые подмножества расширяются по одному элементу за раз (шаг, известный как генерация кандидатов ), а группы кандидатов проверяются по данным. Алгоритм завершается, когда не найдено никаких дальнейших успешных расширений. Apriori использует поиск в ширину и структуру хэш-дерева для эффективного подсчета наборов элементов-кандидатов. Он генерирует наборы элементов-кандидатов длины из наборов элементов длины . Затем он отсекает кандидатов, которые имеют нечастый шаблон подмножества. Согласно лемме о нисходящем замыкании, набор кандидатов содержит все частые наборы элементов длины. После этого он сканирует базу данных транзакций, чтобы определить частые наборы элементов среди кандидатов.

Пример: Предположим, что каждая строка — это образец рака с определенной комбинацией мутаций, обозначенных символом в алфавите. Например, строка может иметь {a, c}, что означает, что она затронута мутацией 'a' и мутацией 'c'.

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

Поскольку все значения поддержки равны трем или выше, обрезки не происходит. Часто встречающийся набор элементов — {a}, {b}, {c} и {d}. После этого мы повторим процесс, подсчитав пары мутаций во входном наборе.

Теперь мы сделаем наше минимальное значение поддержки равным 4, так что после обрезки останутся только {a, d}. Теперь мы будем использовать набор частых элементов для создания комбинаций триплетов. Затем мы повторим процесс, подсчитывая вхождения триплетов мутаций во входном наборе.

Поскольку у нас есть только один элемент, следующий набор комбинаций четверок пуст, поэтому алгоритм остановится.

Преимущества и ограничения:

Apriori имеет некоторые ограничения. Генерация кандидатов может привести к большим наборам кандидатов. Например, 10^4 частый набор из 1 элемента сгенерирует 10^7 набор из 2 элементов. Алгоритм также должен часто сканировать базу данных, а именно n+1 сканирований, где n — длина самого длинного шаблона. Apriori медленнее алгоритма Eclat. Однако Apriori работает хорошо по сравнению с Eclat, когда набор данных большой. Это связано с тем, что в алгоритме Eclat, если набор данных слишком большой, списки tid становятся слишком большими для памяти. FP-growth превосходит Apriori и Eclat. Это связано с тем, что алгоритм FP-growth не имеет генерации или проверки кандидатов, использует компактную структуру данных и имеет только одно сканирование базы данных. ^[27]

Eclat ^[11] (альтернативный ECLAT, сокращение от Equivalence Class Transformation) — это алгоритм обратного отслеживания , который обходит часто встречающийся граф решетки наборов элементов в режиме поиска в глубину (DFS). В то время как обход поиска в ширину (BFS), используемый в алгоритме Apriori, в конечном итоге проверит каждое подмножество набора элементов перед его проверкой, обход DFS проверяет более крупные наборы элементов и может сэкономить на проверке поддержки некоторых из его подмножеств в силу свойства downward-closer. Кроме того, он почти наверняка будет использовать меньше памяти, поскольку DFS имеет меньшую пространственную сложность, чем BFS.

Чтобы проиллюстрировать это, пусть есть частый набор элементов {a, b, c}. DFS может проверять узлы в решетке частых наборов элементов в следующем порядке: {a} → {a, b} → {a, b, c}, в этот момент известно, что {b}, {c}, {a, c}, {b, c} все удовлетворяют ограничению поддержки по свойству нисходящего замыкания. BFS будет исследовать каждое подмножество {a, b, c} перед окончательной проверкой. По мере увеличения размера набора элементов число его подмножеств претерпевает комбинаторный взрыв .

Он подходит как для последовательного, так и для параллельного выполнения со свойствами, улучшающими локальность. ^{[28] [29]}

FP означает частый паттерн. ^[30]

В первом проходе алгоритм подсчитывает вхождения элементов (пары атрибут-значение) в наборе данных транзакций и сохраняет эти подсчеты в «таблице заголовков». Во втором проходе он строит структуру FP-дерева, вставляя транзакции в trie .

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

Рекурсивная обработка этой сжатой версии основного набора данных напрямую увеличивает наборы частых элементов вместо генерации элементов-кандидатов и их тестирования по всей базе данных (как в алгоритме apriori).

Рост начинается с нижней части таблицы заголовков, т.е. с элемента с наименьшей поддержкой, путем поиска всех отсортированных транзакций, которые заканчиваются этим элементом. Назовем этот элемент .${\displaystyle I}$

Создается новое условное дерево, которое является исходным FP-деревом, спроецированным на . Поддержки всех узлов в спроецированном дереве пересчитываются, и каждый узел получает сумму своих дочерних счетчиков. Узлы (и, следовательно, поддеревья), которые не соответствуют минимальной поддержке, отсекаются. Рекурсивный рост заканчивается, когда ни один из отдельных элементов, условных на которых, не соответствует минимальному порогу поддержки. Результирующие пути от корня до будут частыми наборами элементов. После этого шага обработка продолжается со следующим наименее поддерживаемым элементом заголовка исходного FP-дерева.${\displaystyle I}$${\displaystyle I}$${\displaystyle I}$

После завершения рекурсивного процесса будут найдены все часто встречающиеся наборы элементов и начнется создание правила ассоциации. ^[31]

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

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

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

В 1992 году Томас Блишок, менеджер группы розничного консалтинга в Teradata , и его сотрудники подготовили анализ 1,2 миллиона потребительских корзин из примерно 25 магазинов Osco Drug. Были разработаны запросы к базе данных для выявления сходств. Анализ «выявил, что между 5:00 и 7:00 вечера потребители покупали пиво и подгузники». Менеджеры Osco НЕ использовали связь пива и подгузников, размещая продукты ближе друг к другу на полках.

Правила ассоциации с множественными отношениями (MRAR) : Это правила ассоциации, в которых каждый элемент может иметь несколько отношений. Эти отношения указывают на косвенные отношения между сущностями. Рассмотрим следующий MRAR, где первый элемент состоит из трех отношений жить в , рядом и влажный : «Те, кто живет в месте, которое находится недалеко от города с влажным типом климата, и также моложе 20 лет, их состояние здоровья хорошее». Такие правила ассоциации можно извлечь из данных RDBMS или данных семантической сети. ^[37]${\displaystyle \implies }$

Обучение на контрастных наборах является формой ассоциативного обучения. Обучающиеся на контрастных наборах используют правила, которые существенно различаются по своему распределению по подмножествам. ^{[38] [39]}

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

Обнаружение закономерностей высокого порядка облегчает захват закономерностей высокого порядка (политетических) или ассоциаций событий, которые присущи сложным данным реального мира. ^[40]

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

Приблизительный анализ набора часто встречающихся элементов — это упрощенная версия анализа набора часто встречающихся элементов, которая допускает, чтобы некоторые элементы в некоторых строках были равны 0. ^[41]

Обобщенные правила ассоциации иерархическая таксономия (иерархия понятий)

Количественные правила ассоциации категориальных и количественных данных

Правила ассоциации интервальных данных , например, разбиение возраста на 5-летние интервалы

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

Подпространственная кластеризация , особый тип кластеризации многомерных данных , во многих вариантах также основана на свойстве нисходящего замыкания для определенных моделей кластеризации. ^[43]

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

• Последовательная добыча
• Производственная система (информатика)
• Система классификаторов обучения
• Машинное обучение на основе правил

• Аннотированная библиография по правилам ассоциации, архив 2017-02-19 в Wayback Machine М. Хаслера