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

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

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

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

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

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

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

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

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

Հատուկ դեպքում, երբ  ( միակ L1-PC), BNM- ն ընդունում է երկուական-քառակուսային-մաքսիմումի (BQM) ձևը  Անցումը (  ) -ից (  ) -ին, երբ , ճշմարիտ է, քանի որ -ի  եզակի արժեքը  հավասար է , յուրաքանչյուրի  համար  . Հետո, եթե  BQM-ի լուծումն է (  ) -ում, այն ընդունում է հետևյալ տեսքը.  որը -ի ճիշտ L1-PC- ն է, ինչպես սահմանված է (  ) -ում։ Բացի այդ,  և  .

Ալգորիթմներ

Էքսպոնենցիալ բարդության ճիշտ լուծում 
Ինչպես ցույց է տրված վերևում, L1-PCA-ի ճշգրիտ լուծումը կարելի է ստանալ հետևյալ երկաստիճան գործընթացով. 
  1. Լուծեք խնդիրը (  )-ում` ստանալու համար  .
  2. Կիրառել SVD  -ի վրա և ստանալ  .

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

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

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

Ծանոթագրություններ 

Տվյալների վերլուծություն
Pages with unreviewed translations