Меры сходства

ФИЛИАЛ  ФГБОУ ВПО 

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИИ И УПРАВЛЕНИЯ

ИМ. К.Г. РАЗУМОВСКОГО»

В Г.КАЛИНИНГРАДЕ

 

 

РЕФЕРАТ

 

по дисциплине:      «Системы искусственного                                                                                                                                                               

                                           интеллекта»

 

Тема:                             «Меры сходства»

 

 

Проверил:                                 Выполнил:

 

 

 

 

 

 

Студент 4 курса

Факультета______

Специальности________

Группы 

личный номер______

Ф.И.О.

 

 

 

 

 

 

 

 

 

 

 

 

2013. год

Содержание:

 

1.Общие понятия

 

2.Применение классической теории информации К.Шеннона для расчета весовых коэффициентов и мер сходства

 

2.1.Формальная  постановка задачи

 

2.2.Информация  как мера снятия неопределенности

 

2.3.Количество  информации в индивидуальных  событиях и лемма Неймана–Пирсона

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Общие понятия

 

Коэффициент сходства (также  мера сходства, индекс сходства) — безразмерный показатель, применяемый в биологии для количественного определения  степени сходства биологических  объектов. Также известен под названиями «мера ассоциации», «мера подобия» и др.

 

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

 

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

 

Большинство коэффициентов  нормированы и находятся в диапазоне от 0 (сходство отстутствует) до 1 (полное сходство). Сходство и различие взаимодополняют друг друга (математически это можно выразить так: Сходство = 1 − Различие).

 

Коэффициенты сходства можно  условно разделить на три группы в зависимости от того, какое число  объектов рассматривается:

-унарные — рассматривается один объект. В эту группу входят меры разнообразия, меры концентрации.

-бинарные — рассматривается два объекта. Это наиболее известная группа коэффициентов.

-n-арные (многоместные) — рассматривается n объектов. Эта группа наименее известна.

 

2.Применение классической теории информации К.Шеннона для расчета весовых коэффициентов и мер сходства

 

Формально, распознавание  есть не что иное, как принятие решения  о принадлежности распознаваемого  объекта или его состояния  к определенному классу (классам) . Из этого следует внутренняя и органичная связь методов распознавания образов и принятия решений. Аналитический обзор позволяет сделать вывод, что наиболее глубокая основа этой связи состоит в том, что и распознавание образов, и принятие решений есть прежде всего снятие неопределенности. Распознавание снимает неопределенность в вопросе о том, к какому классу относится распознаваемый объект. Если до распознавания существовала неопределенность в вопросе о том, к какому классу относится распознаваемый объект или его состояние, то в результате распознавания эта неопределенность уменьшается, причем возможно и до нуля (когда объект идентифицируется однозначно). Принятие решения (выбор) также снимает неопределенность в вопросе о том, какое из возможных решений будет принято, если существовало несколько альтернативных вариантов решений и принимается одно из них.

 

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

 

 

2.1.Формальная постановка задачи

 

В рефлексивных АСУ активными  объектами модели распознавания  образов и принятия решений применимы  в подсистемах идентификации  состояния АОУ и выработки  управляющего воздействия: идентификация  состояния АОУ представляет собой  принятие решения о принадлежности этого состояния к определенной классификационной категории (задача распознавания); выбор многофакторного  управляющего воздействия из множества  возможных вариантов представляет собой принятие решения (обратная задача распознавания).

 

Распознавание образов есть принятие решения о принадлежности объекта или его состояния  к определенному классу. Если до распознавания существовала неопределенность в вопросе о том, к какому классу относится распознаваемый объект или  его состояние, то в результате распознавания  эта неопределенность уменьшается, в том числе может быть и  до нуля (когда объект идентифицируется однозначно). Из данной постановки непосредственно  следует возможность применения методов теории информации для решения  задач распознавания образов  и принятия решений в АСУ.

 

 

2.2.Информация как мера снятия неопределенности

 

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

 

Так в результате процесса познания уменьшается неопределенность в наших знаниях о состоянии  объекта познания, а в результате процесса труда (по сути управления) –  уменьшается неопределенность поведения  продукта труда (или объекта управления). В любом случае количество переданной информации представляет собой количественную меру степени снятия неопределенности.

 

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

 

 

2.3.Количество информации в индивидуальных событиях и лемма Неймана–Пирсона

 

В классическом анализе Шеннона  идет речь лишь о передаче символов по одному информационному каналу от одного источника к одному приемнику. Его интересует прежде всего передача самого сообщения.

 

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

 

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

 

Для решения поставленной задачи необходимо вычислять не средние  информационные характеристики, как  в теории Шеннона, а количество информации, содержащееся в конкретном i–м признаке (символе) о том, что он пришел от данного j–го источника информации. Это позволит определить и суммарное количество информации в сообщении о каждом информационном источнике, что дает интегральный критерий для идентификации или прогнозирования состояния АОУ.

 

Логично предположить, что  среднее количество информации, содержащейся в системе признаков о системе классов является ничем иным, как усреднением (с учетом условной вероятности наблюдения) "индивидуальных количеств информации", которые содержатся в конкретных признаках о конкретных классах (источниках), т.е.: это выражение определяет так называемую "плотность информации", т.е. количество информации, которое содержится в одном отдельно взятом факте наблюдения i–го символа (признака) на приемнике о том, что этот символ (признак) послан j–м источником.

Если в сообщении содержится M символов, то суммарное количество информации о принадлежности данного  сообщения j–му информационному источнику (классу) составляет:н еобходимо отметить, что применение сложения в выражении является вполне корректным и оправданным, так как информация с самого начала вводилась как аддитивная величина, для которой операция сложения является корректной.

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

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

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

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

 

Таким образом, распознавание  образов есть принятие решения о  принадлежности объекта или его  состояния к определенному классу. Если до распознавания существовала неопределенность в вопросе о  том, к какому классу относится распознаваемый объект или его состояние, то в  результате распознавания эта неопределенность уменьшается, в том числе может  быть и до нуля. Понятие информации может быть определено следующим  образом: "Информация есть количественная мера степени снятия неопределенности". Количество информации является мерой  соответствия распознаваемого объекта (его состояния) обобщенному образу класса.

 

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