Ассоциативные правила и их поиск.
- 31.03.24 г.
- 9772225665000 24010
А. При обработке данных актуальным является выявление зависимостей (связей, закономерностей или правил) тем или иным образом связанных событий (объектов, элементов); например, следование одного события из (после) другого. Такие правила называются ассоциативными: ассоциативные правила. Они выражают закономерности между соотносящимися событиями (объектами, элементами). Иными словами, ассоциативные правила включают две части: в обозначенном случае – условие и следствие (результат).
Отдельно выделяют мультиассоциативные правила – такие ассоциативные правила, в которых каждое событие может иметь несколько зависимостей.
Как считается, впервые задача поиска ассоциативных правил появилась при анализе покупок, поэтому иногда ее еще называют анализом рыночной корзины, или анализом транзакций (наборов товаров, купленных за один раз). Обычно в теории рассматривается эта предметная область.
Ассоциативные правила используются также при сегментации покупателей по поведению при покупках, анализе предпочтений клиентов, планировании расположения товаров в торговых залах и т.п.
Однако, сфера применения алгоритмов поиска ассоциативных правил не ограничивается лишь только торговлей. Их также успешно применяют и в других областях: для анализа посещений веб-страниц, для анализа текста, в медицине и т.д.
В последнее время активно развивались методы машинного обучения на базе правил обнаружения связей между элементами в базах данных.
Б. Поиск ассоциативных правил – это действия, направленные на нахождение закономерностей между соотносящимися событиями. Их целью является установление определенных зависимостей: например, если встретился некоторый набор элементов А (условие), то можно сделать вывод о том, что другой набор элементов В (результат) также же должен появиться (например, часто приводимое для примера утверждение «кто купил А, также купил В»).
Поиск ассоциативных правил осуществляется через сопоставление двух или более событий, объектов, элементов в данных – через реализацию ассоциаций в данных (или как принято говорить – в датасетах, или в айтемсетах). Иными словами, механизм ассоциации основан на выделении групп или отдельных событий, элементов, между которыми существуют явные или неявные зависимости, определяемые условием и следствием, в свою очередь которые могут быть левосторонними и правосторонним членами ассоциативного правила.
Обычно датасет представляет собой разреженную матрицу со значениями «1» и «0». Это – бинарный датасет. Существуют и другие: вертикальный датасет (показывает для каждого элемента вектор транзакций, где он присутствует) и транзакционный датасет (примером является кассовый чек).
В общем, поиск ассоциативных правил – сложная задача, и наиболее существенная проблема– это то, что с ростом числа элементов экспоненциально растет число их потенциальных наборов.
Методы поиска ассоциативных правил предназначены для нахождения правил сочетаний элементов датасетов.
Ключевыми критериями (понятиями) для поиска ассоциативных правил являются
– support (поддержка) – это показатель частотности элемента (показателя) во всех анализируемых транзакциях,
– confidence (достоверность или доверие) – это показатель того, как часто правило срабатывает для всего набора данных,
– lift (в начале назывался «интерес»; на русский язык часто переводится как «поддержка») – это отношение, которое показывает, насколько элементы зависят друг от друга,
– conviction (убедительность) – это частотность ошибок правила.
Значения критериев ассоциативных правил должны быть выше устанавливаемых порогов, называемых минимальной поддержкой и минимальной достоверностью (минимальным доверием).
Если поддержка имеет большое значение, то поиск будет давать очевидные правила, что в целом делает бессмысленным их анализ.
Низкое значение поддержки наиболее актуально, но ведет к выявлению большого количества правил, зачастую статистически необоснованных.
Наборы элементов, которые удовлетворяют порогу минимальной поддержки, обычно встречаются достаточно часто.
Значения минимальной поддержки и минимальной достоверности выбираются так, чтобы уменьшить количество искомых правил.
Поиск ассоциативного правила обычно разделяется на два этапа:
– поиск всех наборов объектов, элементов, с определенной частотой появления в базе данных, для чего используется минимальный порог поддержки,
– к этим наборам применяется ограничение минимальной достоверности в целях формирования правила.
Ограничениями обнаружения ассоциаций и поиска и применения ассоциативных правил является то, что
а) обработка первичных данных обычно производится в плохо программируемом предметном смысле,
б) в ряде случаев нельзя считать выделение устойчивых групп объектов объективным и строго закономерным (или при поиске в большом объеме объектов вероятно большое число случайных ассоциаций),
в) в общем случае обоснованных утверждений и прогнозов делать нельзя.
В. Виды ассоциативных правил:
– обобщенные ассоциативные правила,
– количественные ассоциативные правила,
– косвенные ассоциативные правила,
– интервальные ассоциативные правила,
– ассоциативные правила c отрицанием,
– временные ассоциативные правила
и другие.
При поиске обобщенных ассоциативных правил предполагается, что все анализируемые элементы однородны и имеют одинаковые атрибуты. По сути, все сводится к установлению факта того, присутствует в транзакции тот или иной элемент или нет. Обычно элементы транзакции объединяются в группы, или уровни иерархии, и строятся их иерархическая модель. При этом из данных можно извлекать правила, связывающие группы с группами, отдельные элементы с элементами или группами и т.д.
Элементы на верхних уровнях иерархии стремятся к значительно большим значениям поддержки по сравнению с элементами на нижних уровнях.
Следует отметить, что при добавлении в транзакции групп увеличивается количество атрибутов и соответственно размерность входного пространства, что ведет к генерации еще большего количества вариантов соотношений событий и усложняет задачу их поиска правил.
При поиске количественных ассоциативных правил рассматриваются не только факты наличия события (покупка товара, наличие элемента в транзакции), но и отдельные характеристики: например, в случае рыночной корзины учитываются количество купленного товара, характеристики покупателя и т.д. При этом учитываются различные типы данных: числовые, категориальные и др.
При поиске временных ассоциативных правил рассматриваются временные закономерности последовательных данных, событий. Например, последовательная ассоциация позволяет найти и исследовать временные закономерности последовательных событий: ее целью является установление закономерностей между событиями, упорядоченными во времени.
Следует учитывать, что обработка первичных данных производится в предметном смысле, но в ряде случаев нельзя считать выделение устойчивых групп событий и элементов объективным и строго закономерным, поэтому-то в общем случае обоснованных утверждений и прогнозов делать нельзя.
Г. Имеются разные виды поиска ассоциативных правил (изучения событий и их совокупностей как на одном этапе исследований и в одной совокупности событий, так и на разных этапах и в разных совокупностях):
– брутфорс-алгоритм,
– ECLAT-алгоритм,
– Apriori-алгоритм и AprioriDP-алгоритм,
– FP-growth алгоритм и улучшенный FP-growth (FP Bonsai),
– алгоритм CHARM
и другие.
Д. Получило широкое распространение обучение на ассоциативных правилах, которое
– относительно легко в использовании, и существуют различные его реализации для разных задач,
– хорошо интерпретируется и не требует специальных навыков,
– широко применимо – от традиционного ритейла и онлайн ритейла до банков и телекома (подключаемые сервисы и услуги),
– лежит в основе рекомендательных систем и т.п.
Однако обучение на ассоциативных правилах нельзя назвать эффективными: необходимы очень большие вычислительные мощности.
Е. Указанные выше ограничения поиска и применения ассоциативных правил и обнаружения ассоциаций принципиально важны, по крайней мере, для диалектики, так как обусловливают неизбежность трансформации обработки данных в целом и, особенно, в категориальном смысле в частности, что будет обсуждено отдельно.
Cм. «Ассоциативные правила и диалектика»
Дискуссии и конференции. Методы