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

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


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

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

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

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

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

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

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

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

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

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

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

[формула евклидового расстояния]

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

[матрица расстояний]

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

K-Means

Плагин Attribute based clustering

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

Описание

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

Литература