Elastiskt kort

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 mars 2021; kontroller kräver 2 redigeringar .

Den elastiska kartan används för icke-linjär reduktion av datadimensionen. I ett flerdimensionellt datarum finns en yta som approximerar de tillgängliga datapunkterna och som om möjligt inte är för böjd. Data projiceras på denna yta och kan sedan visas på den, som på en karta. Du kan tänka på det som en elastisk platta nedsänkt i datautrymmet och fäst vid datapunkter med fjädrar. Fungerar som en generalisering av huvudkomponentmetoden (där ett absolut styvt plan används istället för en elastisk platta).

Genom konstruktion är en elastisk karta ett system av elastiska fjädrar inbäddade i ett flerdimensionellt datarum [1] [5] . Detta system approximerar ett tvådimensionellt grenrör. Genom att ändra systemets elasticitetskoefficienter kan användaren byta från helt ostrukturerad K-means klustring (i gränsen för noll elasticitet ) till grenrör nära linjära huvudkomponentgrenrör (i gränsen för mycket stora böjmoduler och små dragmoduler). I det mellanliggande intervallet av värden för elasticitetskoefficienterna, approximerar systemet effektivt något icke-linjärt grenrör. Detta tillvägagångssätt är baserat på en analogi med mekanik: huvudgrenröret som passerar genom "mitten" av data kan representeras som ett elastiskt membran eller en platta. Metoden utvecklades av prof., A. N. Gorban , A. Zinoviev och A. Pitenko 1996-2001.

Elastisk energikarta

Låt datamängden representeras av en uppsättning vektorer i ett ändligt dimensionellt euklidiskt utrymme . En "elastisk karta" representeras av en uppsättning av dess noder i samma utrymme. För varje datapunkt definieras "värd"-noden (värd) som kartnoden närmast punkten (om det visar sig att det finns flera närmaste noder, väljs helt enkelt noden med det lägsta serienumret). Datauppsättningen är indelad i taxonklasser . $S$ $W_j$ $s\i S$ $W_j$ $S$ $K_{j}=\{s\ |\ W_{j}{\mbox{ är en mängd }}s\}$

Approximationsenergin är helt enkelt rotmedelkvadratavvikelsen från kartnoderna

D={\frac {1}{2}}\summa _{{j=1}}^{k}\summa _{{x\in K_{j}}}\|x-W_{j}\| ^{2},

eller, med andra ord, det finns fjädrarnas totala elastiska energi med en elasticitetskoefficient som förbinder varje datapunkt med dess "master"-nod.

Det är nödvändigt att införa följande ytterligare struktur på uppsättningen av noder. Vissa par av noder, , är förbundna med elastiska länk-ribbor. Låt oss beteckna uppsättningen av grafkanter som . Dessutom kommer vi att kombinera några trippel noder till "styvningar". Låt oss beteckna uppsättningen av förstyvningar som . $(W_{i},W_{j})$ $E$ $(W_{i},W_{j},W_{k})$ $G$

Spänningsenergin för en elastisk karta definieras som

U_{{E}}={\frac {1}{2}}\lambda \sum _{{(W_{i},W_{j})\in E}}\|W_{i}-W_{j }\|^{2};

Böjningsenergin hos ett elastiskt kort definieras som

U_{G}={\frac {1}{2}}\mu \sum _{{(W_{i},W_{j},W_{l})\in G}}\|W_{i}- 2W_{j}+W_{l}\|^{2};

var och är elasticitetskoefficienterna för spänning respektive böjning. $\lambda$ $\mu$

Till exempel, i fallet med ett tvådimensionellt rektangulärt rutnät av noder, är elastiska länkar vertikala och horisontella gitterkanter (par av närmaste hörn), medan förstyvningar är vertikala och horisontella trippel av på varandra följande (närmaste) noder.

Energin hos den elastiska kartan definieras som

U=D+U_{E}+U_{G}.

Vi kräver från infogningen av kartan att kartan är i mekanisk jämvikt: kartan måste minimera den elastiska energin . $U$

Förväntningsmaximeringsalgoritm ( EM-algoritm )

För en given uppdelning av datamängden i klasser reduceras minimeringen av den kvadratiska funktionalen till problemet att lösa ett system av linjära ekvationer med en gles matris av koefficienter. På samma sätt som den iterativa algoritmen för att konstruera huvudkomponenterna eller algoritmen för K-means- metoden, kan "delningstekniken" användas: $S$ $K_{j}$ $U$

