Как работает инструмент Найти регионы

Инструмент Найти регионы находит наилучшие регионы во входном растре, которые удовлетворяют требованиям по размеру и пространственным ограничениям. Регионы – это непрерывные группы ячеек с одинаковыми значениями. Некоторыми из требований и ограничений, которые можно определить в этом инструменте, являются общая площадь для выборки, число регионов, среди которых должна быть распределена общая площадь, форма нужных регионов и максимальное/минимальное расстояние между регионами.

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

Примеры задач, решаемых инструментом Найти регионы.

При использовании поверхности, созданной в рамках модели пригодности, вы сможете определить наилучшие регионы для следующего:

• Наиболее подходящая зона для охраны места обитания оленей. Требуется восемь зон обитания для поддержания необходимой популяции, и каждый регион должен быть непрерывным и иметь площадь порядка 50 акров. Для обеспечения размножения в рамках стада эти регионы должны находиться достаточно близко друг к другу, чтобы они могли быть соединены посредством коридора дикой природы.
• Самые подходящие регионы для рубки леса. Чтобы производство было достаточно прибыльным, эти области (регионы) рубки леса должны быть непрерывными и иметь площадь, как минимум, 250 акров; все регионы также должны находиться друг от друга не дальше, чем в одной миле.
• Оптимальное местоположение для открытия нового торгового центра. Для торгового центра потребуется 60 акров; зона постройки должна быть непрерывной, а форма этого участка строительства должна быть максимально компактной.

Группировка ячеек в регионы

Для объединения отдельных ячеек в регионы в растре пригодности имеется шесть методов.

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

Общий алгоритм инструмента Найти регионы

Инструмент Найти регионы использует в качестве входных данных растр, в котором более высокие значения ячеек означают более высокую степень выгодности. На основе этого растра инструмент выбирает наилучшие регионы во входном растре, которые удовлетворяют требованиям к регионам и пространственным ограничениям.

Процесс поиска регионов в этом инструменте состоит из четырех шагов. Ниже подробно описаны эти четыре шага:

1. Устранить местоположения, которые не удовлетворяют требованиям выборки. Такими областями могут быть водные объекты, существующие строения и зоны со слишком крутыми уклонами. Это подготовительный шаг.
2. Определить характеристики требуемого региона или регионов. Такими характеристиками могут быть размер, форма и ориентация. На этом шаге производится настройка параметров инструмента.
3. Идентифицировать все возможные регионы из входного растра на основе определенного пользователем компромисса между заданной формой региона и максимизацией выгодности. Для этого на этом шаге используется доступный в инструменте алгоритм приращения региона.
4. Выбрать наилучший регион или регионы из регионов-кандидатов на основе пользовательских критериев оценки. Например, выбрать только регионы с наивысшими средними значениями. Этот шаг выполняется в этом инструменте с использованием алгоритма выборки на основе выбранного метода оценки.

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

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

• Критерий Метод оценки, например, максимальное среднее значение, максимальная сумма или максимальный объем границы.
• Межрегиональный критерий оценки, определенный параметрами Максимальное расстояние и Минимальное расстояние.

Когда требуется найти несколько регионов, то в параметре Метод отбора вы сможете указать дополнительные параметры отбора наилучших регионов. Это опции COMBINATORIAL и SEQUENTIAL.

• Если выбран метод COMBINATORIAL, то будет произведена оценка всех возможных комбинаций нужного числа регионов. Например, при использовании этого метода, если для параметра Число регионов будет выбрано восемь, и на основе алгоритма приращения регионов было создано 150 000 регионов, то будет произведена оценка всех возможных комбинаций из восьми регионов из этих 150 000 регионов-кандидатов для идентификации оптимального набора из восьми регионов на основе выбранного значения для параметра Метод оценки и пространственных ограничений. Может быть так, что наилучший регион не будет выбран, если он не попал в оптимальную группу из восьми регионов.
• Если выбран метод SEQUENTIAL, то первый регион, который был выбран и который удовлетворяет пространственным ограничениям, станет наилучшим регионом на основе значения параметра Метод оценки. Второй выбранный регион будет следующим наилучшим регионом на основе метода оценки, если он удовлетворяет пространственным ограничениям в отношении первого выбранного региона. Этот процесс продолжится, пока не будет создано нужно количество регионов, которое было определено для параметра Число регионов.

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

Распределение источников

Для снижения времени обработки, чтобы регионы наращивались не из каждой возможной ячейки входного растра, можно производить наращивание регионов-кандидатов из определенных ячеек (называемых источниками). Число источников, из которых будет производиться наращивание регионов, определяется в параметре Число начальных точек, от которых начинается приращение.

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

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

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

Пример распределения источников

В качестве упрощенного примера рассмотрим растр с четырьмя ячейками со значениями выгодности 1, 2, 3 и 4. Распределение будет создано на основе этих четырех значений. Сумма значений ячеек в этом случае равна 10. Эти значения будут нормализованы по шкале от 0 до 1. Ячейка со значением выгодности 1 составляет 10 процентов распределения (от 0 до 0.1 в распределении), ячейка со значением 2 составляет 20 процентов (от 0.1 до 0.3 в распределении), ячейка со значением 3 составляет 30 процентов (от 0.3 до 0.6 в распределении), а ячейка со значением 4 составляет 40 процентов (от 0.6 до 0.1 в распределении). Будет выбрано случайное значение в интервале от 0 до 1. Вероятность выбора случайного значения в интервале распределения от 0.6 до 10 составляет 40 процентов; в этом случае источник будет расположен в ячейке со значением 4, то есть в ячейке с максимальным значением выгодности.

Изменение разрешения приращения региона с учетом желаемого размера регионов

Помимо использования параметра Число начальных точек, от которых начинается приращение для снижения времени обработки, вы также можете улучшить производительность с помощью параметра Разрешение приращения. Вы можете использовать параметр Разрешение приращения, чтобы в работе алгоритма приращения потенциальных регионов (PRG) использовался промежуточный входной растр более низкого разрешения. В этом случае, как только нужные регионы будут выбраны из группы регионов-кандидатов с помощью промежуточного растра, будет произведено снижение разрешения полученных регионов до значения Размер ячейки для создания готового выходного растра. Разрешение промежуточного растра определяется по числу ячеек, связанных с указанным значением Разрешение приращения.

Чтобы в каждом полученном регионе было достаточно ячеек и чтобы избежать ненужной обработки, может быть произведено изменение разрешения и общего числа ячеек, определенных для каждого целевого значения Разрешение приращения для промежуточного растра. На основе разрешения, которое было определено в параметре Разрешение приращения, будет рассчитано число ячеек в регионе среднего размера. Средний размер региона можно получить при делении требуемой общей площади на указанное число регионов. Чтобы обеспечить достаточное количество ячеек в каждом выбранном регионе, если в регионе среднего размера будет слишком мало ячеек, то разрешение промежуточного растра будет увеличено (размер ячейки будет уменьшен, а число ячеек увеличится). Чтобы избежать ненужной обработки, если в регионе среднего размера будет слишком много ячеек, то разрешение промежуточного растра будет снижено.

Пороговые значения, необходимые для того, чтобы определить, не слишком ли много или мало ячеек в регионе среднего размера, определяются на основе параметра Разрешение приращения. Например, если была выбрана опция разрешения LOW, и число ячеек в регионе среднего размера слишком маленькое для получения корректных результатов, то для этой выборки с числом ячеек меньше 1800 разрешение промежуточного растра будет увеличено, чтобы в регионе среднего размера было, как минимум, 1800 ячеек. Это позволит обеспечить достаточное количество ячеек для создания приемлемых регионов. И наоборот, чтобы избежать ненужной обработки, если в регионе среднего размера будет больше, чем 5400 ячеек, то разрешение промежуточного растра для опции разрешения LOW будет снижено, чтобы в регионе среднего размера было не более 5400 ячеек.

