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

Рис. 6. Результаты применения метода FPF (Furthest Point First) Значения диаметра меньше 14 попадают в зеленую зону и нас не интересуют, поскольку для соответствующих объектов ограничения вида (d > D) ^ (G ф G ) вырождается в тождественно истинное утверждения. Значения диаметра больше 28 попадают в красную зону, и для них формируется ограничение cannot-link G ф G . На рисунке 7 показан фрагмент оценки процентного соотношения между объектами, исключаемыми из дальнейшего рассмотрения, и объектами, для которых требуется генерировать либо упрощенное ограничение G ф G , либо ограничение вида (d >D) ^ (G ф G ). Таким образом, на предварительном этапе нам удалось исключить из рассмотрения 30 процентов ячеек. Далее опишем второй шаг метода. На втором шаге уточняется верхняя граница интервала для диаметра разбиения. Для этого применяется модифицированный метод иерархической кластеризации мультимножеств КЛАВА-И [2]. В процессе объединения кластеров учитываются ограничения cannot link, то есть, какие пары объектов не попадают в один кластер. То есть, при выборе кластеров для объединения мы не рассматриваем объекты из красной зоны. На каждом шаге иерархической кластеризации красная зона разрастается. Допустим, если мы объединяем два последних кластера {М,№} и {N 2 ,N 4 }, тогда запрещенные комбинации на объединение каждого из кластеров становятся запретами для итогового кластера {N 1 N 3 N 2 N 4 }, как это показано на рисунках 8,9. 83