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

Материал из GIS-Lab
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 2: Строка 2:
{{Аннотация|Кластеризация векторных объектов по атрибутам в QGIS: описание плагина для QGIS, используемые принципы, примеры использования}}
{{Аннотация|Кластеризация векторных объектов по атрибутам в QGIS: описание плагина для QGIS, используемые принципы, примеры использования}}


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


==Кластеризация объектов==
==Кластеризация объектов==
Строка 69: Строка 69:
[[Файл:At_based_clust_len_obl_color.png|center|600px|Визуализация результата кластеризации по признакам A и B]]
[[Файл:At_based_clust_len_obl_color.png|center|600px|Визуализация результата кластеризации по признакам A и B]]


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


=== K-Means ===
=== K-Means ===
K-Means - классический метод, широко описанный в литературе и статьях в сети Интернет. Общая идея заключается в следующем: изначально выбираются N (по числу требуемых групп) центров, которые затем итеративно перевычисляются таким образом, чтобы минимизировать суммарное квадратичное отклонение точек, относимых к этим центрам [[https://ru.wikipedia.org/wiki/K-means wikipedia]]. Существующие реализации (для модуля использована [http://docs.scipy.org/doc/scipy/reference/cluster.vq.html scipy.cluster]) обеспечивают очень быструю обработку больших наборов данных, однако у быстродействия есть своя цена - нестабильность, обусловленная сильной зависимостью от начального выбора кластеров (в данном случае случайного). Компенсировать эту нестабильность можно лишь увеличивая число итераций перевычисления центров кластеров, что, очевидно, негативно сказывается на той же производительности. При работе с большими массивами данных, когда иерархическая кластеризация требует слишком много ресурсов, K-Means выручает и демонстрирует хорошие результаты. Помимо нестабильности, среди недостатков можно упомянуть, что в scipy-реализации нет поддержки весов.


== Плагин Attribute based clustering ==
== Плагин Attribute based clustering ==


=== Общая информация ===
=== Общая информация ===
Разработанный модуль реализует кластеризацию по атрибутам вышеописанными методами. Иерархическая кластеризация нативная и не требует дополнительных библиотек, K-Means требует наличия SciPy. Распространяется по лицензии [http://www.gnu.org/licenses/old-licenses/gpl-2.0.html GNU GPL v2], поддерживается версиями QGIS от 2.0 и выше.
Для установки модуля достаточно загрузить архив и распаковать его содержимое как директорию в <home dir>/.qgis2/python/plugins/
Например, в Windows это может быть папка C:/users/silent/.qgis2/python/plugins/attributeBasedClustering/
В Linux: /home/silent/.qgis2/python/plugins/attributeBasedClustering/
[http://plugins.qgis.org/plugins/attributeBasedClustering/ Модуль в репозитории QGIS]
[https://github.com/silenteddie/attributeBasedClustering GitHub]


=== Описание ===
=== Описание ===

Версия от 00:47, 27 апреля 2016

Эта страница является черновиком статьи.


Кластеризация векторных объектов по атрибутам в 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

K-Means - классический метод, широко описанный в литературе и статьях в сети Интернет. Общая идея заключается в следующем: изначально выбираются N (по числу требуемых групп) центров, которые затем итеративно перевычисляются таким образом, чтобы минимизировать суммарное квадратичное отклонение точек, относимых к этим центрам [wikipedia]. Существующие реализации (для модуля использована scipy.cluster) обеспечивают очень быструю обработку больших наборов данных, однако у быстродействия есть своя цена - нестабильность, обусловленная сильной зависимостью от начального выбора кластеров (в данном случае случайного). Компенсировать эту нестабильность можно лишь увеличивая число итераций перевычисления центров кластеров, что, очевидно, негативно сказывается на той же производительности. При работе с большими массивами данных, когда иерархическая кластеризация требует слишком много ресурсов, K-Means выручает и демонстрирует хорошие результаты. Помимо нестабильности, среди недостатков можно упомянуть, что в scipy-реализации нет поддержки весов.

Плагин Attribute based clustering

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

Разработанный модуль реализует кластеризацию по атрибутам вышеописанными методами. Иерархическая кластеризация нативная и не требует дополнительных библиотек, K-Means требует наличия SciPy. Распространяется по лицензии GNU GPL v2, поддерживается версиями QGIS от 2.0 и выше.

Для установки модуля достаточно загрузить архив и распаковать его содержимое как директорию в <home dir>/.qgis2/python/plugins/

Например, в Windows это может быть папка C:/users/silent/.qgis2/python/plugins/attributeBasedClustering/

В Linux: /home/silent/.qgis2/python/plugins/attributeBasedClustering/

Модуль в репозитории QGIS

GitHub

Описание

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

Литература