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

Решение задачи кластеризации в подпространствах включает ряд этапов, затратных с точки зрения вычислительных ресурсов [17]. Первый из них заключается в отборе существенных атрибутов и выявлении интересных подпространств, в которых можно разделить объекты на требуемое количество кластеров. Этот этап обеспечивает предварительную подготовку данных. Затем следует этап кластеризации объектов внутри подпространств. Наконец, на последнем этапе требуется сжато описать полученные в результате кластеры с использованием характеристик объектов. Первый этап является наиболее важным и сложным, поскольку для разных кластеров подходят разные подмножества атрибутов. Это явление, при котором различные признаки или сочетания признаков могут быть релевантны для разных кластеров, называется релевантностью локальных признаков или корреляцией локальных признаков [10]. Один из традиционных способов решения проблемы высокой размерности заключается в применении методов снижения размерности набора данных. Такие методы, как анализ главных компонент или преобразование Карунена-Лоева [4; 5], оптимально снижают размерность исходного пространства, формируя измерения, которые являются линейными комбинациями заданных атрибутов. Новое пространство обладает тем свойством, что расстояния между точками остаются примерно такими же, как и раньше. Хотя эти методы помогают снизить размерность пространства поиска, у них есть два недостатка. Во-первых, новые измерения могут вызывать затруднения для интерпретации результирующих кластеров. Во-вторых, эти методы неэффективны при идентификации кластеров, которые могут существовать в различных подпространствах исходного пространства данных. Группа подходов к кластеризации данных высокой размерности основывается на концепции поиска частых паттернов [14]. Разным кластерам соответствуют разные подпространства, чтобы несоответствующие атрибуты не зашумляли кластеры. В такой постановке задачи прослеживается аналогия с поиском частых паттернов, и концепции алгоритмов, первоначально созданные для поиска частых паттернов, могут быть использованы в качестве основы парадигмы кластеризации в подпространствах. Систематизация методов кластеризации в подпространствах В [18] представлен обзор многих методов кластеризации в подпространствах. Эти методы можно разделить на две категории. Методы кластеризации подпространства «Сверху вниз» начинаются с начального приближения кластеров в полном пространстве признаков и итеративно уточняют кластеризацию, назначая вес каждому из измерений. Эти методы не гарантируют нахождение наилучшей кластеризации и, как правило, находят только гиперсферические кластеры [18]. Напротив, алгоритмы кластеризации подпространства «Снизу вверх» начинаются с обнаружения «интересных» кластеров в низкоразмерных подпространствах в соответствии с критериями плотности [17; 19-22] или мерой расстояния [23]. Кластеры в подпространстве итеративно объединяются для формирования кластеров подпространства более высокой размерности. «Узким местом» этих алгоритмов является NP-полнота перечисления кластеров подпространства. Чтобы сделать алгоритмы «Снизу вверх» более эффективными, целесообразно использовать пользовательские ограничения в процессе перечисления, чтобы отсечь большие части пространства поиска. В [24] разделяют три группы методов кластеризации в подпространствах: 1. Методы на основе сетки. При таком подходе пространство данных делится на ячейки, параллельные осям [4]. Затем ячейки, количество объектов в которых превышает заданное пороговое значение, объединяются для формирования кластеров подпространства. Количество интервалов — это еще один входной параметр, который определяет диапазон значений в каждой сетке. Для удаления неперспективных ячеек и повышения эффективности используется свойство антимонотонности, как в алгоритме поиска частых паттернов Apriori. Если ячейка оказывается плотной в k —1 измерении, то она учитывается при поиске плотной ячейки в k измерениях. Если границы сетки строго соблюдаются для разделения объектов, то точность результатов кластеризации снижается, поскольку могут теряться соседние объекты, которые разделены границей сетки. В данных алгоритмах качество кластеризации сильно зависит от входных параметров. Труды Кольского научного центра РАН. Серия: Технические науки. 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 37