EVALUATION OF PROXIMITY OF GRAPHIC OBJECTS ON AN EXAMPLE OF USING ELECTRICAL SCHEMES OF THE INFORMATION CRITERIA.pdf Полноценное использование в сфере образования возможностей современных информационных технологий может быть достигнуто разработкой и внедрением автоматизированных и автоматических систем проверки знаний во всем их многообразии. Внедрение информационных технологий в сферу проверки знаний идёт широким фронтом. Примерами оценки качества знаний студентов с использованием компьютерных комплексов могут служит: единый государственный экзамен (ЕГЭ) (часть А и B) [2]; автоматизированная система тестирования знаний студентов, разрабатываемая в Ивановском государственном энергетическом университете [1]; разрабатываемая в ЛГТУ автоматизированная система оценки знаний учащихся [6] по развёрнутому письменному ответу экзаменуемого. Оценка знаний осуществляется на основе сопоставления содержания ответа экзаменуемого на поставленный вопрос, с содержанием эталонного ответа – материала по данному вопросу, который имеется на определённых страницах учебника (или в электронном конспекте лекций). При автоматизированном сопоставлении ответа с эталоном решается задача формального сравнения содержимого двух информационных объектов, представленных на естественном языке [6]. Материал, изучаемый в технических учебных заведениях, включает информацию, представленную на формальных языках с помощью специализированных формальных алфавитов. Язык электротехнических схем является одним из них. В нем роль алфавита играет множество элементов, ветвей и узлов, из которых составляются все схемы. Назовём его для дальнейшего алфавитом схем. Представляется актуальной задача разработки методов автоматической оценки близости двух информационных объектов, представленных с использованием алфавита схем. Во многих технических дисциплинах изучаются под разными углами зрения (проектирование, функционирование, эксплуатация и пр.) различного рода схемы, которые для демонстрации знаний приходится изображать экзаменуемому и проверять экзаменатору. Настоящая работа опирается на уже имеющиеся разработки в сфере автоматизированного представления схем. Целью является разработка инструмента (системы) автоматического сопоставления ответа с эталоном и формирования гибкой оценки ответа, в зависимости от количества и важности отклонений в схеме-ответе от схемы-эталона. Предназначение системы – помочь экзаменатору реализацией следующих функций: принять ответ-схему, введённую обучаемым, сравнить ответ с хранящимся в системе эталоном, выявить отличия (ошибки) и автоматически сформировать оценку по выбранной шкале. Система наделяется функциями адаптации (настройки) на предметную область и специфику дисциплин. В существующих системах отсутствует возможность оценки близости различного рода схем, и они не позволяют определить, в какой в мере вариант схемы в ответе студента совпадает с эталонным вариантом, предложенным ему для изучения. В CAD-системах проверяется правильность сборки электрической схемы на точное совпадение с заданной [5] и выдачей четкой оценки: правильно или неправильно. В настоящей работе цель состоит в синтезе инструмента для автоматизированного формирования количественной оценки, характеризующей уровень несовпадения схем (правильности ответа). 1. Общая характеристика системы Для решения этой задачи реализована автоматическая система оценки близости схем, структурная схема функционирования которой показана на рис. 1. Рис. 1. Структурная схема функционирования системы На рис. 1 заштрихованные элементы обозначают используемые сторонние разработки и приложения, без штриховки – оригинальные разработки. Введение схем осуществляется с помощью программы DipTrace непосредственно путём перетаскивания в наборное поле элементов и расстановкой связей между ними. Используемое приложение для ввода схем: DipTrace 2.2 Freeware. Все модули и библиотеки включены. Бесплатная версия, ограничение – 300 выводов, 2 слоя, что вполне достаточно в учебных целях [10]. Для ввода в систему используется файл netlist. Он содержит информацию о связях и элементах в схеме. Элементы маркируются выводами, которыми они подключены в ветви или узле. Это может быть как буквенный маркер, так и цифровой. Для полярных элементов в свойствах указывается положительный или отрицательный вывод. Файл netlist содержит информацию обо всех элементах и их параметрах, а также список соединений. Эталонные варианты схем вводятся в компьютер (блок 1 и 2) с помощью программы DipTrace [10] и сохраняются в виде файлов схем и файлов соединений в формате приложения PADs. Все файлы эталонных соединений сохраняются в папке программы с названием: схема_«номер схемы» (например, схема_15) (блок 3). Студенты (блок 4) во время проверки вводят свой вариант схемы в программе DipTrace (блок 5) и сохраняют в папке ответов с названием, указанным преподавателем, с добавлением своей фамилии (например, схема_15_Антонов) (блок 6). Файлы автоматически заносятся в базу данных приложения (блок 3 и 6). Проверяющий запускает приложение для оценки сходства схем (блок 7) и программа автоматически (блок 8) сопоставляет введённые студентами схемы-ответы с эталонным вариантом, выявляет различия и оценивает уровень близости ответа эталону. Информация об отличиях и рекомендуемая оценка выдаются преподавателю (блок 9). Преподаватель может выполнить проверку вручную (блок 10). Для этого из выпадающего списка выбирается схема эталона и из аналогичного списка – схема ответа. 2. Представление схем В ГОСТе [4] принципиальная схема определяется как «схема, определяющая полный состав элементов и связей между ними и, как правило, дающая детальное представление о принципах работы изделия». В соответствии с определением компонентами схемы являются элементы, ветви и узлы. Элементы содержат изменяемые параметры, как для примера показано на рис. 2. Рис. 2. Сопротивление резистора На рис. 3 показаны: элементарные составляющие схем (ветви и узлы). Ветвью называется участок электрической цепи, обтекаемый одним и тем же током. Ветвь образуется последовательно соединёнными элементами цепи. Узел – место соединения трёх и более ветвей. В схемах возможны эквивалентные преобразования – несколько элементов электрической цепи заменяются одним эквивалентным элементом. Замена осуществляется так, что величина токов и напряжений в остальной части схемы не изменяется. Значения параметров эквивалентного элемента определяются исходя из свойств каждого соединения [9]. Рис. 3. Ветви и узлы 3. Методология сравнения схем Для оценки близости информационных объектов, в данном случае схем, они представляются формально в виде однотипной вероятностной модели сравниваемых информационных объектов (ИО) [7]. Вероятностная модель в теории вероятностей [3] имеет вид , (1) где W={w1,w2,…, wm} – множество элементарных исходов; À=(А1,А2,…,Аn) – система (алгебра) случайных событий, составляемых из элементарных исходов; P(A) – вероятности случайных событий. В данном контексте множество элементарных исходов представляют все входящие в систему компоненты. Случайными событиями являются виды компонентов, т.е. элементы, ветви и узлы. Вероятности случайных событий P(A) вычисляются по вероятностям отдельных компонентов , (2) р(wi) – вероятности компонентов, которые могут быть приняты равными 1/m, где m – количество компонентов в схеме. Количество информации в схеме может быть оценено энтропией , (3) где А1 – множество элементов, А2 – множество ветвей, А3 – множество узлов. Величина р(wi) характеризует «вес» или «значимость» каждого отдельного компонента wi. Поэтому вероятности случайных событий P(A), определяемые (2), характеризуют значимость элементов схемы, составляющих систему случайных событий отдельных компонентов алгебры À. При необходимости значимость различных компонентов схемы может дополнительно изменяться введением в (3) весовых коэффициентов для случайных событий. Этим может обеспечиваться настройка системы на предметную область или актуализацию проверки отдельных компонентов, для которых могут вводиться повышенные весовые коэффициенты. Для оценки близости схемы-ответа и схемы-эталона вычисляются энтропии каждой из них. Мерой близости может быть количество взаимной информации [7] в схемах, которое вычисляется в виде , (4) где НЭ – энтропия схемы-эталона; НО – энтропия схемы-ответа, НЭО – совместная энтропия эталона и ответа. Энтропии эталона и ответа вычисляются по (3), а совместная энтропия определяется в виде , (5) где совместные события определяются в виде , (6а) , (6б) , (6в) где верхним индексом отмечена схема, в которую входит рассматриваемый компонент, а нижним – схема, в которую он не входит. Событие (6а) составляется из компонентов, входящих в событие Aj схем эталона и ответа; (6б) объединяет компоненты, входящие в событие Aj эталона, но отсутствующие в ответе; (6в) объединяет компоненты, не входящие в событие Aj в эталоне, но имеющиеся в ответе. Других вариантов для компонентов, присутствующих в двух сопоставляемых схемах, нет. Совместная информация (5) позволяет получить количественную оценку несовпадения ответа и эталона. Эта оценка может быть адаптирована к используемой системе балльных оценок. Наряду с количеством взаимной информации для оценки близости сопоставляемых схем может быть использовано «расстояние» между информационными объектами [8], определяемое в виде . (7) Можно видеть, что числитель (7) представляет сумму двух первых слагаемых правой части (5), отражающих суммарное количество информации в ответе и эталоне, а знаменатель (7) есть последнее слагаемое (5), которое отражает количество информации, входящей одновременно в ответ и эталон. Если ответ и эталон совпадают, то числитель и знаменатель в (7) совпадают, по мере уменьшения общей информации знаменатель будет стремиться к нулю, а «расстояние» – к бесконечности. 4. Иллюстративные примеры Первый пример иллюстрирует формирование вероятностных характеристик компонентов вероятностной модели схемы. На рис. 4 изображена схема, а в табл. 1 – её «характеристика». Принято, что все элементы равновероятны: wi=1/N=1/23. Для сокращения таблицы в строке «перечень» приведены только примеры обозначения компонентов. В примере: 12/23 – вероятность элементов, 7/23 – вероятность ветвей, 4/23 – вероятность узлов. Рис. 4. Схема-эталон Таблица 1 Вероятностная модель объекта-схемы, показанной на рис. 4 Характеристика Случайные события А1 – элементы А2 – ветви А3 – узлы Перечень R4, L1, …, L1C1,L2C2,…, T1BC1R4,…,… Количество 12 7 4 Вероятность 12/23 7/23 4/23 По формуле (3) определяется энтропия (количество информации) схемы, приведённой на рис. 4: 1,0057. В соответствии с описанным выше алгоритмом, показанным на рис. 1, в систему с помощью программы DipTrace заносятся эталонные схемы, для каждой из которых определяется её представление в виде детальной табл. 1. Информация сохраняется в базе данных программы. Аналогичным способом сохраняются ответы, введённые студентами. Информация о схеме-ответе представляется в виде подобной таблицы. На основании информации, представленной в таблицах, производятся их сопоставление и количественная оценка близости. Энтропии определяются, как показано на примере, по таблицам эталона и ответа. Для иллюстрации принципа определения количественной оценки сравнением схем используется пример 2. Схема, используемая в нем, показана на рис. 5, отражающем вид окна приложения DipTrace с введённой схемой. Рис. 5. Изображение окна приложения DipTrace с введённой схемой После того как учащиеся закончили ввод схем и сохранили их, может быть запущена программа (блок 7) проверки в автоматическом режиме (блок 8). Система выявляет все отличия схемы-ответа по отношению к схеме-эталону, формирует итоговую таблицу для группы обучаемых, отражающую допущенные ошибки и содержащую рекомендуемые оценки. Для иллюстрации формирования оценки, в зависимости от ошибок (степени отклонения схемы-ответа от схемы-эталона), была осуществлена имитация ответов с определёнными отклонениями в них от эталона. В табл. 2 приведены различные варианты ответов с отклонениями от эталона. Одновременно табл. 2 отражает форму информации об ответе, выводимую проверяющему. Она содержит все ошибки с указанием их места в схеме. В представленном примере ответы формировались: 1-й и 2-й заменой элементов на другие без изменения числа элементов и связей; с 3-го по 8-й последовательным удалением произвольных элементов; 9-я схема скопирована из первой; 10-й ответ – схема, абсолютно отличающаяся от эталона. Все изменения представлены в табл. 2. В шапке перечислены все случайные события: элементы, ветви и узлы. В строке «Эталон» представлены элементы, узлы и ветви эталонной схемы. В последующих строках, отражающих отличия схем-ответов от эталона, показаны те элементы, которых не хватает в ответах. Таблица 2 Отличия ответов для иллюстрации формирования оценки схемы-ответа Название R Q C D L BT LS MC Ветви Узлы Эталон R1; R2; R3; R4; R5; R6; R7; R8; R9; R10; R11; R12; R13; R14; R15; Q1; Q2; Q3; Q4; Q5; Q6; Q7; C1; C2; C3; C4; C5; C6; C7; C8; C9; D1; D2; D3; D4; D5; D6; L1; BT1; LS1; MC1; C4.2 R5.1; D1.1 D2.2; D3.2 D4.1; R14.2 C7.1; C1.2 MC1.B; D5.2 D6.1; D6.2 C6.1; R1; Q1; C1; Q3; C3; R7; R2; Q2; Q6; R10; C8; BT1; R3; C2; R4; R6; C5; R12; R13; R15; Q4; Q5; R8;R9; Q7; R11; C9; LS1; R1.2 Q1.B C1.1; Q3.C C3.2 R7.1;Q1.C Q3.B C3.1 R2.1; Q2.C Q3.E Q6.E R2.2; R10.2 C8.1 BT1.POS; Q1.E Q2.E R3.2; C2.1 R3.1 R4.2; Q2.B R5.2 R6.1;R6.2 C5.1 D4.2 D5.1 R12.1 R13.2 R15.1 C7.2; Q4.B R7.2 D1.2 D3.1; Q5.B D2.1 R8.1; C5.2 R8.2 R9.2; Q7.E R4.1 R9.1 R11.1 C9.1 BT1.NEG; Q5.C Q7.B C6.2 R11.2; Q4.C Q6.B R10.1; Q5.E Q7.C R13.1; Q4.E Q6.C R12.2;R15.2 L1.2 LS1.A; R1.1 C2.2 C4.1 R14.1 C8.2 C9.2 LS1.B MC1.A; Ответ_1 L1; R15 LS1; R15.2 L1.2 LS1.A Ответ_2 L1; D1.1 D2.2; R15 LS1 Q4.B R7.2 D1.2 D3.1 R15.2 L1.2 LS1.A Ответ_3 D1; L1; D1.1 D2.2; R15 LS1 Q4.B R7.2 D1.2 D3.1 R15.2 L1.2 LS1.A Ответ_4 R5; D1; L1; C4.2 R5.1; D1.1 D2.2; R15 LS1; Q2.B R5.2 R6.1; Q4.B R7.2 D1.2 D3.1; R15.2 L1.2 LS1.A Ответ_5 R5; Q6; D1; L1; C4.2 R5.1; D1.1 D2.2; Q6 R10 R12 R15 Q4 LS1; Q2.C Q3.E Q6.E R2.2 R10.2 C8.1 BT1.POS; Q2.B R5.2 R6.1; Q4.B R7.2 D1.2 D3.1; Q4.C Q6.B R10.1; Q4.E Q6.C R12.2 R15.2 L1.2 LS1.A; Ответ_6 R2; R5 Q6; D1; L1; C4.2 R5.1 D1.1 D2.2 R2 Q6 R10 R12 R15 Q4 LS1 Q1.C Q3.B C3.1 R2.1; Q2.C Q3.E Q6.E R2.2 R10.2 C8.1 BT1.POS; Q2.B R5.2 R6.1; Q4.B R7.2 D1.2 D3.1; Q4.C Q6.B R10.1; Q4.E Q6.C R12.2; R15.2 L1.2 LS1.A; Ответ_7 R2; R5 Q6; D1; D3; D6; L1; C4.2 R5.1; D1.1 D2.2; D3.2 D4.1; D5.2 D6.1; D6.2 C6.1; R2 Q6 R10 R12 R15 Q4 LS1; Q1.C Q3.B C3.1 R2.1; Q2.C Q3.E Q6.E R2.2 R10.2 C8.1 BT1.POS; Q2.B R5.2 R6.1; Q4.B R7.2 D1.2 D3.1; Q4.C Q6.B R10.1; Q4.E Q6.C R12.2; R15.2 L1.2 LS1.A ; Ответ_8 R2; R5 Q6; C3; D1; D3; D6; L1; C4.2 R5.1; D1.1 D2.2; D3.2 D4.1; C1.2 MC1.B D5.2 D6.1 D6.2 C6.1; Q3 C3 R7 R2 Q6 R10 R12 R15 Q4 LS1; Q3.C C3.2 R7.1; Q1.C Q3.B C3.1 R2.1; Q2.C Q3.E Q6.E R2.2 R10.2 C8.1 BT1.POS; Q2.B R5.2 R6.1; Q4.B R7.2 D1.2 D3.1; Q4.C Q6.B R10.1; Q4.E Q6.C R12.2; R15.2 L1.2 LS1.A; Ответ_9 Ответ 10 R4;R5;R6;R7;R8;R9; R10; R11; R12; R13; R14; R15; Q2; Q3; Q4; Q5; Q6; Q7; C4; C5; C6; C7; C8; C9; D5; D6; L1; BT1; LS1; MC1; C4.2 R5.1; D1.1 D2.2; D3.2 D4.1; R14.2 C7.1; C1.2 MC1.B; D5.2 D6.1 D6.2 C6.1; Q3 R7 R2 Q2 Q6 R10 C8 BT1 R3 R4 R6 C5 R12 R13 R15 Q4 Q5; R8 R9 Q7 R11 C9 LS1; R1.2 Q1.B C1.1; Q3.C C3.2 R7.1; Q1.C Q3.B C3.1 R2.1; Q2.C Q3.E Q6.E R2.2 R10.2 C8.1 BT1.POS; Q1.E Q2.E R3.2 C2.1 R3.1 R4.2; Q2.B R5.2 R6.1 R6.2 C5.1 D4.2 D5.1 R12.1 R13.2 R15.1 C7.2 Q4.B R7.2 D1.2 D3.1; Q5.B D2.1 R8.1; C5.2 R8.2 R9.2; Q7.E R4.1 R9.1 R11.1 C9.1 BT1.NEG; Q5.C Q7.B C6.2 R11.2; Q4.C Q6.B R10.1; Q5.E Q7.C R13.1 Q4.E Q6.C R12.2; R15.2 L1.2 LS1.A R1.1 C2.2 C4.1 R14.1 C8.2 C9.2 LS1.B MC1.A В табл. 2 показано, что ответ 1 отличается от эталона отсутствуют элемент «L1», ветви R15 LS1 и узлы R15.2 L1.2 LS1.A. Аналогично для других схем-ответов. Для всех вариантов схем-ответов, представленных в табл. 2, система, используя меры (4), (7), сформировала оценки. Формирование оценок, их зависимость от отклонений схем-ответов от эталона можно проследить по табл. 3, в которой приведены все составляющие для вычисления взаимной информации схем-ответов со схемой-эталоном и «расстояния» между ними. Таблица 3 Результаты расчёта отклонения ответов от эталона Название схемы студента Число элементов, n Число узлов, Nuz Число ветвей, Nvet Элементарная вероятность Px Энтропия образа, Ho Принадлежит только образу, Hэо Совместная энтропия, Hэо Принадлежит только эталону, Hоэ Энтропия эталона, He Расстояние, S Взаимная информация, I Ответ_1 40 17 33 0,011 1,0430 0,0487 1,011145 0,208249 1,0467 0,2541 0,821 Ответ_2 40 17 33 0,011 1,0431 0,1313 1,010582 0,288465 1,0467 0,4153 0,659 Ответ_3 39 17 33 0,012 1,0456 0,1314 1,012127 0,322296 1,0467 0,4481 0,626 Ответ_4 38 17 33 0,0123 1,0480 0,1933 1,011246 0,416244 1,0467 0,6028 0,474 Ответ_5 37 15 30 0,0124 1,0376 0,2460 0,996613 0,597202 1,0467 0,8461 0,244 Ответ_6 36 15 29 0,0126 1,0410 0,2706 0,987263 0,654653 1,0467 0,9372 0,175 Ответ_7 34 15 29 0,0128 1,0468 0,3121 0,988236 0,707244 1,0467 1,0315 0,086 Ответ_8 33 13 27 0,0129 1,0340 0,3217 0,970806 0,767569 1,0467 1,1221 0,020 Ответ_9 41 18 34 0,0107 1,0467 0 1,0467 0 1,0467 0 1,046 Ответ_10 13 5 9 0,0373 1,0304 0,5184 0,29248 1,029436 1,0467 5,2923 0,236 Ответы, как видно из табл. 2, сформированы с нарастанием отклонений (ошибок) в них пропорционально номеру. В табл. 3 можно видеть, что количество взаимной информации уменьшается, а расстояние увеличивается по мере увеличения отклонений ответов от эталона. По определению эти меры являются монотонными функциями количества информации, и, следовательно, взаимная информация или информационное расстояние между объектами адекватны поставленной задаче и могут быть использованы для оценки близости ответа эталону. На рис. 6 графически показано увеличение расстояния между ответом и эталоном с нарастанием степени отличия ответа от эталона. Схема-ответ 9 совпадает с эталоном, и значение информационного расстояния между ними равно нулю. Другой вариант представляет схема 10, в которой имеется лишь несколько элементов, совпадающих с эталоном по параметрам. Для неё получено информационное расстояние 5,2923, которое выпадает из ряда представленных оценок. Система оценивания может настраиваться на произвольную шкалу балльных оценок и адаптироваться к частным особенностям использованием стандартных методов параметрической идентификации моделей. Пример применения идентификации к моделям в образовательной сфере показан в работе [8]. Рис. 6. График роста информационного расстояния при последовательном увеличении отклонений схем-ответов от эталона Возвращаясь к описанию системы, следует добавить, что результаты проверки схем-ответов, представленных группой студентов, форматируются в виде таблицы, вариант которой применительно к имитированным ответам (см. табл. 2, 3) показан на рис. 7 в виде окна программы с выводом таблицы результатов. Рис. 7. Окно программы с выводом результирующей таблицы Проверяющий может запустить систему в ручном режиме (блок 7), для этого ему потребуется выбрать соответствующую функцию при старте программы и вставлять каждую схему через меню добавления файлов. В этом случае ему доступен просмотр каждой отдельной таблицы схемы, где разным цветом указываются различающиеся элементы. Заключение Разработана методика оценки близости электрических схем на основании сопоставления их графических изображений. Набор стандартных элементов (алфавит) схем играет роль алгебры, отражающей структуру схемы в виде структуры вероятностного объекта. Количество информации в схемах оценивается энтропией представляющих их случайных объектов, а мера близости схем определяется количеством взаимной (совместной) информации в сопоставляемых схемах. Количество информации, входящей в один объект и не входящей в другой, определяет информационное расстояние между ними. Показан пример реализации методики. Методика ориентирована на использование в автоматических обучающих системах для синтеза модулей автоматической проверки знаний. Разработанные меры близости схемы-ответа схеме-эталону (количество взаимной информации и информационное расстояние) могут быть соотнесены с системой стандартных балльных оценок.

Скачать электронную версию публикации