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

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

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

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

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

Определение [ править ]

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

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

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

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

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

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

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

Каждое правило состоит из двух разных наборов элементов, также известных как наборы элементов , и , где это называется предшествующим или левым (LHS) и последующим или правым (RHS).${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$

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

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

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

Полезные концепции [ править ]

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

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

Поддержка [ править ]

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

Поддержка по отношению к определяется как доля транзакций в наборе данных, который содержит набор элементов .${\displaystyle X}$${\displaystyle T}$${\displaystyle t}$${\displaystyle X}$

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

В примере набора данных набор элементов имеет поддержку, поскольку он встречается в 20% всех транзакций (1 из 5 транзакций). Аргумент - это набор предварительных условий, и поэтому он становится более ограничительным по мере его роста (вместо более широкого). ^[3]${\displaystyle X=\{\mathrm {beer,diapers} \}}$${\displaystyle 1/5=0.2}$${\displaystyle \mathrm {supp} ()}$

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

Уверенность [ править ]

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

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

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

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

Например, достоверность правила в базе данных составляет, что означает, что для 100% транзакций, содержащих масло и хлеб, правило верно (в 100% случаев, когда клиент покупает масло и хлеб, покупается и молоко).${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$${\displaystyle 0.2/0.2=1.0}$

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

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

Лифт [ править ]

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

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

Ценность подъема заключается в том, что он учитывает как поддержку правила, так и весь набор данных. ^[3]

Осуждение [ править ]

Убеждение в правило, определяется как . ^[6]${\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} \}}$

Альтернативные меры интереса [ править ]

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

• Полное доверие ^[7]
• Коллективная сила ^[8]
• Кредитное плечо ^[9]

Еще несколько показателей представлены и сравниваются Tan et al. ^[10] и Hahsler. ^[4] Поиск методов, которые могут моделировать то, что известно пользователю (и использование этих моделей в качестве меры интереса), в настоящее время является активной исследовательской тенденцией под названием «субъективная интересность».

Процесс [ править ]

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

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

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

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

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

История [ править ]

Концепция ассоциативных правил получила широкую популярность благодаря статье Agrawal et al., Опубликованной в 1993 г. ^[2], которая, по данным Google Scholar, по состоянию на август 2015 г. цитировалась более 18 000 раз, и поэтому является одной из наиболее цитируемых статей в Поле интеллектуального анализа данных. Однако то, что сейчас называется «ассоциативными правилами», было введено уже в статье 1966 года ^[15] о GUHA, общем методе интеллектуального анализа данных, разработанном Петром Хаеком и др. ^[16]

Ранним (примерно в 1989 г.) использованием минимальной поддержки и уверенности для поиска всех ассоциативных правил была структура Feature Based Modeling, которая обнаружила все правила с ограничениями, определяемыми пользователем, или превосходящими их. ^[17]${\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 правил.Статистически обоснованное открытие ассоциации^{[18] [19]} контролирует этот риск, в большинстве случаев снижая риск обнаружения любых ложных ассоциаций до заданного пользователем уровня значимости.

Алгоритмы [ править ]

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

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

Алгоритм априори [ править ]

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

Алгоритм Eclat [ править ]

Eclat ^[14] (альтернативный вариант ECLAT, означает преобразование класса эквивалентности) - это алгоритм поиска в глубину, основанный на пересечении множеств. Он подходит как для последовательного, так и для параллельного выполнения со свойствами повышения локальности. ^{[20] [21]}

Алгоритм FP-роста [ править ]

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

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

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

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

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

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

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

Другое [ править ]

ASSOC [ править ]

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

Поиск OPUS [ править ]

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

Знания [ править ]

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

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

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

Правила ассоциации множественных отношений : Правила ассоциации множественных отношений (MRAR) - это правила ассоциации, в которых каждый элемент может иметь несколько отношений. Эти отношения указывают на косвенные отношения между объектами. Рассмотрим следующую МКАД , где первый элемент состоит из трех отношений живут , поблизости и влажное : «Те , кто живет в месте , которое находится рядом город с влажным типом климата , а также моложе , чем 20 -> их состояние здоровья хорошее». Такие правила ассоциации извлекаются из данных РСУБД или данных семантической сети. ^[29]

Обучение с использованием набора контрастов - это форма ассоциативного обучения. Учащиеся с контрастным набором используют правила, которые существенно различаются по своему распределению по подмножествам. ^{[30] [31]}

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Библиографии [ править ]

• Аннотированная библиография по правилам ассоциации М. Хаслера