RECOGNITION OF HYPERSPECTRAL IMAGES WITH USE OF CLUSTER ENSEMBLE AND SEMISUPERVISED LEARNING

Abstract

We suggest a method for hyperspectral image analysis on the basis of semi-supervised learning. The main idea is to divide the process of training of a classifier into two stages. First of all, with usage of cluster ensemble algorithms, variants of image segmentation are obtained. On their basis, the averaged co-association matrix is calculated. On the second stage, a classifier is constructed on labeled pixels using similarity based learning algorithms with the given matrix as input. An example of the application of the method for analysis of hyperspectral images is given. It is shown that the suggested algorithm is more robust to noise than the standard support vector machine method.

Keywords

• cluster ensemble
• learning by similarity
• semi-supervised learning
• hyperspectral image

-

ядра (kernel based) [7], например, метод опорных векторов (Support Vector Machine), ядерный дискриминант Фишера (Kernel Fisher Discriminant), ядерная версия алгоритма ближайших соседей (Kernel kNN).

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

Постановка задачи полуконтролируемого обучения. Пусть имеется генеральная совокупность объектов распознавания X и конечное множество меток классов Y . Все объекты описываются числовыми признаками.

При заданных признаках f1 fm вектор x  ( f1(x) fm (x)) называется признаковым описанием объекта x  X . Далее мы отождествляем объект и его признаковое описание. В задаче полуконтролируемого обучения на вход подается выборка X N = { x1 xN } объектов из X . В этой выборке присутствуют объекты двух типов: Xc  {x1 xk } - размеченные объекты с заданными классами, которым они принадлежат: Yc  {y1 yk }; Xu  {xk1 xN } - неразмеченные объекты.

В различных вариантах постановки задачи требуется либо провести т.н. индуктивное обучение - построить алгоритм классификации a  X  Y , который будет, минимизируя вероятность ошибки, сопоставлять классы объектам их X u , а также новым объектам Xtest , которые были недоступны на момент построения алгоритма, либо требуется провести трансдуктивное обучение - получить метки классов только для объектов из X u с минимальной ошибкой. В данной работе рассматривается второй вариант постановки задачи.

Коллективные решения в кластерном анализе. Задачей кластерного анализа является разбиение выборки на непересекающиеся подмножества, называемые кластерами, так чтобы каждый кластер представлял группу похожих объектов, а объекты в разных кластерах существенно различались. В настоящее время в кластерном анализе широко применяется коллективный подход, который позволяет получать более устойчивые группировочные решения. Существует несколько вариантов получения коллективного решения задачи кластерного анализа: использование т.н. матрицы усредненного попарного сходства, максимизация степени согласованности решений (с помощью исправленного индекса Ранда, нормализованной взаимной информации и т.д.), применение теоретико-графовых методов. В предлагаемом в данной работе алгоритме используется матрица усредненного попарного сходства. Для построения матрицы кластеризация всех поданных на вход объектов X коллективом различных алгоритмов 1 M кластерного анализа. Каждый алгоритм дает Lm вариантов разбиения, m  1 M . По результатам работы алгоритмов составляется матрица H усредненных попарных различий объектов из X . Элементы матрицы равны:

M 1 Lm h(i j)    hlm (i j) m1 m Lm l1 ( 1 ) где i j {1 N} - номера объектов (i  j)  m  0 - заданные веса такие, что M  m  1, hlm (i j)  0 , если пара (i j) принадлежит разным кластерам в l -ом варианте разбиm1 ния оптимальных весов, минимизирующих оценку погрешности классификации был предложен в работе [8].

Ядерные методы классификации. Для решения задачи классификации с учителем широко распространены ядерные методы, в основе которых лежит понятие ядра (kernel). Подбор ядра определяет переход в «спрямляющее» пространство и позволяет применять линейные алгоритмы классификации к линейно неразделимой выборке [7].

В ядерных методах классификации широко известна теорема Мерсера [9], которая устанавливает необходимое и достаточное условие на то, чтобы функция была ядром: Теорема (Мерсер). Функция K(x, x) является ядром тогда и только тогда, когда она симметрична, K(x, x)  K(x, x) , и неотрицательно определена: для любой конечной выборки X p  (x1,..., xp ) из X матрица K ‖K (xi , x j )‖ размера p  p неотрицательно определена: zT Kz  0 для любого z  p .

Идея алгоритма состоит в построении матрицы похожести ( 1 ) для всех объектов из подаваемой на вход выборки X : чем чаще пара объектов попадает в один и тот же кластер, тем более похожими друг на друга мы их будем считать. Нами доказано следующее Утверждение. Функция ( 1 ) удовлетворяет условиям теоремы Мерсера.

Таким образом, функция H может быть использована в ядерных методах классификации, в частности, в методе опорных векторов SVM.

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

Вход: объекты Xc с заданными классами Yc и объекты Xu , число алгоритмов кластеризации M , число кластеризаций Lm каждым алгоритмом m , m  1,..., M .

Выход: классы объектов Xu . 2. Вычислить матрицу H на X c  X u по формуле ( 1 ). 3. Обучить SVM на размеченных данных Xc , используя матрицу H в качестве ядра. 4. С помощью SVM предсказать классы для неразмеченных объектов Xu .

Конец алгоритма.

Отметим, что в предложенном алгоритме не требуется хранить в памяти матрицу H размера N  N целиком: достаточно хранить матрицу кластеризаций размера N  L , где

M L   Lm , в этом случае матрицу H можно вычислять динамически. В прикладных задачах l1 как правило L  N , например, при работе с пикселями изображений.

Анализ гиперспектрального изображения. Для экспериментального исследования алгоритма был проведен эксперимент с изображением Pavia University scene размером 610 на 340 пикселей, которое содержит 103 спектральных канала. Пространственное разрешение снимка составляет 1.3 м. На рисунке 1а) показан RGB-композит изображения (каналы 40, 50 и 70), а на рисунке 1б) приведено эталонное разбиение изображения на тематические классы.

Отметим, что на снимке имеются неразмеченные пиксели, которые не отнесены ни к одному из девяти классов. Данные пиксели были исключены из рассмотрения при анализе.

При экспериментальном исследовании алгоритма 1% пикселей, отобранных случайным образом для каждого класса, составили размеченную выборку; оставшиеся были включены в неразмеченную часть. Для изучения влияния шума на качество работы алгоритма, случайно отобранные r % значений спектральных яркостей пикселей в разных каналах подвергались искажающему воздействию: соответствующее значение x заменялось величиной, выбранной случайным образом из интервала [x(1 p), x(1 p)] , где r, p - заданные параметры. Зашумленная таблица данных, содержащая значения спектральных яркостей пикселей по всем каналам, подавалась на вход алгоритма CASVM, а котором в качестве базового алгоритма для построения кластерного ансамбля был выбран алгоритм K-средних. Различные варианты разбиения получались варьированием числа кластеров в интервале [30,30  L] , где L было равно 120. Кроме того, для построения каждого варианта решения случайным образом выбирались каналы, число которых было задано двум. Для ускорения работы алгоритма K-средних и получения более разнообразных вариантов группировки, число его итераций было ограничено значением 1.

а б Рис. 1. Гиперспектральное изображение Pavia University scene (RGB композит) (а) и размеченные данные (б).

Поскольку предложенный алгоритм реализует идею обучения метрике расстояния (distance metric learning), было бы естественно провести его сравнение с аналогичным алгоритмом (нашем случае - методом опорных векторов SVM), использующим стандартную евклидову метрику, в аналогичных условиях (выбирались параметры алгоритма, рекомендуемые по умолчанию в среде Матлаб). В таблице показаны значения точности классификации неразмеченных пикселей изображения Pavia University scene для некоторых значений параметров зашумленности. Время работы алгоритма составило около 2 мин на двухъядерном процессоре Intel Core i5 с тактовой частотой 2.8 ГГц и объемом оперативной памяти 4 Гбайт. Как видно из таблицы, алгоритм CASVM обладает большей устойчивостью к шуму, чем алгоритм SVM. Точность алгоритмов CASVM и SVM при различных значениях параметров шума. Параметры шума r, p 0%, 0 10%, 0.1 20%, 0.2 30%, 0.3

CASVM 0.82 0.80 0.78 0.77

SVM 0.83 0.75 0.66 0.64 Заключение. В работе рассмотрен один из вариантов постановки задачи распознавания образов – задача полуконтролируемого обучения. Был разработан алгоритм CASVM для решения этой задачи. Он основывается на сочетании методов коллективного кластерного анализа и ядерных методов классификации. Проведено экспериментальное исследование предложенного алгоритма на гиперспектральном изображении. Показано, что алгоритм CASVM более устойчив к шуму, чем стандартный метод опорных векторов SVM.

References

1. Провести кластеризацию объектов X c  X u алгоритмами 1,. .,  M кластерного анализа , Бондур В.Г . Современные подходы к обработке больших потоков гиперспектральной и многос- пектральной аэрокосмической информации // Исследование Земли из космоса . 2014. N 1.

of Wisconsin, Madison, 2008 ), no. 1530 .

Wang , F. Label propagation through linear neighborhoods / Wang , F. , Zhang , C. // ICML06, 23rd International Conference on Machine Learning. Pittsburgh, USA.

Wang L. , Hao S. , Wang Q. , Wang Y . Semi-supervised classification for hyperspectral imagery based on spatial-spectral Label Propagation // ISPRS Journal of Photogrammetry and Remote Sensing . 2014 .

Vol. 97 . P. 123 - 137 .

Berikov V. , Pestunov I. Ensemble clustering based on weighted co-association matrices: Error bound and convergence properties // Pattern Recognition. 2017 . Vol. 63 . P. 427 - 436 .

Shawe-Taylor J ., Cristianini N. Kernel Methods for Pattern Analysis . Cambridge University Press, 2004 .

Berikov V.B. Weighted ensemble of algorithms for complex data clustering // Pattern Recognition Letters . 2014 . Vol. 38 . P. 99 - 106 .

Mercer J. Functions of positive and negative type and their connection with the theory of integral equations / Philos . Trans. Roy. Soc. London . 1909 .