L1-նորմ հիմնական բաղադրիչների վերլուծություն

L1-նորմ հիմնական բաղադրիչի վերլուծությունը (L1-PCA) հանդիսանում է բազմաբնույթ տվյալների վերլուծության ընդհանուր մեթոդ[1]։ L1-PCA հաճախ ավելի նախընտրելի է ստանդարտ L2-նորմ հիմնական բաղադրիչը վերլուծությունից (PCA), երբ վերլուծած տվյալները պարունակում են հեռավոր կետեր(outliers) [2][3][4]։

L1-PCA-ի համեմատությունը PCA-ի հետ: Նոմինալ տվյալներ (կապույտ կետեր); հեռավոր կետեր (կարմիր կետ); PC (սև գիծ); L1-PC (կարմիր գիծ); նոմինալ առավելագույն վարիացիայի գիծ (կետագծեր):

Ինչպես L1-PCA- ն, այնպես էլ ստանդարտ PCA- ն փնտրում են ուղղահայաց ուղղություններ հիմնական բաղադրիչների համար, որոնք սահմանում են այն տեղը, որտեղ տվյալների ներկայացուցչությունը առավելագույնի հասցվում է ըստ ընտրված չափանիշի[5][6][7]։ Ստանդարտ PCA-ն տվյալների ներկայացումը քանակականացնում է որպես L2- նորմայի տվյալների պրոյեկցիաների ագրեգատ կամ սկզբնական կետերի և նրանց պրոյեկցիաների Էվկլիդյան հեռավորության համարժեք ագրեգատ։ L1-PCA- ն օգտագործում է L1- նորմայի կետերի պրոյեկցիաները[8]։ PCA և L1-PCA-ում հիմնական բաղադրիչների քանակը ավելի քիչ է, քան վերլուծված մատրիցի ռանգը։ Մատրիցը համընկնում է օրիգինալ կետերի միջոցով սահմանված տարածքի չափողականության հետ։ Այդ պատճառով, PCA- ն կամ L1-PCA- ն սովորաբար օգտագործվում են չափողականության իջեցման համար` տվյալների սեղմման կամ աղմուկը քչացնելու նպատակով։

Այնուամենայնիվ, ժամանակակից մեծ տվյալները հաճախ ներառում են հեռավոր կետեր(outlier)[3]։ Ստանդարտ PCA- ն զգայուն է հեռավոր կետերի նկատմամբ[9]։ Պատճառն այն է, որ L2-PCA-ի հիման վրա L2- նորմայի ձևավորումը քառակուսային շեշտադրում է կատարում յուրաքանչյուր կոորդինատի յուրաքանչյուր կետի մեծության վրա՝ ի վերջո գերագնահատելով ծայրամասային կետերը, ինչպիսիք են հեռավոր կետերը։ Մյուս կողմից, L1-norm-ի ձևակերպումից հետո L1-PCA- ն գծային շեշտադրում է կատարում յուրաքանչյուր կետի կոորդինատների վրա՝ արդյունավետորեն ՙՙզսպելով՚՚ հեռավոր կետերը[10]։

ՁևակերպումԽմբագրել

Դիտարկենք ցանկացած մատրիցա՝  , որը բաղկացած է   հատ  -չափանի կետերից։ Սահմանենք ռանգ՝  ։   ամբողջ թվի համար, որը  , L1-PCA- ն ձևակերպումն է ՝ [1]

 

  համար, ( 1 ) պարզեցնում է L1-norm-ի հիմնական բաղադրիչը (L1-PC)   գտնելը՝

 

( 1 ) - ( 2 ) բանաձևերում L1-norm   վերադարձնում է իր արգումենտների բացարձակ արժեքների գումարը։ L2-norm   վերադարձնում է իր արգումենտների քառակուսային արժեքների գումարը։ Եթե փոխարինենք   ( 2 ) բանաձևում ` Frobenius / L2-նորմայով   -ով, ապա խնդիրը դառնում է ստանդարտ PCA և այն լուծվում է  մատրիցով, որ պարունակում է   դոմինանտ եզակի  վեկտորներ (այսինքն, եզակի վեկտորներ, որոնք համապատասխանում են   առավելագույն եզակի արժեքներին)։

