Мера сходства объектов и классов. Расстояния.

Кластерный анализ

Введение

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

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

1. Увеличения быстродействия и объемов памяти ЭВМ;

2. Разработки высокоэффективного прикладного программного обеспечения для автоматизации процессов обработки, классификации и идентификации информации.

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

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

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

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

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

Следует отметить, что это понятие заимствовано из англоязычных работ по теории распознавания, в которых употребляется термин «pattern recognition». Термин «pattern», кроме значения «образ», имеет еще и такие значения: модель, стиль, режим, закономерность и образ действия.

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

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

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

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

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

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

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

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

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

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

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

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

ПРИЗНАКИ ОБЪЕКТА

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

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

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

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

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

Пусть - множество объектов, а - множество всех признаков этих объектов:

.

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

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

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

- вероятностный: каждому элементу множества ставится в соответствие вероятность наблюдения некоторого признака;

- двоичный: при наличии у объекта данного свойства или при его отсутствии.

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

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

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

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

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

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

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

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

,

где

Очевидно, что не исключены случаи, когда для классификации будут предъявляться «треугольники», у которых сумма углов не только равна 180⁰, но может быть меньше или больше 180⁰.

Будем отображать множество всех треугольников точками в трехмерном пространстве. Назовем его пространством образов или существенных признаков. Тогда множество таких треугольников в пространстве существенных признаков будет отображаться точками расположенными внутри куба (см. рис. 2.3).

Выделим в пространстве существенных признаков области, которые содержат треугольники, суммы углов которых равны, меньше и больше 180⁰. Функцию

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

– плоскость, содержит «правильные» треугольники;

– область в кубе для которой - треугольники, у которых сумма углов меньше 180⁰;

– область - треугольники, у которых сумма углов больше 180⁰.

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

На множестве «правильных» треугольников тоже выделим три класса (плоскость на рис. 2.4): . Точка , для которой выполняется условие - это класс равносторонних треугольников. Класс равнобедренных треугольников, отображается прямой . Остальная часть плоскости - это треугольники общего вида. В данном случае множество принятия решений состоит из трех решающих правил – это соотношения, которым должны удовлетворять значения существенных признаков объекта :

.

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

Метрика Махалонобиса

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

Метрика Махаланобиса позволяет значительно улучшить процедуру обучения автоматической системы классификации в следующих случаях:

1. Существенные признаки объектов выбраны неадекватно, классы плохо разделяются;

2. Существенные признаки объектов сильно коррелируют между собой;

3. Разделяющая поверхность между классами сильно изогнута;

4. Классы могут состоять из подклассов, не соприкасающихся между собой в пространстве существенных признаков;

5.
Разделяющие поверхности между классами имеют очень сложную форму.

Эти случаи размещения объектов в пространстве существенных признаков проиллюстрированы на рис. 2.10.

Расстояние по Махалонобису между объектом и центром некоторого класса вычисляется по формуле:

, (2.7.)

где - матрица, обратная к ковариационной матрице для данного класса, матрица – столбец элементы которой – разности одноименных координат объекта и центра класса .

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

Ковариационная матрица

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

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

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

.

Элементы ковариационной матрицы – ковариации – для объектов -того класса вычисляются по формуле:

, (2.12)

где - номер объекта данного класса, и - номера признаков, а -номер класса, и - множества, состоящее из значений соответственно -го и -го существенных признаков (напомним, что -количество объектов в данном классе); и - средние значения соответственно -го и -го существенных признаков (см. формулу (2.8)).

Ковариации обладают следующими важными свойствами:

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

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

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

– , где и – стандартные отклонения -го и -го существенных признаков соответственно (формула (2.10));

– , где – стандартное отклонение и – дисперсия -го существенного признака.

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

Отметим, что ковариационная матрица будет вырожденной в следующих двух случаях:

1. Если количество объектов в данном классе меньше, чем количество существенных признаков плюс 1, т.е. .

2. Если степень корреляции существенных признаков максимальна, т.е. .

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

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

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

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

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

; (2.13)

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

; (2.14)

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

; (2.15)

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

. (2.16)

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

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

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

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

Таблица 2.2. Бинарные значения существенных признаков
	Крылья	Колеса	Двигатель	Оперение
	Автомобиль
	Самолет
	Птица

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

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

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

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

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

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

и .

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

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

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

. (2.17)

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

.

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