Задача кластеризации регионов РФ

sve9280

Добрый день!
Есть задача кластеризации (группировки) субъектов РФ (для конкретики, а вообще — просто географических областей).
Дано: значения некого вещественного параметра P — своё для каждого региона — и карта РФ :)
Необходимо: сгруппировать субъекты в кластеры (не более 10, скажем которые были бы, во-первых, связными георграфически, и во-вторых, характеризовались бы некой общностью значений параметра P.
Подскажите, есть ли какие-то программные пакеты, позволяющие решать подобные задачи? Поиск в гугле показывает, что чаще всего решают задачи кластеризации на карте для набора точек, но не целых географических областей, граничащих между собой, или же кластеризации географических областей, но не ставят явное и строгое условие на связность полученных кластеров.
P.S. про федеральные округа я знаю, но задачи это не снимает :)

griz_a

Задайте регионы точками в трехмерном пространстве, где одна координата - это P, а две других - географические координаты центра области, например. Только отцентрировать, отнормировать не забудьте.
Кстати, связность - это ленточные кластеры (то есть вытянутые допускаются) или все же сгущения?

sve9280

Вы знаете, мне кажется, не покатит такой подход, ведь субъекты значительно разнятся по своим площадям, поэтому от своих соседей Саха-Якутия окажется гораздо дальше, чем некоторые регионы из других кластеров :)
Критерий ленточности будем определять на практике :) Может быть, подойдут, может быть, нет. Для начала пусть хотя бы связными будут.
Одним способом я эту задачу уже решил. Упрощённо: для таблицы N*N, где N — число субъектов, заполнил значением 1 те ячейки с номерами столбца i и строки j, для которых субъект с номером j и субъект с номером i имеют общую границу, 0 — в противном случае. Добавил ещё столбец с признаком P. Таким образом получил таблицу из N + 1 столбца с отдельной строкой для каждого субъекта. Эти данные «засунул» в нейронную сеть Кохонена (ну или можно в кластеризатор — уже не столь принципиально) — получил разделение на кластеры. Даже связные. Но это какой-то очень «коленочный» метод. А ведь возможно есть специально предназначенные для подобных задач программные решения.

iri3955

Можно держать граф, где расстояние определяется разностью значений параметра.
А потом сформулировать задачу минимизации, тут уж как фантазии хватит.
Например, диаметром d региона обзывается максимальная разность значений параметрна в нём.
D - максимальный диаметр. p - кол-во регионов (P - кол-во субъектов).
Минимизируем какую-нибудь функцию f(D, p) (например, f = p(D + 1/P.
Будет 2 крайних случая. D = 0, p = P и D - почти макс. значение, p = 2.
Задача вроде NP-полная, но кажется приближённо делается, либо делением пополам, либо жадным
Но это придётся самому писать.

griz_a

Я же написал - например.
Можно дискретную метрику вводить (как у вас - граничит\не граничит но тогда надо либо методы типа ближнего соседа использовать, либо получится, что кластеры будут кривые.
Можно, например, вводить в качестве расстояния между регионами число регионов между ними (по кратчайшему пути). Только опять же, не забыть отнормировать.

sve9280

Я бы сделал больший упор на программы для работы с картами. Насколько я знаю, ArcGIS обладает довольно мощным функционалом по анализу картографических данных. Кластеризацию точек, как я понимаю, там сделать можно. А вот насчёт областей — непонятно.

seregen-ka

когда прочитал заголовок, почему-то в голове еще одна задача возникла -
виртуализации регионов РФ, а потом резервного копирования регионов РФ...
Оставить комментарий
Имя или ник:
Комментарий: