Меры сходства объектов многомерной выборки

Для решения задачи классификации необходимо ввести понятие сходства объектов по наблюдаемым признакам. В каждый класс должны попасть объекты, обладающие определенной степенью сходства.

В кластерном анализе для количественной оценки сходства вводится понятие метрики. Сходство между объектами будет определяться в зависимости от расстояния в выбранном метрическом пространстве. Если объект, описываемый m признаками представить точкой в k – мерном пространстве, то сходство объектов друг с другом будет определяться как расстояние в данном метрическом пространстве.

В кластерном анализе используется большое разнообразие способов измерения расстояний (метрик). Рассмотрим наиболее распространенными метриками сходства.

1. Евклидово расстояние:

(7.1)

2. Взвешенное евклидово расстояние

(7.2)

3. Расстояние Хемминга (citi-block или Манхеттенское):

(7.3)

4. Расстояние Минковского:

(7.4)

5. Расстояние Махаланобиса:

, (7.5)

где - расстояние между i –м и j – м объектами;

- значение r – го признака соответственно у i – го и j – го объекта;

- вектора значений признаков у i – го и j – го объекта;

- матрица обратная ковариационной матрице, рассчитанной по всей выборке;

- вес, присваиваемый k – ой переменной.

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

Для решения задачи классификации необходимо рассматривать расстояния между каждой парой объектов. Расстояния между парами объектов сводятся в матрицу сходства. Это симметричная матрица. По диагонали матрицы располагаются нулевые значения. Рассмотрим расчет матриц сходства для различных метрик на примере.

Сформируем таблицу данных (с помощью программы генерация многомерных нормальных смесей).

Описание данных:

- количество классов 1, число признаков -3, число наблюдений – 20.

- вектор математических ожиданий , вектор дисперсий D, ковариационная матрица Cov.

Таблица данных (признаки ) представлена на рис. 7.1. В той же таблице произведены расчеты евклидова расстояния (),расстояния Хемминга (), расстояния Махаланобиса (). На рис. 7.1 приведены формулы для расчета расстояний от первого объекта до всех остальных, то есть расчет первых столбцов матриц расстояний тремя различными способами.

Расчет расстояний Махаланобиса выполнен по этапам:

- расчет ковариационной матрицы выборки с помощью программы Ковариация пакета анализа EXCEL (рис. 7.2);

- расчет матрицы обратной ковариационной с помощью функции МОБР (пример использования функции МОБР приведен в приложении "Операции над матрицами");

- расчет разности векторов ;

- расчет произведения, полученных векторов на матрицу обратную ковариационной ;

- окончательный расчет расстояния Махаланобиса с учетом промежуточных вычислений:

Для расчета матриц расстояний была разработана специальная программа (макрос EXCEL). Для установки программы необходимо скопировать файл EXCEL, содержащий макрос. После установки макроса обращение к программе производится по команде Ctrl+q. Перед обращением программе должен быть выделен диапазон для которого рассчитывается матрица расстояний. Интерфейс программы приведен на рис.7.3. Программа рассчитывает матрицу расстояний по указанному методу и размещает ее в указанном месте. Фрагмент матрицы расстояний приведен на рис. 7.4.

Сравнение результатов, рассчитанных по формулам в таблице EXCEL и рассчитанных с помощью программы, показывает полное совпадение результатов. В дальнейшем для расчета матриц расстояний студенты могут использовать специальную программу.

Рис. 7.1. Расчет первого столбца матриц расстояний (евклидова, Хемминга, Махаланобиса)

Рис. 7.2. Расчет ковариационной и обратной к ней матриц

Рис. 7.3. Интерфейс макроса расчета матриц сходства

Рис. 7.4. Фрагмент матрицы расстояний

Оценивать сходство объектов с помощью мер расстояния удобно при использовании числовых признаков. Но часто встречаются признаки, измеренные в других шкалах (например, в ранговой, или, вообще, в номинальной). В этом случае все признаки, используемые для классификации приводятся к представлению в бинарном (двоичном) коде. Предположим, что такое преобразование было выполнено. То есть каждый объект описывается вектором , каждая из компонент которого принимает значения 0 или 1.

Для измерения сходства i-го и j – го объектов введем следующие обозначения частот:

- число совпадающих единичных признаков у обоих пар объектов (пар (1,1));