автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Разработка и исследование методов и алгоритмов для моделирования адаптивных веб-ресурсов на основе нечетких ультраграфов

На правах рукописи

ЦЕЛЫХ Алексей Александрович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ И АЛГОРИТМОВ ДЛЯ МОДЕЛИРОВАНИЯ АДАПТИВНЫХ ВЕБ-РЕСУРСОВ НА ОСНОВЕ НЕЧЕТКИХ УЛЬТРАГРАФОВ

Специальность 05.13.17 - Теоретические основы информатики

Автореферат

* диссертации на соискание ученой степени

кандидата технических наук

Таганрог - 2005

Работа выполнена на кафедре прикладной информатики Таганрогского государственного радиотехнического университета

Научный руководитель •

доктор технических наук, профессор, заслуженный деятель науки и техники РФ БЕРШТЕЙН Леонид Самойлович

Официальные оппоненты:

доктор технических наук, профессор ФИНАЕВ Валерий Иванович доктор технических наук, профессор КАРЕЛИН Владимир Петрович

Ведущая организация: Ростовский государственный университет

Защита состоится 23 июня 2005 г. в 14.20 на заседании диссертационного совета Д 212.259.02 по защите диссертаций на соискание учёной степени доктора технических наук в Таганрогском государственном радиотехническом университете по адресу: 347928, Таганрог, ГСП-17а, пер. Некрасовский, 44, ауд.

Д-406.

С диссертацией можно ознакомиться в библиотеке университета.

«

Автореферат разослан 21 мая 2005 г.

Учёный секретарь диссертационного совета д.т.н., профессор

Бабенко Л.К.

