Сравнительная характеристика графов и деревьев для разработки адаптивной гиперсреды

Manuel Freire and Pilar Rodriguez

Перевод с английского: Смирнов В.А.


Источник: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.7831.pdf


Введение


      Системы адаптивной гиперсреды (AГ) основаны на идее приспособить содержание сайта пользователям,вместо того, чтобы использовать один и тот же подход для всех. Они поддерживают своего рода информацию о пользователе, цели пользователя и предыдущих действиях (пользовательская модель [4]), и пытаются представить контент, который будет относиться к текущей задаче для определенного пользователя, выполняя отличающиеся типы адаптации на (структурированном) репозитории контента; отношение среди элементов в репозитории контента определяют структуру, которую часто называют моделью контента, или когда репозитарий обращается к определенному домену, модели предметной области. В образовательном контексте,репозиторий контента обычно состоит из повторяющихся отдельных курсов (хотя это различиеможет быть нечетким, если возможность многократного использования учитывается в уравнение, и  в некоторых частях   контента курсов ). Поэтому структура адаптивного курса гиперсреды  неизменно более сложна по сравнению со статическим: адаптация выполняется определенными процедурами, которые связывают данную пользовательскую модель с моделью предметной области, и модель предметной области должна включать своего рода дополнительную информацию, которая ведет процесс адаптации в этой задаче. Эта информация обычно добавляется как метаданные, маркируя модули контента или подблоки со специальными тегами и устанавливая отношения между ними. Механизм адаптации позже использует эту информацию и пользовательскую модель, чтобы представить курс безшовным, адаптированным в соответствии с воспринятыми целями этого пользователя и потребностями. Некоторые  отношения среди модулей курса обычно имеют больший приоритет, чем другие. Например, часть  отношения обычно определяет высокоуровневое расположение курса, расположение, которое может быть изменено перед представлением механизма адаптации (возможно "часть того, если" было бы лучшее описание), и затем далее усовершенствованное на более низких уровнях местоположение, чтобы обеспечить более мелкомодульные типы адаптации. Мы представляем эксперимент, сравнивающий различные структурные представления в двух авторских разработках, инструменты разрабатываются для адаптивной системы курса гиперсреды WOTAN. WOTAN новая версия TANGOW [7,6], образовательная система AГ разрабатывается в Мадридском университет исследовательской группой автора. В разделе №2 описываются основы механизмов адаптации  используемых в WOTAN. Редакторы описываются в разделе №3, с акцентом на интерфейс пользователя к структуре, а не фактическим деталям, связанными с обновлением курса,  синтаксисом представления пользовательской модели и т.д. Далее  описываются редакторы основанные на дереве п. №3.1 и  на графе. В разделе №4,описывается экспериментальная установка разработанная, чтобы сравнить оба подхода в различных задачах авторской разработки, и обсудить результаты собранные в эксперименте с небольшим количеством пользователей. Наконец, в разделе №5, содержатся заканчивающиеся комментарии и строки будущей работы, и настаивают на общности проблемы представления, которую будет характерна для любой адаптивной  гиперсреды, которая выполняет глобальную адаптацию на закрытом, сильно связанном репозитории контента.


WOTAN, новая версия TANGOW


Адаптивная система TANGOW была обновлена в прошлом году. Новая версия, WOTAN,
улучшила  функции администрирования, представления и инструментов разработки,
XML-файлы стали использоваться вместо таблиц базы данных для данных курса, пользовательской модели, и конфигурации системы. Также была представлена новая система заданий. Далее в этом разделе рассматривается архитектура системы, модели курса, и пользовательская модель, как основа для представления инструментов разработки. Реконструкция TANGOW была частично взята у другой адаптивной гиперсреды
, в  особенности АГА системы [9,15] и адаптивной гиперсреды эталонной модели такой как [3], хотя в TANGOW нет никакого надлежащего разделения между “обучающей моделью” и “моделью контента”.
2.1. Архитектура
WOTAN реализуется как ряд модулей (сервлеты внутри Java веб-приложений), которые
делят информацию сеанса. Модуль упражнений обеспечивает сетевой интерфейс, который позволяет автору  создавать и тестировать различные типы упражнений, которые могут позже быть включены в курсы; администраторский модуль реализует управление доступом и обеспечивает управление курсом и пользователем. Авторы могут загрузить и скачать курсы из системы через ее интерфейс. Наконец, модуль презентаций отвечает за представление курсов пользователям, выполняя адаптацию при необходимости. В настоящий момент, это все разрабатывается, для близкого подражания поведению предыдущему TANGOW интерфейсу, но модуль адаптации легко заменим для новых требований адаптации. Авторская разработка курса происходит со стороны клиента, и абсолютно не требует интернета; это позволяет обеспечить большую интерактивность  инструментов разработки, и более масштабные представления структуры курса.
2.2. Пользовательская модель, модель курса и адаптация
Рис. 1 иллюстрирует содержание сеанса пользователя. Сеансы включают пользовательскую модель с глобальным понятием  данных студента (такими как предпочтенный язык, стиль обучения [13], и т.д.), специфичный  курс "оверлей" для каждого курса пользователя регистрируется отдельно. Вся информация о модели кодируется в атрибутозависимых парах, где атрибуты накладывают метку расположения в модели курса, когда атрибут имеет уместность. Если пользователь в настоящий момент проходит курс, то модель курса (как аннотирующаяся соответствующим оверлеем) также будет сохранена в сеансе; когда сеанс будет закончен, он будет сериализирован назад в пользовательский оверлей курса модели для данного курса.
1t
Рисунок 1. Конструкция аннотируемой модели курса в WOTAN, новой версии TANGOW.

