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

В кластерном анализе наиболее популярной метрикой расстояния является Евклидово расстояние и квадрат Евклидова расстояния [1]. Пусть дано два объекта 0;; Oj, тогда евклидово расстояние между ними определяется как: d.. = yj(оп - 0jl f + (oi2 - oJ2f +... + (oip - oipf . Квадрат Евклидова расстояния определяется как: d p = ( ° П ~ ° j \ f + ( ° І 2 ~ ° J 2 f + ••• + ( ° i p ~ ° i p f - Другой популярной мерой расстояния является Манхэттенское расстояние [1], определяемое как: d =1 о . , - о I + 1 о п- о .п I + . . . + 1 о - о I. у I іі j\ I I i2 j 2 1 I ip ip I Аналогично, обозначим меру сходства между двумя объектами оІ и о . как 5.. . У 1. Мера сходства широко используется в спектральной кластеризации. Как правило, рассчитывается Гауссова функция различия [2]: s,j =ехр ( 2<хг2у где а і — параметр. Существуют и другие меры сходства, например нормализованная корреляция Пирсона ( normalized Pearson correlation), мера Жакара ( Jaccard measure), мера коэффициента игральной кости ( dice coefficient measure) и др. [1]. Задача кластеризации состоит в разбиении совокупности объектов на классы (группы, кластеры) таким образом, чтобы выполнялось некоторое условие/критерий оптимизации. При кластеризации формируемые классы должны удовлетворять двум свойствам: 1. Однородность {homogeneity). 2. Хорошая разделимость/различимость (well separated). Эти требования обычно выражаются посредством критерия оптимизации. Тогда задача кластеризации может быть определена как проблема оптимизации, состоящая в поиске такого разбиения объектов, которое оптимизирует заданный критерий. Говоря об однородности, предъявляются некоторые требования к объектам внутри одного кластера. Например, может быть задан критерий, состоящий в том, что оптимальным является разбиение с минимальным диаметром (относительно других возможных разбиений). Напомним, что диаметр разбиения — это максимальный диаметр среди всех диаметров кластеров, принадлежащих данному разбиению. Диаметр кластера - это расстояние между наиболее удаленными точками кластера. Вводя критерии разделимости, предъявляются определенные требования к объектам, которые попадают в различные кластеры. В качестве примера подобного критерия может служить критерий, состоящий в том, что оптимальным является разбиение (относительно других возможных разбиений) с максимальным значением функции split. Для конкретного разбиения функция split показывает минимально возможное расстояние между двумя различными кластерами данного разбиения. 118