Участник:OscarFox/Обобщенный прокрустов анализ
Автор: Фостенко О.А.
Свойства и структура алгоритма
Общее описание алгоритма
Обобщенный прокрустов анализ (Generalized Procrustes Analysis, GPA) - это метод, предназначенный для сравнения и выравнивания нескольких наборов из одного и того же числа точек (форм) в пространстве одной размерности. Цель GPA - найти оптимальные преобразования, включающие вращения, масштабирование и сдвиги, для наилучшего согласования форм друг с другом.
Формулировка похожей задачи встречается в работе B. F. Green 1952 года[1], аналитическое решение задачи выравнивания двух множеств точек друг относительно друга (классическое прокрустово преобразование) было предложено P. H. Schönemann в 1966 году[2], а непосредственно алгоритм GPA был разработан и опубликован J. C. Gower в 1975 году[3].
GPA - это итеративный алгоритм: он последовательно согласовывает все формы относительно некоторой «средней формы», обновляя её до тех пор, пока изменения не станут незначительными. К «средней форме» набор из точек приводится с помощью классического прокрустова преобразования. Иллюстрация выравнивания, выполняемого с помощью как классического, так и обобщенного прокрустовых преобразований, приведена на рисунке 1.
Математическое описание алгоритма
Описание данных и формул
Входные данные:
- [math]\displaystyle{ \{X_1, X_2,\dots,X_m\} }[/math] - набор входных форм, то есть матриц одного размера: [math]\displaystyle{ X_i \in \mathbb{R}^{n \times d}, \; i=1,\dots,m }[/math]. Каждая матрица [math]\displaystyle{ X_i }[/math] представляет собой набор из [math]\displaystyle{ n }[/math] точек в [math]\displaystyle{ d }[/math]-мерном пространстве. Точки с одинаковыми индексами (т.е. строки матриц с одинаковыми номерами) предполагаются соответствующими друг другу.
Выходные данные:
- Выровненные формы [math]\displaystyle{ \{ X_1', X_2',\dots,X_m'\} }[/math], где [math]\displaystyle{ X_i'\in \mathbb{R}^{n \times d}, \; i=1,\dots,m }[/math].
Описание алгоритма
Выровненные формы [math]\displaystyle{ \{ X_i' \}_{i=1}^m }[/math], где [math]\displaystyle{ X_i' = s_i X_i R_i + \mathbf{1}_n t_i^T }[/math]. Здесь [math]\displaystyle{ s_i\in \mathbb{R} }[/math] есть константа масштаба, [math]\displaystyle{ R_i\in \mathbb{R}^{d \times d} }[/math] - ортогональная матрица, отвечающая вращению, [math]\displaystyle{ \mathbf{1}_n\in \mathbb{R}^{n \times 1} }[/math] - вектор-столбец из единиц, а [math]\displaystyle{ t_i\in \mathbb{R}^{n \times 1} }[/math] - вектор переноса.
Средняя форма (консенсус): [math]\displaystyle{ M = \frac{1}{m} \sum_{i=1}^m X_i' }[/math].
Программная реализация алгоритма
Литература
- ↑ Green B. F. The orthogonal approximation of an oblique structure in factor analysis // Psychometrika. — 1952. — Vol. 17, no. 4. — P. 429–440. [1]
- ↑ Schönemann P. H. A Generalized Solution of the Orthogonal Procrustes Problem // Psychometrika. — 1966. — Vol. 31, no. 1. — P. 1–10. [2]
- ↑ Gower J. C. Generalized procrustes analysis // Psychometrika. — 1975. — Vol. 40, no. 1. — P. 33–51. [3]