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

3. Метод атрибуции текстов

Теоретические основы

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

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

Для преобразования реального лингвистического объекта в математический объект необходимо определить такой набор измерений {M1,M2,...,Mn}, что применение это-

го набора к объекту r порождает набор констант {x1,x2,...,xn}, представляющих значения признаков изуча-

емого объекта. Полученный набор величин {x1,x2,...,xn} –

описывает математический объект x , являющийся отображением реального объекта r.

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

Пример решения задачи атрибуции

22

Пусть имеются три лингвистических объекта, характеризующиеся пятью параметрами: 01 – число слов в цельном предложении (ЦП); 02 – число графем1 в ЦП;

17 – число знаменательных слов в ЦП; 32 – число под-

лежащих в ЦП; 42 - число согласованных определений в ЦП. Таким образом, каждый объект может быть представлен в виде пятимерного вектора:

M1 {16,8;111,833; 13,100; 1,400; 2,633} ,

M2 {17,0;108,684; 12,974; 1,737; 2,684} ,

M3 {15,387;89,694;10,903;1,387;2,306}.

Полученная информация представляется в виде таблицы:

Таблица 1

Объект	M1	M2	M3
01	16,800	17,0	15,387
02	111,833	108,684	89,694
17	13.100	12,974	10.903
32	1,400	1.737	1,387
42	2,633	2,684	2,306

Далее проводится операция центрирования: определяются групповые средние значения для каждого параметра и выражается имеющаяся информация в отклонениях от этих средних значений:

Таблица 2

	Объект	M1	M2		M3
	01	0,404333	0,604333		-1,00867

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

23

02	8,429333	5,280333	-13,7097
17	0,774333	0,648333	-1,42267
32	-0,108	0,229	-0,121
42	0,092	0,143	-0,235

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

Таблица 3

Объект	M1	M2	M3
01	0,563222	0,841815	-1,40504
02	0,861977	0,539963	-1,40194
17	0,768728	0,64364	-1,41237
32	-0,66661	1,413455	-0,74685
42	0,549354	0,853887	-1,40324

Таким образом, значение ячейки (zik ) таблицы 3 вы-

числяется по формуле: zik xik xk , где: sk

xik - значение k -го признака i-го объекта,

xk - среднее арифметического значений для k -го при-

знака,

	n					2
		(xik	xk )
sk							- среднеквадратическое отклоне-
			n
	i 1
ние.

Следующий шаг - выбор решающего правила. Решающее правило - алгоритм, обеспечивающий разделение в некотором смысле наилучшим образом пространства при-

24

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

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

25

этого используется алгоритм классификации объектов в одномерном пространстве с помощью t-критерия [3]:

t				x1			x		2					,
		2									2
			1								2
				n1					n2

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

x		, tA,xi	t , j 1 n ,
i	A	набл, j
x		, tB,xi	t , j 1 n .
i	B	набл, j

В качестве решающего правила можно выбрать евклидово расстояние между каждым объектом класса и центром класса:

	n
d(A,B)	(xaj xbj )2 .
	i 1

Если Ci - центр (эталон) класса i , а D(X,Ci)– расстояние (близость, похожесть) между объектами X и Ci ,

то принимается решение:

X 1, если D(X,C1) D(X,C2)

X 2 , если D(X,C1) D(X,C2)

Принятие решения по наименьшему евклидову расстоянию основано на неявном предположении, что каждый класс характеризуется вероятностным распределением, плотность которого убывает с ростом расстояния D(X,Ci) от центра Ci . Построение такой модели позволя-

ет классифицировать любой объект, отнеся его к тому

26

классу, для которого расстояние D(X,Ci)имеет мини-

мальное значение.

Возможен также вероятностный вариант классификации, т. е. приписывание вероятности, или степени достоверности, каждому решению. Вероятность принадлежности объекта к j-му классу вычисляется следующим образом:

p	1				1			,
ij	dij			1
					k
						djk
где dij		-		расстояние между объектом и i-м классом,

а djk - расстояние между объектом и остальными класса-

ми классификации.

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

xi A,еслиP(Xi A) 0.5), xi B,еслиP(Xi B) 0.5),

P(Xi A) P(Xi B) 0.5-отказотраспознавания.

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

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

27

Литература

1.Марусенко М.А. Атрибуция анонимных и псевдонимных литературных произведений методами распознавания образов. Л.: Издательство Ленинградского университета, 1990, 168с.

