Плагин Attribute based clustering - простая кластеризация векторных объектов по атрибутам в QGIS

Материал из GIS-Lab
Перейти к навигации Перейти к поиску
Эта страница является черновиком статьи.


Кластеризация векторных объектов по атрибутам в QGIS: описание плагина для QGIS, используемые принципы, примеры использования

В географических исследованиях часто возникает задача типологии изучаемых объектов по набору формализованных параметров. Как сгруппировать большое количество объектов в небольшое число классов по совокупности показателей, определенных для каждого их этих объектов? Существуют различные подходы, в том числе и математический. В статье приводится краткое описание двух простых методов: взвешенной иерархической кластеризации и классического K-Means; описывается разработанный плагин Attribute based clustering, реализующий их; приводится несколько примеров использования.

Кластеризация объектов

Обыкновенно, говоря о кластеризации объектов в ГИС, подразумевают их группировку по пространственному положению (для QGIS см. ConcaveHull Plugin, SciPy Clustering). Однако не менее интересной является кластеризация по атрибутам, когда пространственное положение объекта не играет роли (только если оно не формализовано как атрибут), а значимыми являются его некоторые числовые характеристики. Представьте себе, что каждый объект некоторого набора данных о районах Ленинградской области описывается двумя значениями A и B (это может быть что угодно - площадь, показатель престижности или конфликтогенности, количество музеев, средняя концентрация какого-либо вещества в атмосфере и пр. В данном случае значения получены случайным образом).

Районы Ленинградской области с некоторыми атрибутами

Поскольку пространственное положение нас не очень интересует, посмотрим на те же самые объекты в двумерном пространстве, где осями координат являются эти самые показатели A и B:

Представление объектов в пространстве атрибутов A и B

В данном случае, поскольку показатели неоднородны (т.е. у них разная метрика, условно, в A - экологический показатель, в B - показатель, связанный с людьми), для того, чтобы их можно было сравнивать, они были нормализованы (максимальное значение каждого показателя принято за 1, остальные изменены пропорционально). Именно поэтому на осях графика приведены не абсолютные значения A и B. Нормализация - не обязательная процедура, но она обеспечивает относительно равный вклад каждого показателя в кластеризацию, вне зависимости от их метрики. Иногда, если, к примеру, кластеризация осуществляется по некоторым "балльным" показателям, уже приведенным в нужную исследователю шкалу, нормализация может и навредить.

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


Визуальное выделение объектов в 4 группы

Присвоив соответствующим районам номера групп, в которые они попали, мы решим задачу кластеризации. Однако, развивая мысль, можно столкнуться с массой усложнений: если объектов будет гораздо больше, и группы не будут выделяться так явно - как быть? А что, если производить группировку не по двум показателям, а по N (в N-мерном пространстве признаков)? Да и желаемое количество кластеров может быть очень различным. Визуальной оценкой графика уже не обойдешься!

Взвешенная иерархическая кластеризация

Самый простой, но понятный с точки зрения логики работы алгоритм - иерархическая кластеризация. Его сущность заключается в последовательном объединении наиболее близких друг к другу объектов в группы до тех пор, пока таких групп не останется ровно столько, сколько требуется выделить кластеров. Опишем принцип на примере тех же самых районов Ленинградской области. Первый шаг - считаем каждый отдельный объект принадлежащим своей собственной, независимой группе (в нашем случае начинаем с 18 групп). Вычисляем расстояния между всеми этими группами и... Так, а вот только что считать расстоянием? Самый простой способ - расстояние в N-мерном евклидовом пространстве, вычисляемое по формуле:

Расстояние в n-мерном евклидовом пространстве с весами

где d - собственно расстояние; an, bn - координаты объектов a и b на n-ой оси пространства; wn - вес n-го признака.

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

Результатом расчёта по такой формуле (в данном случае с равными весами = 1) является матрица расстояний (для оптимизации использования ресурсов - только одна её половина, вторая была бы симметричной). В нашем случае она выглядит вот так:

