5.3. Расстояние между классами и мера близости классов

При конструировании различных процедур классификации (кластер-процедур) в ряде ситуаций оказывается целесообразным введение понятия расстояния между целыми группами объектов, так же как и понятия меры близости двух групп объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть группа (класс, кластер) объектов, — число объектов, образующих группу вектор — среднее арифметическое векторных наблюдений, входящих в (другими словами, ) — «центр тяжести» группы), а — расстояние между группами S и

Ниже приводятся наиболее употребительные и наиболее общие расстояния и меры близости между классами объектов.

Расстояние, измеряемое по принципу «ближнего соседа» («nearest neighbour»)

Расстояние, измеряемое по принципу «дальнего соседа» («furthest neighbour») [262, 224]

Расстояние, измеряемое по «центрам тяжести» групп [262, 224]

Мера близости групп, основанная на потенциальной функции [57]

Расстояние, измеряемое по принципу «средней связи».

Определяется [262, 224) как арифметическое среднее всевозможных попарных расстояний между представителями рассматриваемых групп, т. е.

Естественно задать вопрос: нельзя ли получить достаточно общую формулу, определяющую расстояние между классами по заданному расстоянию между отдельными элементами (наблюдениями), которая включила бы в себя в качестве частных случаев все рассмотренные выше виды расстояний?

Изящное обобщение такого рода, основанное на понятии так называемого «обобщенного среднего», а точнее, степенного среднего, было предложено А. Н. Колмогоровым. Под обобщенным средним величин понимается выражение вида , в котором — некоторая функция и соответственно — преобразование, обратное к F. Частным случаем обобщенного среднего является степенное среднее, определяемое как

Нетрудно показать, что (при )

Обобщенное (по Колмогорову) расстояние между классами, или обобщенное -расстояние, вычисляется по формуле

В частности, при и при имеем

Очевидно также

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

Понятие расстояния между группами элементов особенно важно в так называемых агломеративных иерархических кластер-процедурах, поскольку принцип работы таких алгоритмов состоит в последовательном объединении элементов, а затем и целых групп, сначала самых близких, а потом все более и более отдаленных друг от друга. Подробнее об агломеративных иерархических процедурах см. в гл. 8. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным определить порядок пересчета расстояния между классом и классом являющимся объединением двух других классов по расстояниям между этими классами. В [255] предлагается следующая общая формула для вычисления расстояния между некоторым классом и классом

где — числовые коэффициенты, значения которых и определяют специфику процедуры, ее нацеленность на решение той или иной экстремальной задачи. Так, например, полагая приходим к расстоянию, измеряемому по принципу «ближайшего соседа».

Если же положить то расстояние между двумя классами определится как расстояние между двумя самыми далекими элементами этих классов, по принципу «дальнего соседа». И наконец, выбор коэффициентов соотношения (5.9) по формулам

приводит к расстоянию между классами, вычисленному как среднее из расстояний между всеми парами элементов, один из которых берется из одного класса, а другой — из другого.

То, что формула для и, в частности, выбор коэффициентов в этой формуле зачастую определяют нацеленность соответствующей агломеративной иерархической процедуры на решение той или иной экстремальной задачи, т. е. в каком-то смысле определяет ее оптимальную критерийную установку, поясняет, например, следующий результат [331]. Оказывается, если для вычисления воспользоваться следующей модификацией формулы (5.9):

то соответствующий агломеративный иерархический алгоритм обладает тем свойством, что на каждом шаге объединение двух классов приводит к минимальному увеличению общей суммы квадратов расстояний между элементами внутри классов. Отметим сразу, что такая пошаговая оптимальность алгоритма в указанном смысле, вообще говоря, не влечет его оптимальности в том же смысле для любого наперед заданного числа классов, на которые требуется разбить исходную совокупность элементов.