Алгоритм “адаптивного выбора подклассов”

На начальном этапе пользователем задаются:

Z

T

-максимальное предполагаемое количество подклассов. - минимально допустимая мощность кластера

(количество векторов обучающей выборки, отнесенных в соответствующий кластер)

Процесс кластер-анализа заключается в попытке аппроксимации функции

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

с помощью смеси нормальных плотностей распределения каждая компонента этой смеси представляется в виде

f

i

x

i

2 n

2

i

12 1

1

x M

i

t

M

i

2

i

exp

1 x

Mi		- вектор математического ожидания i-кластера;
i		- матрица ковариации i-кластера;
n		- размерность вектора классификационных признаков;

Алгоритм “адаптивного выбора подклассов”

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

В соответствии с этим каждая нормальная компонента смеси представляется в виде

fi

mli

l2

i

						n		1
					n 2
x				2					exp
						l
						l 1		i

- компоненты вектора Mi

	n	xl ml		2
1
			i
			l
2	l 1
			i

- диагональные элементы ковариационной матрицы i

цель классификации будет достигнута, если будут получены оценки параметров

Pi , Mi , Di

ni 0

Алгоритм “адаптивного выбора подклассов”

d

1

D

i

,

d

2 ,

i

,

l

- вектор дисперсий

li

1,z

1,n

i

li

dn

i

в системе кластеризации после окончания обучения обеспечивается вычисление полной ковариационной матрицы соответствующих кластеров i

Введем следующие обозначения:

1) Мода с номером " K"

Модой будем называть область векторов в пространстве признаков R близких к M k 1,z

В качестве метрики используется квадрат эвклидова расстояния

2) Моду с номером i будем называть свободной, если ее параметр Pi 0

мода i свободна при

ni - Число векторов, входящих в моду.

Алгоритм “адаптивного выбора подклассов”

3) Положим по определению

	x		2
x Rn		1
	x
		x	2		b
		n				1
4) Обозначим через i				порог i -ой моды, а через вектор		i
					Bi
					b
						n
вторых моментов i				-ой моды		i

5) Кластер i и таксон i есть синоним термина мода i

Алгоритм “адаптивного выбора подклассов”

Начальные значения параметров ni i 0

i

1,z

Первый цикл итерации по обучающей выборке заключается в следующем.

Пусть на вход АВП поступили первые z векторов обучающей выборки j

1,z

Так как у нас на начальном этапе имеется z

свободных мод,

то указанные вектора становятся начальными векторами мод

M j X j

Bj

X 2j

для j

1,z

nj

1

Начиная с

z

1 -го вектора

алгоритм выходит на поиск ближайшей к данному вектору x моды i

min x j , Mi

x j , Mi

0

i

Алгоритм “адаптивного выбора подклассов”

Если выполняется условие

x j , Mi

i

0

что можно рассматривать как вхождение вектора x в указанную моду,

то происходит уточнение параметров данной моды по формулам

M 'i0

ni0

Mi0

1

x j

n

1

n

1

i0

i0

B'i0

ni0

1

Bi0

x j

ni 1

ni 1

0

0

n'

n

i

1

i

0

0

и происходит переход к анализу следующего вектора обучающей выборки.

Алгоритм “адаптивного выбора подклассов”

Если условие не выполняется, то осуществляется поиск двух ближайших существующих мод l0 и m0

min Ml , Mm

Ml0

, Mm0

чем к Ml

Mm

Если вектор X j ближе к

Mi

и

0

0

0

, Mm

Mi

Ml

X j ,

0

0

0

Mi

то происходит уточнение параметров моды

и корректируется порог моды i0

0

'

1

i0

max

X

, M

i0

2

j

i0

В противном случае производится объединение двух ближайших мод l0 и m0

	'				nl		nm
					0		0
	Ml					Ml		Mm
				nl0	nm0		nl0 nm0

Алгоритм “адаптивного выбора подклассов”

'		nl		nm
	0		0
Bl0			Ml0		Mm0
		nl0 nm0		nl0 nm0

	n'	n		n
	l0		l0	m0
	Mm' 0		0 ;	Bm' 0		0 ;			n'm0 0
	и мода с номером m0								становится свободной
	Новый порог моды							l0		определяется по формуле
	'				1
	l l m						Ml		,	Mm
					2
	0		0	0				0		0

Освободившаяся мода с номером m0

становится центром вновь формируемой на основании вектора X j моды

Mm		X j	nj 1
0			m 0
B		X 2
	m0	j	0

Алгоритм “адаптивного выбора подклассов”

Происходит переход к анализу следующего вектора обучающей выборки После просмотра всех Q векторов обучающей выборки

происходит оценка дисперсий кластеров Di и вероятностей кластеров Pi

1		2	2
Di		Bi	ni Mi
	ni 1

Pi nQi

Выявляются состоятельные кластеры, то есть те кластеры, для которых выполняется соотношение

ni T

Состоятельные кластеры перенумеровываются в порядке 1 Zc

И начинается второй этап итерации по обучающей выборке с целью уточнения оценок параметров кластеров.

Алгоритм “адаптивного выбора подклассов”

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

i arg min j x
	j

где

	1	n		xl mjl	2
					ln 2j l
j x							ln Pj
	2			2
		l 1		jl

Определяется уточненное значение центра кластера

	Mi				1			x j
					n
					i x i
					1					x Mi x Mi t
				n		1
		i								x i
					i