Методы определения семантической близости документов
Области применения: 1.Текстовый поиск в интернете. 2.Поиск «близких» документов. 3.Классификация текстов. 4.Устранение многозначности.
Методы: 1.По тексту 2.По связям
Методы: 1.По тексту 2.По связям
Латентно-семантический анализ
Задача: кластеризовать новости по заголовкам.
Британская полиция знает о местонахождении основателя WikiLeaks В суде США начинается процесс против россиянина, рассылавшего спам Церемонию вручения Нобелевской премии мира бойкотируют 19 стран В Великобритании арестован основатель Wikileaks Джулиан Ассандж Украина игнорирует церемонию вручения Нобелевской премии Шведский суд отказался рассматривать апелляцию основателя Wikileaks НАТО и США разработали планы обороны стран Балтии против России Полиция Великобритании нашла основателя WikiLeaks, но, не арестовала В Стокгольме и Осло сегодня состоится вручение Нобелевских премий
Подготовка: 1.Удаление стоп-слов 2.Стемминг 3.Удаление слов в единст- венном экземпляре
Британская полиция знает о местонахождении основателя WikiLeaks В суде США начинается процесс против россиянина, рассылавшего спам Церемонию вручения Нобелевской премии мира бойкотируют 19 стран В Великобритании арестован основатель Wikileaks Джулиан Ассандж Украина игнорирует церемонию вручения Нобелевской премии Шведский суд отказался рассматривать апелляцию основателя Wikileaks НАТО и США разработали планы обороны стран Балтии против России Полиция Великобритании нашла основателя WikiLeaks, но, не арестовала В Стокгольме и Осло сегодня состоится вручение Нобелевских премий
Считаем количество раз вхождения каждого слова в документы и заносим в матрицу.
Сингулярное разложение матрицы: M = U*W*V t U и V t – ортогональные W – диагональная (элементы в порядке неубывания)
Строки и столбцы с меньшим сингулярным числом дают меньший вклад в произведение. Оставим только 2 самых весомых.
Методы: 1.По тексту 2.По связям
Методы, использующие связи: абстрагируемся от текста, важны только связи между документами. Унификация.
1.Локальные 2.Глобальные
1.Локальные 2.Глобальные
Локальные: близость определяется для пары вершин и не затрагивает большинство вершин.
Ближайшие соседи:
N(a) – множество ближайших соседей узла a
Коэффициент Жаккара: Коэффициент Дайса: СимКос:
Для направленных графов: Со-цитирование Библиографическое сочетание
1.Локальные 2.Глобальные
Глобальные: вычисляют близость между всеми вершинами графа.
SimRank: два объекта похожи, если на них ссылаются похожие объекты C – коэффициент затухания.
Метод итеративен.
Затраты времени и памяти. Базовый подход. O(n 2 ) памяти. O(Kn 2 d 2 ) времени, где: K – количество итераций d 2 – среднее значение |I(a)||I(b)| по всем (a, b)
Затраты времени и памяти. Улучшенный подход: рассматриваем только близкие вершины в графе. Пусть r – радиус в котором рассматриваются соседи. d r – среднее количество соседей в r. O(d r n) памяти O(Knd r d 2 ) времени
??