Критерии качества разбиения на классы

Критерий суммы квадратов ошибок: ni –элементов в Xi:
Мы можем ввести функцию разброса: Yl x mi				2
c
i 1 x X i

m 1 x

ni x X i

Здесь можно минимизировать только положение mi.

Этот критерий хорошо работает, когда предполагается, что кластеры хорошо разнесены.

Y

1

c

n

~

S

i

l

2

i

i 1

~

1

x x

2

Si

n

2

i

x

X x X

j

i

Есть критерий, основанный на матрице рассеивания: матрица рассеивания определяется следующим образом:

Si (x mi )(x mi )T x Xi

mi 1 x

ni x Xi

c

Sw Si

i 1

Где Si -матрица рассеяния внутри группы, Sw – суммарная матрица рассеяния внутри группы.

Есть понятия расстояния между группами:

		c
	SB ni (mi m)(mi m)T
		i 1
	m	1		x
		N			где	m -общее среднее, ST – общее рассеивание
				x X i

N n1 n2 nc

ST Sw SB

На данной базе рассматривают следующие критерии:

Yl tr Sw

c

min tr Sw min x mi 2

i 1 x X i

Еще один критерий основан на минимизации определителя матрицы рассеивания (данный критерий эквивалентен линейным преобразованиям):

Yl Sw ; min Sw

Основные типы кластерных процедур. Основные задачи кластерного анализа

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

1)Малые выборки (10-100 объектов)

2)Большие выборки (100-1000 и больше объектов)

•Задачи кластеризации с точки зрения априорной информации:

1)Число кластеров априорно задано

2)Число кластеров априорно не задано и их нужно определить

3)Число кластеров априорно не задано, но не требуется их точно определять в процессе обработки информации

•Имеются следующие виды процедур:

1)Иерархические. Они отличаются большим объемом вычислений. 2)Параллельные процедуры. На каждом шагу анализируется вся выборка.

3)Процедуры последовательного типа: на каждом шагу анализируется один элемент выборки. Цель-минимизация некоторого функционала разбиения.

Все задачи сводятся к минимизации следующего функционала:

c

I Ii

i 1

Ii x mi 2

x X i

Пусть мы делаем все переборы N-количество элементов

M ~ c N c!

5100

Пример: N=500 c=5, тогда полных переборов: М 1067 5!

Построение последовательной процедуры итеративной оптимизации

Пусть есть 2 кластера хi и хj

передвигаем эту выборку x в xj (физически она остается на месте в пространстве, но относится уже к хj)

Критерий качества:

Ii x mi 2

x xi

	mi	1	x
		Ni
			x Xi

Теперь передвигаем из I->J. Что поменяется в этом случае?

a)m*j m j

x

m j

N j

1

(1)

c

Ni

N

i 1

Когда передвинули i->j , то

Ni

: Ni 1; N j : N j 1

m

(N

j

1) x m

j

m

N

j

x

m*j

j

j

N j 1

N j

1

(2)

b)mi* mi

x mi

Ni

1

*

*

2

*

2

c)I j

x

m j

x m j

; x xi

(старые х)

После преобразования результат получился следующим:

I J* I J

N j

x m j

2

N j 1

Ii*

x mi*

2

x mi*

2

x X i

Ni

2

Ii* Ii

x mi

Ni 1

Ni

N j

c

x mi

2

x m j

2

Нам надо I Ii min, а это будет тогда, когда

N

i

1

N

j

1

i 1

Базовая процедура кластеризации (базовая минимальная квадратичная ошибка)

1)

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

x1,x2,…xc

Пусть с известно.

Вычисляем I и средние m1,m2,…mc .

Цикл:

2)

выбрать следующую выборку xˆ кандидата на передвижение xˆ X i

3)

если Ni =1 , то перейти к следующему, иначе вычислить:

n j

xˆ m j

2

j i

1

n

j

j

ni

xˆ mi

2

j i

ni 1

4)	Передвинуть x в ХК ,если	k i для всех I
	c
5)	Вновь вычислить I = i	, mi , mk

i 1

Следующий:

6) если I не изменилось после N попыток – остановка; иначе перейти к Цикл

N- число выборок

Это типичная последовательная процедура.