Разработка вычислительных алгоритмов для решения задач геоинформатики

Разработка вычислительных алгоритмов для решения задач геоинформатики

 

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

• для ISODATA алгоритма кластеризации гиперспектральных изображений разработаны параллельные алгоритмы с применением технологий MapReduce и MPI;
• выполнена программная реализация параллельных алгоритмов кластеризации гиперспектральных изображений;
• результаты работы программ были протестированы на данных, предоставленных сотрудниками кафедры геоинформатики КазНУ имени аль-Фараби.

Введение. В настоящее время в областидистанционного зондирования Земли (ДЗЗ) одной из актуальных задач является разработка вычислительно эффективных методов для хранения и обработки больших объемов данных. Часто от приложений по обработке данных ДЗЗ требуется возможность предоставлять ответы на запросы в реальном, или близком к реальному, масштабе времени. Одним из важных объектов ДЗЗ являются гиперспектральные изображения. В таких изображениях собираются данные по десяткам и сотням спектральных диапазонов. Сцены, предоставляемые датчиками ДЗЗ, часто называют «кубами данных», для обозначения их высокой размерности [1]-[2].

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

В данной работе представлена реализация параллельного алгоритма кластеризации гиперспектральных изображений с использованием технологии распределенных вычислений MapReduce [3]. Результаты, полученные в работе, показывают высокую эффективность применения технологии MapReduce к задачам обработки гиперспектральных изображений.

Алгоритм кластеризации ISODATA. Алгоритм кластеризации ISODATA (Iterative Self-Organizing Data Analysis Techniques) является разновидностью алгоритма кластеризации k-means [1], [4]. Основная идея алгоритма k-means заключается в пошаговом нахождении центров тяжести кластеров путем минимизации показателя качества, определенного как сумма квадратов расстояний всех точек, входящих в кластерную область, до центра кластера.

Имеется набор точек {x1, x2, …, xN}, состоящий из Nэлементов. Согласно [4] каждый центр кластера zj, j=1, 2, …, Nc, локализуется и корректируется посредством приравнивания его выборочному среднему, найденному по соответствующему подмножеству Sj, т.е.

 

,  j=1, 2, …, Nc

 

Алгоритм кластеризации ISODATA отличается от алгоритма k-means введением эвристических процедур, которые позволяют регулировать число кластеров: объединять кластеры, разделять один кластер на два [4].

Обзор работ по данной теме. Параллельным алгоритмам кластеризации изображений посвящено большое количество работ. В статьях [5]-[6] для параллельной обработки используется технология MPI. Применение технологии MPI требует задания точного числа узлов, причем в случае отказа какого-либо узла, задача должна быть запущена заново. В отличие от этого технология MapReduceвопросы отказоустойчивости, балансировки нагрузки решаются самой выполняющей системой. Ряд работ посвящен реализации алгоритмов кластеризации с применением технологии MapReduce [7]-[11]. Работа [7] описывает подход для кластеризации web документов, при этом учитывается специфика представления web документов. В работе [8] изложен подход кластеризации большого количества спутниковых снимков. Процесс начинается с определения для каждого пикселя ближайшего кластерного центра, а затем вычисления новых центров кластеров на основе пикселей кластерных областей. Общий метод, который для вычисления новых кластерных центров суммирует значениявсех пикселей нового кластера, а затем делит сумму на количество пикселей кластерной области, может привести к переполнению в условиях массовых вычислений. Поэтому принимается стратегия, которая вычисляет новое среднее значение по формуле:

 

= + [Pi – mk] / (Nk + 1)      (1)

 

В (1) означает текущее среднее значение, – текущее количество пикселей, Pi – значение следующей пиксельной точки, [Pi – mk] – разницу между Pi и mk, mk¢ – новое среднее значение. В [9] дан обзор основных алгоритмов обработки изображенийдистанционного зондирования. При этом описана реализация этих алгоритмов для частного случая представления обрабатываемых данных в формате TIFF. В работе [11] предлагается итерационный алгоритм кластеризации, но в отличие от подхода, представленного в [8], кластеризации подвергаются небольшие случайные подмножества данных, для того, чтобы найти соответствующие центроиды для всего набора данных. Этот процесс повторяется многократно, и в результате выбирается оптимальный набор кандидатов центроидов.

В данной работе использован подход из [8], а также предложен вариант реализации алгоритма кластеризации с использованием комбинаторов ([10], [12]), который позволяет улучшить производительность алгоритма.

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

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

Для решения задач с использованием парадигмы MapReduce была выбрана платформа Hadoop [13], которая является каркасом с открытым исходным кодом, предназначенным для создания и запуска распределенных приложений, обрабатывающих большие объемы данных. Неотъемлемым компонентом платформы Hadoop является распределенная файловая система HDFS (Hadoop distributed file system). В основе распределенной файловой системы лежит архитектура master/slave (главный/подчиненный), в которой основной узел поддерживает информацию о файловом пространстве имен (метаданные, структуры директорий, соответствие между определенными файлами и блоками данных, расположение блоков данных и права доступа), а подчиненные узлы управляют непосредственно самими блоками данных [12]-[13].Основной функцией распределенной файловой системы является разделение данных определенного пользователя на блоки данных и репликация данных блоков данных по локальным дискам узлов кластера (рис. 1).

Рисунок 1. Концептуальная модель MapReduce

 

Параллельный алгоритм кластеризации с применением технологии MapReduce. Основная идея параллельной реализации алгоритма кластеризации ISODATA, основанной на технологии MapReduce, заключается в классификации каждого пикселя до ближайшего кластера в функции Map и расчета новых кластерных центров в функции Reduce [8]:

Алгоритм 1:

Map:

Входныеданные: (key, set<pair <pixel, set <pixel>>>).

Выходныеданные: (centroid_id, pixel).

1. Считать значение пикселя  и значения текущих центроидов.

2. Для каждого пикселя  найти ближайший центроид.

3. Назначить пиксель соответствующему  кластеру.

Reduce:

Входныеданные: (centroid_id, set <pixel>).

Выходныеданные: (new_centroid, pixels).

1. Считать значения пикселей  с соответствующим идентификатором  центроида.

2. Вычислить новый центроид.

 

Входные данные для функций Map и Reduce организовываются в виде пар: ключ-значение, key/value. Ключ key во входных данных функции Map не несет полезной информации, но он необходим согласно структуре входных данных; значение valueкаждого пикселя представляет собой строку, состоящую из идентификатора пикселя и значений R, G, B разложения пикселя на цветовые составляющие. Входные данные распределяются между Mapper-ами. Начальное множество кластерных центров или центроидов передается каждому Mapper-у. Каждый центроид задается своим идентификатором в качестве ключа key и значением центроида в качестве значенияvalue. Map функция, сравнивая значение очередного пикселя со значениями кластерных центров, определяет, к какому кластерному центру ближе всего расположен пиксель. Выходными данными Mapper-а будут пара ключ/значение для каждого пикселя, где ключ будет представлять собой идентификатор ближайшего центроида, значение value пикселя остается неизменным.

Выходные данные функции Map записываются в файловую систему HDFS. Между стадией Mapper и Reduce промежуточные данные сортируются и тасуются. Входными данными Reduce-ов будут выходные данные Mapper-ов.

Функция Reduce содержит все пары ключ/значение, которые получены от функции Map. Для всех пар ключ/значение, имеющих один и тот же ключ, их значения сохраняются в итераторе. Reduce функция вычисляет средние значения, которые имеют один и тот же ключ.Метод, который суммирует все значения, а затем делит на количество пикселей, может привести к переполнению в условиях массовых вычислений. Поэтому принимается стратегия из [8], которая вычисляет новое среднее значение по формуле (1).

Параллельный алгоритм кластеризации с использованием комбинаторов. Согласно алгоритму 1 выходные данные функции Map записываются на диск, и функция Reduceсчитывает выходные данные Mapper-ов. Между стадией Mapи Reduceданные сортируются и тасуются. С увеличением объема обрабатываемых данных время, затрачиваемое на сортировку и тасование, сильно растет. В данной работе предлагается модификация алгоритма 1 с использованием комбинаторов ([10], [12]), с помощью которых можно уменьшить объемы данных, которые выдает Mapperв качестве выходных данных, а Reducer соответственно считывает. Для данного алгоритма кластеризации предлагается создать комбинатор, который считывает выходные данные Mapper-а, и вычисляет новые локальные центроиды для каждого Mapper. Reducer считывает выходные данные Mapper, которые представляют собой идентификаторы новых локальных центроидов и их значения. Затем в Reducer-е вычисляются новые глобальные центроиды.

Алгоритм 2:

Map:

Входныеданные: (key, set<pair <pixel, set <pixel>>>).

Выходныеданные: (centroid_id, pixel).

1. Считать значения текущих центроидов.

2. Для каждого пикселя  найти ближайший центроид.

3. Назначить пиксель соответствующему  кластеру.

Combiner:

1. Считать пиксели i-ого центроида (i=1, …, k).

2. Вычислить новый локальный  i-ый центроид (i=1, …, k).

Reduce:

Входныеданные: (centroid_id, set <new_local_centriods>).

Выходныеданные: (new_centroid, pixels).

1. Считать значения локальных центроидов.

2. Вычислить новый глобальный центроид.

Схема работы итерационного алгоритма кластеризации с комбинатором показана на рис. 2.

Рисунок 2.Схема итерационного алгоритма кластеризации с комбинатором

 

Данный алгоритм был реализован на платформе Hadoop 2.0, результаты представлены в [14]-[15]. Ниже приведен фрагмент программного кода реализации функции комбинатора (рис. 3).

 

Рисунок 3. Функция комбинатора алгоритма кластеризации ISODATA

 

Отличительной особенностью алгоритма ISODATA является наличие эвристических процедур, посредством которых можно управлять количеством кластеров: в случае близости значений двух кластерных центров, эти кластеры можно объединять в один; в случае наличия большого количества элементов, относящихся к одному кластеру, данный кластер может быть поделен на два подкластера. На рис. 4 приведен код процедуры слияния кластеров для алгоритма ISODATA, реализованного с использованием MapReduce.

Рисунок 4. Функция слияния кластеров алгоритма кластеризации ISODATA

 

Управление данными. Данные, которые подвергаются кластеризации, не изменяются во время выполнения. В классической схеме итерационного процесса по алгоритму 1 все данные должны проходить стадию тасования (shuffle). В подходе, предлагаемом авторами, согласно [16] предлагается разделять данные на два вида: статические данные и данные состояния. Данные состояния обновляются после каждой итерации. Для алгоритма кластеризации статическими данными являются значения пикселей и данными состояния являются значения локальных центроидов, которые пересчитываются на каждой итерации по алгоритму 2. На рис. 5 показан поток данных для итерационного метода кластеризации. Статические данные считываются Mapper-ом из распределенной файловой системы HDFSтолько при первой итерации, затем после вычисления статические данные сохраняются в локальной файловой системе. Вычисленные значения локальных центроидов в качестве выходных данных Mapper-а подаются в качестве входных данных Reducer-ам. Таким образом, только данные состояния подвергаются тасованию на стадии shuffle.