Материал: Методические указания к лабораторным работам №1-4 по дисциплине «Современные технологии обработки информации». Разинкин К.А

Лабораторная работа №3 Кластерный анализ

Пусть — исходная совокупность объектов, каждый из кото­рых задан набором р признаков. Например, объектами могут быть пациен­ты клиники, а признаками- физические данные (вес, давление и т. д.) и результаты амбулаторного обследования каждого пациента (содержание са­хара в крови, уровень гемоглобина и т. д.)

Задача кластерного анализа состоит в разбиении исходной совокупно­сти объектов на группы схожих, близких между собой объектов. Эти груп­пы называют кластерами или таксонами. Другими словами, кластерный анализ это один из способов классифи­кации объектов по их признакам [6].

Одна из концепций состоит в построении разбиения исходного множе­ства объектов доставляющего оптимальное значение определенной целевой функции. Большая группа методов кластеризации использует в качестве целевой функции внутригрупповую сумму квадратов: разбиение каждого множества должно быть таково, чтобы оно минимизировало внутригрупповые суммы квадратов. Эти методы используют евклидову метрику и назы­ваются методами минимальной дисперсии.

Пусть - объекты, каждый из которых задан набором р признаков. Распределения объектов по кластерам на однородные в некото­ром смысле группы должно удовлетворять критерию оптимальности, кото­рый выражается в терминах расстояния между любой парой объек­тов рассматриваемой совокупности.

В качестве расстояния (метрики) может быть взята любая неотрица­тельная действительная функция , определенная на множестве и удовлетворяющая следующим условиям:

а) тогда и только тогда, когда

б) ;

в) .

Выбор расстояния между объектами неоднозначен и в этом состоит основная сложность.

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

Если признаки измерены в разных единицах измерения, то требуется их предварительная нормировка — такое преобразование исходных дан­ных, которое переводит их в безразмерные величины.

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

; ,

4. Определите уравнение множественной регрессии для этих данных.

5. Какой процент дисперсии данных описывается этим уравнением?

где , i= l, 2, ..., 5 — нормированное значение; х — исходное значение, и — соответственно среднее и среднее квадратическое отклонение х, х' — эталонное (нормативное) значение, и — наибольшее и наименьшее значение х.

В пакете STATISTICA нормировка любой переменной выполняется по формуле . Для этого нужно щелкнуть правой кнопкой мыши на име­ни переменной и в открывшемся меню выбрать: Fill/Standardize Block ->Standardize Columns.

Нормировка, особенно по формуле , сильно искажает геометрию исходного пространства, что может изменить результаты кластеризации.

Выбор метрики для каждой задачи должен производиться с учетом це­лей кластеризации, свойств признаков анализируемых объектов, вероятно­стной структуры данных и т. п. [7].

Наиболее употребительные метрики следующие (в скобках указано анг­лийское обозначение некоторых метрик, используемых в пакете STATIS­TICA в опции Distance measure).

1. Евклидова метрика (Euclidean distance):

где — значение k-то признака i-го объекта.

2. «Взвешенная» евклидова метрика:

где W_k — «вес» k-гo признака. Применяется в тех случаях, когда каждому признаку можно приписать «вес», пропорциональный степени важности данного признака в задаче классификации.

3. Хеммингово расстояние

используется для признаков измеряемых в номинальной шкале и принимающих два значения. В пакете STATISTICA используется связан­ная с р_н метрика: процент несогласия (Percent disagreement).

4. Метрика Махаланобиса, определяемая формулой

где — ковариационная матрица генеральной совокупности, из которой извлекаются объекты и , — симметричная неотрицательно-опреде­ленная матрица весовых коэффициентов, выбираемая обычно диагональ­ной.

5. Коэффициент корреляции Пирсона (Pearson r):

где ,

Процедуры классификации на основе методов кластерного анализа ис­пользуют расстояния между множествами объектов. Эти расстояния можно ввести различными способами. Пусть ый класс (группа, кластер), — число элементов в классе, — «центр тяжести» i-го класса. Компо­ненты вектора вычисляются по формуле

Наиболее употребительные меры расстояния между классами следую­щие.

1. Расстояние, измеряемое по принципу «ближайшего соседа»

В этом методе расстояние между двумя кластерами определяется рас­стоянием между двумя наиболее близкими объектами (ближайшими сосе­дями) в различных кластерах. В результате кластеры представляют длинные «цепочки».

2. Расстояние, измеряемое по принципу «дальнего соседа»:

Расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т. е. «наиболее удаленными соседями»). Метод обычно работает очень хорошо, если клас­теры не имеют удлиненную форму.

3. Расстояние, измеряемое по «центрам тяжести» классов

4. Расстояние, измеряемое по принципу «средней связи»

5. Обобщенное расстояние (по А. Н. Колмогорову):

Обобщенное расстояние при , называется средним расстоянием между классами и , соответствующим данной метрике .

В процедурах кластеризации, использующих последовательное объеди­нение элементов и классов, применяется следующая формула для пересче­та расстояния между классом , и классом являющимся объ­единением двух классов S_m и S_q:

где п_т и п_q — число элементов соответственно в классах и S_q. С этой же целью используют также следующую формулу

(1)

где , , , и — числовые коэффициенты, значения которых определяет выбор той или иной меры расстояния между классами. Например, при — расстояние определяется по принципу ближайшего соседа; при — расстояние определяется по принципу да­льнего соседа; при , получим рас­стояние между классами, определяемое как среднее из расстояний между всеми парами элементов, из которых один берется из одного класса, а вто­рой из другого класса.