авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 26 |

«Электронные библиотеки: Перспективные Методы и Технологии, Электронные коллекции English Труды RCDL 2010 ...»

-- [ Страница 7 ] --

Работа выполнена при финансовой поддержке РФФИ (проект 10-07-00156) Обнаружение тропов на основе дифференциации смыслов © Д.Н. Богданова, Б.А. Новиков Санкт-Петербургский государственный университет dasha.bogdanova@gmail.com, borisnov@acm.org мненным достоинством таких низкоуровневых ха Аннотация рактеристик является легкость их извлечения, по Задачи, связанные с автоматическим анали- служившая причиной их повсеместного использо зом текстов на естественном языке, требу- вания, например, большинство работ по автомати ют особого внимания к различным характе- ческим методам определения авторства основано на ристикам текста. Тропы и другие средства подобных характеристиках. С другой стороны, в выразительности часто бывают полезны для работе [1] показано, что использование низкоуров формирования таких характеристик, но их невых характеристик для решения этой задачи часто алгоритмическое извлечение является очень ведет к неудовлетворительным результатам. К тому сложным. В данной работе мы предлагаем же, лингвистический подход к неавтоматическому метод, определяющий по данному контек- определению авторства учитывает такие высоко сту, является ли слово или выражение уровневые характеристики, как особенности ис употребленным в переносном смысле. Ме- пользования стилистических фигур, звуковых тод основан оценке близости смыслов по приёмов (аллитераций, анафор и др.), наличие рече расстоянию между наборами документов, вых ошибок (в том числе и в качестве средств выра содержащих исследуемое выражение и его зительности), а также особенности восприятия ав контекст. В работе экспериментально опре- тора (например, для Гоголя характерен “взгляд деляются значения параметров, которые по- сверху” на происходящее) и т. д. Эти характеристи зволяют выделить существенные различия, ки отражают авторский стиль более точно, но их и затем оценивается качество результатов алгоритмическое извлечение является очень слож применения метода. ным. В связи с этим было сделано крайне мало по пыток решения задачи автоматического определе 1 Введение ния авторства на основе высокоуровневых характе ристик [17].

Задачи, связанные с автоматическим анализом Долгосрочной целью нашего исследования явля текстов на естественном языке, требуют особого ется выделение высокоуровневых семантически внимания к различным характеристикам текста. насыщенных конструкций из текстов на естествен Осмысленность алгоритмов, направленных на ре ном языке. Помимо задачи определения авторства, шение этих задач, во многом зависит от того, какие выделение таких конструкций является важным для характеристики принимаются во внимание.

Напри- большинства задач обработки текстов на естествен мер, в задачах психолингвистики целесообразно ном языке, поскольку такие высокоуровневые кон уделять внимание характеристикам, отражающим струкции, как, например, тропы или другие средства психофизиологические особенности личности авто- выразительности, являются неотъемлемой частью ра, а в задаче автоматического определения автор языка. В частности, такими являются задачи, свя ства - отражающим идиостиль. Чаще всего при ав- занные с вопросно-ответными системами, в которых томатической обработке текста, например, при требуется умение правильно интерпретировать вы классификации или кластеризации документов, ис- ражения, употребленные переносном смысле. Зада пользуется векторная модель представления текста ча выделения тропов на основе дифференциации [14], то есть текст рассматривается как вектор из смыслов, решаемая в данной работе, является одной своих характеристик, в качестве которых нередко из задач, направленных на решение обозначенной выступают частоты различных знаков препинания, выше проблемы.

средние длины слов и предложений и т. д. Несо- Мы предлагаем решать такую задачу с помощью метода, основанного не следующей гипотезе, на званной нами идеей дифференциации смыслов: су Труды 12й Всероссийской научной конференции щественное различие смысла выражения и смысла «Электронные библиотеки: перспективные методы и его контекста указывает на то, что выражение технологии, электронные коллекции» – RCDL’2010, Казань, Россия, 2010 употреблено в переносном смысле.

Целью данной работы является исследование тропов (в горах моё сердце, живой костёр из снега и этого метода, включающее в себя проверку гипоте- вина и т. д.). Более того, для работы улучшенного зы, на которой он основан, и оценивание качества алгоритма [9] требуется обучающая выборка, алго его работы. ритм, предлагаемый в данной работе, не требует Необходимо подчеркнуть, что в данной работе обучающей выборки.

нас интересует именно различие смыслов, а не по- В [8] представлен алгоритм, который также яв нимание смысла текста. ляется методом контролируемого обучения. Рас сматриваемая задача формулируется как задача классификации: авторы строят обучающую выбор 2 Постановка задачи ку, а затем применяют алгоритм ближайших сосе Задачей, решаемой в данной работе, является ав- дей (k-Nearest Neighbor Classification, [6]).

томатическое определение по данному контексту В исследовании [4] для решения описанной за выражения, является ли оно употребленным в пере- дачи формируются два набора текстов (seed sets):

носном смысле. Употребления слов в переносном первый набор состоит из различных буквальных смысле могут быть представлены, в частности, ме- употреблений выражений, а второй – из употребле тафорами (например, “британский лев мягко ступа- ний в переносном смысле. Авторы вычисляют се ет по российскому правовому пространству”), мето- мантическую близость между рассматриваемым нимиями (“у нас в семье восемь ртов”), метафори- контекстом и двумя описанными наборами и опре ческими эпитетами (“хочу я слов кинжальных”). деляют, как употреблено выражение – буквально Понятие “употребления в переносном смысле” или в переносном смысле, исходя из того, расстоя тесно связано с понятием контекста, поскольку вы- ние до какого из соответствующих наборов меньше.

ражение можно назвать употребленным буквально Алгоритм, описанный в [4], так же как и подход, или метафорически только относительно контекста. предлагаемый в данной работе, обращается к кон Например, такое физическое понятие, как импеданс, цепциям из области Разрешения Лексической Неод употребленное в контексте литературы по базам нозначности (Word Sense Disambiguation). Но этот данных (impedance mismatch), безусловно, является алгоритм, в отличие от нашего, направлен только на метафорой. Как было упомянуто во введении, мы выделение употреблённых метафорически глаголов.

предлагаем решать описанную выше задачу с по- Авторы формулируют вышеописанную задачу как мощью метода, основанного на идее сравнения задачу разрешения лексической неоднозначности смыслов контекста и самого выражения. одного слова (one word или targeted disambiguation) и применяют конкретный существующий метод, в 3 Обзор существующих подходов то время как мы лишь пользуемся идеями из данной области.

Задача определения тропов рассматривалась Как уже было упомянуто, наш алгоритм должен многими исследователями.

уметь определять по контексту, является ли выра В работе [16] предлагается отличать буквальные жение употребленным в переносном смысле. При употребления выражений от их употреблений в пе этом употребления в переносном смысле могут реносном смысле по наличию семантических связей быть выражены, например, метафорами, метони (cohesive links) между словами рассматриваемого миями, метафорическими эпитетами и т. д. Стоит выражения и окружающего контекста. При наличии заметить, что в литературе встречаются алгоритмы, таких связей алгоритм считает рассматриваемое направленные на выделение конкретных тропов, выражение употребленным буквально, а при отсут например, в работе [13] описан метод машинного ствии – употребленным в переносном смысле. Для обучения для обнаружения метонимий. Авторы большинства рассмотренных в работе выражений формулируют задачу выделения метонимий как точность превышает 50% (точность для различных проблему классификации: употребление выражения выражений варьируется от 11% до 98%). В работе нужно либо определить как буквальное, либо отне [9] авторы предлагают улучшение своего алгоритма, сти к одному из предопределенных типов метони добавляя в качестве второго этапа классификацию, мии (например, “место как человек”, “место как основанную на методе опорных векторов: обучаю событие” и т. д.).

щая выборка для алгоритма классификации форми руется описанным выше способом. Таким образом, 4 Подход к решению задачи авторам удалось повысить среднюю точность до 90%. Алгоритм, предлагаемый нами, также основан Мы можем рассматривать переносное значение на предположении, что слабая семантическая связь слова (выраженное, например, метафорой) как до между выражением и его контекстом указывает на полнительное, чаще всего не включенное ни в один то, что выражение употреблено не в буквальном словарь. Хотя нужно заметить, что некоторые мета смысле. Но в отличие от вышеописанных работ, форы в словарях встречаются, например, игольное рассматривающих фразеологизмы, алгоритм, пред- ушко или горлышко бутылки. Такие метафоры лагаемый нами, направлен в большей степени не на катахрезы появляются, чтобы восполнить пробелы в выделение устойчивых выражений (кот в мешке, языке [5], и никак не отражают идиостиль: автор водить за нос и т. д.), а на выделение авторских использует их только потому, что упоминаемый объект нельзя назвать по-другому. Такие метафоры близости между словами зависят от длины пути ме жду соответствующими синсетами 1 в WordNet’е не очень интересны с точки зрения задачи изучения авторского стиля и извлечения семантически насы- [19]. К сожалению, использование подобной меры щенных характеристик текста, поэтому разрабаты- близости недоступно для русского языка из-за от ваемый нами подход не уделяет внимания метафо- сутствия WordNet-подобных словарей.

рам такого рода.

Наш подход к выделению употреблений слов в 5 Эксперименты переносном значении основан на идее дифферен Мы разделили эксперименты на два этапа: на циации смыслов.

первом этапе мы проверяем гипотезу, на которой основан исследуемый нами метод. В случае приня 4.1 Представление смысла тия гипотезы требуется также оценить параметры Определение смыслов не является нашей целью, предлагаемого метода, то есть выяснить, какое раз т. к. мы не решаем задачу понимания текста. Имея личие является достаточно сильным для того, чтобы выражение и его контекст, мы пытаемся выяснить считать рассматриваемое слово или выражение не сами смыслы, а то, насколько они близки или употребленным в переносном смысле. Второй этап далеки друг от друга. Тем не менее нам требуется экспериментов направлен на оценку качества полу представление смысла. Чтобы получить такое пред ченного алгоритма.

ставление, мы обращаемся к идее, на которой осно вано большинство исследований в области Разре- 5.1 Обучение алгоритма шения Лексической Неоднозначности (Word Sense Для первого этапа экспериментов мы выбрали Disambiguation). Смысл предлагается рассматривать несколько выражений (в т. ч. состоящих и из одного как совокупность употреблений (sense is a group of слова), для которых возможно как буквальное, так и contextually similar occurrences of a word) [15]. Таким метафорическое употребление. Для каждого такого образом, мы представляем смыслы слова и его бли выражения мы подобрали по два контекста: в одном жайшего контекста как наборы документов, связан из них выражение употреблялось буквально, а в ных со словом и окружающим это слово текстом другом – в переносном смысле. Из каждого полу соответственно. Такое представление, конечно, не ченного контекста мы удалили само целевое выра может учитывать субъективные оттенки смысла, жение.

однако дает возможность объективной оценки того, Мы условились считать набор текстов, семанти каким образом слово или выражение используется.

чески связанных с данным, за представление смыс Такие наборы текстов мы получаем с помощью ла данного текста. Для формирования этого набора поисковой системы. Для слова в качестве запроса мы рассмотрели два различных способа.

можно использовать его само. Для текста запрос можно формировать как текст целиком или как бо 5.2 Использованиелексических цепей лее значимые его части: в качестве таких частей мы предлагаем использовать выделенные из текста лек- Первый способ основан на выделении лексиче сические цепи, определенные в работе [12]. ских цепей. Лексическая цепь, согласно [12], пред ставляет собой набор семантически связанных слов 4.2 Различие смыслов в тексте. Рассмотрим, например, следующий отры вок из рассказа Рэя Брэдбэри: “Огоньки останавли Имея представление смысла, мы должны выяс вающегося по требованию пассажиров полуночного нить, как измерять различие между смыслами и ка экспресса плясали на рельсах. Только когда поезд кое различие является достаточно сильным для то отошел от станции, я выглянул в дверь пульманов го, чтобы считать рассматриваемое слово или вы ского вагона и посмотрел назад”. В этом отрывке ражение употребленным в переносном смысле. Так существительные “экспресс”, “рельсы”, “поезд”, как смыслы представлены наборами документов, “вагон”, “пассажиры”, “станция” образуют лекси мы можем измерять различия между ними как рас ческую цепь. Лексические цепи широко применя стояние между векторными представлениями [14] ются для разрешения лексической неоднозначности этих наборов документов. В нашей работе мы пред [7] и реферирования текстов [2].

лагаем использовать косинусную меру близости, Мы производили процесс извлечения таких це широко используемую в задачах автоматического пей из текстов вручную, но он может быть автома анализа текстов [3]. Так как рассматриваемая нами тизирован с помощью, например, методов, пред мера является мерой близости, различие между на ставленных в [7, 10]. Далее мы сформировали набор борами зависит от нее обратно пропорционально.

семантически близких к данному текстов из резуль Более перспективный способ нахождения рас татов, возвращенных поисковой системой по запро стояния между наборами документов предложен в су, совпадающему с самой длинной из найденных [11]: авторы предлагают использовать текстовую лексических цепей. При отсутствии в контексте меру близости (text-to-text similarity), которая осно вана на вычислении семантической близости между словами (word semantic similarity), входящими в элементарная единица тезауруса WordNet, представ тексты. Обычно подобные меры семантической ляющая собой набор синонимических лексем очевидно семантически связанных слов, мы форми- Возможно, использование другой поисковой систе ровали запрос из двух существительных, ближай- мы могло бы дать лучшие результаты, однако кон ших к рассматриваемому выражению. Для наших трольные запросы показывают, что различия в на экспериментов мы использовали Google, хотя выбор борах найденных документов не очень значительны.

поисковой системы не является принципиальным.

Таблица 1. Значения косинусной меры близости при использовании лексических цепей 5 текстов 10 текстов 15 текстов Косинусная Косинусная Косинусная Косинусная Косинусная Косинусная мера (бук- мера (пере- мера (бук мера (пере- мера (пере- мера (бук носный вальный носный вальный носный вальный смысл) смысл) смысл) смысл) смысл) смысл) вьюга 0,05 0,17 0,09 0,21 0,12 0, дыхание 0,11 0,16 0,13 0,20 0,15 0, кинжальный 0,08 0,10 0,08 0,12 0,10 0, плясать 0,09 0,16 0,08 0,17 0,12 0, стебель гибкий 0,09 0,11 0,10 0,21 0,14 0, утонул 0,05 0,17 0,08 0,20 0,12 0, хрустальными 0,07 0,21 0,06 0,21 0,09 0, шотландской 0,09 0,29 0,10 0,27 0,12 0, волынкой мед 0,04 0,15 0,06 0,21 0,09 0, лекарство 0,08 0,16 0,10 0,20 0,11 0, Таблица 2. Значения косинусной меры близости при использовании грамматических основ 5 текстов 10 текстов 15 текстов Косинусная Косинусная Косинусная Косинусная Косинусная Косинусная мера (пере- мера (бук мера (бук мера (пере- мера (бук- мера (пере носный вальный носный вальный носный вальный смысл) смысл) смысл) смысл) смысл) смысл) вьюга 0,11 0,12 0,15 0,18 0,19 0, дыхание 0,10 0,13 0,09 0,14 0,09 0, кинжальный 0,06 0,09 0,08 0,12 0,09 0, плясать 0,09 0,17 0,15 0,20 0,17 0, стебель гибкий 0,11 0,11 0,15 0,20 0,15 0, утонул 0,10 0,14 0,16 0,20 0,16 0, хрустальными 0,08 0,10 0,08 0,12 0,09 0, шотландской 0,06 0,20 0,09 0,23 0,10 0, волынкой мед 0,08 0,09 0,09 0,14 0,09 0, лекарство 0,11 0,14 0,14 0,18 0,15 0, 5.3 Представление смысла контекста с помощью 5.4 Сравнения представлений смыслов. Оценка грамматических основ параметров алгоритма Второй способ получения набора основан на вы- В качестве представления смысла самого выра делении грамматических основ из предложений. жения мы также взяли результаты, возвращенные Так как во многих случаях при запросе, совпадаю- поисковой системой по запросу, совпадающему с щем с выделенными основами, несколько первых этим выражением. Поиск проводился по точной десятков результатов поиска содержали только сам фразе.

рассматриваемый текст, мы добавили к запросу тре- Как было упомянуто, для сравнения текстов мы бование об отсутствии в результатах целевого вы- выбрали косинусную меру близости. Предваритель ражения. но все тексты прошли процедуру стемминга с по мощью стеммера Snowball [18] для русского языка.

Результаты, представленные в таблицах 1, 2, по казывают, что наборы, представляющие смыслы буквальных употреблений, действительно ближе к фицировано правильно, 8 % – неправильно, остав смыслам своих контекстов, чем смыслы употребле- шиеся 25 % попали в область неопределенности ний метафорических, что подтверждает гипотезу, на (значение косинусной меры от 0,1 до 0,2). В случае которой основан исследуемый метод. Результаты буквальных употреблений правильно было класси показывают, что различие значений более заметно фицировано 62 %, 23 % – неправильно, 15% попало при использовании лексических цепей (табл. 1), чем в область неопределенности.

при использовании грамматических основ (табл. 2).

При этом различие лучше прослеживается на набо- 6 Заключение ре из 10 первых результатов. В этом случае для 9 из В данной работе мы предложили и исследовали 10 контекстов выражений, употребленных метафо метод обнаружения выражений, употребленных в рически, значение косинусной меры составляет 0, переносном смысле. Метод основан на идее диффе и менее. А для 8 из 10 буквальных контекстов – 0, ренциации смыслов, заключающейся в том, что су и более. Таким образом, мы принимаем значение щественное различие между смыслом выражения и косинусной меры, равное 0,1 и менее, за признак смыслом окружающего его контекста указывает на существенного различия наборов текстов, а значе то, что выражение в этом контексте употреблено в ние, равное 0,2 или более, предлагаем считать при переносном смысле. Мы рассмотрели два способа знаком буквального употребления.

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

го для того, чтобы считать рассматриваемое в кон Одним из направлений дальнейшей работы яв тексте выражение употребленным в переносном ляется более глубокое изучение проблемы автома значении, мы принимаем достаточно малое значе тического выделения метафорических употребле ние косинусной меры близости между наборами, ний, в частности, разработка алгоритма извлечения представляющими смысл самого выражения и подобных употреблений (нахождения в произволь смысл контекста. За достаточно малое значение ко ном тексте выражений, употребленных метафориче синусной меры мы принимаем 0,1 и менее.

ски) с учетом опыта данного исследования.

5.5 Оценка качества алгоритма Мы также планируем рассмотреть задачи выде ления других высокоуровневых конструкций, в ча На втором этапе экспериментов мы выбрали не стности, конструкций, интересных с точки зрения сколько контекстов различных выражений и приме определения индивидуального авторского стиля.

нили к ним уточненный алгоритм, полученный в результате первого этапа. Как показано на рисунке, 67 % метафорических употреблений было класси Рис. Значения косинусной меры близости для различных выражений Литература Figurative language detection techniques based on the sense differentiating [1] Батов В.И., Сорокин Ю.А. Атрибуция текста на основе объективных характеристик// Серия язы Daria Bogdanova, Boris Novikov ка и литературы. – 1975. – Т. 34, № 1.

[2] Barzilay R., Elhadad M. Using lexical chains for In this paper, we propose an idea of sense differentia text summarization// Proc. of the Intelligent Scalable tion and state a figurative language detection techniques Text Summarization Workshop, 1997. based on this idea. We provide a study of the proposed [3] Berry M.W. Survey of text mining: clustering, clas- algorithm: at first, we test the idea of sense differentia sification, and retrieval. – Springer, 2003. tion and estimate the parameters of the algorithm, then [4] Birke J., Sarkar A. A clustering approach for the we evaluate the obtained algorithm. Our experiments nearly unsupervised recognition of nonliteral lan- show that the proposed techniques provide acceptable guage// Proc. of EACL-06, 2006. precision.

[5] Black M. Metaphor// Proc. of the Aristotelian Soci ety. – 1954. – P. 273-294. Работа выполнена при частичной финансовой под [6] Cover T.M., Hart P.E. Nearest neighbor pattern держке РФФИ (проект 10-07-00156) и гранта ком classification// IEEE Transactions on Information пании Google Theory. 1967. – V. 13, No 1. – P. 21-27.

[7] Galley M., McKeown K. Improving word sense disambiguation in lexical chaining// Proc. of IJCAI 2003.

[8] Katz G., Giesbrecht E. Automatic identification of non-compositional multiword expressions using la tent semantic analysis// Proc. of the ACL/COLING 06 Workshop on Multiword Expressions: Identify ing and Exploiting Underlying Properties, 2006.

[9] Li L., Sporleder C. Classifier combination for con textual idiom detection without labelled data// Proc.

of the 2009 Conf. on Empirical Methods in Natural Language Processing, 2009. – P. 315-323.

[10] Medelyan O. Computing lexical chains with graph clustering//ACL 2007, 2007.

[11] Mihalcea R., Corley C., Strapparava C. Cor pus-based and knowledge-based measures of text semantic similarity// Proc. of AAAI-06, 2006.

[12] Morris J., Hirst G.. Lexical cohesion computed by thesaural relations as an indicator of the structure of text// Computational Linguistics. – 1991. – V. 17, No 1. – P.21-43.

[13] Nissim M., Markert K. Syntactic features and word similarity for supervised metonymy resolu tion// Proc. of the 41st Annual Meeting of the Asso ciation for Computational Linguistics (ACL-03), 2003. – P. 56-63.

[14] Salton G, Wong A, Yang C.-S. A vector space model for automatic indexing// Communications of the ACM. – 1975. – V. 18. – P. 613-620.

[15] Schutze H. Automatic word sense discrimina tion// Computational Linguistics. – 1998. – V. 24, No 1. – P. 97-123.

[16] Sporleder C., Li L. Unsupervised recognition of literal and non-literal use of idiomatic expres sions// Proc. of EACL-09, 2009.

[17] Stamatatos E. A survey of modern authorship attribution methods// J. of the American Society for Information Science and Technology. – 2009. – V. 60, No 3. – P. 538-556.

[18] The Snowball Home Page. – http://snowball.

tartarus.org/.

[19] The WordNet Home Page. – http://wordnet.

princeton.edu/.

Анализ машинописных подписей к фотографиям в цифровом альбоме А.Н. Талбонен, А.А. Рогов Петрозаводский государственный университет perhetal@onego.ru, rogov@psu.karelia.ru факты:

Аннотация • оригинальные снимки и подписи к ним бы Статья посвящена вопросам формирования ли сделаны достаточно давно, что негативно сказа электронной коллекции фотографий строи- лось на их качестве;

тельства Беломорско-Балтийского канала. В • цифровые изображения были получены ме статье описаны первые этапы проделанной тодом фотографирования, при этом было изначаль работы, а именно, считывание подписей к но использовано достаточно низкое разрешение: фотографиям и оценка качества их распо- dpi;

знавания. • полученные снимки были сжаты в формат JPEG, что также сказалось на качестве изображений;

1 Особенности задачи • все изображения – черно-белые.

Типичный пример изображения можно увидеть Рассматриваемая в данной статье задача возник- на рис. 1.

ла вследствие необходимости организации поиска в большом массиве цифровых фотографий, относя щихся к одной более крупной тематике. В качестве исходного материала выступила коллекция снимков строительства Беломорско-Балтийского канала (ББК), сделанных в 1930-е годы. Данная коллекция состоит из 8-ми альбомов в среднем по 800 снимков в каждом, что в общей сложности составляет почти 6,5 тыс. изображений, и находится в Карельском государственном краеведческом музее. Каждое изо бражение данной коллекции представляет собой сфотографированный лист, на который были на клеены оригинальная фотография, а также подпись к фотографии в виде небольшой бумажной полоски, с машинописным текстом. Данный текст содержит информацию о времени, месте нахождения объекта снимка, кроме того, кратко описываются содержа ние объекта и сюжет. Помимо фотографии подпись Рис. 1. Пример изображения коллекции, посвящен также несет в себе определенную ценность. В част- ной строительству ББК ности, приведение конкретной подписи в электрон В данных условиях возникает целый ряд про ный текст с последующим логическим разбиением блем, связанных с распознаванием текста подписей.

на составляющие: номер, время, место, сюжет, объ 1. Подписи на цифровых изображениях харак ект, – позволит выполнить классификацию изобра теризуются низким качеством, а именно:

жений данной коллекции по любому из данных при a. на текстовом фоне присутствует шум, кото знаков. Таким образом, пользователь сможет фильт рый обусловлен как изношенностью бумаги, так ровать коллекцию и находить только интересующие и неизбежно возникающей размытостью при его изображения, указывая в поиске нужные пара сжатии растрового изображения в JPEG;

метры.

b. аналогичный шум наблюдается на участках На процесс преобразования подписей к фотогра литер;

фиям в электронно-текстовую форму для после c. отсутствует резкость линий букв текста;

дующего анализа существенно повлияли следующие d. ровни серого текста и фона на некоторых фотографиях отличаются незначительно;

Труды 12й Всероссийской научной конференции 2. Распознавать текст на изображениях, под «Электронные библиотеки: перспективные методы и ставляя их в готовую систему распознавания, на технологии, электронные коллекции» – RCDL’2010, пример, FineReader, крайне затруднительно из-за Казань, Россия, того, что OCR в некоторых случаях ошибочно рас познает элементы участка на самой фотографии как j = W jn / N o.

j отдельные символы, что приводит к многочислен Как видно из таблицы, количество файлов, кото ным ошибкам и возникновению мусора. Кроме того, рые были хоть как-то распознаны, равно 8, что со встречаются случаи, когда OCR вообще не находит ставляет всего 66% от общего количества файлов. А области с текстом на фоне фотографии либо из все общая доля правильно распознанных слов, которая го текста обнаруживается и распознается только вычисляется по формуле = W jn / N o,, со одна часть вследствие неправильного определения j границ области текста. j j ставляет всего лишь 38%. Более того, только в поло Таким образом, все вышеперечисленные про вине случаев OCR смогла правильно выделить об блемы вынуждают искать различные пути улучше ласть текста. Основная причина таких низких ре ния качества как результатов, так и исходных дан зультатов – наличие в процессе распознавания ных.

большой помехи в виде фотографии. Поэтому для 2 Анализ непосредственного решения за- повышения результатов распознавания целесооб дачи разно отделить область текста от остальной части изображения и распознавать только текстосодержа Для проведения непосредственного анализа ОCR щие области.

были отобраны 12 изображений с характерными недостатками, которые были описаны в предыду 3 Выделение области подписи щем разделе. Ниже представлены основные резуль таты непосредственного распознавания текста.

В качестве первого улучшения качества распо Таблица 1. Результаты прямого распознавания изо- знавания был реализован несложный эвристический бражений алгоритм выделения границ подписи на изображе нии. Основная эвристика заключается в принятии j № Gj W jn No Ir того, что в большинстве случаев область текста j j вплотную прилегает к одной стороне изображения, 1 9 16 1 0 0. занимая ее целиком по длине, тем самым разделяя 2 9 15 1 1 0. изображение на две разные по содержанию части.

