Введение

Метод обнаружения интересных связей между переменными в базах данных

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

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

+ Таблица 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 0 Для иллюстрации концепций мы используем небольшой пример из области супермаркетов. Таблица 2 демонстрирует небольшую базу данных, содержащую позиции, где значение 1 в каждой записи означает наличие позиции в соответствующей транзакции, а значение 0 – её отсутствие. Например, правило для супермаркета может быть таким: если покупают масло и хлеб, то покупатели также покупают молоко. Для отбора интересных правил из множества всех возможных правил используются ограничения на различные показатели значимости и интереса. Наиболее известными ограничениями являются минимальные пороговые значения для поддержки и достоверности. Пусть I – наборы элементов, A – правило ассоциации, а T – множество транзакций заданной базы данных. Примечание: этот пример крайне мал. В практических приложениях правило должно иметь поддержку в несколько сотен транзакций, прежде чем его можно будет считать статистически значимым, а наборы данных часто содержат тысячи или миллионы транзакций.

История

Концепция правил ассоциации получила широкую известность, особенно благодаря статье 1993 года Агравала и др., посвященной GUHA – общему методу интеллектуального анализа данных, разработанному Петром Хаеком и др. Одним из первых (около 1989 года) применений минимальной поддержки и достоверности для поиска всех правил ассоциации является фреймворк Feature Based Modeling, который находил все правила, для которых значения поддержки и достоверности превышали заданные пользователем ограничения.

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

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

Алгоритмы

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

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

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

ASSOC

Процедура ASSOC — это метод GUHA, который выявляет обобщенные правила ассоциации, используя быстрые операции с битовыми строками. Правила ассоциации, извлеченные этим методом, более общие, чем те, которые выдает алгоритм Apriori; например, "элементы" могут быть связаны как с помощью конъюнкции, так и с помощью дизъюнкции, а связь между антецедентом и консеквентом правила не ограничивается установлением минимальной поддержки и достоверности, как в Apriori: можно использовать любую комбинацию поддерживаемых мер значимости.

Поиск по OPUS

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

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

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