Smoothing technique for adaptive meshes produced by self organizingmaps .pdf Построение адаптивных сеток является одной из актуальных областей научных исследований, которая привлекает в настоящее время многих исследователей. Адаптивные сетки, являясь дискретной моделью пространственной области, получили важнейшие применения при решении сложных задач численного моделирования [1]. Кроме того, они широко используются при обработке изображений, визуализации данных, в графических приложениях и т.д. [2].Использование адаптивных сеток в задачах численного моделирования позволяет повысить точность приближенного решения задачи без существенного увеличения числа узлов. Среди всех типов сеток можно выделить важный класс, в котором адаптивные сетки получаются в результате отображения некоторой вычислительной области на физическую, переводящего зафиксированную, обычно равномерную, сетку в адаптивную с заданным распределением плотности. К методам построения сеток этого класса относятся такие традиционные методы [3], как метод эквираспределения, метод Томпсона, эллиптический метод и т.д. Для получения качественных адаптивных сеток все эти методы, а также алгебраические методы и методы конформных отображений [4], в конечном счете, требуют решения сложных систем нелинейных дифференциальных уравнений (ДУ) с частными производными. Необходимость решения ДУ накладывает ряд ограничений на возможности этих методов, к числу которых относятся жесткий контроль над способами задания физической области и функции плотности сетки, контроль над свойствами граничных и начальных данных, проблемы при попытках автоматизации работы с этими методами и их эффективного распараллеливания.Одним из альтернативных и многообещающих подходов [5] к построению адаптивных сеток (не только рассматриваемого класса) является использование стохастических нейросетевых моделей самоорганизации, таких как самоорганизующиеся карты Кохонена (Self-Organizing Maps, SOM), растущий нейронный газ (Growing Neural Gas, GNG), растущие клеточные структуры (Growing Cell Structures, GCS) [6]. Принципы самоорганизации, заложенные в этих моделях, позволяют строить сетки с произвольными начальными данными и автоматической расстановкой узлов по границе физической области; стохастическая природа моделей снимает требования с функции плотности сетки, так как плотность контро-лируется вероятностным распределением; внутренний параллелизм, присущий нейросетевым моделям, делает возможным эффективно распараллеливать алгоритмы построения адаптивных сеток [5].Однако стохастический подход имеет и свои проблемы, к числу которых, например, относится недостаточная гладкость результирующих сеток. Целью данной работы является разработка методики сглаживания адаптивных сеток, получаемых с помощью нейросетевых моделей. Эта методика иллюстрируется на примере построения адаптивных сеток упомянутого выше класса с помощью модели SOM.Было установлено, что гладкость сеток напрямую зависит от радиуса обучения нейронной сети SOM. Чем больше радиус, тем выше гладкость адаптивной сетки. Но при увеличении радиуса обучения возникает граничный эффект, который проявляется в том, что сетка перестает аппроксимировать границы физической области, сосредотачиваясь вблизи центра области. Причиной такого эффекта является несимметричность расположения узлов сетки, находящихся в окрестности граничных узлов. Таким образом, основной задачей при достижении требуемой гладкости сеток является преодоление граничного эффекта за счет балансирования упомянутой несимметричности, чтобы обеспечить возможность использования большого радиуса обучения.Граничный эффект - это известная проблема нейросетевой модели SOM. Несколько подходов по его преодолению было предложено ранее, к их числу, например, относятся правило весов Кохонена [6] и реализация модели SOM на сферической решетке Риттера [8]. Однако первый подход не учитывает размер радиуса обучения, который напрямую влияет на граничный эффект и является ключевым параметром при сглаживании сетки. Второй подход неприменим при построении адаптивных сеток рассматриваемого класса. так как требует изменения структуры зафиксированной сетки. Методика, предлагаемая в данной статье, не требует изменения структуры зафиксированной сетки и воздействует только на алгоритм обучения для модели SOM, сохраняя все перечисленные ее свойства. Автор надеется, что предложенная в данной статье методика окажется полезной не только при построении адаптивных сеток, но и в других многочисленных применениях модели SOM, таких, как обработка изображений, сжатие данных, реконструкция поверхностей и др.1. Использование модели SOM для построения адаптивных сетокПусть в евклидовом пространстве с системой координат (x1,..., xn) задана физическая область G, на которой требуется построить адаптивную сетку. Пусть Q - это вычислительная область в пространстве rQ , k < n , с системой координат(q1qk). В вычислительной области Q зафиксирована некоторая сетка, множество узлов которой обозначается QN = {ql,..., qN}, где N - количество узлов сетки,q е Q, q = (?;,,q\), i = 1,...,N . В данной статье предполагается, что зафиксированная сетка является равномерной прямоугольной, что, вообще говоря, необязательно при построении сетки с использованием модели SOM. Пусть dg - это шаг зафиксированной сетки QN по горизонтальному и вертикальному направлениям. Требуемая плотность адаптивной сетки задается функцией плотности сеткиw: G -> R + .Согласно классической постановке задачи построения адаптивных сеток рассматриваемого класса, требуется найти отображение Q на G, которое переводит сетку QN, трансформируя ее, в искомую адаптивную сетку GN с заданной функцией плотности. При отображении граничные узлы сетки QN должны переводиться в граничные узлы сетки GN, распределенные по границе G. Пусть Nb - это число граничных узлов сетки, а - число внутренних узлов.Для использования нейросетевой модели SOM при построении адаптивных сеток нейроны ставятся в соответствие узлам сетки. При этом количество нейронов совпадает с числом узлов N, положения нейронов в нейронном слое модели SOM задаются координатами узлов qt зафиксированной сетки QN, а их веса соответствуют координатам x, искомой адаптивной сетки GN, которые требуется найти в процессе обучения SOM. Таким образом, нейрон в модели SOM рассматривается как пара et = (q;, x,). Каждые два нейрона e и e,, i, j = 1,...,N, в нейронном слоесвязаны латеральной связью, вес которой тем меньше, чем больше расстояние между этими нейронами || q, - q, ||. В качестве входных данных для модели SOM используются случайные точки области G, сгенерированные с заданным вероятностным распределением p(x). Это распределение пропорционально функции плотности сетки w(x) и имеет вид p(x) = w(x)/ J w(z)dz .GАлгоритм обучения нейронной сети SOM, предложенный Кохоненым [6], заключается в следующем. На каждой итерации t алгоритма обучения модели SOM, генерируется случайная точка y из области G, выбирается ближайший к ней узел сетки xm (t), и все нейроны корректируют свои веса в соответствии с формулойX (t +1) = х, (t) + 5(t)nqm (t, q )(y - x, (t)) ,(1)где 8(t) e [0,1] отвечает за шаг обучения, а т\Чш (Л 4i) е [0,1] задает вес латеральнойсвязи между нейронами em и e;. Эти две функции контролируют величины сдвигов узлов x, в области G по направлению к случайной точке y, существенно влияют на качество результирующих сеток и скорость процесса построения.Следуя [5], функция шага обучения в данной работе выбиралась в виде0 о Sit T)/TS(t) = t ' %(t), где %(t) = 1 - e ( ; и T - это максимальное количество итераций, которое фиксируется до начала итерационного процесса пропорционально N (например, T = 10N ). Пусть By (q) - это замкнутая окрестность точки q в вычислительной области радиуса у, т.е.B,f (q) = [р € RQ | d(р, q) r\qm (t, 9;) > s . Функция r\qm (t, 4t) удовлетворяет также следующим условиям:(1) если d(qm, q) = г (t), то y]qm (t, q) = s ;(2) rqm (t, q;) = rqi (t, qm), т.е. латеральная связь между qm и qt симметрична;(3) n?„(t' qm) = 1.Таким образом, на каждой итерации наибольшее приращение получают веса нейрона победителя, тогда как остальные нейроны меняют веса тем меньше, чем дальше они расположены от победителя в нейронном слое. Радиус обучения меняется в течение итерационного процесса по следующему правилу:rit) = r(T) + x(t)(r(1)0,05'/T - r(T)) t-°'25.Здесь r (1) и r (T) - начальный и конечный радиусы, r (1) > r (T).Как показано в [5], приведенный выше алгоритм обучения модели SOM в чистом виде неприменим для построения сеток. Для того чтобы получать приемлемые адаптивные сетки, в [5] предлагается композиционный алгоритм построения сеток, основанный на чередовании применения алгоритма SOM к граничным и внутренним узлам. В результате граничные узлы автоматически растягиваются по границе, а внутренние узлы, согласуясь с граничными, заполняют внутренность области. При использовании такой композиции можно не только исключить нарушения топологии сетки и значительно снизить количество узлов, вышедших за границу области в случае сложных невыпуклых областей, но и преодолеть граничный эффект при малом радиусе обучения. Так, в конце итерационного процесса рекомендуется использовать такие значения радиуса r(T) , чтобы окрестность Br(f)(qi) захватывала только ближайших соседей узла q,. Однако такой маленький радиус обучения ведет к негладким адаптивным сеткам, что может явиться причиной снижения точности последующих расчетов на этих сетках. Связь гладкости результирующих сеток, радиуса обучения и граничного эффекта подробно рассматривается в следующем пункте.2. Измерение гладкости и демонстрация граничного эффектаДля измерения гладкости четырехугольных адаптивных сеток можно рассматривать ломаные, являющиеся образом вертикальных и горизонтальных линий зафиксированной сетки QN при отображении, которое осуществляет SOM. Сегменты этих ломаных связывают соответствующие узлы сетки GN. В двумерном случае гладкость ломаной может быть измерена значениями синусов углов между сегментами вдоль ломаной. Чем меньше число перемен знаков и амплитуда этих синусов, тем ломаная является более гладкой. В трехмерном случае, поскольку сегменты ломаной у трехмерной сетки, как правило, не лежат в одной плоскости, удобно измерять абсолютное значение синусов без знака.Для демонстрации влияния радиуса обучения на гладкость сеток и на граничный эффект был поставлен следующий эксперимент. Сначала с помощью композиционного алгоритма была построена сетка с искусственно маленьким финальным радиусом обучения r(T) = 0,5dß (т.е. к концу итерационного процесса окрестность Br(t)(qm) даже не захватывала ближайших соседей). Далее, внутренние узлы сетки в течение некоторого количества итераций обрабатываются процедурой обучения SOM с постоянным коэффициентом обучения, в котором шаг был зафиксирован как 8 = 0,005, а радиус - в виде r(T) = 10dö. При этом граничные узлы не меняли свое положение, но имели право становиться победителями, чтобы обеспечить согласованность внутренних и граничных узлов (такой же механизм согласования используется и в композиционном алгоритме). Описанный эксперимент проводился в двумерном и трехмерном случаях.Сетки, построенные композиционным алгоритмом с маленьким радиусом (рис. 1, a и d), негладкие даже зрительно, и на графиках рис. 1, c и f серые линии показывают большие значения синусов с многочисленными переменами знаков вдоль одной из ломаных сетки. Гладкость обработанных сеток (рис. 1, b и e) намного лучше, что показывают графики. Однако полученные сетки неприменимы для вычислений из-за сильного граничного эффекта, проявившегося из-за большого радиуса обучения. Итак, главной задачей при получении достаточного уровня гладкости сеток является борьба с граничным эффектом.3. Балансировка граничного эффектаПосле работы композиционного алгоритма все узлы сетки распределены по физической области в соответствии с заданным распределением плотности. Следовательно, предполагается, что для этой сетки выполняется условие равноправия узлов [8]: каждый узел имеет одинаковые шансы стать победителем при случайно сгенерированной входной точке, и соответствующая вероятность равна В теории нейронных сетей, это условие играет роль критерия качества построенного моделью SOM отображения.Граничный эффект возникает из-за несимметричности латеральных связей у нейронов, которые расположены близко к границе вычислительной области. Пусть q, - это внутренний нейрон, для которого расстояние до границы вычислительной области больше радиуса обучения r. Структура сетки QN такова, что все нейроны q, из Br(q,) располагаются симметрично относительно qt. Согласно выбору коэффициента обучения, значения весов латеральных связей rq. (q;) также располагаютсясимметрично относительно q,. Если при этом учитывать условие равноправия узлов, то на нейрон q с одинаковой вероятностью может быть оказано воздействие любым другим нейроном q,. В физической области это означает, что узел x, имеет одинаковую вероятность сдвинуться симметрично во всех направлениях под влиянием нейронов из Br(q;). Так как s близко к нулю, то предполагается, что взаимное влияние между нейронами qt и q, g Br (qt) пренебрежительно мало.Если расстояние от q до границы вычислительной области меньше r, то в окрестности Br(q;) расположено недостаточно нейронов для симметрии. В этом случае большинство нейронов в Br(q;) заставляют узел x, двигаться в основном к центру физической области. Поэтому для балансировки асимметрии узел x, вынужден отодвигаться от границы G.Для оценки асимметрии предлагается рассмотреть следующую характеристику нейрона e :ai = Z Цд, (qi).(2)j£Br (q)Для каждого нейрона эта характеристика равна сумме весов латеральных связей со всеми другими узлами из окрестности Br(q;). Если qt расположен близко к границе Q, то в сумме недостаточно слагаемых. Поэтому а, убывает вблизи границы Q. На рис. 2. показан график величины а, в случае равномерной прямоугольной зафиксированной сетки.Все узлы, расположенные на расстоянии от границы, большем r, имеют равные значения характеристики а . Для балансировки граничного эффекта необходимо, чтобы эта характеристика была одинаковой для всех нейронов. Предлагается методика, которая позволяет использовать граничные узлы в качестве представителей недостающих нейронов за пределами вычислительной области Q.Можно представить, что с каждым граничным нейроном связано K виртуальных нейронов, расположенных за пределами вычислительной области. Эти виртуальные нейроны не существуют в алгоритме и только помогут понять идею, лежащую в основе предлагаемой методики. Точные положения виртуальных нейронов неизвестны. Известно только то, что расстояние между k-м виртуальным нейроном и соответствующим ему граничным нейроном с положением qm равно kdg,к = 1,...,K, где K = \г /dg 1 и \a~| = argmin(a < n) - это наименьшее целое число, которое больше a.Чтобы встроить виртуальные нейроны в процесс обучения, требуется ответить на следующие вопросы: (1) при каких условиях виртуальный нейрон может стать победителем? (2) чему равны веса латеральных связей между нейронами q;, i = 1,...,N , и виртуальными нейронами? (3) каковы направление и величина сдвигов узлов сетки в физической области, когда победителем является виртуальный нейрон?Ответ на вопрос (1). В случае наличия виртуальных нейронов, выбор победителя не может быть основан только на близости к случайной точке, так как за пределами физической области нет точек. Поэтому на каждой итерации, во-первых, необходимо решить, из какого типа нейронов будет выбираться победитель. Так как предполагается, что выполняется условие равноправия нейронов, виртуальные нейроны имеют ту же вероятность стать победителем, что и все остальные нейроны. Вероятность того, что станет победителем виртуальный нейрон, равна NbK /(NbK + Nint), и таким образом внутренний нейрон может статьпобедителем с вероятностью 1 - NbK /(NbK + Nint). Чтобы выбрать победителясреди виртуальных нейронов, генерируется случайная точка y на границе G, выбирается ближайший к y граничный узел, после чего среди виртуальных нейронов, соответствующих выбранному граничному узлу, равновероятно выбирается k-й виртуальный нейрон и назначается победителем.Ответ на вопрос (2). Для задания весов латеральных связей между виртуальными и внутренними нейронами необходимо знать расстояние между ними в вычислительной области. Предполагается, что расстояние между k-м виртуальным нейроном и внутренним нейроном с положением qt равно d (qm, qi) + kdß, где qm -это положение граничного нейрона, соответствующего виртуальному нейрону. Это расстояние приближенное, так как точное положение виртуального нейрона в вычислительной области не задается. Вес латеральной связи между k-м виртуальным нейроном, соответствующим граничному нейрону em, и нейроном et равен( d(qm ,q )+kdg V nq„ ,k (

Скачать электронную версию публикации