МП*/*

3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Бурное развитие информационных технологий и интернет-ресурсов обусловило появление информационных систем, охватывающих интересы большого неоднородного коллектива пользователей. У непрофессиональных почьзователей, как правило, не возникает стремления изучить более или менее спожный язык запросов. Интенсивное обучение его применению не представляется возможным еще и потому, что у пользователей различные цели, интересы и неодинаковая образовательная подготовка.

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

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

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

Теоретические и практические предпосылки настоящего исследования составили фундаментальные и прикладные работы ученых в следующих областях:

• человеко-машинные и ориентированные на пользователя информационные системы (Д.А. Поспелов, В.Г. Захаревич, П. Брусиловский, Б. Мобашер);

. представление и использования знаний и данных (М Минский, X. Уэно), в том числе нечеткоопределенных (Л.А. Заде, Л.С. Берштейн, А В Бо-женюк, А. Кофман, А.Н. Мелихов, Н.Е. Сергеев, Э.А. Трахтенгерц, P.P. Ягер);

. представление структур данных и знаний с помощью графов, гиперграфов и ультраграфов (Л.С. Берштейн. А. Ахо, К. Берж, Р.Х. Гётчел, A.A. Зыков, Н. Кристофидес, О. Ор.е, М. Свами, У. Татт, Д. Хопкрофт);

. методы интеллектуального анализа данных (Р. Агравал, М. Вонг, А. Гинезей, В.А. Дюк).

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

Поставленная цель определяет следующие основные задачи диссертационного исследования:

¡.Выявление особенностей, характерных для рассматриваемою класса задач персонализации, и выбор адекватного подхода к разработке методов их решения.

2. Разработка концепции и методики создания адаптивной интеллектуальной информационно-советующей системы для решения задач персонализации в интернете.

3. Проведение исследований по изучению, разработке и теоретическому обоснованию формальных математических моделей и методов отображения структуры адаптивного веб-ресурса, представленного нечеткими фреймами, в нечеткие ультраграфы.

4. Разработка и исследование методов оценки и классификации информационных потоков в интернете на основе нечетких гиперграфовых и ультраграфовых моделей.

5. Исследование структурных свойств нечетких ультраграфов с позиции нечетких соответствий. Определение понятий нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах.

6. Разработка и исследование методов и алгоритмов определения живучести нечетких ультраграфов на основе выделения нечетких шарниров.

7. Разработка методов и алгоритмов поиска нечетких ассоциативных правил на основе выделения всех биклик (максимальных полных двудольных подграфов) и нахождения всех максимальных паросочетаний в нечетком ультраграфе.

* *

8. Разработка методов и алгоритмов кластеризации нечетких ассоциативных правил на основе автокомпозиции и разрезания нечетких ультраграфов.

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

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

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

2. Впервые введены понятия и исследованы свойства нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах.

3. Разработаны методы и алгоритмы определения живучести нечетких ультраграфов на основе выделения нечетких шарниров в нечетких ультраграфах.

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

5. Разработаны методы и алгоритмы кластеризации нечетких ассоциативных правил на основе разрезания нечетких ультраграфов.

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

1. Разработанные теоретические положения, методы и алгоритмы использованы при создании систем поддержки принятия решений, предназначенных для решения задач персонализации в интернете.

2. Разработанная концепция создания адаптивной интеллектуальной информационно-советующей системы использована при проектировании модуля персонализации веб-контента и организации динамической навигации по сайтам электронной коммерции.

3. Разработанные методы и алгоритмы выделения нечетких шарниров в нечетких ультраграфах использованы при создании комплекса проблемно-ориентированных прикладных программ.

4. Разработанные методы и алгоритмы поиска и кластеризации нечетких ассоциативных правил использованы при создании информационного портала, обеспечивающего индивидуальный подход к посетителям.

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

ем вычислительных экспериментов на ЭВМ, результатами практического использования предложенных в диссертации моделей, методов и алгоритмов, подтвержденного актами и справками об их внедрении, а также апробацией работы на региональных, всероссийских и международных конференциях.

Реализация результатов работы. Диссертация выполнена в соответствии с основным направлением научно-исследовательской работы Таганрогского государственного радиотехнического университета «Формальные системы, искусственный интеллект и системы принятия решений».

Основные результаты диссертационной работы использованы и внедрены при выполнении научных проектов и научно-исследовательских работ, в том числе:

. при выполнении научного проекта Российского Фонда Фундаментальных Исследований (грант РФФИ 03-01-06498 MAC) по теме: «Разработка и развитие теории нечетких гиперграфов и их применение в качестве адекватных моделей сложных систем, работающих в условиях частичной неопределенности», проводимого в 2003 г.;

. при выполнении госбюджетной НИР №15551 «Разработка теории, моделей и методов принятия решений в интегрированных интеллектуальных системах на основе нечетких знаний и смешанного представления атрибутов», выполняемой на кафедре прикладной информатики ТРТУ в 2001-2004 г.г.;

. при разработке модуля персонализации веб-контента и организации динамической навигации по сайтам компании «Мезон.ру» (г.Санкт-Петербург), предоставляющим пользователям возможности поиска релевантных товаров в интернет-магазинах в 2000-2004 г.г.;

. при создании дилерского портала Южной Софтверной Компании «ЮСК: Дистрибьюция» (г.Ростов-на-Дону), обеспечивающего индивидуальный подход к пользователям с целью организации эффективной маркетинговой и информационно-технической поддержки партнеров по дистрибуции ПО в 20042005 г.г.

Внедрение и использование результатов диссертационной работы подтверждаются соответствующими актами и справками.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на П-м Международном научно-практическом семинаре "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2003 г.); Всероссийской научной конференции "Управление и информационные технологии УИТ-2003" (Санкт-Петербург, 2003 г.); международных научно-технических конференциях и молодежных научных конференциях "Интеллектуальные САПР" (Геленджик, 1999-2004 г.г.); Третьем Всероссийском симпозиуме по прикладной и промышленной математике (Со-

шш

1

чи, 2002 г.); Научной сессии МИФИ-2001 "Банки данных. Интеллектуальные системы. Программное обеспечение" (Москва, 2001 г.); 3-й Международной научно-технической конференции "Интерактивные системы ИС-99" (Ульяновск, 1999 г.); И, V, VI, XI международных научно-технических конференциях "Математические методы и информационные технологии в экономике, социологии и образовании" (Пенза, 1999-2003 г.г.); II Всероссийской научно-практической конференции "Проблемы информатики в образовании, управлении, экономике и технике" (Пенза, 2002 г.); IV Международной научно-технической конференции "Логико-математические методы в технике, экономике и социологии " (Пенза, 1999 г.); IV, V, VI Всероссийских научных конференциях студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (Таганрог, 1998, 2000, 2002 г.г.); III Межгосударственной научно-практической конференции "Экономико-организационные проблемы проектирования и применения информационных систем" (Ростов-на-Дону, 1999 г.); 4-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов "Новые информационные технологии в научных исследованиях и в образовании" (Рязань, 1999 г.); I Всероссийской научной конференции молодых ученых и аспирантов "Новые информационные технологии. Разработка и аспекта применения" (Таганрог, 1998 г.); на ежегодных научно-технических конференциях профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ.

Публикации. Результаты диссертации отражены в 14 печатных работах.

Структура и объем работы. Диссертационная работа состоит из введения, 3 основных глав, заключения, списка использованной литературы из 107 наименований и 3 приложений. Объем диссертации - 130 страниц, 19 рисунков, 6 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

На основе методов информационного поиска введена количественная оценка эффективности выдаваемых системой рекомендаций. Будем рассматривать транзакцию в качестве целевой, а подмножество этой сессии ^ в качестве незавершенной сессии. Можно предположить, что рекомендации предска-

*

зывают транзакцию. Пусть г, = ^ - - набор страниц веб-ресурса в рекомендации, за исключением тех, которые уже входят в текущую подсессию, а *

¿'у = -sJ - набор страниц в транзакции, за исключением тех, которые уже входят в текущую подсессию.

Параметры точности и полноты рекомендаций определяются выражениями

• * У^0».' с*

¿и к Г ¡к Э1к _ к г )к Д ¡к

Во второй главе рассмотрены методы оценки и классификации информационных потоков в интернете на основе использования нечетких графовых и гиперграфовых моделей для построения систем поддержки принятия решений в задачах персонализации.

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

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

На втором этапе при анализе свойств нечетких гиперграфов решается задача оптимизации действий сторон путем выявления пользователей, одновременно входящих в классы предпочтения разных поставщиков информации.

Решение этой задачи сводится к выявлению минимальных реберных покрытий 2' с2 в нечетком гиперграфе Н = , для которых справедливо

(V*, еХ)(?т(х,))*0, =

Исследованы основные свойства нечетких гиперграфов относительно минимального реберного нечеткого покрытия, предложен эвристический алгоритм нахождения минимального реберного нечеткого покрытия.

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

Каждой вершине х нечеткого ориентированного графа О = (Х,и) поставим в соответствие некоторый параметр Ух. Каждая нечеткая дуга графа </ли < х1,х] >/ <xI,xJ », соединяющая вершину х1 с вершиной х], определяет влияние параметра К, на параметр V с силой Ни <хчх1>, приписанной ребру.

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

С целью ранжирования критериев предложен метод выделения нечетких баз В, таких минимальных подмножеств вершин, из которых нечетко достижимы все вершины нечеткого графа б = (X, II).

Можно считать, что критерии, представленные нечеткой базой, имеют больший вес, чем остальные. Все прочие вершины графа конденсации ранжируются в зависимости от степени достижимости вершины х} из вершины х,вВ, определяемой выражением

у(х„х) = тах(//(4 (х,, х)), а = 1,2,..п,

СС

где Ьа - различные кратчайшие ориентированные пути из х, в х/.

В третьей главе рассмотрены методы проектирования адаптивных веб-ресурсов на основе использования нечетких ультраграфовых моделей как обобщения понятий нечеткого гиперграфа и нечеткого ориентированного графа.

Нечетким ультраграфом Н = (Х,и,ГЛ) будем называть четверку, состоящую из двух множеств X, и и двух нечетких соответствий Г = (Х,и,Р), А = (и, X, Р). Элементы множества X условимся называть вершинами, а элементы множества и - ребрами нечеткого ультраграфа.

Эквивалентным способом задания нечеткого ультраграфа является пара нечетких матриц инцидентности Ан -¡¡«^|, Вн = где а0=/ит <х,,и1 >, Ър =Мь <иу,х, >.

Структурные свойства нечетких ультраграфов исследованы с позиции нечетких соответствий. В нечетком ультраграфе Н композиция нечетких функциональных (инъективных, всюду определенных, сюръективных, биективных) соответствий нечетко функциональна (инъективна, всюду определена, сюръективна, биективна).

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

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

Вершина хеХ является нечетким полушарниром в нечетком ультраграфе, если удаление ее и инцидентных ей дуг уменьшает степень достижимости у {у, 2) между некоторыми вершинами у иг, х^ у. Все нечеткие маршруты, соединяющие вершины из различных компонент связности, обязательно проходят через нечеткий полушарнир.

Дуга и е ¡7 является нечетким полумостом, если ее удаление уменьшает степень достижимости у{у,~) между некоторыми вершинами у и г, не инцидентными данной дуге.

Теорема Пусть - степень достижимости вершины х ] из х, по-

сле удаления дуги и ] =< /иг, (хпх^1 < х!, х] » .

Следующие высказывания эквиваленты:

а) и} =< ци{хх,х}~)1 < х„х} » - нечеткий полумост;

б) <//„(*„*,);

в) не является дугой с минимальной конъюнктивной прочностью в каком-либо цикле.

Теорема. Если вершина инцидентна двум нечетким полумостам, то она является нечетким полушарниром.

Теорема Если </ии{х,у)/<х,у » - нечеткий полумост, то степень достижимости у(х, у) вершины у из вершины х равна степени инцидентности

Вершина х&Х является нечетким шарниром в нечетком ультраграфе, если удаление ее и инцидентных ей дуг уменьшает степень взаимной достижимости в(у,г) между некоторыми вершинами у иг, х*уФг. Другими словами, удаление нечеткого шарнира приводит к увеличению числа компонент нечеткой сильной связности.

Нечеткий шарнир характеризуется степенью нечеткости а - значением, при котором в ультраграфе На вершина хеХ становится шарниром.

Из определения нечеткого шарнира следует, что вершина у будет нечетким шарниром, с точки зрения вершины х, если ее удаление разорвет в ультраграфе На каждый элементарный цикл, которому принадлежит х. Иными словами, если вершина у принадлежит каждому циклу, в который входит х.

Исходя из этого, запишем алгоритм нахождения нечетких шарнирор в нечетком ультраграфе:

1. Зададим однозначное представление нечеткого ультраграфа нечетким вершинным графом Х(Н).

2. Выбирая все различные степени инцидентности ¡л{х,>х,) в Х{Н), проранжируем их и запишем последовательность 0 <ап <... < а, = к(Х(Н)).

3. Применим к вершинам графа правило нулевой полустепени.

4. Найдем все элементарные циклы в графе (Я):

Шаг 4 1 Инициализация Для каждой вершины v, S(v) = О Для каждой дуги а, S(a):= 0. Текущий путь TT-void.

Шаг 4 2 Выбрать вершину v такую, что S(v) = 0; ЕСЛИ таких вершин нет, ТО переходим к шагу 4 6 7T:={v}, S(v)-1.

IUap 4 3 Выбрать дугу а, выходящую из последней вершины ТТ, ПВершина(ТТ) такую, что S(a) = 0; ЕСЛИ таких дуг нет, ТО S(TlBepuima(TT)) = 2, удаляем ПВершина(ТТ) из ТТ и переходим к шагу 4 5 Добавляем дугу а в текущий путь ТТ = ТТ_а, S(y) = 2 Шаг 4 4 v = КонецДуги(а)

ЕСЛИ S(v)-0, ТО добавляем вершину v в текущий путь TT=TT_v, S(v) = 1, переходим к шагу 4.3.

ЕСЛИ S(v) = 1, ТО заносим найденный цикл v_Xeocm(TT,v)_v в список элементарных циклов графа и переходим к шагу 4.5.

(В случае, когда S(v) = 2) Рекур = 0; вызываем подпрограмму Конкатена-иия(у).

Шаг 4.5 Удаляем последнюю дугу из ТТ. ЕСЛИ ТТ пустой, ТО переходим к шагу 4.2, ИНА ЧЕ к шагу 4.3.

Шаг 4 6 Конец работы процедуры.

5. Присвоим шарнирам графа Ха^Н) степень нечеткости а.

6. Положим п-п-1, и если я > 1, то перейдем к п.З. В противном случае -

к п.7.

7. Конец работы алгоритма.

Алгоритм нахождения нечетких шарниров и генератор нечетких ультраграфов реализованы в виде программ на языке Си++.

Предложен алгоритм нахождения нечетких шарниров в нечетких гиперграфах на основе разложения на а -уровни и метода поиска в глубину.

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

Рассмотрим множество нечетких транзакций, заданных в виде таблицы. Столбцы и строки помечаются идентификаторами элементов / и транзакций

Т , соответственно. На пересечении /-го столбца и j-й строки содержится зна-

чение на интервале [0,1], степень принадлежности Цт-(.х,) элемента х1 нечеткой транзакции т,.

Степень принадлежности набора элементов /0 с / нечеткой транзакции 7] будет определяться выражением

г(/0) = тт(г(х)).

хе!„

Нечетким ассоциативным правилом назовем продукцию вида А => В такую, что А,В с I, А Г) В = 0. А и В являются посылкой и следствием правила, соответственно.

Нечеткая поддержка нечеткого ассоциативного правила А=>В, для которой выполняется свойство антимонотонности, определяется выражением

ЕГК(*.)

М А => В) = МА и В); МА) = -

Нечеткая уверенность для нечеткого ассоциативного правила А=>В, А = {.г,}, Д = {.у,} определяется выражением

ЕПа^К,^/)

=> В) = ^-

г;еГ /

Задача поиска всех частовстречающихся наборов элементов для извлечения нечетких ассоциативных правил адекватна задаче выделения всех биклик (максимальных полных двудольных подграфов) в нечетком двудольном графе. Указанная задача решается нахождением всех максимальных внутренне устойчивых множеств в дополнительном двудольном графе.

В развитие метода чередующихся цепей для нечетких ультраграфов разработан алгоритм выделения всех максимальных паросочетаний в нечетком ультраграфе.

Аугментальный вес увеличивающего нечеткого маршрута будем определять выражением

™(1Ли],*,)) = МХ0.Й {и],х1))-м?(1~ (х1,и ])),

где К-^у.д/(",>*/)) - арифметическая сумма весов свободных ребер пути, "и-'П^ (х[, и 1)) - арифметическая сумма весов ребер паросочетания.

