Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

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

[pic]

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

[pic]

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

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

[pic]

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

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

Сегодня существует достаточно много методов кластерного анализа.
Остановимся на некоторых из них (ниже приводимые методы принято называть методами минимальной дисперсии).
Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., Хu) и квадрат евклидова расстояния между Х( и Хj определяется по формуле:
[pic]

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

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

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

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

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

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

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

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

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

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

{?1}, {?2}…, {? ( , ? j}, …, {?n}.

Повторяя процесс, получим последовательные множества кластеров, состоящие из (n-2), (n-3), (n–4) и т.д. кластеров. В конце процедуры можно получить кластер, состоящий из n объектов и совпадающий с первоначальным множеством ? = (?1, ?2, … ?n).

В качестве меры расстояния возьмем квадрат евклидовой метрики d( j2. и вычислим матрицу D = {di j2}, где di j2 - квадрат расстояния между

? ( и ? j:

| |?1 |?2 |?3 |…. |?n |
|?1 |0 |d122 |d132 |…. |d1n2 |
|?2 | |0 |d232 |…. |d2n2 |
|?3 | | |0 |…. |d3n2 |
|…. | | | |…. |…. |
|?n | | | | |0 |

Рекомендуем скачать другие рефераты по теме: определение реферат, красные дипломы.





Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата