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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

Процесс

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

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

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

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

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

Недостатки

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

Пороги

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

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

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

Таблица 1. Пример порога поддержки и уверенности.

Предметы	Поддерживать	Уверенность		Предметы	Поддерживать	Уверенность
Пункт А	30%	50%		Пункт С	45%	55%
Пункт Б	15%	25%		Пункт А	30%	50%
Пункт С	45%	55%		Пункт Д	35%	40%
Пункт Д	35%	40%		Пункт Б	15%	25%

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

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

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

Полезные понятия

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

идентификатор транзакции	молоко	хлеб	масло	пиво	подгузники	яйца	фрукты
1	1	1	0	0	0	0	1
2	0	0	1	0	0	1	1
3	0	0	0	1	1	0	0
4	1	1	1	0	0	1	1
5	0	1	0	0	0	0	0

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

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

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

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

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

Поддерживать

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

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

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

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

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

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

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

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

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

Таблица 3. Пример поддержки и поддержки × уверенности

если антецедент, то следствие	поддерживать	поддержка X доверия
если купишь молоко, то купи хлеб	2/5= 0.4	0.4×1.0= 0.4
если покупаешь молоко, то покупай яйца	1/5= 0.2	0.2×0.5= 0.1
если купишь хлеб, то купи фрукты	2/5= 0.4	0.4×0.66= 0.264
если покупаешь фрукты, то покупай яйца	2/5= 0.4	0.4×0.66= 0.264
если купишь молоко и хлеб, то купи фрукты	2/5= 0.4	0.4×1.0= 0.4

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

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

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

Уверенность

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

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

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

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

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

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

Таблица 4. Пример уверенности и поддержки × Уверенность

если антецедент, то следствие	Уверенность	Поддержка × Уверенность
если купишь молоко, то купи хлеб	2 ⁄ 2 = 1.0	0.4×1.0= 0.4
если покупаешь молоко, то покупай яйца	1 ⁄ 2 = 0.5	0.2×0.5= 0.1
если купишь хлеб, то купи фрукты	2 ⁄ 3 ≈ 0.66	0.4×0.66= 0.264
если покупаешь фрукты, то покупай яйца	2 ⁄ 3 ≈ 0.66	0.4×0.66= 0.264
если купишь молоко и хлеб, то купи фрукты	2 ⁄ 2 = 1.0	0.4×1.0= 0.4

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

Поднимать

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

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

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

Например, правило $\{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}$ имеет лифт ${\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)}}$.

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

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

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

• Полная уверенность
• Коллективная сила
• Использовать

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

История

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

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

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

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

Алгоритмы

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

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

Априорный алгоритм

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

Схема управления алгоритмом Априори

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

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

Набор входов

{а, б}	{в, г}	{а, д}	{а, е}	{б, д}	{а, б, г}	{а, в, г}	{а, б, в, г}

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

Поддержка ценностей

а	б	с	д
6	4	3	6

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

Поддержка ценностей

{а, б}	{а, в}	{а, д}	{б, в}	{б, д}	{в, г}
3	2	4	1	3	3

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

Поддержка ценностей

{а, в, г}
2

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

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

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

Алгоритм Эклат

Светиться (альт. ECLAT, означает «Преобразование класса эквивалентности») — это алгоритм обратного отслеживания , который обходит решетчатый граф часто встречающихся элементов в режиме поиска в глубину (DFS). В то время как обход в ширину (BFS), используемый в алгоритме Apriori, в конечном итоге будет проверять каждое подмножество набора элементов перед его проверкой, обход DFS проверяет более крупные наборы элементов и может сэкономить на проверке поддержки некоторых из его подмножеств благодаря нисходящему -Близкое свойство. Более того, он почти наверняка будет использовать меньше памяти, поскольку DFS имеет меньшую сложность пространства, чем BFS.

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

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

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

FP означает частый шаблон.

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

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

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

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

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

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

Другие

АССОК

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

ОПУС поиск

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

Лор

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

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

Другие типы интеллектуального анализа правил ассоциации

Правила ассоциации с несколькими отношениями (MRAR) . Это правила ассоциации, в которых каждый элемент может иметь несколько отношений. Эти отношения указывают на косвенные отношения между сущностями. Рассмотрим следующий MRAR, где первый элемент состоит из трех отношений « живут в» , «близко» и «влажно» : «Те, кто живет в месте, расположенном недалеко от города с влажным климатом, а также моложе 20 лет. $\implies$ их состояние здоровья хорошее». Такие правила ассоциации можно извлечь из данных РСУБД или данных семантической сети.

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

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

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

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

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

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

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

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

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

Кластеризация подпространства , особый тип кластеризации многомерных данных , во многих вариантах также основана на свойстве закрытия вниз для определенных моделей кластеризации.

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

См. также

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

Ссылки

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

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