Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 71
Текст из файла (страница 71)
Рассмотренныи в п. 13.5.1 алгоритм нелинейногоотображения требует при реализации выполнения большого количества арифметических операций, на каждом шаге итерации количество умножений пропорционально дп'. Формирование матрицы расстояний между точками в исходном пространстве перед началом работы алгоритма также требует порядка — ри умножений.
Число умножений на 1 каждом шаге итерации в предлагаемом ниже алгоритме быстрого нелинейного отображения (БНО) пропорционально величине (д + 1) а, т. е, растет лишь линейно, в зависимости от числа используемых объектов. Результирующая матрица точек образов на выходе этого алгоритма может быть использована либо непосредственно для дальнейшего анализа, либо как начальная конфигурация для алгоритма нелинейного отображения из п. 13.5.1. Идея алгоритма БИО. Алгоритм БНО !66] основан на том, что в >1-мерном пространстве координаты точки Л можно однозначно определить набором евклидовых расстояний В := ф, (2), ..., >(э (2))' между Л и (>! + !)-й соответствующим образом выбранными опорными точками Е„..., Лэ.
Действительно, разности >7,' (Л) — 4 (7) = 2'(2,— — 2~) Е + >!Е> )!' — 1Д~(>з лишь линейно зависят от координат вектора Х. Поэтому для определения Л можно использовать систему из (> линейных уравнений АЛ =- В, где 1-я строка матрицы А есть А; = 2 (Л, — 2>), а 1-я компонента вектора В равна Ь> = ()Е»!!э — !!2;1!э + Ж (У) — Зо (4 т. е. выражается через известные величины !160). Конечно, опорные точки Л„..., 2 должны быть выбраны так, чтобы матрица А была невырождена.
373 Если опорные точки зафиксированы, то в качестве функционала качества отображения может бьггь использована следующая величина: (13.!8) т ог=ь где б, (Х,) — расстояние между объектом Х~ и опорной точкой Х, в исходном пространстве, а Ы, (ЕД вЂ” аналогичные расстояния, но в пространстве образов. Итерационная процедура уточнения координат точки Е; в пространстве образов имеет вид: Я$'~"= — ~ч"„в)о Ятф)+ 1)+ 7)о ~ч~ (гв)п+!)!(д+ 1), с=а с=а где в<п =(0,(Х,) — от (2~"))/Нт(Е)п).
Выбор нулевого приближения. Начальные значения 2~", (1= 1, п) получаются из решения п систем линейных урав- нений А Е'~' = В',", где 1чя компонента вектора В'," выражается через расстоя- ния и нормы в исходном пространстве, т. е. Х, — /-я опорная точка в исходном пространстве, Выбор системы опорных точек. Выбор системы опорных точек может производиться случайным способом, Обычно его повторяют несколько раз. При этом опорные точки не должны быть слишком близки друг к другу. Поэтому новая опорная точка добавляется к ранее выбранным, только если минимальное расстояние этой точки от ранее выбранных не менее — г(,р, где П„, — среднее расстояние. В качестве 1 2 окончательной конфигурации выбирается та, которая минимизирует критерий (13.18).
Другой способ состоит в разбиении матрицы Х на (д + 1) сгущений с помощью алгоритма Мак-Кина и в качестве опорных выбираются точки, ближайшие к центрам классов. При наличии априорных соображений точки могут задаваться исследователем. Указанные методы можно комбинировать и выбирать отображение либо с минимальной величиной.
критерия, либо наиболее подходящее с визуальной точки зрения. 3?4 Пусть Х„,, Хе — объекты из матрицы данных, выбранные в качестве опорных. Образы опорных точек 2.0,... Л получаются с помощью следующей процедуры. Шаг 1. Вычисляется матрица попарных скалярных произведений размера (д + 1) х (д + 1) У=(011 =(Х,'Х;); (, 1= О, 17). Шаг 2. Вычисляются собственные числа и векторы матрицы Ч. 1ЗО 120 мо 10О ЯО 80 то 80 80 40 зо го ю о 20 40 80 80 100 120 140 160 180 200 220 Рис 1ЗБ Быстрое нелинейное отображение сельскохоаийстаенных регионов СССР в двумерное нространство Пусть 1'1 есть 1-й собственный вектор с (д + 1)-й компонентой„а )1, — соответствующее собственное число. Тогда 1-е координаты опорных точек будут компонентами вектора )У"),, Ко П р н м е р 13.3.
На рнс. 13.5 предоставлены отображения, полученные с помощью алгоритма БНО. В качестве матрицы данных использовалась матрица данных из (149) (р =- 26, п =- 130). См. также пример 19.2. Номера опорных точек 43, 50, 100. На рисунке они обведены кружками. Как видим, точки разделились на три хорошо выделенных кластера, объективность существования которых подтверждается их соотнесением с классификацией, предложенной в (149) .
37Б 13.6.3. Быстрый алгоритм нелинейного проецирования многомерных данных, Как меру искажения геометрической конфигурации будем рассматривать здесь о (д) = — ~' (хссс — с[!с) ° 1 (13.19) Е с'сссс где с[!э! = "! (г!'! —.г!'!)'. с а= ! Для дальнейшего удобно будет использовать величину я т'(г) = ~ ([усс — [сс)', (13.19') сяс Очевидно, что 5(Х) =тэ(Х) [' ~ 1)[с. ! с>с Будем искать преобразование Е (Х): Р'=~ ]те, минимизирующее (13.19'), нли, что то же самое, (!3.!9). Оказываетси, для минимизации (13.!9') можно построить эффективную итеративную процедуру, причем количество арифметических операций (умножений) на каждой итерации будет зависеть от и линейно, т. е. У „„= с (р, (с) и, где константа с (р, с]) от а не зависит с.
Дальше, в силу того, что расстояния не меняются при преобразованиях переноса, не ограничивая общности, бул дем считать, что выполнены следующие условия: ~,', Хс=О, ! ! л ~ л.! = О (исходные данные и их образы цеитрированы). ю=! Из аналогичных соображений (инвариантности расстояний при ортогональных преобразованиях) можно считать, и что ~~"„газ~, ' = О, если 1чь т, т.
е. что переменные-образы с=! попарно ортогонал ьны. Пусть дальше ээ (аса!) есть дисперсия (точнее, ее оценка) для г'"! и э' (хсл!) — дисперсия для лсл!. Введем еще коэффициент сопряженности между двумя п-компонентными векторами у и 1 с (у, Ф) = — ~~~~~ у!11. 1 л ! с В [122] предложена другая процедура мнннмнэапнн ярнтерня (13.!9) с числом операпнй, эаэясящнм от э лннеано. зто Таким образом, это скалярное произведение у и 1, деленное на и. Если у и 1 цеитрированы, то с (у, 1) есть просто коэффициент ковариации между переменными у и 1.
Найдем теперь первую производную от т' (г.) погууо, т. е. у(т' (Х) Ыг7, где гуу! — г-я координата образа уьго объекта (! = 1, и, и =1, у)). Имеем — = — 4 ~~„'', (Иу — у)уу) (гу!' — г~'). д в(д) Я дг)" В точке глобального минимума у(т' (Е)Ыг~',~ = О. Это приводит к следующему уравнению: П П И гГ! Х (Ж вЂ” Ф)+ ч", у(!угу!'! = ~ 0уу.г,'". у= ! у=! у=! Далее имеем у(1.
гуу! = '~' г('! угы! — г! и)' = '~ (г! ! г! и ' — 2г!'! гу'! гуу! -1- у=! у= ! г(у! г гуу!) у' у Меняя порядок суммирования по 1 и), получим с учетом условий ортогональности и центрированности компонент г: л т л у!)уз!у! — ~~~~ ~~~~ гуг! (гуу! гуп)й 2изз(г(г!) гууу+.
у=! ! ! у'=1 + и г, с (х,*, х„), у= ! где векторы г =(г!'у, ... г!'!)'- гу = ((гууу!), ..., (гуу!) ) Аналогично получаем, что уу уу Маг!.'у= — 2и ~ч' ,с(х„г„) хуУо+и ~~~~~ с(х„', г,). у= ! Ф=! 1= ! Кроме того, У О,';=и(Х 1'+иЬрЬг; у= ! и ~ У(~у= 1г Р+иВРВг. у ! 377 Окончательно вектор производных по компонентам г; 7~ тз = — 4п ( — В; 7~+ 2Схг хз+ Сгз г 1ч — Схз г 1 р) 1 ч — вектор размерности с (р) с единичными компонентамн; Сг*г — матрица коэффициентов сопр яженности с(г1, г,) размера дХд; В* = 27 — 1ч () Х~ )' — ) 2; ~~+ Вр Ях — Бр Яг); У=б1ай(з'(г<п) ... зз(гт)); Сх*г — матрица размера д х р с элементами сш — — с (хз.г~); Схг — матрица размера с х р с элементами см =с(хьх~). Поскольку х<М и г<п центрированы, элемент см есть не что иное, как ковариация между переменной хнч и переменной г<п.
Используем для поиска точки минимума разновидность алгоритма с переменной метрикой, для чего потребуется еще матрица вторых производных по 2;. Непосредственным дифференцированием т;т' убеждаемся, что матрица вторых производных р;.т' имеет вид Ч) тт = 4п (В~ + юг 21). Предлагаемый алгоритм основан на применении итерационного соотношения процесса Ньютона отдельно для каждого вектора 2~ 2п+ ы =. 7) и (- — (В, + 22; Е~) ' р~ т~ (2). (13.20) с ' вв Вопросы вычислительной реализации и сходимости итерационной процедуры. Дальнейшие упрощения могут быть получены за счет использования формулы Бартлетта для обращения матрицы (Вс+ 2Е~ Е.) ' = Вс ' — 2 1+22 В; ' Я~ Матрица В, диагональная, и ее обращение не представляет вычислительных трудностей.
Конечно, ее диагональные элементы должны быть ненулевыми. Кроме того, для сходимости итерационного процесса (!3 20) необходимо, чтобы каждая из матриц В; была положительно определенной. Необходимым и достаточным условием положительной определенности всех матриц В; является выполнение соотношения 2 ш(п зз(гно) ) шах (~Х~)з — )2~((з)+(БрВх — Яр$г). ~чз<т 1<ж~л (13.21) 378 В частности, в точках минимума функционала (13.19') условие (13.21) выполняется, поскольку матрица Рт' там не- отрицательно определена н, следовательно, неотрицательно определены ее диагональные блоки 1>,'т (хотя допустимо, что (13.21) обращается в равенство).
Оценим теперь трудоемкость вычисления градиента >гт' и матрицы вторых производных 7'т'. В выражение, задающее каждый из частных градиентов 7>т', входят матрицы Схг, Сз*х, Сх*з, одинаковые для всех (> = 1, г>). Учитывая это, получаем после некоторых преобразований, что для градиента число операций умножения пропорционально (Зр + 24 -, '4'12 )-р4) п. Что касается 7,'т' (Е), то здесь необходимо дополнительно вычислить только матрицы 2,2> (>' = 1, и), что дает в совокупности примерно д'н>2 умножений. Умножение гради.
ента на обратную матрицу (по всем >=1, и в совокупности) дает — дхп умножений и обращение матрицы >>,'т' (Х) с учетом формулы Бартлетта — (д + дз) п умножений и делений. Окончательно количество вычислений (умножений), связанное шагом итерации по методу Ньютона, будет Ф (Зр + 3>1 + Здз + рд) я, т. е. является линейной функцией и. 13.6.4. Сравнение нелинейного проецирования (картироваиия) с линейным. На первый взгляд кажется, что уменьшение суммарного искажения геометрической конфигурации данных, которое обеспечивается нелинейным проецированием, обязательно должно привести к получению большей информации о структуре данных в исходном многомерном пространстве. Ниже приводится модельный пример, который показывает, что применение нелинейного отображения может не только не улучшить, но и ухудшить передачу деталей строения многомерной конфигурации при ее отображении в пространстве более низкой размерности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
