Анализ главных компонент L1-нормы - L1-norm principal component analysis

L1-PCA по сравнению с PCA. Номинальные данные (синие точки); выброс (красная точка); ПК (черная линия); L1-PC (красная линия); номинальная линия максимальной дисперсии (пунктирная линия).

Анализ главных компонент L1-нормы (L1-PCA) - это общий метод многомерного анализа данных.^[1]L1-PCA часто предпочтительнее стандартной L2-нормы Анализ главных компонентов (PCA), когда анализируемые данные могут содержать выбросы (неверные значения или искажения).^[2][3][4]

И L1-PCA, и стандартный PCA ищут коллекцию ортогональный направления (главные компоненты), определяющие подпространство при этом представление данных максимизируется в соответствии с выбранным критерием.^[5][6][7]Стандартный PCA количественно определяет представление данных как совокупность L2-нормы точки данных. прогнозы в подпространство, или, что то же самое, совокупность Евклидово расстояние исходных точек из их представлений, спроецированных на подпространство. L1-PCA вместо этого использует совокупность L1-нормы проекций точек данных в подпространство.^[8] В PCA и L1-PCA количество главных компонентов (ПК) меньше, чем классифицировать анализируемой матрицы, которая совпадает с размерностью пространства, определяемого исходными точками данных, поэтому обычно используются PCA или L1-PCA для уменьшение размерности для шумоподавления или сжатия данных. Среди преимуществ стандартного PCA, которые способствовали его высокой популярности, бюджетный вычислительная реализация с помощью сингулярное разложение (СВД)^[9] и статистическая оптимальность, когда набор данных генерируется истинным многомерный нормальный источник данных.

Однако в современных наборах больших данных данные часто включают поврежденные, ошибочные точки, обычно называемые выбросами.^[10]Стандартный PCA, как известно, чувствителен к выбросам, даже когда они появляются как небольшая часть обработанных данных.^[11]Причина в том, что формулировка L2-нормы L2-PCA уделяет квадратное внимание величине каждой координаты каждой точки данных, в конечном итоге чрезмерно подчеркивая периферийные точки, такие как выбросы. С другой стороны, следуя формулировке L1-нормы, L1-PCA делает линейный акцент на координатах каждой точки данных, эффективно ограничивая выбросы.^[12]

Формулировка

Рассмотрим любые матрица ${\displaystyle \mathbf {X} =[\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{N}]\in \mathbb {R} ^{D\times N}}$ состоящий из ${\displaystyle N}$ ${\displaystyle D}$-размерные точки данных. Определять ${\displaystyle r=rank(\mathbf {X} )}$. Для целого числа ${\displaystyle K}$ такой, что ${\displaystyle 1\leq K<r}$, L1-PCA формулируется как:^[1]

${\displaystyle {\begin{aligned}&{\underset {\mathbf {Q} =[\mathbf {q} _{1},\mathbf {q} _{2},\ldots ,\mathbf {q} _{K}]\in \mathbb {R} ^{D\times K}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}\\&{\text{subject to}}~~\mathbf {Q} ^{\top }\mathbf {Q} =\mathbf {I} _{K}.\end{aligned}}}$

(1)

За ${\displaystyle K=1}$, (1) упрощает нахождение главной компоненты L1-нормы (L1-PC) ${\displaystyle \mathbf {X} }$ к

${\displaystyle {\begin{aligned}&{\underset {\mathbf {q} \in \mathbb {R} ^{D\times 1}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {q} \|_{1}\\&{\text{subject to}}~~\|\mathbf {q} \|_{2}=1.\end{aligned}}}$

(2)

В (1)-(2), L1-норма ${\displaystyle \|\cdot \|_{1}}$ возвращает сумму абсолютных значений своего аргумента и L2-нормы ${\displaystyle \|\cdot \|_{2}}$ возвращает сумму квадратов записей своего аргумента. Если заменить ${\displaystyle \|\cdot \|_{1}}$ в (2) посредством Фробениус / L2-норма ${\displaystyle \|\cdot \|_{F}}$, то задача принимает вид стандартного PCA и решается матрицей ${\displaystyle \mathbf {Q} }$ который содержит ${\displaystyle K}$ доминирующие сингулярные векторы ${\displaystyle \mathbf {X} }$ (т.е. особые векторы, соответствующие ${\displaystyle K}$ наибольший сингулярные значения ).

Метрика максимизации в (2) может быть расширен как

${\displaystyle \|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}=\sum _{k=1}^{K}\sum _{n=1}^{N}|\mathbf {x} _{n}^{\top }\mathbf {q} _{k}|.}$

(3)

Решение

Для любой матрицы ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}}$ с ${\displaystyle m\geq n}$, определять ${\displaystyle \Phi (\mathbf {A} )}$ как ближайшую (в смысле L2-нормы) матрицу к ${\displaystyle \mathbf {A} }$ с ортонормированными столбцами. То есть определить

${\displaystyle {\begin{aligned}\Phi (\mathbf {A} )=&{\underset {\mathbf {Q} \in \mathbb {R} ^{m\times n}}{\text{argmin}}}~~\|\mathbf {A} -\mathbf {Q} \|_{F}\\&{\text{subject to}}~~\mathbf {Q} ^{\top }\mathbf {Q} =\mathbf {I} _{n}.\end{aligned}}}$

(4)

Теорема Прокруста^[13][14] заявляет, что если ${\displaystyle \mathbf {A} }$ есть СВД ${\displaystyle \mathbf {U} _{m\times n}{\boldsymbol {\Sigma }}_{n\times n}\mathbf {V} _{n\times n}^{\top }}$, тогда ${\displaystyle \Phi (\mathbf {A} )=\mathbf {U} \mathbf {V} ^{\top }}$.

Маркопулос, Каристинос и Падос^[1] показал, что если ${\displaystyle \mathbf {B} _{\text{BNM}}}$ является точным решением бинарной задачи максимизации ядерной нормы (BNM)

${\displaystyle {\begin{aligned}{\underset {\mathbf {B} \in \{\pm 1\}^{N\times K}}{\text{max}}}~~\|\mathbf {X} \mathbf {B} \|_{*}^{2},\end{aligned}}}$

(5)

тогда

${\displaystyle {\begin{aligned}\mathbf {Q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {B} _{\text{BNM}})\end{aligned}}}$

(6)

является точным решением L1-PCA в (2). В ядерная норма ${\displaystyle \|\cdot \|_{*}}$ в (2) возвращает сумму сингулярных значений аргумента матрицы и может быть вычислен с помощью стандартного SVD. Более того, верно, что для решения L1-PCA ${\displaystyle \mathbf {Q} _{\text{L1}}}$, решение BNM может быть получено как

${\displaystyle {\begin{aligned}\mathbf {B} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}})\end{aligned}}}$

(7)

куда ${\displaystyle {\text{sgn}}(\cdot )}$ возвращает ${\displaystyle \{\pm 1\}}$-знаковая матрица своего матричного аргумента (без ограничения общности можно рассматривать ${\displaystyle {\text{sgn}}(0)=1}$). Кроме того, отсюда следует, что ${\displaystyle \|\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {B} _{\text{BNM}}\|_{*}}$. BNM в (5) это комбинаторный проблема антиподальных двоичных переменных. Следовательно, ее точное решение можно найти путем исчерпывающей оценки всех ${\displaystyle 2^{NK}}$ элементы его технико-экономического обоснования, с асимптотическая стоимость ${\displaystyle {\mathcal {O}}(2^{NK})}$. Следовательно, L1-PCA также может быть решен через BNM с затратами. ${\displaystyle {\mathcal {O}}(2^{NK})}$ (экспонента от произведения количества точек данных на количество искомых компонентов). Оказывается, что L1-PCA может быть решена оптимально (точно) с полиномиальной сложностью за ${\displaystyle N}$ для фиксированного измерения данных ${\displaystyle D}$, ${\displaystyle {\mathcal {O}}(N^{rK-K+1})}$.^[1]