3 0 7 0 0 0. Кроме того, в большинстве случаев область текста 4 0 11 0 0 0. представляет собой однотонный прямоугольник с 5 6 7 1 0 0. расположенным на нем текстом, цвет которого рез 6 1 8 0 1 0. ко контрастирует с цветом фона, а сам текст отстоит 7 5 7 1 4 0. от нижнего края области текста (в случае, если со 8 0 10 0 0 0.00 риентировать ее прямо) минимум на 10 пикселей, 9 0 16 0 0 0.00 что является достаточным для определения среднего 10 10 11 1 3 0.71 цвета фона. На основе анализа изображений было 11 8 11 0 6 0.47 выявлено, что высота области, содержащей одну 12 9 12 1 6 0.50 строку текста, не превышает 30 пикселей.

Итого 57 87 6 21 0.38 Рассмотрим случай, когда подпись располагается в нижней части изображения прямо под фотографи В табл. 1 использованы следующие обозначения: ей. Поскольку текст и фотография в большинстве W jn – общее количество правильно распознан- случаев располагаются горизонтально, а цвет фона сильно контрастирует как с текстом, так и с фото ных слов файла j;

графией, то для выделения границ подписи доста N o – общее количество слов на изображении;

точно оперировать средней яркостью горизонталь j ных линий. Данный параметр равен среднему ариф I r – индекс распознавания области текста;

он метическому значений яркостей пикселей одной j конкретной горизонтальной линии. Для выявления равен 1 в случае, когда OCR правильно находит и граничной горизонтальной линии, отделяющей под выделяет область текста;

в случае, когда OCR выде пись от фотографии, был использован следующий ляет мусор или текст не полностью, пропуская оп алгоритм.

ределенные области, индекс равняется 0;

1. Будем вести отсчет снизу вверх.

G j – количество слов-мусора;

к ним относятся 2. Рассчитаем среднюю яркость первых NBr слова, которые не могут быть результатом ошибоч- строк изображения. Полученное значение Grad при ного распознавания оригинальных слов, т. е. те, ко- близительно равно средней яркости всей области торым на изображении не соответствует ни одно подписи и будет являться эталоном для сравнения с слово;

данные слова возникают из-за ошибочного яркостями других линий.

распознавания элементов изображения, не содер- 3. Зададим порог GradBr, который определяет жащего текст;

максимальное отклонение яркости «светлого» пик j – доля правильно распознанных слов: селя от средней яркости фона Grad. Если модуль разности яркости текущего пикселя и Grad будет меньше GradBr, то данный пиксель будем считать 11 8 11 1 0 0. «светлым». 12 10 12 1 3 0. 4. Найдем «специальную среднюю яркость Итого 102 131 11 8 0. строки», которая будет равна доле «светлых» пиксе лей данной строки. Как видно из табл. 2, все файлы на этот раз были 5. Зададим порог яркости строки BGBr, выше распознаны, а общая доля правильно распознанных которого строка будет считаться «светлой», а ниже слов составила уже 73 %. При этом процент пра – «темной». Для наглядности можно ввести парал- вильно выделенных областей составил 92 %. Таким лельное 2-е изображение с такими же размерами, образом, введение в решение данного алгоритма что и оригинальное, и окрашивать каждую ее строку значительно повысило качество распознавания тек в черный / белый цвет, если соответствующая стро- ста. Другим важным фактором в применении этого ка оригинального изображения будет «темной» / метода является то, что оригинальные изображения, «светлой». Таким образом, на месте строк текста мы которые используются, были предоставлены Ка получим полосы черного цвета определенной тол- рельским государственным краеведческим музеем и щины. являются его собственностью. Поэтому решение 6. Зададим максимально допустимую толщину обрабатывать только изображения подписей, а не темных полос, соответствующих тексту, TH. сами фотографии, является приемлемым для вла 7. Первые NBr строк автоматически считаем дельца данных фотографий.

«светлыми». Несмотря на значительное улучшение качества 8. Далее, для каждой строки будет определять, распознавания, результат остается неудовлетвори является ли она «темной» или «светлой». тельным, поэтому было принято решение провести 9. Будем запоминать границы полос из иду- предварительную обработку изображений подписей.

щих подряд «темных» строк.

10. При достижении толщины текущей «тем- 4 Методы обработки изображений ной» полосы выше TH алгоритм прекращаем.

11. Наиболее высокая граница «темной» поло- Данные изображения характеризуются низким сы с толщиной не больше TH будет являться грани- качеством. Распознаванию мешают недостаточная цей подписи. четкость символов текста и так называемые эффек 12. После этого копируем область изображения ты «соль-перец», представляющие собой хаотично «ниже» найденной границы. «Ниже» означает – от расположенные пиксели с экстремальными значе начальной линии до границы. ниями яркости (0 и ближе к 0 – «перец», 255 и бли На рис. 2 представлена область подписи изобра- же к 255 – «соль»). Для того чтобы избавиться от жения на рис. 1, выделенная данным методом. лишних шумов и повысить качество изображения, традиционно используют различные методы улуч шения изображений. В данной работе были рас смотрены и опробованы 12 методов, перечисленных Рис. 2. Подпись для изображения на рис. ниже. Для удобства описания методов улучшения Данный алгоритм будет выполняться аналогично изображений введем некоторые понятия:

для случаев, когда подпись располагается в других f ( x, y ), для которой 1. Функция частях. Разница будет только в направлении отсчета x [0;

W ), y [0;

H );

x, y, где W и H – ши линий.

рина и высота изображения, а f называется Ниже представлены результаты распознавания вышеуказанных 12 изображений с той разницей, что функцией изображения.

на них заранее были выделены области текста. В 2. Функция нормирования N ( f ) :

f (x, y ) min f (i, j ) данном случае в OCR подаются только изображения подписей вместо целых изображений.

N ( f (x, y )) = i, j, max f (i, j ) min f (i, j ) Таблица 2. Результаты распознавания выделенной i, j i, j области текста i [0;

W ), j [0;

H );

i, j.

где j № Gj n o r W N I 3. Все арифметические операции над функ j j j циями изображений выполняются попиксельно, на 1 15 16 1 0 0. пример:

2 10 15 0 1 0. f + g = h x, y : h ( x, y ) = f ( x, y ) + g ( x, y ).

3 7 7 1 0 1. 4. Ядро (маска) свертки M определяется как 4 9 11 1 1 0. 5 6 7 1 0 0.86 матрица размером R S с центром в точке (r, s ).

6 6 8 1 0 0. Обычно R = S, а отсчет координат начинается с 0.

7 5 7 1 0 0. 5. Функция свертки Conv(f ( x, y ), M, x, y )) 8 8 10 1 1 0. функции изображения f ( x, y ) с помощью ядра 9 10 16 1 1 0. 10 8 11 1 1 0. сравнению с диапазоном значений оригинальной (маски) M с центром в (r, s ) и фактором F оп функции, поэтому первую функцию необходимо ределяется следующим образом [2]:

нормировать. В результате итоговая функция будет 1 R r 1 S s Conv ( f ( x, y ), M, x, y ) = f ( x + i, y + j ) определяться следующим образом:

F i = r j = s h( x, y )=N ( f ( x, y ) + NConv(f ( x, y ), M, x, y ))).

M (i + r, j + s ).

Данная функция будет обозначена как ALaplas.

Будем считать, что центр ядра является централь b. Выровненное аддитивное изображение с ным элементом матрицы M, а фактор F = 1, если использованием простого Лапласиана. Данная иные значения не оговорены. функция изображения сходна с предыдущей с той 6. Функция изображения h( x, y ) называется разницей, что она подвергается операции гисто аддитивной, если она была получена в результате граммного выравнивания с оригинальной функцией.

арифметической операции результирующей функ- Обозначим данную функцию как EALaplass.

ции g ( x, y ) и оригинальной f ( x, y ). Например, c. Аддитивное изображение с использованием сложного Лапласиана. Усложнение заключается в h( x, y) = g ( x, y) + f ( x, y) – часто распространен том, что Лапласиан высчитывается не над ориги ный прием повышения четкости изображения за нальным изображением, а над его размытием. Раз счет наложения на него результата применения Ла мытием изображения f ( x, y ) будет результат пласиана.

свертки это изображения со следующим ядром:

7. Функция изображения h( x, y ) считается 1 1 выровненной к оригинальной функции f ( x, y ), если S = 1 1 1, к первой было применено гистограммное выравни 1 1 вание [2]. Перейдем к описанию рассмотренных в данной при этом фактор равняется 9. Вместо того, чтобы работе методов: последовательно применять две операции свертки с 1. Эвристический метод порогового отсече- двумя разными ядрами, эти ядра можно заменить ния без параметров. Суть метода состоит в том, что одним равноценным ядром размерности 5 5 :

на изображении устраняются все пиксели (а именно, 1 2 3 2 заменяются белым цветом), величина которых равна 2 6 6 или превышает некоторое значение. Из-за необхо, E = 3 4 4 димости определять это значение и того, что оно может зависеть от общей яркости изображения (чем 2 6 6 темнее фон, тем меньше должно быть пороговое 1 2 3 2 значение), было решено использовать следующую формулу определения порога: фактор равен 9. Тогда итоговое изображение будет определяться так:

C = (W H )1 f ( x, y ) + D,, h( x, y )=N ( f ( x, y ) + NConv(f ( x, y ), M, x, y ))).

