4.3.3. Агломеративный алгоритм кластеризации лесных массивов

Классические агломеративные алгоритмы кластеризации выполняют сле­дующую последовательность шагов:

Шаг 1. В соответствии с выбранным критерием (например, метрикой евклида) рассчитываются расстояния между всеми парами объектов (или альтерна­тив в случае многокритериального оценивания). В таблице, содержащей описание m покрытых лесом земельных участков, таких расстоянии будет: m*(m-1)/2

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

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

В случае двух интегральных индексов, как это представлено в табл.4,2, экологическое качество земельных участков можно изобразить в виде точек на координатной плоскости, как это показано на рис.4.16.

Полужирной линией на рис.4.16 показано расстояние между первым и пя­тым участками. Всего таких расстояний будет: 5*(5-1)/2 = 10. Их удобно предста­вить в виде квадратной матрицы:

В матрице Y на главной диагонали приведены расстояния объектов самих с собой, которые равны нулю. Матрица Y симметрична, так как расстояние от I-го объекта до /-го равно расстоянию от У-го до 7-го.

Таблица 4.2. Пример таблицы качества земельных участков:

Шаг 2. Осуществляется группировка объектов в бинарное иерархичное дерево.

На этом шаге алгоритма объекты объединяются в пары по критерию минимального расстояния между ними. Эти пары называются бинарными кластерами.

Далее алгоритм объединяет образованные на нижнем уровне пары класте­ров в пары более высокого уровня иерархии. Таким образом формируется бинарное дерево кластеров, которое получило название дендрограммы.

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

Рис.4.13. Пример расположения пяти земельных участков

на координатной плоскости экологического качества природной

среды: 11,1₂ - интегральные индексы

1 Рис.4.14. Пример формирования бинарных кластеров на схеме расположения пяти земельных участков на координатной плоскости экологического качества природной среды.

Рис.4.15. Дендрограмма дерева кластеров земельных участков,

сгруппированных по критерию экологического качества природной среды

Рис.4.16. Схематическое изображение расстояний между границами двух соседних экологических зон

На рис.4.17 представлены новые объекты со следующими номерами. Шес­той объект - бинарный кластер, объединивший 1-й и 2-й земельные участки. Седьмой объект - бинарный кластер, объединивший 3-й и 4-й земельные участ­ки. Восьмой объект - бинарный кластер, объединивший 6-й и 7-й объекты -кластеры нижнего уровня иерархии.

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

Группировка земельных участков в кластеры показана в виде таблицы в табл.4.3.

Более наглядную картину расположения бинарных кластеров можно полу­чить с помощью дендрограммы. Дендрограмма, соответствующая табл.4.3., представлена на рис.4.15.

Шаг 3. Выделение кластеров с помощью дендрограммы.

Как следует из рис.4.15, первые четыре земельных участка можно объеди­нить в единый класс качества, поскольку расстояние между всеми объектами ■этого кластера много меньше, чем расстояние от него до пятого земельного участка.

Таблица 4.3. Пример таблицы с описанием бинарного дерева кластеров экологического качества земельных участков:

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

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

Для рассмотренного примера коэффициенты несоответствия представлены

в табл.4.4.

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

сечения.

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

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

Для модельной доза-эффект зависимости, представленной на табл.4.1, на­ми были выделены пять зон экологического районирования со следующими диапазонами по дозе: {0 +,-0,25; 0,25 +,- 0,32; 0,32 +,- 0,55; 0,55 +,- 0,75; 0,75 +,- 1}. Используя эти граничные точки по дозе и таблицы доза-эффект зависимостей, можно получить граничные точки по эффекту. Граничные точки по эффекту представляют собой граничные величины интегральных индексов. В случае от­сутствия в табл. соответствующих измерений можно воспользоваться интерпо­ляцией.

Таблица 4.4. Коэффициенты несоответствия объектов дендрограммы рис.4.19

Номер объектов	Средняя дли­на связи	Стандартное отклонение длин связей	Количество свя­зей, использо­ванных для рас­чета	Коэффициент несоответствия
(1-2)	1	0	1	0
(3,4)	1	0	1	0
(6,7)	1,138	0.239	3	1.155
(8,5)	1,982	0,803	2	0,707

Шаг 2. В конфигурационном пространстве интегральных индексов рассчи­тывается матрица расстояний R между соседними экологическими зонами. Ка­ждая строка матрицы R соответствует двум соседним зонам и включает три расстояния, показанные на рис.4.16.

Количество строк в матрице равно: N - 2, где N- количество экологических зон, полученное в результате анализа доза-эффект зависимостей. .

Шаг 3. Рассчитываются минимальное и максимальное расстояния между соседними зонами:

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

Шаг 4. Осуществляется построение дендрограммы.

Шаг 5. На дендрограмме проводятся два сечения на уровнях: r_mjn и r_max. В результате в качестве кластеров выделяются только те узлы, которые попадают в интервал: (r_min, г_шах). При этом используется матрица объектов, пример кото­рой представлен в табл.4.3.

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

Рис.4.17. Блок-схема агломеративного алгоритма кластеризации

с учетом притяжения кластеров к особым точкам доза-эффект

зависимостей