Такие же настройки будут производиться для опций выборки MEDIUM и HIGH параметра Разрешение приращения, но пороговые значения могут отличаться. Для опции разрешения MEDIUM нижним пороговым значением для региона среднего размера является 3200 ячеек, а верхним – 9600 ячеек. Для опции разрешения HIGH нижним пороговым значением для региона среднего размера является 7200 ячеек, а верхним – 21600 ячеек.

В результате второй корректировки общее число ячеек для промежуточного растра, на основе которого будет произведен запуск алгоритма наращивания регионов-кандидатов для каждого указанного значения Разрешение приращения, может быть меньше или больше, чем целевое количество ячеек.

Определение регионов при использовании значений минимальной и максимальной площади

Если указаны значения для параметров Минимальная площадь региона и Максимальная площадь региона, то будет слишком много возможных комбинаций регионов для сравнения, если для каждого источника будет учитываться каждый возможный регион с размером в рамках указанных минимальной и максимальной площади. Поэтому для каждого источника 'этот алгоритм определит число регионов с допустимыми размерами, которые будут созданы в процессе наращивания регионов-кандидатов; они будут рассмотрены в процессе выборки COMBINATORIAL и SEQUENTIAL для идентификации наилучших регионов.

Все размеры регионов будут созданы на основе минимального, максимального и среднего размера региона. Для определения среднего размера региона алгоритм производит деление общей площади на указанное число регионов. Средний размер региона – это первый размер региона, который будет создан из каждого местоположения источника. Как правило, средний размер региона будет ближе к значению указанной минимальной или максимальной площади. То есть, это большее отклонение между Abs(максимум – среднее) или Abs(минимум – среднее). Это значение будет называться LargerDist.

Чтобы рассчитать интервал шага для определения размеров регионов, которые попадут в диапазон между средним размером региона и большим отклонением, используется следующая формула:

StepInterval = LargerDist/(N - 1)

• где N – это указанное число регионов.

Начиная со среднего размера региона, значение StepInterval будет последовательно добавляться или вычитаться, пока не будет достигнуто значение большего отклонения. То же значение StepInterval будет последовательно добавляться или вычитаться в противоположном направлении, пока не будет достигнуто значение меньшего отклонения.

На этом этапе обработки, если используется менее четырех размеров региона, то между каждым из существующих значений будет добавлено два дополнительных значения. Если используется 3-7 размеров региона, то между каждым из существующих значений будет добавлено одно дополнительное значение. В результате минимальное количество размеров регионов, которое будет создано из каждого источника, будет равно 7, и в зависимости от указанного значения регионов максимальное количество размеров региона будет 15.

Некоторые примеры с иллюстрацией работы этих параметров доступны ниже в этом разделе.

Когда указаны значения для параметров Минимальная площадь региона и Максимальная площадь региона, в процессе выборки COMBINATORIAL или SEQUENTIAL, каждый из размеров регионов будет рассмотрен для каждого источника в качестве региона-кандидата и протестирован в процессе выборки для идентификации наилучших регионов.

Если будет определен только параметр Минимальная площадь региона а параметр Максимальная площадь региона не будет определен, то максимальная площадь будет определена на основе минимальной площади, общей площади и указанного числа регионов. Например, для параметра Минимальная площадь региона выбрано 5 кв. миль, общая площадь равна 50 кв. милям, и число регионов равно 5. Максимальная возможная площадь определяется на основе того, что 4 региона имеют размер минимальной площади (в этом случае, 5 кв. миль), что дает в сумме 20 кв. миль. Остается область площадью 30 кв. миль, что составляет максимально возможную площадь, которая и будет использоваться. Такой же подход используется, когда указано значение только для параметра Максимальная площадь региона, но минимальная площадь должна быть больше 0.

Пример 1

В этом примере были определены следующие параметры:

