Сравнение дендрограмм с равным числом вершин

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

ОПРЕДЕЛЕНИЕ РАССТОЯНИЯ МЕЖДУ ДЕНДРОГРАММАМИ

Пусть A, B – две дендрограммы, содержащие n объектов. Обозначим A^k , B^k – k-е слои данных дендрограмм. Первоначально каждая дендрограмма содержит n объектов, каждый из которых выделен в свой кластер. На каждом слое происходит объединение двух кластеров в один, в результате на k-м слое дендрограмма содержит n – k кластеров. В таком случае функцию схожести ρ ( A , B ) двух дендрограмм можно задать как функцию от функции схожести ρ ( A^k , B^k ) одинаковых слоев дендрограмм. В качестве такой функции могут выступать ^p m ( A, B ) = ^max_1 ^{р (} A , B ) или P a ( A , B) = -^ £ P ( A k , B k ) . В работе [4] и в данном исследовании используется p a ( А , В ).

Функцию схожести одинаковых слоев дендрограмм можно задать как функцию от функций схожести р (A k , B j ) для каждого из n - k кластера этого слоя.

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

ев безотносительно к способу нумерации узлов, например в задачах сравнения деревьев семантического описания, для корректности значения данной функции необходимо произвести нормировку значения, учитывать инвариантность к способу нумерации объектов и кластеров. Этим свойствам будет удовлетворять следующая метрика: р ( A k , B k ) = 'min £ р ( A j , B p, n - k ^e^ *=7         ¹

где A j , B ^ j - соответственно i и 6 кластеры k-го слоя дендрограмм A и B, Θ – множество всевозможных n – k элементных размещений номеров групп от 1 до n – k.

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

1 n _ k           2 * N

p(Ak, Bk) = — £ pi, pi =-----— для расстояния n=1      N^X + n,2

Хемминга, p =-----1—— для расстояния n,,1 + n,,2 _ N

Роджерса – Танимото, где n_{i 1} и n_{i 2}– число объектов в группе, содержащей ^, объе^, кт i, соответственно в первом и втором дереве, N_i – число совпадающих элементов в группах, содержащих объект i. В данной статье рассматривается второй подход.

ОПРЕДЕЛЕНИЕ ЗНАЧИМОСТИ РАЗЛИЧИЙ МЕЖДУ ДЕНДРОГРАММАМИ

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

Определим случайный эксперимент, порождающий пару дендрограмм. Расстояние между случайно появившимися дендрограммами будет случайной величиной. На этой основе можно получить вероятностное распределение значений расстояния и провести градуировку интервала возможных значений с помощью квантилей функции распределения расстояния. Пусть λ_a – квантиль уровня a для функции распределения F_{p ( t )}. Тогда, если расстояние p оказывается не меньше, чем λ_a , можно сделать вывод, что не менее чем a * 100 % случайно выбранных пар разбиений имеют между собой расстояние меньше, чем p . Аналогичный подход рассмотрен авторами в работе [1] при сравнении расстояний между подмножествами.

ВЕРОЯТНОСТНАЯ МОДЕЛЬ ПОЯВЛЕНИЯ ЗНАЧЕНИЯ РАССТОЯНИЯ

Представим кластера Aki и Bkj в виде бинарных векторов a и b размерности n, построенных по принципу: ai = 1 тогда и только тогда, когда объект u_ входит в кластер А: u_ G A, в противном случае ai = 0 (аналогично для b и B). Обозначим через pi, i = 1, …, n вероятность появления элемента ui в кластере. Рассмотрим случайный эксперимент, состоящий из n независимых испытаний, в каждом из которых элемент может как появиться, так и не появиться в кластерах. Тогда в каждом испытании возможны исходы четырех видов Auv = {Xj = u, y f = v}, где u, v G {0,1}, i - но- мер испытания. Пусть I(A) – индикатор события n

A , I ( A^ ) + 1 ( A ^) + 1 ( A 0 1 ) + 1 ( A 0 0 ) = 1 , a = 1 I ⁽ A^ ) ,

Учитывая, что p i = —Ц-, формула (1) примет n - к

