x X i

КЛАСТЕРНЫЙ АНАЛИЗ

Постановка задачи группировки данных

Задача состоит в том ,чтобы на основании данных , находящихся в множестве Х разбить их на m групп таким образом , чтобы

x X i

Такое разбиение должно отвечать некоторому критерию сходства, т.е. элементы из одного класса отвечают критерию сходства, а элементы из разных классов- нет.

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

Кластеризация может быть и нечетной. Может быть вероятностная постановка задачи кластеризации.

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

Мы будем рассматривать кластерный анализ в детерминированном смысле.

Задача классификации может решаться очень успешно, если вначале провести кластеризацию.

Задача кластеризации: 1)Изучение данных

2)Использование кластеров для более правильного решения задачи классификации.

На чем базируется задача кластеризации:

Результат кластеризации зависит от критерия, по которому будет проходить кластеризация. Большинство методов основано на понятии расстояния между объектами.

Х={3,4,7,4,3,3,4,4}

xcp 1 8 x 4

8 i 1 i

Сумма квадратов отклонения:

Пример

8

w (x xcp )2 12

i 1

x1 {3,3,3} x2 {4,4,4,4} x3 {7}

Внутригрупповые квадраты отклонения (критерий- это минимум внутригруппового отклонения)

w1=0

w2=0

w3=0

w=w1+w2+w3=0

Все метрические методы основаны функции расстояния между объектами.

Функция расстояния xi , x j x R

a) (xi , x j ) 0

b) (xi , x j ) 0; xi x j c) (xi , x j ) (x j , xi )

d ) (xi , x j ) (xi , xk ) (xk , x j )

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

N Наименование

1Евклидово расстояние

2Квадрат Евклидова расстояния

3L1-норма

4Supremum

5Lp- расстояние (расстояние Минковского)

6-нормаp,r

7Расстояние Махланобиса

8Для бинарных данных: расстояние Хемминга.

Формула

	n		1
		2	2
2 (xi , x j ) (xki xkj )
	k 1
	n
2 2	(xki xkj )2

k 1

n

1 (xi , x j ) xki xkj

k1

(xi , x j ) sup (xki xkj ) k 1..n

Обычно Sup сводится к максимуму. (Расстояние Чебышева)

n

1

xki xkj

p

p

p (xi , x j )

k 1

n

1

p,r (xi , x j )

xki xkj

p r

k 1

max2

(xi

x j )T 1 (xi

x j )

quantity{xki xkj } n

и т.д.)

Свойство расстояния Махланобиса:

xi , x j ,		заданы

это расстояние обладает свойством инвариантности по отношению к линейному преобразованию.

yBx

yi Bxi

yj Bx j

max2 (xi , x j ) max2 ( yi , y j )

(Нужно доказать свойство инвариантности. Выписать формулы

L (x , x ).; L ( y , y )

Если имеется maxобъектов,i j maxто можноi j определить матрицу расстояний между этими объектами для каждой пары xi и xj

Условно обозначим

(xi , x j ) ij

11		.	. 1m			Некоторые алгоритмы работают на основе таких матриц.
		.	.	.
.
	m1	.	.
				mm

Мера сходства определяется следующим образом: S(xi , x j ) Sij и обладают следующими свойствами:

a)0 S(xi , x j ) 1 b)S(xi , x j ) 1

c)S(xi , x j ) S(x j , xi ) m(xi ) 0

			n
		xki xkj
rij			i 1
		n			n			1
				2			2 2
			x	ki		x	kj
	k 1				k 1

rij-коэффициент корреляции.

Если m(xi ) 0 то rij определяется немного не так.

Меру сходства очень просто построить из меры расстояния:

Sij 1 1 ij2

Sij 1 ij 0 Sij 0 ij

Фактически это обратная функция

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

Sij nIy nij

n

-число совпадений единиц (если все совпадают, то Sij =1,если нет, то Sij =0) nnIyij -число совпадений нулей

Что такое расстояние между кластерами:

1)Расстояние на основе ближайшего соседа – это расстояние, которое определяется минимальным расстоянием между элементами рассматриваемых кластеров.

min (xi , x j )

min (Sl , Sq )	xi Sl
	x j Sq

2)Расстояние по принципу дальнего соседа(т.е. рассматриваются наиболее удаленные точки между объектами)

max (xi , x j )

max (Sl , Sq )

xi Sl

xj Sq

3)Расстояние между центрами тяжести (или между математическими ожиданиями)

(Sl , Sq ) (M l (x), M q (x))

M x средний вектор.

4)Расстояние по принципу средней связи.

	cp (Sl , Sq )	1	(xi , x j )
		nl nq
			xi Sl x j Sq