Автоматическая оценка подобия тематического содержания текстов на основе сравнения их формализованных смысловых описаний © В.Н. Захаров © А. А. Хорошилов ИПИ РАН ЦИТиС Москва vzakharov@ipiran.ru a.a.horoshilov@mail.ru ны. Эти успехи зависят, прежде всего, от достиже- Аннотация ний в изучении процессов человеческого мышления, В работе описываются методы процессов речевого общения между людьми и от умения моделировать эти процессы на ЭВМ. автоматического построения формализован- Основной проблемой, возникающей при обработке ного смыслового описания документа и оценки подобия тематического содержания текстовой информации, является трудность автома- текстов. Эти методы базируются на приме- тического составления формализованного описания смыслового содержания документов и, как следст- нении процедур семантико-синтаксического вие этого - трудность установления смысловой и концептуального анализа, обеспечиваю- щих выявление понятийного состава текста связи между различными документами. Это обусловлено тем, что в разных текстах одни и те же и назначения наименованиям понятий ситуации могут описываться в терминах различной характеристик, соответствующих их семан- степени общности и с помощью различных языко- тической роли и значимости в тексте. Автоматическая оценка подобия тематичес- вых средств. И только человек, анализирующий документы, руководствуясь своими представлени- кого содержания текстов производится пу- ями о содержании документов и средствах тем сравнения понятийного состава текстов. Результатом работы явилось создание комп- выражения этого содержания и опираясь на свои лекса программных средств, предназначен- профессиональные знания и опыт, в состоянии ного для оценки подобия тематического установить степень смысловой близости анализи- содержания текстов. Основными преиму- руемых документов. Большинство систем автомати- ческой обработки текстовой информации, функции- ществами данного программного комплекса онирующих в настоящее время, не могут в полной является его быстродействие и возможность степени решать эти проблемы. обработки текстов, относящихся к любым предметным областям. В связи с этим возникает необходимость в разработке эффективных методов автоматического 1 Введение анализа содержания документов. Отличительная особенность предлагаемых методов заключается в 1.1 Проблемы обработки текстовой информации том, что они базируются на современных представлениях о смысловой структуре текстов и В настоящее время в связи с постоянно оригинальных процедурах семантико-синтаксичес- растущими объемами информационных ресурсов кого и концептуального анализа. доступ пользователей к интересующим их сведениям становится все более затруднительным. 1.2 Методы сравнения текстов Для решения этой проблемы создаются современные информационные технологии, В рамках наших исследований были базирующиеся на мощном фундаменте рассмотрены такие методы, как TF, Opt Freq, Lex телекоммуникационных и вычислительных средств. Rand, Log_Shingle, Megashingles, Long Sent, Descr Сейчас эти средства достигли высокого уровня Words [11-15]. Широкомасштабный эксперимент по развития. Особенно ярко эти успехи проявляются в сравнительному анализу этих методов был области развития средств связи и разработки выполнен Ю.Г. Зеленковым и И.В. Сегаловичем в мощных вычислительных систем. работе [11]. В этой работе ставилась задача оценить качество наиболее известных, разнообразных и На фоне этих успехов успехи в области эффективных с вычислительной точки зрения смысловой обработки информации менее значитель- алгоритмов определения нечетких дубликатов. При Труды 14-й Всероссийской научной конференции этом предполагалось сравнивать алгоритмы по «Электронные библиотеки: перспективные методы и параметрам полноты и точности, а также определить технологии, электронные коллекции» — RCDL-2012, их взаимную корреляцию и совместное покрытие Переславль-Залесский, Россия, 15-18 октября 2012 г. разными сочетаниями алгоритмов исходного мно- 143 жества пар нечетких дубликатов. В качестве слов и назначения им грамматических признаков. тестового массива использовалась веб-коллекция Используемый в наших исследованиях морфологи- документов РОМИП (около 500 тыс. документов). ческий анализ разработан профессором Г. Г. В исследуемых алгоритмах в качестве одного из Белоноговым [5] на основе созданной им системы параметров меры сходства документов были флективных классов русских слов. Система флек- использованы различные текстовые фрагменты тивных классов была создана путем анализа текстов, (буквенные подстроки, фиксированные последова- в которых в различных контекстных окружениях тельности значимых слов «шинглы», частотные слова могут приобретать различные формы. Это словари слов и т.д.), подвергнутые статистической могут быть формы словоизменения и словообра- обработке. При этом лучшие результаты по зования. точности были у алгоритмов, базирующиеся на Процедура морфологического анализа использовании более длинных фрагментов текста. функционирует следующим образом. На первом Алгоритмы, базирующиеся на более коротких этапе производится поиск в словаре "служебных и фрагментах текста, обеспечивали лучшую полноту, коротких слов", а затем, в случае неудачи, в но проигрывали в точности сравнения. словаре концов словоформ. Результаты анализа, Необходимо отметить, что во всех полученные в процессе поиска по первому словарю, рассмотренных алгоритмах текст рассматривается считаются правильными. Вероятность правильного как некоторое множество, состоящее из отдельных анализа слов по словарю концов словоформ при слов. Различные операции, выполняемые в процессе обработке текстов любой тематики превышает 99% поиска текстов-дубликатов, производились над сло- [4,5]. вам и их цепочкам. Между тем текст это не 2.3 Семантико-синтаксический анализ множество слов и их последовательностей, и при установлении смысловой близости документов Семантико-синтаксический анализ проводится с нужно сопоставлять, прежде всего, смысловые целью получения формализованного представления единицы текста – понятия, выраженные словосо- структуры текстов – выделения в них смысловых четаниями. При этом, необходимо учитывать такое единиц и установления связей между ними [5]. В явление как вариативность форм представления в результате анализа в тексте должны быть выделены тексте одного и того же смысла. (См. ниже). А это составные части текста, которыми являются речевые явление в вышерассмотренных алгоритмах пол- отрезки, обозначающие понятия: слова, слово- ностью игнорировалось. Поэтому алгоритмы сочетания, фразы, сверхфразовые единства. При установления смысловой близости документов описании синтаксической структуры текстов в должны базироваться на современных процедурах качестве одной из формализованных моделей была семантико-синтаксического и концептуального ана- использована модель дерева зависимостей. Соглас- лиза, позволяющих выявлять в текстах наимено- но этой модели каждое предложение представляется вания понятий, представленные в различных фор- в виде дерева, в узлах которого находятся слова. мах их представлений. Отношения непосредственной доминации визуали- зируются путем указания для каждого подчинен- 2 Процедуры семантического анализа ного слова (“слуги”) его подчиняющего слова документов (“хозяина”). При этом степень дифференциации этих отношений может быть различной, в частности, 2.1 Единицы языка и речи иногда достаточно установления только факта наличия смысловой связи. Основными единицами языка и речи, принятыми Алгоритм синтаксического анализа текстов, как в лингвистике, являются морфемы, слова, и множество подобных ему алгоритмов, имеет тот словосочетания, фразы и различного рода недостаток, что в нем в явном виде не выделяются сверхфразовые единства. Система единиц языка и смысловые единицы, выраженные словосочета- речи обычно представляется в виде иерархической ниями. В свою очередь смысловое содержание структуры, в которой единицы вышестоящих уров- текстов документов выражается с помощью единиц ней включают в свой состав единицы нижестоящих смысла – понятий и связей между ними. Профессор уровней и сами входят в состав единиц более Г. Г. Белоногов [4,5] определяет понятие, как высоких уровней. Для каждого уровня единиц языка социально значимый мыслительный образ, за разработаны инструментальные средства их обра- которым в языке закреплено его наименование в ботки. Для обработки слова обычно используется виде отдельного слова или, значительно чаще, в морфологический анализ. Для обработки предло- виде устойчивого фразеологического словосоче- жений и сверхфразовых единств (текстов) обычно тания. Под устойчивыми фразеологическими слово- применяется семантико-синтаксический и концеп- сочетаниями мы будем понимать не только идиома- туальный анализ. тические выражения и терминологические словосо- 2.2 Морфологический анализ четания, но и любые повторяющиеся отрезки связных текстов, для их выделения применяется Морфологический анализ слов естественных процедура концептуального анализа. языков предназначен для определения структуры 144 2.4 Концептуальный анализ признаков и их отношений [4,5]. Свойством преди- кативности обладают и высказывания, форму- Процедура концептуального анализа текстов лируемые на формализованных языках. Таким обра- предназначена, прежде всего, для выявления зом, в основе и предложений на естественном язы- наименований понятий в тексте. Эта процедура ке, и формализованных логических высказываний базируется на результатах семантико-синтаксичес- лежит предикатно-актантная структура, компонен- кого анализа и использовании эталонного словаря тами которой являются понятия-предикаты (отно- наименований понятий предметной области, к шения) и понятия-актанты, выступающие в роли которой принадлежит анализируемый текст. описываемых объектов. На первом этапе текст обрабатывается В соответствии с положенной в основу наших программами семантико-синтаксического анализа, в исследований концепцией в текстах понятия-актан- результате которого текст членится на предложения, ты выражаются чаще не отдельными словами, а строится синтаксическая структура предложений, и устойчивыми словосочетаниями. А словами или каждому слову назначается набор грамматических словосочетаниями, устанавливающими смысловые признаков. Затем каждое предложение исходного отношения между ними - понятиями-предикатами - текста разбивается на различные фрагменты и на их являются обычно глаголы или отглагольные формы основе формируются “поисковые образы” в виде существительных, прилагательных и наречий. При последовательностей нормализованных слов и этом необходимо учитывать, что в текстах описа- словосочетаний. Далее эти последовательности ние одинаковых понятий или ситуаций часто может заменяются на их первичные хеш-коды – на более выполняться в терминах различной степени общ- короткие восьмибайтовые кодовые комбинации, ности и с помощью различных языковых средств. которые в дальнейшем используются в процессе Например, в различных контекстных окружениях отождествления отрезков исходного текста с наименования понятий могут описываться с исполь- наименованиями понятий эталонного словаря. зованием явлений словоизменения и словообразова- После того как текст был представлен в виде ния, а также явлений синонимии и гипонимии. Все списка слов и словосочетаний, из него выбираются эти явления существенно затрудняют распознавание наиболее информативные слова и словосочетания. и сравнение между собой текстовых форм наимено- Такой выбор осуществляется по эталонному ваний понятий. словарю наименований понятий (концептуальный Таким образом, при проведении исследований анализ с контролем по тезаурусу) или путем необходимо выявление понятийной структуры тек- проверки структуры словосочетаний программой ста. Под такой структурой текста будем понимать синтаксического контроля и последующего совокупность понятий, выявленных в тексте и исключения из их состава малоинформативных связанных между собой смысловыми отношениями. словосочетаний по так называемому словарю стоп- Между тем выявленную понятийную структуру тек- слов. ста, состоящую из текстовых форм наименований понятий, необходимо автоматически привести к формализованной форме ее представления. Такое 3 Концепция смысловой обработки приведение выполняется путем автоматической текстовой информации нормализации текстовых форм наименований поня- тий (слов или словосочетаний) к их каноническим 3.1 Структура языка и речи формам. При разработке процедур автоматической 3.2 Приведения понятий к нормализованной обработки текстовой информации важно исходить (канонической) форме из правильных представлений о смысловой структуре языка и речи. По современным Обычно под нормализованной (канонической) представлениям наиболее информативными и формой слова понимается та его форма, которая наиболее устойчивыми единицами смысла являются традиционно указывается в словарях. Например, для понятия [4-6,9]. Они занимают центральное место в существительного - это форма именительного языке и речи, с их помощью описывается смысловое падежа единственного или (в случае pluralia tantum) содержание текстов и именно они являются теми множественного числа, для глагола – форма инфи- базовыми строительными блоками, на основе нитива, для прилагательного – форма именитель- которых формируются смысловые единицы более ного падежа единственного числа мужского рода. высоких уровней. Второй по значимости единицей Процедура замены исходной вариантной формы смысла является предложение. Из предложений слова на каноническую называется процедурой формируются различного рода сверхфразовые един- нормализации или лемматизации. ства, которые представляются в виде последователь- Необходимо отметить, что нормализация ностей предложений связного текста. слов/словосочетаний может выполняться с различ- Основной чертой предложений является их ной степенью смысловой общности – на уровне предикативность – то есть то их свойство, что в них словоизменения или на уровне словообразования. утверждается наличие у объектов определенных Порядок слов в словосочетании и неизменяемые формы слов при нормализации не изменялись. 145 3.3 Концепция формализованного смыслового • Значение числа встречаемости наимено- описания документа вания понятия в тексте (локальная частота) • Длина наименования понятия (в словах) Исходя из вышесказанного, смысловую струк- туру текста можно представить в виде совокупности • Принадлежность наименования понятия к нормализованных наименований понятий и связей фамильно-именной группе. между ними. Такую смысловую структуру текста При назначении весовых коэффициентов мы вос- будем называть его формализованным смысловым пользуемся предложенной нами формулой: описанием.  ( pij  fg ij )  f ij  lij lij  kmax В состав формализованного смыслового описа- Wij   ния документа должны быть включены наименова- ( pij  fg ij )  f ij  kmax lij  kmax , ния понятий, сопровождаемые коэффициентом, определяющим степень их смысловой значимости в тексте. Поэтому при формировании формализо- ванного описания документа нужно определить его где, pij - коэффициент, увеличивающий степень состав и назначить каждому элементу его весовой значимости наименования понятия в зависимости от коэффициент. Для этого необходимо в анализиру- его принадлежности к фамильно-именной группе, емом тексте выявить информативные слова или географическим названиям и т.д. словосочетания, опираясь на их формальных харак- теристиках, среди которых: значения их частот в lij - количество слов в словосочетании, которым предметной области и конкретном тексте, длины выражается j-ое понятие в i-ом тексте; словосочетаний (в словах), принадлежности к f ij - частота появления j-ого понятия в i-ом категории географических названий или фамильно- именной группе, а также их наличие или отсутствие тексте; в эталонном концептуальном словаре и их наличие fg ij - нормированная глобальная частота j-ого или отсутствие в словаре стоп-слов. понятия в i-ом тексте; В формализованном смысловом описании документа каждый элемент состоит из пары kmax - коэффициент, установленный опытным наименований понятий-актантов, связанных между путем, соответствующий максимальной длине собой понятием-предикатом. словосочетания, после которой она не должна Таким образом, можно сформулировать следу- влиять на итоговый вес наименования понятия. ющее определение формализованного смыслового 3.5 Порядок построения табличного описания документа (ФСОД), под которым будем называть упорядоченное множество представления формализованного смыслового описания документа F = {Sui | i [1, nF ]} , где На основании высказанного можно определить nF - количество элементов в формализованном следующий порядок построения табличного пред- смысловом описании документа; ставления формализованного смыслового описания документа: Sui  ( Nci , wi , Ri ) - i -ый элемент ФСОД; 1. Определение синтаксической и концеп- Nci — наименование понятия; туальной структуры текста; 2. Разрешение анафорических ссылок в тексте; wi - весовой коэффициент, соответствующий наименованию понятия; 3. Получение частотного словаря наименова- ний понятий; Ri - множество связей, относящихся к данному 4. Установление смысловых связей между элементу ФСОД. наименованиями понятий; 3.4 Определение весовых коэффициентов 5. Исключение малоинформативных слов или словосочетаний; наименований понятий 6. Приведение различных форм представления Для указания смысловой значимости наименований понятий к единой унифицированной наименования понятия в формализованном форме; смысловом описании документа необходимо 7. Дополнение полученной по тексту таблицы назначить каждому наименованию понятия весовой связей наименований понятий внеконтекстными коэффициент. парадигматическими и ассоциативными связями. На весовой коэффициент оказывают влияние следующие характеристики наименования понятия: • Значение числа встречаемости наименова- ния понятия в предметной области (глобальная частота) 146 4 Автоматическая оценка подобия f pj - j-ая компонента вектора локальных частот тематического содержания текстов наименований понятий, содержащихся в p-ом тексте. 4.1 Описание процесса автоматической оценки f qj - j-ая компонента вектора локальных частот подобия тематического содержания текстов наименований понятий, содержащихся в q-ом тек- Процедура автоматической оценки подобия сте. тематического содержания текстов выполняется пу- тем сопоставления формализованного смыслового n  - размерность вектора наименований поня- содержания двух документов. Поскольку в данной тий, содержащихся в обоих текстах. работе задача состоит в определении смысловой близости тематически связанных документов, в np - размерность вектора наименований поня- которых освещены те же темы, но возможно в нес- тий, содержащихся в p-ом тексте. колько другом аспекте, мы можем упростить форма- лизованное смысловое описание и в данном случае nq - размерность вектора наименований исключить из него связи между объектами. Тогда формализованное смысловое описание документа понятий, содержащихся в q-ом тексте. примет следующий вид: С ростом коэффициента K sim увеличивается F = {Sui | i [1, nF ]} , где степень тематического подобия тематического nF - количество элементов в формализованном содержания текстов. Если коэффициент K sim =1, смысловом описании документа; тогда тексты идентичны. Sui  ( Nci , wi ) - i -ый элемент ФСОД; 4.2 Пример работы данного алгоритма на Nci — наименование понятия; коротких запросах wi - вес наименования понятия. Приведем пример одного из экспериментов, ил- Для выполнения данной задачи оценки подобия люстрирующих работу вышеизложенных алгорит- тематического содержания текстов необходимо мов, и заключающихся в сравнении результатов установить формальные критерии, определяющие ранжирования документов, выполненных поисковой численную характеристику степени их подобия. Эта системой Google, программным комплексом, характеристика получена как произведение коэф- разработанным авторами и человеком-экспертом. фициента нормировки и частного от деления суммы Для этого с помощью поисковой системой Google весов совпавших наименований понятий на сумму был выполнен поиск по следующему короткому весов всех наименований понятий эталонного доку- запросу: “Як-38 - самолет ОКБ Яковлева с мента. Назовем эту характеристику коэффициентом технологией вертикального взлета”. Далее первые подобия тематического содержания текстов. Тогда 100 из найденных поисковой системой документов формулу для вычисления коэффициента подобия были обработаны с помощью разработанного авто- тематического содержания p-ого и q–ого текстов рами программного комплекса и отсортированы по можно записать следующим образом: степени их подобия поисковому запросу. И, np наконец, эти найденные документы также были n оценены человеком по степени их релевантности w  f j 1 j j 1 pj данному поисковому запросу. Результаты этого эксперимента приведены в таблице 1. K sim  np nq В первом столбце отображено ранжирование до- кументов, полученное поисковой системой Google. w  f j 1 pj j 1 qj Во втором столбце – ранжирование, полученное после обработки программным комплексом авторов, и в третьем столбце – ранжирование, полученное экспертом. В четвертом столбце приведена оценка w j - j-ая компонента вектора весовых коэф- тематического подобия документов запросу, фициентов наименований понятий, содержащихся в полученная с помощью созданного программного обоих текстах, причем веса берутся из формали- обеспечения, результаты приведены в процентах. зованного смыслового описания q-ого текста. Последняя колонка содержит краткие комментарии к анализируемым текстам. Результаты этого экспе- w pj - j-ая компонента вектора весовых коэф- римента показывают, что ранжирование документов, фициентов наименований понятий, содержащихся в выполненное разработанным программным комп- p-ом тексте. лексом, более точно соответствует ранжированию, выполненному экспертом-человеком, чем произве- денное системой Google. 147 Следующим этапом в развитии этого программ- ного комплекса может быть реализация новых Таблица 1 Фрагмент результатов сравнения ранжирований функциональных возможностей: документов по степени их релевантности 1. Выделение в тексте смысловых фрагментов, отражающих различные темы документа; Ранжирование документов по степени их 2. Установление смысловой близости доку- релевантности поисковому запросу ментов с учетом связей между объектами; 3. Установление заимствований из других Поисковая Программный документов; Человек- система комплекс 4. Оценка тождественности (аутентичности) эксперт Google авторов смыслового содержания разноязычных текстов. 1 6 8 Литература [1] Кузнецов И.П. Механизмы обработки семан- 2 8 5 тической информации. – М.: Наука, 1978. – 175с [2] Осипов Г.С. Приобретение знаний интеллек- 3 9 9 туальными системами: Основы теории и тех- нологии. – М.: Наука. Физматлит, 1997. – 4 1 1 112с [3] Золотова Г.А. «Коммуникативные аспекты русского синтаксиса» — М., КомКнига, 5 4 3 2010. – 368 с [4] Белоногов Г.Г., и др. Компьютерная линг- 6 11 11 вистика и перспективные информационные технологии. Теория и практика построения систем автоматической обработки текстовой 7 7 7 информации — М.: Русский мир, 2004. – 264 с. [5] Белоногов Г.Г. Теоретические проблемы 8 5 6 информатики, Том 2. Семантические проб- лемы информатики. Под общей редакцией К.И. Курбакова. – М.: РЭА им. Г.В. Плеха- 9 10 10 нова. 2008 г. – 342с. [6] Васильев В.Г., Кривенко М.П. Методы 10 3 4 автоматизированной обработки текстов. – М.: ИПИ РАН. 2008г. – 301с. [7] Киселев М.В. Метод кластеризации текстов, 11 2 2 основанный на попарной близости термов, характеризующих тексты, и его сравнение с метрическими методами кластеризации. – 5 Заключение ИНТЕРНЕТ-МАТЕМАТИКА 2007, Екате- Предложенные в данной работе методы были ринбург: Изд-во Урал. Ун-та, 2007. – 224с. реализованы в виде программного комплекса, и их [8] Крейнес М.Г. Обеспечение активности эффективность была проверена на 25 выборках по содержания многоязычия текстовых доку- 30 текстов разной степени тематического подобия ментов: технология КЛЮЧИ ОТ ТЕКСТА. – общественно-политической тематики с участием Информационное общество. 2000, вып. 2, экспертов, оценивающих степень подобия текстов, 241с. также данный эксперимент был повторен при ана- [9] Соссюр Фердинанд де. Курс общей лингвис- логичных условиях для текстов по ядерной физике. тики. – М.: Прогресс,. 1977. – 370с. Проведенные эксперименты подтвердили эффек- [10] Чугреев В.Л. Модель структурного пред- тивность изложенных методов. Предлагаемые мето- ставления текстовой информации и метод ее ды могут использоваться в системах автоматической тематического анализа на основе частотно- обработки текстовой информации. В настоящее контекстной классификации. Диссертация время данный программный комплекс функциони- на соискание ученой степени кандидат тех- рует в составе Системы оперативного мониторинга нических наук. – Санкт-Петербург, 2003. – СМИ (СКЦ РосАТОМ). 185 с. 148 [11] Зеленков Ю.Г., Сегалович И.В. Сравнитель- Lost or Related Documents, SIGIR’02, August ный анализ методов определения нечетких 11-15, 2002, Tampere, Finland. дубликатов для Web-документов // Труды 9 ой Всероссийской научной конференции Automatic assessment of similarity of the «Электронные библиотеки: перспективные texts’ thematic content on the base of their методы и технологии, электронные коллек- formalized semantic descriptions ции». – RCDL’2007, Переславль, Россия, 2007. – Том 1, С. 166-174. comparison [12] U. Manber. Finding Similar Files in a Large File Victor Zakharov, Alexey Khoroshilov System. Winter USENIX Technical Conference, 1994. The paper describes the methods for automatic generation of the formalized semantic document [13] A. Broder, S. Glassman, M. Manasse and G. description and the assessment of the thematic text Zweig. Syntactic clustering of the Web. Proc. of content similarity. These methods are based on the use the 6th International World Wide Web of semantic-syntactic and conceptual analysis Conference, April 1997. procedures providing the identification of the [14] Д. Гасфилд. Строки, деревья и последова- conceptual text content and the assignment of the тельности в алгоритмах. СПб.: Невский диа- characteristics to the concept names, corresponding to лект, 2003. their semantic role in the text. Automatic thematic text [15] S.-T. Park, D. Pennock, C. Lee Giles, R. Kro- content similarity assessment is made by comparison of vetz, Analysis of Lexical Signatures for Finding the conceptual text content. 149