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

Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 82-96. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 82-96. В соответствии с базой транзакций создадим объектно-признаковую таблицу (табл. 2). Таблица 2 Объектно-признаковая таблица Обозначение a b с d e № транзакции Карандаши Кнопки Скрепки Бумага Клей 1 1 1 1 2 1 1 3 1 1 4 1 1 1 5 1 1 6 1 1 7 1 1 8 1 1 1 1 9 1 1 1 Зададим значение минимальной поддержки (minsup), равное двум. Требуется найти все частые паттерны с данной поддержкой. Алгоритм Априори Первым из наиболее известных примеров практической реализации поиска ассоциативных правил является алгоритм Априори (англ. Apriori) [2], который позволяет находить частые паттерны в данных. Введем некоторые обозначения: ^-множеством будем называть множество, состоящее из k элементов. Обозначим через Lk множество всех часто встречающихся k-множеств. Объединение Lk по всем k дает все искомое множество частых паттернов. Построение Lk выполняется по шагам. Сначала находится Li (множество одноэлементных частых паттернов). Затем для каждого фиксированного k > 2 , используя найденное множество Lk-i, определяется Lk . Процесс завершается, когда k станет больше максимального количества элементов. Определение Lk при известном Lk-i выполняется в два шага: 1 ) генерируются множества — кандидаты Ck; 2) затем из этого множества исключаются лишние элементы. Полученное таким образом множество и будет равно Lk . Шаг 1. Находим все 1-элементные частые паттерны с заданным значением minsup (т. е. записи, представленные в БД минимум 2 раза): Li = {{a}, {b}, { с } ,{d}, {e}}. Шаг 2. Задаем k = 2 и запускаем процедуру apriori gen, которая для i-элементных частых множеств признаков порождает (i + 1 )-надмножества и возвращает только множество потенциально частых кандидатов. Таким образом, из множества Li формируется множество кандидатов C 2 , отсортированных по алфавиту. Результат: C 2 = {{a, b}, {a, с}, {a, d}, {a, e}, {b, с}, {b, d}, {b, e}, {с, d}, {с, e}, {d, e}}. Шаг 3. Инициализируем счетчик нулевым значением (обозначим его как c.count). © Зуенко А. А., Фридман О. В., 2024 84