close

Вход

Забыли?

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

?

Презентация (PPT, 0.2MB)

код для вставкиСкачать
Решение задачи тематического
информационного поиска в
Рунет
Козлов Дмитрий Дмитриевич
1
Задача тематического ИП в Интернет
Задача тематического информационного поиска в Интернет
является частным случаем задачи информационного поиска,
обладающим следующими особенностями:
невозможно собрать все объекты поиска в единую базу данных;
объекты – это гипертекстовые страницы, образующие граф Web;
объекты группируются по web-сайтам;
в начале поиска пользователь не знает четко свою
информационную потребность чтобы идентифицировать объекты с
помощью запроса;
пользователь уточняет информационную потребность в процессе
поиска.
2
Пример тематического ИП в Интернет
Информационная потребность
? (надо как-то выбрать
кондиционер)
Запрос
«кондиционер»
Результат
Список из >100
вариантов
Оказывается, кондиционеры бывают разных типов
Обзор
типов
нужен обзор типов кондиционеров
Кондиционеры имеют много разных функций
Обзор
функций
Обзор функций кондиционеров
. . .
3
Актуальность задачи
Решением задачи тематического ИП в библиотеках занимались
профессионалы. Широкое распространение Интернет привело к
тому, что с этой задачей часто сталкиваются рядовые
пользователи.
Традиционные методы ИП, разработанные для электронных
библиотек, основаны на предположениях, противоречащих
свойствам задачи тематического ИП в Интернет.
Широко распространенные в Интернет системы поиска по
ключевым словам (СПКС), а также методы поиска тематических
сообществ, не учитывают особенностей задачи тематического
ИП.
Тематические каталоги в Интернет создаются почти всегда
вручную.
Задача тематического ИП в Интернет
Пространство поиска S:
G = <O, L> – ориентированный граф объектов, G=G(t), t=0,1,2,…
O = {oj = <aj1,…, ajk> – объекты поиска, k=k(j)},
Начальный запрос пользователя b0={bo1, …, b0m} – множество
требуемых атрибутов объектов поиска.
Запрос пользователя изменяется в процессе поиска bt = b(t).
Функция поиска A осуществляет поиск в S по запросу bt: A(bt,Gt)=ōO.
Оценка результатов поиска пользователем E(bt, ō) = ō’ ō.
Функция построения уточнения запроса Q(ō’, bt) = <bt+1, lt+1>. lt+1 L.
Функция расширения пространства поиска: Gt+1 = W(Gt, lt+1, bt).
Для решения задачи тематического ИП в Интернет необходимо
построить функции A, Q, W.
Критерий останова поиска: l ō’t+1 l - l ō’t l <
Точность поиска: l ō’t l / l ōt l
5
Цель работы
Цель работы:
1. Разработать алгоритм который реализует функцию поиска
A(bt,Gt) и функцию расширения пространства поиска
W(Gt,lt+1,bt) таким образом, чтобы максимизировать точность
поиска.
2. Исследовать вопрос о возможности автоматизации функции
построения нового запроса Q(ō’, bt).
3. Провести экспериментальное исследование эффективности
предложенного алгоритма.
6
Основные предшествующие идеи
Представление Web в виде ориентированного графа.
Использование информации о графе Web, накопленной
в существующих поисковых системах
(J. Kleinberg, 1998).
Предположение о семантике гиперссылок
(D. Gibson, J. Kleinberg, 1998).
Принцип тематической локальности Web
(B. Davison, 2000).
Оценка значимости внутри тематической группы
страниц (J. Kleinberg, 1998).
Методы поиска тематических сообществ
(D. Gibson, J. Kleinberg 1998, M. Henzinger 2000).
7
Модель тематического ИП в Интернет
Исходные данные
Построение подграфа
Граф
Web
Анализируемый
подграф
Обратная
связь
Анализ
Исходные данные:
набор ключевых слов .
Операции расширения
анализируемого подграфа:
скачивание страницы;
получение ссылок на
страницу;
получение от систем
поиска по ключевым
словам результатов
запроса.
Модель темы
8
Модель тематического ИП в Интернет
Исходные данные
Построение подграфа
Граф
Web
Анализируемый
подграф
Обратная
связь
Анализ
Модель темы
Результат поиска – модель темы MT:
множество страниц P = {p},
гиперссылки между страницами
HP = { <p1,p2> | p1, p2 P };
множество ресурсов
R = { r | r P };
граф ресурсов GR = (R,HR);
оценки страниц и ресурсов:
релевантность, значимость;
TFIDF-модель темы T P.
Обратная связь:
по релевантности –
RFB={ <p, rel>, <r, rel>
| p P, r R},
rel {tfidf, model, none, bad};
направление поиска –
DFB={ r | r R };
9
Алгоритм тематического ИП в Интернет
Исходные данные
Построение подграфа
Граф
1. Построение анализируемого
подграфа графа Web.
2. Анализ подграфа.
3. Отбор страниц в модель
темы.
Web
Анализируемый
подграф
Обратная
связь
Итерация работы системы:
4. Получение обратной связи
от пользователя и выбор
направления поиска на
следующую итерацию.
Анализ
Модель темы
10
Алгоритм тематического ИП в Интернет
Итерация работы системы:
На первой итерации:
1. Построение анализируемого
подграфа графа Web.
2. Построение графа ресурсов.
СПКС
Root set
Expanded set
3. Оценка страниц и ресурсов.
4. Отбор страниц в модель.
5. Получение обратной связи
от пользователя и выбор
направления поиска на
следующую итерацию.
На последующих итерациях:
Анализируемый граф
расширяется на основе
выбранного на предыдущей
итерации направления поиска.
11
Алгоритм тематического ИП в Интернет
Итерация работы системы:
1. Построение анализируемого
подграфа графа Web.
Предложен набор правил,
позволяющий объединять
страницы в ресурсы.
2. Построение графа ресурсов.
Ресурсом могут быть
3. Оценка страниц и ресурсов.
web-сайт;
4. Отбор страниц в модель.
часть сайта;
5. Получение обратной связи
от пользователя и выбор
направления поиска на
следующую итерацию.
домашняя страница
пользователя;
отдельная web-страница;
группа сайтов.
Ресурс должен быть тематически
однороден.
12
Алгоритм тематического ИП в Интернет
Итерация работы системы:
Оценка релевантности:
1. Построение анализируемого
подграфа графа Web.
2. Построение графа ресурсов.
3. Оценка страниц и ресурсов.
4. Отбор страниц в модель.
5. Получение обратной связи
от пользователя и выбор
направления поиска на
следующую итерацию.
текстов страниц;
текстов гиперссылок между
страницами.
Для вычисления оценок
релевантности используется
алгоритм TFIDF.
Релевантность ресурса
определяется как среднее
значение релевантности страниц
ресурса.
13
Алгоритм тематического ИП в Интернет
Итерация работы системы:
Оценка значимости ресурсов:
1. Построение анализируемого Используется алгоритм SALSA, со
подграфа графа Web.
следующими модификациями:
2. Построение графа ресурсов.
анализ ресурсов, а не страниц;
3. Оценка страниц и ресурсов.
учет релевантности ссылок:
4. Отбор страниц в модель.
a(v) = h(u1) * weight(u1,v) + …
5. Получение обратной связи
от пользователя и выбор
направления поиска на
следующую итерацию.
учет средней релевантности
страниц ресурса:
h(u) = a(v1) * rel(v1) + …
Предложенные модификации
повышают точность оценки.
14
Алгоритм тематического ИП в Интернет
Итерация работы системы:
Фильтрация по языку ресурса.
1. Построение анализируемого Вычисление комбинированной
подграфа графа Web.
оценки ресурсов:
2. Построение графа ресурсов.
3. Оценка страниц и ресурсов.
4. Отбор страниц в модель.
5. Получение обратной связи
от пользователя и ыбор
направления поиска на
следующую итерацию.
значимость ресурса +
релевантность ресурса
Отбор ограниченного числа
кандидатов на включение в
модель темы на основе
комбинированной оценки.
15
Алгоритм тематического ИП в Интернет
Итерация работы системы:
1. Построение анализируемого
подграфа графа Web.
2. Построение графа ресурсов.
3. Оценка страниц и ресурсов.
4. Отбор страниц в модель.
5. Получение обратной связи
от пользователя и выбор
направления поиска на
следующую итерацию.
Обратная связь по релевантности:
оценка кандидатов на
включение в модель темы;
отбор страниц для пополнения
TFIDF-модели (оценка tfidf).
Выбор направления поиска:
задание пользователем,
автоматический выбор.
Автоматический выбор
направления:
отбор значащих гиперссылок на
основе эвристик и оценок
значимости.
16
Экспериментальное исследование
Целью
экспериментального
исследования
являлся
анализ
эффективности предлагаемого подхода, а именно:
оценка точности предлагаемого метода поиска по сравнению с
существующими методами поиска тематических сообществ;
сравнение вычислительной сложности предлагаемого метода
поиска со сложностью существующих методов поиска
тематических сообществ.
17
Постановка эксперимента
Задача поиска ключевых ресурсов Интернет по заданной теме:
По заданной в виде набора ключевых слов теме необходимо построить
список источников (web-сайтов или их частей), в которых
концентрируются документы, относящиеся к данной теме.
Исходные данные для Реальные данные Рунет.
экспериментов:
Эталонные результаты: 1.
2.
Эталонные результаты собранные
для каждой темы из каталогов
yaca.yandex.ru, list.ru, aport.ru,
dmoz.org.
Эталонные результаты,
предоставленные экспертами.
Мера эффективности: Точность на 10 первых результатах
поиска.
18
Результаты экспериментов
ландшафтный дизайн (q1)
авторская песня (q2)
программирование на java (q3)
технология xml (q4)
операционная система linux (q5)
раннее развитие детей (q6)
автострахование (q7)
пчеловодство (q8)
1
0,9
0,8
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0
q1
q2
q3
q4
q5
q6
q7
q8
0,7
обзоры железа (Q1)
имитационное моделирование
непрерывно-дискретных систем (Q2)
паевые инвестиционные фонды (Q3)
декабристы (Q4)
пальчиковые игры (Q5)
бродский (Q6)
0,6
0,5
0,4
0,3
0,2
0,1
0
Q1
Q2
Q3
Q4
Q5
Q6
HITS, SALSA, Предложенный метод
19
Сравнение вычислительной сложности
Алгоритм/Класс операций
HITS
SALSA
Предложенный
подход
на
итерации
1-й
Предложенный подход
на последующих итерациях
Получение
от
СПКС
результатов по запросу q
1
1
1
0
Скачивание страниц
N
N
N
K (константа, определяемая
пользователем)
|Root Set|
|Root Set|
|Root Set|
K
Вычисление оценки
релевантности страницы
0
0
N
N+K
Вычисление
релевантности
гиперссылки
0
0
~7*N
~ 7 * (N +K)
Вычисление
оценки
значимости, сколько раз,
какова сложность
1 раз,
О(N2)
1 раз,
О(N2)
1 раз,
О(N2)
1 раз,
О((N+K)2)
Удаление
внутренних
гиперссылок
О(N)
О(N)
0
0
Построение графа ресурсов
0
0
О(N)
О(N)
Скачивание
ссылок
страницу
на
оценки
текста
20
Результаты
1.
Построена модель тематического ИП в Интернет, которая учитывает
динамическое уточнение информационной потребности пользователя и
динамическое изменение пространства поиска.
2.
Разработан алгоритм тематического ИП в Интернет, реализующий
предложенную модель за счет обобщения методов поиска тематических
сообществ в части:
направленной организации итерационного процесса поиска;
новой интерпретации механизма обратной связи;
расширения алгоритма анализа структуры гиперссылок (алгоритма
SALSA) средствами анализа текстов страниц.
3.
Полученные оценки точности и сложности предложенного алгоритма
показывают, что он обеспечивает более высокую точность поиска по
сравнению с существующими методами поиска тематических сообществ
за счет определенного увеличения вычислительной сложности.
21
Документ
Категория
Презентации по информатике
Просмотров
6
Размер файла
248 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа