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

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

классификация как необходимый предварительный этап статистической обработки многомерных данных;

классификация в задачах оптимального регулирования и планирования,

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

Само название метода происходит от того же корня, что и слово «класс», «классификация». Английское слово «the cluster» имеет значения: группа, пучок, куст, то есть объединение каких-то однородных явлений.

Все задачи кластерного анализа можно подразделить на два типа в зависимости от объема совокупности классифицируемых наблюдений:

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

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

С точки зрения информации об окончательном числе классов, на которое требуется разбить исследуемую совокупность объектов, задачи кластерного анализа можно подразделить на три типа:

число кластеров заранее задано;

число кластеров неизвестно и подлежит определению;

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

В соответствии с разделением задач кластерного анализа можно выделить три основных типа процедур кластерного анализа:

а) процедуры иерархические, предназначены в основном для решения задач типа 3; кластерный евклид математический статистический

б) процедуры параллельные, реализуемые с помощью алгоритмов, на каждом шаге которых одновременно используются все имеющиеся наблюдения;

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

Математический аппарат кластерного анализа.

Каждая единица совокупности в кластерном анализе считается «точкой в признаковом пространстве». Значение каждого из признаков у данной единицы совокупности служит ее координатой в этом «пространстве» по аналогии с координатами точки в нашем реальном трехмерном пространстве. Таким образом, «признаковое пространство» - это область варьирования всех признаков совокупности изучаемых явлений. Если мы уподобим это пространство нашему пространству, имеющему Евклидову метрику, то получим возможность измерять «расстояния» между точками признакового пространства. Эти расстояния называют «Евклидовыми». Их вычисляют по тем же правилам, как и в обычной Евклидовой геометрии. На плоскости (то есть в «двухмерном пространстве») расстояние между точками А и В равно, как показано на рисунке, корню квадратному из суммы квадратов разностей параметров рассматриваемых точек по осям координат - на основании знаменитой теоремы Пифагора.

Размещено на http://www.allbest.ru/

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

В многомерном признаковом пространстве расстояние между точками р и q с «К» координатами (то есть индивидуальными значениями К признаков) определяется как:

Размещено на http://www.allbest.ru/

(1)

Совершенно очевидно, что нельзя суммировать квадраты отклонений одной и точки от другой в абсолютных значениях разнокачественных признаков. Необходимо сначала выразить различия между единицами совокупности по каждому признаку в каком-то относительном безразмерном показателе. В качестве такого показателя часто применяют «нормированную разность», то есть величину:

Размещено на http://www.allbest.ru/

(2)

Иначе говоря, нормированная разность есть отношение абсолютной разности значений j - того признака у единиц совокупности с номерами p и q к среднему квадратическому отклонению этого признака. Знаки нормированных разностей не имеют значения, так как «расстояния» в признаковом пространстве - скалярная, а не векторная величина.

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

Размещено на http://www.allbest.ru/

(3)

Существует много достаточно сложных по алгоритму методик кластерного анализа и родственных ему, но иначе называющихся методов: «Распознавание образов», «Многомерная автоматизированная группировка и классификация». Однако можно привести один из простейших алгоритмов кластерного анализа. Этапы методики (алгоритм):

Вычисление средних величин каждого из группировочных признаков x_j по совокупности.

Вычисление средних квадратических отклонений каждого из группировочных признаков уxj по совокупности.

Вычисление матриц нормированных разностей по каждому из группировочных признаков.

Вычисление Евклидовых расстояний между каждой парой сочетаний единиц совокупности по формуле (3).

Выбор наименьшего из Евклидовых расстояний.

Объединение единиц совокупности с наименьшим Евклидовым расстоянием между ними в один кластер.

Вычисление новых, усредненных значений всех группировочных признаков для объединенного кластера.

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

Вычисление новых Евклидовых расстояний объединенного кластера от остальных единиц или кластеров.

Выбор наименьшего из Евклидовых расстояний.

11-16 - повторение операций 6-10 и так далее.

Объединение в кластеры прекращается, когда все Евклидовы расстояния между оставшимися кластерами, превысят заданную критическую величину r_max. Завершение объединения в кластеры может быть осуществлено не при достижении r _max, а при достижении заданного числа кластеров (типов). Так поступают, если число таких типических кластеров известно заранее или предполагается некоторой гипотезой.

В нормально распределенной совокупности нормированная разность в среднем равна единице. В такой совокупности средняя величина Евклидова расстояния должна быть, поэтому, равна корню квадратному из числа группировочных признаков К. В таком случае, в качестве предельной величины расстояния для продолжения объединения кластеров, можно принять эту величину среднего расстояния.

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