Метод обнаружения дубликатов в потоке текстовых документов © А.М. Андреев © Д.В. Березкин © И.А. Козлов © К.В. Симаков МГТУ им. Н.Э. Баумана, Москва arkandreev@gmail.com dmitryb2007@yandex.ru kozlovilya89@gmail.com skv@ixlab.ru ние таких документов в коллекцию снижает её каче- Аннотация ство [12, 16]. Работа посвящена решению задачи устра- В данной статье рассматривается решение задачи нения дублирующихся документов из пото- обнаружения дубликатов в потоке текстовых сооб- ка текстовых сообщений. Приведена много- щений. Особое внимание уделяется обеспечению критериальная модель документа, предло- возможности использования разработанного метода жен метод обнаружения дубликатов на ос- для обработки документов из различных предмет- нове бинарной классификации с помощью ных областей. метода опорных векторов. Основной акцент сделан на обеспечении применимости мето- 2 Постановка задачи да для обработки документов из разных предметных областей. Предложен способ 2.1 Функционирование системы сбора снижения вычислительной сложности мето- и обработки новостной информации да посредством предварительной фильтра- В работе [9] авторами было предложено решение ции кандидатов. задачи качественного автоматического сбора ново- стных данных из Интернет-источников, предпола- 1 Введение гающего извлечение с веб-страницы текста новости, В настоящее время во многих предметных об- а также сопутствующих метаданных, включающих ластях существует потребность в формировании название, дату публикации, автора новости и др. больших текстовых коллекций. При этом произво- При этом осуществляется контроль корректности дится сбор текстовой информации из открытых Ин- извлекаемой информации, то есть проверка соответ- тернет-источников, а также специализированных ствия текстов загружаемых документов исходным ресурсов. Основной областью использования созда- текстам новостей на сайте. ваемых таким образом хранилищ документов явля- Текстовые данные, извлеченные с веб-сайтов, ется интеллектуальная обработка текстов, которую, подвергаются обработке различными методами ин- как правило, можно отнести к классу Text Mining. теллектуального анализа [7-8], такими как автома- С ростом количества разнообразных источников тическая классификация и кластеризация докумен- данных в сети Интернет (новостные сайты, блоги, тов, извлечение знаний и фактов из естественно- социальные сети) всё более серьезной проблемой языковых текстов, выявление трендов и прогноз становится дублирование информации. Сообщения, развития ситуаций. публикуемые одним источником, зачастую много- Для эффективного применения перечисленных кратно перепечатываются другими (в исходном виде методов обработки текстовых данных необходимо или с небольшими изменениями). В результате, при обеспечить качество анализируемой коллекции до- выполнении автоматического сбора документов из кументов. Помимо вышеупомянутой корректности многочисленных источников в формируемой тек- каждого конкретного текста, качество коллекции стовой коллекции накапливаются идентичные или подразумевает требование оригинальности состав- близкие по содержанию документы – дубликаты. В ляющих её новостей. Присутствие в обрабатывае- некоторых задачах наличие дубликатов должно учи- мом наборе одинаковых или очень близких по со- тываться – например, при определении значимости держанию документов может отрицательно сказать- сообщений [14]. Но в большинстве случаев попада- ся на качестве обработки. Это касается работы мо- дулей, выполняющих статистический анализ доку- Труды 16-й Всероссийской научной конференции ментов, например, модуля анализа трендов. Его ра- «Электронные библиотеки: перспективные методы и бота основана на выявлении в коллекции новостей, технологии, электронные коллекции» — RCDL-2014, относящихся к анализируемой ситуации, и опреде- Дубна, Россия, 13–16 октября 2014 г. лении зависимости частоты встречаемости таких документов от времени. Появление дублей приведет 181 к многократному учету модулем идентичных ново- Она должна анализировать каждый загружаемый стей, что повлечет за собой некорректный вид по- документ и принимать решение о его оригинально- строенной зависимости. сти. Для этого необходимо сравнить его с загружен- Для обеспечения оригинальности документов, ными ранее новостями и определить, является ли он составляющих текстовую коллекцию, в систему нечетким дубликатом одной из них. При обнаруже- сбора необходимо встроить подсистему, задачей нии дубля он должен быть удален до этапа загрузки которой является оперативное обнаружение и уда- данных в базу данных. ление из коллекции нечетких дубликатов (рис. 1). Рис. 1. Место подсистемы обнаружения дубликатов в системе автоматизированного сбора и анализа новостной информации 2.2 Особенности решаемой задачи информативно необходим постольку, поскольку вносит свой уникальный, неповторимый в других Если проблема обнаружения и удаления полных элементах, вклад в суммарную информацию, пере- дублей тривиальна, то при необходимости распо- даваемую высказыванием». Таким образом, задача знавать нечеткие дубликаты (то есть, документы, обнаружения нечетких дубликатов состоит в распо- имеющие различный текст, но близкие по содержа- знавании и удалении сообщений, не являющихся нию) возникают значительные сложности. информативно-необходимыми. В связи с явлением частичного дублирования в Установить информативную необходимость и работе [10] предлагается понятие информативной ценность некоторого высказывания возможно толь- необходимости элемента высказывания: «Всякий ко с учетом соответствующего ситуативного кон- частично-дублетный элемент, если он отвечает текста. Так, при ручной проверке документов экс- коммуникативной задаче высказывания, признается перт, определяя наличие или отсутствие дублирова- информативно-необходимым в той же мере, что и ния, принимает решение с учетом предметной об- прочие, недублетные элементы речи: такой элемент ласти и характера документов, составляющих ана- 182 лизируемую коллекцию. Например, при работе с оригинального алгоритма предложили несколько юридическими документами особое внимание способов сэмплирования множества. должно уделяться метаданным – для текстов такого Дальнейшим развитием этого метода стал алго- типа два документа с практически идентичным со- ритм «супершинглов» [4]. Его идея состоит в при- держанием, но различающимися названиями и да- менении к элементам множества шинглов различ- тами публикации не могут считаться дублями. Дру- ных хэш-функций и выборе для каждой из них шин- гой подход используется при анализе экономиче- гла, минимизирующего её значение. Из выбранных ских новостей, например, сводок о состоянии фон- шинглов формируются группы, именуемые «супер- дового рынка – дубликатами не должны признавать- шинглами». Два документа считаются похожими, ся документы, имеющие одно и то же название и если мера сходства их наборов «супершинглов» не одинаковый текст, но различающиеся числовыми меньше заданного значения. данными (значениями курсов валют). Таким образом, в разных случаях эксперт срав- 3.2 Сигнатурные методы нивает документы с точки зрения различных крите- Другим распространенным классом приближен- риев (близость текстового содержания, сходство ных подходов к поиску нечетких дубликатов явля- названий, разница во времени публикации), то есть ется класс сигнатурных методов. Подробный обзор использует различные модели распознавания дубли- алгоритмов этого класса выполнен в [12]. Общей катов в зависимости от предметной области и кон- идеей является представление документа с помо- текста коммуникационных сообщений. Поэтому не щью одного числового значения – «сигнатуры», что представляется возможным выработать единую сис- сводит проверку схожести документов к сравнению тему правил для обнаружения нечеткого дублирова- их сигнатур. Совпадение этих значений означает, ния сразу для всех случаев. Следовательно, разраба- что документы являются нечеткими дубликатами. тываемая подсистема должна иметь возможность Существует множество способов вычисления сигна- гибкой настройки на разные предметные области, тур документов: что позволит ей моделировать деятельность экспер- та по распознаванию дублей с использованием раз-  использование хэш-функции, вычисленной личных моделей. Поскольку система сбора выпол- для всего документа (это позволяет обнаруживать няет извлечение документов из множества источни- лишь точные дубликаты); ков, которые относятся к различным предметным  использование хэш-функции, вычисленной областям, необходимо обеспечить возможность ра- для строки, полученной из сцепленных в алфавит- боты с несколькими моделями распознавания дуб- ном порядке нескольких слов документа с наиболь- ликатов одновременно. шими значениями весов, рассчитанных различными Еще одной проблемой, с которой приходится методами (например, TF, TF-IDF и OptFreq); столкнуться при решении задачи устранения дубли-  использование хэш-функции, вычисленной для катов, является большой объем обрабатываемых строки, полученной из сцепленных в алфавитном по- данных. Наличие в коллекции сотен тысяч докумен- рядке нескольких наиболее длинных или «тяжелых» тов делает весьма трудоемким анализ каждого ново- (то есть, состоящих из слов с наибольшим суммарным го сообщения путем сравнения его с каждым из ра- значением весов) предложений документа. нее загруженных. Эта проблема может быть решена Несколько иной подход предложен в работе [14]: с помощью приближенных методов, но их примене- здесь сигнатура представляет собой не хэш-сумму ние ведет к снижению качества обнаружения дубли- цепочки слов, а саму цепочку. При этом документы катов, то есть уменьшению точности и полноты [12]. признаются дубликатами при совпадении заданного При разработке предлагаемого подхода решалась числа элементов их цепочек. задача совмещения высокого качества и низкой вы- числительной сложности проверки документов. 3.3 Методы, использующие векторные модели 3 Обзор методов обнаружения дублей В задачах интеллектуальной обработки текстов (Text Mining) широко используются векторные модели 3.1 Методы, основанные на использовании текстовых документов. При этом каждое сообщение шинглов представляется в виде вектора в многомерном призна- ковом пространстве D  ( D1 , D 2 , ..., D N ) , каждый Одним из наиболее популярных методов, ис- элемент которого отражает некоторую характеристику пользуемых при поиске нечетких дубликатов веб- документа. документов, является алгоритм шинглов [2, 5]. Он основан на представлении документа в виде множе- В качестве элементов могут использоваться сло- ства всевозможных последовательностей фиксиро- ва, встречающиеся в текстах коллекции [11]. При ванной длины k, состоящих из соседних слов. Такие этом значениями элементов вектора (1), представ- последовательности называются «шинглами». Два ляющего некоторый документ, являются веса соот- документа считаются похожими, если их множества ветствующих слов, отражающие их значимость для шинглов значительно пересекаются. Количество этого документа: шинглов примерно равно длине документа в словах, d i  ( w1i , wi2 , ..., win ) , (1) поэтому в целях повышения эффективности авторы 183 где N – общее количество различных слов во всех подвергаются разнообразной обработке и анализу. документах, wij – вес j-ого слова в i-ом документе. Поэтому представляется целесообразным применять для обнаружения дублей алгоритмы и модели, кото- Хотя такой выбор признакового пространства явля- рые могут быть использованы для задач интеллекту- ется наиболее распространенным, могут применять- альной обработки текстов. ся и другие характеристики текстов, например, час- тота появления различных пар символов или частота Модель и метод, представленные в [16], также появления тех или иных частей речи [17]. предназначены исключительно для решения кон- кретной задачи, а именно устранения идентичных В работе [1] векторная модель использована при фрагментов сообщений. Кроме того, для эффектив- решении задачи обнаружения дубликатов. При этом ного использования этого метода документы долж- вектором представляется не отдельный документ, а ны быть предварительно распределены по класте- пара документов из обучающей выборки. В качестве рам, соответствующим событиям. В нашей же си- значения элемента вектора здесь используется произ- туации устранение дублей, напротив, выполняется ведение весов соответствующего слова в первом и на этапе предварительной обработки данных перед втором документе пары. Полученный вектор подвер- использованием интеллектуальных аналитических гается классификации с помощью метода опорных методов, таких как обнаружение событий. векторов (support vector machine, SVM) [15] для приня- тия решения о наличии или отсутствии дублирования. 4 Предложенный подход к обнаружению Несколько иной подход предложен в статье [13]. Он также использует векторное представление пары дубликатов документов, но вектор в целом здесь характеризует В целях обеспечения возможности применения схожесть элементов пары, а его отдельные компо- разрабатываемой модели документов для решения ненты – близость документов с точки зрения раз- различных задач из области Text Mining, было ре- личных критериев. Пары, отмеченные в обучающей шено использовать в качестве её основы векторное выборке как «дубликаты» или «не дубликаты», представление текстов. Однако использование слов представлены двумя кластерами точек многомерно- документов в качестве признаков (1) позволяет го пространства. Таким образом, задача обнаруже- сравнить сообщения лишь с точки зрения состава ния дублей сводится к классификации новых пар слов, что недостаточно для принятия правильного документов, то есть отнесению их к одному из этих решения. Во многих предметных областях сущест- кластеров. Классификация основана на выборе кла- венную роль играют и другие критерии (см. 2.2), и стера, центроид которого находится ближе к точке, эти критерии должны быть включены в модель. представляющей новую пару документов. Таким образом, модель должна предусматривать 3.4 Метод, основанный на выявлении близких возможность сравнения документов по различным признакам. Окончательно же решение должно при- по смыслу частей текстов ниматься на основе анализа пары документов с точ- В [16] решается несколько иная, но близкая зада- ки зрения всех критериев. Исходя из этого, удобно ча: формирование из группы документов, описы- представить пару документов (d i , d j ) вектором (2), вающих некоторое событие, одного сообщения, со- элементами которого являются результаты сравне- держащего только оригинальную информацию о ния документов по соответствующим признакам: событии. Для этого выполняется поиск и исключе- ние из текстов документов фрагментов, содержащих  i , j  (  i1, j ,  i2, j , ...,  ik, j ) , (2) идентичную информацию. С этой целью выполняет- ся представление документов цепочками значимых где  i,k j характеризует сходство документов d i и слов, сравнение этих цепочек и обнаружение их d j по k-му критерию. На основе этого вектора при- схожих участков. нимается решение о наличии или отсутствии дубли- 3.5 Анализ рассмотренных методов обнаружения рования. Для этого необходимо задать функцию, дубликатов выполняющую интерпретацию вектора i, j , то есть У сигнатурных методов и алгоритмов, исполь- определяющую вектор в один из двух классов, один зующих шинглы, есть некоторые схожие черты: эти из которых означает наличие дублирования (обо- методы минимизируют вычислительную сложность значим его M  ), другой – отсутствие ( M  ): операции сравнения документов. Поэтому они на- ходят широкое применение в системах, работающих 1,  i , j  M  ; D(  )   (3) с гигантскими объемами данных (например, в по- 0,  i , j  M  . исковых системах). Обратной стороной медали яв- ляется их узкая направленность – эти методы и мо- С учетом выбранного подхода, процесс обнару- дели представления текстов, которыми они опери- жения дублей можно разбить на следующие этапы руют (шинглы, сигнатуры), пригодны лишь для уст- (рис. 2): ранения дублей и не могут быть использованы для 1. Построение модели документа, отражающей других задач. Однако, как было показано выше, характеристики новостного сообщения с точки зре- очищенные от дубликатов данные впоследствии ния каждого из выбранных критериев. 184 2. Сравнение моделей двух документов и полу- 3. Интерпретация вектора с помощью решаю- чение результирующего вектора i, j . щей функции D(  i , j ) . di dj i , j Рис. 2. Этапы обнаружения дубликатов Для обеспечения возможности сравнения соста- 5 Модель документа вов слов документов, модель должна включать век- Важным этапом решения задачи является выбор торное представление текста сообщения (1). Если критериев для сравнения документов. Набор крите- слово не встречается в документе, его вес равен ну- риев должен быть достаточно выразительным, что- лю. Для остальных слов вес рассчитывается по ме- бы обеспечивать возможность гибкой настройки тоду TF-IDF с использованием алгоритма Okapi модели в соответствии со спецификой различных BM25 [6]. Рассчитанный таким образом вес слова предметных областей. Для определения набора кри- wt = tf * idf пропорционален частоте его употребле- териев было проведено исследование выборки тек- ния в документе tf и обратно пропорционален часто- стовых документов, автоматически собираемых из те употребления слова в других документах коллек- различных Интернет-источников. ции idf. В результате, модель текста документа d i В качестве источников были выбраны 35 сайтов представляет собой вектор: по различной тематике: основные новостные сайты, w d iw  ( wi1 , wi2 , ..., wiN ) , (4) публикующие материалы общественно- политической и экономической тематики, офици- где N w – общее количество различных слов во всех альные сайты органов государственной власти РФ, некоторые сайты органов законодательной и испол- документах, wij – вес j-го слова в i-ом документе. нительной власти субъектов РФ. Такой набор сайтов Векторное представление позволяет использо- позволил охватить значительное число тем и типов вать для сравнения текстов простые алгебраические информационных сообщений (ленты новостей, ана- методы. В качестве меры сходства часто используют литические статьи и обзоры, документы правового евклидову метрику – расстояние между двумя точ- характера, документы, содержащие финансово- ками в многомерном пространстве, вычисляемое по экономические показатели). теореме Пифагора. Однако она плохо подходит для 1200 пар документов были проанализированы сравнения документов, похожих по содержанию, но экспертами вручную. В результате выполненного значительно различающихся по размеру. Поэтому анализа были выявлены следующие критерии, ха- при решении задач информационного поиска более рактеризующие модель распознавания дубликатов. распространен другой способ сравнения векторов, называемый косинусной мерой. Близость векторов 5.1 Содержание текста оценивается на основании значения косинуса угла  между ними, что позволяет не учитывать при срав- В большинстве случаев определяющее значение нении длину векторов: имеет близость текстов. Прежде всего, это харак- N терно для общественно-политических новостей, вклад которых в суммарную информацию, переда- w w n i n j . (5) ваемую новостным потоком, определяется ориги- simcos (d , d )  i w w j n 1 N N нальностью их текстового содержания.  (w )  (w ) n 1 n 2 i n 1 n 2 j 185 На первый взгляд, в целях обнаружения дубли- предложений и абзацев в i-ом документе. В свою оче- катов лучше использовать евклидово расстояние, редь, каждое предложение представляет собой после- поскольку размер должен играть роль при сравне- довательность слов, а потому может быть представле- нии документов: тексты существенно различающей- но векторной моделью cij  (cij ,1, cij ,2 , ..., cij , N ) , где w ся длины с очень низкой вероятностью являются нечеткими дубликатами. Однако для обеспечения cij , k – вес k-го слова в j-ом предложении i-ого доку- большей гибкости системы было решено разделить мента. Аналогичным образом представлен каждый оценку документов с содержательной и структурной w абзац документа: pij  ( pij ,1, pij , 2 , ..., pij , N ) . точки зрения. Чтобы сделать оценку содержатель- ной близости документов независимой от других Поскольку структурные элементы представлены характеристик, решено использовать для сравнения множествами, для определения их сходства можно косинусную меру близости. При использовании не- использовать коэффициент Жаккара. Так, для пред- отрицательных весов слов косинусная мера прини- ложений близость документов будет равна мает значения в интервале [0, 1], поэтому в качестве оценки различия векторов используется значение dic  dic simcj (dic , d cj )  . (7) iw, j  1  simcos (diw , d wj ) . (6) dic  dic 5.2 Содержание заголовка Такая мера близости принимает во внимание лишь количество совпадающих и различающихся Отдельно при принятии решения учитываются предложений, но не учитывает, какие именно пред- заголовки сообщений, причем их роль значительно ложения совпадают и различаются. Однако совпа- варьируется в зависимости от предметной области. дение значимых, содержательных предложений При перепечатке новостей общественно- должно иметь больший вес, чем одновременное по- политической тематики с одного сайта на другой явление в обоих документах одинаковых коротких и нередко изменяется только заголовок, причем ино- незначительных фраз. В связи с этим вместо коли- гда – весьма существенно. В таком случае наличие чества предложений используется их суммарный дублирования может быть обнаружено на основе вес. Вес каждого предложения рассчитывается как близости остального текста новостей. Однако для сумма весов составляющих его слов. сообщений другого типа (например, правового ха- Кроме того, представленная мера является сим- рактера), различие заголовков имеет решающее зна- метричной, и потому она плохо подходит для срав- чение, и такие документы не должны признаваться нения документов, один из которых получен из дру- дубликатами, несмотря на близкое содержание. гого путем удаления нескольких предложений: в В модели заголовок текста представляется ана- этом случае первое сообщение содержит дополни- логично основному тексту (4), с той лишь разницей, тельную информацию относительно второго, но что в качестве элементов вектора используются сло- второе не имеет оригинальных данных относитель- ва, встречающиеся в заголовках документов коллек- но первого. Чтобы учесть требуемую несимметрич- t ции: d it  (ti1 , ti2 , ..., t iN ) , где N t – общее количество ность, было решено использовать меру включения вместо меры сходства: различных слов в заголовках всех документов, tij – Nw вес j-го слова в заголовке i-го документа.  [ ck ] Сравнение составляющих моделей, отражающих c d ic  d ic k 1 c siminc (dic , d cj )  . (8) содержание заголовков, также выполняется анало- Nw гично сравнению содержания документов (6):  [ c ] k cd ic k 1   1  simcos (d , d ) . t i, j i t t j Для оценки различия документов с точки зрения 5.3 Предложения и абзацы предложений используются значения ic, j  1  siminc c (dic , d cj ) и  cj ,i  1  siminc c (d cj , dic ) . Помимо оценки близости текстового содержания документов в целом, эксперт обращает особое вни- Аналогичным образом выполняется сравнение мание на наличие в сообщениях идентичных струк- абзацев, результатом которого являются значения турных элементов текстов – предложений и абзацев. меры различия ip, j и  jp,i . Это связано с тем, что при перепечатке некоторым источником ранее опубликованного документа мно- 5.4 Числовые данные гие из этих элементов переносятся в текст-дубликат без изменений. Кроме документов, содержащих только тексто- Для сравнения структурных элементов текста вую информацию, часто встречаются и те, которые документ представляется множествами своих включают числовые данные. В ряде случаев даже c незначительное изменение этих данных может су- предложений d ic  (ci1 , ci2 , ..., ciN i ) и абзацев щественно повлиять на содержание сообщения. Np Примером таких документов являются новостные di p  ( p1i , pi2 , ..., pi i ) , где N ic и Nip – количество сообщения из области экономики (новости о со- 186 стоянии фондового рынка) или спорта (сообщения о При сравнении фотоматериалов, включенных в результатах соревнований). Такие документы не сообщение, возникают сложности: определить иден- должны признаваться дубликатами даже при пол- тичность фотографий в двух документах проблема- ном совпадении их текста. тично, поскольку одинаковые с точки зрения экс- Для сравнения документов с точки зрения число- перта фотографии могут иметь различные URL и вых значений каждое сообщение представляется разный размер. Поэтому было принято решение набором чисел, извлеченных из его текста: учитывать не сами фотографии, а их количество в N nd документе: diim . Также в модель включается компо- din  {ni1, ni2 , ..., ni i } , где N ind – количество различ- нент, отражающий количество ссылок, присутст- ных чисел в i-ом документе. Для выполнения оцен- ки сходства таких наборов также используется мера вующих в тексте сообщения: d ih . Различие доку- включения, однако элементы сравниваемых мно- ментов с точки зрения этих критериев определяется жеств не являются взвешенными, а потому учитыва- как разность соответствующих значений: ется лишь количество одинаковых и различающихся iim ,j  d im i  d im j ,  h i, j  d i h  d h j . числовых значений: din  din 5.6 Дата и время публикации n siminc (din , d nj )  . (9) din Существенным фактором, влияющим на приня- тие решения о наличии или отсутствии дублирова- Расстояние между документами по данному ния, является разница во времени публикации со- критерию равно in, j  1  siminc n (din , d nj ) . общений. Так, при дублировании новостных статей перепечатыванию обычно подвергаются свежие но- Для некоторых предметных областей важен не вости, недавно опубликованные на сайте первоис- только состав набора чисел, но и порядок их следо- точника. С увеличением интервала между момента- вания в тексте документа. Это относится, в частно- ми появления документов в сети вероятность дуб- сти, к спортивным новостям, где разные последова- лирования быстро убывает тельности одних и тех же чисел могут соответство- В модели эта характеристика сообщения пред- вать различным результатам соревнований (напри- ставлена посредством POSIX-времени момента пуб- мер, два сета в теннисном матче, завершившиеся со ликации (которое определяется как количество се- счетом «6:4» и «4:6»). В таком случае для представ- кунд, прошедших с полуночи 1 января 1970 года до ления сообщения используется кортеж момента, когда документ был опубликован источ- N na din  {n1i , ni2 , ..., ni i } , где N ind – общее количество ником): d idt . Различие между документами опреде- чисел в i-ом документе. ляется как разность между моментами публикации В этом случае для сравнения документов необ- сообщений в секундах:  idt, j  d idt  d dtj . ходимо выбрать меру различия, учитывающую по- рядок следования элементов. Такой мерой является 5.7 Авторитетность источника расстояние Дамерау–Левенштейна [3], равное коли- честву операций вставки, удаления, замены и пере- При анализе документов эксперты обращают становки элементов, необходимых для преобразова- внимание на источники сообщений, при этом они ния одной последовательности символов (в данном руководствуются своими представлениями об авто- случае – чисел) в другую. Эта мера является моди- ритетности источников. Статья из авторитетного фикацией расстояния Левенштейна, отличающаяся источника (который обычно публикует оригиналь- наличием операции перестановки двух соседних ные материалы) имеет существенно меньшую веро- символов (транспозиции). Это важно для нашей за- ятность быть признанной дубликатом, чем доку- дачи, поскольку при перепечатке документа иногда мент, полученный из источника, регулярно зани- изменяется порядок следования его абзацев и пред- мающегося перепечаткой чужих сообщений. ложений, что приводит к появлению перестановок в Авторитетность источника s представляется последовательности чисел. значением aut ( s )  [0, 1] , отражающим вероятность Расстояние между сообщениями при использо- публикации им оригинального сообщения. Это вании этой меры равно in, j  dist DL (din , d nj ) и явля- значение может быть задано экспертом вручную или получено на основе обучающей выборки как ется симметричным. соотношение количества оригинальных документов, 5.5 Фотографии и ссылки поступивших от источника, к общему количеству опубликованных им сообщений. Информация в сообщении может быть представ- В модель документа включается компонент, от- лена не только текстом или числовыми данными, но ражающий авторитетность источника, опублико- и различными объектами, включенными в текст до- вавшего этот документ: d ia  aut ( src (d i )) , где кумента - фотографиями, видеороликами, ссылками на сторонние источники. Присутствие в документе ( src(d i ) – функция, устанавливающая соответствие дополнительных фото- и видеоматериалов значи- между документом и его источником. тельно повышает вероятность его оригинальности 187 Таким образом, модель документа представляет На основе полученных результатов принимается собой совокупность компонентов, характеризующих решение о дальнейших действиях в отношении до- сообщение с точки зрения различных критериев: кументов. Так, в разработанной системе решалась задача проверки документов в момент их поступле- d i  (d iw , d it , d in , d ic , d ip , d iim , d ih , d idt , d ia ) . (10) ния от источника, при этом загружаемые сообщения сравнивались на предмет дублирования с докумен- 6 Метод обнаружения дубликатов тами, уже загруженными в базу. Поэтому интерес представлял лишь один из результатов интерпрета- 6.1 Интерпретация результата сравнения ции – является ли загружаемый документ дублика- После получения моделей d i и d j двух доку- том ранее полученного сообщения. Однако при об- работке готовой коллекции документов с целью об- ментов необходимо сравнить их и вынести решение наружения и устранения дубликатов важно выявить о том, являются ли документы нечеткими дублика- все пары сообщений, в которых имеет место дубли- тами. Для этого выполняется анализ схожести со- рование, для чего требуется использовать оба ре- общений по каждому из критериев. Результатом зультата. сравнения документов с точки зрения некоторого критерия k является значение  ik, j . Выполнив по- 6.2 Метод предварительного отбора кандидатов парно сравнение компонентов моделей для каждого Предложенный метод выявления нечетких дуб- из критериев, получим вектор ликатов имеет существенный недостаток – высокую вычислительную сложность. Каждое новое сообще-  i , j  (  iw, j ,  it, j ,  in, j ,  ic, j ,  ip, j ,  iim , j , i, j , i, j , i, j ) h dt a ние подвергается сравнению со всеми ранее загру- (11) женными, и при каждом сравнении выполняется Ввиду вышеуказанной несимметричности мер расчет близости документов по множеству критери- сходства, используемых для некоторых критериев, ев. Однако очевидно, что в большинстве случаев в результатом сравнения двух документов являются таком тщательном анализе нет необходимости – два различных вектора  i, j и  j,i , характеризующие сильно различающиеся по тексту документы с вы- сокой вероятностью различны и по содержанию. степень отличия первого и второго сообщения друг Следовательно, нужно исключать из рассмотрения от друга. Каждый из этих векторов интерпретирует- те из ранее загруженных новостей, которые слиш- ся с помощью функции D(  ) (3). ком сильно отличаются от текущей. Для интерпретации результата сравнения необ- С этой целью вышеописанный метод предваря- ходимо решить задачу бинарной классификации, то ется процедурой отбора документов, дубликатом есть отнести вектор к классу M  или M  . Для на- которых может быть текущая новость (то есть, от- стройки параметров классификатора используется бора кандидатов на роль оригинала этой новости). обучающая выборка – набор векторов, каждый из Эта процедура, по сути, также решает задачу обна- которых снабжен меткой m  {M  , M  } , обозна- ружения дубликатов, причем основными требова- ниями, предъявляемыми к ней, являются мини- чающей класс, к которому принадлежит этот вектор. мальная вычислительная сложность и максимальная Задача бинарной классификации состоит в том, полнота (поскольку отброшенные из числа кандида- чтобы для вновь поступившего на исследование тов документы далее рассматриваться не будут). вектора   (  1 ,  2 , ...,  K ) определить класс, к В качестве такой процедуры рассматривались которому он принадлежит, то есть значение m. Для представленные в работе [12] приближенные мето- её решения будем использовать метод опорных век- ды обнаружения дубликатов, имеющие высокую торов (SVM). Этот метод основан на построении в производительность. Ввиду наличия набора взве- K-мерном пространстве (K – 1)-мерной гиперпло- шенных слов, было решено использовать для описа- скости, разделяющей объекты классов M  и M  . В ния сообщения сигнатуру, представляющую собой строку, состоящую из сцепленных в алфавитном зависимости от расположения вектора  относи- порядке нескольких наиболее «тяжелых» слов до- тельно этой гиперплоскости, выполняется его отне- кумента. При этом процедура отбора кандидатов сение к одному из классов. заключается в выборе из ранее загруженных доку- Возможны следующие результаты интерпретации: ментов тех, которые имеют такую же сигнатуру, как  D (  i , j )  D (  j ,i )  0 . В этом случае оба до- и текущая новость. Такие пары документов с совпа- дающими сигнатурами должны быть подвергнуты кумента признаются оригинальными; проверке основным методом, представленным в  D(  i , j )  D(  j ,i ) . Один из документов явля- предыдущем подразделе. В работе [12] предложено ется оригиналом, а второй – дублем; использовать сигнатуры из 6 слов, но это приводит к низкому значению полноты (0.54). В целях получе-  D(  i , j )  D(  j ,i )  1 . Оба документа являются ния высокой полноты, было решено сократить ко- дублями друг относительно друга. То есть, ни один личество слов, составляющих сигнатуру, до двух. из них не содержит оригинальных данных относи- тельно другого. 188 7 Экспериментальная проверка метода В рамках второго эксперимента выполнялась оценка качества основного метода. Для тестирова- В рамках данной работы были проведены экспе- ния использовались 26 036 документов, извлечен- рименты, направленные на анализ качества работы ных с 20 новостных сайтов. С помощью метода разработанной подсистемы обнаружения дублика- фильтрации было отобрано 2650 пар-кандидатов, тов, реализующей предложенный метод. Все экспе- каждая из которых была проанализирована экспер- рименты проводились на ПЭВМ со следующими тами на предмет наличия дублирования. Часть пар основными параметрами: процессор Intel Core 2 Duo использовалась для обучения, на остальных выпол- 2,2 ГГц, объем ОЗУ 2 Гб. нялось тестирование метода. Целью эксперимента Целью первого эксперимента была оценка каче- было определение зависимости показателей качест- ства метода предварительного отбора потенциаль- ва (точности, полноты и F-меры) от мощности обу- ных дубликатов на примере анализа общественно- чающей выборки и от учитываемых критериев. политических новостей. Тестирование производи- Полученные зависимости представлены на рис. 3 лось в течение суток. В качестве входных данных (а – при использовании только близости составов использовались 1502 документа, извлеченных с 20 слов, б – при использовании только схожести новостных сайтов. Каждый из документов подвер- параграфов, в – при использовании всех критериев, гался сравнению с 10293 загруженными ранее со- приведенных в разделе 5). общениями. В общей сложности было выполнено Как видно из рисунка, при использовании 400 16 586 310 сравнений документов, при этом 259 пар обучающих примеров происходит насыщение, и с были отобраны для проверки основным методом. дальнейшим увеличением обучающей выборки ка- Таблица 1. Оценка качества метода отбора кандидатов чество работы метода не улучшается. Таким обра- зом, для обучения системы достаточно 400 пар до- Np N or N dup кументов, размеченных экспертами. Всего 16 586 310 16 586 121 189 Проведенный эксперимент доказывает целесооб- разность многокритериального сравнения документов: Прошли отбор 259 108 151 при использовании всех критериев достигаются более Отброшено 16 586 051 16 586 013 38 высокие показатели качества (F-мера в зоне насыще- ния равна 0,82), чем при анализе документов только с Где N p – общее количество пар, N or – число точки зрения слов (0,67) или параграфов (0,64). пар, элементы которых не дублируют друг друга, и При анализе результатов эксперимента было вы- N dup – количество пар документов-дубликатов. явлено несколько факторов, негативно сказываю- щихся на качестве. Одним из них является челове- Из 189 пар дубликатов отбор прошла 151 пара ческий фактор: каждый эксперт, принимавший уча- (80%). Таким образом, использование сигнатуры из стие в подготовке обучающей и тестовой выборок, двух слов позволяет увеличить полноту по сравне- имеет свое представление о том, какие документы нию с шестисловными сигнатурами, однако добить- являются информативно необходимыми, а какие – ся полноты, близкой к 100%, не удалось. Метод час- нет, в результате чего возникают конфликты в суж- то отбрасывает дубликаты в случаях, когда один из дениях экспертов. Также эксперимент показал, что документов является урезанной копией другого – система не может обнаруживать дублирование в отсутствие нескольких параграфов значительно случае переписывания оригинального текста без влияет на веса слов. Анализ результатов экспери- изменения его содержания (рерайтинга), что говорит ментов показывает необходимость доработки мето- о необходимости доработки модели для обнаруже- да предварительного отбора. ния такого рода дублирования. Наконец, при прове- Отброшенные пары не используются для обуче- дении эксперимента была выполнена попытка на- ния и тестирования основного метода, однако было стройки единой модели распознавания для всех до- обнаружено, что 38 ошибочно отброшенных пар кументов, загружаемых с новостных сайтов. Но эти дубликатов по своим характеристикам близки к тем документы принадлежат различным предметным 151, которые прошли отбор. Таким образом, недос- областям – среди общественно-политических ново- таточная полнота метода предварительного отбора стей попадаются экономические, спортивные, юри- ведет к появлению в коллекции большего количест- дические. Для повышения качества работы эти до- ва дублирующихся сообщений, но не снижает каче- кументы должны анализироваться с использованием ство обучения основного метода. специализированных моделей распознавания. Среди всех 259 пар, прошедших отбор, дублика- Проведенный эксперимент также показал, что ты составляют 58%. Столь низкая точность метода среднее время, затрачиваемое на анализ пары доку- доказывает необходимость дополнительного анали- ментов основным методом, составляет 5 мс. С учетом за отобранных пар. При этом метод продемонстри- высокой эффективности метода предварительной ровал высокую эффективность (под эффективно- фильтрации это означает, что система способна обра- стью понимается отношение количества пар, от- батывать 10 000–50 000 документов в час (в зависимо- брошенных на этапе предварительного отбора, к сти от количества загруженных ранее сообщений, с общему числу пар): из 16 586 310 пар документов которыми требуется сравнивать новые документы). было отброшено 16 586 051 (0,99998%). 189 Рис. 3. Зависимость точности (тонкая сплошная линия), полноты (тонкая пунктирная линия) и F-меры (жирная линия) от мощности обучающей выборки 190 [3] Damerau, F. 1964. A technique for computer 8 Направления дальнейших исследований detection and correction of spelling errors. Помимо обнаружения и устранения дубликатов, Communications of the ACM 7, 3 (1964), 171–176. предлагаемый метод может быть использован для [4] D. Fetterly, M. Manasse, M. Najork. A Large-Scale решения других задач интеллектуального анализа Study of the Evolution of Web Pages, WWW2003, текстов. При соответствующей настройке набора May 20–24, 2003, Budapest, Hungary. учитываемых критериев и порога близости доку- [5] U. Manber. Finding Similar Files in a Large File ментов, необходимого для вынесения решения о System. Winter USENIX Technical Conference, наличии дублирования, метод может быть применен 1994. для решения общей задачи обнаружения докумен- [6] Robertson S., Walker S., Jones S., Hancock M.- тов, близких по содержанию к заданному. Это по- Beaulieu, M. Gatford. Okapi at trec-3. The Third зволит, в частности, выполнять формирование под- Text REtrieval Conference (TREC-3), 1995. борок тематически близких документов, а также [7] Андреев А.М., Березкин Д.В., Симаков К.В. сообщений, которые с большой долей вероятности Модель извлечения фактов из естественно- связанны с каким-то общим событием. Таким обра- языковых текстов и метод ее обучения // зом, имеется возможность использования разрабо- Электронные библиотеки: перспективные танного метода для решения задачи динамической методы и технологии, электронные коллекции: кластеризации коллекции документов. Труды 8-й Всероссийской научной Еще одним перспективным направлением разви- конференции (RCDL’2006). – Суздаль, 2006. тия метода является снабжение его возможностью [8] Андреев А.М., Березкин Д.В., Морозов В.В., не только обнаружения наличия или отсутствия Симаков К.В. Метод кластеризации дублирования, но и выделения в тексте близких по документов текстовых коллекций и синтеза содержанию сообщений фрагментов с оригинальной аннотаций кластеров // Электронные (недублированной) информацией. библиотеки: перспективные методы и технологии, электронные коллекции: Труды 9 Заключение 10-й Всероссийской научной конференции В работе предложен метод обнаружения и устра- (RCDL’2008). – Дубна, 2008. – С. 220–229. нения нечеткого дублирования в потоке текстовых [9] Андреев А.М., Березкин Д.В., Козлов И.А., сообщений. В его основе лежит отнесение пар до- Симаков К.В. Метод обнаружения изменений кументов к классу «дубликатов» или «не- структуры веб-сайтов в системе сбора дубликатов» с помощью метода опорных векторов. новостной информации // Электронные Предлагаемый метод обладает высокой гибко- библиотеки: перспективные методы и стью благодаря возможности его настройки для об- технологии, электронные коллекции: Труды работки сообщений из различных предметных об- 14-й Всероссийской научной конференции ластей. Это достигается посредством включения в (RCDL-2012). – Переславль-Залесский, 2012. – модель документа компонентов, отражающих кри- С. 124–133. терии, которыми руководствуются эксперты при [10] Блох М.Я. Теоретические основы грамматики : анализе текстовых коллекций вручную. учебник. – 2-е изд., исправл. – М. : Высш. шк., 2000. – 160 с. Для обеспечения низкой вычислительной слож- ности предложена процедура отбора пар-кандидатов [11] Большакова Е.И., Клышинский Э.С., Ландэ Д.В., на основе сравнения числовых сигнатур докумен- Носков А.А., Пескова О.В., Ягунова Е.В. тов. Это позволяет применять основной метод лишь Автоматическая обработка текстов на к документам, прошедшим отбор. естественном языке и компьютерная лингвистика : учеб. пособие. – М. : МИЭМ, 2011. – 272 с. Представленный метод был апробирован при ре- [12] Зеленков Ю.Г, Сегалович И.В. Сравнительный шении задачи анализа потока текстовых сообщений, загружаемых из открытых интернет-источников, с анализ методов определения нечетких дубликатов целью устранения документов, являющихся дублика- для Web-документов // Электронные библиотеки: тами ранее загруженных материалов. перспективные методы и технологии, электронные коллекции: Труды 9-й Литература Всероссийской научной конференции (RCDL’2007). – Переславль-Залесский, 2007. – [1] M. Bilenko, R.J. Mooney. Adaptive Duplicate С. 166–174. Detection Using Learnable String Similarity [13] Князева А.А., Турчановский И.Ю., Колобов Measures. Proceedings of the Ninth ACM О.С. Выявление дубликатов в SIGKDD International Conference on Knowledge библиографических базах данных // Discovery and Data Mining(KDD-2003), Электронные библиотеки: перспективные Washington DC, pp. 39–48, August, 2003. методы и технологии, электронные коллекции: [2] A. Broder. Algorithms for duplicate documents. Труды 15-й Всероссийской научной http://www.cs.princeton.edu/courses/archive/spr05 конференции (RCDL2013). – Ярославль, 2013. /cos598E/bib/Princeton.pdf – С. 276–282. 191 [14] Ландэ Д.В., Дармохвал А.Т., Морозов А.Ю. : учеб. пособие. – Томск : ТМЛ-Пресс, 2007. – Подход к выявлению дублирования сообщений 144 с. в новостных информационных потоках // Электронные библиотеки: перспективные The Method of Detecting Duplicates методы и технологии, электронные коллекции: in a Stream of Text Documents Труды 8-ой Всероссийской научной конференции (RCDL2006). – Суздаль, 2006. A. Andreev, D. Berezkin, I. Kozlov, K. Simakov [15] Лифшиц Ю. Метод опорных векторов. Курс The problem of duplicate documents elimination лекций «Алгоритмы для Интернета», 2006. from a stream of text messages is considered. A [16] Никконен А.Ю. Устранение избыточности и multicriterion model of text document is given. Criteria дублирования сюжетов новостных сообщений are chosen to properly represent documents from // Сборник работ участников конкурса different domains. An approach for duplicates detection «Интернет-математика 2007». based on binary classification is proposed. A method of [17] Шевелёв О.Г. Методы автоматической candidates preliminary filtration is proposed in order to классификации текстов на естественном языке reduce the computational complexity of the approach. 192