Реферат: Кластерный анализ

3. Сюпремум - норма d¥ (Хi , Хj) = sup

k = 1, 2, ..., р

4. lp - норма dр(Хi , Хj) =

Евклидова метрика является наиболее популярной. Метрика l1 наиболее легкая для вычислений. Сюпремум-норма легко считается и включает в себя процедуру упорядочения, а lp - норма охватывает функции расстояний 1, 2, 3,.

Пусть n измерений Х1, Х2,..., Хn представлены в виде матрицы данных размером p ´n:

Тогда расстояние между парами векторов d(Хi , Хj) могут быть представлены в виде симметричной матрицы расстояний:

Понятием, противоположным расстоянию, является понятие сходства между объектами Gi. и Gj. Неотрицательная вещественная функция S(Хi ; Хj) = Sij называется мерой сходства, если :

1) 0£ S(Хi , Хj)<1 для Хi¹ Хj

2) S(Хi , Хi) = 1

3) S(Хi , Хj) = S(Хj , Хi)

Пары значений мер сходства можно объединить в матрицу сходства:

Величину Sij называют коэффициентом сходства.

1.3. Методы кластерного анализа.

Сегодня существует достаточно много методов кластерного анализа. Остановимся на некоторых из них (ниже приводимые методы принято называть методами минимальной дисперсии).

Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., Хu) и квадрат евклидова расстояния между Хi и Хj определяется по формуле:

1) Метод полных связей.

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

2) Метод максимального локального расстояния.

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

3) Метод Ворда.

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

4) Центроидный метод.

Расстояние между двумя кластерами определяется как евклидово расстояние между центрами (средними) этих кластеров:

d2 ij = (`X –`Y)Т(`X –`Y) Кластеризация идет поэтапно на каждом из n–1 шагов объединяют два кластера G и p, имеющие минимальное значение d2ij Если n1 много больше n2, то центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп.

1.4 Алгоритм последовательной кластеризации.

Рассмотрим Ι = (Ι1, Ι2, … Ιn) как множество кластеров {Ι1}, {Ι2},…{Ιn}. Выберем два из них, например, Ι i и Ι j, которые в некотором смысле более близки друг к другу и объединим их в один кластер. Новое множество кластеров, состоящее уже из n-1 кластеров, будет:

{Ι1}, {Ι2}…, {Ι i , Ι j}, …, {Ιn}.