Теорема Пусть М - паросочетание с минимальным весом среди паросо-четаний мощности |л/| в нечетком ультраграфе Н, Ьтт - увеличивающий путь

с минимальным аугментальным весом, а М' = М ® 1.„т - новое паросочетание, полученное на основе £„,„. Тогда М' будет иметь минимальный вес среди па-росочетаний размерности \м\ +1.

Страницы

* х4 **

1 0,7 1 0,8 0,6

а в 2 0,4 0,5 0,7

я 3 0,4 0,6 1 1

а а Е- 4 0,5 0,9 0,7 0,6

5 1 0,5 1 0,4 0,8

6 1 1 1

Задача поиска всех нечастовстречающихся наборов элементов адекватна нахождению минимальных нечетких трансверсалей в нечетком гиперграфе

Нечеткой трансверсалью, или нечетким вершинным покрытием, нечеткого гиперграфа Н = (Х,1/) будем называть нечеткое подмножество вершин Т с X, для которого справедливо О/и, еи)(Т г\и1 #0), при этом

М*)= V и (х).

«,<1! '

Разработаны методы поиска минимальных нечетких трансверсалей в нечетком гиперграфе как обобщение метода Магу для четких графов и на основе разложения нечеткого гиперграфа на множество гиперграфов а -уровня.

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

В результате прямой автокомпозиции нечеткого ультраграфа получим нечеткий граф Ох - (X, IV), представляющий собой нечеткое отношение на множестве вершин ультраграфа.

Пусть значение функции принадлежности Hf(,p-p*) = Hw определяется выражением

»*/»)=&, цПР)(ха,и)<* Ицр'М^р), xa,xfieX_

Граф Gx = (X,W) представляет собой нечеткое отношение нечеткого равенства вершин. Выделение семейства ¿-нечетких клик позволяет осуществить группирование вершин нечеткого ультраграфа в классы, нечетко эквивалентные со степенью эквивалентности не меньшей t.

Разработан последовательный локально оптимальный алгоритм разрезания нечеткого ультраграфа, разбивающий множество X на классы Х„, а с А = {l,2, .Д} с оптимизацией (минимизацией значения) целевой функции, характеризующей число разрывов нечетких дуг нечеткого ультраграфа.

Экспериментальная оценка произведена на основе данных о посещениях сайта Microsoft из специализированного репозитория больших наборов данных. Зависимости параметров точности и полноты рекомендаций от выбранного порога рекомендаций при различной глубине окна текущей подсессии представлены на рисунке.

В заключении перечислены основные результаты работы.

В приложении 1 представлены акты о внедрении и справки об использовании результатов работы.

В приложении 2 приведен листинг программного кода, реализующего генерацию нечетких ультраграфов.

В приложении 3 приведены диаграмма иМЬ и листинг программного кода, реализующего поиск нечетких шарниров в нечетких ультраграфов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В ходе проведенных исследований получены следующие основные научные результаты:

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

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

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

4. Разработаны методы и алгоритмы поиска нечетких ассоциативных правил на основе выделения всех максимальных полных двудольных подграфов и нахождения всех максимальных паросочетаний в нечетких ультраграфах. Обобщены методы и алгоритмы нахождения нечеткого гиперграфа трансверса-лей. При работе с базами данных с большим числом нечетких транзакций предложенный подход характеризуется более высокой производительностью в сравнении с традиционными алгоритмами Арпоп.

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

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

Основные положения диссертационной работы отражены в следующих публикациях:

1. Целых A.A. Формирование оптимальных информационных потоков в сети Интернет при нечетких запросах пользователей // Известия ТРТУ. Тематический выпуск: Интеллектуальные САПР. Таганрог: ТРТУ, 1999, №3(13). С.33-36.

2. Целых A.A. Методы персонализации процессов взаимодействия сторон в электронной коммерции на основе кластеризации // Известия ТРТУ. Тематический выпуск: Интеллектуальные САПР. Таганрог: ТРТУ, 2000, №2(16). С.73-75.

3. Целых A.A. Выделение нечетких шарниров в нечетких ориентированных гиперграфах второго рода // Известия ТРТУ. Тематический выпуск: Проектирование и моделирование интеллектуальных систем. - Таганрог: ТРТУ, 2004, №4. С.250-251.

4. Дикарев С.Б., Целых A.A. Некоторые подходы к проектированию адаптивных систем // Перспективные Информационные Технологии и Системы. №1(21), 2005. С.11-23.

5. Целых A.A. Методы нахождения нечеткого гиперграфа трансверсалей // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник трудов И-го Международного научно-практического семинара. - М.: Физматлит, 2003. С.137-140.

6. Целых A.A. Метод нахождения нечеткого гиперграфа трансверсалей на основе разложения на гиперграфы д-у ровня // Математические методы и информационные технологии в экономике, социологии и образовании: сборник материалов XI Международной научно-технической конференции. - Пенза. 2003. С.265-268.

7. Целых A.A. Нечеткая гиперграфовая модель кластеризации для автоматической персонализации в электронной торговле // Обозрение прикладной и промышленной математики. - М.: ОПиПМ, 2002. С.483.

8. Целых A.A. К решению задач интеллектуального анализа данных на нечетких гиперграфах // Проблемы информатики в образовании, управлении, экономике и технике: сборник материалов II Всероссийбкой научно-практической конференции. - Пенза, 2002. С.27-30.

9. Целых A.A. Использование методов нечеткой кластеризации в электронной коммерции для учета индивидуальных запросов покупателей // Техническая кибернетика, радиоэлектроника и системы управления. Тезисы докладов V Всероссийской научной конференции студентов и аспирантов. - Таганрог, 2000. С.284-285.

10. Целых A.A. Моделирование поведения участников рынка информационных услуг в интернете на основе выявления минимальных покрытий нечеткого гиперграфа // Математические методы и информационные технологии в экономике: сборник материалов V Международной научно-технической конференции. 4.1. - Пенза, 2000. С.80-82.

11. Tselykh A. Analysis of Information Streams Represented with Fuzzy Hyper-graphs // Интерактивные системы ИС-99. Материалы 3-й Международной научно-технической конференции. - Ульяновск, 1999. С.69-70.

12. Tselykh A. The Account of Indeterminacy in Socio-economic Systems on the Market of Information Services // Логико-математические методы в технике, экономике и социологии: сборник материалов IV Международной научно-технической конференции. - Пенза, 1999. С.89-90.

13. Целых A.A. Методы формирования классов нечеткого предпочтения на рынке информационных услуг // Новые информационные технологии в научных исследованиях и в образовании Материалы 4-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов. - Рязань, 1999. С.10-11.

14. Целых A.A. Технология работы виртуального магазина // Новые информационные технологии. Разработка и аспекты применения. Тезисы докладов I Всероссийской научной конференции молодых ученых и аспирантов. - Таганрог, 1998. С.138-140.

В работе [4], опубликованной в соавторстве, личный вклад автора состоит в разработке методов интеллектуального анализа данных для описания модели пользователя на основе нечетких гиперграфов и ультраграфов.

Соискатель

A.A. Целых

»

г Таганрог, типография ТРТУ заказ Хе fvß, тираж 100 экз , 2005 г

ганро]

»11537

РНБ Русский фонд

2006-4 7922

Введение

Глава 1. Разработка математических методов персонализации на основе исследования моделей адаптивных веб-ресурсов

1.1. Математические модели и методы персонализации в интернете 15 4 1.1.1. Модели информационного поиска

1.1.2. Методы совместной фильтрации

1.1.3. Методы интеллектуального анализа данных

1.1.3.1. Метод кластеризации транзакций и обращений к веб-ресурсу

1.1.3.2. Метод выдачи рекомендаций на основе нечеткого композиционного правила вывода

1.2. Разработка математической модели и методов проектирования адаптивных веб-ресурсов

1.2.1. Исследование адаптивных систем

1.2.2. Методы и технические приемы адаптивной гипермедиа

1.2.3. Модель адаптивного веб-ресурса

1.2.4. Модель пользователя

1.3. Выводы по первой главе

Глава 2. Использование нечетких графовых моделей для построения системы поддержки принятия решений в задачах персонализации

2.1. Метод оценки и классификации информационных потоков на основе нечеткой гиперграфовой модели

2.2. Метод определения набора критериев для системы поддержки принятия решений с многокритериальным выбором альтернатив

2.3. Выводы по второй главе

Глава 3. Разработка методов проектирования адаптивных веб-ресурсов на основе нечетких ультраграфовых моделей

3.1. Разработка теории и исследование нечетких ультраграфовых моделей

3.1.1. Определение и способы задания нечетких ультраграфов

3.1.2. Исследование нечетких ультраграфов с позиции нечетких соответствий

3.1.3. Связность и достижимость в нечетких ультраграфах

3.2. Метод определения живучести нечетких ультраграфов

3.2.1. Нечеткие полушарниры, шарниры и мосты в нечетких ультраграфах

3.2.2. Алгоритм поиска нечетких шарниров в нечетких ультраграфах

3.2.3. Алгоритм поиска нечетких шарниров в нечетких гиперграфах

3.3. Методы поиска нечетких ассоциативных правил на основе нечетких ультраграфов

3.3.1. Нечеткие транзакции и нечеткие ассоциативные правила

3.3.2. Паросочетания и покрытия в нечетком ультраграфе

3.3.3. Алгоритм поиска максимальных паросочетаний в нечетком ультраграфе

3.3.4. Методы поиска минимальных нечетких трансверсалей в нечетком гиперграфе

3.4. Методы кластеризации ассоциативных правил на основе нечетких ультраграфов

3.4.1. Метод кластеризации на основе автокомпозиции нечетких ультраграфов

3.4.2. Метод кластеризации на основе разрезания нечетких ультраграфов

3.5. Экспериментальная оценка эффективности адаптивного поиска

3.6. Выводы по третьей главе

Актуальность темы. Бурное развитие информационных технологий и Всемирной Паутины обусловило появление информационных систем, охватывающих интересы большого неоднородного коллектива пользователей. У непрофессиональных пользователей, как правило, не возникает стремления - особенно если у них нет времени - изучить более или менее сложный язык запросов. Интенсивное обучение применению языка запросов не представляется возможным еще и потому, что у пользователей различные цели, интересы и неодинаковая образовательная подготовка.

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

В настоящее время отслеживание поведения и предпочтений потребителей, а также взаимодействие с ними в реальном времени с помощью технологий персонализации, является одним из ключевых элементов работы с пользователями через интернет, беспроводные устройства и интерактивное телевидение. По данным исследования Forrester Research, лишь 13% веб-ресурсов содержат элементы персонализации, между тем, на них совершается 68% всех покупок в интернете. Согласно результатам исследования Evans Data Corporation, в котором участвовало более 800 производителей программного обеспечения из США и Канады, в ближайшие год-два экспоненциально растущим спросом будет пользоваться разработка решений в области персонализации. К 2006 году инвестиции в технологии персонализации составят 2,1 миллиарда долларов, и их разработка будет доминирующим направлением в развитии приложений для интернета.

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

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

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

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

Теоретические и практические предпосылки настоящего исследования составили фундаментальные и прикладные работы ученых в следующих областях:

• человеко-машинные и ориентированные на пользователя информационные системы (П. Брусиловский, В.Г. Захаревич, Б. Мобашер, Д.А. Поспелов);

• представление и использования знаний и данных (М. Минский, X. Уэно), в том числе нечеткоопределенных (JI.A. Заде, JI.C. Берштейн, A.B. Боженюк, А. Кофман, А.Н. Мелихов, Н.Е. Сергеев, Э.А. Трахтенгерц, P.P. Ягер);

• представление структур данных и знаний с помощью графов, гиперграфов и ультраграфов (JI.C. Берштейн, А. Ахо, К. Берж, Р.Х. Гётчел, A.A. Зыков, Н. Кристофидес, О. Ope, M. Свами, У. Татт, Д. Хопкрофт);

• методы интеллектуального анализа данных (Р. Агравал, М. Вонг, А. Гинезей, В.А. Дюк).

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

Поставленная цель определяет следующие основные задачи диссертационного исследования:

1. Выявление особенностей, характерных для рассматриваемого класса задач персонализации, и выбор адекватного подхода к разработке методов их решения.

2. Разработка концепции и методики создания адаптивной интеллектуальной информационно-советующей системы для решения задач персонализации в интернете.

3. Проведение исследований по изучению, разработке и теоретическому обоснованию формальных математических моделей и методов отображения структуры адаптивного веб-ресурса, представленного нечеткими фреймами, в нечеткие ультраграфы.

4. Разработка и исследование методов оценки и классификации информационных потоков в интернете на основе нечетких гиперграфовых и ультраграфовых моделей.

5. Исследование структурных свойств нечетких ультраграфов с позиции нечетких соответствий. Определение понятий нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах.

6. Разработка и исследование методов и алгоритмов определения живучести нечетких ультраграфов на основе выделения нечетких шарниров.

7. Разработка методов и алгоритмов поиска нечетких ассоциативных правил на основе выделения всех биклик (максимальных полных двудольных подграфов) и нахождения всех максимальных паросочетаний в нечетком ультраграфе.

8. Разработка методов и алгоритмов кластеризации нечетких ассоциативных правил на основе автокомпозиции и разрезания нечетких ультраграфов.

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

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

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

