НАЦИОНАЛЬНАЯ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА
«ИНТЕЛЛЕКТУАЛЬНО-ТВОРЧЕСКИЙ ПОТЕНЦИАЛ РОССИИ»
Конкурс исследовательских работ «ЮНОСТЬ, НАУКА, КУЛЬТУРА»

Секция: Программирование

Информационная система ранжирования и кластеризации информации на базе методов ELECTRE и целочисленного линейного программирования

Выводы.. 13

Библиографический список. 14

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

Введение

Одним из движущих факторов человеческого мышления является выбор. Выбрать – значит определить лучшее для себя, т. е. дать субъективную оценку всем данным вариантам и предпочесть оптимальный. Цель существующей теории принятия решений – выделение объективно лучшего варианта с помощью использования различных математических соотношений. Такие соотношения (способы учета неопределенности - СУН) позволяют обоснованно переходить от субъективных данных, т. е. неопределенностей (обобщенных потерь), к наиболее корректным решениям (необобщенным потерям). Область применения методов принятия решений огромна: от выбора сотового телефона до расчета весовых коэффициентов в различных математических моделях.[2] [3]

На факультете информационных систем и технологий СГАСУ уже в течение нескольких лет работает система комплексного оперативного мониторинга учебной и творческой деятельности студентов. Мониторинг – это специально организованное систематическое наблюдение за состоянием каких-либо объектов. Мониторинг направлен на получение и использование объективных и независимых данных об объекте исследования, факторов на него влияющих и составления прогноза изменения ситуации в будущем. Данная система включает в себя мониторинг учебной, творческой и общественной деятельности студентов. В результате мониторинга каждого вида деятельности формируется комплексный рейтинг студента. [6]

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

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

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

Постановка задачи комплексного мониторинга деятельности студента в вузе[6] [7]

Организация мониторинга учебной деятельности

В организации мониторинга учебной деятельности задействованы:

- старосты групп;

- технический сотрудник деканата;

- преподаватели дисциплин;

- кураторы групп и начальники потоков;

- заместители декана по учебной и воспитательной работе;

- студенческий совет факультета;

- декан.

Функции участников процесса определяются следующим образом:

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

- во-вторых, информирует каждого преподавателя о результатах оценки успеваемости каждого студента рассчитанные информационной системы;

- в-третьих, вводят коррективы в рассчитывающую информационную систему, которые сообщает преподаватель;

- в-четвертых, информирует студентов группы об обсуждении итогов мониторинга на студенческом совете и в деканате;

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

Организация мониторинга творческой деятельности

Все студенты факультета в рамках курса «Технология и методология научных исследований» выполняют исследовательские работы. Оценка производится по 9-ти функциям научной квалификации. Оценкой работ занимается другая группа исследователей, это не входит в рамки моей задачи. Мною берутся только данные. Т. к. исследовательская работа выполняется раз в семестр, то частота изменения данных – один раз в семестр (См. рисунок 2).

Организация мониторинга личностной активности

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

Что такое метод ELECTRE и история его происхождения[1]

В конце 60-х годов группа французских ученых во главе с проф. Б. Руа предложила подход к попарному сравнению мно­гокритериальных альтернатив, не основанный на теории полез­ности. В отличие от MAUT оценка каждой альтернативы явля­ется не абсолютной, а относительной (по сравнению с другой альтернативой). Так возник метод ELECTEE (ELimination Et Choix Traduisant la Eealite — исключение и выбор, отражающие реальность). В настоящее время разработан ряд методов семей­ства ELECTRE.

Методы ELECTEE направлены на решение задач с уже за­данными многокритериальными альтернативами. В отличие от метода АНР в мето­дах ELECTRE не определяется количественно, показатель каче­ства каждой из альтернатив, а устанавливается лишь условие превосходства одной альтернативы над другой.

Перейдем к краткой характеристике метода ELECTRE.

Постановка задачи обычно имеет следующий вид:

Дано: N критериев со шкалами оценок (обычно количест­венные), веса критериев (обычно целые числа), альтернативы с оценками по критериям.

Требуется: выделить группу лучших альтернатив.

Основные этапы методов ELECTRE

1.  На основании заданных оценок двух альтернатив подсчитываются значения двух индексов: согласия и несогласия. Эти индексы определяют согласие и несогласие с гипотезой, что альтернатива А превосходит альтернативу В.

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

3.  Из множества альтернатив удаляются доминируемые. Оставшиеся образуют первое ядро. Альтернативы, входящие в ядро, могут быть либо эквивалентными либо несравнимыми.

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

5.  В последнее ядро входят наилучшие альтернативы. По­следовательность ядер определяет упорядоченность альтернатив по качеству.

Индексы согласия и несогласия

В различных методах семейства ELECTRE индексы согла­сия и несогласия строятся по-разному. Основные идеи построе­ния этих индексов далее будут показаны на примере метода ELECTRE 1.

Каждому из N критериев ставится в соответствие целое число р, характеризующее важность критерия. Б. Руа предло­жил рассматривать р как «число голосов» членов жюри, голо­сующих за важность данного критерия.

Выдвигается гипотеза о превосходстве альтернативы А над альтернативой В. Множество I, состоящее из N критериев, раз­бивается на три подмножества:

I — подмножество критериев, по которым А предпочти­тельнее В;

I" — подмножество критериев, по которым А равноценно В;

Г" - подмножество критериев, по которым В предпочти­тельнее А.

Далее формулируется индекс согласия с гипотезой о пре­восходстве А над В. (В других методах семейства ELECTRE ис­пользуются индексы сильного и слабого превосходства.)

Индекс согласия подсчитывается на основе весов критери­ев. Так, в методе ELECTRE1 этот индекс определяется как от­ношение суммы весов критериев подмножеств 1+ и I - к общей сумме весов:

Индекс несогласия dAB с гипотезой о превосходстве А над В определяется на основе самого «противоречивого» критерия — критерия, по которому В в наибольшей степени превосходит А.

Чтобы учесть возможную разницу длин шкал критериев, разность оценок В и А относят к длине наибольшей шкалы:

dAB= max(Ai-Bi/Li)

где Аi, Вi— оценки альтернатив А и В по i - му критерию; Li — длина шкалы i-ro критерия.

Бинарные отношения. Выделение ядер

В методе ELECTRE 1 бинарное отношение превосходства задается уровнями согласия и несогласия. Если сАВ > ci и dAB <di, где ci, di — заданные уровни согласия и несогласия, то аль­тернатива А объявляется лучшей по сравнению с альтернативой В. Если же при этих уровнях сравнить альтернативы не уда­лось, то они объявляются несравнимыми.

С методологической точки зрения введение понятия несрав­нимости было важным этапом развития теории принятия реше­ний. Если оценки альтернатив в значительной степени противо­речивы (по одним критериям одна намного лучше другой, а по другим - наоборот), то такие противоречия никак не компенси­руются и такие альтернативы сравнивать нельзя. Понятие не­сравнимости исключительно важно и с практической точки зре­ния. Оно позволяет выявить альтернативы с «контрастными» оценками как заслуживающие специального изучения.

Похожие идеи используются и в других методах семейства ELECTRE.

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

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

Общая характеристика подхода

Важным достоинством методов ELECTRE является поэтап­ность выявления предпочтений ЛПР в процессе назначения уровней согласия и несогласия и изучения ядер. Детальный анализ позволяет ЛПР сформировать свои предпочтения, опре­делить компромиссы между критериями. Использование отно­шения несравнимости позволяет выделить пары альтернатив с противоречивыми оценками, остановиться на ядре, выделение которого достаточно обоснованно с точки зрения имеющейся информации. Трудности при применении методов ELECTRE связаны с назначением ЛПР весов. В ряде случаев при выделе­нии ядер могут возникать циклы.

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

Сравнительный анализ результатов использования метода ELECTRE и кластеризации данных.

