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

Поиск максимальных S-n-кластеров, содержащих более одного атрибута Для ^-«-кластера (T, G) и атрибута a <t G, если есть по крайней мере mr объектов в T, являющихся ^-соседями друг друга по атрибуту a, то атрибут a можно добавить в G, чтобы сформировать ^-«-кластер с еще одним атрибутом. Чтобы найти все такие атрибуты a, мы поддерживаем список атрибутов для каждого объекта. Список атрибутов объекта x содержит все атрибуты, по которым у объекта x имеется по крайней мере mr —1 ^-соседей. Например, в табл. 2 атрибут a имеет два максимальных набора объектов. Если просто добавить a к спискам атрибутов всех объектов, содержащихся в его двух максимальных наборах объектов, то нельзя определить, какие объекты находятся в одних и тех же максимальных наборах объектов. Чтобы решить эту проблему, при добавлении имени атрибута к спискам атрибутов объектов следует добавить нижний индекс к имени атрибута. Списки атрибутов объектов в одном и том же максимальном наборе объектов получают атрибут с тем же нижним индексом. Имя атрибута с нижним индексом называется символом атрибута, чтобы отличать его от самого атрибута. Количество символов атрибута равно количеству максимальных наборов объектов атрибута, а частота символа атрибута в списках атрибутов равна размеру максимального набора объектов, который представляет символ. В приведенном выше примере атрибут a имеет два символа ai и a 2, списки атрибутов объектов 1, 3 и 4 содержат ai, а списки атрибутов объектов 1, 2, 4, 6 и 8 содержат a 2. Списки атрибутов всех объектов в табл. 1 показаны в табл. 3. Труды Кольского научного центра РАН. Серия: Технические науки. 2025. Т. 16, № 3. С. 35-55. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2025. Vol. 16, No. 3. P. 35-55. Таблица 3 Списки атрибутов объектов Объект Список атрибутов 1 a1, a2, b1, с1, d1 2 a2 3 a1, c2 4 a1, a2, b1, c2 5 bi 6 a2, b1, c1 7 c1, d1 8 a2, d1 Лемма 2. Два объекта являются ^-соседями по атрибуту a тогда и только тогда, когда списки атрибутов двух объектов содержат один и тот же символ атрибута a. Поскольку списки атрибутов содержат полную информацию, списки атрибутов используются для обнаружения максимальных ^-«-кластеров в последующем поиске. Алгоритм поиска основан на следующем наблюдении. Лемма 3. Набор атрибутов G образует ^-«-кластер с набором объектов T тогда и только тогда, когда списки атрибутов объектов в T содержат один и тот же символ каждого атрибута в G [39]. Если рассматривать символы атрибутов как элементы, наборы символов атрибутов как наборы элементов, а списки атрибутов как транзакции, то поиск ^-«-кластеров можно представить как поиск частых наборов элементов (паттернов) из базы данных транзакций [16]. Концепция максимальных ^-«-кластеров используется в статье для удаления избыточных ^-«-кластеров, и она похожа на концепцию частых замкнутых паттернов [45], которая используется для удаления избыточных наборов элементов при поиске паттернов. Набор элементов (паттерн) замкнут, если он максимален в наборе транзакций, содержащих его. Если ^-«-кластер максимален, то соответствующий ему набор символов атрибутов является замкнутым паттерном относительно списка атрибутов. Таким образом, появляется возможность применять алгоритмы поиска частых замкнутых паттернов для получения максимальных 5-и-кластеров. В работе [23] используется LCM [46] для поиска максимальных «-кластеров. Замкнутый набор элементов (паттерн) не всегда соответствует максимальному ^-«-кластеру. Например, © Зуенко О. Н., Фридман О. В., 2025 46