Для особого случая ${\displaystyle K=1}$ (один L1-ПК из ${\displaystyle \mathbf {X} }$), BNM принимает форму бинарно-квадратичной максимизации (BQM)

${\displaystyle {\begin{aligned}&{\underset {\mathbf {b} \in \{\pm 1\}^{N\times 1}}{\text{max}}}~~\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} .\end{aligned}}}$

(8)

Переход от (5) к (8) за ${\displaystyle K=1}$ верно, поскольку единственное сингулярное значение ${\displaystyle \mathbf {X} \mathbf {b} }$ равно ${\displaystyle \|\mathbf {X} \mathbf {b} \|_{2}={\sqrt {\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} }}}$, для каждого ${\displaystyle \mathbf {b} }$. Тогда, если ${\displaystyle \mathbf {b} _{\text{BNM}}}$ является решением BQM в (7) справедливо

${\displaystyle {\begin{aligned}\mathbf {q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {b} _{\text{BNM}})={\frac {\mathbf {X} \mathbf {b} _{\text{BNM}}}{\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}}}\end{aligned}}}$

(9)

является точным L1-PC ${\displaystyle \mathbf {X} }$, как определено в (1). Кроме того, считается, что ${\displaystyle \mathbf {b} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}})}$ и ${\displaystyle \|\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}}$.

Алгоритмы

Точное решение экспоненциальной сложности

Как показано выше, точное решение L1-PCA можно получить с помощью следующего двухэтапного процесса:

1. Решите проблему в (5) чтобы получить ${\displaystyle \mathbf {B} _{\text{BNM}}}$.2. Применить СВД на ${\displaystyle \mathbf {X} \mathbf {B} _{\text{BNM}}}$ чтобы получить ${\displaystyle \mathbf {Q} _{\text{L1}}}$.

BNM в (5) может быть решена путем перебора области определения ${\displaystyle \mathbf {B} }$ со стоимостью ${\displaystyle {\mathcal {O}}(2^{NK})}$.

Точное решение полиномиальной сложности

Кроме того, L1-PCA может быть решена оптимально по цене. ${\displaystyle {\mathcal {O}}(N^{rK-K+1})}$, когда ${\displaystyle r=rank(\mathbf {X} )}$ постоянна по отношению к ${\displaystyle N}$ (всегда верно для конечной размерности данных ${\displaystyle D}$).^[1][15]

Приблизительные эффективные решатели

В 2008 году Квак^[12] предложили итерационный алгоритм приближенного решения L1-PCA для ${\displaystyle K=1}$. Позднее этот итерационный метод был обобщен для ${\displaystyle K>1}$ составные части.^[16] Еще один приближенный эффективный решатель был предложен Маккой и Троппом.^[17] с помощью полуопределенного программирования (SDP). Совсем недавно L1-PCA (и BNM в (5)) были эффективно решены с помощью итераций с переворачиванием битов (алгоритм L1-BF).^[8][18]

Алгоритм L1-BF

 1  функция L1BF (${\displaystyle \mathbf {X} }$, ${\displaystyle K}$): 2 Инициализировать ${\displaystyle \mathbf {B} ^{(0)}\in \{\pm 1\}^{N\times K}}$ и ${\displaystyle {\mathcal {L}}\leftarrow \{1,2,\ldots ,NK\}}$ 3 комплект ${\displaystyle t\leftarrow 0}$ и ${\displaystyle \omega \leftarrow \|\mathbf {X} \mathbf {B} ^{(0)}\|_{*}}$ 4 До расторжения (или ${\displaystyle T}$ итераций) 5 ${\displaystyle \mathbf {B} \leftarrow \mathbf {B} ^{(t)}}$, ${\displaystyle t'\leftarrow t}$ 6 Для ${\displaystyle x\in {\mathcal {L}}}$ 7              ${\displaystyle k\leftarrow \lceil {\frac {x}{N}}\rceil }$, ${\displaystyle n\leftarrow x-N(k-1)}$ 8              ${\displaystyle [\mathbf {B} ]_{n,k}\leftarrow -[\mathbf {B} ]_{n,k}}$                // перевернуть бит 9              ${\displaystyle a(n,k)\leftarrow \|\mathbf {X} \mathbf {B} \|_{*}}$               // рассчитывается SVD или быстрее (см.[8])10 если ${\displaystyle a(n,k)>\omega }$11                  ${\displaystyle \mathbf {B} ^{(t)}\leftarrow \mathbf {B} }$, ${\displaystyle t'\leftarrow t+1}$12                  ${\displaystyle \omega \leftarrow a(n,k)}$13 end14 если ${\displaystyle t'=t}$                    // бит не был перевернут15 если ${\displaystyle {\mathcal {L}}=\{1,2,\ldots ,NK\}}$16 прекратить17 else18 ${\displaystyle {\mathcal {L}}\leftarrow \{1,2,\ldots ,NK\}}$

Вычислительная стоимость L1-BF составляет ${\displaystyle {\mathcal {O}}(NDmin\{N,D\}+N^{2}K^{2}(K^{2}+r))}$.^[8]

Комплексные данные

L1-PCA также был обобщен для обработки сложный данные. Для сложного L1-PCA в 2018 году были предложены два эффективных алгоритма.^[19]

Тензорные данные

L1-PCA также был расширен для анализа тензор данные в форме L1-Tucker, робастного аналога L1-нормы стандартного Разложение Таккера.^[20] Два алгоритма решения L1-Tucker - это L1-HOSVD и L1-HOOI.^[20][21][22]

Код

MATLAB код для L1-PCA доступен на MathWorks^[23] и другие репозитории.^[18]

Рекомендации

1. Markopoulos, Panos P .; Каристинос, Джордж Н .; Падос, Димитрис А. (октябрь 2014 г.). «Оптимальные алгоритмы обработки сигналов L1-подпространства». Транзакции IEEE при обработке сигналов. 62 (19): 5046–5058. arXiv:1405.6785. Bibcode:2014ITSP ... 62,5046M. Дои:10.1109 / TSP.2014.2338077.
2. Барродейл, И. (1968). «Аппроксимация L1 и анализ данных». Прикладная статистика. 17 (1): 51–57. Дои:10.2307/2985267. JSTOR  2985267.
3. Барнетт, Вик; Льюис, Тоби (1994). Выбросы в статистических данных (3-е изд.). Чичестер [u.a.]: Уайли. ISBN  978-0471930945.
4. Канаде, Т .; Кэ, Кифа (июнь 2005 г.). Надежная факторизация нормы L1 при наличии выбросов и отсутствующих данных с помощью альтернативного выпуклого программирования. 2005 Конференция компьютерного общества IEEE по компьютерному зрению и распознаванию образов (CVPR'05). 1. IEEE. п. 739. CiteSeerX  10.1.1.63.4605. Дои:10.1109 / CVPR.2005.309. ISBN  978-0-7695-2372-9.
5. Джоллифф, И. (2004). Анализ главных компонентов (2-е изд.). Нью-Йорк: Спрингер. ISBN  978-0387954424.
6. Епископ, Кристофер М. (2007). Распознавание образов и машинное обучение (Корр. Полиграф. Ред.). Нью-Йорк: Спрингер. ISBN  978-0-387-31073-2.
7. Пирсон, Карл (8 июня 2010 г.). "На прямых и плоскостях, наиболее приближенных к системам точек в пространстве" (PDF). Лондонский, Эдинбургский и Дублинский философский журнал и научный журнал. 2 (11): 559–572. Дои:10.1080/14786440109462720.
8. Markopoulos, Panos P .; Кунду, Сандипан; Чамадия, Шубхам; Падос, Димитрис А. (15 августа 2017 г.). «Эффективный анализ основных компонентов L1-нормы с помощью перестановки битов». Транзакции IEEE при обработке сигналов. 65 (16): 4252–4264. arXiv:1610.01959. Bibcode:2017ITSP ... 65.4252M. Дои:10.1109 / TSP.2017.2708023.
9. Голуб, Джин Х. (апрель 1973 г.). «Некоторые модифицированные матричные задачи на собственные значения». SIAM Обзор. 15 (2): 318–334. CiteSeerX  10.1.1.454.9868. Дои:10.1137/1015032.
10. Барнетт, Вик; Льюис, Тоби (1994). Выбросы в статистических данных (3-е изд.). Чичестер [u.a.]: Уайли. ISBN  978-0471930945.
11. Candès, Emmanuel J .; Ли, Сяодун; Могу ли я; Райт, Джон (1 мая 2011 г.). «Надежный анализ главных компонент?». Журнал ACM. 58 (3): 1–37. arXiv:0912.3599. Дои:10.1145/1970392.1970395.
12. Квак, Н. (сентябрь 2008 г.). «Анализ главных компонентов на основе максимизации L1-нормы». IEEE Transactions по анализу шаблонов и машинному анализу. 30 (9): 1672–1680. CiteSeerX  10.1.1.333.1176. Дои:10.1109 / TPAMI.2008.114. PMID  18617723.
13. Элден, Ларс; Парк, Хэсун (1 июня 1999 г.). «Проблема Прокруста на многообразии Штифеля». Numerische Mathematik. 82 (4): 599–619. CiteSeerX  10.1.1.54.3580. Дои:10.1007 / s002110050432.
14. Шёнеманн, Питер Х. (март 1966 г.). «Обобщенное решение проблемы ортогональных прокрастов». Психометрика. 31 (1): 1–10. Дои:10.1007 / BF02289451. HDL:10338.dmlcz / 103138.
15. Markopoulos, PP; Кунду, S; Chamadia, S; Цагкаракис, N; Падос, Д.А. (2018). Обработка данных с устойчивостью к выбросам с помощью анализа главных компонентов L1-Norm. Достижения в области анализа основных компонентов. п. 121. Дои:10.1007/978-981-10-6704-4_6. ISBN  978-981-10-6703-7.
16. Nie, F; Хуанг, Н; Дин, С; Луо, Дижун; Ван, Х (июль 2011 г.). «Робастный анализ главных компонент с нежадной максимизацией l1-нормы». 22-я международная совместная конференция по искусственному интеллекту: 1433–1438.
17. Маккой, Майкл; Тропп, Джоэл А. (2011). «Два предложения по надежному PCA с использованием полуопределенного программирования». Электронный статистический журнал. 5: 1123–1160. arXiv:1012.1086. Дои:10.1214 / 11-EJS636.
18. Маркопулос, стр. «Репозиторий программного обеспечения». Получено 21 мая, 2018.
19. Цагкаракис, Николай; Markopoulos, Panos P .; Скливанитис, Джордж; Падос, Димитрис А. (15 июня 2018 г.). "L1-Norm анализ главных компонентов сложных данных". Транзакции IEEE при обработке сигналов. 66 (12): 3256–3267. arXiv:1708.01249. Bibcode:2018ITSP ... 66.3256T. Дои:10.1109 / TSP.2018.2821641.
20. Chachlakis, Dimitris G .; Пратер-Беннетт, Эшли; Маркопулос, Панос П. (22 ноября 2019 г.). "L1-норма Tucker Tensor Decomposition". Доступ IEEE. 7: 178454–178465. Дои:10.1109 / ACCESS.2019.2955134.
21. Markopoulos, Panos P .; Chachlakis, Dimitris G .; Пратер-Беннетт, Эшли (21 февраля 2019 г.). "Сингулярная декомпозиция высших порядков L1-нормы". IEEE Proc. Глобальная конференция IEEE 2018 по обработке сигналов и информации. Дои:10.1109 / GlobalSIP.2018.8646385.
22. Markopoulos, Panos P .; Chachlakis, Dimitris G .; Папалексакис, Евангелос (апрель 2018 г.). «Точное решение для разложения TUCKER2 R-1-нормы L1». Письма об обработке сигналов IEEE. 25 (4). arXiv:1710.11306. Дои:10.1109 / LSP.2018.2790901.
23. "L1-PCA TOOLBOX". Получено 21 мая, 2018.