Алгоритм вычисления расстояния по Махалонобису

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 7Следующая ⇒

▷ Похожие статьи

Шаг 1. Вычислить средние значения существенных признаков объектов принадлежащих классу :

для , где - множество значений -го существенного признака, – количество объектов в классе, – количество существенных признаков. Тем самым будет найден и центр класса .

Шаг 2. Вычислить ковариации между всеми парами существенных признаков:

и составить ковариационную матрицу:

Шаг 3. Если матрица обратима, то вычислить расстояние по Махалонобису между предъявленным объектом и центром класса :

,

где - матрица, обратная к .

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

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

Найдем центры каждого класса. Координаты центров классов вычисляют как среднеарифметические значения одноименных, существенных признаков. Для первого класса:

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

Аналогичным образом найдем дисперсию второго существенного признака первого класса , и для второго класса . Тогда для среднеквадратического отклонения первого класса получим

,

а для второго класса

.

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

.

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

.

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

.

Определитель матрицы равен единице, . Найдем обратную матрицу . Элементы обратной матрицы находят по формуле

,

где - алгебраическое дополнение элемента в определителе .

По определению . - минор (определитель), который получают в результате вычеркивания в определителе -той строки и -того столбца. Вычислим элементы обратной матрицы . В соответствии с формулой необходимо вычислить алгебраические дополнения:

.

Таким образом,

.

Найдем расстояние между объектом и вторым классом. Для этого вычислим элементы матрицы

.

Далее вычислим произведение матриц

Тогда расстояние между объектом и вторым классом

.

ФУНКЦИИ СХОДСТВА.

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

Пусть заданы два объекта и , - бинарные значения существенных признаков этих объектов. Для того чтобы определить функции сходства введем в рассмотрение следующие параметры:

1. Количество одинаковых признаков, которые есть у объектов и :

; (2.13)

2. Количество одинаковых признаков, которых нет у объектов и :

; (2.14)

3. Количество одинаковых признаков, которых нет у объекта , и которые есть у :

; (2.15)

4. Количество одинаковых признаков, которые есть у объектов , и которых нет у :

. (2.16)

Рассмотрим пример, пусть заданы два объекта и . Вычислим значения параметров, приведенных выше, для этих двух объектов.

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

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

Рассмотрим применение функций сходства на простом примере распознавания объектов самолет, автомобиль и птица, которые характеризуются следующими признаками: крылья, колеса, двигатель и оперение. Установим значения существенных признаков для представителей этих классов (таблица 2.2).

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

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

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

РАССТОЯНИЕ МЕЖДУ СПИСКАМИ

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

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

и .

Введем параметр:

, при условии, что .

С учетом введенного параметра расстояние между списками будет определяться по формуле (расстояние по Кендалу):

. (2.17)

Рассмотрим пример. Пусть Заданы два объекта и . Вычислим расстояние между ними. В этом случае , , , , и , следовательно

.

Отсюда следует, что два списка упорядоченные одинаково являются идентичными. Пусть теперь . Тогда , и . При этом . В остальных случаях .

Если порядок следования элементов в двух списках одинаков, то и результат суммирования равен половине числа размещений . Но поскольку то

Для сопоставления списков, элементы которых выражаются не числами, а некоторыми понятиями, на их множестве необходимо предварительно установить некоторое отношение порядка.

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

	большое	красивое	холодное	безобразное	огромное

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

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры