Труды КНЦ вып.12 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 5/2021(12))

Таким образом, актуальным направлением исследований представляется разработка способов ускорения обработки нечисловых ограничений (новых методов распространения нечисловых ограничений). Данное направление исследований наиболее полно отражено в [3]. Другое направление работ, которое активно развивается в настоящих исследованиях, связано с тем, чтобы уменьшить количество ограничений, используемых для представления задачи, и упростить их вид. В ходе исследований было предложено генерировать ограничения не для всех пар объектов, а лишь для некоторых, что способно существенно снизить размерность решаемой задачи. Предлагаемый метод Проиллюстрируем применение предлагаемого подхода на примере задачи кластеризации c критерием минимизации диаметра разбиения. Пусть задача состоит в том, что требуется разбить n объектов на k кластеров таким образом, чтобы диаметр разбиения был минимальным среди всех возможных разбиений. Диаметр разбиения - это максимальный диаметр для всех кластеров разбиения. Диаметр кластера - это максимальное расстояние между любыми двумя точками, принадлежащими данному кластеру. Описываемая модель позволяет искать разбиение при условии, что не задано точное число k итоговых кластеров, а задан лишь интервал k е [kmin, kmax]. В настоящей работе предполагается, что и кластер и кластеризуемый объект представляются как мультимножества, а расстояние между ними ( dij ) ищется с помощью метрик в пространстве мультимножеств Петровского [3]. Кратко опишем предлагаемый подход: 1 шаг. Оценить диапазон значений, в который должен попадать искомый оптимальный диаметр разбиения. Для нахождения первоначального разбиения предлагается использовать метод FPF (Furthest Point First), представленный в [4]. Данный приближенный метод позволяет найти оценку для оптимального диаметра разбиения: D е ^ d FF / 2, d FFF J . При этом, чем точнее мы определяем нижнюю границу, тем менее точной оказывается верхняя, и наоборот. Как правило, этот метод позволяет получить хорошую оценку именно для нижней границы. На основе полученной оценки генерируются ограничения cannot-link ( Gt ф Gj ) для тех пар кластеров, для которых dtJ > dFPF . Для пар объектов, удовлетворяющих условию dij < (dFFF / 2 ), ограничений и вовсе генерировать не требуется, поскольку для них ограничения вида (d > D) ^ (G ф G ) вырождаются в тождественно истинные утверждения. 2 шаг. Выполнить конкретизацию верхней границы интервала D е [ dFFF /2 , d FFF ] . Для этого осуществляется процедура иерархической кластеризации мультимножеств, описанная в [3]. Существенная модификация данной процедуры заключается в том, что в ходе кластеризации анализируются ограничения cannot-link . Применение данного метода повышает эффективность вычислительных процедур и позволяет сократить перебор вариантов объединения кластеров. В результате данного шага получаем новый интервал для оценки D . 77