Методичка. Распознование образов

ББК 74.200.585.0 Н 346

Авторы-составители:

Ю. В. Сидоров, Н. В. Смирнов

Вероятностные методы анализа неструкту- H 346 рированной текстовой информации / авт-сост.

Ю. В. Сидоров, Н. В. Смирнов. − Петрозаводск : Изд-во ПетрГУ, 2012. − 212 с.

ISBN 978-5-8021-1052-2

В пособии рассматриваются основные методы первичного анализа текстовой информации. Приведены примеры решения различными методами задач: классификации новостей в сети Интернет, определение спама, атрибуции литературных текстов и др. Содержит задачи для самостоятельного выполнения. Пособие предназначается студентам, изучающих курсы «Математические методы распознавания образов», «Интеллектуальные информационные системы».

БКК 74.200.585.0

Сидоров Ю.В., Смирнов Н. В., составление, 2012 ISBN 978-5-8021-1052-2 Петрозаводский государственный университет, 2012

	Содержание
Введение...............................................................................		5
1.	Вероятностная языковая модель...................................	7
	Построение вероятностной языковой модели..............	7
	Пример: задача определения автора.............................	9
	Задания для индивидуальной работы..........................	11
	Литература....................................................................	14
2.	Байесовская модель......................................................	16
	Теоретические основы.................................................	16
	Пример: задача определения спама.............................	17
	Классификатор байесовского типа..............................	18
	Задания для индивидуальной работы..........................	20
	Литература....................................................................	20
3.	Метод атрибуции текстов............................................	22
	Теоретические основы.................................................	22
	Пример решения задачи атрибуции ............................	22
	Задания для индивидуальной работы..........................	27
	Литература....................................................................	28
4.	Линейный дискриминант Фишера ..............................	29
	Теоретические основы.................................................	29
	Задания для индивидуальной работы..........................	30
	Литература....................................................................	31
5.	Метод k-ближайших соседей.......................................	32
	Теоретические основы.................................................	32
	Пример решения задачи атрибуции ............................	33
	Задания для индивидуальной работы..........................	34
	Литература....................................................................	34
6.	Метод Парзеновского окна..........................................	36
	Теоретические основы.................................................	36
	Задания для индивидуальной работы..........................	38
	Литература....................................................................	38
7.	Метод опорных векторов.............................................	39
	Описание метода..........................................................	39

3

	Программная реализация метода опорных
	векторов – SVM Light...........................................	43
	Задания для индивидуальной работы .........................	45
	Литература...................................................................	45
8.	Метод потенциальных функций .................................	48
	Теоретические основы.................................................	48
	Пример решения задачи..............................................	51
	Задания для индивидуальной работы .........................	52
	Литература...................................................................	52
9.	Метод k-средних..........................................................	54
	Теоретические основы.................................................	54
	Задания для индивидуальной работы .........................	55
	Литература...................................................................	55
Приложение 1: Возможные признаки текстовой
	информации.................................................................	57
Дополнительный список литературы и
	источников...................................................................	58

4

Введение

Зачастую у студентов, изучающих курс «Математические методы распознавания образов», возникают некоторые трудности при практической работе с методами распознавания образов, прослушанных ими на лекционных занятиях в теории: это и разный уровень подготовки студентов, среди которых могут быть пришедшие в магистратуру специальности, для которой читается данный курс, из бакалавриата другой специальности и обладающие более слабой математической подготовкой; сложности с придумыванием задач и определением набора признаков для выбранных ими объектов; сложности с адаптацией усвоенного в теории метода для его программной реализации и т.д.

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

5

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

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

Кроме магистрантов специальностей «Прикладная математика» и «Информационные системы», изучающих дисциплину «Математические методы распознавания образов», данное пособие может оказаться полезным и студентам, обучающимся по курсу «Интеллектуальные информационные системы», которые для практических занятий по данному курсу избрали работу с текстовой информацией.

6

1. Вероятностная языковая модель

Построение вероятностной языковой модели

Основа вероятностных языковых моделей была заложена в работе известного отечественного математика А.А. Маркова [4], где исследовалось распределение доли гласных и согласных букв среди первых 20000 букв текста "Евгения Онегина". С тех пор данное исследование является базисом для построения новых подходов к изучению языка при помощи статистических исследований. К примерам таких моделей относятся одно-, двух- и трехсловные языковые модели (модели одно-, двух- и трехсловных сочетаний).

