The system of fuzzy classification of Earth remote sensing (ERS) data is discussed. The system involves fuzzy automatic classification (clustering) and fuzzy supervised classification. The fuzzy clustering subsystem consists of the next algorithms of fuzzy clustering: fuzzy C-means (FCM), fuzzy Cmeans with regularization (PCM) and extended C-means and Gustafson-Kessel algorithms. The fuzzy supervised classification subsystem involves the Wang's method and the explicit fuzzy supervised classification method.
Бучнев А.А., Пяткин В.П.
Институт вычислительной математики и математической геофизики СО РАН Рассматривается система нечеткой классификации данных дистанционного зондирования Земли (ДЗЗ). Система включает нечеткую автоматическую классификацию (кластеризацию) и нечеткую контролируемую классификацию. Подсистема нечеткой кластеризации включает реализацию следующих алгоритмов: алгоритма С-средних (FCM), алгоритма С-средних с регуляризацией (PCM) и расширенных алгоритмов С-средних и Густафсона-Кесселя. Подсистема нечеткой контролируемой классификации включает метод Вонга и метод явной нечеткой контролируемой классификации.
Ключевые слова: дистанционное зондирование, кластерный анализ, жесткая кластеризация, нечеткая кластеризация, вероятностная нечеткая кластеризация, возможностная нечеткая кластеризация, контролируемая классификация, нечеткая контролируемая классификация.
Введение. Характерной особенностью данных ДЗЗ является “загрязнение” выборок смешанными векторами признаков, т.е. векторами, которые образуются при попадании в элемент разрешения съемочной системы нескольких природных объектов. Это обстоятельство является одним из источников ошибок при построении карты классификации [1]. Большинство алгоритмов классификации для отнесения векторов признаков кластерам (классам) вычисляют для каждого вектора значения подходящей функции «правдоподобия». В случае зачисления вектора признаков в кластер (класс) по максимальному значению функции правдоподобия получается так называемая жесткая классификация.
Альтернативой жесткой разделяющей классификации является мягкая или нечеткая классификация, разрешающая векторам измерений принадлежать всем кластерам (классам) с коэффициентом членства uij [0,1] , определяющим степень принадлежности j-го вектора iму кластеру (классу):
C uij 1, j i1
(1)
L 0 uij L , i ,
j1 определяя этими соотношениями нечеткую классификацию. Здесь C – число кластеров (классов), L – количество векторов признаков.
Нечеткая кластеризация. В недавнее время нами в состав подсистемы кластеризации программного комплекса по обработке данных ДЗЗ была включена реализация широко используемого алгоритма нечеткой кластеризации, известного как метод C-средних (Fuzzy Cmeans, FCM) [2]. Это итерационный алгоритм, который используется для разделения смешанных векторов признаков в данных ДДЗ. Идея метода заключается в описании сходства вектора с каждым кластером с помощью функции уровней принадлежности, принимающей значения от нуля до единицы. Значения функции, близкие к единице, означают высокую степень сходства вектора с кластером. Здесь сумма значений функции уровней принадлежности для каждого пиксела равняется единице. Параметрами соответствующей процедуры (кроме числа кластеров) являются тип метрики и вариант выбора начальных центров кластеров. Дополнительным параметром является показатель нечеткости, значения которого для ДДЗ предлагается брать близкими к двум (см., например, [1]).
Вторым алгоритмом нечеткой кластеризации, включенным в состав программного комплекса по обработке данных ДЗЗ, является алгоритм нечеткой кластеризации с регуляризацией – так называемый алгоритм Possibilistic C-means, PCM. Принципиальное отличие алгоритма PCM от алгоритма FCM состоит в снятии ограничения (1) на элементы матрицы принадлежности вектора признаков кластерам: в алгоритме FCM для каждого вектора признаков сумма элементов матрицы принадлежности по всем кластерам должна равняться единице (вероятностное – probabilistic – свойство алгоритма FCM). Таким образом, в алгоритме FCM членство вектора в кластере является относительным, т.к. оно зависит от членства этого вектора во всех других кластерах, в то время как в алгоритме PCM значение членства вектора в кластере является абсолютным (т.е. не зависящим от значений членства этого вектора в других кластерах) и может интерпретироваться в терминах типичности вектора. Алгоритм PCM пытается найти моды в наборе данных, так как каждый полученный кластер соответствует плотной области в этом наборе. В процессе выполнения итераций алгоритма прототипы кластеров последовательно перемещаются в плотные области в пространстве признаков.
PCM алгоритм является робастным методом кластеризации, который может быть использован для обнаружения плотных областей в данных. Степень членства вектора признаков в кластере определяется двумя величинами: расстоянием вектора до прототипа кластера и параметром K, называемым ссылочным расстоянием кластера. Значение этого параметра индивидуально для каждого кластера и зависит от среднего размера кластера.
Нижеследующие рисунки демонстрируют результаты работы алгоритмов С-средних. На рис. 1 представлен фрагмент снимка ИСЗ SPOT-4, полученного 04.05.2011 г., с паводковой ситуацией в районе Камня-на-Оби (снимок предоставлен Сибирским центром НИЦ «Планета»). На рис. 2 приведен результат обработки алгоритмом FCM. Фрагменты исходного изображения, являющиеся «шумом» по отношению к области интереса, исключены из процесса обработки. На рис. 3 и 4 представлены результаты обработки алгоритмом PCM со значениями ссылочных расстояний K=1 и K=0.8 соответственно. Выделялось 10 кластеров, выполнялось 50 итераций алгоритмов.
Авторы алгоритма [3] отмечают, что для получения качественных результатов кластеризации требуется хорошая инициализация ссылочных расстояний кластеров. Следуя их рекомендациям, в качестве начального приближения матрицы степеней членства векторов признаков в кластерах используется результат выполнения алгоритма нечеткой кластеризации методом FCM. Т.е. необходимым условием выполнения алгоритма PCM для какого-либо набора данных является предварительное выполнение алгоритма FCM для этого набора данных. Рис. 1. Исходное изображение.
Рис. 2. Кластеризация методом FCM. Рис. 3. Кластеризация методом PCM с K=1.
Дальнейшим развитием системы нечеткой кластеризации данных ДЗЗ является
реализация нечеткой кластеризации расширенными алгоритмами С-средних (Fuzzy C-means – FCM) и
Густафсона-Кесселя (Gustafson-Kessel – GK) [
Расширения FCM и GK алгоритмов (получаются E-FCM и E-GK алгоритмы) состоят в следующем: 1. В качестве прототипов кластеров используются объемные прототипы (volume prototypes). В частности, если в алгоритме E-FCM используется евклидова метрика, тогда таким прототипом будет гипершар. В алгоритме E-GK объемным прототипом кластера является гиперэллипсоид. Размеры объемных прототипов определяются на основе объемов кластеров. Такие прототипы менее чувствительны к отклонениям в распределении данных. 2. Вводится понятие «сходства» (similarity) кластеров. Начиная с заведомо большего числа кластеров, кластеры, степень сходства которых превышает заданный порог, объединяются в итерационном процессе кластеризации для того, чтобы получить подходящее разбиение данных.
Заметим, что в качестве начального разбиения векторов признаков по нечетким кластерам используются выходные данные алгоритма С-средних.
Основная часть работы алгоритмов нечеткой кластеризации состоит в итерационном перестроении матрицы уровней принадлежности векторов признаков кластерам и пересчете центров кластеров. Алгоритмы заканчивают работу при выполнении заданного числа итераций либо при достижении матрицы уровней принадлежности состояния стабильности, т.е. состояния, при котором норма разности матриц в двух последовательных итерациях не превосходит заданного порога. Эта работа требует больших временн’ых затрат при ее последовательном выполнении, особенно в случае, когда показатель нечеткости неравен двум, в связи с чем реализованы параллельные версии алгоритмов. Параллельная реализация алгоритмов осуществляется средствами ОС Windows в рамках одного процесса путем запуска нескольких параллельных потоков. Количество запускаемых потоков равно количеству логических процессоров компьютера. Каждый поток перестраивает соответствующую часть матрицы уровней принадлежности. Необходимая при работе параллельных потоков синхронизация реализуется с нения параллельной процедуры нечеткой кластеризации методом FCM набора векторов признаков рис. 1. Приводятся результаты измерений времени (в секундах) для значений параметра нечеткости m=2 и m=2.2. Измерения проводились под управлением Windows-10 на аппаратной платформе i3-2100 с четырьмя логическими процессорами. Выполнялось 50 итераций. Аналогичные данные для алгоритма PCM приведены в таблице 2.
Нечеткая контролируемая классификация. Вонг [1] изменил традиционный метод максимального правдоподобия путем предварительного вычисления нечеткой ковариационной матрицы. Затем степени нечеткого членства векторов в классах вычисляются путем применения процедуры максимального правдоподобия к нечетким сигнатурам классов.
В общем случае алгоритм Вонга требует априорных знаний о членствах в классах векторов из обучающих выборок. Мы в своей реализации метода используем для этого выходные данные алгоритма нечеткой кластеризации [2].
Значение m m=2 m=2.2 Значение m m=2 m=2.2
1 76.18 для класса c, c=1,…,C, в спектральной полосе b, а стандартное отклонение ∗, является модулированным значением оценки стандартного отклонения , . Значение коэффициента модуляции определяется на основе ожидаемого размера класса в данной полосе. Таким образом, на первом этапе с каждым вектором признаков связывается матрица F, число столбцов которой равно числу классов, а число строк равно размерности вектора признаков: , ( ) , ( ) ⋮ ⋮ ⋯ , ( ) ⋯ , ( ) ⋯ ⋮
. ( , ( ) , ( ) ⋯ , ( )) Эти матрицы являются входными данными ко второму этапу. На втором этапе к полученным данным применяется правило нечеткого вывода для получения, после нормирования, нечеткой классификации набора векторов признаков. В качестве правила нечеткого вывода используется одно из двух правил Мамдани: правило MIN для получения минимального значения в списке аргументов и правило PRODUCT для получения произведения значений аргументов. Эти правила применяются к столбцам матриц F. Наконец третий этап алгоритма, используя правило MAX для выбора среди смешанных в векторе признаков тематических классов класса с максимальным значением членства, переводит нечеткую классификацию в жесткую (defuzzification step).
Заключение. Включение алгоритмов нечеткой классификации в состав системы тематической обработки программного комплекса по обработке данных ДЗЗ позволяет построить карту классификации, более полно соответствующую истинным тематическим классам в наборе данных.
Работа выполнена частично при финансовой поддержке Российского фонда фундаментальных исследований (проект № 16-07-00066) и Программы I.33П Президиума РАН (проект № 0315-2015-0012).