Труды КНЦ (Технические науки вып. 3/2024(15))

Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 82-96. Transactions of the Kola Science Centre of RA s . Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 82-96. For citation: Zuenko A. A., Fridman O. V. Survey of friequent pattern search methods for data mining // Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 82-96. doi:10.37614/2949-1215.2024.15.3.007. Введение В настоящей статье рассматриваются методы решения задачи поиска частых паттернов при обработке данных, которая впервые была поставлена в работе [ 1 ]. Пусть задан набор транзакций (транзакционная база данных, обучающая выборка, набор объектов), где каждая транзакция представляет собой набор элементов (предметный набор, набор признаков). Паттерном называется любое подмножество элементов. Частый паттерн — это такое множество элементов (признаков), которое достаточно часто встречается среди объектов обучающей выборки. Обычно задается некий порог Ѳ , и все паттерны, которые встречаются не менее, чем в Ѳ объектах обучающей выборки считаются частыми. Задача поиска частых паттернов используются как составляющая многих более сложных задач интеллектуального анализа данных, в частности, при поиске ассоциативных правил. Ассоциацитивное правило - это выражение вида X ^ Y, где X и Y - наборы элементов. Интуитивный смысл такого правила заключается в том, что транзакции в базе данных, содержащие элементы из X , как правило, также содержат элементы из Y . Ассоциативное правило обычно характеризуется двумя числами, которые называются поддержка и достоверность. Поддержка правила X ^ Y - это процент транзакций из транзакционной базы данных, которые содержат как X, так и Y. Достовернсть правила - это условная вероятность P (Y | X ) , т. е. вероятность того, что если в транзакции присутствуют элементы из множества X, то в них будут присутствовать элементы из Y. Пример ассоциативного правила: 97 % клиентов, покупающих, например, творог, также покупают сметану. Здесь 97 % - - это достоверность правила. Проблема поиска ассоциацитивных правил состоит в том, чтобы найти все правила, которые удовлетворяют заданной пользователем минимальной поддержке и минимальной достоверности. Известны следующие приложения методов поиска ассоциативных правил: — анализ потребительской корзины; — размещение предметов; — обнаружение мошенничества; — медицинские исследования; — реинжиниринг процесса и др. Далее приводится краткое описание нескольких алгоритмов, предназначенных для поиска ассоциацитивных правил, и на простом примере транзакционной базы данных рассмотривается их работа. Описание примера Пусть имеются транзакции купленных товаров, представленные в табл. 1. Таблица 1 Транзакции купленных товаров № транзакции Купленные товары 1 Карандаши, кнопки, клей 2 Кнопки, бумага 3 Кнопки,скрепки 4 Карандаши, кнопки, бумага 5 Карандаши, скрепки 6 Кнопки,скрепки 7 Карандаши, скрепки 8 Карандаши, кнопки, скрепки, клей 9 Карандаши, кнопки, скрепки © Зуенко А. А., Фридман О. В., 2024 83