'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10


Слайд 11

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


Слайд 12


Слайд 13

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


Слайд 14


Слайд 15


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

??


×

HTML:





Ссылка: