Содержание к диссертации
Введение
Глава 1. Разработка математических методов персонализации на основе исследования моделей адаптивных веб-ресурсов 15
1.1. Математические модели и методы персонализации в интернете 15
1.1.1. Модели информационного поиска 17
1.1.2. Методы совместной фильтрации 21
1.1.3. Методы интеллектуального анализа данных 25
1.1.3.1. Метод кластеризации транзакций и обращений к веб-ресурсу 26
1.1.3.2. Метод выдачи рекомендаций на основе нечеткого композиционного правила вывода 35
1.2. Разработка математической модели и методов проектирования адаптивных веб-ресурсов 38
1.2.1. Исследование адаптивных систем 38
1.2.2. Методы и технические приемы адаптивной гипермедиа 41
1.2.3. Модель адаптивного веб-ресурса 43
1.2.4. Модель пользователя 47
1.3. Выводы по первой главе 53
Глава 2. Использование нечетких графовых моделей для построения системы поддержки принятия решений в задачах персонализации 55
2.1. Метод оценки и классификации информационных потоков на основе нечеткой гиперграфовой модели 55
2.2. Метод определения набора критериев для системы поддержки принятия решений с многокритериальным выбором альтернатив 63
2.3. Выводы по второй главе 72
Глава 3. Разработка методов проектирования адаптивных веб-ресурсов на основе нечетких ультраграфовых моделей 74
3.1. Разработка теории и исследование нечетких ультраграфовых моделей 74
3.1.1. Определение и способы задания нечетких ультраграфов 74
3.1.2. Исследование нечетких ультраграфов с позиции нечетких соответствий 77
3.1.3. Связность и достижимость в нечетких ультраграфах 79
3.2. Метод определения живучести нечетких ультраграфов 83
3.2.1. Нечеткие полушарниры, шарниры и мосты в нечетких ультраграфах 83
3.2.2. Алгоритм поиска нечетких шарниров в нечетких ультраграфах 87
3.2.3. Алгоритм поиска нечетких шарниров в нечетких гиперграфах 93
3.3. Методы поиска нечетких ассоциативных правил на основе нечетких ультраграфов 95
3.3.1. Нечеткие транзакции и нечеткие ассоциативные правила 95
3.3.2. Паросочетания и покрытия в нечетком ультраграфе 99
3.3.3. Алгоритм поиска максимальных паросочетаний в нечетком ультраграфе 102
3.3.4. Методы поиска минимальных нечетких трансверсалей в нечетком гиперграфе 109
3.4. Методы кластеризации ассоциативных правил на основе нечетких ультраграфов 110
3.4.1. Метод кластеризации на основе автокомпозиции нечетких ультраграфов 111
3.4.2. Метод кластеризации на основе разрезания нечетких ультраграфов 114
3.5. Экспериментальная оценка эффективности адаптивного поиска 119
3.6. Выводы по третьей главе 121
Заключение 124
Литература 126
Приложения 135
- Метод выдачи рекомендаций на основе нечеткого композиционного правила вывода
- Метод определения набора критериев для системы поддержки принятия решений с многокритериальным выбором альтернатив
- Исследование нечетких ультраграфов с позиции нечетких соответствий
- Нечеткие транзакции и нечеткие ассоциативные правила
Введение к работе
Актуальность темы. Бурное развитие информационных технологий и Всемирной Паутины обусловило появление информационных систем, охватывающих интересы большого неоднородного коллектива пользователей. У непрофессиональных пользователей, как правило, не возникает стремления - особенно если у них нет времени - изучить более или менее сложный язык запросов. Интенсивное обучение применению языка запросов не представляется возможным еще и потому, что у пользователей различные цели, интересы и неодинаковая образовательная подготовка.
Проблему избытка информации можно эффективно решать путем адаптации информации к конкретному пользователю или группе пользователей. Эффективным инструментом адаптации в сети интернет являются механизмы персонализации. Они позволяют настроить веб-ресурс на нужды конкретного пользователя и в результате каждому посетителю предложить информацию и товары, соответствующие его вкусам и предпочтениям. При этом учитываются различия в индивидуальных социально-психологических и иных требованиях, обоснованные неоднородностью пользовательских запросов.
В настоящее время отслеживание поведения и предпочтений потребителей, а также взаимодействие с ними в реальном времени с помощью технологий персонализации, является одним из ключевых элементов работы с пользователями через интернет, беспроводные устройства и интерактивное телевидение. По данным исследования Forrester Research, лишь 13% веб-ресурсов содержат элементы персонализации, между тем, на них совершается 68% всех покупок в интернете. Согласно результатам исследования Evans Data Corporation, в котором участвовало более 800 производителей программного обеспечения из США и Канады, в ближайшие год-два экспоненциально растущим спросом будет пользоваться
6 разработка решений в области персонализации. К 2006 году инвестиции в технологии персонализации составят 2,1 миллиарда долларов, и их разработка будет доминирующим направлением в развитии приложений для интернета.
Особую актуальность данный подход приобретает в системах электронной коммерции. Разнообразие потребительских товаров и услуг затрудняет выбор. Вместо прежнего относительно узкого диапазона коммерческих предложений потребитель сталкивается с сотнями и тысячами вариантов. Системы персонализации в интернете комбинируют проверенные приемы маркетинга с возможностями новой информационной среды. Они охватывают большой диапазон продукции, стараются определить индивидуальные вкусы и потребности и на основании этого выдать персональные рекомендации, подсказывающие, какой вариант для потребителя наиболее предпочтителен. Если такие рекомендации оказываются востребованными, они способствуют созданию дополнительной ценности и лояльности. Оказание помощи потребителю при его выборе способствует тому, что потребитель точнее и самостоятельнее определяет собственные вкусы.
Удобство для пользователя относится к так называемым нечетким понятиям, его невозможно определить точно и выразить количественно. Существенная часть знаний о пользователях носит скрытый, неявный характер. Выявить такие знания на основе анализа поведения пользователей в системе позволяют методы интеллектуального анализа данных и технологии добычи данных, ориентированные на автоматическое накопление и формирование знаний.
Информационные потоки в интернете, и в системах персонализации в частности, подвержены большому числу ошибок и нечеткостей, которые сопровождают все этапы, начиная с извлечения схем взаимодействия пользователей с веб-ресурсом и заканчивая выдачей рекомендаций. Они включают в себя стадии протоколирования обращений к веб-ресурсу,
7 обработки протоколов с целью выделения пользовательских сессий и транзакций, кластеризации сессий и извлечения пользовательских профилей. Для моделирования столь широкого спектра нечеткостей естественным является обращение к теории нечетких множеств и мягких вычислений.
Разработка систем персонализации в интернете является предметом исследований большого числа ученых, по этой тематике проводятся многочисленные международные конференции, выходят книги и специальные выпуски журналов.
Теоретические и практические предпосылки настоящего исследования составили фундаментальные и прикладные работы ученых в следующих областях:
человеко-машинные и ориентированные на пользователя информационные системы (П. Брусиловский, В.Г. Захаревич, Б. Мобашер, Д.А. Поспелов);
представление и использования знаний и данных (М. Минский, X. Уэно), в том числе нечеткоопределенных (Л.А. Заде, Л.С. Берштейн, А.В. Боженюк, А. Кофман, А.Н. Мелихов, Н.Е. Сергеев, Э.А. Трахтенгерц, P.P. Ягер);
представление структур данных и знаний с помощью графов, гиперграфов и ультраграфов (Л.С. Берштейн, А. Ахо, К. Берж, Р.Х. Гётчел, А.А. Зыков, Н. Кристофидес, О. Оре, М. Свами, У. Татт, Д. Хопкрофт);
методы интеллектуального анализа данных (Р. Агравал, М. Вонг, А. Гинезей, В.А. Дюк).
Цель работы и задачи исследования. Целью диссертационной работы является развитие теории и разработка методов и алгоритмов решения задач интеллектуального анализа данных на основе нечетких ультраграфов, а также применение разработанных подходов к проектированию адаптивных интернет-ресурсов.
Поставленная цель определяет следующие основные задачи диссертационного исследования:
Выявление особенностей, характерных для рассматриваемого класса задач персонализации, и выбор адекватного подхода к разработке методов их решения.
Разработка концепции и методики создания адаптивной интеллектуальной информационно-советующей системы для решения задач персонализации в интернете.
Проведение исследований по изучению, разработке и теоретическому обоснованию формальных математических моделей и методов отображения структуры адаптивного веб-ресурса, представленного нечеткими фреймами, в нечеткие ультраграфы.
Разработка и исследование методов оценки и классификации информационных потоков в интернете на основе нечетких гиперграфовых и ультраграфовых моделей.
Исследование структурных свойств нечетких ультраграфов с позиции нечетких соответствий. Определение понятий нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах.
Разработка и исследование методов и алгоритмов определения живучести нечетких ультраграфов на основе выделения нечетких шарниров.
Разработка методов и алгоритмов поиска нечетких ассоциативных правил на основе выделения всех биклик (максимальных полных двудольных подграфов) и нахождения всех максимальных паросочетаний в нечетком ультраграфе.
Разработка методов и алгоритмов кластеризации нечетких ассоциативных правил на основе автокомпозиции и разрезания нечетких ультраграфов.
Методы проведения исследований основаны на использовании теории и методов искусственного интеллекта, аппарата теории нечетких множеств и нечеткой логики, теории графов (гиперграфов и ультраграфов), методов интеллектуального анализа данных, теории информационного поиска.
9 Научная новизна работы заключается в следующем:
Предложена математическая модель адаптивного веб-ресурса, представленного нечеткими фреймами, позволяющая на основе нечетких ультраграфов естественно формализовать и исследовать индивидуальные запросы пользователей.
Впервые введены понятия и исследованы свойства нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах.
Разработаны методы и алгоритмы определения живучести нечетких ультраграфов на основе выделения нечетких шарниров в нечетких ультраграфах.
Разработаны методы и алгоритмы поиска нечетких ассоциативных правил на основе выделения всех биклик и нахождения всех максимальных паросочетаний в нечетких ультраграфах.
5. Разработаны методы и алгоритмы кластеризации нечетких
ассоциативных правил на основе разрезания нечетких ультраграфов.Практическая ценность результатов исследования заключается в следующем:
Разработанные теоретические положения, методы и алгоритмы использованы при создании систем поддержки принятия решений, предназначенных для решения задач персонализации в интернете.
Разработанная концепция создания адаптивной интеллектуальной информационно-советующей системы использована при проектировании модуля персонализации веб-контента и организации динамической навигации по сайтам электронной коммерции.
Разработанные методы и алгоритмы выделения нечетких шарниров в нечетких ультраграфах использованы при создании комплекса проблемно-ориентированных прикладных программ.
Разработанные методы и алгоритмы поиска и кластеризации нечетких ассоциативных правил использованы при создании
10 информационного портала, обеспечивающего индивидуальный подход к посетителям.
Достоверность полученных в диссертации результатов подтверждается математическими и аналитическими доказательствами и оценками, проведением вычислительных экспериментов на ЭВМ, результатами практического использования предложенных в диссертации моделей, методов и алгоритмов, подтвержденного актами и справками об их внедрении, а также апробацией работы на региональных, всероссийских и международных конференциях.
Реализация результатов работы. Диссертация выполнена в соответствии с основным направлением научно-исследовательской работы Таганрогского государственного радиотехнического университета «Формальные системы, искусственный интеллект и системы принятия решений».
Основные результаты диссертационной работы использованы и внедрены при выполнении научных проектов и научно-исследовательских работ, в том числе:
при выполнении научного проекта Российского Фонда Фундаментальных Исследований (грант РФФИ 03-01-06498 МАС) по теме: «Разработка и развитие теории нечетких гиперграфов и их применение в качестве адекватных моделей сложных систем, работающих в условиях частичной неопределенности», проводимого в 2003 г.;
при выполнении госбюджетной НИР №15551 «Разработка теории, моделей и методов принятия решений в интегрированных интеллектуальных системах на основе нечетких знаний и смешанного представления атрибутов», выполняемой на кафедре прикладной информатики ТРТУ в 2001-2004 г.г.;
при разработке модуля персонализации веб-контента и организации динамической навигации по сайтам компании «Мезон.ру» (г. Санкт-Петербург), предоставляющим пользователям возможности поиска
11 релевантных товаров в интернет-магазинах в 2000-2004 г.г.;
при создании дилерского портала Южной Софтверной Компании
«ЮСК: Дистрибьюция» (г.Ростов-на-Дону), обеспечивающегоиндивидуальный подход к пользователям с целью организации эффективной маркетинговой и информационно-технической поддержки партнеров по дистрибуции ПО в 2004-2005 г.г.
Внедрение и использование результатов диссертационной работы подтверждаются соответствующими актами и справками.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на И-м Международном научно-практическом семинаре "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2003 г.); Всероссийской научной конференции "Управление и информационные технологии УИТ-2003" (Санкт-Петербург, 2003 г.); международных научно-технических конференциях и молодежных научных конференциях "Интеллектуальные САПР" (Геленджик, 1999-2004 г.г.); Третьем Всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2002 г.); Научной сессии МИФИ-2001 "Банки данных. Интеллектуальные системы. Программное обеспечение" (Москва, 2001 г.); 3-й Международной научно-технической конференции "Интерактивные системы ИС-99" (Ульяновск, 1999 г.); И, V, VI, XI международных научно-технических конференциях "Математические методы и информационные технологии в экономике, социологии и образовании" (Пенза, 1999-2003 г.г.); II Всероссийской научно-практической конференции "Проблемы информатики в образовании, управлении, экономике и технике" (Пенза, 2002 г.); IV Международной научно-технической конференции "Логико-математические методы в технике, экономике и социологии " (Пенза, 1999 г.); IV, V, VI Всероссийских научных конференциях студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (Таганрог, 1998, 2000, 2002 г.г.); III Межгосударственной научно-практической конференции "Экономико-организационные проблемы
12 проектирования и применения информационных систем" (Ростов-на-Дону, 1999 г.); 4-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов "Новые информационные технологии в научных исследованиях и в образовании" (Рязань, 1999 г.); I Всероссийской научной конференции молодых ученых и аспирантов "Новые информационные технологии. Разработка и аспекты применения" (Таганрог, 1998 г.); на ежегодных научно-технических конференциях профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ.
Публикации. Результаты диссертации отражены в 14 печатных работах. Структура и объем работы. Диссертационная работа состоит из введения, 3 основных глав, заключения, списка использованной литературы и 3 приложений.
Во введении обоснована актуальность темы диссертационной работы, сформулированы цель и задачи исследования, охарактеризованы научная новизна работы, ее практическая ценность, реализация и апробация результатов работы, дано краткое содержание структуры диссертации.
В первой главе дана формальная постановка задач персонализации и определены общие принципы формирования моделей предметной области. Представлены и сравниваются между собой различные модели и методы персонализации, проведен их анализ и классификация. Проведено исследование адаптивных систем, дан обзор методов и технических приемов адаптации. Разработаны концепция и методика создания адаптивной интеллектуальной информационно-советующей системы для решения задач персонализации в интернете, позволяющие интегрировать семантические знания и онтологии с целью учета иерархии концептов на множестве веб-ресурсов. Разработана модель адаптивного веб-ресурса, представленного нечеткими фреймами, которая позволяет на основе нечетких ультраграфов формализовать и исследовать индивидуальные запросы пользователей. Модель пользователя описана в виде профилей на основе истории посещений.
13 Во второй главе рассмотрены методы оценки и классификации информационных потоков в интернете на основе использования нечетких графовых и гиперграфовых моделей для построения систем поддержки принятия решений в задачах персонализации. Предложены методы определения набора значимых критериев для системы поддержки принятия решений с многокритериальным выбором альтернатив на основе выделения нечетких баз в нечетких графах, позволяющие снять неопределенность оценки важности критериев.
В третьей главе рассмотрены методы проектирования адаптивных веб-
ресурсов на основе использования нечетких ультраграфовых моделей как
обобщения понятий нечеткого гиперграфа и нечеткого ориентированного
графа. Разработан метод определения живучести нечетких ультраграфов на
основе нахождения нечетких шарниров. С этой целью впервые введены
понятия нечетких полушарниров и шарниров, полумостов и мостов в
нечетких ультраграфах. Для поиска устойчивых сочетаний обращений к веб-
ресурсу на основе их совместного вызова в транзакциях разработаны методы
поиска нечетких ассоциативных правил на основе выделения всех биклик
(максимальных полных двудольных подграфов) в нечетком двудольном
графе. В развитие метода чередующихся цепей для нечетких ультраграфов
разработан алгоритм выделения всех максимальных паросочетаний в
нечетком ультраграфе. С целью нахождения интересных ассоциативных
правил в условиях многомерных разреженных данных разработаны методы
кластеризации нечетких ассоциативных правил на основе автокомпозиции и
разрезания нечеткого ультраграфа. Предложен последовательный локально
оптимальный алгоритм разрезания нечеткого ультраграфа.Экспериментальная оценка произведена на основе данных о посещениях сайта Microsoft из специализированного репозитория больших наборов данных.
В заключении перечислены основные результаты работы.
В приложении 1 представлены акты о внедрении и справки об использовании результатов работы.
В приложении 2 приведен листинг программного кода, реализующего генерацию нечетких ультраграфов.
В приложении 3 приведены диаграмма UML и листинг программного кода, реализующего поиск нечетких шарниров в нечетких ультраграфов.
Метод выдачи рекомендаций на основе нечеткого композиционного правила вывода
В случае, когда s = 1, t = 0, поведение пользователя i2 близко к поведению пользователя /,. В ситуации, когда Dw =0 для s = l, г = 0, пользователь /2 ведет себя в точности как пользователь /,. Если Dsl = 0 для s = 1, г = 1, пользователь г, более экспансивен и склонен выставлять оценку на 1 балл выше. С другой стороны, если Dsl =0 для $ = \, t = -\, более экспансивен пользователь /2. Наконец, если Dxl =0 для s = -l, / = v + l, поведение пользователя i2 полностью обратно поведению пользователя /,. Однако, во всех описанных случаях пользователь /, надежно предсказывает поведение пользователя г,.
Данный алгоритм удобно реализовать на ориентированном графе [рис. 1.1]. Вершины ориентированного графа представляют пользователей, а ребра между ними - предсказуемость как степень близости между двумя пользователями. Для того чтобы вычислить оценку конкретного объекта для пользователя in нужно найти кратчайший путь из вершины /„ к вершине im, представляющей пользователя, который уже дал оценку этому объекту.
Когда путь найден, по значениям s и t для каждой дуги графа обратным проходом вычисляется значение оценки для пользователя in.
В отличие от многих других подходов к совместной фильтрации, хортинг исследует транзитивные отношения: граф может быть пройден через пользователей, которые еще не давали оценки объекта. Кроме того, метод учитывает такую характеристику пользователя, как эмоциональность, а также принимает во внимание пользователей с противоположными оценками.
Главным недостатком методов совместной фильтрации является необходимость сбора большого числа оценок, что затруднительно на первых этапах работы системы. При этом актуальной является проблема масштабируемости алгоритмов [Sarwar, Karypis, etc., 2000]. Производительность методов и точность оценок снижается с ростом числа объектов оценки и пользователей.
В работе [Nichols, 1998] за предпочтение объекта другим объектам принимается его покупка. В работе [Breeze, 1998] функция предпочтения пользователя строится на основе списка документа, к которым пользователь обращался непосредственно перед совершением покупки. Однако сбор не выраженных явно оценок в полной мере не решает проблемы, поскольку ложноположительная рекомендация может в итоге привести к разочарованию клиента. Хорошие результаты метод совместной фильтрации показывает при использовании небинарных оценок [Dai, etc., 2000].
В [Linden, Smith, York, 2003] предложен алгоритм, который вместо схожих пользователей ищет схожие объекты. Для этого на основе данных о двух и более объектах в пользовательской корзине предварительно строится матрица близости объектов. Далее алгоритм ищет объекты, релевантные текущему набору пользователя, производит их агрегацию и рекомендует наиболее коррелируемые из них. Основная часть вычислений производится в офлайне, что позволяет решить проблему масштабируемости, сохраняя при этом качество рекомендаций. Данный метод персонализации используется в системе Amazon.com.
Интеллектуальный анализ данных (ИАД) предназначен для выявления скрытых тенденций, закономерностей, взаимосвязей и перспектив развития процесса, учет которых помогает повысить качество принимаемых решений. Методы, используемые в интеллектуальном анализе данных, являются логическим обобщением различных аналитических подходов, как традиционных, имеющих длительную историю развития, например, статистика, так и сравнительно новых: генетические алгоритмы, нейронные сети, нечеткие множества. Новизна интеллектуального анализа данных заключается в расширении сферы применения этих методов, что стало возможным благодаря возросшей доступности данных и удешевлению вычислений.
Рост интереса к средствам интеллектуального анализа объясняется, главным образом, возросшими требованиями к результатам анализа, резким увеличением объема перерабатываемой информации, усложнением решаемых задач и временными ограничениями анализа обстановки и принятия решений. Интеллектуальные системы компьютерного анализа данных, как правило, основываются на следующих подходах. Первый заключается в том, что в системе фиксируется опыт эксперта, который используется для оценки создавшейся ситуации. На этом подходе базируется построение экспертных систем.
Второй подход основывается на анализе исторических данных, описывающих поведение изучаемого объекта, принятые в прошлом решения, их результаты (например, анализ временных рядов стоимости валют и акций, статистика продаж различного рода товаров, результаты избирательной кампании и т.п.).
Наконец, существует третий подход - комбинация первых двух: результаты, полученные при анализе исторических данных, оцениваются на основе опыта эксперта.
В последнее время резко возрос интерес ко второму и третьему подходам. Это объясняется тем, что в связи с резким усложнением управленческих задач возникли новые потребности в глубоком анализе поступающей и хранящейся в базах данных информации, выполняемой в реальном масштабе времени.
В современных условиях особое значение приобретает задача управления знаниями о пользователях и потребителях. В силу этого наблюдается большой научный и практический интерес к интеллектуальному анализу данных и технологии добычи данных в сети Интернет (web mining) -извлечению знаний, интересных схем, моделей, не выраженной в явном виде информации в интернете.
В применении к интеллектуальному анализу данных в интернете классические методы кластеризации оказываются малоэффективными ввиду высокой размерности данных и несовершенства избираемых мер близости. В связи с этим активно разрабатываются новые подходы, учитывающие специфику предметной области.
Метод определения набора критериев для системы поддержки принятия решений с многокритериальным выбором альтернатив
Оверлейные модели могут осуществлять независимое измерение уровня знаний пользователя по различным темам. Они были разработаны в области интеллектуальных обучающих систем (ИОС) и моделирования обучаемого. Во многих ИОС модель обучаемого представляет собой только оверлейную модель знаний обучаемого. Поэтому оверлейная модель знания пользователя как часть комплексной модели пользователя иногда называется моделью обучаемого.
Оверлейная модель представляет гибкий и мощный механизм адаптации. Недостатком данной модели является сложность инициализации, когда трудно установить весь набор значений модели для нового пользователя.
Другая модель представления знаний - стереотипная модель пользователя, в которой различают несколько типичных пользователей для каждого направления классификации. Стереотипная модель также может быть представлена в виде набора пар "стереотип-значение", где значением выступает, например, "истина" или "ложь" как принадлежность пользователя к стереотипу либо вероятностная величина как вероятность принадлежности пользователя к данному стереотипу. Стереотипная модель, в общем случае, не такая мощная, но более простая и универсальная, чем оверлейная модель, ее проще инициализировать и поддерживать.
Исследователи отмечают, что для реализации большого числа эффективных методов и технических приемов адаптации возникает необходимость в детализированной оверлейной модели. Преобразование данных из стереотипной модели в оверлейную может быть реализовано, используя сопоставление постоянного набора пар "концепт-значение" с каждым стереотипом либо с помощью подхода, основанного на "трудности" концептов.
Хорошие результаты достигаются в результате совмещения стереотипной и оверлейной моделей. При этом стереотипная модель используется в начале работы с целью классификации нового пользователя и инициализации начальных значений оверлейной модели, после чего используется традиционная оверлейная модель.
Цель пользователя или задача пользователя - это параметр, зависящий, в большей степени, от самой природы работы пользователя в гипермедиа, нежели от пользователя как такового. В зависимости от типа системы, это может быть рабочая цель (в прикладных системах), цель поиска (в информационно-поисковых системах), и цель обучения или решения (в обучающих системах). Во всех этих случаях цель является ответом на вопрос «Почему пользователь использует систему и чего хочет в итоге достичь?». Цель пользователя - это наиболее изменчивая характеристика пользователя. Она почти всегда будет другой при новом сеансе работы с системой, а иногда может изменяться и во время одного сеанса работы. Целесообразно различать локальные цели, которые могут изменяться достаточно часто, и общие, являющиеся более стабильными.
Для моделирования цели пользователя, как правило, используется оверлейная модель. В этом случае система гипермедиа поддерживает и распознает фиксированный набор возможных целей (или задач) пользователя. Набор целей может быть небольшим, тогда для простого моделирования текущей цели пользователя цель включается в модель пользователя. Более развитые системы работают одновременно с возможными и текущими целями пользователя. Возможные цели можно эффективно представить в виде иерархии (дерева) задач.
Следующие две характеристики пользователя, уровень подготовки и имеющийся опыт, имеют нечто общее с уровнем знаний пользователя, но функционально отличаются от него. Под уровнем подготовки пользователя будем понимать всю информацию, связанную с предыдущим опытом работы пользователя, не относящуюся к темы данной гипермедиа-системы. Подготовка включает в себя профессию пользователя, опыт работы в смежных областях, а также точку зрения пользователя и его перспективу. Опытом работы пользователя в данной гипермедиа мы называем характеристику, отражающую то, насколько хорошо пользователь знаком со структурой адаптивной гипермедиа, и то, насколько легко он может осуществлять навигацию в данной гипермедиа или данной гипермедийной модели.
Для моделирования уровня подготовки и опыта работы часто используется стереотипная модель пользователя. Стереотипом выступает стереотип опыта или стереотип уровня подготовки для таких категорий как профессия, перспектива или родной язык.
Еще одной характеристикой пользователя, рассматриваемой системами адаптивной гипермедиа, является набор предпочтений пользователя. По различным причинам пользователь может предпочитать некоторые узлы, ссылки и части страниц гипермедиа другим. Эти предпочтения могут быть абсолютными или относительными, то есть, зависящими от текущего узла, цели или текущего контекста. Предпочтения отличаются от других компонентов модели пользователя по нескольким аспектам. В отличие от других компонентов, предпочтения не могут быть логически выведены системой, поэтому пользователь должен непосредственно или косвенно (например, посредством простой обратной связи) сообщить системе свои предпочтения.
Модель пользователя удобно описать в виде нечетких профилей на основе истории посещений. Исходными данными при этом выступают записи в протоколах обращений к серверу в расширенном формате Combined Logfile Format (CLF) следующего вида [Енюков, Ретинская, Скуратов, 2004]: remotehost authuser [date] "request" status bytes referrer agent, где remotehost - имя или IP-адрес машины пользователя; authuser - идентификатор пользователя; date - дата и время обращения; request - запрос пользователя (метод HTTP-запроса, путь к странице на сервере, HTTP-протокол); status - код статуса, возвращенный сервером; bytes - количество переданных байт; referrer - ссылающийся ресурс; agent - сведения о машине пользователя. На этапе предобработки данных на основе эвристик и формальных методов, приведенных в [Cooley, Mobasher, Srivastava, 1999], производится последовательная очистка данных, идентификация пользователя, идентификация сессии, выправление сессии и, наконец, идентификация транзакций и формирование пользовательских профилей.
Исследование нечетких ультраграфов с позиции нечетких соответствий
Задача поиска всех нечастовстречающихся наборов элементов адекватна нахождению минимальных нечетких трансверсалеи в нечетком гиперграфе [Целых, 2003].
Определение 3.32. Нечеткой трансверсалью, или нечетким вершинным покрытием, нечеткого гиперграфа Н = {X,U) назовем нечеткое подмножество вершин TQX, ДЛЯ которого справедливо (\/ujGU)(f nUj 0), при этом Иными словами, пересечение нечеткого подмножества вершин f с х с каждым ребром не пусто, при этом функция принадлежности элемента ХЕ X нечеткому покрытию f совпадает с наибольшей степенью инцидентности этого элемента ребрам UjSU . Определение 3.33. Минимальной нечеткой трансверсалью нечеткого гиперграфа H = (X,U) называется такая нечеткая трансверсаль f, что никакое ее нечеткое подмножество T QT не является нечеткой трансверсалью.
Семейство минимальных нечетких трансверсалеи нечеткого гиперграфа Н = (Х,Е) задает нечеткий гиперграф трансверсалеи Тг(Н) на X с минимальными нечеткими трансверсалями в качестве гиперребер. Свойство 3.13. Каждая нечеткая трансверсаль содержит хотя бы одну минимальную нечеткую трансверсаль. Один из алгоритмов нахождения семейства всех нечетких трансверсалеи основан на алгоритме, предложенном Магу для четких графов [Берштейн, Боженюк, 1999; Зыков, 1987]. Достаточно, записав нечеткую конъюнктивную нормальную форму, раскрыть скобки в полученном выражении и выполнить минимизацию по правилам нечеткой логики. При этом значение поглощающей нечеткой переменной выбирается как минимум из всех поглощаемых и собственного значения. На практике данный алгоритм эффективен, когда пересечение множеств ,. достаточно мощное и можно существенно воспользоваться законом поглощения по мере раскрытия скобок. Кроме того, если предварительно известна хотя бы одна нечеткая трансверсаль, то в процессе раскрытия скобок можно отбрасывать слагаемые, представляющие собой произведение \т\ и более различных переменных. Другой подход к нахождению нечеткого гиперграфа трансверсалей основан на разложении нечеткого гиперграфа на множество гиперграфов а -уровня. Для нахождения 7У(Я) воспользуемся процедурой алгоритма нахождения четкого гиперграфа трансверсалей, приведенной в работе [Berge, 1989]. Разложим нечеткий гиперграф Н = {Х,Е) на базовое множество четких ультраграфов {на ,На2,...,на"}. Найдем Тг(Н" ). Для каждой полученной минимальной нечеткой трансверсали т;.1 найдем Гг(Я2 и{{ху} є 7; . Будем производить аналогичные вычисления вплоть до шага п: Tr(Ha" Kj Xj}\xjeT" 1]). В итоге, получим нечеткое множество г 1 2 - =и{сг(7; ,ч ,,/J к = 1,. ..,п], которое задает нечеткий гиперграф трансверсалей Тг(Н). С целью нахождения интересных нечетких ассоциативных правил в многомерных разреженных данных рассмотрим методы кластеризации Ill нечетких ассоциативных правил на основе автокомпозиции и разрезания нечеткого ультраграфа. Определение 3.34. Композиция нечеткого ультраграфа H = (X,U) и двойственного ему ультраграфа Я =(U,X) называется прямой Щ автокомпозицией нечеткого ультраграфа. В результате прямой автокомпозиции получим нечеткий граф Gx =(X,W), представляющий собой нечеткое отношение на множестве вершин ультраграфа. Используя различные выражения для построения функции принадлежности №F(PP ) можно получить различные модификации отношений, представляемых графом Gx =(X,W) [Мелихов, Берштейн, Коровин, 1990]. Пусть значения функции принадлежности MF(P.P ) MW определяются выражением: В этом случае граф Gx = {X,W) представляет собой нечеткое отношение нечеткого равенства вершин ультраграфа и может быть использован для щ кластеризации исходного множества вершин. Выделение семейства /-нечетких клик позволяет осуществить группирование вершин в классы, нечетко эквивалентные со степенью эквивалентности не меньшей t. Для выделения f-нечетких клик рассмотрим понятие нечетко смежных и нечетко полных подмножеств гиперграфа. Нечетко смежными называются вершины ха и хр, если существует нечеткое ребро UJGU, которое инцидентно обеим вершинам, причем величина называется степенью смежности вершин ха и хр. Отношение нечеткой смежности f, заданное на множестве вершин X нечеткого ультраграфа H-(X,U), является отношением нечеткой толерантности, поскольку оно одновременно нечетко рефлексивно: cc(T)ref = & //x(x,,x() 0,5, так как {ix(xi,xi) = l, и нечетко симметрично: , что следует из определения нечеткой смежности вершин. Поскольку отношение f в общей сложности не транзитивно, то каждая вершина ХЕ X порождает по отношению Г множество нечетких классов толерантности fr(x). Класс толерантности fr(x) представляет собой нечеткое подмножество множества X, образованное попарно нечетко смежными вершинами.
Нечеткие транзакции и нечеткие ассоциативные правила
Рассмотрены методы проектирования адаптивных веб-ресурсов на основе использования нечетких ультраграфовых моделей как обобщения понятий нечеткого гиперграфа и нечеткого ориентированного графа. Структурные свойства нечетких ультраграфов исследованы с позиции нечетких соответствий. Исследованы вопросы связности и достижимости в нечетких ультраграфах. Введены понятия нечеткого ориентированного маршрута, нечеткого цикла, степени достижимости и степени взаимной достижимости.
Разработан метод определения живучести нечетких ультраграфов на основе нахождения нечетких шарниров. Впервые введены понятия и исследованы свойства нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах. Разработан алгоритм нахождения нечетких шарниров в нечетком ультраграфе на основе выделения всех элементарных циклов в нечетком ультраграфе. Алгоритм нахождения нечетких шарниров и генератор нечетких ультраграфов реализованы в виде программы на языке Си++. Предложен эффективный алгоритм нахождения нечетких шарниров в нечетких гиперграфах на основе разложения на а -уровни и метода поиска в глубину.
Разработаны методы и алгоритмы поиска нечетких ассоциативных правил. Показано, что задача поиска нечетких ассоциативных правил адекватна задаче выделения всех биклик (максимальных полных двудольных подграфов) в нечетком двудольном графе. Указанная задача решается поиском всех максимальных внутренне устойчивых множеств в дополнительном двудольном графе. В развитие метода чередующихся цепей для нечетких ультраграфов предложен алгоритм выделения всех максимальных паросочетаний в нечетком ультраграфе. Обобщены методы и алгоритмы поиска нечеткого гиперграфа трансверсалей.
Разработаны методы кластеризации нечетких ассоциативных правил на основе прямой автокомпозиции и разрезания нечеткого ультраграфа, позволяющие находить интересные ассоциативные правила в многомерных разреженных данных. Разработан последовательный локально оптимальный алгоритм разрезания нечеткого ультраграфа, разбивающий множество вершин на классы с оптимизацией целевой функции, характеризующей число разрывов нечетких дуг нечеткого ультраграфа. Экспериментальная оценка произведена на основе данных о посещениях сайта Microsoft из репозитория больших наборов данных с использованием количественной оценки эффективности выдаваемых рекомендаций на основе методов информационного поиска. В ходе проведенных исследований получены следующие основные научные и практические результаты: 1. Разработаны концепция и методика создания адаптивной интеллектуальной информационно-советующей системы, отличающейся от известных интеграцией семантических знаний и онтологии с целью учета иерархии концептов на множестве веб-ресурсов. Разработана математическая модель адаптивного веб-ресурса, представленного нечеткими фреймами, которая позволяет на основе нечетких ультраграфов естественно формализовать и исследовать индивидуальные запросы пользователей. 2. Разработаны и исследованы методы оценки и классификации информационных потоков на основе нечетких гиперграфовых моделей. Предложен метод определения набора значимых критериев для системы поддержки принятия решений с многокритериальным выбором альтернатив на основе выделения нечетких баз в нечетком графе, позволяющий ЛПР исследовать критерии, агрегированные в ранжируемые группы, и снять неопределенность оценки их важности. 3. Впервые введены понятия и исследованы свойства нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах. Исследованы структурные свойства нечетких ультраграфов. Впервые предложен метод определения живучести нечетких ультраграфов на основе выделения нечетких шарниров в нечетких ультраграфах и разработаны алгоритмы нахождения нечетких шарниров в нечетких ультраграфах и нечетких гиперграфах. 4. Разработаны методы и алгоритмы поиска нечетких ассоциативных правил на основе выделения всех максимальных полных двудольных подграфов и нахождения всех максимальных паросочетаний в нечетких ультраграфах. Обобщены методы и алгоритмы нахождения нечеткого гиперграфа трансверсалей. При работе с базами данных с большим числом нечетких транзакций предложенный подход характеризуется более высокой производительностью в сравнении с традиционными алгоритмами Аргіогі. 5. Разработаны методы и алгоритмы кластеризации нечетких Т ассоциативных правил на основе автокомпозиции и разрезания нечетких ультраграфов, позволяющие в условиях многомерных разреженных данных получать более качественные решения по сравнению с известными подходами. Предложен последовательный локально оптимальный алгоритм разрезания нечетких ультраграфов. 6. Разработаны прикладные программы, осуществляющие генерацию нечетких ультраграфов и реализующие алгоритмы поиска нечетких шарниров в нечетких ультраграфах. Правильность теоретических положений диссертационной работы, эффективность предложенных методов и алгоритмов подтверждаются результатами вычислительного эксперимента с использованием наборов данных из специализированного репозитория больших наборов данных.
Похожие диссертации на Разработка и исследование методов и алгоритмов для моделирования адаптивных веб-ресурсов на основе нечетких ультраграфов
