Участник:OscarFox/Обобщенный прокрустов анализ
Автор: Фостенко О.А.
Свойства и структура алгоритма
Общее описание алгоритма
Обобщенный прокрустов анализ (Generalized Procrustes Analysis, GPA) - это метод, предназначенный для сравнения и выравнивания нескольких наборов из одного и того же числа точек (форм) в пространстве одной размерности. Цель GPA - найти оптимальные преобразования, включающие вращения, масштабирование и сдвиги, для наилучшего согласования форм друг с другом.
Формулировка похожей задачи встречается в работе B. F. Green 1952 года[1], аналитическое решение задачи выравнивания двух множеств точек друг относительно друга с учетом только вращений (ортогональная задача Прокруста) было предложено P. H. Schönemann в 1966 году[2], в 1970 году им же в соавторстве с R. M. Carroll[3] предложено аналитическое решение для модификации, учитывающей, помимо вращений, смещения и масштабирование (классический прокрустов анализ), а непосредственно алгоритм GPA был разработан и опубликован J. C. Gower в 1975 году[4].
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{ Y\in \mathbb{R}^{n \times d} }[/math].
- Опционально, коэффициенты масштаба [math]\displaystyle{ s_i\in \mathbb{R} }[/math].
Вспомогательные понятия:
- [math]\displaystyle{ CPA(X, Y): \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times d} \rightarrow \mathbb{R}^{n \times d} }[/math] - функция, выполняющая классический прокрустов анализ, вращая, смещая и масштабируя форму [math]\displaystyle{ X }[/math] так, чтобы она наилучшим образом подходила под форму [math]\displaystyle{ Y }[/math]. Возвращает матрицу из [math]\displaystyle{ \mathbb{R}^{n \times d} }[/math], отвечающую преобразованной форме [math]\displaystyle{ X }[/math].
- [math]\displaystyle{ \| X \|_F = \sqrt{tr(X X^T)} }[/math] - норма Фробениуса матрицы [math]\displaystyle{ X }[/math].
Описание алгоритма (GPA)[4]
Пусть [math]\displaystyle{ X_i' = s_i X_i R_i + \mathbf{1}_n t_i }[/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}^{1 \times d} }[/math] - вектор переноса.
В процессе работы GPA итеративно минимизирует следующую функцию:
[math]\displaystyle{ S = \displaystyle \sum_{i\lt j}^{m} \| X_i' - X_j' \|_F^2 }[/math]
по всевозможным смещениям [math]\displaystyle{ t_i }[/math], вращениям [math]\displaystyle{ R_i }[/math] и константам масштаба [math]\displaystyle{ s_i }[/math] для всех [math]\displaystyle{ i=1,\dots,m }[/math], с условием, что [math]\displaystyle{ \displaystyle \sum_{i=1}^{m} s_i^2 \| X_i \|_F^2 = \sum_{i=1}^{m} \| X_i \|_F^2 }[/math] (чтобы избежать зануления всех [math]\displaystyle{ s_i }[/math]).
Минимизация [math]\displaystyle{ S }[/math] сводится к минимизации [math]\displaystyle{ S_r = \displaystyle \sum_{i=1}^{m} tr(X_i' X_i'^T) - m \cdot tr(Y Y^T) }[/math], где [math]\displaystyle{ Y }[/math] - средняя форма (консенсус).
Алгоритм (GPA)
Шаг 1. Инициализация.
Задаем начальные значения выравниваемых форм, центрируя их:
Вычисляем смещение для центрирования форм: [math]\displaystyle{ \bar{X_i} = \frac{1}{n} \mathbf{1}_n^T X_i }[/math]
Центрируем формы: [math]\displaystyle{ X_i' := X_i - \mathbf{1}_n \bar{X_i}, \; i = 1,\dots,m. }[/math]
Далее нормируем масштаб форм (в совокупности):
[math]\displaystyle{ \displaystyle X_i' := \lambda X_i', \; \lambda = \sqrt{\frac{m}{ \sum_{i=1}^{m} \| X_i \|_F^2}}, \; i=1,\dots,m. }[/math]
Задаем начальную среднюю форму, выбирая одну из центрированных форм входного набора (например, первую): [math]\displaystyle{ Y := X_1' }[/math].
Шаг 2. Инициализация функции ошибки.
Выполнить подгонку каждой формы (без учета первой - так как выбрали ее за изначальный консенсус) [math]\displaystyle{ X_i' }[/math] к [math]\displaystyle{ Y }[/math] и оценить функцию ошибки:
[math]\displaystyle{ \forall i=2,\dots,m \; X_i' := CPA(X_i', Y) }[/math];
Пересчитать консенсус: [math]\displaystyle{ \displaystyle Y := \frac{1}{m} \sum_{i=1}^{m} X_i' }[/math];
Посчитать начальное значение функции потерь: [math]\displaystyle{ S_r := m(1 - tr(Y Y^T)) }[/math];
Также инициализируем [math]\displaystyle{ s_i := 1, \; i=1,\dots,m }[/math].
Заметим, что на данном шаге в рамках классического прокрустова анализа ([math]\displaystyle{ CPA(X, Y) }[/math]) вычисляется только матрица поворота, но не смещение и масштаб (так как формы уже центрированы, а масштаб вычисляется далее).
Шаг 3. Выравнивание форм относительно средней.
Для всех текущих форм [math]\displaystyle{ X_i', \; i = 1,\dots,m }[/math] выполняется их выравнивание относительно средней формы (консенсуса). Заметим, что здесь также выполняется только поворот, но не смещение и масштабирование:
[math]\displaystyle{ X_i' }[/math] присваивается новое значение: [math]\displaystyle{ X_i' := CPA(X_i', Y) = X_i' R_i, \; i=1,\dots,m }[/math].
Выполняется вычисление нового консенсуса: [math]\displaystyle{ Y^* := \frac{1}{m} \sum_{i=1}^{m} X_i' }[/math];
также выполняется пересчет функции ошибки: [math]\displaystyle{ S_r^* := S_r - m \cdot tr(Y^* (Y^*)^T - Y Y^T) }[/math];
и устанавливаем [math]\displaystyle{ S_r^{**} := S_r^* }[/math].
Шаг 4.
Если масштабирование не требуется, перейти на шаг 6, присвоив [math]\displaystyle{ Y := Y^* }[/math], иначе перейти на следующий шаг.
Шаг 5. Масштабирование.
Для каждого [math]\displaystyle{ i=1,\dots,m }[/math]
выполняется подсчет [math]\displaystyle{ s_i^* := s_i \cdot \sqrt{ \frac{tr(X_i' Y^T)}{tr(X_i' X_i'^T) \cdot tr(Y Y^T)}} }[/math];
далее присваиваем [math]\displaystyle{ X_i' := \frac{s_i^*}{s_i} X_i' }[/math];
устанавливаем [math]\displaystyle{ s_i := s_i^* }[/math];
вычисляем новый консенсус: [math]\displaystyle{ Y := \frac{1}{m} \sum_{i=1}^{m} X_i' }[/math];
пересчитываем функцию ошибки [math]\displaystyle{ S_r^{**} := S_r^* - m \cdot tr(Y Y^T - Y^* (Y^*)^T) }[/math]
Шаг 6. Проверка критерия останова.
Если [math]\displaystyle{ S_r - S_r^{**} \gt \varepsilon }[/math], где [math]\displaystyle{ \varepsilon }[/math] - установленный заранее параметр точности, то установить [math]\displaystyle{ S_r := S_r^{**} }[/math] и перейти на шаг 3, иначе перейти на следующий шаг.
Шаг 7. Завершение итераций.
Вернуть результат: [math]\displaystyle{ Y, \; X_i' }[/math], а также опционально [math]\displaystyle{ s_i, \; i=1,\dots,m }[/math].
Описание подзадачи (CPA)[2]
Задача классического прокрустова анализа (Classical Procrustes Analysis) без масштабирования и сдвигов заключается в нахождении матрицы вращения [math]\displaystyle{ R }[/math], минимизирующей [math]\displaystyle{ \| AR - B \|^2_F }[/math] для некоторых матриц [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] одного размера. Такая постановка также называется ортогональной задачей Прокруста (Orthogonal Procrustes Problem, OPA).
У этой задачи есть аналитическое решение. Такая оптимальная матрица поворота находится следующим образом:
Сначала вычисляется произведение [math]\displaystyle{ M = A^T B }[/math].
Далее для нахождения [math]\displaystyle{ R }[/math] требуется выполнить сингулярное разложение [math]\displaystyle{ M: M = U \Sigma V^T }[/math].
Тогда искомая матрица поворота [math]\displaystyle{ R }[/math] выражается как [math]\displaystyle{ R = VU^T }[/math].
Если [math]\displaystyle{ det(R) \lt 0 }[/math], то преобразование выполняется с отражением. Чтобы исключить такие случаи, достаточно домножить последний столбец матрицы [math]\displaystyle{ V }[/math] на [math]\displaystyle{ -1 }[/math]. Тогда для полученного [math]\displaystyle{ R }[/math] будет выполнено ограничение [math]\displaystyle{ det(R)=1 }[/math] при сохранении оптимальности.
Вычислительное ядро алгоритма
Вычислительное ядро каждой итерации GPA зависит от размерности выравниваемых матриц [math]\displaystyle{ X_i \in \mathbb{R}^{n \times d} }[/math]. Если [math]\displaystyle{ d \gt n }[/math], то основную сложность представляют сингулярное разложение и конструирование матрицы вращений в рамках классического прокрустова анализа для каждой формы: [math]\displaystyle{ CPA(X_i', Y) = X_i' R_i }[/math] (последовательная сложность - [math]\displaystyle{ O(d^3) }[/math]). Иначе, основные вычисления приходятся на матричные умножения видов [math]\displaystyle{ X^TY }[/math] и [math]\displaystyle{ XR }[/math], где [math]\displaystyle{ X, Y \in \mathbb{R}^{n \times d}, R \in \mathbb{R}^{d \times d} }[/math]. Эти матричные умножения имеют место как в рамках классического прокрустова преобразования, так и при обновлении форм (последовательная сложность - [math]\displaystyle{ O(nd^2) }[/math]).
Макроструктура алгоритма
В данном разделе используются те же обозначения, что и в разделе "Математическое описание алгоритма"
В качестве макроопераций выделяются:
- Операция вычисления матрицы вращения с помощью классического прокрустова анализа [math]\displaystyle{ CPA(X, Y) }[/math]: на каждой итерации GPA (после нулевой) выполняется [math]\displaystyle{ m }[/math] таких операций, где [math]\displaystyle{ m }[/math] - число форм во входных данных. На нулевой же итерации производится [math]\displaystyle{ m-1 }[/math] операций этого типа.
- Вычисление консенсусной формы (сложение матриц, отвечающих [math]\displaystyle{ m }[/math] формам, и умножение этой суммы на скаляр): 1 операция на 1 итерацию GPA. Сложность - [math]\displaystyle{ }[/math]
- Масштабирование форм (вычисление скаляров для каждой формы): [math]\displaystyle{ m }[/math] операций на 1 итерацию GPA (кроме нулевой, где скаляры принимаются равными 1).
- Пересчет функции ошибки: две операции на 1 итерацию GPA (вариация GPA, учитывающая масштаб)
Программная реализация алгоритма
Литература
- ↑ Green B. F. The orthogonal approximation of an oblique structure in factor analysis // Psychometrika. — 1952. — Vol. 17, no. 4. — P. 429–440. [1]
- ↑ 2,0 2,1 Schönemann P. H. A Generalized Solution of the Orthogonal Procrustes Problem // Psychometrika. — 1966. — Vol. 31, no. 1. — P. 1–10. [2]
- ↑ Schönemann P. H., Carroll R. M. Fitting one matrix to another under choice of a central dilation and a rigid motion // Psychometrika. — 1970. — Vol. 35, no. 2. — P. 245–255. [3]
- ↑ 4,0 4,1 Gower J. C. Generalized procrustes analysis // Psychometrika. — 1975. — Vol. 40, no. 1. — P. 33–51. [4]