Метод Верле – это итерационный метод вычисления следующего местоположения материальной точки по текущему и прошлому местоположениям с учетом накладываемых связей внутри системы точек.
Упругая структура – это наиболее общий вид структур для аппроксимации данных. Это набор узлов и упругих связей между ними. В качестве таких связей могут выступать пружинная связь между парой точек с равновесным расстоянием между точками и ребра жесткости тройки узлов с равновесным углом между узлами. Для аппроксимации набора точек упругой структурой предлагается использовать физическую интерпретацию точек данных как центров, притягивающих узлы упругой структуры. Частным случаем упругой структуры являются нелинейные главные компоненты. Это набор упругих цепочек с общей точкой пересечения. При большой жесткости упругих связей нелинейные главные компоненты переходят в классические главные компоненты факторного анализа. Для расчета движения точек упругой структуры в поле притяжения и учета связей между узлами упругой структуры предлагается использовать метод численного интегрирования Верле.
Многомерное шкалирование позволяет в рамках гипотезы о размерности целевого пространства расположить объекты по их взаимным расстояниям таким образом, чтобы восстанавливаемые расстояния между объектами приближались к эмпирическим. На базе метода Верле предлагается осуществить многомерное шкалирование, тем самым взаимные расстояния между точками будут учтены с наибольшей точностью. В качестве матрицы взаимных расстояний будет выступать матрица корреляций. С помощью многомерного шкалирования будет осуществлена факторизация корреляционной матрицы, тем самым будет восстановлена факторная структура данных в факторном пространстве. Чтобы получить интерпретабельное решение предлагается использовать отдельные методы факторного вращения, примененные к восстановленной факторной структуре.
1. Метод Верле
Алгоритм Верле используется для вычисления следующего положения точки по текущему и прошлому:
, 
– вычисляемые координаты j-ой точки на i-ой итерации, m – размерность пространства, 
– вектор скорости j-ой точки.
– вектор влияния k-го центра притяжения, представленного точкой данных 
, на j-ую точку,
.
На систему точек накладываются ограничения: некоторые из точек связаны упругими стержнями заданной длины.
Алгоритм работает следующим образом:
- 1. Вычисляются новые положения точек.
- 2. Для каждой связи удовлетворяется соответствующее условие.
- 3. Шаг 2 повторяется s раз.
Например, s = 16.
Процедура релаксации связи описывается следующими формулами:
Если связь представлена точками 
и 
с равновесным расстоянием между ними 
, то
,
,
,
– коэффициент упругости связи,
– коэффициент, зависящий от числа s повторений шага 2.
Рис. 1. Пружинная связь пары точек с равновесным расстоянием
Тройки узлов могут образовывать ребра жесткости с равновесным углом. Такие связи предлагается эмулировать связями в виде упругих стержней между крайними точками. Равновесное расстояние между крайними точками при этом задается из равенства треугольника. Если связь представлена точками 
, 
, 
c равновесным углом 
, тогда равновесное расстояние 
между точками и вычисляется по формуле:
.
Рис. 2. Ребро жесткости тройки точек с равновесным углом
2. Многомерное шкалирование
Многомерное шкалирование (МНШ) — это способ наиболее эффективного размещения объектов, приближенно сохраняющий наблюдаемые между ними расстояния. МНШ размещает объекты в пространстве заданной размерности и проверяет, насколько точно полученная конфигурация сохраняет расстояния между объектами. МНШ использует алгоритм минимизации некоторой функции, оценивающей качество получаемых вариантов отображения.
Мерой, наиболее часто используемой для оценки качества подгонки модели (отображения), измеряемого по степени воспроизведения исходной матрицы сходств, является так называемый стресс. Величина стресса φ для текущей конфигурации определяется так:
.
Здесь dij − воспроизведенные расстояния в пространстве заданной размерности, а δij − исходное расстояние. m – количество объектов. Функция f(δij) обозначает неметрическое монотонное преобразование исходных данных (расстояний). МНШ воспроизводит не количественные меры сходств объектов, а лишь их относительный порядок. Чем меньше значение стресса, тем лучше матрица исходных расстояний согласуется с матрицей результирующих расстояний.
3. Главные компоненты и факторная модель
Модель главных компонент описывается следующими формулами:
m – число переменных,
g – число факторов,
− исходные переменные,
− общие факторы,
− специфичные факторы.
4. Упругая факторная структура
В качестве системы точек для метода Верле может быть использована координатная система, представленная осями 
,
, где
w – число точек, образующей факторную ось,
,
g – количество факторных осей.
Например при 
(число w должно быть нечетным большим 1)
l – расстояние между парой соседних точек, образующих факторную ось.
– индекс центральной точки факторной оси.
Пары точек 
образуют связь с равновесным расстоянием l.
Пары точек 
образуют связь с равновесным расстоянием 
.
Все пары точек 
различных осей i и j образуют связь с нулевым равновесным расстоянием.
Пары точек 
, 
, 
, 
различных осей i и j образуют связь с равновесным расстоянием, равным начальному расстоянию между точками. Эти связи задают прямые углы между различными факторными осями i и j. Другим способом задания ортогональной факторной структуры является добавление ребер жесткости с прямым равновесным углом между тройками точек 
между различными факторными осями i и j.
Рис. 3. Способы задания факторной структуры для метода Верле
Элементы факторной структуры 
могут быть определены как коэффициент корреляции между j-ой факторной осью и i-ой осью исходной системы координат:
,
,
– символ Кронекера,
– вектор направления j-ой факторной оси.
5. Упругая структура многомерного шкалирования
Корреляции между исходными переменными могут быть определены как скалярное произведение нормализованных последних с нулевым средним и единичной дисперсией:
n – размерность исходного пространства переменных.
Коэффициенты корреляций между исходными переменными определяют матрицу корреляций, сходную с матрицей взаимных расстояний метода многомерного шкалирования. Поскольку ближним объектам в факторном пространстве соответствуют большие значения коэффициентов корреляций, то элементы матрицы взаимных расстояний dij получаются из соответствующих элементов матрицы корреляций rij по формуле:
.
С помощью метода Верле будет восстановлена факторная структура в рамках гипотезы о размерности g факторного пространства.
Элементы факторной структуры 
могут быть определены как коэффициент корреляции между j-ой факторной осью и i-ой переменной:
,
,
– символ Кронекера,
– вектор направления j-ой переменной в факторном пространстве.
– j-ая переменная в факторном пространстве.
– центр масс факторной структуры переменных в факторном пространстве.
Рис. 4. Упругая структура многомерного шкалирования
6. Программная реализация
Метод Верле был реализован программно с использованием общедоступной JavaScript библиотеки Verlet.js, которая была усовершенствована для многомерного случая. Web приложение факторного анализа по методу расчета упругой факторной структуры и многомерного шкалирования на базе метода Верле доступно по адресам http://svlaboratory.org/application/pca и http://svlaboratory.org/application/multscal после регистрации нового пользователя. Приложение позволяет визуализировать процесс сходимости метода Верле в заданной плоскости координат (рис. 5).
Рис. 5. Визуализация метода Верле в web приложении
Заключение
В качестве упругой структуры была использована многомерная факторная структура, содержащая факторные оси и связи между различными точками факторных осей. Для аппроксимации набора точек упругой структурой был использован метод Верле и физическая интерпретация точек данных в многомерном пространстве как центры притяжения. Метод многомерного шкалирования на базе метода Верле, применный к корреляционной матрице, является альтернативным методом факторизации. В качестве многомерной упругой структуры может быть использована произвольная структура, тем самым предложенный метод аппроксимации на базе метода Верле имеет обобщенный характер.
Автор: vladshow
