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

вычисленных на них. Поэтому немаксимальные кластеры подпространства удаляются на этапе постобработки. В конце этого этапа максимальные кластеры описываются как пара (O, D), где O — набор объектов, а D — набор ячеек разных измерений (подпространство). В случае nCluster ячейки bij заменяются соответствующей исходной размерностью di. Этот шаг также можно использовать для обрезки избыточных подпространственных кластеров или тех, которые, например, не соответствуют определенным ограничениям, которые не могут быть эффективно реализованы в процессе поиска (например, немонотонные ограничения) [23]. Алгоритм CLIQUE [17] Приложения для интеллектуального анализа данных предъявляют особые требования к алгоритмам кластеризации, включая: способность находить кластеры, встроенные в подпространства данных высокой размерности, масштабируемость, понятность результатов для конечного пользователя, отсутствие предположения о каком-либо каноническом распределении данных и нечувствительность к порядку входных записей. Алгоритм CLIQUE удовлетворяет каждому из этих требований. Он идентифицирует плотные кластеры в подпространствах максимальной размерности, генерирует описания кластеров в виде выражений ДНФ, которые минимизированы для простоты понимания, выдает идентичные результаты независимо от порядка, в котором представлены входные записи. В алгоритме CLIQUE используется подход, основанный на плотности: кластер — это область, которая имеет более высокую плотность точек, чем окружающая ее область. Необходимо автоматически идентифицировать проекции входных данных, то есть подмножество атрибутов, предполагая, что эти проекции включают области высокой плотности. Чтобы аппроксимировать плотность точек данных, пространство данных разбивается и находится количество точек, которые лежат внутри каждой ячейки (единицы) разбиения. Это достигается путем разбиения каждого измерения на одинаковое количество интервалов равной длины. Каждая ячейка имеет одинаковый объем, и поэтому количество точек внутри нее может быть использовано для аппроксимации плотности ячейки. После нахождения соответствующих подпространств задача состоит в том, чтобы найти кластеры в этих проекциях. Кластеры представляют собой объединения связанных ячеек высокой плотности в подпространстве. Чтобы упростить их описания, кластеры ограничиваются осями — параллельными гиперпрямоугольниками (брусами). Каждая ячейка в k-мерном подпространстве может быть описана как конъюнкция неравенств, так как она является пересечением 2 k осей. Поскольку каждый кластер является объединением таких ячеек, его можно описать с помощью выражения ДНФ. Компактное описание получается путем покрытия кластера минимальным числом максимальных, возможно, перекрывающихся прямоугольников и описания кластера как объединения этих прямоугольников. Кластеризация в подпространствах позволяет обрабатывать отсутствующие значения во входных данных. Точка данных считается принадлежащей определенному подпространству, если значения атрибутов в этом подпространстве не отсутствуют, независимо от значений остальных атрибутов. Это позволяет использовать записи с отсутствующими значениями для кластеризации и получать более точные результаты, чем в случае замены отсутствующих значений значениями, взятыми из распределения [17]. Постановка задачи Пусть A = [A\, A 2 ,..., Ad} — набор полностью упорядоченных доменов, а S =A 1 хA 2 x...xAd - d-мерное числовое пространство, A 1 ,A 2 , . , Ad — измерения (атрибуты) S. Входные данные состоят из набора d-мерных точек V = к v 2 ,..., vm}, где vi = {vn, va,..., vid). j -й компонент vi взят из домена Aj. Пространство данных S разбивается на неперекрывающиеся прямоугольные ячейки. Ячейки получаются путем разбиения каждого измерения на интервалы равной длины. Длина Е является одним из входным параметров. Каждая ячейка u является пересечением одного интервала из каждого атрибута. Она имеет вид {u 1 , u 2 ,..., ud}, где ui = [li, hi) — открытый справа интервал в разбиении Ai. Точка v = {v 1 , v 2 ,..., vid) Труды Кольского научного центра РАН. Серия: Технические науки. 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 41