Возможности кластеризации сложной графической информации в соответствии с топологическими свойствами фазового пространства динамической системы распознавания образов

УДК 004.93’14

М. И. Бояркин, И. А. Данилушкин, С. А. Колпащиков, А. А. Миронов, А. С. Рязанов,

А. А. Юдашкин

ВОЗМОЖНОСТИ КЛАСТЕРИЗАЦИИ СЛОЖНОЙ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ В СООТВЕТСТВИИ С ТОПОЛОГИЧЕСКИМИ СВОЙСТВАМИ ФАЗОВОГО ПРОСТРАНСТВА ДИНАМИЧЕСКОЙ СИСТЕМЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

Описываются практические возможности группировки многомерных данных, используемых в задачах динамического распознавания образов, по признаку их контекстной принадлежности областям притяжения аттракторов системы. Критерии принадлежности вводятся на базе евклидового определения расстояния в подпространстве с неортонормированным базисом.

Задачи кластеризации данных являются достаточно распространёнными в прикладной математике и обработке информации. Кластеризация позволяет осуществить классификацию данных в соответствии с их сущностью, то есть предоставить полный анализ информации вне зависимости от субъективно вводимых критериев. Как известно, кластеризация является достаточно сложной задачей даже для данных небольшой размерности. В задачах распознавания образов размерность данных чрезвычайно высока, в частности, вследствие необходимости работы с растровыми изображениями. В настоящее время существует ряд методик, наиболее популярных в качестве основы распознавания образов. К ним относятся искусственные нейронные сети, SVM и байесовские алгоритмы. Несмотря на относительно успешные применения указанных методик для решения частных задач, до сих пор не удавалось создать эффективной модели, позволяющей накапливать и классифицировать информацию о распознаваемых изображениях аналогично тому, как это делает человек, самостоятельно обучаясь на примерах из окружающей среды и не смешивая их. Основной проблемой здесь является необходимость либо мириться с существенной неопределённостью схем «без учителя», либо пытаться обойти ограничения субъективно вводимых критериев в схемах обучения «с учителем». В данном сообщении рассматривается новая возможность инкрементального накопления необходимой информации для формирования отдельных кластеров, отражающих различный смысл входных данных, для распознавания лиц людей в рассматриваемом случае.

В работе в качестве базовой схемы распознавания используется самоорганизующаяся нейронная сеть Хакена, предложенная в работе [1] и в дальнейшем развитая в [2, 3]. Одно из приложений данной модели рассмотрено в работе [4].