• Общая площадь равна 300 кв. милям
• Число регионов равно 6
• Минимальная площадь региона равна 40 кв. милям
• Максимальная площадь региона равна 100 кв. милям

Первым размером региона, который будет создан в работе алгоритма приращений региона-кандидата, будет средний размер региона, который можно определить, разделив общую площадь на число регионов (300/6 = 50 кв. миль). Значение LargerDist составит 50 (LargerDist = Abs(100 – 50)). Значение StepInterval составит 10 (StepInterval = 50/(6 – 1)).

Чтобы рассчитать второй размер региона для создания из каждого источника, необходимо сложить значение StepInterval и средний размер региона (10 + 50) = 60 кв. миль. Затем нужно продолжить складывать значение StepInterval, равное 10, со значением среднего размера региона, пока не будет получено значение большего отклонения. Таким образом можно рассчитать третий, четвертый, пятой и шестой размеры регионов: 70, 80, 90 и 100 кв. миль, соответственно. Наконец, нужно продолжать вычитание значения StepInterval из значения среднего размера региона, пока не будет получено значение меньшего отклонения; таким образом, можно получить седьмой размер региона, 40 кв. миль. В этом случае из каждого источника будет создано 7 регионов; они будут иметь площадь 40, 50, 60, 70, 80, 90 и 100 кв. миль.

Пример 2

В этом примере были определены следующие параметры:

• Общая площадь равна 100 кв. милям
• Число регионов равно 4
• Минимальная площадь региона равна 10 кв. милям
• Максимальная площадь региона равна 60 кв. милям

Первым размером региона, который будет создан в работе алгоритма приращения региона-кандидата, будет средний размер региона, который можно определить, разделив общую площадь на число регионов (25 кв. миль).

Значение LargerDist составит 35 кв. миль (Abs(60 – 25)). Значение StepInterval составит 11.6667 (35/(4 – 1)). Затем нужно продолжить добавлять значение 11.6667 к значению среднего размера региона, пока не будет получено значение большего отклонения. Будут получены значения 36.6667, 48.3334 и 60. Затем нужно производить вычитание значения StepInterval из среднего размера региона до тех пор, пока разница не будет меньше или равна минимальному значению. Таким образом, будет получено значение 13.3333. На этом этапе было определено 5 размеров регионов: 13.3333, 25, 36.6667, 48.3334 и 60. Обратите внимание на то, что минимальное и максимальное значения, которые создали меньшее отклонение, не обязательно будут включены в список размеров регионов (в этом примере, 13.3333 – 11.6667 = 1.6666, что меньше 10). Таким образом, минимальное число размеров регионов, которое будет создано из каждого источника, будет равно 7, а максимальное число размеров регионов будет равно 15. Поскольку 5 меньше, чем требуемое минимальное значение 7, дополнительные размеры регионов будут добавлены между каждым из 5 размеров регионов. В этом примере из каждого источника будет создано 9 регионов; они будут иметь площадь 13.3333, 19.1667, 25, 30.8334, 36.6667, 42.5001, 48.3334, 54.1667 и 60 кв. миль.

Список литературы

Brooks, Christopher J. 1997. A parameterized region growing programme for site allocation on raster suitability maps International Journal of Geographic Information Science, 11:4, 375-396.

Brooks, Christopher J. 1997. A genetic algorithm for location optimal sites on raster suitability maps. Transactions in GIS, Vol. 2, No. 3, p 201-212.

Brooks, Christopher J. 1998. A genetic algorithm for designing optimal region configurations in GIS. Диссертация на степень Doctor of Philosophy, University College, University of London, London.

Brooks, Christopher J. 2001. A genetic algorithm for designing optimal patch configurations in GIS. International Journal of Geographic Information Science, Vol. 15, No. 6, 539-559.

Li, Xia and Anthony Gar-On Yeh, 2005. Integration of genetic algorithms and GIS for optimal location search, International Journal of Geographic Information Science, Vol. 19, No. 5, 581-601.