Метрики оценки тематической сегментации текстов
Н.А. Авдееваa, К. К. Боярскийb
aЭкономико-математический институт РАН, СПб
bСПб НИУ ИТМО, Санкт-Петербург
Assoul@yadnex.ru, boyarin9@yandex.ru
Рассматриваются методы проверки качества тематической сегментации текстов на примере «низкоконтрастных» текстов из монографий на русском языке. В качестве базового алгоритма сегментации был выбран TextTiling., анализирующий связность между соседними частями текста. Рассмотрено несколько способов вычисления меры сходства частей текста. Исследована взаимозависимость таких параметров, как полнота, точность и уровень шума при сегментации, а также их влияние на оценку качества анализа. На примере русского языка подтверждено, что подключение внешнего семантического классификатора существенно повышает качество сегментации. 
Ключевые слова: TextTiling, сегментация, коэффициент корреляции Мэтьюса, F-мера
The quality evaluation methods of topic segmentation of scientific texts are discussed. The research is based on the TextTiling algorithm that analyses how tightly adjoining parts of a text cohere.We analyzed some ways to find cohesion between the parts of the text. We examined how recall, precision and the noise rate change and how they influence the quality evaluation methods. The studies on Russian suggest that external semantic classifier notably improves the segmentation quality.
Keywords: TextTiling, topic segmentation, Matthews correlation coefficient, F-score
1 Введение
Сейчас в литературе описано достаточно много алгоритмов тематической сегментации текстов. Как правило, они эффективны на искусственно созданных текстах: на конкатенации отдельных предложений или коротких текстовых фрагментов из газетных или Интернет-публикаций [1], или на больших текстовых корпусах [2]. Результаты применения этих алгоритмов к реальным научным текстам представлены крайне скудно [1].
Для научного текста характерна информационная насыщенность, низкая контрастность лексики (обилие терминов, наличие синонимов) и тематическое единство с плавными переходами от одной подтемы к другой. Это затрудняет автоматическую тематическую сегментацию текстов, которая необходима для организации информационного поиска внутри научного текста при первичном отборе источников, при работе с источниками на иностранных языках, при быстром погружении в проблематику исследования и т. п.
2 Отбор и тематическая сегментация текстов
Тексты извлекались из монографий технической тематики на русском языке (табл. 1). 
Табл. 1 Характеристики текстовых источников
Обозначение источника	Размер фрагмента (печатн. знаков)	
1. Ромм [4]	161152	
2. Подводники [5]	60560	
3. Новости	23800	
В качестве базового алгоритма был взят TextTiling [3], использующий локальную информацию о связности между соседними частями текста. Каждому абзацу был приписан вектор i ={}, нормированный на единичную длину, где — это частота токена в i-ом абзаце. В качестве токена выступала либо лемма существительного (вариант сравнения «по словам»), либо его семантический класс (сравнение «по классам»), выявленный в ходе синтаксического анализа программой SemSin [6]. В последнем случае предполагалось, что слова, принадлежащие одному классу по классификатору [7], совпадают, например, слова судно, фрегат,… в тексте «Ромм» или каска, фуражка, бескозырка в тексте «Подводники». Подробное описание алгоритма приводится в [8]. 
На основании построенных векторов определялась мера сходства соседних абзацев. Мера нормировалась от 0 до 1, причем, чем выше значение меры, тем сильнее сходство абзацев. 
Существует несколько способов определения сходства. Мы сравнивали абзацы по косинусной мере (Cos), связанной с расстоянием Евклида, и по нормированному манхеттеновскому расстоянию (Manh): .
3 Метрики оценки качества сегментации
Между двумя соседними абзацами проводилась граница (H), то есть тема менялась, если мера сходства оказывалась меньше определенного уровня – уровня отсечки z, который мог задаваться в диапазоне от 0 до 1. Затем сопоставлялись последовательности А (граница смены темы, заданные автором) и Н. Как правильное совпадение (TP) рассматривались случаи, когда в обеих последовательностях (A и H) были отмечены локальные минимумы («провалы») для одного и того же абзаца или для соседних абзацев. Такое смещение возможно, поскольку, как показал детальный анализ, часто в первом абзаце новой темы автор пытается плавно сменить тему, и, в сущности, переход происходит только в следующем абзаце. Остальные «провалы» H отмечались как ложные (FP), а «провалы» A – как пропущенные (FN). 
Табл. 2 Матрица сопряженности бинарной классификации
	Авторская разметка	
Автоматическая разметка	TP (true positive)	FP (false positive)	
	FN (false negative)	TN (true negative)	
По этим данным определялись точность  и полнота .
В нашем исследовании для оценки качества сегментации использовалась сбалансированная F-мера [9]: 
,            			   (1)
Метрику F-меры (1) удобно рассматривать как критерий оптимизации, а ее максимум – как наилучшее соотношение P и R. С другой стороны, на значение F-меры не влияет количество верно определенных абзацев, не являющихся границами смены темы (TN), которое уменьшается с увеличением значения уровня отсечки. Следовательно, постепенно данные становятся более «зашумленными», что отражает коэффициент FPR (false-positive rate):.
Из рис. 1 видно, что, начиная с , F-мера слабо изменяется при резком возрастании FPR. 