x, y где D – некоторое целое значение, выбираемое эм- Обозначим данную функцию как AELaplass.

пирически и устраняющее вклад темных пикселей в d. Выровненное аддитивное изображение с оценку средней яркости фона. В нашем случае было использованием сложного Лапласиана. Как и в слу выбрано значение 10. Таким образом, итоговая чае 2.b, результирующая функция выравнивается по функция изображения определяется следующим гистограмме с оригинальным изображением. Обо образом: значим данную функцию как EAELaplass.

f ( x, y ), f ( x, y ) C, 3. Методы на основе выделения границ h ( x, y ) = a. Оператор Собеля [6]. Данный оператор ис 0, f ( x, y ) C.

пользует две свертки изображения с ядрами 1 0 Обозначим данную функцию как Cut. 1 2 M = 2 0 2.

2. Методы пространственной фильтрации, M1 = 0 0 0, применяющие Лапласиан [2, 3]. 1 0 1 2 a. Аддитивное изображение с использованием На основе полученных сверток G1 и G2 вычисляет простого Лапласиана. Ядро Лапласиана выглядит следующим образом: ся общая свертка 1 1.

G ( x, y ) = G1 ( x, y ) 2 + G2 ( x, y ) 2.

M = 1 9 1 1 Полученная свертка вычитается из оригинального Результат свертки функции f ( x, y ) с таким изображения: h( x, y ) = f ( x, y ) G ( x, y ). Обозначим ядром дает дискретный Лапласиан g ( x, y ). Обычно данную функцию как ASobel.

диапазон значений g ( x, y ) резко отличается по b. Оператор Робертса [7]. Метод основан на 5 Автоматическое распознавание и кор применении двух ядер рекция ошибок 0 1 0 1 и M 2 = 1 0, M1 = В предыдущих двух примерах количество распо знанных слов и общее количество слов определя лись вручную по мере просмотра каждого изобра каждое из них имеет центр в точке (0,0). Конечное жения в OCR. Однако для оценки качества распо изображение определяется аналогично оператору знавания больших коллекций данный метод не явля Собеля. Обозначим данную функцию как ARobets.

ется рациональным. Кроме того, результирующий c. Оператор Прюитт [8]. Данный оператор текст содержал в себе определенный процесс некор использует две свертки изображения с ядрами ректно распознанных слов, т. е. таких слов, в кото 1 1 1 0 рых присутствовало небольшое количество ошибок 0.

M 1 = 1 0 1, M 2 = 0 в символах (не больше 2). Человек вручную может 1 1 0 1 легко «восстановить» оригинальное слово, однако это невозможно при больших объемах данных. По Конечное изображение определяется аналогично этому было решено разработать специальный тек оператору Собеля. Обозначим данную функцию как стовый анализатор, предназначенный для выявления APrewitt.

и исправления слов с ошибками, а также для разде d. Оператор Щарра [6]. Данный оператор ис ления всего текста на семантические составляющие, пользует две свертки изображения с ядрами а именно: дата (день, месяц, год, а также слово, обо 3 0 3 10 значающее дату) и отдельные предложения. Анали 0, M 2 = 10 0 10.

M1 = 0 0 затор представляет собой скрипт на языке PHP. Ал 3 0 3 10 3 горитм работы анализатора основан на применении функции поиска похожих слов. Ниже приведено Конечное изображение определяется аналогично описание данной функции:

оператору Собеля. Обозначим данную функцию как 1. За основу алгоритма взята функция, вычис AScarr.

ляющая расстояние Левенштейна [9, 11] (минималь 4. Методы сглаживания изображения ное количество замен, добавлений или удалений a. Простое сглаживание [4, 12]. Метод осно букв, для того чтобы из слова A получить слово B).

ван на свертке изображения с ядром:

2. Алгоритм выполняет последовательное вы 1 1 числения расстояний Левенштейна для данного сло M = 1 1 1, фактор равен 9. Итоговое изобра- ва, сравнивая его с каждым словом массива слово 1 1 1 форм.

3. В результате алгоритм находит слово, кото жение определяется как рое ближе всего к данному.

4. В случае, когда минимальное расстояние h( x, y )=NConv(f ( x, y ), M, x, y )).

Левенштейна среди всех слов массива превышает Обозначим данную функцию как Smooth. значение 3, алгоритм сообщает, что данное слово не b. Размытие по Гауссу [4, 12]. Данный метод распознано.

1 2 1 5. В случае, когда для слова, содержащего не, фактор равен 16.

использует ядро: сколько ошибок, обнаруживается исправленная сло M = 2 1 воформа, оно считается исправленным и исправля 1 2 ется на эту словоформу.

Итоговое изображение определяется как Каждый файл, поданный на вход данному скрип ту, обрабатывается следующим образом:

h( x, y )=NConv(f ( x, y ), M, x, y )).

1. Задается массив слов-названий месяцев в Обозначим данную функцию как Gauss. формах: в именительном, родительном падежах и в 5. Метод медианного фильтра [5]. Для данного сокращении.

случая будем рассматривать окрестность точки 2. Задается массив слов русского языка, вклю ( x, y ) радиусом в 1 пиксель, представляющую со- чая все словоформы. В качестве массива выступила база данных словоформ, найденная в интернете [1].

бой множество из 8-ми пикселей, окружающих точ 3. Задается массив всех возможных предлогов.

ку ( x, y ), а также содержащую саму точку ( x, y ).

4. Задается массив всех возможных окончаний Обозначим окрестность как U f ( x, y ). Для каждой числительных.

точки ( x, y ) изображения f ( x, y ) находится ме- 5. В тексте находится ключевое слово, отве чающее за конец даты: «год» или «г.». Наличие од диана множества U ( x, y ). Данное значение будет ного из этих слов означает наличие даты в тексте.

являться соответствующим значением пикселя Часть текста, расположенная слева от данного клю ( x, y ) итогового изображения чевого слова, копируется в строку даты. Все, что g ( x, y ) : g ( x, y ) = median(U f ( x, y )). справа, копируется в строку текста.

Обозначим данный метод как Median.

• 6. На основе двух самых распространенных оригинальное слово – указывается только форм записи даты: день, месяц, год и ме- для исправленных слов с целью дальнейшей сяц, день, год выполняется поиск дня, месяца проверки правильности исправления.

и года. Год и день определяются как числа, распо- Для дальнейшей обработки полученных мета ложенные в определенном порядке относительно файлов с целью определения качества распознава месяца. Поиск названия месяца осуществляется с ния, а также для организации альбомов с целью про помощью алгоритма поиска похожих слов, описан- смотра полученных результатов распознавания и ного выше. сравнения их с оригинальными изображениями 7. Строка текста разбивается на предложения подписей была разработана специальная программа (разделитель предложений – точка). Каждое пред- CaptionViewer. Программа предполагает создание ложение разделяется на слова (разделитель слов – альбомов фотографий на основе данных метафайла все возможные пробелы и пунктуация). с целью дальнейшей обработки уже целых альбо 8. Для каждого слова в массиве словоформ с мов. Информация об альбомах и метафайлах пред помощью вышеописанного метода находится соот- ставлена следующей базой данных:

ветствующая словоформа. Слово считается распо- Альбом:

знанным, если для него была найдена словоформа. • идентификатор альбома;

9. Отдельно выполняется поиск чисел, предло- • название альбома;

гов, числительных, символов номера, которые также • каталог изображений подписей;

считаются распознанными словами. • каталог текстовых файлов подписей;

10. Слово, состоящее только из цифр, считается Файл:

числом. • идентификатор файла;

11. Если слово, предшествующее числу, состо • идентификатор альбома;

ит из одного – двух служебных символов либо явля • индикатор даты;

ется одним из символов N, №, #, то оно заменяется • день;

символом «№» и считается символом номера.

• месяц;

12. Слово, совпадающее с одним из слов масси • год;

ва предлогов, считается предлогом.

• метаинформация.

13. Слово, состоящее из числа, за которым сле Данные о структуре отдельного файла было ре дует окончание из массива окончаний числительных шено хранить в одном единственном поле за счет с возможным разделением дефисом, считается чис сериализации структур данных. Информация о со лительным.

держащихся в файле предложениях и словах хра 14. Все остальные слова считаются мусором.

нится в формате JSON [13]. Этот текстовый формат 15. Полученная семантическая структура, со хранения объектов лучшим образом подходит для держащая информацию обо всех предложениях, хранения иерархических данных в одном поле. Бла словах и их типах, записывается в метафайл в опре годаря простоте и скорости сериализации/ десериа деленном формате.

лизации данные метафайла пригодны для быстрой В процессе работы скрипта в памяти процесса обработки.

накапливается информация обо всех предложениях, словах и типах слов обрабатываемого файла. Для 6 Оценка качества распознавания, срав удобства работы информация по всем файлам одно нение различных методов распознавания го обрабатываемого альбома записывается в один альбомов файл. Данная информация образует следующую иерархическую структуру. Для сравнения результатов распознавания изо Файл: бражений, полученных различными методами • список метафайлов;

улучшения, были выделены следующие признаки:

Метафайл:

Di – показатель определения даты файлов аль • имя файла;

бома i. Для каждого альбома рассчитывается сум • индикатор даты – логическое значение, оп ределяющее наличие даты в метафайле;

