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

1-мерные плотные ячейки, выполняя проход по данным. Этот алгоритм похож на алгоритм Apriori для поиска частых паттернов [42]. Определив (k - 1)-мерные плотные ячейки, кандидаты k-мерных клеток определяются с помощью процедуры генерации кандидатов, описанной в [42]. Проход по данным выполняется для поиска тех кандидатов, которые являются плотными. Следующим шагом алгоритма CLIQUE является поиск кластеров в отобранных подпространствах. Входные данные для этого шага CLIQUE — это набор плотных ячеек D, все в одном и том же k-мерном пространстве S . Выходные данные будут разбиением D на D 1, . , Dq таким образом, что все ячейки в Di связаны и никакие две ячейки ul е D1, u е D с i Фj не связаны. Каждое такое разбиение является кластером согласно определению, приведенному в [17]. Задача эквивалентна поиску компонент связности в графе, определенном следующим образом: вершины графа соответствуют плотным ячейкам и между двумя вершинами есть ребро тогда и только тогда, когда соответствующие плотные ячейки имеют общую грань. Для выявления связанных компонент графа в [43] применяется алгоритм поиска в глубину. Входными данными для следующего шага является множество C связанных плотных ячеек в том же k-мерном пространстве S. Выходными данными будет множество ^максимальных областей, таких, что R является покрытием C. Для решения этой задачи используется алгоритм жадного роста. Начинают с произвольной плотной ячейки u 1 е C и жадно наращивают (как описано ниже) максимальную область R 1 , которая покрывает u 1 . Добавляют R 1 к R Затем находят другую единицу u 2 eC , которая еще не покрыта ни одной из максимальных областей в R Далее жадно наращивают максимальную область R 2 , которая покрывает u 2 . Эта процедура повторяется, пока все ячейки в C не будут покрыты некоторой максимальной областью в R Чтобы получить максимальную область, покрывающую плотную ячейку u, начинают с u и наращивают ее вдоль измерения a 1 как слева, так и справа от ячейки. Увеличивают u как можно больше в обоих направлениях, используя связанные плотные ячейки, содержащиеся в C . Результатом является прямоугольная область. Эта процедура повторяется для всех измерений, что дает максимальную область, покрывающую u . Порядок, в котором измерения рассматриваются для увеличения плотной области, определяется случайным образом. Последний шаг CLIQUE принимает в качестве входных данных покрытие для каждого кластера и находит минимальное покрытие. Минимальность определяется в терминах количества максимальных областей (прямоугольников), необходимых для покрытия кластера. В [17] предлагается следующая жадная эвристика: из покрытия удаляется наименьшая (по количеству ячеек) максимальная область, которая является избыточной (т. е. каждый блок также содержится в некоторой другой максимальной области). Связи разрываются произвольно. Процедура повторяется до тех пор, пока не останется ни одной максимальной области. Также предлагается следующая эвристика сложения: кластер рассматривается как пустое пространство. К покрытию добавляется максимальная область, которая покроет максимальное количество еще непокрытых ячеек в кластере. Связи разрываются произвольно. Процедура повторяется до тех пор, пока весь кластер не будет покрыт. На заключительном шаге генерируются описания кластеров в форме выражений ДНФ, которые минимизированы для простоты понимания (см. пример 1). При проектировании CLIQUE были объединены разработки из нескольких областей, включая интеллектуальный анализ данных, стохастическую сложность, распознавание образов и вычислительную геометрию [17]. Он нечувствителен к порядку входных записей и не предполагает некоторого канонического распределения данных. Алгоритм «C luster В работе [23] предложена модель кластеризации подпространства на основе расстояния, называемая 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 43