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

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

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

 

 

 

 

 

 

Курсовая  работа

 

по курсу

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

 на тему:

 

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

 

 

 

 

 

 

 

 

Выполнила

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

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

Проверили:

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

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

 

 

 

 

 

 

 

 

Дубна, 2011

Оглавление

Введение…………………………………………………………………………………….……3

Постановка задачи………………………………………………………………………….……4

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

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

Заключение………………………………………………………………………………...……13

Приложение 1……………………………………………………………………………...……14

Приложение 2…………………………………………………………………………………...15

Приложение 3………………………………………………………………………...…………16

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Постановка задачи

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

Цель

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

Исходные данные

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

Прикладная информатика			ГМУ			Менеджмент
Матем.	Р. Я.	Общ-е	Матем.	Р. Я.	Общ-е	Матем.	Р. Я.	Общ-е
80	72	70	80	72	70	80	72	70
68	72	70	68	72	70	68	72	70
73	71	69	73	71	69	73	71	69
69	75	70	69	75	70	69	75	70
80	76	75	80	76	75	80	76	75
67	71	74	67	71	74	67	71	74
80	75	70	80	75	70	80	75	70
80	75	65	80	75	65	80	75	65
66	69	73	66	69	73	66	69	73
71	73	69	71	73	69	71	73	69
74	75	73	74	75	73	74	75	73
76	69	70	76	69	70	76	69	70

 

 

 

 

 

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

Алгоритм  «Голотип 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 году поступили на данные специальности первой волной.

Прикладная информатика			ГМУ			Менеджмент
Матем.	Р. Я.	Общ-е	Матем.	Р. Я.	Общ-е	Матем.	Р. Я.	Общ-е
80	72	70	56	83	75	53	69	82
68	72	70	59	81	76	51	70	83
73	71	69	62	78	79	58	72	86
69	75	70	61	82	73	50	69	87
80	76	75	57	79	75	54	75	92
67	71	74	59	85	69	59	74	94
80	75	70	55	80	72	61	71	92
80	75	65	56	79	70	60	70	89
66	69	73	52	79	77	55	69	88
71	73	69	60	81	80	54	72	86
74	75	73	58	79	81	53	70	85
76	69	70	56	80	72	51	71	87

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Из этих данных мы создадим ТОС, в которой имеется часть представителей каждого образа и на каждом объекте материала обучения и материала экзамена измерены косвенные свойства:  — результаты ЕГЭ по математике (баллы),  — результаты ЕГЭ по русскому языку (баллы) и f₃ — результаты ЕГЭ по обществознанию (баллы). Объекты материала обучения  расклассифицированы по образам.

	f1	f2	f3	образ
a1	80	72	70	1
a2	68	72	70	1
a3	73	71	69	1
a4	69	75	70	1
a5	80	76	75	1
a6	67	71	74	1
a7	80	75	70	1
a8	80	75	65	1
a9	66	69	73	1
a10	71	73	69	1
a11	74	75	73	1
a12	76	69	70	1
a13	56	83	75	2
a14	59	81	76	2
a15	62	78	79	2
a16	61	82	73	2
a17	57	79	75	2
a18	59	85	69	2
a19	55	80	72	2
a20	56	79	70	2
a21	52	79	77	2
a22	60	81	80	2
a23	58	79	81	2
a24	56	80	72	2
a25	53	69	82	3
a26	51	70	83	3
a27	58	72	86	3
a28	50	69	87	3
a29	54	75	92	3
a30	59	74	94	3
a31	61	71	92	3
a32	60	70	89	3
a33	55	69	88	3
a34	54	72	86	3
a55	53	70	85	3
a66	51	71	87	3