Данные адаптации содержатся в описании курса, XML-документе, который описывает курс с точки зрения задач, правил, фрагментов, версий, и функций адаптации. Задачами являются блоки контента, которые могут содержать идругие блоки и фрагменты контента. Курс всегда определяет основную задачу, которая действует как точка входа к целому курс. Включение не является монопольным: несколько задач могут ссылаться, либо прямо либо косвенно, к тем же самым подзадачам или фрагментам; но никакая задача не может включать предка как подзадачу. Поэтому,  курсы TANGOW рассматривают ацикличные графы (то есть графы, где никакие циклы не могут быть созданы следующими гранями). Разложением задачи в подзадачах управляют правила. У каждого правила есть активационное условие (условие на пользовательской модели, которое должно быть использовано для правила), список подзадач, и критерии для того, чтобы упорядочить подзадачи (в рекомендуемом им порядке) и оценка успешного завершения задачи. Когда несколько правил являются одновременно активными для данной задачи, только одно может быть использовано (у студента есть выбор ). Чтобы упростить навигацию, как минимум одно правило для каждой задачи должно быть выбрано. Это означает, что в любой момент, путь, построенный студентом,  по курсу будет правильно преобразован в дерево. Задача + механизм правила реализуют навигационную адаптацию в TANGOW. Фрагменты являются маленькими отрывками html, изображений, апплетов, и т.д. У фрагмента могут быть несколько  версий и в каждой версии будет связанное выражение, которое оценивает его пригодность к данным пользовательской модели. Самая подходящая версия каждого фрагмента в задаче выбирается при создании страниц html, которые представят  задачу данному пользователю, реализовывая текстовую адаптацию. Функции описывают дополнительные аспекты, которые будут добавлены к пользовательской модели для этой детали курса. Например, в курсе о микропроцессорах, могут быть необходимы знания  пользователем  булевой алгебры. Функции булевой алгебры могли бы быть добавлены как "функции", которые рассмотрят в курсе. Функции инициализируются, когда курс посещается в первый раз, используя автоматически сгенерированный анкетный опрос, а заполненные значения позже доступны в целях адаптации. В этом случае, значение функции было бы доступно как map.course.boolean-algebra. Дополнительно, определенные встроенные пользовательские модели характеристики (такие как предпочтенный язык) доступны для всех курсов, и целой модели предметной области непосредственно (включая полную историю) доступную для адаптации. Например, map.task.booleanExercises.grade> =.5 (представление итоговой отметки в задаче, которая включает ряд упражнений о булевой алгебре), может быть лучше чем предоставленное пользователем значение "функции", решая вопрос о понимании пользователем  булевой алгебры. Выражения используют значения от аннотируемой пользовательской модели используя в активации правила, выбор версии фрагмента, условия завершения задачи и параметре распространения вокруг системы, и было реализовано с использованием известного пакета синтаксического анализатора выражений Java [1].