2. Впервые введены понятия и исследованы свойства нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах.

3. Разработаны методы и алгоритмы определения живучести нечетких ультраграфов на основе выделения нечетких шарниров в нечетких ультраграфах.

4. Разработаны методы и алгоритмы поиска нечетких ассоциативных правил на основе выделения всех биклик и нахождения всех максимальных паросочетаний в нечетких ультраграфах.

5. Разработаны методы и алгоритмы кластеризации нечетких ассоциативных правил на основе разрезания нечетких ультраграфов.

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

1. Разработанные теоретические положения, методы и алгоритмы использованы при создании систем поддержки принятия решений, предназначенных для решения задач персонализации в интернете.

2. Разработанная концепция создания адаптивной интеллектуальной информационно-советующей системы использована при проектировании модуля персонализации веб-контента и организации динамической навигации по сайтам электронной коммерции.

3. Разработанные методы и алгоритмы выделения нечетких шарниров в нечетких ультраграфах использованы при создании комплекса проблемно-ориентированных прикладных программ.

4. Разработанные методы и алгоритмы поиска и кластеризации нечетких ассоциативных правил использованы при создании информационного портала, обеспечивающего индивидуальный подход к посетителям.

Достоверность полученных в диссертации результатов подтверждается математическими и аналитическими доказательствами и оценками, проведением вычислительных экспериментов на ЭВМ, результатами практического использования предложенных в диссертации моделей, методов и алгоритмов, подтвержденного актами и справками об их внедрении, а также апробацией работы на региональных, всероссийских и международных конференциях.

Реализация результатов работы. Диссертация выполнена в соответствии с основным направлением научно-исследовательской работы Таганрогского государственного радиотехнического университета «Формальные системы, искусственный интеллект и системы принятия решений».

Основные результаты диссертационной работы использованы и внедрены при выполнении научных проектов и научно-исследовательских работ, в том числе:

• при выполнении научного проекта Российского Фонда Фундаментальных Исследований (грант РФФИ 03-01-06498 MAC) по теме: «Разработка и развитие теории нечетких гиперграфов и их применение в качестве адекватных моделей сложных систем, работающих в условиях частичной неопределенности», проводимого в 2003 г.;

• при выполнении госбюджетной НИР №15551 «Разработка теории, моделей и методов принятия решений в интегрированных интеллектуальных системах на основе нечетких знаний и смешанного представления атрибутов», выполняемой на кафедре прикладной информатики ТРТУ в 2001-2004 г.г.;

• при разработке модуля персонализации веб-контента и организации динамической навигации по сайтам компании «Мезон.ру» (г. Санкт-Петербург), предоставляющим пользователям возможности поиска релевантных товаров в интернет-магазинах в 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 Межгосударственной научно-практической конференции "Экономико-организационные проблемы проектирования и применения информационных систем" (Ростов-на-Дону, 1999 г.); 4-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов "Новые информационные технологии в научных исследованиях и в образовании" (Рязань, 1999 г.); I Всероссийской научной конференции молодых ученых и аспирантов "Новые информационные технологии. Разработка и аспекты применения" (Таганрог, 1998 г.); на ежегодных научно-технических конференциях профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ.

Публикации. Результаты диссертации отражены в 14 печатных работах.

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

3.6. Выводы по третьей главе

2. Разработан метод определения живучести нечетких ультраграфов на основе нахождения нечетких шарниров. Впервые введены понятия и исследованы свойства нечетких полушарниров и нечетких шарниров, нечетких полумостов и нечетких мостов в нечетких ультраграфах. Разработан алгоритм нахождения нечетких шарниров в нечетком ультраграфе на основе выделения всех элементарных циклов в нечетком ультраграфе. Алгоритм нахождения нечетких шарниров и генератор нечетких ультраграфов реализованы в виде программы на языке Си++. Предложен эффективный алгоритм нахождения нечетких шарниров в нечетких гиперграфах на основе разложения на а -уровни и метода поиска в глубину.

3. Разработаны методы и алгоритмы поиска нечетких ассоциативных правил. Показано, что задача поиска нечетких ассоциативных правил адекватна задаче выделения всех биклик (максимальных полных двудольных подграфов) в нечетком двудольном графе. Указанная задача решается поиском всех максимальных внутренне устойчивых множеств в дополнительном двудольном графе. В развитие метода чередующихся цепей для нечетких ультраграфов предложен алгоритм выделения всех максимальных паросочетаний в нечетком ультраграфе. Обобщены методы и алгоритмы поиска нечеткого гиперграфа трансверсалей.

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

ЗАКЛЮЧЕНИЕ

В ходе проведенных исследований получены следующие основные научные и практические результаты:

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

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

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

4. Разработаны методы и алгоритмы поиска нечетких ассоциативных правил на основе выделения всех максимальных полных двудольных подграфов и нахождения всех максимальных паросочетаний в нечетких ультраграфах. Обобщены методы и алгоритмы нахождения нечеткого гиперграфа трансверсалей. При работе с базами данных с большим числом нечетких транзакций предложенный подход характеризуется более высокой производительностью в сравнении с традиционными алгоритмами Арпоп.

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

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

126

1. Андрейчиков A.B., Андрейчикова О.Н. Интеллектуальные информационные системы. - М.: Финансы и статистика, 2004.

2. Астанин C.B., Берштейн Л.С., Захаревич В.Г. Проектирование интеллектуального интерфейса "человек-машина". Ростов н/Д.: Издательство РГУ, 1990. 118 с.

3. Астанин C.B., Захаревич В.Г. Обработка и представление знаний в информационно-советующих комплексах систем гибридного интеллекта. Таганрог: ТРТУ, 1997. 136 с.

4. Балабанов И.Т. Электронная коммерция. СПб: Питер, 2001.

5. Беллман Р., Заде Л.А. Принятие решений в расплывчатых условиях./ Вопросы анализа и процедуры принятия решений. М.: Мир, 1976. С.172-215.

6. Богданова Е.Л. Информационный маркетинг. Учебное пособие. СПб: Альфа, 2000.

7. Борисов А.Н., Алексеев A.B., Меркурьева Г.В. и др. Обработка нечеткой информации в системах принятия решений.- М.: Радио и связь, 1989. 304 с.

8. Борисов А.Н., Крумберг O.A., Федоров И.П. Принятие решений на основе нечетких моделей: Примеры использования.- Рига: Зинатне, 1990. 184 с.

