Расстояние между кластерами

ХЕММИНГОВО РАССТОЯНИЕ

(7.4)

используя как мера различия объектов, задаваемых дихотомическими признаками. Хеммингово расстояние равно числу несовпадений значений соответствующих признаков в рассматриваемых i -м и j -м объектах.

─ расстояние, измеряемое по принципу «ближайшего соседа»

(7.5)

─ расстояние, измеряемое по принципу «дальнего соседа»

(7.6)

─ расстояние, измеряемое по «центрам тяжести» групп

(7.7)

─ расстояние, измеряемое по принципу «средней связи». Это расстояние определяется как среднее арифметическое всех парных расстояний между представителями рассматриваемых групп

(7.8)

Академиком А.Н.Колмогоровым было предположено:

(7.9)

Можно показать, что при

при

при

.

Из формулы (7.9) следует, что если -группа элементов, полученная путем объединения кластеров , то обобщенное расстояние между кластерами и определяется по формуле

(7.10)

агломеративных иерархических кластер – процедурах, так как принцип работы таких алгоритмов состоит в последовательном объединении сначала самых близких элементов, а затем и целых групп все более и более отдаленных друг от друга элементов.

При этом расстояние между классами и , являющимся объединением двух других классов , можно определить по формуле:

(7.11)

где - расстояние между классами ;

-числовые коэффициенты, значение которых определяет специфику процедуры, ее алгоритм.

Например, при и приходим к расстоянию, построенному по принципу «ближайшего соседа». При и расстояние между классами определяется по принципу «дальнего соседа», как расстояние между двумя самыми дальними элементами этих классов. И наконец, при

Соотношение (7.11) приводит к расстоянию ρ между классами, вычисленному как среднее из расстояния между всеми парами элементов, один из которых берется из одного класса, а другой – из другого класса.

Дата добавления: 2014-01-20