Рис. 1. Зависимость от уровня отсечки параметров оценки сегментации по косинусной мере для текста «Ромм» 
В отличие от F-меры, коэффициент корреляции Мэтьюса (MCC) [10,11] учитывает все значения матрицы сопряженности:
 (2)
MCC изменяется в интервале (-1; 1), таким образом, что MCC = 1 означает абсолютную корреляцию по всем точкам, при  линейной корреляции нет, а если MCC = –1, то величины абсолютно независимы. MCC < 0, если количество пропущенных значений превышает количество верно определенных границ (FN > TP) или, что то же самое, когда R < FNR. Значение MCC не вычисляется, если уровень отсечки ниже минимального значения функции расстояния (TP = FP = 0) или выше максимального (TN = FN = 0).
Из рис. 1 видно, что график MCC имеет существенно более узкий максимум, спадая при больших уровнях отсечки вследствие увеличения числа ложных срабатываний.
Можно добиться существенно более высокого качества сегментации за счет перехода от сравнения «по словам» к сравнению «по классам» (табл. 2).
Табл. 2 Максимальные значения F-меры и MCC для разных текстов 
	«по словам» (cos)	«по классам» (cos)	
	F-мера	MCC	F-мера	MCC	
Ромм	0.23	0.2	0.75	0.76	
Подводники	0.21	0.19	0.65	0.65	
Новости	0.61	0.5	0.8	0.74	

Во всех рассмотренных текстах уровни отсечки при максимальных значениях F-меры и MCC различаются не более чем на 0.05. Это означает, что для поиска оптимального уровня отсечки, можно использовать как F-меру, так и MCC. Однако для общей оценки когерентности текста MCC оказывается более информативным. 
4. Сравнение мер сходства
В результате сравнения двух метрик определения сходства между абзацами, было выявлено, что при измерении по Manh точность быстрее убывает, а полнота быстрее возрастает по сравнению с измерением по Cos (рис. 2а). Максимум F-меры по Cos смещен вправо относительно максимума по Manh (рис. 2б), однако высота максимума в обоих случаях практически одинакова. Это означает, что обе метрики определения расстояния применимы, однако для них являются оптимальными разные уровни отсечки.

Рис. 2. Параметры оценки сегментации по Cos и Manh: а - точность и полнота; б – F-меры. Текст «Подводники» по классам.

5 Заключение
Проведено детальное сравнение F-меры и коэффициента Мэтьюса (MCC) как оценок качества сегментации научно-технических текстов. Было выявлено, что MCC точнее отражает степень связности текста, но для задачи тематического деления эти две метрики равнозначны. Показано, что выбор метрики семантического расстояния между смежными абзацами некритичен для разбиения текста на сегменты. На примере русского языка подтверждено, что подключение внешних лексических ресурсов существенно повышает качество сегментации.
Литература
1.	G. Dias, E. Alves, J.G.P.Lopes. Topic Segmentation Algorithms for Text Summarization and Passage Retrieval: An Exhaustive Evaluation // AAAI'07 Proceedings of the 22nd national conference on Artificial intelligence. №2. p. 1334–1339.
2.	Jeffrey C. Reynar. 1994. An automatic method of finding topic boundaries // Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p. 331–333, Morristown, NJ, USA. 
3.	Hearst, Marti A. TextTiling: Segmenting text into multi-paragraph subtopic passages // Computational Linguistics, 23(1), p. 33–64, March 1997.
4.	Ромм Ш. Искусство, или главные начала и правила, научающие искусству строения, вооружения, правления и вождения кораблей / пер. А. Шишков. – Санкт-Петербург, 1793.
5.	Уильямсон Г. Подводный флот Германии. 1914–1945 / пер. М.А. Мальцевой. – М.: ООО «Издательство АСТ», 2003. 
6.	Боярский К. К., Каневский Е. А. Семантико-синтаксический парсер SemSin // Научно-технический вестник информационных технологий, механики и оптики, №5, 2015.
7.	Тузов В.А. Компьютерная семантика русского языка. СПб: Изд-во С.‑Петерб. ун-та, 2004.
8.	Artemova A, Avdeeva N., Boyarin K., Gusarova N., Dobrenko N., kanevsky K. Subtopic Segmentation of Scientific Texts: Parameter Optimisation. (в печати)
9.	Е.И. Большакова и др. Автоматическая обработка текстов на естественном языке и компьютерная лингвистика. М.: МИЭМ. 2011. 
10.	Baldi, P. Assessing the accuracy of prediction algorithms for classification: an overview // Bioinformatics review, vol.16, p. 412-424, USA.
11.	Matthews, B. W. Comparison of the predicted and observed secondary structure of T4 phage lysozyne // Biochimica et Biophysica Acta (BBA): Protein Structure. 1975, № 405 (2). P. 442-451. http://www.sciencedirect.com/science/article/pii/0005279575901099  (Date of access 25.08.2015)