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

(например, [21; 22; 38]), начинаются с дискретизации каждого измерения на ячейки. Количество ячеек может быть определено пользователем [20; 22; 38] или основано на распределении данных [39]. Пусть j -я ячейка измерения di обозначается как by, i 6 [1, n], j 6 [1, pi], где pi — количество ячеек измерения di. Полученное разбиение исходного пространства данных можно рассматривать как многомерную сетку, где пересечение ровно одного интервала из каждого измерения образует ячейку подпространства: u = bn х ...х bnq, где l 6 [1,p i], q 6 [1 ,p j . k-мерная ячейка — это ячейка, созданная путем пересечения k интервалов из k различных измерений. После разбиения необработанный набор данных кодируется в булевый набор данных, который указывает на наличие или отсутствие каждого объекта в каждой из ячеек. Алгоритмы кластеризации в подпространствах на основе расстояний, такие как n Cluster [23], сначала вычисляют расстояние между каждой парой объектов в каждом измерении. Для каждого измерения di два разных объекта находятся в одном наборе, если расстояние между ними в этом измерении ниже определенного пользователем порога S х R (где R — длина диапазона di). Количество максимальных наборов, которые могут быть созданы для каждого измерения di , определяет количество ячеек di. Этап анализа данных Алгоритмы «Снизу вверх» начинаются с перечисления соответствующих одномерных подпространств и итеративно генерируют подпространства более высоких размерностей, которые удовлетворяют критериям, предъявляемым к получаемым кластерам [17; 22; 23; 38-40]. Чтобы сделать процесс перечисления эффективным, критерии должны состоять из антимонотонных ограничений, которые используются для обрезки пространства поиска. Если рассматривать предварительно обработанный набор данных как транзакционные данные, то поиск для k-мерных плотных единиц сводится к задаче поиска частых k-элементных наборов [26]. Набор транзакций сопоставляется с набором объектов O , а элементы транзакций соответствуют ранее вычисленным интервалам измерений. Тогда k-мерная ячейка с плотностью, большей, чем т, может рассматриваться как частый набор размера k с частотой, большей, чем т. Поскольку ячейки не пересекаются, два разных набора одинаковой размерности не могут встречаться в одном и том же частом наборе, и, таким образом, вычисленный частый набор может рассматриваться как плотная k-мерная ячейка. CLIQUE использует свойство антимонотонности ограничения на плотность: если k-мерное пространство плотное, то любое из его (k —1)-мерных подпространств также плотное [17]. В случае алгоритма на основе расстояния, ячейки могут перекрываться. Это может привести к большему количеству ячеек, чем в подходах на основе плотности, что увеличивает сложность алгоритма. Чтобы преодолеть эту проблему, nCluster напрямую ищет максимальные кластеры, принимая стратегию поиска замкнутого набора элементов [41]. nCluster использует следующее антимонотонное свойство: если набор объектов O и набор ячеек D образуют ^-n-кластер (т. е. для каждых двух объектов ow и oz из O и каждого интервала bij 6 D , ow и oz являются соседями относительно меры расстояния на di и порога S), то O образует ^-n-кластер с каждым подмножеством D, а D образует S — ^-n-кластер с каждым подмножеством O. Кроме того, он рассматривает кластер подпространства как имеющий смысл, если он состоит из mr объектов и mc измерений (mc и mr задаются предварительно). Добавление дополнительных ограничений к этому шагу интеллектуального анализа данных может сделать процесс кластеризации не только более эффективным, но и более точным. Этап постобработки Этап постобработки может иметь несколько целей. Одна из них — идентификация максимальных кластеров и генерация их соответствующих описаний. Например, CLIQUE генерирует k-мерно- максимальные кластеры, соединяя k-мерные плотные единицы (полученные на предыдущем шаге), имеющие общие грани. В случае n Cluster применяемый алгоритм интеллектуального анализа замкнутых множеств вычисляет замкнутый набор ячеек, связанных с замкнутым набором объектов, но некоторые из них фактически могут быть не максимальными при рассмотрении измерений вместо ячеек, Труды Кольского научного центра РАН. Серия: Технические науки. 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 40