марный коэффициент Di. Для каждого файла аль • день;

бома i коэффициент увеличивается на 1 при распо • месяц;

знавании компонент даты:

• год;

a. ключевое слово конца даты («г.» или «год»);

• список предложений;

b. год;

Предложение: c. месяц;

• список слов;

d. день.

Слово:

Di рассчитывается как Di0 /(4ni ), где Далее • слово;

ni – количество файлов в альбоме.

• тип слова (слово, исправленное слово, пред лог, числительное и др.);

i – доля правильно распознанных слов для альбома i.

изображения с использованием сложного Лапласиа Пусть Wijo – количество слов в оригинальном на» и «Метод медианного фильтра».

текстовом файле j для альбома i. Предполагается, что изначально n файлов были распознаны разными 7 Дальнейшие планы методами, а результаты распознавания были сохра нены в разных альбомах (отдельный альбом для ка 1. Семантический анализ подписи. С помощью ждого метода распознавания). Оригинальным фай семантического анализа подписи предполагается лом i для альбома j называется текстовый файл i, выделять такие атрибуты, как место, сюжет и объ полученный распознаванием с помощью метода j.

ект. Способ выделения времени фотографирования Пусть Wijn – количество правильно распознан описан в разделе 5. Выделение остальных атрибутов ных слов в файле i для альбома j. Найдем предполагается осуществлять также с использова W jo = max Wijo – наибольшее количество слов распо- нием словаря-тезауруса. Методы семантического i анализа, основанные на использовании словаря знанного текста для файла j и максимальное общее тезауруса, позволят определить в сообщении стили количество слов оригинальных текстов: W o = W o.

стически маркированную лексику, наличие которой j в подписи отнесет ее к определенным атрибутам.

j Тогда = W n / W o. Методы синтаксического анализа позволят опреде ij лять в подписи те или иные синтаксические конст i j рукции, типичные для каждого атрибута.


Анализ i* – максимальная доля правильно распознан- контекстуального окружения части текста позволит установить дополнительные признаки того, принад ных слов среди файлов альбома i: i* = max ij, где лежит ли данная часть к определенному атрибуту j или нет. Предполагается использование статистиче ij = W / W. n o ij j ских методов анализа текста подписи. Такие методы С помощью разработанной программы Caption- используются, например, для выявления стилисти Viewer было проведено сравнение методов предва- ческих особенностей текста. Они предполагают по рительной обработки изображений, описанных в строение вероятностной модели на основе анализа разделе 4. Полученные результаты анализа пред- существующей выборки данных. Применение по ставлены в табл. 3. Значения критериев Di, i и добной модели позволит высчитывать для каждого части подписи некоторый коэффициент (соответст i* указаны в процентах.

вующий оценке вероятности того, что часть подпи Таблица 3. Результаты текстового анализа различ- си принадлежит данному атрибуту) и идентифици ными методами. Словом Original был назван альбом, ровать его, если значение коэффициента выше неко полученный прямым распознаванием выделенных торого установленного порогового значения.

подписей, т. е. без предварительного применения Так, например, признаками места является нали методов улучшения изображений чие двух подряд идущих слов, первое относится к наименованию вида места (поселок, губа, деревня и i Имя альбома / i* Di т. д.). Второе относится к именам собственным метода (№ 4, Ведлозеро и т. д.), причем место фотографи Cut 98 57 88 рования может быть задано одним или двумя значе ALaplas 60 35 88 ниями. Например, на представленной подписи – это поселок № 4 и губа озера Ведлозеро. При анализе EALaplas 100 50 подписей были использованы онтологии географи AELaplas 95 56 ческих названий. Заметим, что на подписях были EAELaplas 98 56 использованы некоторые сокращения географиче ASobel 72 45 ских названий, которые были включены в онтологи ARoberts 85 43 ческий класс, например, Водл. вместо Водлозера, и APrewitt 75 44 др.

AScharr 82 53 2. Текстурный и контурный анализы. С по Smooth 95 55 мощью методов анализа текстур участков фотогра Gauss 92 54 фий предполагается выделять отдельные объекты:

Median 100 56 водную поверхность, стенки карьера, людей, флаги, Original 90 52 растяжки с лозунгами и т. д. Сочетание текстурного и контурного анализов позволит выделять дома, Как видно из табл. 3, альбом Original уступает по машины, людей и т. д. Заметим, что текстурные ха указанным критериям многим из других альбомов, рактеристики существенно зависят от времени которые были получены с помощью улучшения съемки (зима или лето).

изображений. К сожалению, добиться стопроцент Для решения задач поиска похожих текстур бу ного результата не удалось. Наилучшими методами дут использоваться методы:

оказались «Эвристический метод порогового отсе • фрактальная размерность Реньи [10];

чения без параметров», «Выравнивание аддитивного • вейвлет-анализ [2];

• набор фильтров Габора [14]. Литература Распознавание текстур ведется методом обуче [1] Генерация всех словоформ (по мотивам ния с учителем. Выделяются обучающая и кон трольная выборки. На фотографиях из обучающей словарей Ispell). – http://ispell.narod.ru/.

выборки выделяем прямоугольные фрагменты разы- [2] Гонсалес Р., Вудс Р. Цифровая обработка скиваемого объекта размером n m пикселей. изображений. – М.: Техносфера, 2005. – 1072 с.

[3] Дискретный оператор Лапласа. – Википедия. – Анализируя их, находим для рассматриваемого ме http://ru.wikipedia.org/wiki/Дискретный_оператор тода граничные параметры принадлежности текстур _Лапласа.

к типу разыскиваемых объектов. Обрабатывая кон [4] Каньковски П. Как работают фильтры размытия.

трольную выборку, проверяем работу алгоритма – http://www.computerra.ru/gid/rtfm/graphic/ (правильность поиска).

35934/.

Определение наличия людей на фотографиях [5] Медианный фильтр. – Википедия. – http://ru.

проводится согласно следующего алгоритма. С по wikipedia.org/wiki/Медианный_фильтр.

мощью текстурного анализа находится участок с [6] Оператор Собеля. – Википедия. – http://ru.

текстурой похожей на лицо человека, затем опреде wikipedia.org/wiki/Оператор_Собеля.

ляется контур этого участка, проводится его регуа [7] Перекрестный оператор Робертса. – Википедия.

лизация и контур сравнивается с возможными кон – http://ru.wikipedia.org/wiki/Перекрёстный_ турами лиц, учитывая наличие волос и головных оператор_Робертса.

уборов, т. е. обрезанный овал.

[8] Прюитт. – Википедия. – http://ru.wikipedia.org/ 3. Планируется разработать программную сис wiki/Прюитт.

тему для анализа фотографий, которая позволит [9] Расстояние Левенштейна. – Википедия. – http:// указывать для каждой фотографии участки, соответ ru.wikipedia.org/wiki/Расстояние_Левенштейна.

ствующие объектам, а также действия, совершаемые [10] Рогов А.А., Спиридонов К.Н. Применение над ними. С помощью данной программы можно спектра фрактальных размерностей Реньи как будет наделить каждую фотографию дополнитель инварианта графического изображения // Вест ными сложными атрибутами.

ник Санкт-Петербургского университета. Сер.

4. Планируется разработать информационную 10. – 2008. – Вып. 2. – С. 30-43.

систему поиска фотографий по атрибутам, получен [11] Руководство по PHP. Levenshtein. – http:

ным из подписи и анализа текстур. Таким образом, //www.php.ru/manual/function.levenshtein.html.

можно будет найти, например, все фотографии, на [12] Image Processing for Dummies with C# and которых изображены карьер или какое-нибудь ад GDI+. Part 2. – Convolution Filters. – http://www.

министративное здание.

codeproject.com/KB/GDI-plus/csharpfilters.aspx.

[13] JSON. – Википедия. – http://ru.wikipedia.org/ 8 Заключение wiki/JSON.

[14] Movellan J.R. Tutorial on Gabor filters. – В процессе решения поставленной задачи было http://mplab.ucsd.edu/tutorials/gabor.pdf/ сделано следующее:

• рассмотрены и опробованы различные спо Analysis of typewritten captions in digital собы распознавания больших объемов изображений;

• album реализованы различные методы улучшения изображений;

A.N. Talbonen, A.A. Rogov • разработан механизм исправления ошибок распознанного текста;

This article is devoted to problems of creating a digital • разработан формат хранения результатов collection of photos from White Sea-Baltic Canal’s con распознавания;

struction. The article contains a description of the first • step of carried work which aim was to read photos cap предложены различные критерии оценки tions and to evaluate a quality of their recognition.

качества распознавания текстов;

• создана программа, позволяющая работать с результатами распознавания и также сравнивать качество распознавания с помощью различных предложенных критериев.

Данная работа еще не закончена и будет про должена в направлении семантического анализа подписей и текстурного и контурного анализа фото графий.

Кластеризация текстовых документов на основе составных ключевых термов © В.Б. Барахнин, Д.А. Ткачев Институт вычислительных технологий СО РАН, г. Новосибирск Новосибирский государственный университет bar@ict.nsc.ru, relk-tda@yandex.ru тьи – далеко не всегда содержат классификацион Аннотация ные признаки, к тому же классификатор источника Классический подход к координатному ин- может не совпадать с классификатором, используе дексированию текстов с целью их после- мым создателями информационной системы.