Следуя [1], построим такие языковые модели. В однословной модели (модели однословных сочетаний) каждому слову в словаре присваивается вероятность P(w). В этой модели предполагается, что слова выбираются независимо, поэтому вероятность строки представляет собой произведение вероятностей входящих в нее слов и определяется выражением:

P(wi)	(1),
i

где wi - слово из этой строки.

Вдвухсловной модели каждому слову присваивается вероятность P(wi |wi 1 )с учетом предыдущего слова.

Вмодели n -словных сочетаний учитываются преды-

дущие		n 1		слов и присваивается вероятность
P(wi	|w	,w	,....,w	).
	i 1	i 2	i (n 1)

Рассмотрим книгу, весь словарь которой включает примерно 15 тысяч различных слов. Модель двухсловных сочетаний включает 150002 = 225 миллионов пар слов.

7

Безусловно, что вероятность появления по меньшей мере 99,8% этих пар будет равна нулю, но сама модель не должна указывать на то, что появление любой из этих пар

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

втекстовой совокупности равно N , а количество возможных n-словных сочетаний равно B , то каждому n- словному сочетанию с частотой встречаемости C присва-

ивается	сдвинутая на единицу оценка			вероятности
	C		1.
P (w)	N B
Таким образом, формулу (1) можно представить в сле-
дующем виде:
(P(wi) 1) = P'(wi)				(2)
i			i

Другой подход заключается в логарифмировании относительной частоты встречаемости n-словного сочетания

		C		. Понятно, что тогда произведение в
P (w) ln
		N B

формуле (1) заменяется на сумму.

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

8

Perplexity(words) 2

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

log2 (P(words))

N ,

Где N – количество слов words. Чем ниже показатель связности, тем лучше модель [1].

Пример: задача определения автора

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

В текстах каждого автора посчитаем вероятностную частоту встречаемости слов. Для этого возьмём оригинальные тексты этих авторов1, сгруппируем и упорядочим слова, суммируя частоту их повторения.

Пусть X k (xk ,xk ,..., xk ) – сгруппированная ранжи-
1 2	nk
рованная выборка для	k -ого автора, где xk	–i-ое слово,
	i

nk – количество различных слов, встречающихся у этого автора.

Тогда Y k (yk , yk ,..., yk ) – вектор частот встречаемо-
1 2	nk

сти каждого из слов у k -ого автора, yik – частота повторе-

ния i-го слова.

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

9

Пусть			Zk (zk	,zk ,..., zk )–		вектор вероятностных ча-
			1	2	nk
стот каждого из элементов выборки, zik							–	вероятностная
частота i-го слова.				Величина		zik считается по формуле:
	yk
zk	i	, где n – общее количество слов у k -ого автора.
i	n		k
	k
Тогда			X k (xk	,xk ,..., xk ) и		Zk (zk ,zk		,..., zk ) образу-
			1	2	nk	1	2	nk
ют класс определенного автора. Пусть							C (c1,c2,...,ck ) –
множество классов				k	различных авторов.			cj – конкрет-
ный	j -ый класс. Подобным образом описываются классы

для каждого автора.

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

Пусть S (s1,s2,...,sm)– набор слов во входном тексте,

где m – количество различных		слов,		sj	–	j -ое слово
входного текста.
Пусть Pk (pk , pk ,..., pk ) –		вероятностная						частота
1 2	m						m – ко-
элементов входного текста для k -го класса, где
личество слов во входном тексте.		pkj	–	вероятностная ча-
		k		k	sj	xi
стота j -го слова для k -го класса				zi ,				.
		pj			иначе
				0 ,

Если все слова входного текста присутствуют во всех классах, то для каждого класса, используя (1), определим

m

U k pkj . Если некоторых входных слов нет хотя бы в

j 1

10

одном из классов, то для каждого класса воспользуемся

m

формулой (2): U k (pkj 1).

j 1

Наибольшее Uk указывает на класс, автору которого принадлежит входной текст.

Задания для индивидуальной работы

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

2.Решите задачу сегментации (поиска границ между словами в тексте без пробелов) для нескольких произвольных предложений из моноязыковой совокупности, используемой в упражнении 1, с использованием модели однословных сочетаний и уравнения Витерби [2, 3]. Проанализируйте полученные результаты сегментации.

3.Предлагается разработать классификатор для выявления авторства текстов: при наличии некоторого текста неизвестного автора этот классификатор должен попы-

11