( 2 ) բանաձևում առավելագույնի չափումը կարելի է ընդլայնել՝

 

ԼուծումԽմբագրել

Ցանկացած մատրիցայի համար՝  , որտեղ , սահմանել   որպես ամենամոտ (L2-norm իմաստով) մատրից  , որն ունի օրթոնորմալ սյուներ։ Այսինքն՝

 

Procrustes թեորեմն [11][12] ասում է, որ եթե   ունի SVD  , ապա   .

Մարկոպուլոսը, Կարիստինոսը և Պադոսը [1] ցույց տվեցին, որ, եթե   երկուական միջուկային նորմայի առավելագույնի բարձրացման (BNM) խնդրի ճշգրիտ լուծումն է, ապա՝

 

ապա

 

( 2 )-ում L1-PCA- ի ճշգրիտ լուծումն է։ Միջուկային նորմ   ( 2 )-ում վերադառնում է իր մատրիցային արգումենտի եզակի արժեքների ամփոփումը և կարող է հաշվարկվել ստանդարտ SVD- ի միջիններով։ Ավելին, այն պնդում է, որ հաշվի առնելով L1-PCA լուծումը,  , BNM- ի լուծումը կարելի է ստանալ հետևյալ կերպ՝

 

որտեղ   վերադարձնում է իր մատրիցի արգումենտի   նշանի մատրից (ընդհանուր կորստի բացակայության դեպքում մենք կարող ենք դիտարկել, որ  ): Բացի այդ, դրանից հետևում է, որ   . BNM- ը ( 5 ) -ում կոմբինատորիկայի խնդիր է՝ կապված անտիպոդալ երկուական փոփոխականների հետ։ Հետևաբար, դրա ճշգրիտ լուծումը կարելի է գտնել բոլոր   էլեմենտների սպառիչ գնահատման միջոցով   ասիմպտոտիկ արժեքով։ Հետևաբար, L1-PCA- ն նույնպես կարող է լուծվել BNM- ի միջոցով`  -ով։ Պարզվում է, որ L1-PCA- ն հնարավոր է օպտիմալ կերպով (ճշգրիտ) լուծել`  -ում պոլինոմիալ բարդության դեպքում ֆիքսված  չափողականության համար ,   .[1]

Հատուկ դեպքում, երբ   (  միակ L1-PC), BNM- ն ընդունում է երկուական-քառակուսային-մաքսիմումի (BQM) ձևը

 

Անցումը ( 5 ) -ից ( 8 ) -ին, երբ  , ճշմարիտ է, քանի որ  -ի եզակի արժեքը հավասար է  , յուրաքանչյուրի   համար . Հետո, եթե   BQM-ի լուծումն է ( 7 ) -ում, այն ընդունում է հետևյալ տեսքը.

 

որը  -ի ճիշտ L1-PC- ն է, ինչպես սահմանված է ( 1 ) -ում։ Բացի այդ,   և   .

ԱլգորիթմներԽմբագրել

Էքսպոնենցիալ բարդության ճիշտ լուծումԽմբագրել

