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

Ограничение must-link между двумя объектами оІ и о . , обозначаемое как М!А()1',()/ ). предписывает, что оба объекта оІ и о. должны быть в одном кластере. Напротив, ограничение cannot-link между объектами оІ и о . , обозначаемое как ( '/.(о , ;о ■). предписывает, что эти два объекта не должны находиться в одном кластере. Согласно [9], ограничения на объекты кластеров имеют следующие свойства: 1. Ограничения must-link транзитивны: Пусть ССа и ССЬ являются связанными компонентами (подграфами, полностью связанными посредством ограничений must-link), пусть о; и Oj будут объектами в ССа и ССЪ соответственно, тогда: МІ, ( оі:ot ) : оі е СY \ е СY =>МІ,(ох:оѵ ) : V ох:о ѵ : охеССа;оуеССь. 2. Для ограничений cannot-link справедливо следующее: пусть ССа и ССЪ являются связанными компонентами (подграфами, полностью связанными посредством ограничений must-link), пусть о; и о . будут объектами в ССа и ССЪ соответственно, тогда: C l ( o !;oJ);o! eC C a;0j еСС ь ^ С і ( о х;оу );Ѵох;оу :ох еС С а;оу еСС ь. Идея о введении ограничений must-link и cannot-link может показаться простой, но на самом деле эти ограничения являются мощным инструментом для многих приложений. Увеличение количества ограничений на пары объектов может существенно улучшить точность результата кластеризации. Ограничения must-link и cannot-link также могут использоваться для выражения других пользовательских ограничений. В работе [10] введены ограничения 8 -constraint и е -constraint, которые могут быть обработаны совместно с ограничениями на пары объектов: • Ограничение 8 -constraint (также называемое minimum split constraint) выражает, что расстояние между любой парой точек, которые находятся в двух разных кластерах, должно быть не меньше, чем значение 8 . Это ограничение может быть представлено в виде конъюнкции ограничений must-link для всех пар объектов с расстоянием меньше, чем 8 . • Ограничение е -constraint для любого кластера Сс , содержащего более одного объекта, для каждого объекта о, е Сс должен существовать другой объект о . g Сс , такой, что расстояние между о; и о . не превышает б/;/ : < s . В работе показано, что это ограничение эквивалентно дизъюнкции ограничений must-link. Для каждой точки оІ вычисляется множество % объектов Oj таких, что: d tj < s . Ограничение e-constraint может быть представлено как дизъюнкция ограничений must-link между объектом о; и точками множества %. Другим ограничением, которое относится к ограничениям на объекты кластеров, является ограничение на максимальный диаметр (максимально возможное расстояние между объектами одного кластера). Это ограничение 121