Редакторы


      Инструменты разработки для образовательной AГ должны предоставлять интерфейс, подходящий авторам с хорошим знание их соответствующих доменов, но не обязательно должны обладать всесторонним знанием внутренней работы системы. Интерфейс должен представлять краткий обзор структуры курса, и позволять прямую модификацию этой структуры, поскольку курс развивается. Как описано в [8], высококачественные курсы AГ будут развиваться, таким образом, интерфейс должен учесть и создание курса и более позднее обслуживание. Двумя очевидными кандидатами на структурное представление являются деревья и графы. Деревья обеспечивают иерархическую модель организации курсов, из многих ссылочных материалов найденых в таблице оглавлений. Большинство систем AГ использует деревья в своих инструментах разработки, исключительно или в дополнение к другим представлениям (например, [9,5,7]). Единственный недостаток  использования деревьев то, что неиерархические отношения трудно представить в дереве. Они однако, обычно представляются направленными графами (которые являются обобщением деревьев, где у отдельных узлов может быть больше чем один 'предок'). Основанные на графах инструменты для адаптивного редактирование гиперсреды имеют большее распространено, как в АГА 2.0 основанной на графе редактор [9] и редактор ATLAS TANGOW [12]. Деревья являются очень универсальными интерфейсами, со стандартным расширением и операцией коллапса, а также  имеют хорошо понятную семантику. Дополнительные возможности, обеспеченные представлением графа, делают основанные на графе системы намного более неоднородными. Мы представляем два инструмента разработки для курсов WOTAN, способных к точно тем же самым задачам, которые отличаются только по их представлению курсов. Фактически, оба - автономные Java приложения, которые совместно используют большую часть их кодовой базы. Авторы курса загрузят существующий курс из системы как заархивированый файл (или создадут новый при помощи выбранного редактора), отредактируют курс локально, и загрузят его снова в систему. Редакторы также позволяют авторам импортировать предыдущие ограниченные базой данных курсы в новый формат, и помогают пользователю в редактировании и добавлении версий фрагмента. Однако, это должно не  беспокоить в следующих подразделах, которые имеют дело  исключительно со структурным интерфейсом.
3.1. Редактор дерева
Этот редактор, изображенный в Рис. 2, основан на интерфейсе, найденном в предыдущем сетевом редакторе инструмента для TANGOW. Компонент представляет структуру курса как расширяемое дерево, где узлы могут представить задачи, правила, фрагменты и версии фрагмента. Значки имеющие цветную маркировку  используются, чтобы обозначить каждый из этих элементов. Версии фрагмента являются единственными реальными листами.
2t3t
Рисунок 2. Интерфейс дерева, выводит на экран           Рисунок 3. Интерфейс графа, выводя на экран тот же
часть курса "Трафика". Круговая отметка -                     курс. Аннотации были сделаны  шрифтом Arial.           
задача, доступная через несколько путей.

Дерево может быть расширено и свернуто, не содержит внутреннего состояния (так, чтобы изменение структуры курса при редактировании, вновь придавало актуальность представлению), и может фильтроваться согласно “пользовательскому фильтру” модели.
В Рис. 2 пример иллюстрирует основной недостаток использования деревьев для структуры курса: если единственная задача достижима через различные маршруты, она отмечается с восклицательный знак (в примере, “s_prio_theo”, яркой стрелкой). Трудно
представлять эти неиерархические отношения в иерархическом представлении  дерева.
3.2. Редактор графа
Основанный на графе редактор значительно более сложен. Его начальная цель состояла в том, чтобы решить проблему из неиерархических отношений, с которыми встречаются в основанном на дереве подходе. Однако, использование графов представляет новые проблемы: графы значительно менее эффективны экранируют пространство, требуют выполнение нетривиальное расположения ( автоматически или пользователем),  результат непонятный вне определенного размера. Это заставило принять несколько методов визуализации информации, уменьшить сложность представляемых графов, поддерживая требуемые характеристики это делает их сопоставимыми с деревьями, когда одни только деревья были бы достаточны. Во-первых, автоматическое расположение было предпочтено ручному расположению, поскольку мы понимаем ,что ручное расположение
это слишком большое бремя для пользователей, а автоматическое расположение и выполнение не такое долгое, поскольку количество узлов сохраняется низким. Это достигается через кластеризацию связанных узлов. Навигация всюду по графу выполняется кликом по узлам, которые преобразуют выбранный узел в текущее необходимое место, и разворачивает соседние необходимые узлы и удаляет удаленные 'несоответствующие'. Поведение по умолчанию этого подозрительного подхода [11]  может быть изменено любым не выполнением определенных узлов (так, чтобы ни их позиция, ни их свернутое - несвернутое состояние было изменено изменениями визуализации), или модификацией  переменных: число узлов, которые будут показаны, и размер окружения для расширения. Рис. 3 является снимком экрана интерфейса графа. Нанесенная цветная маркировка и формы используются, чтобы различить различные узлы и граничные типы. Край между “S_Signs” и “S_Types” является  “кластерным краем”, то есть, содержит несколько граней (см. древовидное представление того же самого курса,
в Рис. 2, чтобы идентифицировать включенные грани). Анимация переходов используется, чтобы сохранить  карту пользователя курса во время навигации, поскольку каждое изменение в точке зрения или фильтрации подразумевает другое расположение
узлов, внезапно изменяющиеся позиции узлов имеют раздражающую тенденцию.Основанный на графе редактор создается на основе CLOVER [10] (Кластерная Ориентированная Визуализация Окружения), платформа визуализации графа, которая использует JGraph [2] компонент. CLOVER не является определенным для курсов TANGOW, или действительно адаптивной гиперсреды; это было использовано для визуализации графика в других доменах приложения, таких как система Targeteam [14,10]допускающее повторное использование создание контента.


