close

Вход

Забыли?

вход по аккаунту

?

bd000102636

код для вставкиСкачать
На правах рукописи
ЗАЙЦЕВ ИЛЬЯ БОРИСОВИЧ
А Д А П Т И В Н Ы Е Г И П Е Р М Е Д И А ИЗДАНИЯ,
ИНТЕГРИРОВАННЫЕ В ИНТЕРНЕТ
Специальность 05.13.06 - Автоматизация и управление технологическими
процессами и производствами (полиграфическое производство)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
/Г/
Москва - 2005
Работа выполнена на кафедре «Информационные технологии» Московского
государственного университета печати
доктор технических наук, профессор
Научный руководитель:
Гасов Владимир Михайлович
доктор технических наук, профессор
Официальные оппоненты:
Майков Константин Анатольевич
кандидат технических наук, доцент
Чиннова Ирина Игоревна
Научно-производственное
Ведущая организация:
объединение «Издательство «Наука»
Защита диссертации состоится «2,2 » декабря 2005 г. в f ^ час. Q_0_ мин. на
заседании
диссертационного
совета
К
212.147.02
в
Московском
государственном университете печати по адресу: 127550, г.Москва, ул.
Прянишникова, 2а.
С
лиссертапией
можно
ознакомиться
в
библиотеке
Московского
государственного университета печати.
Автореферат разослан «_/£_» ноября 2005 г.
Ученый секретарь
диссертационного совета
/^л-'Ь^}^^—"
^•"•Агеев
2тЛ- ZZIS07^
гг^г'!
О Б Щ А Я ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы
Среди прочих средств массовой информации (телевидение, радио,
печатные издания) Интернет становится равноправным источником, и его роль
в современном обществе увеличивается с каждым днем. По оценкам Роспечати
интернет-СМИ сегодня выходят на второе место после телевидения, при этом
число постоянных пользователей глобальной сети в России в настоящее время
превысило 18 млн. человек. Популярность информационных интернет-изданий
за последние пягь лет возросла десятикратно, что явилось причиной усиления
конкуренции на рьгаке онлайн-периодики. Все больше традиционных печатных
СМИ вынуждены развивать интернет подписку и делать электронные версии
собственных печатных изданий; на данный момент раздел российского
сегмента «СМИ-Периодика» уже насчитывает более 1700 web-ресурсов.
Прогаозируется, что среди прочих ресурсов именно электронные версии
периодических изданий в ближайшее время будут занимать лидирующие
позиции по посещаемости.
С каждым днем объем информации, хранящийся на web-серверах,
увеличивается,
внедряются
все
новые
технологии.
Увеличение
функциональности гипермедиа систем приводит к усложнению интерфейсов,
логической
структуры,
а
также
информационной
«перегруженности»
визуальных макетов. В такой постоянно развивающейся среде как Интернет,
конечному
пользователю
становится
все
сложнее
ориентироваться
в
гиперпространстве и осуществлять доступ к информацигашым архивам. В
результате
возникает
чрезвычайно
актуальная
проблема,
связанная
с
неэффективным использованием web-ресурсов (увеличение временных затрат
на поиск релевантных гипермедиа документов, досрочное прекращение сеанса
работы и т.д.). Решение данной проблемы может быть найдено в разработке
интеллектуальных
механизмов
прогнозирования предпочтений
РОС. НАЦИОНАЛ' ' АУ
БИБЛИОТЕКА
;
з^.'УЖ^';
- *
конечных
пользователей и представление информации в форме, отвечающей их текущим
потребностям.
Использование методов и подходов из различных областей искусственного
интеллекта и математической статистики дает возможность построения, так
называемых, адаптивных гипермедиа систем, способных динамически изменять
свою структуру и формат представляемых данных в ответ на действия
пользователя, который взаимодействует с данной системой. Таким образом,
наряду с интерактивньпии и статическими гипермедиа изданиями, которые
предоставляют однотипную информацию для всей аудитории, можно говорить
о появлении нового класса адаптивных электронных изданий, целью которых
является персонализация содержимого (текстовой и мультимедиа информации),
навигационной структуры или формата отображаемых данных. Однако следует
отметить, что наиболее значимой проблемой, стоящей перед адаптивными
изданиями, является оптимизация навигационной структуры гипермедиа
страниц, в результате которой добавляются релевантные гиперссылки или
исключаются избьггочные варианты навигации.
Повышающийся с каждым годом уровень требований к современным
1-ипермедиа изданиям, рост конкуренции на рынке сетевой периодики ставят
перед разработчиками ряд задач, связанных с проектированием адаптивных
интерфейсов и эффективным прогнозированием предпочтений пользователей.
Вместе с тем необходимо учитывать специфику поведения пользователей в
ходе взаимодействия с информационными гипермедиа изданиями, в частности,
электронными версиями
отсутствие
стимула
информации,
в
периодических
предоставлении
долгосрочное
печатных
изданий, а именно:
предпочтений
использование
и
персональной
web-ресурсов,
преобладание
пассивного характера просмотра издания.
Таким образом, наиболее актуальным вопросом является реализация
гибких
механизмов
адаптатдаи,
осуществляющие
прогнозирование
характеристик пользователя без ведения интерактивного диалога с ним.
Цель работы
Разработка методик адаптации навигационной структуры гипермедиа
изданий, интегрированных в глобальную сеть Интернет, для обеспечения
эффективного поиска, просмотра
и доступа к
информации конечного
пользователя.
Задачи исследования
Для достижения поставленной цели в работе решаются основные задачи:
• Обобщение опыга теоретических и практических разработок в
области адаптивных гипермедиа систем.
• Выбор подхода к адаптации, учитывающего специфику класса
информационных электронных изданий.
• Разработка методики неявного определения значимости гипермедиа
страниц для конечного пользователя.
• Разработка
модифицированных
алгоритмов
адаптации,
учитывающих офаничения информационной фильтрации.
• Практическая реализация модуля адаптации с помощью выбранных
аппаратных и прохраммных средств.
• Оценка действенности и практической пригодности предложенных
методик на примере интеграции электронной версии печатного
издания в адаптивную гипермедиа систему.
Объект исследования
Объектом исследования в данной диссергационной работе выбраны
гипермедийные электронные издания, интегрированные в x■Jюбaльнyю сеть
Интернет.
Предмет исследования
В
качестве
предмета
исследования
выступает
процесс
адаптации
навигационной структуры сетевых электронных изданий для конечного
пользователя.
Методы исследования
Для достижения поставленной в работе цели и решения перечисленных
задач использованы методы различных областей искусственного интеллекта,
математической статистики, а также интеллектуального анализа данных.
Теоретической и методологической основой диссертационной работы
послужили работы отечественных и зарубежных специалистов в области
совместной фильтрации (Резник Ф., Бриз Д., Сарвар Б., Голдберг Д.),
статистической обработки данных (Цукерман И., Берхин П., Левен М.,
Андерсон К.), теории случайных процессов (Рабинер Л., Чен X.), теории
информации (Шанон К.), человеко-компьютерного взаимодействия (Дикарев
СБ., Брусиловский П.Л., Перковиц М.),
Научная новизна
Наиболее
существенные
научные
результаты,
полученные
в
диссертационной работе:
• Построена модель адаптивного гипермедиа издания, отражающая
процесс
адаптации
на
уровне
навигационной
структуры
в
соответствии с характеристиками конечного пользователя.
• Предложен новый алгоритм совместной фильтрации, основанный на
«наивном»
Байесовском
классификаторе
и
коэффициенте
взаимозависимости пользовательских сеансов, который позволяет
повысить
точность
рекомендации
и
обеспечить
низкую
вычислительную сложность.
• Впервые предложена модель расчета индексов предпочтения для
гипермедиа страниц на основе скрытых марковских цепей, которая
позволяет прогнозировать релевантность документов с учетом
особенностей
поведения
комбинированный
конечных
индикатор
пользователей.
предпочтения,
Разработан
базирующиеся на
скрытых марковских моделях и времешплх наблюдениях. Впервые
предложена
методика
нормализации
временных
индексов
предпочтения на основе коробчатых диаграмм распределения с
учетом объема гипермедиа страниц.
• Разработана архитектура адаптивного гипермедиа издания с учетом
предложенных методик, обеспечивающая гибкую интеграцию с
существующими динамическими гипермедиа системами. Подход к
интеграции
механизмов
персонализации
электронных
изданий
является новым и оригинальным.
Практическая ценность работы
Обоснован выбор программных и аппаратных средств для построения
адаптивной архитектуры гипермедиа издания и
внедрения результатов
исследования; определены требования к данным и обучающим выборкам,
используемым в алгоритмах совместной фильтрации.
Разработаны
программные
модули
адаптации,
которые
реализуют
предложенные в рамках диссертациошюй работы методики и интегрированы в
адаптивную гипермедиа систему на примере электронной версии печатного
издания.
Сформулированы рекомендации по технической реализации, которые
могут быть использованы для проектирования адаптивных гипермедиа
изданий,
модификации
существующих
гипермедиа
изданий,
а
также
построения смежного класса гипермедиа систем, в частности, адаптивных
обучающих систем, интегрированных в Интернет.
Апробация работы
Разработанные методики и алгоритмы адаптации реализованы в виде
серверных профаммных модулей, которые интегрированы в электронное
периодическое издание «Мир печати», а также в информационную гипермедиа
систему ЗАО «Курортпроект», о чем свидетельствуют соответствующие акты
внедрения.
Содержание отдельных разделов диссертации в целом докладывались на
заседаниях кафедры «Информационные технологии» и на конференции
«Информационные системы управления учебным процессом в вузе» в
Московском государственном университете печати.
Публикация
Основные результаты диссертации отражены в четырех печатных работах,
а также тезисах доклада на конференции «Информационные системы
управления учебным процессом в вузе» в МГУП.
Структура и объем диссертации
Диссертационная работа состоит из введения, четырех глав, выводов, двух
приложений, списка литературы из 92 наименований, содержит 150 страниц
машинописного текста, в том числе 6 таблиц и 35 рисунков.
Положения, выносимые на защиту
1. Методика определения релевантности гипермедиа страниц для
конечного пользователя на основе скрытых марковских моделей.
2. Модифицированный алгоритм «наивного» Байесовского
классификатора в рамках совместной фильтрации.
3. Оценка эффективности адаптивной гипермедиа системы на базе
разработанного индикатора предпочтения.
4. Адаптивная архитектура гипермедиа издания, интегрированного в
Интернет на примере электронной версии периодического издания
«Мир печати».
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность работы, определяется объект и
предмет
исследования,
формулируются
цели
и
задачи
исследования,
раскрывается научная новизна и практическая ценность работы.
Первая
глава
посвящена
вопросам
адаптивного
представления
информации в гипермедиа системах.
В разделе 1.1 рассматриваются вопросы совремешюго состояния развития
рынка сетевых
информационных
изданий. Анализ текущего состояния
российского сегмента глобальной сети Интернет показывает, чго в настоящее
время большинство
традиционных
гипермедиа
изданий, предоставляют
статическую информацию и не учитывают предпочтения и характеристики
пользователей.
Выделяются наиболее значимые проблемы эффективного взаимодействия
пользователя с гипермедиа изданиями, включая jpymmpOBKy совместной и
коррелированной информации. Производится анализ ограничений статического
представления информации и архитектуры традиционных интерактивных
систем. Показывается, что адаптивная архитектура призвана обеспечить
эффекгивный просмотр, поиск и доступ к гипермедиа документам.
В разделе 1.2 приводится классификация электронных изданий, а также
гипермедиа систем, интегрированных в Интернет. Находится пересечение
данных классификаций. Наряду с интерактивными и детерминированными
электронными изданиями выделяется новый класс адаптивных гипермедиа
изданий (АГИ), которые являются частным случаем адаптивных web-сайтов.
В
разделе 1.3 производится анализ существующих форм и видов
адаптации, а также обосновывается выбор подходов и форм адаптации
применительно к рассматриваемому классу информационных изданий. Главная
1фоблема, стоящая перед адаптивными изданиями, заключается в изменении
навигационной
добавляются
структуры
релевантные
гипермедиа
страниц,
гиперссылки
или
в
результате
исключаются
которой
избыточные
варианты навигации.
Дается обзор теоретических и практических разработок в области
адаптивных
гипермедиа
систем
(раздел
1.4).
Производится
анализ
существующих подходов к адаптации; подчеркивается вклад отечественных
(Брусиловский П.Л, Дикарев СБ.) и зарубежных (Сарвар Б., Либерман X.,
Мобашер Б., Резник Ф.)
ученых в развитие теории информационной
фильтрации и человеко-компьютерного взаимодействия.
Осуществляется
попытка
анализа
стратегий
взаимодействия
пользователей с гипермедиа изданиями. Для электронных версий печатных
периодических изданий наиболее х^актерна неориентированная стратегия
просмотра,
поэтому
наиболее
целесообразно
рассматривать
вопросы
группировки совместной информации.
В разделе 1.5 осуществляется систематизация характеристик конечного
пользователя, необходимых для построения пользовательской модели, а также
производится выбор конкретных характеристик для реализации адаптивной
гипермедиа системы.
Для реализации конкретных
методов адаптации предпочтительным
является использование неявных оценок релевантности гипермедиа страниц. Из
рассмотренных характеристик пользователя наиболее важными в построении
пользовательской модели являются: текущая и агрегатная релевантность,
краткосрочные и среднесрочные интересы.
В соответствие со спецификой класса рассматриваемых электронных
изданий в качестве основы разрабатываемой адаптивной системы были
выбраны методы совместной фильтрации, которые учитывают
модель
пользователя и принимают во внимание целевые характеристики, а также
характеристики состояния. Результат совместной фильтрации представляется в
форме рекомендации, которой соответствуют следующие основные виды
адаптации на навигационном уровне: добавление дополнительного блока
гиперссылок, скрытие гиперссылок, форматирование гиперссылок, создание
расширенных гиперссылок.
Вторая глава посвящена разработке модели адаптивного гипермедиа
издания и модифицированных алгоритмов современной фильтрации.
В разделах 2.1 и 2.2 рассматриваются особенности систем рекомендаций и
этапов
совместной фильтрации, выделяется ряд задач и
составляется
математическая модель разрабатываемой адаптивной системы.
Для
решения
поставленных
задач
требуется
ввести
следующие
обозначения;
W — (P,L,Mw)
-
исходная
гипермедиа
вертикальном уровне описания;
10
система
на
конечном
Р = {Pi,P2,"fPu}
- множество конечных гипермедиа страниц;
Z- = {/,, /j,...} - множество гиперссылок, связывающие данные страницы;
I = (^p^,Pj,a) - отдельная гиперссылка представляет собой совокупность
исходящей страницы, входящей страницы и якоря, содержащего текстовое
описание ссылки;
Mw = (B,T)
- макет гипермедиа системы, определяющий визуальную
структуру концептуальньк блоков;
В = {b^,b2,...} - тип концептуальных блоков: навигационный блок,
информационный блок, колонтитул страницы, дополнительный навигационный
блок
и
т.д.;
Т
-
матрица,
определяющая
взаимное
расположение
концептуальных блоков;
Исходная адаптивная гипермедиа система включает в себя М конечных
гипермедиа страниц, а также хранит данные о Л^ прошлых сеансов. Обучающая
выборка представляет собой матрицу размером NxM, в которой каждый
элемент Гу является индексом предпочтенияу-ой страницы г-ым пользователем.
Под
индексом
предпочтения
понимается
количественное
выражение
релевантности, которая в свою очередь является характеристикой пользователя
и отражает степень его заинтересованности в размещенной на конкретной
странице
значения,
информации. Индексы
при
этом
предпочтений
невостребованные
принимают
страницы
дискретные
(которые
не
были
просмотрены за текущий сеанс) имеют неопределенное значение, обозначаемое
символом i..
и = {u^,U2,...,Ufj} - множество прошлых N пользовательских сеансов
взаимодействия с гипермедиа изданием;
[ ? ; . ] - обучающая выборка R (матрица индексов предпочтений);
[Гд,] - М-разрядный вектор Ra частичной сессии текущего пользователя;
т; . е {l,2,...,F,±|,
i=l,2,...,N, j=l,2,...,M - тскрегш&я шкала оценок
(индексов предпочтения);
11
р^Л La(^L
- текущая (активная) страница, на которой сгенерировано
некоторое подмножество гиперссылок;
Р^ ~{Pri'Pr2'"-'PrL}
~ множество рекомендуемых страниц, имеющих
максимальные индексы предпочтений, которые были прогнозированы для
отсутствующих значений вектора Ra;
L r = {/^,,/^2>• • •}> К~{Ра'Рг'^)^
LrczL
- множество рекомендуемых
гиперссылок;
Адаптация заключается в изменении навигационной структуры исходной
гипермедиа системы W путем объединения множеств Lr и La, то есть
Lr^La,
при этом блок рекомендаций генерирует множество ссылок Lr: Ь^^^ Т Lr.
Цель совместной фильтрации заключается в рекомендации L гипермедиа
документов
с
наибольшими
значениями
прогнозируемых
индексов
предпочтений г а/, рассчитанных на основе обучающей выборки R я Мразрядного вектора Ra:
Га/ = f{R,Rd),
V/: г^^ =J. - прогнозирование индексов предпочтения
для каждой невостребованной текущим пользователем страницы.
Среди множества существующих методов совместной фильтрации были
выбраны и исследованы методы регрессии, классификации и кластеризации, а
также предложены решения, учитывающие ограничения каждого из методов.
В разделе 2.3 описывается методика, основанная на классификаторе «J^ближайших» соседей. Для данной методики был предложен механизм проверки
значимости расчетного коэффициента корреляции Пирсона с использованием
Г-теста, а также введены дополнительные критерии для формирования
множества ближайших пользователей.
В
разделе
2.4
описывается
вероятностный
подход к
совместной
фильтрации и представляется новый алгоритм «наивного» Байесовского
классификатора, позволяющий производить обучение классификатора только
12
для сильносвязанных пользовательских сессии по отношению к целевой
странице.
Чтобы хфименить
метод Байесовского
классификатора для задачи
совместной фильтрации, отдельно обучается один классификатор для каждой
гипермедиа страницы р^, где у €.\,...,М. В классификации участвуют только
те пользовательские сессии в обучающей выборке, в которых страница р
была востребована:
и^>^ ciU,\fu';'^ ■.r,^^^L,ie[\..n^l
где П =-\и '"^^^ I - число сессий во множестве U ^^^.
Входные
вектора,
которые
используются
для
формирования
классификатора, содержат значения индексов предпочтения для всех страниц,
кроме самой страницы р . Страница р
называется целевой, остальные
элементы входного вектора - страницами-атрибутами.
Для
повышения
множество и^^.
точности
классификации
предложено
01раничить
Для этого оценивается вес целевой страницы в текущей
сессии, то есть агрегатная значимость данной страницы по отношению ко всем
другим страницам;
•5,,^ =bgm',
'-
где
—
.
тп\-\
K.jy= log (и^^ In у) - поправочный коэффициент;
и - число сессий, имеющих совместные просмотры страниц JTny;
m'l - число востребованных страниц в пользовательской сессии;
Ml
= H{R
MI,
) + H(R
) - H{R
,Ry) - коэффициент взаимозависимости.
чг-'е-.
=УУ P{R=co,R=
о)-log
13
P(R=a},R=v)
^-^
-^
'—
Коэффициент взаимозависимости, основанный на энтропии, позволяет
выявить статистическую зависимость между целевой страницей и каждой
страницей-атрибутом. Поправочный коэффициент вводится в выражение с
целью уменьшить влияние коэффициента Mlj^y для тех страниц, которые имеют
незначительное перекрытие (количество совместных просмотров).
Таким образом, для обучения классификатора для каждой целевой
страницы используется отдельное множество, в которое попадают только те
пользовательские сессии, которые содержат сильно связанные страницы по
отношению к целевой, а также имеют большее количество просмотров:
VM'^^^5.
> V
I
i,y
у
Модифицированные выражения для расчета начальных и условных
вероятностей (во избежание нулевых частот):
V + Пу
P{Rj
=а)\Щ=о)-
\ + Т."'А(а)-д^(о)
^ ' = ' '-'^ ^
'''^ ^
где
1, если г^у = V
I О, если r^^^tu
где
11, если r^j-(o
^,Л^) = I О, если r^j ^ (О
Прогнозирование индексов предпочтения для невостребованных текущим
пользователем страниц (с учетом отсутствующих странш^-атрибутов):
14
ray =2^gmsxP%=v)Y[Y[P{R^=cD\R^
=vY"""\
где
fl, если r^j = CO
5Л(о)
=
>
■
a/'
10, если r^j 4t (o
Далее, в разделе 2.5 рассматриваются приемы стандартной кластеризации
многомерных векторов, а также представляется эффективный алгоритм
инициализации для метода кластеризации «^Г-медиан», который уменьшает
влияние результирующих данных от исходного выбора центров кластеров.
Для каждой описанной методики приводится: общее математическое
обоснование, функциональные схемы осуществления рекомендации, а также
блок-схемы модифицированных алгоритмов.
Третья
глава
посвящена
анализу
традиционных
индикаторов
предпочтения и разработке нового индикатора, основанного на интерфейсных
наблюдениях.
В
разделе 3.1 дается классификация существующих индикаторов,
используемых в современных адаптивных гипермедиа системах, проводится
анализ ограничений временных и одиночных интерфейсных индикаторов с
использованием
коробчатых
диаграмм. Из
рассмотренных
индикаторов
предпочтений пользователей наиболее эффективным остается индикатор,
основанный на временных наблюдениях. Показано, что выбор подхода к
нормализации временных индексов предпочтения играет значительную роль
для последующих методов совместной фильтрации. Предложена методика
нормализации временных индексов предпочтения на основе коробчатых
диаграмм распределения с учетом объема гипермедиа страниц.
Выдвигается пpeдпoJЮжeниe о том. что в процессе использования
гипермедиа издания пользователь последовательно пребывает в одном из
нескольких состояний. Данные состояния являются скрытыми, то есть, их
15
нельзя распознать и зафиксировать на стороне сервера. Вьщелено три основных
скрытых
состояния
пользователя:
«беглый
просмотр»,
«чтение»,
«игнорирование». Беглый просмотр характеризуется попыткой пользователя
ознакомиться с содержимым страницы, прежде чем он начинает более
детальное
изучение.
В
процессе
чтения
пользователь
внимательно
просматривает отдельные фрагменты гипермедиа страницы. Игнорирование
характеризуется желанием пользователя уйти со страницы или найти
альтернативные пути навигации и в конечном счете сводится к возвращению на
предыдущую страницу, переходу в другой тематический раздел или окончанию
сеанса работы с текущим гипермедиа изданием.
На основе предположения о скрытых состояниях пользователя разработана
методика вычисления индексов предпочтения с использованием аппарата
скрытых марковских моделей (раздел 3.2). Считается, что генерация состояний
пользователя - марковский случайный процесс. Поскольку состояния системы
не наблюдаемы, имеет место скрытая марковская цепь. Наблюдаемые символы
составляют цепочку внешних интерфейсных наблюдений, которую возможно
однозначно распознать и обработать на стороне сервера. Поскольку из любого
состояния возможно оказаться в любом другом за один шаг и число
наблюдаемых символов конечно, то рассматривается эргодическая дискретная
модель.
Ниже приведены составляющие скрытой марковской модели:
S - {Sy,...,Sff} - множество N скрытых состояний пользователя:
Si= 's' («scan» - беглый просмотр);
S2= 'г' («read» - чтение);
8з= ' i ' («ignore» - игнорирование);
Q = {q^,...,qj) - последовательность скрытых состояний;
^, - переменная, отображающая скрытое состояние в момент времени t;
Y = {и, ,...,Уд^} - множество Мнаблюдаемых символов (отдельных
интерфейсных событий):
16
ц =' г («MouseMoveNav» - движение «мыши» над вспомогательными и
навигационными блоками);
U2='2' («MouseMovebif» - движение «мьппи» над конечным
информационным блоком);
L>3 ='3' («MouseClickInf» - нажатие левой кнопки «мьгащ» в пределах
конечного информационного блока);
U4='4' («ScrollPage» - пролистывание страницы);
U5='5' («ScrollStop» - символ окончания пролистывания). Событие
наступает
только
в
случае,
если
предыдущий
символ
соответствует
пролистьгеанию страницы и в данный момент времени не наблюдается других
событий;
Указанные интерфейсные наблюдения снимаются в фиксированные
моменты времени (через каждые 0,5 сек). Исключение составляют нажатия
клавиш «мьппи», которые соотносятся с ближайшей меткой времени.
А = [Oj ] - квадратная матрица переходов NxN дня скрыгых состояний;
а, ^ = Рх{я,+\ = Sj\q^= s^) - вероятность переходов между скрьггьпкш
состояниями в модели Я ;
В = [Ь (т)]
- матрица эмиссии MxN;
bj (т) = P^{o,=o^\q,=Sj)
- вероятность эмиссии D^^ в состоянии Sj;
О = (o,,...,Oj.) - последовательность Г внешних наблюдений;
о^ - переменная, отображающая внешнее наблюдение в момент времени /;
Я" = [я",] ~ вектор начальных вероятностей перехода в скрытые состояния;
Я = (У4,5,Л") - скрытая марковская модель, которая определяется
параметрами А, В и ж.
17
Вероятность генерации
данной последовательности
наблюдений конкретной
моделью
последовательность
скрытых состояний
<HTML>
irrissirsiTT
0 = (0,,02,...,0j.)
последовательность
внешних наблюдений:
• движение «мыши»
• пролистывание страницы
• окончагае пролистывания
W
'-
-'
Алгоритм
прямого хода
t
aj Щ
' '•/! —{п
4i W
'<?;(.~ -.Л'."''SiT.'-'
о
я
Алгоритм ВнтерОи
4t-
aj
I
min
тах>
Рис. 1. Принцип определения релевантности гипермедиа страниц на основе
скрытых марковских моделей
В с ю процедуру расчета индексов предпочтения можно разбить на три
этапа (рис. 1).
1.
Выбор
оптимальной
модели,
описывающей
заданную
цепочку
интерфейсных наблюдений. С одной стороны на вход системы поступает
иоследовашльность наблюдений 0 = (а,,...,с,.), с другой - набор обученных
С М М для релевантной и нерелевантной страниц - Л,^ и Л^ соответственно.
Вероятность генерации текущей последовательности каждой из обученных
моделей Р{01 ^j,) и Р{0 \ /l^) осуществляется с помощью алгоритма прямого
хода путем вычисления ОТ, (г) - вероятности частичной последовательности
наблюдений до момента времени t и пребывании в состоянии 5, в момент
времени t, если задана модель X:
18
aXi) =
P(Ov-o„q,=Si\A)
Из двух моделей выбирается та, которая имеет большую вероятность
генерации заданной последовательности Р(0 \ Я).
2. Декодирование последовательности внешних наблюдений с учетом
выбранной модели. Данный этап предполагает нахождение последовательности
скрьггых состояний пользователя, которая наилучшим образом соответствует
последовательности интерфейсньпс наблюдений. Данная задача решается с
помощью алгоритма Витерби, где за критерий оптимальности принимается
максимизация вероятности P ( g , 0 | Д).
3. Расчет индексов предпочтения на основе последовательности скрытых
состояний. Релевантность конкретной гипермедиа страницы оценивается с
точки зрения отношения количества состояний, соответствующих «чтению»
информационного блока к числу всех остальных состояний. Релевантность тем
вьппе, чем больше пользователь читал страницу.
т
Vшш)■2l^i^^'^2)
(^шах
^.=
1Г^-^
(I
+ К,.,
где Siq„s,)
если а, =s,
= \'
/=i /-1
В
данном разделе также особое внимание уделяется особенностям
обучения моделей, а также вопросам инициализации процедуры Баум-Велча.
Исходные параметры СММ выбирались исходя из экспертных оценок с
последующим анализом согласованности мнений экспертов.
В третьем разделе производится оценка эффективности предложенной
методики с использованием непараметрического теста Крускаля-Валлиса, а
также
выявляются
соответствующие
ограничения. Суть
данного теста
заключается в сравнении медиан распределений выборок, соответствующим
релевантным и нерелевантным просмотрам, при этом надежность индикатора
определяется степенью различия уровня медиан. Экспериментальная оценка
эффективности
предложенного
индикатора
19
показала
преимущества
по
сравнению с временными и отдельными интерфейсными индикаторами
предпочтения (табл. 1).
Таблица 1. Результаты теста Крускаля-Валлиса
Время
Критическое значение/^ при уровне значимости 0,05
Н-: 0,0520
Н+: 0,0373
Н+: 0,0125
Время
движения
«мьшга»
Н-: 0,1731
Н-: 0,1352
Н-: 0,1222
Преимущества
индикатора
пролистывания
S
2S
3S
Число нажатий
клавшп «мыши»
Н-: 0,2358
Н--0,2151
Н-: 0,1452
Время
пребывания на
странице
Н+: 0,0435
Н+: 0,0232
Н+: 0,0096
Индикатор
СММ
Н+: 0,0033
Н+. 0,0027
Н+: 0,0048
предпочтений, основанного на
скрытых
марковских моделях, заключаются в возможности прогнозирования скрытых
состояний
пользователя,
выявлении
доли
событий,
отвечающих
за
непосредственное чтение страницы, возможности учета квалификации и стиля
поведения пользователя. В отличие от временных индикаторов, индексы
предпочтения не требуют нормализации, и в меньшей степени зависит от
объема гипермедиа страницы. При достаточной интерфейсной активности
разработанный индикатор способен также распознавать фршментальную
релевантность.
При
небольших
(Г<8)
последовательностях
внешних
интерфейсных наблюдений рекомендуется использовать комбинированный
индикатор предпочтения, учитывающий временные наблюдения.
Четвертая
глава
посвящена
вопросам
практической
реализации
разработанного адаптивного гипермедиа издания, а также особенностям
интеграции его в глобальную сеть Интернет.
В разделах 4.1 и 4.2 производится выбор аппаратных и программных
средств для реализации модуля адаптации на примере интеграции электронной
версии печатного издания «Мир печати» в адаптивную гипермедиа систему
(рис. 2). Рассматривается функциональная модель адаптивного модуля (рис. 3),
а также структура модуля сбора интерфейсных наблюдений. Для конечной
реализации адаптивной гипермедиа системы рекомендовано использовать webсерверную платформу Apache в связке с интерпретатором серверных сценариев
РНР и СУБД MySQL.
20
в
третьем разделе осуществляется сравнение методик совместной
фильтрации и оценка эффективности предложенных модифицированных
алгоритмов.
Производится
выбор
конкретной
методики
совместной
фильтрации для осуществления рекомендаций с учетом вычис;штельной
сложности и статистических показателей эффективности.
Клиентская часть
Модуль сбора
интерфейсных
наблюдений
Web-«6poy3ep»
<НТМ1>
.. ■ S
Л
I. Запрос по протоколу http
Серверная часть
2. Передача скрытых
данных о пользователе
Web-сервер
Модуль
адаптации
с5СЯ1РТ> I
адаптации
—2^—-~
Гипермедиа система:
программная часть
<8СИРТ>
А 4. Получение данных из базы знаний
3. Обновление
Web-сервер Б Д
5. Результат
■
7 Генерация конечных
html страниц
V
у
6. Выборка содержимого
с учетом результатов
адаптации
Информагдаонное
содержимое
Модель
пользователя
1
Рис. 2. Архитектура адаптивного гипермедиа издания
Оценка эффективности производится следующим образом. Обучающая
выборка разделяется на две части: для проведения эксперимента и для
непосредственного
обучения
системы.
Для
каждого
сеанса
м,
из
экспериментальной выборки «удерживается» первые и просмотров, формируя,
таким образом, частичную сессию {Ra}, которая поступает на вход модуля
адаптации. Далее, множество {Lr} рекомендуемых гиперссылок сопоставляется
с оставшейся частью пользовательской сессии {R-Ra} и находится количество
совпадений. Эффективность метода совместной фильтрации оценивается
посредством статистических показателей: точности, покрытия и меры F1:
1
^|{Zr-}n{J?--Jga-}|
pr(L) = —Y}—
1
21
1
1
s\{Lr^>}n{R<'>-Ran\
cov(Z) = — ■ Х-
i
j
N и \{Г'^-Ка^^}\
^j(j-)^2pr(L)-cov(Z,)
/7r(L) + cov(X)
Точность определяет долю востребованных рекомендаций по отношению к
общему числу
отображаемых
рекомендаций. Вместе
с тем, покрыгае
характеризует долю востребованных рекомендаций по отношению к общему
числу просмотров в текущей
сессии за исключением удержанных п
просмотров. Оба показателя являются важными для оценки эффективности,
поэтому в экспериментах акцентируется внимание на величине F1, которая
принимает
максимальное
значение,
когда
и
точность,
и
покрытие
максимизированы. Чтобы определить окончательные значения приведенных
показателей находится среднее для всего множества пользовательских сессий в
экспериментальной выборке.
Из трех предложенных методик совместной фильтрации наиболее
предпочтительньш
является
модифицированный
алгоритм
«наивного»
Байесовского классификатора, поскольку обеспечивает компромисс между
вычислительной
эксперимента
сложностью
для
методики
и
показателями
«наивного»
эффективности.
Байесовского
В
ходе
классификатора
установлен необходимый и достаточный объем обучающей выборки, вьине
которого абсолютная ошибка рекомендации не уменьшается. Наименьшую
вычислительную сложность обеспечивает методика кластеризации «/(Г-медиан»,
однако имеет невысокую точность рекомендации.
В
заключении представлены основные результаты диссертационной
работы.
В
приложениях приведены фрагменты программного кода модуля
адаптации на языке серверных
сценариев РНР,
а также
результаты
итерационной процедуры Баум-Велча для обучения скрытых марковских
моделей.
22
с
Модуль адаптации
Z)
Получение
характеристик
пользователя
Корректность
данных
Обученные
скрытые
Маковские
...мрлеад...
Вычисление ицдексов
предпочтения для
страницы-источника
1
Корректность
индексов
'
Обновление
серверного
журнала
''
Совместная
фильтрация
Выборка
повторных
рекомендаций
1 Параметры
, модели
Формирование
рекомендаций
Генерация
гипермедиа
содержимого
Конец
сеанса?
Генерация
«всплывающего»
(скрытого) окна
Отправка данных
пользователю
Рис. 3. Функциональная модель адаптивного модуля гипермедиа издания,
интегрированного в Интернет
23
ОСНОВНЫЕ ВЬШОДЫ и РЕЗУЛЬТАТЫ РАБОТЫ
1. В результате анализа существующих видов и подходов к адаптации
применительно к электронным версиям периодических изданий
выделены формы адаптащга, касающиеся рекомендации пгасрмедиа
документов и оптимизации навигационной структуры электронных
изданий в реальном времени, которые позволяют обеспечить
эффективный доступ к информационным архивам и ориентировать
конечных
пользователей
на
долгосрочное
использование
электр01тых изданий.
2. Согласно
задачам
предложены
группировки
совместной
модифицированные
информации,
алгоритмы
регрессии,
классификации и кластеризации, учитывающие ограничения методов
совместной фильтрации. В частности, для методики «/С-ближайших
соседей» был предложен механизм проверки значимости расчетного
коэффициента корреляции Пирсона с использованием Г-теста, что
позволило динамически формировать множество
К-ближайших
пользователей в зависимости от количества совместных просмотров.
Для методики «наивного» Байесовского классификатора удалось
повысить
точность
рекомендации
путем
обучения
среди
сильносвязанных пользовательских сессий по отношению к целевой
странице на основе коэффициента взаимозависимости. Для методики
кластеризации «К-медиап» предложен алгоритм инициализации,
уменьшающий влияние исходного выбора центров кластеров на
результирующие данные.
3. Разработана
методика
определения
релевантности
гипермедиа
документов, базрфующаяся на скрытых марковских моделях (СММ),
которая позволяет вычислять неявные индексы предпочтения с
учетом
особенностей
частности,
скорости
поведения
восприятия
24
конечных
пользователей,
информации
и
в
моментов
бездействия.
Результаты
эксперимента
с
использованием
непараметрического теста Крускаля-Валлиса подтвердили гипотезу
об адекватности предложенной модели.
4. В соответствии с пользовательской моделью произведен сбор и
статистическая
обработка
навигационной
информации,
формирующей обучающую выборку, что позволило определить
требования к входным данным для предложенных алгоритмов
совместной фильтрации.
5. Произведен
сравнительный
анализ
предложенных
методик
совместной фильтрации, на основе статистических показателей
эффективности:
точности,
покрытия
рекомендации,
а
также
величины F 1 . В результате оценки эффективности для конечной
реализации
выбран
алгоритм
«наивного»
Байесовского
классификатора, обеспечивающий высокую точность рекомендации
и компромисс в вычислительной сложности. Выявлен достаточный
объем обучающей выборки, при котором достигается минимальная
абсолютная ошибка рекомендации.
6. Осуществлена программная реализация предложенных методик на
примере интеграции электронной версии периодического печатного
издания «Мир печати» в адаптивную гипермедиа систему. Модуль
адаптации включает в себя пакет серверных сценариев, написанных
на web-ориентированном языке РНР
и предназначенных для
интеграции с СУБД MySQL. В ходе эксплуатации адаптивного
издания зафиксировано увеличение средней длины пользовательских
сеансов
на
24%,
а
также
предпочтений в среднем на 40%.
25
увеличение
агрегатного
индекса
Основное содержание работы изложено в следующих публикациях:
1. Зайцев И.Б. Оптимизация передачи гипертекстовых изданий в
глобальных сетях // Известия вузов. Проблемы полиграфии и
издательского дела. Вып.З. - М.: М Г У П , 2003. - С. 82-86. (0,28 п.л.).
2 Зайцев И.Б. Модифицированный алгоритм «К-ближайших соседей»
для совмесшой фильтрации в адаптивных гипертекстовых системах
// Вестник МГУП. Хо5. - М.: МГУП, 2005. - С. 105-112. (0,69 п.л.).
3. Зайцев И.Б. Оценка релевантности гипермедиа документов на основе
скрытых марковских моделей // Информационные технологии
моделирования и управления №5 (23). - Воронеж: Изд-во «Научная
книга», 2005. - С . 730-738. (0,55 п.л.).
4. Зайцев И.Б. Методика «наивного» Байесовского классификатора для
задачи совместной фильтрации в системах рекомендации // Доклады
независимых авторов. Вып.2. Изд-во «DNA», Россия-Израиль, 2005.
- С . 20-27. (0,51 П.Л.).
26
Принято к исполнению 18/11 /2005
Исполнено 18/11/2005
0 0 0 «11-й Ф О Р М А Т » И Н Н 7726330900
Москва, В^шавское ш., 36
(095) 975-78-56
(095) 747-64-70
www.autoreferat.ru
Заказ № 1320
Тираж: 100 экз.
1122 4 42
РНБ Русский фонд
2006-4
22827
Документ
Категория
Без категории
Просмотров
0
Размер файла
926 Кб
Теги
bd000102636
1/--страниц
Пожаловаться на содержимое документа