О методе главных компонент

На днях пришлось столкнуться с «методом главных компонент» (principal component analysis, PCA). Ниже даю обретённое мною понимание оного.

Дано: набор точек { pi ∈ ℝd | i∈1:n }, dn.

Предположение: точки получены аффинным преобразованием реализации случайного процесса y: pi = μ + yiW, где μ ∈ ℝd, W — некая матрица, а yi удовлетворяют многомерному нормальному распределению с нулевым матожиданием и единичной матрицей ковариации.

Задача: найти μ, W и yi.

Замечание 1. Размерность yi не обязана совпадать с размерностью pi.

Замечание 2. В качестве оценки матожидания μ возьмём арифметическое среднее pi: μ = Σi pi / n. Обозначим: xi = pi − μ.

Замечание 3. Так как покоординатно независимое нормальное распределение порождает «шарообразное» скопление точек yi, то следует ожидать, что xi формируют скопление, визуально напоминающее повёрнутый d-осный эллипсоид. Иными словами, можно искать матрицу W как комбинацию анизотропного масштабирования и поворота: W = TR, где T может иметь ненулевые элементы только на главной диагонали, а R ортогональна.

Через X обозначим n×d-матрицу, составленную из строк xi.

«Поточечная» матрица ковариации XX имеет размеры n×n. «Покоординатная» матрица ковариации XX имеет размеры d×d. Обе эти матрицы симметричны, но в общем случае не диагональны.

Через Y обозначим n×r-матрицу, составленную из строк yi. По предположению имеем YY = 1n или YY = 1r. Выберем пока первый вариант. Из него немедленно следует rn. Логично положить r = n, тогда Y ортогональна.

Итак, X = YTR, где Y и R ортогональны, а T имеет ненулевые элементы только на главной диагонали. Данное разложение матрицы X есть ни что иное, как разложение сингулярных значений (singular value decomposition, SVD).

Возьмём любую реализацию SVD и построим разложение: X = USV*. В общем случае матрицы U и V унитарны, звёздочкой обозначено эрмитово сопряжение. В нашем случае они ортогональны и сопряжение есть транспонирование, поэтому можно положить:

Y = U, T = S, R = V, W = SV.

Замечание 4. На диагонали S стоят сингулярные значения, в нашей задаче имеющие геометрический смысл длин полуосей эллипсоида. Они неотрицательны и по построению отсортированы по величине от больших к меньшим. В конце могут стоять нули, означающие, что по соответствующим направлениям (которым отвечают столбцы V) эллипсоид вырожден, и эти измерения можно отбросить. С практической точки зрения может быть разумным отбросить все измерения, для которых полуось (сингулярное значение) меньше некоторой заданной величины. WW = SS — диагональная матрица, составленная из квадратов сингулярных значений.

Шаг 1. A = XV. Так как V есть матрица, обратная к R, то A = YT. Это эллипсоид, повёрнутый так, чтобы его оси совпали с осями координат стандартного базиса, причём разброс данных на каждой следующей оси не больше, чем на предыдущей. Кому-то этого результата уже может быть достаточно.

Шаг 2. Пусть задано ρ ≥ 0 — предельная «чувствительность» по измерению. Исходная полная матрица S может быть неквадратной и содержать нулевой блок под квадратом d×d, здесь я его проигнорирую и положу S = diag(sj), 1 ≤ jd.

Пусть r = max{ j | sj > ρ }. Положим B = A[1:r], т.е. первые r столбцов матрицы A. Строки bi матрицы B есть точки в пространстве уменьшенной размерности r ≤ d.

Шаг 3. Составим усечённую псевдообратную матрицу S+ = diag(1/sj), 1 ≤ jr.
Положим Z = BS+. Так как S+ есть матрица, обратная к усечённой T, то мы получим, что Z = Y[1:r], т.е. первые r столбцов Y. Если мы уже вычислили U, то можно просто взять из неё первые r столбцов: Z = U[1:r]. Имеем ZZ = 1r.

Точки zi имеют уменьшенную размерность r ≤ d и отмасштабированы по осям координат.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход /  Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход /  Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход /  Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход /  Изменить )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d такие блоггеры, как: