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

Как и во многих алгоритмах интеллектуального анализа данных, проверяется согласованность монотонных и антимонотонных ограничений, чтобы в конечном итоге остановить процесс рекурсии и, таким образом, обрезать пространство поиска [51]. Удовлетворение ограничения на плотность сводится к отсечению ячеек (O, D), имеющих плотность меньше т, т. е. |O\/\ O \ < т. Алгоритм SC-MINER проверяет ограничение на близость, что гарантирует, что каждый элемент, который был отсеян в процессе генерации кандидатов, не может быть добавлен к текущему кандидату, т. е. не находится ли каждый такой элемент в N в связи хотя бы с одним элементом из J U Y. В противном случае кандидат и все его потомки не являются замкнутыми (поскольку данный элемент из N может быть добавлен для формирования большей ячейки, имеющей ту же поддержку) и их можно безопасно обрезать [51]. Этап распространения. На этом этапе SC-MINER проверяет, является ли (O, D) ячейкой: когда элемент a помещается в J , функция PROPAGATION удаляет все элементы Y, которые не связаны с a в наборе данных. Кроме того, PROPAGATION использует преимущества ограничений на экземпляры объектов следующим образом: для ограничения cannot-li«kCL(ot, oj), когда генерируется кандидат ( J U {ot}, Y \ {ot}, N), функция PROPAGATION автоматически удаляет Oj из Y; для ограничения must-li«kML(ot, Oj), когда генерируется кандидат ( J U {ot}, Y \ {ot}, N), функция PROPAGATION автоматически помещает oj в J и удаляет элемент из D', который не связан с oj. Когда генерируется кандидат (J, Y \ {ot}, N U {ot}), функция PROPAGATION автоматически удаляет oj из Y [51]. Ограничения на формируемые подпространства В кластеризации данных обычно не рассматриваются двоичные данные баз транзакций или дискретные данные в целом, а вместо этого чаще всего изучаются непрерывные векторные данные с действительными значениями, как правило, предполагается евклидово векторное пространство. В этом пространстве атрибуты могут быть зашумленными или даже нерелевантными для определенных кластеров. Если измерять сходство по всему пространству, т. е. по всем атрибутам, обнаружение таких кластеров в подпространствах становится все более трудным для большего числа нерелевантных измерений. С целью определения релевантных атрибутов и измерения сходства только по ним фундаментальная алгоритмическая идея алгоритма Apriori [26] была перенесена на кластеризацию в евклидовых пространствах, что привело к задаче «кластеризации в подпространствах», которая была определена как «нахождение всех кластеров во всех подпространствах» [17]. Этот перенос осуществлялся разными способами. Наиболее важными вариантами являются определение кластеров в подпространствах, которые, в свою очередь, квалифицируют некоторое подпространство как «частый паттерн», или определение интересных подпространств без прямой кластеризации, но как предпосылка для последующей кластеризации в этих подпространствах или как неотъемлемая часть некоторой процедуры кластеризации. После идентификации подпространств для поиска кластеров внутри этих подпространств применяются традиционные алгоритмы кластеризации, выполняется адаптация меры расстояния к этим подпространствам в фактической процедуре кластеризации или итеративно уточняются кластеры и соответствующие подпространства. Таким образом, «интересные» подпространства здесь выявляются не по кластерам, которые они содержат (что специфично для конкретной модели кластеризации), «интересные» подпространства определяются более обобщенно, например, с точки зрения того, насколько сильно в них взаимодействуют атрибуты. В поиске подпространств, как и в кластеризации в подпространствах, концепции «элементов» и «наборов элементов» из анализа частых паттернов трансформируются в «измерение» и «подпространство» соответственно. Понятие «частого паттерна» в соответствии с некоторым пороговым значением частоты здесь становится «интересным подпространством» в соответствии с некоторой мерой «интересности» [14]. Поиск подпространств, основанный на концепции анализа частых паттернов, применяется как отдельно от конкретных алгоритмов кластеризации, так и в составе некоторого алгоритма кластеризации, Труды Кольского научного центра РАН. Серия: Технические науки. 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 49