Труды КНЦ (Технические науки вып. 7/2023(14))

Труды Кольского научного центра РАН. Серия: Технические науки. 2023. Т. 14, № 7. С. 16-25. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2023. Vol. 14, No. 7. P. 16-25. Ограничения на пары объектов бывают двух типов [4]: ограничения must-link и cannot-link. Ограничение must-link означает, что два объекта oi и oj должны попасть в один кластер. И наоборот: ограничение cannot-link гласит, что два объекта oi и oj должны быть в разных кластерах. Ограничения на объекты выглядят простыми, но, по сути, являются очень полезными и эффективными для множества приложений. Их применение зачастую приводит к повышению точности результата. Кроме того, ограничения must-link и cannot-link также могут использоваться для выражения других пользовательских ограничений. Еще одним ограничением на объекты является пороговое значение максимального диаметра, которое определяет верхнюю границу диаметра кластера, обозначающую, что между каждой парой объектов кластера расстояние не может превышать эту границу. Это требование может рассматриваться как конъюнкция ограничений cannot-link между всеми парами объектов с расстоянием, превышающим границу. В подходах, основанных на ограничениях, алгоритм кластеризации модифицируется для интеграции попарных ограничений, тогда как в подходах, основанных на расстоянии, изменяется только мера расстояния. Один из алгоритмов, основанных на ограничениях, является модификацией метода k-means [4]. Он интегрирует в себе ограничения must-link и cannot-link , и на каждой итерации, когда происходит обновление разбиения, все эти ограничения должны удовлетворяться. Но у этого алгоритма есть существенный недостаток, т. к. в нем не предусмотрена процедура возврата. Поэтому алгоритм может не найти никакого разбиения, даже если оно существует. Эту проблему можно обойти, если допустить удовлетворения не всех ограничений, а только большинства из них [5, 6]. Другим способом ввести ограничения на объекты является модификация метрики расстояния или целевой функции [7]. Основная идея заключается в том, что если на два объекта oi и oj накладывается ограничение must-link , то расстояние между ними может быть меньше обычного, чтобы у них было больше шансов оказаться в одном кластере. Похожий подход применяется и к ограничению cannot-link . Как раз такой подход предлагается в работе [8]. Задача нахождения метрики расстояния здесь формулируется как задача оптимизации. Целевая функция является суммой расстояний между парами объектов ограничения must-link . Алгоритм призван минимизировать эту сумму. При этом расстояние между парами объектов ограничения cannot-link должно превышать некоторую константу. Ограничения на кластеры, соответственно, накладывают требования на кластеры. Помимо ограничения на минимальное разбиение, максимальный диаметр, существуют еще ограничения на кластер: • минимальная мощность (населенность) кластера — это ограничение требует, чтобы число объектов в каждом кластере было не меньше заданной границы а: 1 Cc I - a,^c6 I1,k] ; • максимальная мощность кластера — требует, чтобы число объектов в каждом кластере было не больше заданной границы в: 1 Cc \-Р>^c 6 [1>k] ; • ограничение на среднюю населенность кластера требует, чтобы соблюдался баланс, и все кластеры были примерно одного размера, т. е. отношение между размером самого маленького min.6[U]|C | >ѳ и самого большого кластера было больше заданной границы Ѳ: maxmui 1 Cj I . В работе [9] предложен другой тип ограничений для алгоритма кластеризации, который использует относительное сравнение: x ближе к y , чем к z . Данный алгоритм кластеризации исследует лежащую в основе меру различия. Как показывают эксперименты на многомерных текстовых наборах данных, предложенный алгоритм точнее и надежнее, чем аналогичные алгоритмы, использующие ограничения must-link и cannot-link . Идея данного алгоритма заключается в том, что объекты могут быть разбиты на кластеры неверно, но при этом они удовлетворяют ограничению cannot-link . Пары же, которые удовлетворяют ограничению must-link , могут соответствовать разным кластерам. Поэтому вводятся относительные сравнения под названием триплетные ограничения (triplet constraints ). А также предлагается алгоритм кластеризации, который не только учитывает триплетные ограничения, но и одновременно изучает © Зуенко А. А., Зуенко О. Н., 2023 18