Экспериментальная установка


      Поскольку оба редактора совместно используют те же самые возможности редактирования, цель эксперимента состоит в том, чтобы измерить скорость, точность и удовлетворение автора каждым из редакторов. Во-первых, участники эксперимента получили краткий учебник для начинающих к структуре курса WOTAN и пример для каждого из инструментов и описанных задач, которые будут сформованы. Им также выдали печатное руководство, используемое в представлении курса и список требуемых задач. Наконец, участников просят выполнить задачи  курса в качестве примера, в порядке использования одного редактора, а затем другого. Порядок выбора инструмента изменяется для каждого участника, так, чтобы половина участников запускала инструменты основанные на дереве, а другая половина запускала  основанные на графе. Поскольку те же самые задачи выполняются дважды для каждого инструмента, пользователям без предыдущего опыта работы с системой (или AH вообще), мы ожидали находить скорость и точность из второго выполнения задания, чтобы они были показательнее  первого запуска.
4.1. Задачи
Все задачи выполняются на курсе в качестве примера, изображенном в предыдущих снимках экрана инструментов. Задачи разрабатываются для того, чтобы быть простыми, но представительными для типичного сеанса редактирования, и представлены в порядке увеличивающейся трудности. Для каждой задачи, время, требуемое для успешного завершения  (как определено экспериментатором по запросу) записывается. После выполнения всех задач, пользователя требуют заполнить маленький "обзор трудности", выставить оценку трудности каждой комбинации задачи/инструмента.
Задача 1: найдите и поменяйте имя данного узла фрагмента, идентифицированного путем, который приводит к нему. Предметы должны будут переместиться по использованию соответствующего инструмента, который является единственной проблемой, представленной этой задачей.
Задача 2: определите местоположение всех путей, приводящих к узлу задачи. Один из путей обеспечивается оператором. Эта задача является наглядной для типичной проблемы в курсах AГ, и мы ожидали, что представление графом  будет выполнено лучше, чем древовидное представление.
Задача 3: добавьте правило, которое будет активным только для пользователей с определенным профилем (расположение правила, и соответствующий профиль информации обеспечиваются в операторе), вставьте задачу в это правило, и добавьте фрагмент к вставленной задаче. Это тестирует основной рост курса.
4.2. Результаты
Результаты эксперимента могут показаны на рисунках 4 и 5. Только 8 участников были приглашены и разделены на две группы. Диаграммы на верхнем ряду представляют время в секундах, требуемых на выполнение каждой задачи. В каждой диаграмме есть 6 блоков столбцов; первые три столбца представляют время, требуемое выполнять каждую из этих 3 задач с каждым из редакторов, в порядке, слева направо. Диаграммы во второй строке выводят на экран воспринятую трудность каждой задачи с каждым редактором (заполненный после выполнения всех задач со всеми редакторами), скорректированный так, чтобы наименее трудная задача для каждого пользователя была на 1 “уровне трудности”.
4t
Рисунок 4. Участники, которые запускали редактор основанный на дереве. Задачи слева выполнялись сначала.
5t
Рисунок 5. Диаграммы для участников, которые начали работу с редактором основанном на графе.

Статистический анализ не является значимым с такой небольшой выборкой, но определенные тенденции видимы. Например, время задачи намного короче во втором выполнении, чем при первом показе, независимо от редактора, который использовался сначала. Это предполагает, что знакомство с понятиями системы и структурой курса более трудно ведущему устройству, чем взаимодействие с редакторами (пользователи только получили очень основное введение в обоих). Время выполнения задачи при помощи  первого инструмента каждой группы очень похожи, хотя Задача 1, кажется, занимает больше времени когда выполняется впервые с редактором графа, вероятно потому что навигация графа более сложна чем древовидная навигация. Как ожидалось, Задача 2 выполняется немного быстрее при использовании редактора графа. Лучшая начальная подготовка должна была понизить время намного больше. Воспринятая трудность обычно ниже для Задачи 2 при использовании редактора основанного на графе. Также интересно, что пользовательские задачи являются более трудными, когда они начинали с древовидого редактора. Это предполагает, что те, кто используют основанный на графе редактор, имели лучшее понимание структуры курса при втором выполнении, и сочли задачи более легкими при выполнении. Вообще, несмотря на различия в интерфейсе, оба инструмента примерно равны для неопытных пользователей,  при выполнении простых задачх. Инструменты графа воспринимают, как более тяжелые в использовании и занимают больше времени, чтобы привыкнуть к инструментам дерева, но обеспечивают лучшее понимание. Знакомство с системой происходило быстро, но все еще учитывало большую часть различия между обоими выполнениями.


