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

Свойство 3. Ограничение must-linkML(o,, oj) является дизъюнкцией монотонного и антимонотонного ограничений относительно Q: {oi, o; } Q O монотонно, а {oi, o; } П O = 0 антимонотонно: VP Q O: {oi, oj} Q P ^ {oi, o; } Q O, VP Q O: {oi, o; } П O = 0 ^ {oi, o; } П P = 0. Свойство 2 означает, что для выполнения ограничения CL(oi, oj) необходимо искать кластеры подпространства, где объекты oi и oj никогда не присутствуют вместе. Поскольку k-мерный кластер никогда не может содержать больше объектов, чем любая из его k —1-мерных проекций, ограничение cannot-link является антимонотонным. Свойство 3 гласит, что для выполнения ограничения ML ( oi , oj ) необходимо искать кластеры подпространства, где объекты oi и oj либо оба присутствуют, либо оба отсутствуют. Если один из объектов присутствует, а другой отсутствует, кластер подпространства не имеет значения. Эффективное использование этих ограничений может зависеть от процесса перечисления кластеров. Действительно, такие алгоритмы, как SUBCLU [11] или DUSC [40], напрямую обнаруживают кластеры в подпространстве, применяя алгоритм, подобный DBSCAN. Как следствие, ограничения на экземпляры объектов должны быть непосредственно введены в этот алгоритм, как, например, в C-DBSCAN [23]. Существующие методы «Снизу вверх» используют алгоритмы поиска замкнутых паттернов для перечисления возможных кластеров подпространства. Однако обычные алгоритмы поиска паттернов (например, Apriori [26]) не обрабатывают антимонотонные ограничения совместно с монотонными ограничениями, поскольку введение монотонных ограничений может привести к сокращению антимонотонного отсечения [52; 53]. В работе [51] расширяется алгоритм DMINER [54], который является алгоритмом интеллектуального анализа данных, до алгоритма SC-MINER, который обрабатывает ограничения на экземпляры объектов. Производится поиск только замкнутых наборов элементов, чтобы избежать избыточных подпространств, которые могут возникнуть при использовании предыдущих методов. На первом этапе работы алгоритма SC-MINER выполняется генерация кандидатов. Основная техника, используемая SC-MINER для обработки ограничений на экземпляры объектов, основана на универсальном алгоритме «разделяй и властвуй», предложенном в [54; 55]. SC-MINER рекурсивно перечисляет в глубину сначала все кластеры подпространства ( O , D ), которые содержат элемент (объект или интервал) a , а затем все кластеры подпространства, которые не содержат a . В процессе перечисления элементы, которые уже были перечислены, отделяются от тех, которые еще предстоит перечислить. Кандидат в процессе перечисления описывается тройкой (X, Y, N), состоящей из трех пар кортежей: пара X = (O, D) — это набор объектов и набор интервалов, содержащихся в кандидате и его потомках (полученных рекурсивно). Эти элементы уже были перечислены как члены строящихся кластеров в подпространствах; пара Y = (O', D') содержит объекты и интервалы, которые еще предстоит перечислить; пара N = (On, D n ) используется для обеспечения ограничения близости, которое не является ни монотонным, ни антимонотонным. Эти элементы не принадлежат ни к одному подпространственному кластеру, находящемуся в стадии построения [51]. Кластеры подпространства состоят из максимальных наборов объектов и интервалов, которые находятся в отношении: каждый объект O должен принадлежать k-мерной ячейке, определенной в D, и каждый интервал в D должен содержать каждый объект O. Следующим этапом является отсечение. Алгоритм SC-MINER может накладывать монотонные и антимонотонные ограничения на набор объектов или на набор ячеек. Это интересное свойство основано на том факте, что для заданного кандидата (X, Y, N) кластеры подпространства (Oi, D), которые могут быть сгенерированы, удовлетворяют следующим выражениям: O Q Oi Q O U O' и D Q Di Q D U D'. Труды Кольского научного центра РАН. Серия: Технические науки. 2025. Т. 16, № 3. С. 35-55. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2025. Vol. 16, No. 3. P. 35-55. © Зуенко О. Н., Фридман О. В., 2025 48