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

{ai, a 2 , bi} — это замкнутый набор элементов в табл. 3, а соответствующий ему набор атрибутов — {a, b}, а набор объектов — {1, 4}, но ({1, 4}, {a, b}) не является максимальным «-кластером, поскольку один из его суперкластеров ({1, 4, 6}, {a, b}) также является ^-«-кластером. Немаксимальные ^-«-кластеры удаляются на этапе постобработки. Использование дополнительных ограничений в процедурах кластеризации в подпространствах Ограничения на экземпляры кластера Все существующие алгоритмы кластеризации в подпространствах используют входные параметры, которые можно рассматривать как ограничения. Например, CLIQUE [17] использует пороговое значение минимальной плотности, которую может иметь кластер. Хотя небольшие изменения этих параметров могут полностью изменить результат кластеризации, значения этих пороговых значений обычно никогда заранее не известны пользователю. С другой стороны, более интуитивные ограничения, такие как знание априорной группировки некоторых объектов внутри кластеров, могут принести существенную пользу с точки зрения повышения эффективности алгоритмов кластеризации. Эти ограничения, известные как ограничения уровня экземпляра, были введены в [30] и успешно применялись к различным традиционным плоским алгоритмам, алгоритмам агломеративной кластеризации [47-49] и деревьям прогнозирующей кластеризации [50]. Несмотря на то, что анализ ограничений позволяет получать более значимые кластеры, зачастую их применение приводит к увеличению сложности алгоритмов [17]. Таким образом, актуальной проблемой является разработка методов кластеризации, которые использовали бы ограничения для усечения пространства поиска и в конечном счете ускорения получения решения. Также с точки зрения уменьшения вычислительной сложности процедур кластеризации в подпространствах желательно, чтобы пользователь изначально указывал только интересующие его измерения, где следует производить кластеризацию. Однако в реальности это далеко не всегда возможно. Существуют различные типы предпочтений пользователя и фоновых знаний предметной области, которые целесообразно учитывать и анализировать в процессе кластеризации, например: ожидаемое количество кластеров, минимальный или максимальный размеры кластера, веса для различных объектов и измерений, ограничения на параметры кластеризации (порог плотности, выбранная функция расстояния, порог энтропии и т. д.), а также ограничения на уровне экземпляра, такие как must-li«k (два объекта должны быть в одном кластере) и ca««ot-li«k (два объекта должны быть в разных кластерах). При наличии двух последних ограничений алгоритм становится алгоритмом с частичным привлечением учителя [15]. В работе [51] представлен алгоритм кластеризации в подпространствах на основе ограничений SC-MINER, который находит кластеры в подпространствах с учетом ограничений на экземпляры объектов. Авторы предлагают расширить общую структуру для методов кластеризации в подпространствах «Снизу вверх», интегрировав ограничения must-li«k и ca««ot-li«k в процедуры кластеризации на этапе анализа данных, чтобы повысить не только эффективность алгоритмов, но и их точность. Эти два ограничения позволяют конечному пользователю влиять на результаты кластеризации в подпространствах, добавляя некоторые экспертные знания. В [51] эти ограничения определяются следующим образом. Определение 4 (ограничение cannot-li«k). Ограничение cannot-li«k на объекты О і и Oj, записанное CL(Oi, Oj), удовлетворяется в процессе кластеризации в подпространстве SC тогда и только тогда, когда для каждого кластера подпространства (O, D) е SC, {оі, Oj} £ O. Определение 5 (ограничение must-li«k). Ограничение must-li«k на объекты О і и oj, записанное ML(Oi, Oj), удовлетворяется в процессе кластеризации в подпространстве SC тогда и только тогда, когда для каждого кластера подпространства (O, D) е SC, {оі, о; } С O или {оі, о; } П O = 0. Следующие свойства показывают, как ограничения must-li«k и ca««ot-li«k можно использовать для эффективного сокращения перечисления кластеров в подпространствах. Свойство 2. Ограничение ca««ot-li«k CL(Oi, o;) является антимонотонным относительно С: VP С O: {оі, о; } £ O ^{о і, Oj} <z P. Труды Кольского научного центра РАН. Серия: Технические науки. 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 47