В моей предыдущей работе «Мониторинг учебного процесса и кластерный анализ студенческого контингента в условиях информационно-коммуникационной среды вуза» я рассматривал кластеризацию с использованием целочисленного линейного программирования. В результате исследования на базе тех же исходных данных выделилось 5 кластеров (См. рисунок 11). В данном исследовании тоже выделилось 5 ядер. Получилось частичное соответствие полученных групп. Это зависит от разности подхода методов: методы ELECTRE распределяют на основе полного или частичного превосходства по всем критериям, тогда как кластеризация выделяет относительно близкие по показателям альтернативы.

Библиографический список

1.  Теория и методы принятия решений, а также Хроника событий в Волшебных странах. Учебник. М.: Логос, 2002. – 392 с.

2.  Управляемое развитие научных способностей молодежи. М. Академия наук о Земле. 2001. – 109 с.

3.  . Теория и методы принятия решений. М., "Логос", 2000 г.

4.  С#: учебный курс – СПб.: Питер; К.: Издательская группа ВНV, 2003. – 512 с.

5.  Методы оптимизации и оптимального управления: Учебное пособие/ Самарский государственный архитектурно-строительный университет. - Самара, 2004.

6.  , Мониторинг качества учебной деятельности студентов с использованием информационной системы. – М.: Исследовательский центр проблем качества подготовки специалистов, 2006. – с. 50-54

7.  , Разработка системы комплексного мониторинга формирования IT-специалиста в вузе. Материалы международной научно-технической конференции. – Самара: СГАСУ, 2006. – с. 279-286.

8.  http://www. /rules/intro. html

Приложение

Рисунок 1 – Формирование рейтинга учебной деятельности

Рисунок 2 – Формирование рейтинга творческой активности

Рисунок 3 – Блох-схема программы

Таблица 1 - Характеристика программной среды

Среда программирования	Microsoft Visual Studio 2005
Язык программирования	C#
Исходные данные	База данных Access

Выписываем доминируемую альтернативу

Рисунок 4 – Пример технологических карт

Рисунок 5 – Ввод первичной информации

Таблица 2 – Исходные данные

Анд	84.86707	13.440985	0
Ару	94.88754	22.99024	30
Вас	74.84663	0	0
Гал	99.3865	13.440985	47
Гор	96.11452	13.440985	53.19149
Гре	99.591	54.611989	41.13475
Дав	76.27812	0	0
Дро	93.04703	0	40
Ере	81.18609	13.440985	0
Зин	63.19018	0	0
Иль	98.56852	22.99024	60
Кал	60.1227	0	0
КисД	89.77505	0	100
КисМ	72.80164	94.086896	0
Мал	97.13701	30	0
Мар	93.45603	0	0
Мих	89.57056	0	0
Пан	90.38855	26.88197	0
Рах	97.13701	13.440985	0
Сар	81.79958	0	22
Сок	78.52761	100	0
Тим	94.06953	0	40
Тол	96.52353	25	0
Чир	87.73006	0	15
Шиш	100	25	0
Ятм	91.41104	0	37
Яшк	97.95501	0	34.04255

Рисунок 6 – Полученная матрица индексов согласия

Рисунок 7 – Полученная матрица индексов несогласия

Рисунок 8 – Формирование первого ядра

Рисунок 9 – Формирование всех ядер

Таблица 3 – Полученные ядра

Ядра	1-е ядро	2-е ядро	3-е ядро	4-е ядро	5-е ядро
Индекс согласия	1	0.8	0.4	0.2	0
Индекс не огласия	0	0.2	0.4	0.8	1
	Анд	КисД	Шиш	Сок	Гре
	Ару	Гал
	Вас	Иль
	Гор
	Дав
	Дро
	Ере
	Зин
	Кал
	КисМ
	Мал
	Мар
	Мих
	Пан
	Рах
	Сар
	Тим
	Тол
	Чир
	Ятм
	Яшк

Рисунок 10 – График распределения по индексам согласия и несогласия

Рисунок 11 – Полученные кластеры.

Идеальные	Середняки	Умники	Неуспевающие	Равнодушные
Ару	Анд	Гал	Анд	КисМ
Гре	Ере	Гор	Вас	Сок
КисД	Мал	Дро	Дав
Сар	Пан	Иль	Ере
	Рах	Тим	Зин
	Тол	Ятм	Кал
	Шиш	Яшк	Мар
			Мих
			Чир