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

содержится в ячейке и = {u\, и г , . , Ud}, если li < v , < hi для всех Ui. Селективность ячейки определяется как доля всех точек данных, содержащихся в ячейке. Ячейку и называют плотной, если селективность (и) больше, чем г, где порог плотности гявляется другим входным параметром. Аналогично определяются ячейки во всех подпространствах исходного d-мерного пространства. Рассмотрим проекцию набора данных V в Ati х A ti х... xAtk , где k < d и ti < tj, если i < j. Ячейка в подпространстве является пересечением интервала из каждого из k атрибутов. Кластер — это максимальный набор связанных плотных ячеек в k-измерениях. Две k-мерные ячейки ui, иг связаны, если они имеют общую грань или если существует другая k-мерная ячейка из, такая, что иі связана с из и иг связана с из. Ячейки иі = {rti,..., rtk} и иг = {r'ti,..., r'tk} имеют общую грань, если есть k - 1 измерений A t i , . , Atk, таких, что rj = r ' и либо htk = l'k, либо h'k = ltk. Область в k измерениях — это параллельный осям прямоугольный k-мерный набор. Интересны только те области, которые могут быть представлены как объединения ячеек. Область может быть описана в виде дизъюнктивной нормальной формы (ДНФ) на интервалах доменов Ai. Область R, содержащаяся в кластере C, называется максимальной, если ни одно собственное надмножество R не содержится в C. Минимальное описание кластера — это неизбыточное покрытие кластера максимальными областями. То есть минимальное описание кластера C — это множество R максимальных областей, такое, что их объединение равно C , но объединение любого собственного подмножества R не равно C [17]. Задача кластеризации в данном случае состоит в том, что, при заданном множестве точек данных и входных параметрах % и г , требуется найти кластеры во всех подпространствах исходного пространства данных и представить минимальное описание каждого кластера в виде выражения ДНФ. Приведем пример такой задачи. Пример 1 [17]. На рис. 2 двумерное пространство (возраст, зарплата) разделено сеткой 10 х 10. Ячейка — пересечение интервалов; примером может служить ячейка f = (30 < возраст < 35)л(1 < зарплата < 2). Область представляет собой прямоугольное объединение ячеек. A и B являются областями: A = (30 < возраст < 50) л (4 < зарплата < 8) и B = (40 < возраст < 60) л (2 < зарплата < 6). Плотные ячейки затемнены, и очевидно, что A u B является кластером. A является максимальной областью, содержащейся в этом кластере, тогда как A n B таковой не является. Минимальным описанием для этого кластера может служить следующее выражение ДНФ: ((30 < возраст < 50) л (4 < зарплата < 8)) ѵ ((40 < возраст < 60) л (2 < зарплата < 6)). Труды Кольского научного центра РАН. Серия: Технические науки. 2025. Т. 16, № 3. С. 35-55. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2025. Vol. 16, No. 3. P. 35-55. 10 э » 8 8 7 о 2 б X 5я 5 4 =. 1 0 2 0 2 5 3 0 3 5 4 0 4 5 5 0 5 5 6 0 6 5 7 0 Возраст Рис. 2. Иллюстрация примера Первый шаг алгоритма CLIQUE заключается в поиске интересных подпространств. Для этого выполняется поиск плотных ячеек, из которых в дальнейшем конструируются подпространства. Среди подпространств отбираются те, которые содержат достаточное количество точек. Для поиска плотных ячеек используется алгоритм «Снизу вверх». Алгоритм работает по уровням. Сначала он определяет © Зуенко О. Н., Фридман О. В., 2025 42