[[0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.31, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.43, 0.56, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.37, 0.40, 0.80, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.54, 0.84, 0.50, 0.83, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.61, 0.78, 0.22, 0.99, 0.47, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.25, 0.42, 0.68, 0.18, 0.65, 0.84, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.22, 0.43, 0.64, 0.24, 0.60, 0.80, 0.06, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.40, 0.11, 0.58, 0.50, 0.91, 0.80, 0.53, 0.54, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.22, 0.35, 0.65, 0.16, 0.68, 0.83, 0.08, 0.11, 0.45, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.10, 0.29, 0.53, 0.27, 0.62, 0.72, 0.17, 0.16, 0.39, 0.12, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.27, 0.52, 0.66, 0.31, 0.55, 0.80, 0.13, 0.09, 0.63, 0.20, 0.24, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.27, 0.52, 0.66, 0.31, 0.55, 0.80, 0.13, 0.09, 0.63, 0.20, 0.24, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.64, 0.36, 0.70, 0.75, 1.11, 0.90, 0.79, 0.80, 0.26, 0.71, 0.65, 0.88, 0.88, 0.00, 0.00, 0.00, 0.00, 0.00],
 [0.06, 0.37, 0.43, 0.39, 0.49, 0.60, 0.25, 0.21, 0.46, 0.24, 0.14, 0.24, 0.24, 0.70, 0.00, 0.00, 0.00, 0.00],
 [0.67, 0.86, 0.31, 1.04, 0.42, 0.11, 0.88, 0.83, 0.89, 0.88, 0.77, 0.83, 0.83, 1.00, 0.64, 0.00, 0.00, 0.00],
 [0.43, 0.74, 0.53, 0.68, 0.17, 0.57, 0.50, 0.44, 0.83, 0.54, 0.49, 0.38, 0.38, 1.05, 0.38, 0.55, 0.00, 0.00],
 [0.32, 0.62, 0.44, 0.60, 0.24, 0.52, 0.42, 0.36, 0.71, 0.45, 0.38, 0.32, 0.32, 0.93, 0.26, 0.52, 0.12, 0.00]]

Теперь найдем в ней минимальное расстояние: 0.06. Оно соответствует двум объектам, которые находятся ближе всего друг к другу в нашем пространстве признаков (1 и 15). Объединяем их в одну группу, рассчитывая для этого их среднее положение. Теперь кластеров стало на один меньше: а две точки слились в одну. Посмотрим на график ещё раз:

Объединение двух точек

Хорошо видно, что были объединены две самые близкие точки. Возвращаемся к расчёту расстояний (теперь новых, ведь ситуация изменилась) и построению матрицы. Её размерность, конечно, уменьшится на 1. Повторяем поиск минимального расстояния и объединение точек. Развлекаясь так некоторое время, обнаруживаем, что осталось всего 4 точки:

Последний шаг - осталось 4 точки

Это, по сути, центры искомых кластеров. Пометив, какая исходная точка попала в конечном итоге в какую из этих 4х, мы получаем список точек-участниц каждой группы. А это и есть искомое. Покрасив районы Ленинградской области в соответствии с принадлежностью к группам, визуализируем результаты кластеризации:

Визуализация результата кластеризации по признакам A и B

Алгоритм справится с практически любым количеством признаков (параметров), по которым исследователю нужно кластеризовать объекты, а возможность задавать веса делает его достаточно гибким. Но есть и существенный недостаток - необходимость расчёта матрицы расстояний (размером NxN, где N - текущее количество групп). Если ваш набор данных содержит 1000 объектов, матрица на первом этапе будет содержать 1000000 ячеек, из которых для ~500000 придётся рассчитывать расстояния. При работе с разработанным модулем, реализующим иерархический метод, как будет показано дальше, относительно комфортно можно обрабатывать слои с сотнями и первыми тысячами объектов.

K-Means

Плагин Attribute based clustering

Общая информация

Описание

Использование

Литература