9. Боэм Б.У. Инженерное проектирование программного обеспе-чения. М.: Радио и связь, 1995. 512 с.

10. Ю.Гафт М.Г. Принятие решений при многих критериях. М.: Знание, 1979.

11. П.Гембл П., Стоун М., Вудкок Н. Маркетинг взаимоотношений с потребителями. М.: Гранд, 2002.

12. Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи. М.: Мир, 1982. 416 с.

13. Джерк Н. Разработка приложений для электронной коммерции. М.: СПб: Питер, 2001.

14. Дикарев С.Б., Целых A.A. Некоторые подходы к проектированию адаптивных систем. // Перспективные Информационные Технологии и Системы, №1(21), 2005. С. 11-23.

15. Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике: Пер. с франц.- М.: Радио и связь, 1990. 288 с.

16. Дюк В., Самойленко A. Data Mining: учебный курс. СПб: Питер, 2001.

17. Евланов Л.Г. Теория и практика принятия решений / Редколлегия М. Сергеев и др. М.: Экономика, 1984. 176 с.

18. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. и др. Лекции по теории графов. М.: Наука, 1990.

19. Енюков И.С., Ретинская И.В., Скуратов А.К. Статистический анализ и мониторинг научно-образовательных Интернет-сетей. М.: Финансы и статистика, 2004.

20. Заде Л.А. Основы нового подхода к анализу сложных систем и процессов принятия решений / Математика сегодня. М.: Знание, 1974. С. 5-49.

21. Заде Л.А. Понятие лингвистической переменной и его применение к принятию приближенных решений.- М.: Мир, 1976. 168 с.

22. Заде Л.А. Размытые множества и их применение в распознавании образов и кластер-анализе. В кн.: Классификация и кластер. М.: Мир, 1980. С.208-247.

23. Зыков А. А. Гиперграфы. Успехи математических наук, 1974, N6, с.89-154.24.3ыков А. А. Основы теории графов. М.: Наука, 1987. 384 с.

24. Иванов Б.И. Дискретная математика. Алгоритмы и программы. М.: Лаборатория Базовых Знаний, 2001.

25. Кини P.J1., Райфа X. Принятие решений при многих критериях: Предпочтения и замещения. М.: Радио и связь, 1981. 560 с.

26. Козье Д. Электронная коммерция. М.: Русская редакция, 1999.

27. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368 с.

28. Котлер Ф. Маркетинг в третьем тысячелетии: Как создать, завоевать и удержать рынок. М.: ACT, 2001.

29. Кофман А. Введение в прикладную комбинаторику. М.: Наука, Гл. ред. физ.-мат. лит., 1975. 480 с.

30. Кофман А. Введение в теорию нечетких множеств.- М.:Радио и связь, 1982,- 432 с.

31. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.

32. Кузин Л.Т. Основы кибернетики. Т.2. Основы кибернетических моделей. Учеб.пособие для вузов. М.: Энергия, 1979. 584 с.

33. Лантон И. Маркетинг по базам данных. Минск: Амалфея, 1998.

34. Ларичев О.И. Человеко-машинные процедуры принятия решений (обзор). // Автоматика и телемеханика, 1971, № 12.

35. Ларичев О.И., Мошкович Е.М. Качественные методы принятиярешений. М: Наука. Физматлит.1996.

36. Люгер Д. Искусственный интеллект: Стратегии и методы решения сложных проблем. М.: Вильяме, 2003.

37. Малышев Н.Г., Берштейн Л.С., Боженюк Л.Г. Нечеткие модели для экспертных систем в САПР. М.: Энергоатомиздат, 1991.

38. Мелихов А.Н, Берштейн Л.С. Конечные четкие и расплывчатые множества. Часть 1. Четкие множества. Таганрог: ТРТИ, 1980.

39. Мелихов А.Н, Берштейн Л.С. Конечные четкие и расплывчатые множества. Часть 2. Расплывчатые множества. Таганрог: ТРТИ, 1981.

40. Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: Изд-во РГУ, 1981.

41. Мелихов А.Н., Берштейн JI.C., Коровин С.Я. Ситуационные советующие системы с нечеткой логикой. М.: Наука, 1990.

42. Мелихов А.Н., Карелин В.П. Методы распознавания изоморфизма и изоморфного вложения четких и нечетких графов. Учебное пособие. Таганрог. ТРТУ, 1995.

43. Мец К. Инструменты персонализации: Web по индивидуальному заказу // PC Magazine/RE. 2000. - №10.

44. Минский М. Фреймы для представления знаний. М.: Прогресс, 1975.

45. Миркин Б.Г. Проблема группового выбора. М.: Наука, 1974.

46. Москвинова Г.И. Дискретная математика. Математика для менеджера. М.: Логос, 2000.

47. Некрестьянов И.С. Тематико-ориентированные методы информационного поиска. СПб: СПГУ, 2000.

48. Нечепуренко М.И., Попков В.К., Майнагашев С.М. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. Сиб.отд., 1990.515 с.

49. Нечеткие множества в моделях управления и искусственного интеллекта./Под ред. Д.А. Поспелова.-М.: Наука, 1986. 312 с.

50. Нечеткие множества и теория возможностей. Последние достижения / Под ред. Р. Ягера. М.: Радио и связь, 1986.

51. Нильсон Н. Принципы искусственного интеллекта. М.: Радио и связь, 1985. 373 с.

52. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2000.54.0вчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. М.: МГТУ, 2001.

53. Ope О. Графы и их применение. Новокузнецк: НФМИ, 2000.

54. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. М.: Наука. Гл. ред. физ.-мат. лит., 1981.208 с. 43.

55. Поспелов Д.А. Ситуационное управление: теория и практика. М.: Гл.ред.физ.-мат. лит., 1986.- 288 с.

56. Постама П. Новая эра маркетинга. СПб.: Питер, 2002.

57. Прикладные нечёткие системы / Под ред. Т.Тэрано, К.Асаи, М. Оугэ-но.: Пер. с яп.- М.: Мир, 1993.

58. Реброва М.П. Автоматическая классификация в системах обработки информации. Поиск документов. М.: Радио и связь, 1983. 92с.

