Принятие решений на примере задачи распознавания образов с использованием алгоритма «Голотип N»

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

Мой курсач КВ.doc

Международный университет природы, общества и человека «Дубна»

Кафедра системного анализа и управления

«Теория принятия решений»

«Принятие решений на примере задачи распознавания образов с использованием алгоритма «Голотип N»»

студентка группы 2071

Волостникова К. С.

проф. Черемисина Е.Н.

доцент Крейдер О.А.

Оглавление

Применение алгоритма «Голотип N» для распределения абитуриентов………………….…8

Список используемой литературы…………………………………………………… ……….18

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

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

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

Существует множество различных алгоритмов, позволяющих определить принадлежность объекта к образу. Например, «Дискриминантная функция», «Голотип 1», «Голотип N», «Энтропия», «Тесты», «Кора», «Метод эталонов» и т. д. Прежде чем приступить к распознаванию и выбору алгоритма необходимо анализировать данные, чтобы ошибка при отнесении объекта к образу была минимальной либо отсутствовала вовсе. Подходящий алгоритм распознавания выбирается в зависимости от того, сколько образов присутствует в материале обучения, а также от взаиморасположения объектов в пространстве свойств.

В данной курсовой работе рассматривается применение алгоритма «Голотип N» в практической задаче. Задача состоит в распознавании образов—результатов экзаменов ЕГЭ абитуриентов, поступавших в университет «Дубна» в 2009 году со второй волной на три различные специальности. Необходимо с помощью алгоритма «распознать» эти объекты и соотнести их к соответствующим образам—наиболее подходящим по их результатам специальностям.

Использование алгоритма для распределения абитуриентов в университет «Дубна» по специальностям Прикладная информатика (по областям), Государственное и муниципальное управление (ГМУ), Менеджмент. В 2009 году для поступления на эти специальности требовались результаты ЕГЭ по трем предметам: математика, русский язык, обществознание. Однако имелись приоритеты для каждой специальности: для ПИ — математика, для ГМУ — обществознание, будущим же менеджерам приходилось показать наивысшие результаты по русскому языку. В приемной комиссии абитуриент заполнял бланк для поступления в МУПОЧ «Дубна», называя несколько специальностей, на которые он бы хотел пройти (для прохождения на которые у него имелись соответствующие результаты ЕГЭ), и в соответствии с его результатами он определялся на наиболее подходящую специальность. Этот пример вполне подходит для применения и тщательного изучения алгоритма «Голотип N», что и является основной задачей данной курсовой работы.

Показать применение алгоритма «Голотип N» при решении практической задачи—распределения абитуриентов, поступающих в МУПОЧ «Дубна» со второй волной.

Для анализа представлены следующие данные:

Представления о модели

Алгоритм «Голотип N» используется в ситуациях, когда в МО представлены объекты k образов, где k>=2. Отсутствуют требования жесткой компакции исследуемых объектов, в качестве исходных данных могут присутствовать объекты, свойства которых измерены в разных шкалах, в алгоритмах используется «бюрократический» подход к распознаванию, т.е. ситуация, когда один раз проводится процесс обучения и строится решающее правило, и затем это решающее правило многократно применяется к объектам экзамена.

С помощью программы MS Office Excel и алгоритма для распознавания образов «Голотип N» абитуриенты будут распределены по наиболее подходящим для них специальностям.

Критерии оценки результата

Все образы МЭ распознаны и принадлежат к одному из образов МО.

Алгоритм «Голотип N»

Назначение – решение задач распознавания в ситуациях, когда в МО представлены объекты k образов, где k>=2.

• В материале обучения присутствуют представители всех образов.
• Для каждого объекта указана его принадлежность к образу.
• В процессе распознавания определяется принадлежность объектов экзамена к одному из образов.
• Распознавание может проводиться в двух режимах: с отказом и без отказа.
• ТОС должна быть без пропусков; свойства — арифметические, логические 1-го и 2-го рода.

Шаг 1. Постановка задачи.

На данном шаге замеряются необходимые свойства, все исходные данные заносятся в ТОС.

Шаг 2. Вычисление экстремальных разностей.

По каждому свойству определим минимальное и максимальное значения и вычислим экстремальные разности: , где k= 1,2..m и m – общее число свойств.

Шаг 3. Введение меры сходства.

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

1. , если свойство является арифметическим или логическим 2-го рода.
2. , если свойство является логическим 1-го рода.

Шаг 4. Построение матрицы мер сходства для каждого свойства.

, где k = 1,2..m и m – общее число свойств; i, j = 1,2..n и n – количество всех объектов в МО.

Шаг 5. Вычисление общей матрицы мер сходства.

, где – вес k-го свойства.

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

Шаг 6. Вычисление порога для разбиения МО на компактные группы.

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

Шаг 7. Построение голотипов и радиусов.

Голотип – это тот объект, у которого средняя мера сходства с остальными объектами данной группы является максимальной, т.е. тот на который все остальные объекты в группе наиболее похожи. Голотип находится по формуле: , где m – количество объектов в группе.

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

Шаг 8. Распознавание.

Пусть объект экзамена – X.

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

Если выполняется условие: , то мы определяем его в q-ю группу, и соответственно определяем его в образ, которому принадлежит группа.

Применение алгоритма «Голотип N» для распределения абитуриентов

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