1.5. Матрица объект-объект и признак-признак. Расстояние и близость
Пусть имеется матрица данных X(N х п). Если рассматривать строки данной матрицы как N векторов xi, в пространстве п признаков, то естественно рассмотреть расстояние между двумя некоторыми векторами. Расстояния между всевозможными парами векторов дают матрицу R(N x N) расстояний типа объект - объект.
Напомним, что метрикой или расстоянием между векторами в пространстве признаков
16
называется некоторая величина d, удовлетворяющая следующим условиям:
1.d(x1, x2)>0, d(x1, x1)=0 ;
2. d(x1, x2)= d(x2, x1)
3. d(x1, x2)+ d(x2, x3) d(x1, x3) (неравенство треугольника).
Таким образом, матрица расстояний является симметричной с нулевой главной диагональю. Существуют различные метрики, но наиболее известной вообще и наиболее применяемой в обработке данных, в частности, является евклидова метрика
Часто используется линейная метрика вида
Применение линейной метрики оправдано, когда расстояние определяется как расстояние между домами в городе по кварталам, а не напрямик. Возможны и другие виды расстояний.
Часто рассматривается величина, обратная в некотором смысле расстоянию - близость. На практике часто используют функции близости вида
или
где определяет крутизну функции близости. Очевидно, что матрица близостей также является симметричной с единичной главной диагональю, так как (x1, x1)= 1.
Если рассмотреть признаки как п векторов в N-мерном пространстве объектов, то получим другое преобразование матрицы данных в матрицу R(n х п) типа признак - признак. Элементом rij такой матрицы является значение расстояния или близости между признаками Xi и Xj. Наиболее распространено представление в виде матрицы близостей между признаками, где под близостью понимается, например, корреляция соответствующих признаков.
Легко заметить, что содержательные задачи на матрице данных X(N х n) интерпретируются на квадратных матрицах R(N х N) и R(n х п) как выделение блочно - диагональной структуры путем одновременной перегруппировки строк и столбцов. Тогда в каждом диагональном блоке группируются элементы, близкие в соответствующем пространстве и далекие от элементов других блоков. Такая задача группировки известна как задача диагонализации матрицы связей (Рис. 1.8). Задача о диагонализации матрицы связей является наиболее общей для матриц связей произвольной природы. Особенно интересным является
17
случай, когда матрица связей является корреляционной матрицей. Именно для этого случая разработаны и широко применяются на практике специальные алгоритмы, известные как алгоритмы экстремальной группировки признаков (параметров).
X1 . . . X n X1 . . . X n
X1
.
.
.
XN
X1
G1
G2
…
Xn
G
3
Рис. 1.8.Диагонализация матрицы связей.