вид:   f,(t)= 1, 1 iic^VIw

(a,b,с,d)еC(A1\,„,A„no ) BM n k n - к -1 n - к

1      (         ₁             ' ⁽ A 01 )" ' ^{( A} 1 i 0 )

1 [ n - к -1 ] I n - к I n - к ))

у у П ¹    ( n - к - 1)2 d ( n - к - 1)

UbTdVcU 1 a- A h( n - к ) ² a ( n - к ) ^{2 d} ( n - к ) ^{2 b + 2} c

( ^{a , b , c ,} d ) ^{I C} ( A n,.., A 00 I B ¹=1 ^{v         7 v 7 v 7}

b + c

- ( n - к - 1) ^{n + d - a}

, ¹. ¹ 11      ^{2 n}

^{( a , b , c , d} ) e C ( A 1\, „ , A n I B ^- =l ^{( n к} )

.

РАССТОЯНИЕ ХЕММИНГА

Для конкретных расстояний формула (2) может упрощаться. В [6] в качестве простейшего коэффициента различия между множествами, обладающего свойствами метрики, предлагается мощность симметрической разности: |X A Y | =| ( X \ Y ) u ( Y \ X ) . Если разделить это число на n , то получим расстояние Хэмминга [3] между бинарными векторами, принимающее значения от 0 до 1:

p H ( X , Y ) =  ----- = — , где m = b + c .

nn

Вероятность исходов Aⁱ ₁₀ и Aⁱ ₀₁ равняется 1          1 n к 1m

-----* (1--) =------- 2-. Тогда n - к n - к ( n - к )

X \           2 ^{b + c} ( n - к - 1) ^{b +} c

F , ( t ) = P ⁽ p ^H ( X , Y ) < t ) = 1 C —    '    2 b +, ’   x

—        ^{( n к} )

m : < t n

((n - к)2 - 2(n - к -1))a+d (n - к)2a+2d b = 11 (Aio),

c = 1 1 ⁽ A 01 ) , d = 1 1 ⁽ A Oo ) . Тогда a +

i = 1                            i = 1                           i = 1

+ b + c + d = n .

Согласно мультиномиальному (полиномиальному) распределению [5], функция распреде-

1 —

Cn m m:—< t

n

2 ^{b + c} ( n - к - 1) ^{b + c} *2 ^{b + c} ( n - к - 1) ^{b + c}

( n - к )^{2 b + 2 c}

( n - к )^{2 b + 2 c}    '

ления расстояния примет вид:

F , ⁽ t ) = P p ⁽ X , Y ) < t ) = ₍₁₎ = 1 1 ri p ' ( A "¹» - p ■ *⁰⁰ ’ ( p. ( 1 - p.» *A "^Mo ' ^{( a ,} b ^, c ^, d ) e C ( A h , _ , A 0По | B i = 1 ’

1C— m m:—< t

n

2 ^m ( n - к - 1) ^m ( n - к )² a ^{+ 2 d} - 2 ⁿ ( n - к - 1) ⁿ ( n - к )^{2 n}

C m ² m ( n - к - 1) m b m- ⁿ    ( n - к )^{2 m}

m : < t

n

C m ² n ( И - к - 1) n ^ m?      ( n - к )^{2 n}

m :—< t         ^{x 7}

n

.

где C = { ( a,b,c,d ) G Z ⁴: a,b,c,d >  0 , a + b + c + d = = n,h (a,b,c,d )}.

Объединение любых двух кластеров на каждом шаге является равновозможным. Будем считать равновозможной нумерацию кластеров на каждом слое. Вычислим вероятность появления произвольного объекта в любом кластере. Вероятность P k, попадания i-го объекта в j-й кластер на k-м слое не зависит от i и j и равняется ——.

n - к

РАССТОЯНИЕ РОДЖЕРСА – ТАНИМОТО

Одним из часто используемых коэффициентов различия между бинарными векторами является расстояние Роджерса – Танимото, получаемое из одноименной меры близости [5] и равное

,R (X, Y ) = 1--a + d 4 = 2(b + c) = 2—, a + d + 2(b + c) n + b + c n + m где m – количество исходов A01 ∪ A10 в n испытаниях, то есть m = b + c.

Число исходов m рассчитывается аналогично предыдущему пункту, следовательно,

2^ ( 2 — k — 1) m

F R ( t ) = P (p ^{RT (} X , Y ) < t ) = - C m   ¹     2 m

2 m        ( 2 — k )

m:-----< t n+m

_   2 ² ( n — k — 1) ²

m

• ^{— 2}   ( n — k )^{2 2}

• m :-----< t

n + m

—

m

^C n .

2 m m:-----< t n+m

ЧИСЛЕННОЕ ВЫЧИСЛЕНИЕ КВАНТИЛЕЙ РАСПРЕДЕЛЕНИЯ

Для подсчета квантилей функций распределения расстояний была разработана специальная компьютерная программа. Результаты работы этой программы представлены в табл. 1, содержащей в себе квантили уровня a для двух рассмотренных в статье расстояний, рассчитанные для различных n . Для каждого a в табл. 1 представлены 2 квантиля, расположенные следующим образом: вверху – квантиль для расстояния Хэмминга, внизу – для расстояния Роджерса – Танимото.

Таблица 1

Квантили функции распределения для различных n (с точностью 0,001)

k\p	0,6	0,7	0,8	0,9	0,95	0,99
3	0,334	0,334	0,334	0,667	0,667	0,667
	0,501	0,501	0,501	0,801	0,801	0,801
4	0,334	0,334	0,334	0,667	0,667	0,667
	0,501	0,501	0,501	0,801	0,801	0,801
5	0,401	0,401	0,401	0,601	0,601	0,801
	0,572	0,572	0,572	0,751	0,751	0,889
15	0,334	0,334	0,401	0,467	0,534	0,601
	0,501	0,501	0,572	0,637	0,696	0,751
30	0,334	0,367	0,401	0,434	0,467	0,534
	0,501	0,537	0,572	0,605	0,637	0,696
45	0,356	0,356	0,378	0,423	0,445	0,489
	0,525	0,525	0,549	0,594	0,616	0,657
60	0,351	0,367	0,384	0,417	0,434	0,484
	0,519	0,537	0,555	0,589	0,605	0,652

АНАЛИЗ ДЕНДРОГРАММ ПРИ КЛАССИФИКАЦИИ ТЕКСТОВ С РАЗНЫМ НАБОРОМ ПРИЗНАКОВ

Задача сравнения дендрограмм была поставлена в [4], где анализировались результаты кластеризации объектов с разным количеством при- знаков. При проведении исследований по атрибуции текстов использовалось: распределение 16 частей речи на первых трех и последних трех позициях каждого предложения. Таким образом, каждому тексту соответствовал набор 96 (16 х 6) признаков; расширенный набор признаков за счет учета дополнительных морфологических характеристик, свойственных каждой части речи (например, падеж для существительных, форму и степень сравнения для прилагательных, вид, залог и лицо для глаголов и т. д.). В итоге стали использоваться 156 признаков, соответственно, текст стал характеризоваться набором в 936 (156 х 6) признаков.

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

Таблица 2

Коэффициенты близости между иерархическими деревьями, построенными на основе различного числа признаков: 16 (1) и 156 (2)

По всему тексту	(1)	0,877995
	(2)	0,839487
По первому и последнему предложению абзаца	(1)	0,936056
	(2)	0,914381
По первому предложению абзаца	(1)	0,910971
	(2)	0,880166
По последнему предложению абзаца	(1)	0,941005
	(2)	0,921237

Из табл. 2 видно, что коэффициенты близости текстов принимают значения немногим меньше 1. Сравнивая их с экспериментальными результатами (табл. 1), можно сделать вывод, что значения мер близости встречаются менее чем в 1 % случаев (уровень надежности – 0,99). Это означает, что увеличение числа грамматических признаков не позволяет эффективно решать задачу атрибуции анонимных и псевдонимных литературных произведений. Проведенное исследование показало статистически незначимое отличие классификации текстов по двум наборам признаков.