дующей кластеризации заключается в ис- Другой распространенный подход к удовлетво пользовании средства анализа на основе те- рению информационных потребностей научных зауруса обрабатываемой предметной облас- работников – поиск «по аналогии» – заключается в ти. Но если вести речь об обработке корпу- нахождении документов, которые в том или ином сов текстов достаточно узких тематик, то в смысле аналогичны документу (или множеству до таких случаях требуются весьма подробные кументов), уже известному данному лицу (подроб тезаурусы, которые имеются (по крайней нее см., например, [1]).

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

чевых словосочетаний по сравнению с Проблема, возникающая в процессе индексиро весьма популярной кластеризацией на ос- вания документов, состоит в выборе структуры спи нове анализа только однословных ключе- ска ключевых слов: должен ли он состоять исклю вых термов, при этом для выделения клю- чительно из одиночных слов или он может вклю чевых словосочетаний используются обще- чать в себя и составные выражения? Конечно, со доступные программные средства, не тре- ставные ключевые слова более адекватно описыва бующие особых вычислительных затрат. ют предметную область, но при их использовании значительно усложняется морфологический анализ 1 Введение текста. Более того, в некоторых работах, например, в статье [2], содержащей подробный обзор совре Постоянный рост объема научной информации, менных методов классификации документов с ис представленной в электронной форме, делает акту пользованием ключевых слов, утверждается, что альным решение задачи разработки методики авто использование одиночных ключевых слов является матизированного вовлечения электронных докумен «наиболее приемлемым». Такой подход при нали тов в научно-информационный процесс. Одним из чии качественных средств морфологического ана важнейших этапов этого процесса является класси лиза представляется недостаточно обоснованным, фикация документов, поскольку при отсутствии по крайней мере, для коллекций документов, отно классификационных признаков поиск документа сящихся к какой-либо определенной узкой тематике человеком или его обработка интеллектуальной ин (данная оговорка сделана и в [2]), поскольку ис формационной системой может опираться только на пользование одиночных ключевых слов имеет серь простую проверку вхождения тех или иных терми езные теоретические недостатки [3]: возможность нов в текст документа. К сожалению, даже наиболее ложной координации, ложных синтагматических структурированные документы – журнальные ста связей и др.


Цель данной работы заключается в демонстра Труды 12й Всероссийской научной конференции ции практических преимуществ кластеризации до «Электронные библиотеки: перспективные методы и кументов на основе ключевых словосочетаний по технологии, электронные коллекции» – RCDL’2010, сравнению с кластеризацией на основе анализа Казань, Россия, только однословных ключевых термов, при этом для выделения ключевых словосочетаний исполь- что составные ключевые фразы, состоящие более зуются общедоступные программные средства, не чем из двух слов, будут давать лучший результат требующие особых вычислительных затрат. кластеризации, особенно если она производится на массиве документов близкой тематики. Вычисли тельные эксперименты с такими, более сложными 2 Алгоритм извлечения ключевых тер составными ключевыми термами, планируется про мов вести в дальнейшем.

Важной задачей обработки текстовых докумен- После завершения подсчета вхождений ключе тов, результат решения которой используется не вых слов и словосочетаний в документе необходимо только для их классификации (категоризации), но и произвести отделение наиболее значимых слов, от для извлечения из них информации и знаний, явля- ражающих контекстное содержание корпуса. Коли ется координатное индексирование, т. е. извлечение чество вхождений слов в текст в большинстве слу из текстов документов ключевых слов и словосоче- чаев поддается закону распределения частот Ципфа:

таний. если все слова упорядочить по убыванию частоты Классический подход к решению данной про- их использования, то частота n-го слова в этом спи блемы заключается в использовании средства ана- ске окажется примерно обратно пропорциональной лиза на основе тезауруса обрабатываемой предмет- его порядковому номеру (рангу). Для отделения ной области. Но метод выделения ключевых слов и одиночных ключевых слов использовался именно словосочетаний, основанный на анализе тезауруса закон Ципфа.

предметной области, имеет существенный недоста- Однако данный закон не работает для частоты ток: таким способом нельзя производить индекси- распределения ключевых словосочетаний. К данно рование корпусов текстов произвольных тематик. му выводу мы пришли, проанализировав большое Более того, если вести речь об обработке корпусов количество русскоязычных документов средней и текстов достаточно узких тематик, то в таких случа- большой размерности.

ях требуются весьма подробные тезаурусы, которые Для ограничения числа составных ключевых имеются (по крайней мере, в широком доступе) да- фраз, наиболее точно описывающих содержание леко не для всех предметных областей. Подход же, электронного документа, использовалась следую основанный на извлечении ключевых выражений щая закономерность, замеченная эмпирическим без априорных ограничений, носит гораздо более путем, которая проверялась на достаточно большом универсальный характер, хотя, естественно говоря, количестве корпусов текстов средней и большой несколько проигрывает в адекватности индексиро- величины:

вания. max(Frequency) word num (1) KeyPhrase(i):, Ввиду того, что в русском языке имена сущест- Frequency(i) вительные и прилагательные при склонении изме где max(Frequency) – максимальная частота встре няют свою форму, разработка эффективного алго чаемости 1-го (т. е. наиболее часто встречаемого) ритма автоматизации извлечения ключевых слов терма и всех его словоформ терма в корпусе тек является нетривиальной задачей, так как необходи стов);

Frequency(i) – частота встречаемости i-го, мо учитывать и те случаи, когда слова, образующие проверяемого, терма;

wordnum – желаемое (ориенти термин (т. е. ключевое слово), находятся не только в ровочно) количество отобранных термов.

именительном, но и в косвенных падежах.

Разумеется, данное условие (как и закон Ципфа) Для решения этой задачи мы опирались на мор весьма плохо работает на документах небольшого фологический анализ текстов и выделении ключе размера (типа аннотаций), поскольку в них частоты вых словосочетаний по морфологическим шаблонам всех однословных и многословных ключевых тер с использованием программного продукта компа минов приблизительно равны и стремятся к еди нии Яндекс (http://company.yandex.ru/technology/ ничному вхождению в рамках контекста документа.

mystem/), который является бесплатным для неком Для демонстрации качества отбора ключевых мерческих целей. При фильтрации и разборе произ слов и ключевых словосочетаний на основе морфо водился отсев стоп-слов. Ключевые словосочетания логических шаблонов приведем результаты их от отбирались по морфологическим шаблонам с уче бора из текст романа Л.Н. Толстого «Война и мир», том словоформ языка.

а также текста научной статьи философской на Для определения ключевых словосочетаний ис правленности (З.О. Османов «К вопросу о различе пользовались классические морфологические шаб нии эпистемологических категорий»), размер кото лоны, которые достаточно качественно определяют рой является совершенно обычным (средним) в искомые ключевые выражения:

пределах рамок, используемых для публикации на (Причастие) (Существительное) учных материалов.

(Прилагательное) (Существительное) В таблицах, представленных ниже, приводятся (Существительное) (Существительное твор. п.) результаты выделения ключевых терминов из доку (Существительное) (Существительное род. п.) ментов различной тематики. В нихе рядом с каждым Представленные морфологические шаблоны термом приведено количество его вхождений (в производят отбор составных ключевых выражений, различных формах) в текст документ. Для состав состоящих из двух слов. Есть основание полагать, ных ключевых термов: фраза в скобках – форма, в кластеризации корпуса научных статей близкой которой данное выражение встречалось последний тематики (см., например, [5]), хотя и обладающим раз («крайнее вхождение»), которое приводится для сравнительно большой вычислительной сложно облегчения (в необходимых случаях) понимания стью.

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

сических конструкций (к каковым из числа полу- Строится матрица схожести парных сочетаний ченных двухсловных термов можно отнести выра- каждого документа с каждым, т. е. матрица NxN, где жения «обладающее свойством», «следующим об- N равняется количеству документов в кластеризуе разом» и «изучаемых объектов») достаточно мал. мой выборке. На пересечении задаются меры сход Это позволяет сделать вывод о том, что данная ме- ства документов в шкале [0;

1], причем 0 соответст тодика выбора однословных и двухсловных ключе- вует полному различию документов, а 1 – полному вых термов показала достаточно хорошее качество их сходству. Разумеется, матрица заполняется толь работы. В обработке участвовали электронные до- ко до главной диагонали.

кументы среднего и большого размера. Для выбора Ищется строка матрицы, сумма компонент кото списка значимых ключевых слов из документов рой будет максимальной. Эта строка содержит в крайне малого размера необходимо четко различать себе все коэффициенты подобия i-го документа ко предметную область обрабатываемого в настоящий всем остальным документам. Этот документ объяв момент документа, чтобы случайно не отбросить ляется центром 1-го кластера. Затем в кластер до значимые слова и выражения, вхождения которых бавляются все документы, коэффициенты подобия к будут недостаточно часты. В данной работе эта которым больше либо равны некоторого заранее проблема не рассматривается. заданного порогового значения, являющегося пара Вполне закономерно, что в списки отобранных метром данного метода и позволяющего управлять лемм (исходная форма слова) могут попадать слова, процессом кластеризации.

