Методы определения семантической близости документов

Области применения:
Текстовый поиск в интернете.
Поиск «близких» документов.
Классификация текстов.
Устранение многозначности.

Методы:
По тексту
По связям

Методы:
По тексту
По связям

Латентно-семантический анализ

Задача: кластеризовать новости по заголовкам.

Британская полиция знает о местонахождении основателя WikiLeaks
В суде США начинается процесс против россиянина, рассылавшего спам
Церемонию вручения Нобелевской премии мира бойкотируют 19 стран
В Великобритании арестован основатель Wikileaks Джулиан Ассандж
Украина игнорирует церемонию вручения Нобелевской премии
Шведский суд отказался рассматривать апелляцию основателя Wikileaks
НАТО и США разработали планы обороны стран Балтии против России
Полиция Великобритании нашла основателя WikiLeaks, но, не арестовала
В Стокгольме и Осло сегодня состоится вручение Нобелевских премий

Подготовка:
Удаление стоп-слов
Стемминг
Удаление слов в единст- венном экземпляре

Британская полиция знает о местонахождении основателя WikiLeaks
В суде США начинается процесс против россиянина, рассылавшего спам
Церемонию вручения Нобелевской премии мира бойкотируют 19 стран
В Великобритании арестован основатель Wikileaks Джулиан Ассандж
Украина игнорирует церемонию вручения Нобелевской премии
Шведский суд отказался рассматривать апелляцию основателя Wikileaks
НАТО и США разработали планы обороны стран Балтии против России
Полиция Великобритании нашла основателя WikiLeaks, но, не арестовала
В Стокгольме и Осло сегодня состоится вручение Нобелевских премий

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

Сингулярное разложение матрицы:
M = U*W*Vt
U и Vt – ортогональные
W – диагональная (элементы в порядке неубывания)

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

Методы:
По тексту
По связям

Методы, использующие связи: абстрагируемся от текста, важны только связи между документами.
Унификация.

Локальные
Глобальные

Локальные
Глобальные

Локальные: близость определяется для пары вершин и не затрагивает большинство вершин.

Ближайшие соседи:

N(a) – множество ближайших соседей узла a

Коэффициент Жаккара:
Коэффициент Дайса:
СимКос:

Для направленных графов:
Со-цитирование
Библиографическое сочетание

Локальные
Глобальные

Глобальные: вычисляют близость между всеми вершинами графа.

SimRank: два объекта похожи, если на них ссылаются похожие объекты
C – коэффициент затухания.

Метод итеративен.

Затраты времени и памяти.
Базовый подход.
O(n2) памяти.
O(Kn2d2) времени, где:
K – количество итераций
d2 – среднее значение |I(a)||I(b)| по всем (a, b)

Затраты времени и памяти.
Улучшенный подход: рассматриваем только близкие вершины в графе.
Пусть r – радиус в котором рассматриваются соседи.
dr – среднее количество соседей в r.
O(drn) памяти
O(Kndrd2) времени