Изучение правил ассоциации - Википедия - Association rule learning

Изучение правил ассоциации это машинное обучение на основе правил метод обнаружения интересных отношений между переменными в больших базах данных. Он предназначен для выявления строгих правил, обнаруженных в базах данных, с использованием некоторых мер интереса.^[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}$.

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

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

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

Пример правила для супермаркета: ${ displaystyle { mathrm {масло, хлеб} } Rightarrow { mathrm {молоко} }}$ Это означает, что если покупаются масло и хлеб, клиенты покупают и молоко.

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

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

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

Позволять ${ 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 substeq t } |} {| T |}}}$

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

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

Уверенность

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

В уверенность ценность правила, ${ Displaystyle X Rightarrow Y}$ , по набору транзакций ${ displaystyle T}$, - доля транзакций, содержащих ${ displaystyle X}$ который также содержит ${ displaystyle Y}$.

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

${ Displaystyle mathrm {conf} (X Rightarrow Y) = mathrm {Supp} (X cup Y) / mathrm {Supp} (X)}$

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

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

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

Поднимать

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

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

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

Например, правило ${ displaystyle { mathrm {молоко, хлеб} } Rightarrow { mathrm {масло} }}$ есть лифт ${ displaystyle { frac {0,2} {0,4 times 0,4}} = 1,25}$.

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

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

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

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

Убеждение

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

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

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

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

• Полное доверие^[8]
• Коллективная сила^[9]
• Использовать^[10]

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

Процесс

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

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

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

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

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

История

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

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

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

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

Алгоритмы

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

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

Алгоритм априори

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

Алгоритм Eclat

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

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

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

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

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

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

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

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

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

Другие

АССОК

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

Поиск OPUS

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

Лор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

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

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