Труды КНЦ (Технические науки вып. 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. или превышает количество понятий. На каждом этапе цикла сгенерированное понятие проверяется на каноничность, что требует времени, линейного по количеству понятий. Кроме инкрементных и пакетных алгоритмов, также выделяют упорядоченные. Алгоритмы обходят решетку в некотором заданном порядке. Например, Close by One [10, 11] использует лексикографический порядок, чтобы определить, порождалось ли данное понятие в первый раз. Полученное понятие считается каноничным, если оно не предшествовало текущему по порядку. Алгоритм Close by One (CbO) использует понятие каноничности и метод выбора подмножеств, представленный в работе [ 1 1 ], и является родоначальником для семейства алгоритмов, предложенных позднее (подробный обзор и сравнительный анализ этих алгоритмов приведен в исследовании [ 1 0 ]). Он использует промежуточную структуру, которая помогает более эффективно вычислять замыкания с помощью созданных понятий. Алгоритм CbO получает каждое новое замыкание из понятия, сгенерированного им на предыдущем шаге, путем пересечения его объема с объемом признака, который не принадлежит его содержанию. Исходная версия алгоритма CbO использует дерево в качестве промежуточной структуры. Дерево понятий можно построить следующим образом: 1 ) создать фиктивный корень, соответветствующий понятию с пустым содержанием; 2 ) исследовать признаки из М и для каждого понятия дерева проверить, обладают ли рассматриваемым признаком все объекты понятия; — если да, добавить его в набор признаков понятия; — в противном случае сформировать новый узел и объявить его дочерним узлом текущего; 3) содержание соответствующего понятия равно содержанию родительского узла плюс исследуемый признак; 4) объем формируемого понятия является пересечением объема, соответствующего рассматриваемому признаку, и объема родительского узла; 5) проверить новый узел на каноничность; 6 ) если тест не пройден, удалить новый узел из дерева. Алгоритм вычисляет понятия в соответствии с лексикографическим порядком, определенным на подмножествах M. При помощи алгоритма CbO на основе объектно-признаковой таблицы (табл. 2) построим дерево понятий, которое позволит получить замкнутые частые паттерны, необходимые для формулирования ассоциативных правил. На рис. 3 представлено дерево понятий. В левой части записи, обозначающей узел, перечислены объекты (номера транзакций), а в правой части — обозначения признаков (свойств объектов). Признаки при построении дерева упорядочены в лексикографическом порядке. Рис. 3. Дерево понятий © Зуенко А. А., Фридман О. В., 2024 92