59. Розен В.В. Цель оптимальность - решение (математические модели принятия оптимальных решений. М.: Радио и связь, 1982. 168 с.

60. Саати Т., Керне К. Аналитическое планирование и организация систем. М. Радио и связь, 1991, 224с.

61. Старостина Т. А. О живучести нечетких графов // Обозрение прикладной и промышленной математики, 2002, т. 9, в. 3, с. 656.

62. Тихомиров Ю.А. Управленческие решения. М.: Наука, 1972.

63. Трахтенгерц Э.А. Субъективность в компьютерной поддержкеуправленческих решений. М.: Синтег, 2001.

64. Ульянов C.B. Нечёткие модели интеллектуальных систем управления: теоретические и прикладные аспекты (обзор) // Техническая кибернетика. 1991, N3, с.3-28.

65. Факторы, влияющие на принятие решений о покупке // Cosmo. 1999.

66. Фомин Г.П. Математические методы и модели в коммерческой деятельности. М.: Финансы и статистика, 2001.

67. Фрэнк Г., Фриш И. Сети, связь и потоки. М.: Связь, 1978.

68. Хэнсон У. Internet-маркетинг. М.: Юнити, 2001.

69. Целых А. А. Выделение нечетких шарниров в нечетких ориентированных гиперграфах второго рода // Известия ТРТУ.

70. Тематический выпуск: Проектирование и моделирование интеллектуальных систем. Таганрог: ТРТУ, 2004, №4. С.250-251

71. Целых A.A. К решению задач интеллектуального анализа данных на нечетких гиперграфах. // Проблемы информатики в образовании, управлении, экономике и технике: сборник материалов II Всероссийской научно-практической конференции. Пенза, 2002. С.27-30.

72. Целых A.A. Методы нахождения нечеткого гиперграфа трансверсалей. // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник трудов 11-го Международного научно-практического семинара. М.: Физматлит, 2003. С. 137-140.

73. Целых A.A. Методы персонализации процессов взаимодействия сторон в электронной коммерции на основе кластеризации.// Известия ТРТУ. Тематический выпуск: Интеллектуальные САПР. Таганрог: ТРТУ, 2000, №2(16). С.73-75.

74. Целых А.А. Нечеткая гиперграфовая модель кластеризации для автоматической персонализации в электронной торговле. // Обозрение прикладной и промышленной математики. М.: ОПиПМ, 2002. С.483.

75. Целых А.А. Технология работы виртуального магазина. // Новые информационные технологии. Разработка и аспекты применения. Тезисы докладов I Всероссийской научной конференции молодых ученых и аспирантов. Таганрог, 1998. С.138-140.

76. Целых А.А. Формирование оптимальных информационных потоков в сети Интернет при нечетких запросах пользователей // Известия ТРТУ. Тематический выпуск: Интеллектуальные САПР. Таганрог: ТРТУ, 1999, №3(13). С.33-36.

77. Aggarwal С.С., Wolf J.L., Wu K.-L., Yu P.S. Horting Hatches an Egg: A New Graph-Theoretic Approach to Collaborative Filtering. // Proceedings of the Fifth ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'99). 1999.

78. Agrawal R., Srikant R. Fast Discovery of Association Rules // Proc. of the 20th International Conference on VLDB, Santiago, Chile. 1994.

79. Bartolini G. Web usage mining and discovery of association rules from HTTP servers logs. Melbourne: Monash University, 2000.

80. Berge C. Graphs and Hypergraphs. New York: American Elsevier, 1976.

81. Brin S., Motwani R., Ullman J. Dynamic Itemset Counting and Implication Rules for Market Basket Data // Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York. 1997.

82. Cooley, R., Mobasher, В., Srivastava, J. Data Preparation for Mining World Wide Web Browsing Patterns // Journal of Knowledge and Information Systems. 1999. - V.l. - №1.

83. Dai H., Mobasher В., Luo T., Nakagawa M. Discovery of Aggregate Usage Profiles for Web Personalization // Proceedings of the Web Mining for ECommerce Workshop (WebKDD'2000). 2000.

84. Davidow W., Malone M. The Virtual Corporation: Structuring and Revitalizing the Corporation for the 21st Century, 1992.

85. FIRST: Fuzzy Information Retrievol System/Lucarella D., Morara R./J.Inf. Sei.-1991.-17, №2. Англ.

86. Gunopulos D., Khardon R., Mannila H., Toivonen H. Data Mining, Hypergraph Transversals, and Machine Learning // Proc. PODS'97. 1997.

87. Joy B. Why the Future Doesn't Need Us. // Wired Magazine. 2000. - №4.

88. Kohavi R. Mining E-Commerce Data: The Good, the Bad, and the Ugly // Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2001.

89. Mamdani E. H., Sembi B. S. On the nature of implication in fuzzy logic //Proc.9th Int. Symp. of Multiple-Valued Logies.- New York, 1979,- P. 143151.

90. Mobasher В., Cooley R., Srivastava J. Automatic Personalization Based On Web Usage // Communication of ACM. 2000. - Volume 43. - Issue 8.

91. Mobasher В., Han E., Karypis G., and Kumar V. Clustering Based on Association Rule Hypergraphs // Proceedings of SIGMOD'97 Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD'97). -1997.

92. Park J.S., Chen M.-S., Philip S.Y. An Effective Hash Based Algorithm for Mining Association Rules // Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York. 1995.

93. Peppers, D., Rogers M. The one to one future: building relationships one customer at a time. Currency/Doubleday, 1993.

94. Personalization Technologies. Making One-to-One a Reality. CRM Report Series. // Datamonitor. 2001.

95. Pine, J.B. Mass Customization. Boston: Harvard Business School Press. 1993.lOl.Sarwar В., Karypis G., Konstan J., Riedl J. Analysis of Recommendation Algorithms for E-Commerce // Proceedings of the ACM EC'OO Conference. 2000.

96. Savasere A., Omiecinski E., Navathe S. An Efficient Algorithm for Mining Association Rules in Large Databases // Proc. of 21st Int'l Conf. Very Large Data Bases. 1995.

97. Srivastava J., Cooley R., Deshpande M., Tan P.-N., Web Usage Mining: Discovery and Applications of Usage Patterns from Web Data. // SIGKDD Explorations. 2000. - №1(2).

98. Tselykh A. Analysis of Information Streams Represented with Fuzzy Hypergraphs. // Интерактивные системы ИС-99. Материалы 3-й Международной научно-технической конференции. Ульяновск, 1999. С.69-70.

99. Uno Т. Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs // Lecture Notes on Computer Science, Springer Verlag, 1997.

100. Wind J., Mahajan V. Digital Marketing // Forthcoming 2000. 2000. -№2.