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

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

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- ն գծային շեշտադրում է կատարում յուրաքանչյուր կետի կոորդինատների վրա՝ արդյունավետորեն ՙՙզսպելով՚՚ հեռավոր կետերը։

Ձևակերպում

Դիտարկենք ցանկացած մատրիցա՝ $𝐗=[{𝐱}_1,{𝐱}_2,\dots ,{𝐱}_N]\in {ℝ}^{D\times N}$, որը բաղկացած է $N$ հատ $D$-չափանի կետերից։ Սահմանենք ռանգ՝ $r=rank(𝐗)$։ $K$ ամբողջ թվի համար, որը $1\le K<r$, L1-PCA- ն ձևակերպումն է՝ Կաղապար:NumBlk

$K=1$ համար, ( Կաղապար:Eqref ) պարզեցնում է L1-norm-ի հիմնական բաղադրիչը (L1-PC) $𝐗$ գտնելը՝ Կաղապար:EF ( Կաղապար:Eqref ) - ( Կաղապար:Eqref ) բանաձևերում L1-norm $\Vert \cdot {\Vert }_1$ վերադարձնում է իր արգումենտների բացարձակ արժեքների գումարը։ L2-norm $\Vert \cdot {\Vert }_2$ վերադարձնում է իր արգումենտների քառակուսային արժեքների գումարը։ Եթե փոխարինենք $\Vert \cdot {\Vert }_1$ ( Կաղապար:Eqref ) բանաձևում ` Frobenius / L2-նորմայով $\Vert \cdot {\Vert }_F$ -ով, ապա խնդիրը դառնում է ստանդարտ PCA և այն լուծվում է $𝐐$մատրիցով, որ պարունակում է $K$ դոմինանտ եզակի $𝐗$վեկտորներ (այսինքն, եզակի վեկտորներ, որոնք համապատասխանում են $K$ առավելագույն եզակի արժեքներին)։

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

Լուծում

Ցանկացած մատրիցայի համար՝ $𝐀\in {ℝ}^{m\times n}$, որտեղ$m\ge n$, սահմանել $\mathrm{\Phi }(𝐀)$ որպես ամենամոտ (L2-norm իմաստով) մատրից $𝐀$, որն ունի օրթոնորմալ սյուներ։ Այսինքն՝ Կաղապար:EF Procrustes թեորեմն ասում է, որ եթե $𝐀$ ունի SVD ${𝐔}_{m\times n}{\mathrm{\Sigma }}_{n\times n}{𝐕}_{n\times n}^{\mathrm{\top }}$, ապա $\mathrm{\Phi }(𝐀)=𝐔{𝐕}^{\mathrm{\top }}$ .

Մարկոպուլոսը, Կարիստինոսը և Պադոսը ցույց տվեցին, որ, եթե ${𝐁}_{\text{BNM}}$ երկուական միջուկային նորմայի առավելագույնի բարձրացման (BNM) խնդրի ճշգրիտ լուծումն է, ապա՝ Կաղապար:EF ապա Կաղապար:EF ( Կաղապար:Eqref )-ում L1-PCA- ի ճշգրիտ լուծումն է։ Միջուկային նորմ $\Vert \cdot {\Vert }_{*}$ ( Կաղապար:Eqref )-ում վերադառնում է իր մատրիցային արգումենտի եզակի արժեքների ամփոփումը և կարող է հաշվարկվել ստանդարտ SVD- ի միջիններով։ Ավելին, այն պնդում է, որ հաշվի առնելով L1-PCA լուծումը, ${𝐐}_{\text{L1}}$, BNM- ի լուծումը կարելի է ստանալ հետևյալ կերպ՝ Կաղապար:EF որտեղ $\text{sgn}(\cdot )$ վերադարձնում է իր մատրիցի արգումենտի $\{\pm 1\}$ նշանի մատրից (ընդհանուր կորստի բացակայության դեպքում մենք կարող ենք դիտարկել, որ $\text{sgn}(0)=1$): Բացի այդ, դրանից հետևում է, որ $\Vert {𝐗}^{\mathrm{\top }}{𝐐}_{\text{L1}}{\Vert }_1=\Vert 𝐗{𝐁}_{\text{BNM}}{\Vert }_{*}$ . BNM- ը ( Կաղապար:Eqref ) -ում կոմբինատորիկայի խնդիր է՝ կապված անտիպոդալ երկուական փոփոխականների հետ։ Հետևաբար, դրա ճշգրիտ լուծումը կարելի է գտնել բոլոր $2^{NK}$ էլեմենտների սպառիչ գնահատման միջոցով $𝒪(2^{NK})$ ասիմպտոտիկ արժեքով։ Հետևաբար, L1-PCA- ն նույնպես կարող է լուծվել BNM- ի միջոցով` $𝒪(2^{NK})$-ով։ Պարզվում է, որ L1-PCA- ն հնարավոր է օպտիմալ կերպով (ճշգրիտ) լուծել` $N$-ում պոլինոմիալ բարդության դեպքում ֆիքսված $D$չափողականության համար , $𝒪(N^{rK-K+1})$ .

Հատուկ դեպքում, երբ $K=1$ ($𝐗$ միակ L1-PC), BNM- ն ընդունում է երկուական-քառակուսային-մաքսիմումի (BQM) ձևը Կաղապար:EF Անցումը ( Կաղապար:Eqref ) -ից ( Կաղապար:Eqref ) -ին, երբ $K=1$, ճշմարիտ է, քանի որ $𝐗𝐛$-ի եզակի արժեքը հավասար է $\Vert 𝐗𝐛{\Vert }_2=\sqrt{{𝐛}^{\mathrm{\top }}{𝐗}^{\mathrm{\top }}𝐗𝐛}$, յուրաքանչյուրի $𝐛$ համար . Հետո, եթե ${𝐛}_{\text{BNM}}$ BQM-ի լուծումն է ( Կաղապար:Eqref ) -ում, այն ընդունում է հետևյալ տեսքը. Կաղապար:EF որը $𝐗$-ի ճիշտ L1-PC- ն է, ինչպես սահմանված է ( Կաղապար:Eqref ) -ում։ Բացի այդ, ${𝐛}_{\text{BNM}}=\text{sgn}({𝐗}^{\mathrm{\top }}{𝐪}_{\text{L1}})$ և $\Vert {𝐗}^{\mathrm{\top }}{𝐪}_{\text{L1}}{\Vert }_1=\Vert 𝐗{𝐛}_{\text{BNM}}{\Vert }_2$ .

Ալգորիթմներ

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

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

 1. Լուծեք խնդիրը ( Կաղապար:Eqref )-ում` ստանալու համար ${𝐁}_{\text{BNM}}$ .
 2. Կիրառել SVD  $𝐗{𝐁}_{\text{BNM}}$-ի վրա և ստանալ ${𝐐}_{\text{L1}}$ .

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

L1-PCA- ն հնարավոր է օպտիմալ կերպով լուծել $𝒪(N^{rK-K+1})$, երբ $r=rank(𝐗)$ հաստատուն է $N$-ի նկատմամբ (միշտ ճիշտ է սահմանափակ $D$ չափողականության համար)։

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

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

Կոդ

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