2.Математическая и информационная поддержка методов обработки литературных текстов на основе фор- мально-грамматических параметров./ Ю.В. Сидоров. Автореферат на соискание ученой степени кандидата технических наук., Петрозаводск, 2002. – 19 с.

3.Хетсо Г. Принадлежность Достоевскому: к вопросу об атрибуции Ф.М. Достоевскому анонимных статей в журналах “Время” и “Эпоха”. SOLUM FORLAG A.S.: OSLO 1986.

4.Виноградов В.В. Проблемы авторства и теория сти-

лей. М., 1961. - 263 с.

5.Мартыненко Г. Я. Основы стилеметрии. Л.: Изд-во ЛГУ, 1988. - 176 с.

6.От Нестора до Фонвизина: новые методы определе-

ния авторства // Милов Л.В., Бородкин Л.И., Иванова Т.В. и др.; Под ред. Л.В.Милова. -М.: Прогресс,1994. – 445 с.

7.Фоменко В.П., Фоменко Т.Г. Авторский инвариант русских литературных текстов. Предисловие А.Т.

Фоменко. // Фоменко А.Т. Новая хронология Греции: Античность в средневековье. Т. 2. М.: Изд-во МГУ, 1996. С.768-820.

28

4. Линейный дискриминант Фишера

Теоретические основы

Большую популярность среди исследователей приобрел метод, предложенный Фишером еще в 1936 году [1, 2]. В основе метода лежит попытка разделить объекты двух классов, построив в многомерном признаковом пространстве такую прямую, чтобы проекции на нее описаний объектов этих двух классов были максимально разделены. Далее изложим метод согласно [2]. Пусть вектор w задает направление некоторой прямой. Проекцией произвольного вектора x на направление, задаваемое w, является отношение wtx/|w|, где |w|- абсолютная величина вектора w, которая реально является несущественным масштабным коэффициентом. В качестве меры различий проекций двух классов K1 и K2 на направление w предлагается использовать функционал

J(w) [y1(w) y2 (w)]2 d1(w) d2 (w) ,

где yi(w)- среднее значение проекций векторов опи-

саний объектов обучающей выборки из класса Ki , т.е.

y	i	(w)		1		wtx(sj ), а di (w) - выборочная
			(m m
					)| w| s		K	i
			i	i 1		j

дисперсия проекций векторов описаний объектов обучающей выборки из класса Ki ,

		1		[			wtx(sj )			2	, i {1,2}.
di	(w)							yi]
		(m m					|w|
			) s		K
		i i 1		j		i

29

Смысл функционала J(w) с точки зрения разделения двух классов ясен из его структуры. Он возрастает при

увеличении отношения квадрата различия

между средни-

ми значениями проекций двух классов к сумме

внутри-

классовых выборочных дисперсий.

Показано [3], что функционал J(w)

достигает сво-

его максимума при

w D 1

(μˆ

μˆ

2

),

где D -матрица раз-

w

1

w

броса

внутри

классов,

μˆi

1

x(sj )-

(m m

) s

K

i

i

i 1

j

выборочный центр класса Ki ,

i {1,2}. Матрица разброса

внутри классов определяется как сумма матриц разброса по каждому из классов или Dw D1 D2 , где

Di			1		[x(sj ) μˆi][x(sj ) μˆi ]t .
		(m m
				) s		K	i
		i	i 1		j

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

Линейный дискриминант Фишера может быть распространен на случаи большего, чем 2 числа классов.

В книге [1] можно найти листинг программы на С- подобном языке программирования, реализующий данный метод.

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

Реализовать задания 3 – 7 параграфа 1 при помощи метода линейного дискриминанта Фишера, сравнить полу-

30

ченные результаты с результатами, полученными при помощи других методов.

Литература

1. Игорь Гайдышев, "Анализ и Обработка Данных: специальный справочник", СПб: Питер, 2001. - 752 с.

2. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.:

Фазис, 2006.

3.Р.Дуда, П.Харт. Распознавание образов и анализ сцен. -

М.: Мир, 1976. – 511 с.

4.Лепский А.Е., Броневич А.Г. Математические методы распознавания образов: Курс лекций. – Таганрог: Изд-

во ТТИ ЮФУ, 2009. – 155 с.

5.Воронцов К.В. Курс лекций «Математические методы обучения по прецедентам» // http://www.machinelearning.ru/wiki/images/6/6d/Voron- ML-1.pdf

31