Понятие расстояния. Функция расстояния

Понятно то, что объекты i-ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками x_i и x_j было бы достаточно малым, и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между x_i и x_j из Е^d, где Е^d – d-мерное евклидово пространство. Неотрицательная функция L(x_i,x_j) называется функцией расстояния (метрикой), если она отвечает основным аксиомам метрики [25].

Это неотрицательность расстояния:

L(x_i, x_j) ³ 0. (1)

Симметрия:

L(x_i, x_j) = 0, (2)

тогда и только тогда, когда x_i = x_j.

Неразличимость тождественных объектов:

L(x_i, x_j) = L(x_j, x_i). (3)

Неравенство треугольника:

L(x_i, x_j) £ L(x_i, x_k) + L(x_k, x_j). (4)

Значение L(x_i, x_j) для x_i и x_j называется расстоянием между x_i и x_j и эквивалентно расстоянию между G_i и G_j соответственно выбранным характеристикам F₁, F₂, F₃,..., F_d.. В многочисленных изданиях посвященных кластерному анализу описано более 50 различных способов вычисления расстояния между объектами [25, 27].

Большинство расстояний являются расстояниями Минковского (геометрические расстояния в многомерном пространстве), и общая формула для них выглядит, как [5]:

. (5)

Наиболее часто употребляются следующие функции расстояний, представленные в Таблице 1 [25].

Таблица 1 – Некоторые функции расстояния

Название	Формула
Евклидово расстояние	(6)
Манхэттэнское (сити-блок, хэмминговское) расстояние	(7)
Супремум – норма (расстояние Чебышева)	(8)

Манхэттэнское расстояние, как правило, используется в случае использования дихотомических (имеющих всего два значения) качественных признаков. То есть, например, при бинарном представлении встречаемости терминов.

Пусть n измерений x₁, x₂,..., x_n представлены в виде матрицы данных X размером p ´ n:

. (9)

Тогда расстояние между парами векторов L(x_i,x_j) могут быть представлены в виде симметричной матрицы расстояний:

. (10)