Заключительные комментарии и будущие доработки


      Адаптивные образовательные инструменты разработки гиперсреды должны выбрать подходящий интерфейс, чтобы представить структуру контента и отношений. Двумя основными кандидата являются основанные на дереве и основанные на графе представления. Представляется экспериментальная установка для того, чтобы сравнить два подхода к представлению структуры курса, использования деревьев и графов. Основная функция - то, что оба инструмента совместно используют точно те же самые возможности, отличаясь только по представлению курса. Хотя инструменты разработки  разрабатываются на примере системы WOTAN , мы полагаем, что идеи  этого эксперимента применимы к широкому диапазону адаптивных систем гиперсреды. Результаты эксперимента предполагают, что основанные на графе представления лучше подходят для навигации и ориентации в структурах AГ, чем основанные на дереве. Однако, доказательство является неокончательным: выборка является маленькой, знакомство с системой и требуемыми задачами должен быть учтены из эксперимента, чтобы обеспечить более значимое сравнение. Последующий эксперимент с большим объемом выборки планируется в ближайшем будущем, включая более длинное введение в систему WOTAN  обоих редакторов и более широкий массив задач. Интерфейсные незначительные сбои, обнаруженные во время этого первого эксперимента, будут исправлены перед продолжением эксперимента.

Литература

1. Java expression parser. http://www.singularsys.com/jep/.
2. Jgraph java graph visualization component. http://www.jgraph.com/.
3. Paul De Bra, Geert-Jan Houben, and Hongjing Wu. AHAM: A dexter-based reference model for
adaptive hypermedia. In UK Conference on Hypertext, pages 147–156, 1999.
4. P Brusilovsky. Adaptive Hypermedia. In User Modeling and User-Adapted Interaction, volume
11, pages 87–110. Kluwer Academic Publishers, The Netherlands, 2001.
5. Peter Brusilovsky and Gerhard Weber. Elm-art: An adaptive versatile system for web-based
instruction. International Journal of Artificial Intelligence in Education, 12:351–384, 2001.
6. R. M. Carro, E. Pulido, and P. Rodriguez. Dynamic generation of adaptive Internet-based courses.
Journal of Network and Computer Applications, 22(4):249–257, October 1999.
7. R. M. Carro, E. Pulido, and P. Rodriguez. TANGOW: a Model for Internet Based Learning.
International Journal on Continuing Education and Life-Long Learning, 11(1–2), 2001.
8. Alexandra Cristea and Lora Aroyo. Adaptive authoring of adaptive educational hypermedia.
Lecture Notes in Computer Science, 2347:122–132, 2002.
9. P. De Bra, A. Aerts, D. Smits, and N. Stash. AHA! Version 2.0, More Adaptation Flexibility for
Authors. In Proceedings of the AACE ELearn’2002 conference, pages 240–246, October 2002.
10. Manuel Freire and Pilar Rodriguez. A graph-based interface to complex hypermedia structure
visualization. In AVI ’04: Proceedings of the working conference on Advanced visual interfaces,
pages 163–166, New York, NY, USA, 2004. ACM Press.
11. G. W. Furnas. Generalized fisheye views. In Proceedings of the SIGCHI conference on Human
factors in computing systems, pages 16–23. ACM Press, 1986.
12. J. A. Macias and P. Castells. Interactive Design of Adaptive Courses. In M. Ortega and J. Bravo,
editors, Computers and Education - towards an Interconnected Society. Kluwer Academic Publishers,
Dordrecht (The Netherlands), 2001.
13. Pedro Paredes and Pilar Rodriguez. Considering sensitive-intuitive dimension to expositionexemplification
in adaptive sequencing. Lecture Notes in Computer Science, 2347:556–559,
2002.
14. J. Schlichter and G. Teege. Web-based information management for university education. In
Jari Multisilta and Jari-Pekka Niemi, editors, Proceedings of LETTeT 98 and MaTILDA 98 joint
conference, pages 99–106, May 1998.
15. N. Stash and P. De Bra. Building Adaptive Presentations with AHA! 2.0. In Proceedings of the
PEG Conference, July 2003.