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

Презентация:



Advertisements
Похожие презентации
© ElVisti Лекция 7 Кластерный анализ и информационный поиск Дмитрий Владимирович ЛАНДЭ МЕЖДУНАРОДНЫЙ СОЛОМОНОВ УНИВЕРСИТЕТ.
Advertisements

Кластеризация статей кафедральной базы знаний студент 4 курса И.И. Савин 1 руководитель: И.С. Игнатьев.
Алгоритм Катхилла-Макки. 2 Основные определения Граф можно представить себе состоящим из конечного множества узлов, или вершин, вместе с множеством ребер,
Взвешенные графы. Матрицы смежности. Взвешенные графы Взвешенный граф (сеть) - граф, ребрам или дугам которого поставлены в соответствие числовые величины.
Текстовая кластеризация алгоритмом ROCK студент 4 курса МИЭМ, каф. ИКТ Иван Савин 1.
Метод выявления неявных связей объектов Снарский А.А., Ландэ Д.В., Женировский М. И. НТУУ «Киевский политехнический институт», Информационный центр «ЭЛВИСТИ»,
Бесплатное продвижение возможно, или внутренняя оптимизация сайта. Якимов Василий телефон:
Методы предварительной обработки данных для алгоритма Клейнберга А. Корявко И. Некрестьянов
Исследование CBR (Case Based Reasoning) метода при автоматизированном проектировании информационных систем.
§2. Определители 1. Вспомогательные определения ОПРЕДЕЛЕНИЕ. Пусть n – натуральное число. Факториалом числа n (обозначают: n!) называют произведение натуральных.
Анализ данных Кластеризация. План лекции Определение кластеризации Применение кластеризации Общий алгоритм кластеризации Типы кластеризации Цели: Дать.
ТЕМА ЛЕКЦИИ : « МАТРИЦЫ И ДЕЙСТВИЯ НАД НИМИ ». ПЛАН ЛЕКЦИИ 1. Определение матрицы, элементы матриц 2. Виды матриц 3. Линейные операции над матрицами.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Автор: Сергеенкова И.М., ГБОУ Школа 1191, г. Москва Автор: Сергеенкова И.М., ГБОУ Школа 1191, г. Москва.
Исследование CBR (Case Based Reasoning) метода при автоматизированном проектировании информационных систем.
Урок по теме: Система управления базами данных. Табличная форма данных.
§2. Определители 1. Вспомогательные определения ОПРЕДЕЛЕНИЕ. Пусть n – натуральное число. Факториалом числа n (обозначают: n!) называют произведение натуральных.
Метод кластеризации текстов, основанный на попарной близости термов, характеризующих тексты, и его сравнение с метрическими методами кластеризации Михаил.
Задачи электронных таблиц автоматические вычисления с данными в таблицах: хранение данных в табличном виде; представление данных в виде диаграмм; анализ.
Транксрипт:

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

Области применения: 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 ) времени

??