Работа посвящена решению задачи устранения дублирующихся документов из потока текстовых сообщений. Приведена многокритериальная модель документа, предложен метод обнаружения дубликатов на основе бинарной классификации с помощью метода опорных векторов. Основной акцент сделан на обеспечении применимости метода для обработки документов из разных предметных областей. Предложен способ снижения вычислительной сложности метода посредством предварительной фильтрации кандидатов.
В настоящее время во многих предметных областях существует потребность в формировании больших текстовых коллекций. При этом производится сбор текстовой информации из открытых Интернет-источников, а также специализированных ресурсов. Основной областью использования создаваемых таким образом хранилищ документов является интеллектуальная обработка текстов, которую, как правило, можно отнести к классу Text Mining.
С ростом количества разнообразных источников данных в сети Интернет (новостные сайты, блоги, социальные сети) всё более серьезной проблемой становится дублирование информации. Сообщения, публикуемые одним источником, зачастую многократно перепечатываются другими (в исходном виде или с небольшими изменениями). В результате, при выполнении автоматического сбора документов из многочисленных источников в формируемой текстовой коллекции накапливаются идентичные или близкие по содержанию документыдубликаты. В некоторых задачах наличие дубликатов должно учитыватьсянапример, при определении значимости сообщений [14]. Но в большинстве случаев попада-ние таких документов в коллекцию снижает её качество [12,16].
В данной статье рассматривается решение задачи обнаружения дубликатов в потоке текстовых сообщений. Особое внимание уделяется обеспечению возможности использования разработанного метода для обработки документов из различных предметных областей.
В работе [9] авторами было предложено решение задачи качественного автоматического сбора новостных данных из Интернет-источников, предполагающего извлечение с веб-страницы текста новости, а также сопутствующих метаданных, включающих название, дату публикации, автора новости и др. При этом осуществляется контроль корректности извлекаемой информации, то есть проверка соответствия текстов загружаемых документов исходным текстам новостей на сайте.
Текстовые данные, извлеченные с веб-сайтов, подвергаются обработке различными методами интеллектуального анализа [7][8], такими как автоматическая классификация и кластеризация документов, извлечение знаний и фактов из естественноязыковых текстов, выявление трендов и прогноз развития ситуаций.
Для эффективного применения перечисленных методов обработки текстовых данных необходимо обеспечить качество анализируемой коллекции документов. Помимо вышеупомянутой корректности каждого конкретного текста, качество коллекции подразумевает требование оригинальности составляющих её новостей. Присутствие в обрабатываемом наборе одинаковых или очень близких по содержанию документов может отрицательно сказаться на качестве обработки. Это касается работы модулей, выполняющих статистический анализ документов, например, модуля анализа трендов. Его работа основана на выявлении в коллекции новостей, относящихся к анализируемой ситуации, и определении зависимости частоты встречаемости таких документов от времени. Появление дублей приведет к многократному учету модулем идентичных новостей, что повлечет за собой некорректный вид построенной зависимости.
Для обеспечения оригинальности документов, составляющих текстовую коллекцию, в систему сбора необходимо встроить подсистему, задачей которой является оперативное обнаружение и удаление из коллекции нечетких дубликатов (рис. 1).
Она должна анализировать каждый загружаемый документ и принимать решение о его оригинальности. Для этого необходимо сравнить его с загруженными ранее новостями и определить, является ли он нечетким дубликатом одной из них. При обнаружении дубля он должен быть удален до этапа загрузки данных в базу данных.
Рис. 1. Место подсистемы обнаружения дубликатов в системе автоматизированного сбора и анализа новостной информации
Если проблема обнаружения и удаления полных дублей тривиальна, то при необходимости распознавать нечеткие дубликаты (то есть, документы, имеющие различный текст, но близкие по содержанию) возникают значительные сложности.
В связи с явлением частичного дублирования в работе [10] предлагается понятие информативной необходимости элемента высказывания: «Всякий частично-дублетный элемент, если он отвечает коммуникативной задаче высказывания, признается информативно-необходимым в той же мере, что и прочие, недублетные элементы речи: такой элемент информативно необходим постольку, поскольку вносит свой уникальный, неповторимый в других элементах, вклад в суммарную информацию, передаваемую высказыванием». Таким образом, задача обнаружения нечетких дубликатов состоит в распознавании и удалении сообщений, не являющихся информативно-необходимыми.
Установить информативную необходимость и ценность некоторого высказывания возможно только с учетом соответствующего ситуативного контекста. Так, при ручной проверке документов эксперт, определяя наличие или отсутствие дублирования, принимает решение с учетом предметной области и характера документов, составляющих ана-лизируемую коллекцию. Например, при работе с юридическими документами особое внимание должно уделяться метаданнымдля текстов такого типа два документа с практически идентичным содержанием, но различающимися названиями и датами публикации не могут считаться дублями. Другой подход используется при анализе экономических новостей, например, сводок о состоянии фондового рынкадубликатами не должны признаваться документы, имеющие одно и то же название и одинаковый текст, но различающиеся числовыми данными (значениями курсов валют).
Таким образом, в разных случаях эксперт сравнивает документы с точки зрения различных критериев (близость текстового содержания, сходство названий, разница во времени публикации), то есть использует различные модели распознавания дубликатов в зависимости от предметной области и контекста коммуникационных сообщений. Поэтому не представляется возможным выработать единую систему правил для обнаружения нечеткого дублирования сразу для всех случаев. Следовательно, разрабатываемая подсистема должна иметь возможность гибкой настройки на разные предметные области, что позволит ей моделировать деятельность эксперта по распознаванию дублей с использованием различных моделей. Поскольку система сбора выполняет извлечение документов из множества источников, которые относятся к различным предметным областям, необходимо обеспечить возможность работы с несколькими моделями распознавания дубликатов одновременно.
Еще одной проблемой, с которой приходится столкнуться при решении задачи устранения дубликатов, является большой объем обрабатываемых данных. Наличие в коллекции сотен тысяч документов делает весьма трудоемким анализ каждого нового сообщения путем сравнения его с каждым из ранее загруженных. Эта проблема может быть решена с помощью приближенных методов, но их применение ведет к снижению качества обнаружения дубликатов, то есть уменьшению точности и полноты [12]. При разработке предлагаемого подхода решалась задача совмещения высокого качества и низкой вычислительной сложности проверки документов.
Одним из наиболее популярных методов, используемых при поиске нечетких дубликатов вебдокументов, является алгоритм шинглов [2,5] В качестве элементов могут использоваться слова, встречающиеся в текстах коллекции [11]. При этом значениями элементов вектора (1), представляющего некоторый документ, являются веса соответствующих слов, отражающие их значимость для этого документа:
где N -общее количество различных слов во всех документах, -вес j-ого слова в i-ом документе. Хотя такой выбор признакового пространства является наиболее распространенным, могут применяться и другие характеристики текстов, например, частота появления различных пар символов или частота появления тех или иных частей речи [17]. j i w В работе [1] векторная модель использована при решении задачи обнаружения дубликатов. При этом вектором представляется не отдельный документ, а пара документов из обучающей выборки. В качестве значения элемента вектора здесь используется произведение весов соответствующего слова в первом и втором документе пары. Полученный вектор подвергается классификации с помощью метода опорных векторов (support vector machine, SVM) [15] для принятия решения о наличии или отсутствии дублирования.
Несколько иной подход предложен в статье [13]. Он также использует векторное представление пары документов, но вектор в целом здесь характеризует схожесть элементов пары, а его отдельные компонентыблизость документов с точки зрения различных критериев. Пары, отмеченные в обучающей выборке как «дубликаты» или «не дубликаты», представлены двумя кластерами точек многомерного пространства. Таким образом, задача обнаружения дублей сводится к классификации новых пар документов, то есть отнесению их к одному из этих кластеров. Классификация основана на выборе кластера, центроид которого находится ближе к точке, представляющей новую пару документов.
В [16] решается несколько иная, но близкая задача: формирование из группы документов, описывающих некоторое событие, одного сообщения, содержащего только оригинальную информацию о событии. Для этого выполняется поиск и исключение из текстов документов фрагментов, содержащих идентичную информацию. С этой целью выполняется представление документов цепочками значимых слов, сравнение этих цепочек и обнаружение их схожих участков.
У сигнатурных методов и алгоритмов, использующих шинглы, есть некоторые схожие черты: эти методы минимизируют вычислительную сложность операции сравнения документов. Поэтому они находят широкое применение в системах, работающих с гигантскими объемами данных (например, в поисковых системах). Обратной стороной медали является их узкая направленностьэти методы и модели представления текстов, которыми они оперируют (шинглы, сигнатуры), пригодны лишь для устранения дублей и не могут быть использованы для других задач. Однако, как было показано выше, очищенные от дубликатов данные впоследствии подвергаются разнообразной обработке и анализу. Поэтому представляется целесообразным применять для обнаружения дублей алгоритмы и модели, которые могут быть использованы для задач интеллектуальной обработки текстов.
Модель и метод, представленные в [16], также предназначены исключительно для решения конкретной задачи, а именно устранения идентичных фрагментов сообщений. Кроме того, для эффективного использования этого метода документы должны быть предварительно распределены по кластерам, соответствующим событиям. В нашей же ситуации устранение дублей, напротив, выполняется на этапе предварительной обработки данных перед использованием интеллектуальных аналитических методов, таких как обнаружение событий.
В целях обеспечения возможности применения разрабатываемой модели документов для решения различных задач из области Text Mining, было решено использовать в качестве её основы векторное представление текстов. Однако использование слов документов в качестве признаков (1) позволяет сравнить сообщения лишь с точки зрения состава слов, что недостаточно для принятия правильного решения. Во многих предметных областях существенную роль играют и другие критерии (см. 2.2), и эти критерии должны быть включены в модель.
Таким образом, модель должна предусматривать возможность сравнения документов по различным признакам. Окончательно же решение должно приниматься на основе анализа пары документов с точки зрения всех критериев. Исходя из этого, удобно представить пару документов вектором (2), элементами которого являются результаты сравнения документов по соответствующим признакам:
) , (
, ), другойотсутствие ( ):
С учетом выбранного подхода, процесс обнаружения дублей можно разбить на следующие этапы (рис. 2):
1. Построение модели документа, отражающей характеристики новостного сообщения с точки зрения каждого из выбранных критериев. 1200 пар документов были проанализированы экспертами вручную. В результате выполненного анализа были выявлены следующие критерии, характеризующие модель распознавания дубликатов.
В большинстве случаев определяющее значение имеет близость текстов. Прежде всего, это характерно для общественно-политических новостей, вклад которых в суммарную информацию, передаваемую новостным потоком, определяется оригинальностью их текстового содержания.
На первый взгляд, в целях обнаружения дубликатов лучше использовать евклидово расстояние, поскольку размер должен играть роль при сравнении документов: тексты существенно различающейся длины с очень низкой вероятностью являются нечеткими дубликатами. Однако для обеспечения большей гибкости системы было решено разделить оценку документов с содержательной и структурной точки зрения. Чтобы сделать оценку содержательной близости документов независимой от других характеристик, решено использовать для сравнения косинусную меру близости. При использовании неотрицательных весов слов косинусная мера принимает значения в интервале [0, 1], поэтому в качестве оценки различия векторов используется значение
Отдельно при принятии решения учитываются заголовки сообщений, причем их роль значительно варьируется в зависимости от предметной области. При перепечатке новостей общественнополитической тематики с одного сайта на другой нередко изменяется только заголовок, причем иногдавесьма существенно. В таком случае наличие дублирования может быть обнаружено на основе близости остального текста новостей. Однако для сообщений другого типа (например, правового характера), различие заголовков имеет решающее значение, и такие документы не должны признаваться дубликатами, несмотря на близкое содержание.
В модели заголовок текста представляется аналогично основному тексту (4), с той лишь разницей, что в качестве элементов вектора используются слова, встречающиеся в заголовках документов коллекции:
, где общее количество различных слов в заголовках всех документов, вес j-го слова в заголовке i-го документа.
Такая мера близости принимает во внимание лишь количество совпадающих и различающихся предложений, но не учитывает, какие именно предложения совпадают и различаются. Однако совпадение значимых, содержательных предложений должно иметь больший вес, чем одновременное появление в обоих документах одинаковых коротких и незначительных фраз. В связи с этим вместо количества предложений используется их суммарный вес. Вес каждого предложения рассчитывается как сумма весов составляющих его слов.
Кроме того, представленная мера является симметричной, и потому она плохо подходит для сравнения документов, один из которых получен из другого путем удаления нескольких предложений: в этом случае первое сообщение содержит дополнительную информацию относительно второго, но второе не имеет оригинальных данных относительно первого. Чтобы учесть требуемую несимметричность, было решено использовать меру включения вместо меры сходства:
(
Для оценки различия документов с точки зрения предложений используются значения и . ) , ( 1
Кроме документов, содержащих только текстовую информацию, часто встречаются и те, которые включают числовые данные. В ряде случаев даже незначительное изменение этих данных может существенно повлиять на содержание сообщения. Примером таких документов являются новостные сообщения из области экономики (новости о со-стоянии фондового рынка) или спорта (сообщения о результатах соревнований). Такие документы не должны признаваться дубликатами даже при полном совпадении их текста.
Для сравнения документов с точки зрения числовых значений каждое сообщение представляется набором чисел, извлеченных из его текста:
, где количество различных чисел в i-ом документе. Для выполнения оценки сходства таких наборов также используется мера включения, однако элементы сравниваемых множеств не являются взвешенными, а потому учитывается лишь количество одинаковых и различающихся числовых значений:
Информация в сообщении может быть представлена не только текстом или числовыми данными, но и различными объектами, включенными в текст документафотографиями, видеороликами, ссылками на сторонние источники. Присутствие в документе дополнительных фото-и видеоматериалов значительно повышает вероятность его оригинальности При сравнении фотоматериалов, включенных в сообщение, возникают сложности: определить идентичность фотографий в двух документах проблематично, поскольку одинаковые с точки зрения эксперта фотографии могут иметь различные URL и разный размер. Поэтому было принято решение учитывать не сами фотографии, а их количество в документе:
. Также в модель включается компонент, отражающий количество ссылок, присутствующих в тексте сообщения:
. Различие документов с точки зрения этих критериев определяется как разность соответствующих значений:
, .
Существенным фактором, влияющим на принятие решения о наличии или отсутствии дублирования, является разница во времени публикации сообщений. Так, при дублировании новостных статей перепечатыванию обычно подвергаются свежие новости, недавно опубликованные на сайте первоисточника. С увеличением интервала между моментами появления документов в сети вероятность дублирования быстро убывает В модели эта характеристика сообщения представлена посредством POSIX-времени момента публикации (которое определяется как количество секунд, прошедших с полуночи 1 января 1970 года до момента, когда документ был опубликован источником):
. Различие между документами определяется как разность между моментами публикации сообщений в секундах:
.
При анализе документов эксперты обращают внимание на источники сообщений, при этом они руководствуются своими представлениями об авторитетности источников. Статья из авторитетного источника (который обычно публикует оригинальные материалы) имеет существенно меньшую вероятность быть признанной дубликатом, чем документ, полученный из источника, регулярно занимающегося перепечаткой чужих сообщений.
Авторитетность источника
, отражающим вероятность публикации им оригинального сообщения. Это значение может быть задано экспертом вручную или получено на основе обучающей выборки как соотношение количества оригинальных документов, поступивших от источника, к общему количеству опубликованных им сообщений.
В модель документа включается компонент, отражающий авторитетность источника, опубликовавшего этот документ:
, где функция, устанавливающая соответствие между документом и его источником.
)) ( (
Таким образом, модель документа представляет собой совокупность компонентов, характеризующих сообщение с точки зрения различных критериев:
6 Метод обнаружения дубликатов
Ввиду вышеуказанной несимметричности мер сходства, используемых для некоторых критериев, результатом сравнения двух документов являются два различных вектора и , характеризующие степень отличия первого и второго сообщения друг от друга. Каждый из этих векторов интерпретируется с помощью функции
Для интерпретации результата сравнения необходимо решить задачу бинарной классификации, то есть отнести вектор к классу или . Для настройки параметров классификатора используется обучающая выборканабор векторов, каждый из которых снабжен меткой , обозначающей класс, к которому принадлежит этот вектор.
Задача бинарной классификации состоит в том, чтобы для вновь поступившего на исследование вектора определить класс, к которому он принадлежит, то есть значение m. Для её решения будем использовать метод опорных векторов (SVM). Этот метод основан на построении в K-мерном пространстве (K -1)-мерной гиперплоскости, разделяющей объекты классов
зависимости от расположения вектора относительно этой гиперплоскости, выполняется его отнесение к одному из классов. Возможны следующие результаты интерпретации:
. Оба документа являются дублями друг относительно друга. То есть, ни один из них не содержит оригинальных данных относительно другого.
На основе полученных результатов принимается решение о дальнейших действиях в отношении документов. Так, в разработанной системе решалась задача проверки документов в момент их поступления от источника, при этом загружаемые сообщения сравнивались на предмет дублирования с документами, уже загруженными в базу. Поэтому интерес представлял лишь один из результатов интерпретацииявляется ли загружаемый документ дубликатом ранее полученного сообщения. Однако при обработке готовой коллекции документов с целью обнаружения и устранения дубликатов важно выявить все пары сообщений, в которых имеет место дублирование, для чего требуется использовать оба результата.
Предложенный метод выявления нечетких дубликатов имеет существенный недостатоквысокую вычислительную сложность. Каждое новое сообщение подвергается сравнению со всеми ранее загруженными, и при каждом сравнении выполняется расчет близости документов по множеству критериев. Однако очевидно, что в большинстве случаев в таком тщательном анализе нет необходимостисильно различающиеся по тексту документы с высокой вероятностью различны и по содержанию. Следовательно, нужно исключать из рассмотрения те из ранее загруженных новостей, которые слишком сильно отличаются от текущей.
С этой целью вышеописанный метод предваряется процедурой отбора документов, дубликатом которых может быть текущая новость (то есть, отбора кандидатов на роль оригинала этой новости). Эта процедура, по сути, также решает задачу обнаружения дубликатов, причем основными требованиями, предъявляемыми к ней, являются минимальная вычислительная сложность и максимальная полнота (поскольку отброшенные из числа кандидатов документы далее рассматриваться не будут).
В качестве такой процедуры рассматривались представленные в работе [12] приближенные методы обнаружения дубликатов, имеющие высокую производительность. Ввиду наличия набора взвешенных слов, было решено использовать для описания сообщения сигнатуру, представляющую собой строку, состоящую из сцепленных в алфавитном порядке нескольких наиболее «тяжелых» слов документа. При этом процедура отбора кандидатов заключается в выборе из ранее загруженных документов тех, которые имеют такую же сигнатуру, как и текущая новость. Такие пары документов с совпадающими сигнатурами должны быть подвергнуты проверке основным методом, представленным в предыдущем подразделе. В работе [12] предложено использовать сигнатуры из 6 слов, но это приводит к низкому значению полноты (0.54). В целях получения высокой полноты, было решено сократить количество слов, составляющих сигнатуру, до двух. Проведенный эксперимент доказывает целесообразность многокритериального сравнения использовании всех критериев достигаются более высокие показатели качества (F-мера в зоне насыщения равна 0,82), чем при анализе документов только с точки зрения слов (0,67) или параграфов (0,64).
При анализе результатов эксперимента было выявлено несколько факторов, негативно сказ хся на качестве. Одним из них является человеческий фактор: каждый эксперт, принимавший участие в подготовке обучающей и тестовой выборок, имеет свое представление о том, какие документы являются информативно необходимыми, а какиенет, в результате чего возникают конфликты в суждениях экспертов. Также эксперимент показал, что система не может обнаруживать дублирование в случае переписывания оригинального текста без изменения его содержания (рерайтинга), что говорит о необходимости доработки модели для обнаружения такого рода дублирования. Наконец, при проведении эксперимента была выполнена попытка настройки единой модели распознавания для всех документов, загружаемых с новостных сайтов. Но эти документы принадлежат различным предметным областямсреди общественно-политических новостей попадаются экономические, спортивные, юридические. Для повышения качества работы эти документы должны анализироваться с использованием специализированных моделей распознавания.
Проведенный эксперимент также показал, что среднее время, затрачиваемое на анализ пары тов основным методом, составляет 5 мс. С учетом высокой эффективности метода предварительной фильтрации это означает, что система способна обрабатывать 10 000-50 000 документов в час (в зависимости от количества загруженных ранее сообщений, с которыми требуется сравнивать новые документы).
ndreev, D. Berezkin, I. Kozlov, K. Sima The problem of duplicate documents elimination m a stream of text messages is considered. lticriterion model of text document is given. Criteria are chosen to properly represent documents from different domains. An approach for duplicates detection based on binary classification is proposed. A method of candidates preliminary filtration is proposed in order to reduce the computational complexity of the approach.