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

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

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

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

Определение

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

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

Позвольте быть набором двоичных атрибутов, называемых элементами .

Пусть будет набор транзакций, называемый базой данных .

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

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

, где .

В Агравале, Имиелински, Свами правило определяется только между набором и одним предметом, так как .

Каждое правило состоит из двух разных наборов элементов, также известных как наборы элементов , и , где это называется антецедент или левая сторона (LHS) и последующая или правая сторона (RHS).

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

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

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

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

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

Позвольте быть наборами элементов, правилом ассоциации и набором транзакций данной базы данных.

Служба поддержки

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

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

В примере набора данных набор элементов имеет поддержку, поскольку он встречается в 20% всех транзакций (1 из 5 транзакций). Аргумент - это набор предварительных условий, и поэтому он становится более ограничительным по мере его роста (вместо более широкого).

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

Уверенность

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

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

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

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

Обратите внимание, что это означает поддержку объединения элементов в X и Y. Это несколько сбивает с толку, поскольку мы обычно думаем в терминах вероятностей событий, а не наборов элементов. Мы можем переписать как вероятность , где и - события, которые транзакция содержит itemset и , соответственно.

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

Поднимать

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

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

Например, у правила есть подъем .

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

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

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

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

Убеждение

Убеждение в правило, определяется как .

Например, правило убедительно и может быть интерпретировано как отношение ожидаемой частоты, с которой X встречается без Y (то есть частота, с которой правило делает неверный прогноз), если X и Y были независимыми, деленными на наблюдаемая частота неверных прогнозов. В этом примере значение убедительности 1,2 показывает, что правило было бы неверным на 20% чаще (в 1,2 раза чаще), если бы связь между X и Y была чисто случайной.

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

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

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

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

Процесс

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

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

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

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

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

История

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

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

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

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

Алгоритмы

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

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

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

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

Алгоритм Eclat

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

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

FP означает частый паттерн.

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

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

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

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

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

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

Другие

АССОК

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

OPUS поиск

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

Лор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

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