Ինչպես ցույց է տրված վերևում, L1-PCA-ի ճշգրիտ լուծումը կարելի է ստանալ հետևյալ երկաստիճան գործընթացով.

 1. Լուծեք խնդիրը ( 5 )-ում` ստանալու համար   .
 2. Կիրառել SVD   -ի վրա և ստանալ   .

Պոլինոմիալ բարդության ճշգրիտ լուծումԽմբագրել

L1-PCA- ն հնարավոր է օպտիմալ կերպով լուծել  , երբ   հաստատուն է  -ի նկատմամբ (միշտ ճիշտ է սահմանափակ   չափողականության համար)[1][13]։

Կոմպլեքս տվյալներԽմբագրել

L1-PCA- ն ընդհանրացվել է նաև կոմպլեքս տվյալների մշակման համար։ Կոմպլեքս L1-PCA-ի համար 2018-ին առաջարկվել է երկու արդյունավետ ալգորիթմ։ [14]

ԿոդԽմբագրել

L1-PCA-ի համար MATLAB կոդը հասանելի է MathWorks- ում [15] և այլ պահոցներում [16]։

ԾանոթագրություններԽմբագրել

  1. 1,0 1,1 1,2 1,3 1,4 Markopoulos Panos P., Karystinos George N., Pados Dimitris A. (October 2014)։ «Optimal Algorithms for L1-subspace Signal Processing»։ IEEE Transactions on Signal Processing 62 (19): 5046–5058։ Bibcode:2014ITSP...62.5046M։ arXiv:1405.6785։ doi:10.1109/TSP.2014.2338077 
  2. Barrodale I. (1968)։ «L1 Approximation and the Analysis of Data»։ Applied Statistics 17 (1): 51–57։ JSTOR 2985267։ doi:10.2307/2985267 
  3. 3,0 3,1 Barnett Vic, Lewis Toby (1994)։ Outliers in statistical data (3. ed.)։ Chichester [u.a.]: Wiley։ ISBN 978-0471930945 
  4. Kanade T., Ke Qifa (June 2005)։ Robust L1 Norm Factorization in the Presence of Outliers and Missing Data by Alternative Convex Programming։ 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) 1 (IEEE)։ էջ 739։ ISBN 978-0-7695-2372-9։ doi:10.1109/CVPR.2005.309 
  5. Jolliffe I.T. (2004)։ Principal component analysis (2nd ed.)։ New York: Springer։ ISBN 978-0387954424 
  6. Bishop Christopher M. (2007)։ Pattern recognition and machine learning (Corr. printing. ed.)։ New York: Springer։ ISBN 978-0-387-31073-2 
  7. Pearson Karl (հունիսի 8, 2010)։ «On Lines and Planes of Closest Fit to Systems of Points in Space»։ The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 2 (11): 559–572։ doi:10.1080/14786440109462720 
  8. Markopoulos Panos P., Kundu Sandipan, Chamadia Shubham, Pados Dimitris A. (օգոստոսի 15, 2017)։ «Efficient L1-Norm Principal-Component Analysis via Bit Flipping»։ IEEE Transactions on Signal Processing 65 (16): 4252–4264։ Bibcode:2017ITSP...65.4252M։ arXiv:1610.01959։ doi:10.1109/TSP.2017.2708023 
  9. Candès Emmanuel J., Li Xiaodong, Ma Yi, Wright John (մայիսի 1, 2011)։ «Robust principal component analysis?»։ Journal of the ACM 58 (3): 1–37։ arXiv:0912.3599։ doi:10.1145/1970392.1970395 
  10. Kwak N. (September 2008)։ «Principal Component Analysis Based on L1-Norm Maximization»։ IEEE Transactions on Pattern Analysis and Machine Intelligence 30 (9): 1672–1680։ PMID 18617723։ doi:10.1109/TPAMI.2008.114 
  11. Eldén Lars, Park Haesun (հունիսի 1, 1999)։ «A Procrustes problem on the Stiefel manifold»։ Numerische Mathematik 82 (4): 599–619։ doi:10.1007/s002110050432 
  12. Schönemann Peter H. (March 1966)։ «A generalized solution of the orthogonal procrustes problem»։ Psychometrika 31 (1): 1–10։ doi:10.1007/BF02289451 
  13. Markopoulos PP, Kundu S, Chamadia S, Tsagkarakis N, Pados DA (2018)։ Outlier-Resistant Data Processing with L1-Norm Principal Component Analysis։ Advances in Principal Component Analysis (Springer, Singapore)։ էջ 121։ ISBN 978-981-10-6703-7։ doi:10.1007/978-981-10-6704-4_6 
  14. Tsagkarakis Nicholas, Markopoulos Panos P., Sklivanitis George, Pados Dimitris A. (հունիսի 15, 2018)։ «L1-Norm Principal-Component Analysis of Complex Data»։ IEEE Transactions on Signal Processing 66 (12): 3256–3267։ Bibcode:2018ITSP...66.3256T։ arXiv:1708.01249։ doi:10.1109/TSP.2018.2821641 
  15. «L1-PCA TOOLBOX»։ Վերցված է May 21, 2018 
  16. Markopoulos PP։ «Software Repository»։ Վերցված է May 21, 2018 (չաշխատող հղում)