Центрографический метод

Алгоритмы и параметры кластеризации

Метод иерархических алгоритмов.

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

В прикладных социально-экономических исследованиях наи­более широкое применение получили две группы методов кластерного анализа:

1) метод иерархических алгоритмов

2) центрографический метод определения концентрации объектов.

Иерархические алгоритмы — это алгоритмы последовательной кластеризации (группировки) объектов по принципу от общего к частному.

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

Практическая реализация любого иерархического алгоритма предполагает выполнение следующих пяти действий:

1) представление всех последовательно наблюдаемых oбъктов х_i (i= 1,2, …, п) в виде п самостоятельных кластеров k_i;

2) определение пар наименьших расстояний d_lm между объектами l и кластерами т;

3) последовательное объединение выбранных пар и уменьшение числа кластеров на единицу на уровне каждого шага;

4) определение расстояния d_rq между значением r найденного и любого другого q;

5) последовательное применение действий пп. 2 — 4 до момента получения одного и только одного конечного кластера.

Реализация любого иерархического алгоритма предполагает, что наблюдаемые как внутригрупповые (d_ij), так и межгрупповые (d_rq) расстояния нормированы или задаются заранее требуе­мой метрикой.

Общая формула расчета расстояний между кластером r, пред­ставляющим результат объединения кластера l и m, с кластером q следующая:

где d_lq, d_mq, d_lm - геометрические расстояния между соответствующими

кластерами;

α_l, α_т, β, γ— параметры, определяющие конкретный алгоритм иерар­хической кластеризации.

В таблице приведены значения параметров, соответствую­щие трем рассмотренным критериям кластеризации.

Таблица.

Алгоритм	Значение параметра
αl	αт	β	γ
«Ближний сосед» «Дальний сосед»   «Средний сосед»	½ ½	½ ½		-½ ½

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

Шаг 1. Определим количество точек, попавших в этот ра­диус, на основе произвольно выбранной точки-центра, при заданном радиусе Т.

Шаг 2. Рассчитаем средние значения признаков по совокупности объектов, попавших в первый круг наблюдения.

Шаг 3. Определим среднюю для второго круга наблюдаемых объектов, приняв за очередную точку-центр при том же заданном радиусе Т.

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

Шаг 5. Интерпретируем полученный результат. Объекты, попавшие в последний круг, идентифицируем как объекты первого кластера, и, следовательно, исключаем их из дальнейшего анализа.

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

Шаг 7. Прекращаем процедуру. Процедура прекращается при условии распределения всех наблюдаемых объектов по кластерам.

Задача.

Проиллюстрируем методы кластерного анализа на примере классификации пяти точек: (4;3), (7;4), (2;0), (2;1), (0;4), изображенных на рисунке

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

За метрику расстояний примем квадрат евклидова расстояния.

;

;

;

;

;

;

;

;

;

.

Матрица расстояний приведена в таблице:

Дата добавления: 2014-10-22