Jag tror att det inte är så mycket gleshet, utan den höga dimensionaliteten som vanligtvis är förknippad med glesa data. Men kanske är det ännu värre när uppgifterna är mycket glesa. Eftersom avståndet mellan två objekt sannolikt kommer att vara ett kvadratiskt medelvärde för deras längder, eller $$ \ lim_ {dim \ rightarrow \ infty} d (x, y) = || x-y || \ rightarrow_p \ sqrt {|| x || ^ 2 + || y || ^ 2} $$

Denna ekvation gäller triviellt om $ \ forall_i x_i = 0 \ vee y_i = 0 $. Om du ökar dimensionen och glesheten tillräckligt så att den rymmer nästan alla attribut, kommer skillnaden att vara minimal.

Ännu värre: om du normaliserade dina vektorer så att de hade längden $ || x || = 1 $ , då blir det euklidiska avståndet för två objekt $ \ sqrt {2} $ med hög sannolikhet.

Så som en tumregel, för att euklidiskt avstånd ska vara användbart Jag hävdar inte att det är användbart eller meningsfullt) objekten ska vara noll i attributen $ 3/4 $. Då borde det finnas ett rimligt antal attribut där $ | y_i | \ neq | x_i-y_i | \ neq | x_i | $ så att vektordifferensen blir användbar. Detta gäller också alla andra norminducerade skillnader. För i situationen över $ | x-y | \ rightarrow_p | x + y | $

Jag tror inte att detta är ett önskvärt beteende för avståndsfunktioner att bli till stor del oberoende av den faktiska skillnaden, eller den absoluta skillnaden som konvergerar till den absoluta summan!

En vanlig lösning är att använda avstånd såsom Cosine-avstånd. På vissa data fungerar de mycket bra. Grovt sett ser de bara på attribut där båda vektorerna inte är noll. Ett intressant tillvägagångssätt diskuteras i referensen nedan (de uppfann det inte, men jag gillar deras experimentella utvärdering av fastigheterna) är att använda delade närmaste grannar. Så även när vektorerna x och y inte har några attribut gemensamt kan de ha några vanliga grannar. Att räkna antalet objekt ansluta två objekt är nära relaterat till grafavstånd.

Det diskuteras mycket om avståndsfunktioner i:

• Kan avstånd från delade grannar besegra dimensionens förbannelse?
  M. E. Houle, H.-P. Kriegel, P. Kröger, E. Schubert och A. Zimek
  SSDBM 2010

och om du inte föredrar vetenskapliga artiklar, även på Wikipedia: Curse of Dimensionality

Jag föreslår att du börjar med Cosine-avstånd, inte euklidiskt, för data med de flesta vektorer nästan ortogonala, $ x \ cdot y \ cirka $ 0.
För att se varför, titta på $ | x - y | ^ 2 = | x | ^ 2 + | y ​​| ^ 2 - 2 \ x \ cdot y $.
Om $ x \ cdot y \ ungefär $ 0 minskar detta till $ | x | ^ 2 + | y ​​| ^ 2 $: ett smutsigt mått på avstånd, som Anony-Mousse påpekar.

Cosine-avstånd uppgår till att använda $ x / | x | $, eller att projicera data på ytan av enhetens sfär, så alla $ | x | $ = 1. Då $ | x - y | ^ 2 = 2 - 2 \ x \ cdot y $
en helt annan och vanligtvis bättre mått än vanlig euklidisk. $ x \ cdot y $ kan vara liten, men den maskeras inte av bullriga $ | x | ^ 2 + | y ​​| ^ 2 $.

$ x \ cdot y $ är mestadels nära 0 för glesa data. till exempel, om $ x $ och $ y $ har 100 termer som inte är noll och 900 nollor, kommer de båda att vara noll på bara cirka 10 termer (om termerna som inte är noll sprids slumpmässigt).

Normalisering av $ x $ / = $ | x | $ kan vara långsam för glesa data; det går snabbt i scikit-learning.

Sammanfattning: börja med cosinusavstånd, men förvänta dig inte under på gamla data.
Framgångsrika mätvärden kräver utvärdering, inställning, domän kunskap.

Här är ett enkelt leksaksexempel som illustrerar effekten av dimension i ett diskrimineringsproblem, t.ex. problemet du står inför när du vill säga om något observeras eller om bara slumpmässig effekt observeras (detta problem är en klassiker inom vetenskapen).

Heuristisk. Nyckelfrågan här är att den euklidiska normen ger samma betydelse för alla riktningar. Detta utgör en brist på tidigare, och som du säkert vet i hög dimension finns det ingen gratis lunch (dvs om du inte har någon tidigare uppfattning om vad du letar efter, så finns det ingen anledning till att lite buller inte skulle se ut som du är söker efter, detta är tautologi ...).

Jag skulle säga att det för alla problem finns en gräns för information som är nödvändig för att hitta något annat än buller. Denna gräns är på något sätt relaterad till "storleken" på det område du försöker utforska med avseende på "ljudnivån" (dvs. nivån på informativt innehåll).

I hög dimension, om du har tidigare att din signal är gles kan du ta bort (dvs straffa) icke gles vektor med ett mått som fyller utrymmet med gles vektor eller med hjälp av en tröskelvärde teknik.

Framework Anta att $ \ xi $ är en gaussisk vektor med genomsnittlig $ \ nu $ och diagonal kovarians $ \ sigma Id $ ($ \ sigma $ är känd) och att du vill testa den enkla hypotesen

$$ H_0: \; \ nu = 0, \; Vs \; H _ {\ theta}: \; \ nu = \ theta $$ (för en given $ \ theta \ i \ mathbb {R} ^ n $) $ \ theta $ är inte nödvändigtvis känd i förväg.

Testa statistik med energi . Intuitionen du verkligen har är att det är en bra idé att utvärdera normen / energin $ \ mathcal {E} _n = \ frac {1} {n} \ sum_ {i = 1} ^ n \ xi_i ^ 2 $ av dig observation $ \ xi $ för att bygga en teststatistik. Egentligen kan du konstruera en standardiserad centrerad (under $ H_0 $) version $ T_n $ av energin $ T_n = \ frac {\ sum_i \ xi_i ^ 2- \ sigma ^ 2} {\ sqrt {2n \ sigma ^ 4}} $ . Det gör en kritisk region på nivå $ \ alpha $ för formuläret $ \ {T_n \ geq v_ {1- \ alpha} \} $ för en väl vald $ v_ {1- \ alpha} $

Testets och dimensionens kraft. I det här fallet är det en enkel sannolikhetsövning att visa följande formel för kraften i ditt test:

$$ P _ {\ theta} (T \ leq v_ {1- \ alpha}) = P \ left (Z \ leq \ frac {v_ {1- \ alpha}} {\ sqrt {1 + 2 \ | \ theta \ | _2 ^ 2 / (n \ sigma ^ 2)}} - \ frac {\ | \ theta \ | ^ 2_2} {\ sqrt {2n \ sigma ^ 4 + 2 \ sigma ^ 2 \ | \ theta \ | _2 ^ 2 / (n \ sigma ^ 2)}} \ höger) $$ med $ Z $ en summa av $ n $ i slumpmässiga variabler med $ \ mathbb {E} [Z] = 0 $ och $ Var (Z) = 1 $.

Detta innebär att kraften i ditt test ökas med energin i din signal $ \ | \ theta \ | ^ 2_2 $ och minskas med $ n $. Praktiskt taget betyder det att när du ökar storleken $ n $ på ditt problem om det inte ökar signalens styrka samtidigt, lägger du till informativ information till din observation (eller så minskar du andelen användbar information i den information du har): det här är som att lägga till brus och minska testets kraft (dvs. det är mer troligt att du inte säger att något observeras medan det faktiskt finns något).

Mot ett test med en tröskelstatistik. Om du inte har mycket energi i din signal men om du känner till en linjär transformation som kan hjälpa dig att få denna energi koncentrerad till en liten del av din signal, då kan du bygga en teststatistik som bara utvärderar energin för den lilla delen av din signal. Om du i förväg visste var den är koncentrerad (till exempel visste du att det inte kan finnas höga frekvenser i din signal) kan du få en effekt i föregående test med $ n $ ersatt av ett litet antal och $ \ | \ theta \ | ^ 2_2 $ nästan samma ... Om du inte vet det i förväg måste du uppskatta det leder till välkända tröskelprov.

Observera att detta argument ligger precis till grund för många artiklar som

• A Antoniadis, F Abramovich, T Sapatinas och B Vidakovic. Wavelet-metoder för testning i funktionell analys av variansmodeller. International Journal on Wavelets and itsapplications, 93: 1007–1021, 2004.
• M. V. Burnashef och Begmatov. På ett problem med signalavkänning som leder till stabil distribution. Teori om sannolikhet och dess tillämpningar, 35 (3): 556–560, 1990.
• Y. Baraud. Icke asymptotisk minimax-hastighet för testning vid signaldetektering. Bernoulli, 8: 577–606, 2002.
• J Fan. Test av betydelse baserat på wavelet tröskelvärde och Neymans trunkering. JASA, 91: 674–688, 1996.
• J. Fläkt och S-K Lin. Test av betydelse när data är kurvor. JASA, 93: 1007–1021, 1998.
• V. Spokoiny. Adaptativ hypotesprovning med hjälp av wavelets. Annals of Statistics, 24 (6): 2477–2498, december 1996.

En del av dimensionalitetens förbannelse är att data börjar spridas bort från centrum. Detta gäller för multivariat normalt och även när komponenterna är IID (sfäriska normala). Men om du strikt vill tala om euklidiskt avstånd även i lågdimensionellt utrymme om data har en korrelationsstruktur är euklidiskt avstånd inte lämpligt mått. Om vi ​​antar att uppgifterna är multivariata normala med vissa icke-nollkovarianter och för argumentets skull antar att kovariansmatrisen är känd. Då är Mahalanobis-avståndet lämpligt avståndsmått och det är inte detsamma som euklidiskt avstånd som det bara skulle minska till om kovariansmatrisen är proportionell mot identitetsmatrisen.

Jag tror att detta är relaterat till förbannelsen av dimensionalitet / måttkoncentration men jag kan inte längre hitta den diskussion som motiverar denna anmärkning. Jag tror att det fanns en tråd om metaoptimering men jag misslyckades med att Google det ...

För textdata kommer normalisering av vektorerna med TF-IDF och sedan tillämpning av cosinuslikhet förmodligen att ge bättre resultat än euklidiskt avstånd så länge dokument (med många ord) kan dela samma ämnen och därför mycket liknar korta dokument som delar ett stort antal vanliga ord. Att kassera normerna för vektorerna hjälper i det specifika fallet.

Ett axiomatiskt mått på sparsity är det så kallade $ \ ell_0 $ -antalet, som räknar (slutligt) antal poster som inte är noll i en vektor. Med detta mått, vektorer $ (1,0,0,0) $ och $ (0,21,0,0 ) $ har samma gleshet. Och absolut inte samma $ \ ell_2 $ norm. Och $ (1,0,0,0) $ (mycket gles) har samma $ \ ell_2 $ span > norm som $ \ left (\ frac {1} {4}, \ frac {1} {4}, \ frac {1} {4}, \ frac {1} { 4} \ höger) $ , en mycket platt, icke-gles vektor. Och absolut inte samma $ \ ell_0 $ -antal.

Den här funktionen, varken en norm eller en quasinorm, är icke-smidig och icke-konvex. Beroende på domän är dess namn legion, till exempel: kardinalitetsfunktion, måttlighet eller helt enkelt parsimon eller gleshet. Det anses ofta vara opraktiskt för praktiska ändamål eftersom dess användning leder till NP-hårda problem.

Medan standardavstånd eller normer (som $ \ ell_2 $ Euklidiska avståndet) är mer smidiga, en av deras problem är deras $ 1 $ -homogenitet: $$ \ | a.x \ | = | a | \ | x \ | $$ för $ a \ neq 0 $ . Detta kan ses som icke-intuitivt, eftersom den skalära produkten inte ändrar andelen nollposter i data ( $ \ ell_0 $ är $ 0 $ -homogen).

Så i praktiken, resurs till kombinationer av $ \ ell_p (x) $ termer ( $ p \ ge1 $ ), såsom lasso, ås eller elastiska nätregulariseringar. Normen $ \ ell_1 $ (Manhattan eller Taxicab-avstånd) eller dess utjämnade avatarer är särskilt användbar. Eftersom verk av E. Candès och andra kan man förklara Varför $ \ ell_1 $ är en bra uppskattning till $ \ ell_0 $ : En geometrisk förklaring. Andra har gjort $ p < 1 $ i $ \ ell_p (x) $ , till priset av icke -konvexitetsfrågor.

En annan intressant väg är att återaxiomisera begreppet sparsity. Ett av de senaste anmärkningsvärda verken är Comparing Measures of Sparsity, av N. Hurley et al., Som handlar om sparsity i distributioner. Från sex axiomer (med roliga namn som Robin Hood, Scaling, Rising Tide, Cloning, BillGates och Babies) framkom ett par sparsitetsindex: en baserad på Gini-index, en annan på normförhållanden, särskilt en-över-två $ \ frac {\ ell_1} {\ ell_2} $ normförhållande, visas nedan:

Även om de inte är konvexa, beskrivs vissa konvergensbevis och några historiska referenser i Euclid i en taxikåpa: Sparse Blind Deconvolution with Smoothed $ \ frac {\ ell _1} {\ ell_2} $ Regularisering. Några pseudonorm / normförhållanden $ \ ell_p / \ ell_q $ finns i SPOQ ℓp-Over-ℓq Regularization for Sparse Signal Recovery tillämpas på masspektrometri.

Papperet Om det överraskande beteendet hos avståndsmetriker i högdimensionellt utrymme diskuterar beteendet hos avståndsmätvärden i högdimensionella utrymmen.

De tar på sig $ L_k $ -normen och föreslå Manhattan $ L_1 $ -norm som den mest effektiva i högdimensionella utrymmen för klustringsändamål. De introducerar också en fraktionsnorm $ L_f $ som liknar $ L_k $ -normen men med $ f \ in (0..1) $.

Kort sagt visar de att för högdimensionella utrymmen med den euklidiska normen som standard är förmodligen inte en bra idé; vi har vanligtvis lite intuition i sådana utrymmen, och den exponentiella sprängningen på grund av antalet dimensioner är svår att ta hänsyn till med det euklidiska avståndet.