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

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

Пример применения кластерного анализа. Рассмотрим n стран, каждую из которых характеризуем валовым национальным продуктом на душу населения (С1), личным потреблением на душу населения (С2), потреблением электроэнергии на душу населения (С3) и т.п. Тогда Х1 (вектор измерений) представляет собой набор указанных характеристик для первой страны, Х2 – для второй страны и т. д. Задача заключается в том, чтобы разбить страны по уровню развития.

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

Решение задачи кластерного анализа основано на количественном определении понятия сходства и разнородности. Оно основано на определении расстояния между Хi и Xj. Функция расстояния (метрика или мера) – неотрицательная вещественная функция d (Xi, Xj), обладает свойствами.

1. d (Xi, Xj) > 0 для всех Xi и Xj

2. d (Xi, Xj) = 0 тогда и только тогда, когда Xi = Xj

3. d (Xi, Xj) = d (Xj, Xi)

4. d (Xi, Xj) < d (Xi, Xk) + d (Xk, Xj)

Наиболее употребительные метрики

1. Евклидова d (Xi, Xj) = ((Xki – Xkj))

2.. l – норма (манхеттенская) d (Xi, Xj) = | Xki - Xkj|

3. Сюпремум - норма d (Xi, Xj) = sup (|Xki – Xkj|)

N измерений X1, X2, … Xn могут быть представлены в виде матрицы данных размером n* p, где р – число количественных показателей.

Х = (Х1, Х2, … Хn)

Аналогичным образом могут быть выражены матрицы расстояний.

Понятием, противоположным расстоянию между Xi и Xj является понятие сходства. Неотрицательная вещественная функция S (Xi, Xj) = Sij называется мерой сходства, если

1. 0 < S (Xi, Xj) < 1 для Xi Xj

2. S (Xi, Xi) = 1

3. S (Xi, Xj) = S (Xj, Xi)

На основании анализа матрицы меры расстояния или матрицы меры сходства согласно заданному критерию оптимальности разбивают совокупность из n объектов на отдельные группы (кластеры).

Пример выполнения задания.