Шевченко Алексей, 422 группа

Введение в проблему поиска документов Автоматическое индексирование цитат - система CiteSeer Решение, основанное на методах LASVM и DBSCAN Пара слов о комбинированном методе

Быстрый рост количества научных публикаций Большой разброс публикаций по сети Отсутствие какой-либо общей структуры научных работ Отсутствие свободного доступа к публикациям некоторых электронных журналов Улучшение возможностей доступа к публикациям Различный формат документов (текст, html, PDF и т.д.)

Структуризация документов на основе взаимного цитирования Создание базы данных, объединяющей существующие научные публикации Полнота охвата данных в конкретной области Низкая вероятность ошибок при связывании документов Большое количество человеческих трудозатрат Создание программного средства, обеспечивающего индексацию электронных документов Полная автоматизация процесса индексации документов Высокая вероятность ошибки Возможность обрабатывать индексировать документы только на одном языке Комбинированный подход: использование базы данных одновременно со средствами автоматической индексации

Поиск научных публикаций Анализ полученных документов Индексирование и связывание документов

Поиск с помощью существующих поисковых машин Поиск по ключевым словам (например, publication, paper, postscript) Получение информации из дружественных источников Получение ссылок на документы по RSS или аналогичным способом Непосредственная загрузка ссылок в базу данных системы автоматического индексирования авторами или издателями научных статей Определение «научности» документа на основании наличия списка литературы или секции «Related works»

Поиск ссылочной секции по форматированию Поиск непосредственно ссылок на прочие работы Под словами «ссылка» или «цитата» подразумевается ссылка на статью вида год-автор-заголовок и т.д. Полнотекстовый поиск не производится. Извлечение метаданных из цитат Извлечение метаданных из документа

Сохранение метаданных документа в базе данных Группировка цитат, относящихся к одном документу, и сопоставление ссылок и цитируемых документов на основании метаданных документа и цитаты Данная задача является ключевой при построении графа цитирования Существуют различные методы решения этой задачи. Можно выделить четыре основных способа ее решения: На основании расстояний между строками или расстояний редактирования На основании статистики слов (например, TFIDF) Сопоставление подполей (subfield) цитат и метаданных (например, год издания) Вероятностные модели, также использующие информацию подполей А также комбинации вышеперечисленных методов

Идеальный вариант – подполя цитаты полностью совпадают с метаданными документа Различное написание ссылок на одни и те же документы Ошибки и опечатки в имени автора, годе выпуска и т.д. Два подполя с одинаковым значением могут ссылаться на различные данные Пример: Aha, D. W. (1991), Instance-based learning algorithms, Machine Learning 6(1), D. W. Aha, D. Kibler and M. K. Albert, Instance-Based Learning Algorithms. Machine Learning , Kluwer Academic Publishers, Aha, D. W., Kibler, D. & Albert, M. K. (1990). Instance-based learning algorithms. Draft submission to Machine Learning.

CiteSeer – известная программа, выполняющая ACI CiteSeer использует алгоритм, основанный на нормализации цитат, сортировки цитат по длине и сопоставления слов и фраз внутри подполей Алгоритм может быть улучшен методами машинного обучения, проводимого на существующих библиографических базах Кроме того, можно разрешить определенным пользователям вносить изменения CiteSeer позволяет классифицировать статьи как исследовательские, учебные и обзорные на основании информации о количестве цитат из широко цитируемых статей (hubs and authorities) CiteSeer предоставляет дополнительные функции, такие как навигация по графу цитирования, сбор статистики (например, за какие годы больше всего статей у определенного автора). Из индексации исключены «stop-words», например, «the», и т.д.

Самыми простыми методами группировки метаданных являются определение строковых расстояний и TFIDF-мера Эти способы не учитывают информацию подполей; они рассматривают цитаты и, возможно, метаданные документов как текстовую строку Существует множество различных строковых расстояний. Цитаты считаются относящимися к одной группе, если расстояние между ними не превышает некоторой эмпирически установленной величины. Одним из самых простых расстояний является расстояние Левеншайна, которое считается как количество удалений, вставок и замен, необходимый для преобразования одной строки в другую (расстояние редактирования). Существуют и гораздо более сложные метрики (например, LikeIt)

Для определения схожести текстов может использоваться tf*idf мера (Tf = term frequency, Idf = inverse document frequency): Размерность вектора, представляющего текст, равна общему количеству термов (различных слов) во всей выборке текстов J-й элемент вектора I, соответствующего I-му документу, равен tf*idf Tf = ½ + ½ * TermFrequency/MaxTermFrequency, где TermFrequency – частота терма в тексте, MaxTermFrequency – максимальная частота термов в тексте Idf = log(N/df), где N – число документов в выборке, df – число документов, в которых встречается терм Схожесть текстов определяется как косинус угла между векторами, представляющими документы:

Сначала для каждого документа p(i) выделяются все упоминаемые авторы a(i,j), каждый из которых соотносится с метазаписью Для каждой записи выделяются подполя (атрибуты) t(i, j, k), 1

«Блочный» модуль группирует непротиворечивые цитаты (метазаписи) в «предварительные классы» (candidate classes) Для каждой пары внутри класса строится поатрибутный вектор похожести, причем для разных типов атрибутов используются разные функции похожести (например, расстояние редактирования для URL и TFIDF для имен) На основании этого вектора SVM (Support Vector Machine) определяет попарные расстояния между метазаписями На основании данных DBSCAN проводит кластеризацию

Для обучения SVM- алгоритма используется обучающая выборка, состоящая из векторов похожести и их булевых меток. Задача алгоритма – поиск оптимальной гиперплоскости (w*x) + b = 0, w – Rn, b – R, разделяющей обучающую выборку. Для оптимизации ищется минимальное значение |w|^2, при условии, что Yi((w*xi) + b) >= 1 (Yi – булевая метка, +1 или -1) LASVM – модификация SVM-алгоритма. В то время как SVM работает только с пакетами, LASVM способен работать в онлайн-режиме, т.е. при добавлении новых данных не нужно заново обрабатывать всю обучающую выборку. За счет этого можно использовать меньше оперативной памяти, т.о. LASVM применим к очень большим объемам данных Для оптимизации обучающей выборки используются ASM – active sample selection, которая оставляет наиболее значимые данные и удаляет «шумы». Выборка считается тем более оптимальной, чем ближе она находится к гиперплоскости. Использование классической ASM в сочетании с SVM слишком дорого, однако можно использовать упрощенные методы без полного поиска; например, выбрать из каждый 50 сэмплов один наилучший

DBSCAN is Density Based Spatial Clustering of Applications with Noise Попарная кластеризация с превышением порога создает проблему транзитивности, когда A и B и В и С попадают в один кластер, а А и С – нет. Эта проблема возникает из-за ошибок в извлечении метаданных и несовершенстве используемых метрик DBSCAN – высокоэффективный метод кластеризации, основанный на густоте точек Причины использования DBSCAN: Довольно хорошее решение проблемы транзитивности Моделирование кластеров любой формы; кроме того, границы кластеров более приближены к человеческому восприятию Высокая эффективность метода, при вычислительной сложности O(N*logN)

Для всех определений будем полагать заданными параметры Eps и MinPts. Точка P непосредственно густо-достижима (directly density- reachable) из точки Q, если P лежит в Eps-окрестности Q и кол-во всех точек в этой окрестности >= MinPts. Q – центр (core point) P густо-достижима из Q, если существует последовательность P1…Pn, где P1 = Q, Pn = P и Pi+1 непосредственно густо-достижима из Q P густо-связанная с Q, если существует O, т.ч. P и Q густо-достижимы из O Кластер - непустое подмножество C исходного множества точек, удовлетворяющее след. условиям: 1) Для любых P и Q, если P принадлежит C и Q г.-д. из P, то Q принадлежит C 2) Для любых P и Q из C, P густо-связана с Q Шум – множество точек исходного множества, не принадлежащих ни одному кластеру

Корректность следует из двух лемм: Если в Eps-окрестности точки P находится не менее MinPts точек, то все густо-достижимые из P точки образуют кластер Если C – кластер и P - центр, то C эквивалентен мно-ву всех густо-достижимых точек из P Общий принцип работы алгоритма кластеризации таков. Алгоритм начинает работу в произвольной точке P Если точка P является центром, то все густо- достижимые из P точки образуют кластер Если точка P не является центром, то выбирается следующая точка, и т.д.

Каждая цитата обрабатывается сразу же, при поступлении в систему, и, если соответствующий документ не был найден, в соответствие ставится некий виртуальный документ. При поступлении в систему подходящего документа виртуальный документ заменяется на реальный Для извлеченных из каждой цитаты метаданных строится структура, состоящая из конъюнкции дизъюнкций всех полей, относящихся к имени автора, и конъюнкции прочих атрибутов Далее, для заданного документа ищется список всех цитат, «похожесть» которых превышает некоторое значение, и для заданной цитаты ищется аналогичный список документов. На основании этих данных делается вывод, относится заданная цитата к документу или нет Также ставится задача определения метаданных некоторого неизвестного документа на основании метаданных всех ссылающихся на него цитат. В таком случае из всех возможных вариантов строится «доверительный вектор», состоящий из вероятностей всех возможных вариантов. При появлении нового варианта вектор перерасчитывается с учетом нового возможного значения

Steve Lawrence, C. Lee Giles, Kurt Bollacker. Digital Libraries and Autonomous Citation Indexing. В данной статье описана проблема индексирования цитат и документов, а также описана работа системы для ACI CiteSeer Anand Sivasubramaniam, C. Lee Giles, and others. Learning Metadata from the Evidence in an On-Line Citation Matching Scheme. В данной статье описан комбинированный подход к проблеме построения графа цитирования, основанный на вероятностных моделях и кластеризации. Jian Huang1, Seyda Ertekin2, and C. Lee Giles. Efficient Name Disambiguation for Large-Scale Databases. В данной статье описана система, основанная на методах LASVM (обучаемый алгоритм, используемый для извлечения метаданных) и DBSCAN (метод кластеризации, основанный на понятии плотности) Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. В данной статье приводится детальное описание алгоритма DBSCAN.