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

множеств вида: (объем, содержание) [10, 11]. Контекстом в АФП называют тройку K = (О, M , I ) , где G — множество объектов; M - множество признаков, а отношение I с О х M говорит о том, какие объекты какими признаками обладают. Для произвольных A с О и B с M определены операторы Галуа: A ' = (m е M | Vg е A ( g I m)}, B ' = {g e О | Vm e B ( g I m)}. Оператор "(двукратное применение оператора ') является оператором замыкания. Множество объектов A с О такое, что А " = А называется замкнутым. Пара множеств (A, Б) таких, что A с О , B с M , A' = B и В ' = A называется формальным понятием контекста K. Для множества объектов A множество их общих признаков A ' служит описанием сходства объектов из множества A , а замкнутое множество A " является кластером сходных объектов (с множеством общих признаков A'). Отношение "быть более общим понятием" задается следующим образом: (A, Б) > (С, D) тогда и только тогда, когда A ^ С. В работах [10, 11] рассматриваются несколько алгоритмов, генерирующих множество всех формальных понятий и графов-диаграмм решеток понятий. Различные алгоритмы отличаются условием выхода из цикла, методом выбора подмножеств для вычисления замыканий, методом проверки того, было ли понятие сгенерировано ранее (тест на каноничность) и методом вычисления замыканий. Смысл теста на каноничность состоит в том, что для любого понятия существует уникальная каноническая генерация, которая указана в каждом конкретном алгоритме. Интенсионал D, полученный из B, является каноническим, если B и D согласуются по всем атрибутам до текущего атрибута j. Если же в D есть атрибут, идущий до j, которого нет в B, то понятие считается неканоническим. Все алгоритмы можно разделить на две категории: инкрементные алгоритмы [12-14], которые на i-м шаге создают набор понятий или граф-диаграмму для i первых объектов контекста, и пакетные, которые строят набор концептов и его граф-диаграмму для всего контекста с нуля [11, 15]. Инкрементные алгоритмы достраивают решетку посредством постепенного добавления объектов и пересечения с имеющимися понятиями. В противовес этому принципу «пакетные» алгоритмы выполняют все построение в один проход. Любой пакетный алгоритм обычно придерживается одной из двух стратегий: сверху вниз (от максимального объема к минимальному) или снизу вверх (от минимального объема к максимальному). Алгоритм, предложенный в работе [16], продемонстрировал хорошую производительность для баз данных с очень большим количеством объектов. Аналогичные алгоритмы применялись для машинного обучения и анализа данных [14, 17]. Инкрементный алгоритм, предложенный в работе [18], использует «специальные» операции с объектами. Алгоритм, представленный в работе [19] использует так называемые бинарные диаграммы и работает в очень плотных контекстах. Выбор алгоритма построения решетки понятий должен основываться на свойствах входных данных. Алгоритм [13] следует использовать для небольших и разреженных контекстов; для плотных контекстов следует использовать алгоритмы, основанные на критерии каноничности, линейные по количеству входных объектов [11]. Алгоритм, представленный в работе [9], хорошо работает в контекстах средней плотности, особенно когда необходимо построить граф-диаграммы. Эксперименты с реальными данными [10] показывают, что, когда нужны только понятия, лучшим выбором будет простой и интуитивно понятный алгоритм, представленный в работе [ 2 0 ]. В исследовании [10] рассматривается семейство алгоритмов CbO, основанных на вычислении замыканий для подмножеств G . Они следуют следующей схеме: 1 ) выбрать одно из условий, и пока это условие верно: 2) для некоторого множества A с G; вычислить (А"; А'); 3) если понятие (A"; А') генерируется первый раз (или, как в некоторых алгоритмах, понятие генерируется в последний раз), добавить его в набор концептов. Самый простой (наивный) алгоритм, соответствующий этой схеме, вычисляет замыкания всех подмножеств G, кроме пустого. Он выполняет проверку каноничности, просматривая все сгенерированные на данный момент понятия. Цикл выполняется 2”раз, где n = |G|. Таким образом, количество итераций равно Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 82-96. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 82-96. © Зуенко А. А., Фридман О. В., 2024 91