Факторное моделирование на базе метода Верле

в 9:11, , рубрики: data mining, PCA, principal component analysis, Алгоритмы, метод Верле, метод главных компонент, многомерное шкалирование, метки:

Метод Верле – это итерационный метод вычисления следующего местоположения материальной точки по текущему и прошлому местоположениям с учетом накладываемых связей внутри системы точек.

Упругая структура – это наиболее общий вид структур для аппроксимации данных. Это набор узлов и упругих связей между ними. В качестве таких связей могут выступать пружинная связь между парой точек с равновесным расстоянием между точками и ребра жесткости тройки узлов с равновесным углом между узлами. Для аппроксимации набора точек упругой структурой предлагается использовать физическую интерпретацию точек данных как центров, притягивающих узлы упругой структуры. Частным случаем упругой структуры являются нелинейные главные компоненты. Это набор упругих цепочек с общей точкой пересечения. При большой жесткости упругих связей нелинейные главные компоненты переходят в классические главные компоненты факторного анализа. Для расчета движения точек упругой структуры в поле притяжения и учета связей между узлами упругой структуры предлагается использовать метод численного интегрирования Верле.

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

1. Метод Верле

Алгоритм Верле используется для вычисления следующего положения точки по текущему и прошлому:

Факторное моделирование на базе метода Верле - 1, Факторное моделирование на базе метода Верле - 2 – вычисляемые координаты j-ой точки на i-ой итерации, m – размерность пространства, Факторное моделирование на базе метода Верле - 3 – вектор скорости j-ой точки.

Факторное моделирование на базе метода Верле - 4 – вектор влияния k-го центра притяжения, представленного точкой данных Факторное моделирование на базе метода Верле - 5, на j-ую точку,
Факторное моделирование на базе метода Верле - 6.

На систему точек накладываются ограничения: некоторые из точек связаны упругими стержнями заданной длины.

Алгоритм работает следующим образом:

  • 1. Вычисляются новые положения точек.
  • 2. Для каждой связи удовлетворяется соответствующее условие.
  • 3. Шаг 2 повторяется s раз.

Например, s = 16.

Процедура релаксации связи описывается следующими формулами:

Если связь представлена точками Факторное моделирование на базе метода Верле - 7 и Факторное моделирование на базе метода Верле - 8 с равновесным расстоянием между ними Факторное моделирование на базе метода Верле - 9, то
Факторное моделирование на базе метода Верле - 10,
Факторное моделирование на базе метода Верле - 11,
Факторное моделирование на базе метода Верле - 12,
Факторное моделирование на базе метода Верле - 13 – коэффициент упругости связи,

Факторное моделирование на базе метода Верле - 14 – коэффициент, зависящий от числа s повторений шага 2.

Факторное моделирование на базе метода Верле - 15
Рис. 1. Пружинная связь пары точек с равновесным расстоянием

Тройки узлов могут образовывать ребра жесткости с равновесным углом. Такие связи предлагается эмулировать связями в виде упругих стержней между крайними точками. Равновесное расстояние между крайними точками при этом задается из равенства треугольника. Если связь представлена точками Факторное моделирование на базе метода Верле - 16, Факторное моделирование на базе метода Верле - 17, Факторное моделирование на базе метода Верле - 18 c равновесным углом Факторное моделирование на базе метода Верле - 19, тогда равновесное расстояние Факторное моделирование на базе метода Верле - 20 между точками и вычисляется по формуле:

Факторное моделирование на базе метода Верле - 21.

Факторное моделирование на базе метода Верле - 22
Рис. 2. Ребро жесткости тройки точек с равновесным углом

2. Многомерное шкалирование

Многомерное шкалирование (МНШ) — это способ наиболее эффективного размещения объектов, приближенно сохраняющий наблюдаемые между ними расстояния. МНШ размещает объекты в пространстве заданной размерности и проверяет, насколько точно полученная конфигурация сохраняет расстояния между объектами. МНШ использует алгоритм минимизации некоторой функции, оценивающей качество получаемых вариантов отображения.

Мерой, наиболее часто используемой для оценки качества подгонки модели (отображения), измеряемого по степени воспроизведения исходной матрицы сходств, является так называемый стресс. Величина стресса φ для текущей конфигурации определяется так:

Факторное моделирование на базе метода Верле - 23.

Здесь dij − воспроизведенные расстояния в пространстве заданной размерности, а δij − исходное расстояние. m – количество объектов. Функция f(δij) обозначает неметрическое монотонное преобразование исходных данных (расстояний). МНШ воспроизводит не количественные меры сходств объектов, а лишь их относительный порядок. Чем меньше значение стресса, тем лучше матрица исходных расстояний согласуется с матрицей результирующих расстояний.

3. Главные компоненты и факторная модель

Модель главных компонент описывается следующими формулами:

Факторное моделирование на базе метода Верле - 24
m – число переменных,
g – число факторов,
Факторное моделирование на базе метода Верле - 25 − исходные переменные,
Факторное моделирование на базе метода Верле - 26 − общие факторы,
Факторное моделирование на базе метода Верле - 27 − специфичные факторы.

4. Упругая факторная структура

В качестве системы точек для метода Верле может быть использована координатная система, представленная осями Факторное моделирование на базе метода Верле - 28,
Факторное моделирование на базе метода Верле - 29, где
w – число точек, образующей факторную ось,
Факторное моделирование на базе метода Верле - 30,
g – количество факторных осей.

Например при Факторное моделирование на базе метода Верле - 31 (число w должно быть нечетным большим 1)

Факторное моделирование на базе метода Верле - 32

l – расстояние между парой соседних точек, образующих факторную ось.

Факторное моделирование на базе метода Верле - 33 – индекс центральной точки факторной оси.

Пары точек Факторное моделирование на базе метода Верле - 34 образуют связь с равновесным расстоянием l.

Пары точек Факторное моделирование на базе метода Верле - 35 образуют связь с равновесным расстоянием Факторное моделирование на базе метода Верле - 36.

Все пары точек Факторное моделирование на базе метода Верле - 37 различных осей i и j образуют связь с нулевым равновесным расстоянием.

Пары точек Факторное моделирование на базе метода Верле - 38, Факторное моделирование на базе метода Верле - 39, Факторное моделирование на базе метода Верле - 40, Факторное моделирование на базе метода Верле - 41 различных осей i и j образуют связь с равновесным расстоянием, равным начальному расстоянию между точками. Эти связи задают прямые углы между различными факторными осями i и j. Другим способом задания ортогональной факторной структуры является добавление ребер жесткости с прямым равновесным углом между тройками точек Факторное моделирование на базе метода Верле - 42 между различными факторными осями i и j.

Факторное моделирование на базе метода Верле - 43 Факторное моделирование на базе метода Верле - 44
Рис. 3. Способы задания факторной структуры для метода Верле

Элементы факторной структуры Факторное моделирование на базе метода Верле - 45 могут быть определены как коэффициент корреляции между j-ой факторной осью и i-ой осью исходной системы координат:

Факторное моделирование на базе метода Верле - 46,
Факторное моделирование на базе метода Верле - 47,
Факторное моделирование на базе метода Верле - 48 – символ Кронекера,
Факторное моделирование на базе метода Верле - 49 – вектор направления j-ой факторной оси.

5. Упругая структура многомерного шкалирования

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

Факторное моделирование на базе метода Верле - 50

n – размерность исходного пространства переменных.

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

Факторное моделирование на базе метода Верле - 51.

С помощью метода Верле будет восстановлена факторная структура в рамках гипотезы о размерности g факторного пространства.

Элементы факторной структуры Факторное моделирование на базе метода Верле - 52 могут быть определены как коэффициент корреляции между j-ой факторной осью и i-ой переменной:

Факторное моделирование на базе метода Верле - 53,
Факторное моделирование на базе метода Верле - 54,
Факторное моделирование на базе метода Верле - 55 – символ Кронекера,
Факторное моделирование на базе метода Верле - 56 – вектор направления j-ой переменной в факторном пространстве.
Факторное моделирование на базе метода Верле - 57j-ая переменная в факторном пространстве.
Факторное моделирование на базе метода Верле - 58 – центр масс факторной структуры переменных в факторном пространстве.

Факторное моделирование на базе метода Верле - 59
Рис. 4. Упругая структура многомерного шкалирования

6. Программная реализация

Метод Верле был реализован программно с использованием общедоступной JavaScript библиотеки Verlet.js, которая была усовершенствована для многомерного случая. Web приложение факторного анализа по методу расчета упругой факторной структуры и многомерного шкалирования на базе метода Верле доступно по адресам http://svlaboratory.org/application/pca и http://svlaboratory.org/application/multscal после регистрации нового пользователя. Приложение позволяет визуализировать процесс сходимости метода Верле в заданной плоскости координат (рис. 5).

Факторное моделирование на базе метода Верле - 60Факторное моделирование на базе метода Верле - 61
Рис. 5. Визуализация метода Верле в web приложении

Заключение

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

Автор: vladshow

Источник

Поделиться новостью

* - обязательные к заполнению поля