För en given position av noder finner vi ; $\{W_{j}\}$ $\{K_{j}\}$
För en given partition minimerar vi och hittar ; $\{K_{j}\}$ $U$ $\{W_{j}\}$
Om konfigurationen av noderna ändras lite, avsluta processen, annars upprepa iterationen.

En sådan förväntningsmaximeringsalgoritm garanterar konvergens till ett lokalt minimum . För att förbättra approximationen kan olika ytterligare metoder användas: till exempel "mjukningsstrategin". Enligt denna teknik måste vi börja bygga en karta med ett mycket styvt system (små kantlängder, små böjar och stora värden på elasticitetskoefficienter och ), och slutföra konstruktionen med ett "flexibelt" system (små värden på och ). Träningen av kartan sker i flera steg, och varje steg kännetecknas av sin elasticitet. $U$ $\lambda$ $\mu$ $\lambda$ $\mu$

En annan variant av optimeringsstrategin kan kallas ett "växande rutnät": att bygga en karta börjar med ett litet antal noder, och fortsätter med det gradvisa tillägget av nya noder, följt av optimering av systempositionen i varje steg [5] .

Applikation

Metoden har funnit sina huvudsakliga tillämpningar inom bioinformatik [7] [8] , för explorativ analys och visualisering av flerdimensionell data, för datavisualisering inom ekonomi, sociologi och statsvetenskap [9] , som en hjälpmetod för att visualisera data av olika karaktär, knuten till ett geografiskt rutnät. På senare tid har metoden anpassats som ett verktyg för beslutsstödssystem för att välja, optimera och organisera lagerkorgar . [tio]

Anteckningar

↑ 1 2 A. N. Gorban, AY Zinovyev, Principal Graphs and Manifolds Archived September 6, 2008 at the Wayback Machine , Från: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods and Techniques, Olivas ES et al Eds. Information Science Reference, IGI Global: Hershey, PA, USA, 2009. 28-59.
↑ Wang, Y., Klijn, JG, Zhang, Y., Sieuwerts, AM, Look, MP, Yang, F., Talantov, D., Timmermans, M., Meijer-van Gelder, ME, Yu, J. et al. al.: Genuttrycksprofiler för att förutsäga fjärrmetastaser av lymfkörtelnegativ primär bröstcancer. Lancet 365, 671-679 (2005); Onlinedatauppsättning Arkiverad 17 juli 2011 på Wayback Machine
↑ A. Zinovyev, ViDaExpert Arkiverad 26 april 2012 på Wayback Machine - Multidimensional Data Visualization Tool. Institut Curie .
↑ A. Zinovyev, ViDaExpert-översikt Arkiverad 4 mars 2012 på Wayback Machine ( Institut des Hautes Études Scientifiques ).
↑ 1 2 A. Yu. Zinoviev. Visualisera multidimensionell data Arkiverad 13 juni 2008 på Wayback Machine . Krasnoyarsk: KSTU Publishing House, 2000. - 168 sid.
↑ AN Gorban, A. Zinovyev, Huvudsakliga grenrör och grafer i praktiken: från molekylärbiologi till dynamiska system Arkiverad 10 juni 2016 på Wayback Machine , International Journal of Neural Systems , Vol. 20, nej. 3 (2010) 219-232.
↑ AN Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), Principal Manifolds for Data Visualization and Dimension Reduction Arkiverad 6 mars 2019 på Wayback Machine , LNCSE 58, Springer: Berlin-Heidelberg-New York, 2007 ISBN 978-3-540-73749-0
↑ M. Chacón, M. Lévano, H. Allende, H. Nowak, Detektion av genuttryck i mikroarrayer genom att applicera iterativt elastiskt neuralt nät Arkiverad 24 augusti 2011 på Wayback Machine , I: B. Beliczynski et al. (Eds.), Lecture Notes in Computer Sciences, Vol. 4432, Springer: Berlin-Heidelberg 2007, 355-363.
↑ A. Zinovyev, Datavisualisering i statsvetenskap och samhällsvetenskap Arkiverad 26 augusti 2016 på Wayback Machine , I: SAGE Arkiverad 11 januari 2012 på Wayback Machine " International Encyclopedia of Political Science ", Badie, B., Berg-Schlosser, D ., Morlino, LA (red.), 2011.
↑ M. Resta, Portfolio optimization through elastic maps: Some evidence from the Italian Stock Exchange , Knowledge-Based Intelligent Information and Engineering Systems, B. Apolloni, RJ Howlett och L. Jain (red.), Lecture Notes in Computer Science, Vol. ... 4693, Springer: Berlin-Heidelberg, 2010, 635-641.