Предъявляемый к распознаванию образ q(0) является вектором, состоящим из N вещественных чисел. В модели имеется М образов-прототипов V{ (г = 1,2,..., М), имеющих такую же структуру. В процессе распознавания образ может быть представлен в виде линейной комбинации запомненных образов Vг- с коэффициентами мод йг и некоторого остатка

М

q (г ) = £ йг (г )v г + £(г). г=1

Данное представление распознаваемого образа позволяет свести распознавание к конкуренции мод, значения которых изменяются во времени, и рассматривать задачу не в фазовом пространстве размерности N, ав пространстве мод размерности М.

После предъявления системе образа, она со временем эволюционирует в одно из устойчивых состояний — узлов в фазовом пространстве мод, соответствующее одному из запомненных образов системы в соответствии с динамикой системы дифференциальных уравнений

М

М

и=1

М

у=1

М

к

к=г

где В, С, Хг — в общем случае неотрицательные настраиваемые параметры; начальные условия определяются следующим образом:

с

Здесь Л = в-1, в = УУ; У — матрица NхМ, составленная из набора векторов-столбцов {V1, V2,..., Vп}.

К сожалению, на практике приходится иметь дело с наборами изображений, представляющих один и тот же объект, но отличающихся друг от друга достаточно существенно для того, чтобы система (1) допустила ошибку. Ликвидация этого недостатка в приложениях, связанных с обработкой больших объёмов информации и их индексации, основана на формировании кластеров [5] из изображений одного и того же объекта и конкуренции между кластерами. Отнесение объекта к кластеру должно происходить с помощью естественного механизма, связанного с топологией пространства, натянутого на векторы образов в ситуации, когда эти векторы не образуют базиса и при этом число их растёт.

В данной работе кластер — это совокупность образов C = [c\, c2,cn}, объединённая по субъективному признаку их визуального сходства. Образы, как и выше, представлены вещественнозначными векторами из N компонент. Учитывая свойства евклидовой метрики, считаем, что чем дальше образы друг от друга в пространстве R, тем они менее похожи визуально. Аналогично методу модифицированного правила Хебба, ранее применявшемся для повышения качества запоминания образов в модели Хопфилда [6], используем разложение некоторого образа q на уже известную системе часть (образ «Да») и новую составляющую (образ «Нет») в виде q = q у + qN. Образ «Да» вектора q по отношению к набору векторов {v i, v2,..., v n} — это результат разложения вектора q по набору векторов {vi, v2,vn}, как по базису, вычисляемый по формуле

qY (q, V) = VG-iV'q.

Так как набор векторов {vi, v2,vn} в общем случае не является базисом в пространстве векторного представления образов, то q не совпадает с образом «Да».

Образ «Нет» вектора q по отношению к набору векторов {vi, v2,..., vn} — это вектор, равный разности между q и «Да», то есть степень «новизны» q по отношению к введённому набору, и определяемый из формулы

q n (q ,V ) = q - q y (q ,V ) = q - VG-1V ' q.

В зависимости от образов «Да» и «Нет», получившихся в результате такого разложения вектора, представляющего q, принимается решение о включении образа q в тот или иной кластер Ci. Данная процедура является одним из этапов работы описываемой модели кластеризации и называется первичной кластеризацией. Подгруппа образов, наиболее хорошо линейно аппроксимирующая свойства кластера, в большинстве случаев достаточна для описанной выше процедуры в качестве набора {vi, v2,..., vn}. Данная подгруппа называется ядром кластера. Формирование ядра кластера и последующая корректировка его формы называется рекластеризацией.

Для упрощения работы модели кластеризации матрица G может быть сформирована на основе инкрементально вычисленных образов V¡nk при помощи процедуры ортогонализации Грамма—Шмидта для исходной упорядоченной последовательности векторов {vi, v2,..., vn}:

V ink(V) = Il v i qN ( v 2, v i) qN (v3, ||v i qN (v2, v i) ||) ... qN (v n, ||v i qN (v2, v i) ... qN (v n-i,...)||)||.

Легко убедится в том, что получающаяся матрица G становится диагональной, что существенно облегчает вычисление обратной матрицы.

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

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

Работа выполнена в рамках гранта Президента РФ для государственной поддержки молодых российских учёных МД-9422.2006.9 и гранта РФФИ по проекту 07-08-00401-а.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Haken, H. Synergetic computers and cognition: A top-down approach to neural nets [Text]/ H. Haken. — SpringerVerlag New York, Inc., 1991. — 225 p. — ISBN 0-387-53030-4.

2. Yudashkin, A. A topological approach to the pattern classification in neural networks [Text] / A. Yudashkin // Proc.

of 1996 IEEE Int. Conf. on Neural Networks (Washington, DC, USA, 3-6 June 1996). — Washington, 1996. —Vol. 3. —

P. 1484-1487.

М. И. Бояркин, И. А. Данилушкин, С. А. Колпащиков, А. А. Миронов, А. С. Рязанов,

А. А. Юдашкин

3. Юдашкин, А. А. Бифуркации стационарных решений в синергетической нейронной сети и управление распознаванием образов [Текст] / А. А. Юдашкин // Автоматика и телемеханика. — 1996. — № 11. — С. 139-147.

4. Mobile Biometric Person Identification System on the Basis of Pattern Recognition Software and GSM Cellular Networks [Text] / A. Yudashkin, I. Danilushkin, S. Kolpaschikov and other / eAdoption and the Knowledge Economy: Issues, Applications, Case Studies (Proc. of eChallenges-2004, Vienna, Austria, 2004). — Amsterdam, Berlin, Oxford, Tokyo, Washington: IOS Press, 2004. — Part 1. — P. 102-108.

5. Frigui, H. Clustering and aggregation of relational data with applications to image database categorization [Text] / H. Frigui, C. Hwang, F. Chung—Hoon Rhee // Pattern Recognition. — 2007. — Vol. 40, Issue 11. — P. 3053-3068.

6. Лоскутов, А.Ю. Введение в синергетику [Текст]: Учеб. рук. / А. Ю. Лоскутов, А. С. Михайлов. — М.: Наука, 1990. — 272 с. — ISBN 5-02-014475-4.

Самарский государственный технический университет, г. Самара

Поступила 30.05.2007