Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Поиск в социальных сетях: тенденции и алгоритмы Илья Сегалович (Яндекс) - презентация

1 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Поиск в социальных сетях: тенденции и алгоритмы Илья Сегалович (Яндекс)

2 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Почему социальная сеть Популярность поиска: обратная сторона Жизнь документов и сайтов: компании и люди, переезды и повторы «Популярность» и посещаемость Ошибки, форматы, «грязь», скрипты Почему анализ текста беспомощен

3 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Цитируемость Индекс цитирования (backlinks) Статический ранг: PageRank Локальный ранг: Hits, SALSA, локальный PageRank Ссылочное ранжирование и anchor-text propagation

4 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Непотизм – вызов XXI века Внутрисайтовость (в т.ч. IP?) Выявление линкфармов, каталогов само ввода, гестбуков, форумов Тематическая близость? Использование DOM структуры HTML? Что делать с

5 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Природа дубликатов Повтор текста – фундаментальная особенность социальной сети Технические причины (в т.ч. «переодетые зеркала») Копирование с редактированием Скрипты

6 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Почти-дубликаты Шинглы (требуют кластеризации) «Супершингл» (Яндекс.Почта) Локальные лексические сигнатуры Глобальные лексические сигнатуры (Яндекс)

7 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Веб-Каталог: Фасеты vs. Глубина Сколько нужно категорий? Сложная навигация Повтор структур в листьях Темы Регионы (Россия, Москва, …) Жанр (Худ Лит, Науч Тех,...) Доверие к источнику (официальный, пресса, частный, анонимный) … Многомерный каталог

8 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Regional Reliability Addressee Domain Topics

9 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Кластеризация «каталогом» Визуальная структура результатов Сопровождать документ «темой» Ограничение поиска «темой» Вес группы:

10 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Полуавтоматический процесс Аннотировать вершины – не страницы Вес по цитируемости Вес по «размеру» Структура сайта Вершина Тема Цитиру- емость Размер «Вес»

11 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Тематическая классификация Лучшие 10,000 слов по TF*IDF 45,000-размерное пространство Наследование признаков 8-10 часов для 30,000,000 документов Встроена в «робота»

12 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Стилистичесикй авто классификатор Социальная природа жанра Относительная простота классификации Признаки: морфология (части речи, глагольные формы), лексика (слова из заданных списков), синтаксис (цепочки родительных падежей, '{можно|нужно} + инфинитив), формальные (длина слова, предложения) Составление минимального набора параметров Дискриминантный анализ

13 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Морфология Несловарный стемминг. Snowball (80-120) Словарная нормализация: PC-Kimmo, RXRCE (30-50) Словарь = «супер правило». Алгоритм БЫКА (40) (Сегалович, 1996)

14 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Поиск по «кворуму» Способ «фильтрации» при поиске Длинные запросы = «нечеткие цитаты» Близкий vs. широкий контекст Многоместный AND с разным контекстом

15 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Синтаксический анализ для выявления скрытого контекстного ограничения ATN-грамматика адаптированная для зависимостей Только именные группы Примыкание, притяжение, перечисление

16 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Трансформации запроса [что такое сегнетова соль] [сегнетова соль /+1 !%это] [я тебя ненавижу - но ко мне ты все ближе] [+!я +!тебя ненавижу - +!но +!ко +!мне +!ты +!все ближе] [что такое кванза] [кванза /+1 !%это /(-2 4) %означает /(-2 4) %аббревиатура /(-2 4) %расшифровывается"]

17 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 P2P: Распределенное индексирование Точность предсказания <10% Обмен списками файлов, не индексом Простой текстовый формат протокола Открытая документация V 2 F H U /index.html U /about.html T C d41d8cd ecf8427e V 2 H U /index.html D /about.html?qqq T C d41d8cd ecf8427e Пример реального протокола: Платформы: FreeBSD, Win32, SUN, Linux, HP, Lotus Notes

18 Семинар Москоской секции ACM SIGMOD 26 декабря 2002 Вопросы? Илья Сегалович