которые, как правило, не отражают сути анализи- Исключаются все документы, попавшие в кла руемого материала, например, слова «человек», стер, т. е. из матрицы вычеркиваются все строки и «время» и т. п. Для их исключения можно произве- столбцы, соответствующие документам, добавлен сти фильтрацию на основе частотного словаря рус- ным в кластер. Далее пункты 1 и 2 повторяются до ской лексики С.А. Шарова [8], однако при таком тех пор, пока не останется документов, не включен подходе весьма вероятно излишнее отсечение зна- ных в какой-либо кластер.

чимого ключевого слова, которое могло не отражать Очевидно, что таких операций будет не более сути документа одной тематики, но в это же время чем N. При подобном подходе можно пройти весь хорошо соответствовать тематике другого материа- массив документов, сформировав некоторое коли ла. Например, слово «ряд», согласно данному сло- чество кластеров, которое будет варьироваться в варю, является 36-м среди самых встречаемых су- зависимости от информационной потребности (реа ществительных. Если оно будет отсеяно в материа- лизуется изменением порогового значения).

лах общей тематики, то улучшение качества про изойдет незначительное, т. к. среди большего коли- 4 Вычислительные эксперименты чества слов, отражающих смысл, оно имеет сравни Были проведены две серии экспериментов: кла тельно небольшой вес и тем самым влияет на про стеризация достаточно большого множества доку цесс кластеризации несущественно. Но, в то же ментов правовой направленности (около 1300 доку время, возможно существенное ухудшение качества ментов) и набор научных документов математиче кластеризации математических документов, где ской направленности, содержащих классификаци данное слово является значимым. Из-за необходи онные признаки классификатора MSC2000 (около мости выработки универсального подхода для кла 300 документов).

стеризации документов заранее неизвестной тема Целью первой серии экспериментов была про тики приходится идти на данные уступки, которые верка работы механизма кластеризации в целом (от если и могут в некоторых случаях могут снизить этапа автоматического выделения ключевых тер качество кластеризации, то весьма незначительно.

мов, до итогового получения разбиения на кластеры множества документов) на примере достаточно 3 Алгоритм кластеризации текстов большого массива документов. Во второй серии Кластеризация наборов электронных документов экспериментов априорное знание классификацион выполнялась с использованием так называемого ных признаков позволило произвести вычисление «жадного алгоритма» [4], который признан мето- мер качества и сравнить работу методики при рабо дом, дающим достаточно хорошие результаты при те алгоритма с использованием однословных и двухсловных ключевых выражений, варьируя при термов, были случайным образом выбраны 3 кла этом параметрический коэффициент жадного алго- стера и выписаны названия случайно выбранных ритма кластеризации. документов, включенных в них. В данном экспери Так как вычисление ошибки кластеризации в менте на меру сходства между двумя документами классическом виде в первом эксперименте не вы- оказывали влияние как однословные, так и состав полнялось (поскольку не производилось экспертно- ные ключевые термы.

го разбиения выборки документов), то для демонст- Как видно из приведенных названий статей, до рации корректности работы методики, основанной кументы каждого из кластеров относятся к опреде на анализе ключевых однословных и составных ленной, явно выраженной тематике.

Таблица 1. Выделенные термы из романа Л.Н. Толстого «Война и мир»

Однословные термы Двухсловные термы князь - 2011 княжна марья - 93 (княжною Марьей) человек - 1755 старый князь - 92 (старого князя) княжна - 885 полковой командир - 76 (полкового командира) граф - 734 старый граф - 53 (старого графа) время - 714 русский армия - 50 (русская армия) москва - 644 русский войска - 41 (русскими войсками) француз - 595 молодой человек - 32 (молодого человека) государь - 591 исторический лицо - 30 (исторические лица) солдат - 581 выражение лицо - 30 (выражением лица) наполеон - 575 французский армия - 28 (французской армией) жизнь - 572 главный квартира - 27 (главная квартира) слово - 566 французский войска - 26 (французские войска) рост - 544 старый графиня - 23 (старой графини) офицер - 543 князь андрей - 23 (князем Андреем) кутузов - 533 военный министр - 23 (военного министра) армия - 463 французский офицер - 21 (французских офицеров) лошадь - 450 великий князь - 20 (великого князя) графиня - 441 расположение дух - 19 (расположении духа) войска - 435 лицо наташа - 19 (лицо Наташи) Таблица 2. Выделенные термы из статьи З.О. Османова «К вопросу о различении эпистемологических категорий»

Однословные термы Двухсловные термы знание - 131 эпистемологический категория – 5 (эпистемологических категорий) суждение - 85 познавательный процесс - 5 (познавательный процесс) истина - 71 обладающее свойством - 5 (обладающее свойством) вера - 50 достоверный знание - 5 (достоверное знание) мнение - 38 эпистемологический статус – 4 (эпистемологический статус) сведение - 37 тематический словарь - 4(тематический словарь) заблуждение - 37 следующим образом - 4(следующим образом) истинность - 36 некий суждение - 4(некоему суждению) отношение - 32 мнение вера - 4(мнения веры) объект - 29 эмоциональный оценивание - 3(эмоциональное оценивание) субъект - 28 познавательный деятельность - 3(познавательной деятельности) состояние - 26 ложный вера - 3(ложная вера) слово - 26 логический круг - 3(логических кругов) истинный суждение - 3(истинных суждений) истинный вера - 3(истинная вера) изучаемых объектов - 3(изучаемых объектов) аффективный точка - 3(аффективной точки) Кластер 1, общая тематика – налогообложение 2. Функции государства – налогообложение и и уклонение от уплаты налогов взимание налогов.

1. Бухгалтер в России. 3. Налоговые преступления.

4. Уклонение от уплаты налогов с организаций.

5. Уклонение физического лица от уплаты нало- является объективным критерием совпадения тема га или страхового взноса. тики данных документов.

Кластер 2, общая тематика – управление и го- Работа по оцениванию мер качества кластериза сударственная служба ции была разбита на следующие этапы:

1. Понятие, принципы и порядок прохождения 1. Кластеризация подготовленных текстов статей государственной службы. на основе жадного алгоритма с различными значе 2. Управление: основные понятия, система ниями входного параметра (порогового значения).

управления, ее признаки [... ]. 2. Получение результатов кластеризации с ис 3. Основные принципы создания, [... ] организа- пользованием однословных ключевых терминов и ции арбитражных управляющих. результатов, основанных на смешанном критерии, 4. Особенности государственной службы субъ- т.е. с использованием как простых, так и составных екта Российской Федерации. ключевых выражений.

5. Органы внутренних дел Российской Федера- 3. Вычисление внешних мер для полученных ре ции, правовые основы [... ]. зультатов. Нахождение оптимального метода кла Кластер 3, общая тематика – имущественные стеризации (и задание оптимального параметра по права рогового значения для жадного алгоритма), который 1. Институциональные аспекты землепользова- даст результат, наиболее близкий к результату раз ния. биения на основе кодов классификатора MSC2000.

2. О возможности защиты права собственности Выделяют следующие два вида мер качества на недвижимость путем виндикации. кластеризации документов: внешние и внутренние 3. Природа виндикационного притязания и эле- меры (см., например, [6, 7]).

менты виндикационного иска. Внешние меры основаны на сравнении автома 4. Правовое положение лица, владеющего иму- тического разбиения с полученным от экспертов ществом [... ]. эталонным разбиением этих же данных. Идея, по 5. Критика понятия «объект правоотношения». ложенная в основу этих мер, заключается в том, Итоговые кластеры не являются чем-то отдель- чтобы для каждой пары документов автоматически но-стоящим: через некоторые ключевые выражения сопоставить два решения о сходстве этих тематик.

они могут быть связаны с другими группами, а так- Примерами внешних мер являются традицион же с другими документами, как в своей, так и в чу- ные для оценки систем поиска такие характеристи жой группе. Диаграмма на рис. 1 показывает взаи- ки, как полнота (Recall), точность (Precision), ошиб мосвязь через некоторое ключевое выражение кла- ка классификации (Error), F1-мера и другие. Эти стеров, которые, несмотря на свою «непохожесть», характеристики подсчитываются по известным имеют что-то общее. формулам [9] a+d Рис. 2 показывает, что удельный объем класте- a, Precision =, Recall = ров, содержащих достаточно большое количество a+b a+b+c+d элементов, довольно велик, т. е. разделение доку b+c 2 Precision Recall ментов по тематикам выполнялось на хорошем,F= Error =, a + b + c + d 1 Precision + Recall уровне, с учетом того, что все документы принад где коэффициенты a, b, c, d определяются в соот лежали одной обширной области знаний.

ветствии с табл. 3.

Документов, не включенных ни в какой кластер (иными словами, количество кластеров, состоящих Таблица 3. Коэффициенты для подсчета внешних из 1-го документа), оказалось 202, т. е. около 15% от мер сходства общего количества документов, которые участвова ли в данном эксперименте. Для каждой пары dj и di принад- dj и di принад Исходные данные второй серии экспериментов документов dj и di лежат одному лежат разным позволили произвести вычисление мер, с помощью кластеру в кластерам в которых можно оценить качество работы методики. «эталонном» «эталонном»



Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 26 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.