Niet -lineaire dimensionaliteitsvermindering

Hoog-dimensionaal Gegevens, wat betekent dat gegevens die meer dan twee of drie dimensies moeten vertegenwoordigen, kunnen zijn, kunnen zijn Moeilijk te interpreteren. Een benadering van vereenvoudiging is om aan te nemen dat de gegevens van interesse in een lagere dimensionale ruimte liggen. Als de gegevens van interesse van voldoende dimensie zijn, kunnen de gegevens worden gevisualiseerd in de laagdimensionale ruimte.

Linksboven: een 3D-gegevensset van 1000 punten in een spiraalvormige band (ook bekend als de Zwitserse rol) met een rechthoekig gat in het midden. Rechtsrecht: het originele 2D-verdeelstuk dat wordt gebruikt om de 3D-gegevensset te genereren. Linksonder en rechts: 2d herstel van het verdeelstuk respectievelijk met behulp van de LLE en Hessian Lle Algoritmen zoals geïmplementeerd door de modulaire gegevensverwerkingstoolkit.

Hieronder is een samenvatting van enkele opmerkelijke methoden voor niet -lineaire dimensionaliteitsvermindering.^[1][2] Veel van deze niet-lineair dimensionaliteitsvermindering Methoden zijn gerelateerd aan de lineaire methoden die hieronder worden vermeld. Niet-lineaire methoden kunnen in grote lijnen worden ingedeeld in twee groepen: die die een mapping bieden (hetzij van de hoog-dimensionale ruimte tot de lage dimensionale inbedding of vice versa), en die die alleen een visualisatie geven.

Gerelateerde lineaire ontledingsmethoden

• Onafhankelijke componentanalyse (ICA)
• Hoofdcomponentanalyse (PCA) - Ook wel genoemd Karhunen - Loève stelling- KLT
• Singuliere waarden ontbinding (SVD)
• Factoren analyse

Toepassingen van NLDR

Overweeg een dataset weergegeven als een matrix (of een databasetabel), zodat elke rij een set attributen (of functies of dimensies) vertegenwoordigt die een bepaald exemplaar van iets beschrijven. Als het aantal attributen groot is, is de ruimte met unieke mogelijke rijen exponentieel groot. Dus, hoe groter de dimensionaliteit, hoe moeilijker het wordt om de ruimte te proeven. Dit veroorzaakt veel problemen. Algoritmen die werken op hoog-dimensionale gegevens hebben de neiging om een ​​zeer hoog tijdcomplexiteit te hebben. Veel machine learning-algoritmen worstelen bijvoorbeeld met hoog-dimensionale gegevens. Het verminderen van gegevens in minder dimensies maakt analyse -algoritmen vaak efficiënter en kan helpen bij het helpen van machine learning -algoritmen.

Mensen hebben vaak moeite om gegevens in hoge dimensies te begrijpen. Het verminderen van gegevens tot een klein aantal dimensies is dus nuttig voor visualisatiedoeleinden.

Plot van de tweedimensionale punten die het gevolg zijn van het gebruik van een NLDR-algoritme. In dit geval wordt spruitstukculptuur gebruikt om de gegevens te verminderen tot slechts twee dimensies (rotatie en schaal).

De gereduceerde dimensionale weergaven van gegevens worden vaak "intrinsieke variabelen" genoemd. Deze beschrijving houdt in dat dit de waarden zijn waaruit de gegevens zijn geproduceerd. Overweeg bijvoorbeeld een gegevensset die afbeeldingen bevat van een letter 'A', die is geschaald en gedraaid door verschillende hoeveelheden. Elke afbeelding heeft 32x32 pixels. Elke afbeelding kan worden weergegeven als een vector van 1024 pixelwaarden. Elke rij is een monster op een tweedimensionaal verdeelstuk in 1024-dimensionale ruimte (a Hameringsruimte). De intrinsieke dimensionaliteit is twee, omdat twee variabelen (rotatie en schaal) werden gevarieerd om de gegevens te produceren. Informatie over de vorm of het uiterlijk van een letter 'a' maakt geen deel uit van de intrinsieke variabelen omdat deze in elk geval hetzelfde is. Niet -lineaire dimensionaliteitsvermindering zal de gecorreleerde informatie (de letter 'A') weggooien en alleen de verschillende informatie (rotatie en schaal) herstellen. De afbeelding rechts toont voorbeeldafbeeldingen uit deze dataset (om ruimte te besparen, niet alle invoerafbeeldingen worden getoond), en een plot van de tweedimensionale punten die het gevolg is van het gebruik van een NLDR-algoritme (in dit geval werd het beeldhouwen van verdeelstuk gebruikt) Om de gegevens te verminderen in slechts twee dimensies.

PCA (een lineair dimensionaliteitsreductie -algoritme) wordt gebruikt om dezelfde dataset te verminderen tot twee dimensies, de resulterende waarden zijn niet zo goed georganiseerd.

Ter vergelijking, als Hoofdcomponentanalyse, wat een lineair dimensionaliteitsreductie -algoritme is, wordt gebruikt om dezelfde dataset te verminderen tot twee dimensies, de resulterende waarden zijn niet zo goed georganiseerd. Dit toont aan dat de hoog-dimensionale vectoren (die elk een letter 'a' vertegenwoordigen) dat dit verdeelstuk op een niet-lineaire manier varieert.

Het moet daarom duidelijk zijn dat NLDR verschillende toepassingen heeft op het gebied van computervisie. Overweeg bijvoorbeeld een robot die een camera gebruikt om in een gesloten statische omgeving te navigeren. De beelden verkregen door die camera kunnen worden beschouwd als monsters op een verdeelstuk in hoog-dimensionale ruimte, en de intrinsieke variabelen van dat verdeelstuk zullen de positie en oriëntatie van de robot vertegenwoordigen.

Invariant spruitstukken zijn van algemeen belang voor modelorderreductie in dynamische systemen. In het bijzonder, als er een aantrekkende invariant verdeelstuk in de faseruimte is, zullen in de buurt van de nabijgelegen trajecten zich ermee convergeren en er voor onbepaalde tijd aan blijven, waardoor het een kandidaat maakt voor dimensionaliteitsreductie van het dynamische systeem. Hoewel dergelijke verdeelstukken in het algemeen niet zijn gegarandeerd, zijn de theorie van Spectral Submanifolds (SSM) geeft voorwaarden voor het bestaan ​​van unieke aantrekkende invariante objecten in een brede klasse van dynamische systemen.^[3] Actief onderzoek in NLDR probeert de observatieverdeelstukken te ontvouwen die zijn geassocieerd met dynamische systemen om modelleringstechnieken te ontwikkelen.^[4]

Sommige van de meer prominente niet -lineaire dimensionaliteitsvermindering Technieken worden hieronder vermeld.

Belangrijke concepten

Sammon's mapping

Sammon's mapping is een van de eerste en populairste NLDR -technieken.

Benadering van een hoofdcurve door eendimensionaal Somber (a gebroken lijn met rode vierkanten, 20 knooppunten). De eerste hoofdcomponent wordt gepresenteerd door een blauwe rechte lijn. Gegevenspunten zijn de kleine grijze cirkels. Voor PCA, de Fractie van variantie onverklaarbaar In dit voorbeeld is 23,23%, voor SOM is het 6,86%.^[5]

Zelforganiserende kaart

De Zelforganiserende kaart (Som, ook wel genoemd Kohonen -kaart) en zijn probabilistische variant generatieve topografische mapping (GTM) Gebruik een puntrepresentatie in de ingebedde ruimte om een ​​te vormen Latent variabel model Gebaseerd op een niet-lineaire mapping van de ingebedde ruimte naar de hoog-dimensionale ruimte.^[6] Deze technieken zijn gerelateerd aan werk op dichtheidsnetwerken, die ook zijn gebaseerd op hetzelfde probabilistische model.

Kernel hoofdcomponentanalyse

Misschien wel het meest veelgebruikte algoritme voor dimensionale reductie is kernel pca.^[7] PCA begint met het berekenen van de covariantiematrix van de ${\ displaystyle m \ maal n}$ Matrix ${\ DisplayStyle \ Mathbf {x}}$

${\ displaystyle c = {\ frac {1} {m}} \ sum _ {i = 1}^{m} {\ mathbf {x} _ {i} \ mathbf {x} _ _ {i}^{\ mathsf {T}}}.}$

Het projecteert vervolgens de gegevens op de eerste k Eigenvectoren van die matrix. Ter vergelijking: KPCA begint met het berekenen van de covariantiematrix van de gegevens nadat hij is omgezet in een hoger-dimensionale ruimte,

${\ displaystyle c = {\ frac {1} {m}} \ sum _ {i = 1}^{m} {\ phi (\ mathbf {x} _ {i}) \ phi (\ mathbf {x} _ {i})^{\ Mathsf {t}}}.}$

Het projecteert vervolgens de getransformeerde gegevens op de eerste k Eigenvectoren van die matrix, net als PCA. Het gebruikt de kerneltruc om een ​​groot deel van de berekening weg te laten, zodat het hele proces kan worden uitgevoerd zonder daadwerkelijk te berekenen ${\ DisplayStyle \ Phi (\ Mathbf {x})}$. Natuurlijk ${\ DisplayStyle \ Phi}$ moet zodanig worden gekozen dat het een bekende bijbehorende kernel heeft. Helaas is het niet triviaal om een ​​goede kernel te vinden voor een bepaald probleem, dus KPCA levert geen goede resultaten op met sommige problemen bij het gebruik van standaardkorrels. Het is bijvoorbeeld bekend dat het slecht presteert met deze kernels op de Zwitserse rol verdeelstuk. Men kan echter bepaalde andere methoden bekijken die goed presteren in dergelijke instellingen (bijv. Laplacian Eigenmaps, LLE) als speciale gevallen van kernel PCA door een gegevensafhankelijke kernelmatrix te construeren.^[8]

KPCA heeft een intern model, dus het kan worden gebruikt om punten toe te wijzen aan de inbedding ervan die niet beschikbaar waren tijdens de trainingstijd.

Hoofdcurven en spruitstukken

Toepassing van hoofdcurves: niet -lineaire kwaliteit van leven index.^[9] Punten vertegenwoordigen gegevens van de VN 171 landen in 4-dimensionale ruimte gevormd door de waarden van 4 indicatoren: Bruto product per hoofd van de bevolking, levensverwachting, kindersterfte, tuberculose incidentie. Verschillende vormen en kleuren komen overeen met verschillende geografische locaties. Red Bold -lijn vertegenwoordigt de hoofdcurve, het benaderen van de gegevensset. Deze hoofdcurve werd geproduceerd door de methode van elastische kaart. Software is beschikbaar voor gratis niet-commercieel gebruik.^[10][11]

Hoofdcurven en spruitstukken Geef het natuurlijke geometrische raamwerk voor niet -lineaire dimensionaliteitsvermindering en breid de geometrische interpretatie van PCA uit door expliciet een ingebed verdeelstuk te construeren, en door te coderen met behulp van standaard geometrische projectie op het verdeelstuk. Deze benadering werd oorspronkelijk voorgesteld door Trevor Hastie In zijn stelling van 1984,^[12] die hij formeel introduceerde in 1989.^[13] Dit idee is door veel auteurs verder onderzocht.^[14] Hoe de "eenvoud" van het verdeelstuk te definiëren is probleemafhankelijk, maar het wordt vaak gemeten door de intrinsieke dimensionaliteit en/of de gladheid van het verdeelstuk. Gewoonlijk wordt het belangrijkste verdeelstuk gedefinieerd als een oplossing voor een optimalisatieprobleem. De objectieve functie omvat een kwaliteit van gegevensbenadering en enkele boetes voor het buigen van het spruitstuk. De populaire initiële benaderingen worden gegenereerd door lineaire PCA en Kohonen's SOM.

Laplacian Eigenmaps

Laplacian Eigenmaps gebruikt spectrale technieken om dimensionaliteitsreductie uit te voeren.^[15] Deze techniek is gebaseerd op de basisaanname dat de gegevens in een laagdimensionaal verdeelstuk liggen in een hoog-dimensionale ruimte.^[16] Dit algoritme kan geen uit-sample punten insluiten, maar technieken gebaseerd op Reproduceren van kernel Hilbert -ruimte Regularisatie bestaat voor het toevoegen van deze mogelijkheid.^[17] Dergelijke technieken kunnen ook worden toegepast op andere niet -lineaire dimensionaliteitsreductie -algoritmen.

Traditionele technieken zoals principale componentanalyse beschouwen de intrinsieke geometrie van de gegevens niet. Laplacian Eigenmaps bouwt een grafiek uit buurtinformatie van de gegevensset. Elk gegevenspunt dient als een knooppunt op de grafiek en connectiviteit tussen knooppunten wordt bepaald door de nabijheid van aangrenzende punten (met behulp van bijvoorbeeld de K-hemelse buuralgoritme). De aldus gegenereerde grafiek kan worden beschouwd als een discrete benadering van het laagdimensionale verdeelstuk in de hoog-dimensionale ruimte. Minimalisatie van een kostenfunctie op basis van de grafiek zorgt ervoor dat punten dicht bij elkaar op het verdeelstuk dicht bij elkaar worden toegewezen in de laagdimensionale ruimte, waardoor lokale afstanden worden behouden. De eigenfuncties van de Laplace - Beltrami -operator op het verdeelstuk dienen als de inbedding afmetingen, omdat onder milde omstandigheden deze operator een telbaar spectrum heeft dat een basis is voor vierkante integreerbare functies op het verdeelstuk (vergelijk met Fourier -serie op de eenheid Circle -verdeelstuk). Pogingen om Laplaciaanse eigenmaps op vaste theoretische grond te plaatsen, hebben enig succes gehad, omdat is aangetoond dat de grafiek Laplaciaanse matrix onder bepaalde niet -beperkende veronderstellingen is, is aangetoond dat de Laplace -Beltrami -operator convergeert naar de Laplace -Beltrami -operator.^[16]

Isomap

Isomap^[18] is een combinatie van de Floyd -Warshall -algoritme met klassieker Multidimensionale schaling. Klassieke multidimensionale schaalverdeling (MDS) neemt een matrix van paarsgewijze afstanden tussen alle punten en berekent een positie voor elk punt. Isomap veronderstelt dat de paarsgewijze afstanden alleen bekend zijn tussen aangrenzende punten en het Floyd-Warshall-algoritme gebruikt om de paarsgewijze afstanden tussen alle andere punten te berekenen. Dit schat effectief de volledige matrix van paars geodetische afstanden tussen alle punten. Isomap gebruikt vervolgens klassieke MDS om de gereduceerde dimensionale posities van alle punten te berekenen. Landmark-isomap is een variant van dit algoritme dat oriëntatiepunten gebruikt om de snelheid te verhogen, ten koste van enige nauwkeurigheid.

Bij verdeelstukken leren wordt verondersteld dat de invoergegevens zijn bemonsterd uit een laag dimensionaal verdeelstuk die is ingebed in een hoger-dimensionale vectorruimte. De belangrijkste intuïtie achter MVU is om de lokale lineariteit van spruitstukken te benutten en een mapping te creëren die lokale buurten op elk punt van het onderliggende verdeelstuk behoudt.

Lokaal lineaire inbedding

Lokaal lineaire inbedding (LLE)^[19] werd op ongeveer dezelfde tijd gepresenteerd als Isomap. Het heeft verschillende voordelen ten opzichte van Isomap, waaronder snellere optimalisatie wanneer geïmplementeerd om te profiteren van schaarse matrix Algoritmen en betere resultaten met veel problemen. LLE begint ook met het vinden van een set van de dichtstbijzijnde buren van elk punt. Het berekent vervolgens een reeks gewichten voor elk punt dat het punt het beste beschrijft als een lineaire combinatie van zijn buren. Ten slotte gebruikt het een op eigenvector gebaseerde optimalisatietechniek om de laagdimensionale inbedding van punten te vinden, zodat elk punt nog steeds wordt beschreven met dezelfde lineaire combinatie van zijn buren. LLE heeft de neiging om niet-uniforme monsterdichtheden slecht te verwerken, omdat er geen vaste eenheid is om te voorkomen dat de gewichten drijven omdat verschillende gebieden verschillen in monsterdichtheden. LLE heeft geen intern model.

Lle berekent de barycentrische coördinaten van een punt X_i Gebaseerd op zijn buren X_j. Het oorspronkelijke punt wordt gereconstrueerd door een lineaire combinatie, gegeven door de gewichtsmatrix W_IJ, van zijn buren. De reconstructiefout wordt gegeven door de kostenfunctie E(W).

${\ displaystyle e (w) = \ sum _ {i} | {\ mathbf {x} _ {i}-\ sum _ {j} {\ mathbf {w} _ {iJ} \ Mathbf {x} _ _ {j }} |}^{\ Mathsf {2}}}$

De gewichten W_IJ Raadpleeg de hoeveelheid bijdrage het punt X_j heeft tijdens het reconstrueren van het punt X_i. De kostenfunctie wordt geminimaliseerd onder twee beperkingen: (a) elk gegevenspunt X_i wordt alleen gereconstrueerd van zijn buren, waardoor ze worden gehandhaafd W_IJ om nul te zijn als het punt is X_j is geen buurman van het punt X_i en (b) de som van elke rij van de gewichtsmatrix is ​​gelijk aan 1.

${\ displaystyle \ sum _ {j} {\ mathbf {w} _ {ij}} = 1}$

De originele gegevenspunten worden verzameld in een D Dimensionale ruimte en het doel van het algoritme is om de dimensionaliteit te verminderen d zoals dat D >> d. Dezelfde gewichten W_IJ die de ihet gegevenspunt in de D Dimensionale ruimte zal worden gebruikt om hetzelfde punt in de onderste te reconstrueren d Dimensionale ruimte. Op basis van dit idee wordt een kaart voor het behoud van de buurt gemaakt. Elk punt x_i in de D Dimensionale ruimte wordt in kaart gebracht op een punt y_i in de d Dimensionale ruimte door de kostenfunctie te minimaliseren

${\ displaystyle c (y) = \ sum _ {i} | {\ mathbf {y} _ {i}-\ sum _ {j} {\ mathbf {w} _ {iJ} \ Mathbf {y} _ _ _ {j }} |}^{\ Mathsf {2}}}$

In deze kostenfunctie, in tegenstelling tot de vorige, de gewichten w_IJ worden vastgehouden en de minimalisatie wordt gedaan op de punten y_i om de coördinaten te optimaliseren. Dit minimalisatieprobleem kan worden opgelost door een schaars op te lossen N X N Eigen waardeprobleem (N het aantal gegevenspunten zijn), wiens onderkant d Niet -nul eigen vectoren bieden een orthogonale set coördinaten. Over het algemeen worden de gegevenspunten gereconstrueerd van K dichtstbijzijnde buren, zoals gemeten door Euclidische afstand. Voor een dergelijke implementatie heeft het algoritme slechts één gratis parameter K, die kan worden gekozen door kruisvalidatie.

Hessian Lokaal-lineaire inbedding (Hessian LLE)

Net als LLE is Hessian LLE ook gebaseerd op schaarse matrixtechnieken.^[20] Het heeft de neiging om resultaten op te leveren van een veel hogere kwaliteit dan LLE. Helaas heeft het een zeer dure computationele complexiteit, dus het is niet goed geschikt voor zwaar bemonsterde spruitstukken. Het heeft geen intern model.

Gemodificeerde lokaal lineaire inbedding (MLLE)

Modified lle (mlle)^[21] is een andere LLE -variant die meerdere gewichten in elke buurt gebruikt om het lokale gewichtsmatrixconditioneringsprobleem aan te pakken dat leidt tot vervormingen in LLE -kaarten. Losjes gesproken De meerdere gewichten zijn de lokale orthogonale projectie van de originele gewichten geproduceerd door LLE. De makers van deze geregulariseerde variant zijn ook de auteurs van de lokale raakruimte-uitlijning (LTSA), die impliciet is in de MLLE-formulering bij het beseffen dat de globale optimalisatie van de orthogonale projecties van elke gewichtsvector, in-essence, de lokale raakruimtes in lijn brengt van elk gegevenspunt. De theoretische en empirische implicaties van de juiste toepassing van dit algoritme zijn verreikend.^[22]

Lokale raaklijnruimte -uitlijning

HET IS EEN^[23] is gebaseerd op de intuïtie dat wanneer een verdeelstuk correct wordt ontvouwd, alle raakhyperplanes van het verdeelstuk uit zijn uitgelijnd. Het begint met het berekenen van de k-Earste buren van elk punt. Het berekent de raakruimte op elk punt door de d-First hoofdcomponenten in elke lokale buurt. Vervolgens optimaliseert het om een ​​inbedding te vinden die de raakruimtes uitlijnt.

Maximale variantie die zich ontvouwt

Maximale variantie die zich ontvouwt, Isomap en lokaal lineaire inbedding delen een gemeenschappelijke intuïtie die afhankelijk is van het idee dat als een verdeelstuk correct wordt ontvouwd, de variantie over de punten wordt gemaximaliseerd. De eerste stap, zoals Isomap en lokaal lineaire inbedding, is het vinden van de k-Earste buren van elk punt. Het probeert dan het probleem op te lossen van het maximaliseren van de afstand tussen alle niet-nationale punten, zodanig beperkt dat de afstanden tussen aangrenzende punten worden bewaard. De primaire bijdrage van dit algoritme is een techniek om dit probleem als een semidefinietprogrammeringsprobleem te werpen. Helaas hebben Semidefinite -programmeeroplossers hoge rekenkosten. Net als lokaal lineaire inbedding heeft het geen intern model.

Autoencoders

Een autoencoder is een feed-forward neuraal netwerk die is getraind om de identiteitsfunctie te benaderen. Dat wil zeggen, het is getraind om van een vector van waarden naar dezelfde vector in kaart te brengen. Bij gebruik voor dimensionaliteitsreductiedoeleinden is een van de verborgen lagen in het netwerk beperkt om slechts een klein aantal netwerkeenheden te bevatten. Het netwerk moet dus leren om de vector in een klein aantal dimensies te coderen en vervolgens terug te decoderen in de oorspronkelijke ruimte. Aldus is de eerste helft van het netwerk een model dat in kaart brengt van hoge naar laag-dimensionale ruimte, en de tweede helft kent uit van lage tot hoog-dimensionale ruimte. Hoewel het idee van autoencoders vrij oud is, is de training van diepe autoencoders pas recent mogelijk geworden door het gebruik van Beperkte Boltzmann -machines en gestapelde Denoising Autoencoders. Gerelateerd aan Autoencoders is het Neuroschaal -algoritme, dat stressfuncties gebruikt geïnspireerd door multidimensionale schaling en Sammon -toewijzingen (zie hierboven) om een ​​niet-lineaire mapping te leren van de hoog-dimensionale naar de ingebedde ruimte. De toewijzingen in NeuroSaal zijn gebaseerd op Radiale basisfunctienetwerken. Een ander gebruik van een neuraal netwerk voor dimensionaliteitsvermindering is om het de raakvlakken in de gegevens te laten leren.^[24]

Gaussiaans proces latente variabele modellen

Gaussiaanse proces latente variabele modellen (GPLVM)^[25] zijn probabilistische dimensionaliteitsreductiemethoden die Gaussiaanse processen (GPS) gebruiken om een ​​lagere dimensionale niet-lineaire inbedding van hoge dimensionale gegevens te vinden. Ze zijn een uitbreiding van de probabilistische formulering van PCA. Het model wordt probabilistisch gedefinieerd en de latente variabelen worden vervolgens gemarginaliseerd en parameters worden verkregen door de waarschijnlijkheid te maximaliseren. Net als kernel PCA gebruiken ze een kernelfunctie om een ​​niet -lineaire mapping te vormen (in de vorm van een Gaussiaans proces). In de GPLVM is de mapping echter van de ingebedde (latente) ruimte tot de gegevensruimte (zoals dichtheidsnetwerken en GTM), terwijl het in kernel PCA in de tegenovergestelde richting is. Oorspronkelijk werd het voorgesteld voor visualisatie van hoge dimensionale gegevens, maar is uitgebreid om een ​​gedeeld verdeelstukmodel tussen twee observatie -ruimtes te construeren. GPLVM en zijn vele varianten zijn speciaal voorgesteld voor menselijke bewegingsmodellering, bijvoorbeeld terug beperkte GPLVM, GP Dynamic Model (GPDM), gebalanceerde GPDM (B-GPDM) en topologisch beperkte GPDM. Om het koppelingseffect van de pose- en loopverdeelstukken in de loopanalyse vast te leggen, werd een meerlagige gewrichtsspoorspruitstukken voorgesteld.^[26]

T-verdeeld stochastische buur

T-verdeeld stochastische buur (T-SNE)^[27] wordt veel gebruikt. Het is een van een familie van stochastische buurman inbedding methoden. Het algoritme berekent de kans dat paren datapunten in de hoog-dimensionale ruimte gerelateerd zijn en vervolgens kiest voor laagdimensionale inbeddings die een vergelijkbare verdeling produceren.

Andere algoritmen

Relationele perspectiefkaart

Relationele perspectiefkaart is een multidimensionale schaling algoritme. Het algoritme vindt een configuratie van gegevenspunten op een verdeelstuk door een dynamisch systeem met meerdere delen op een gesloten spruitstuk te simuleren, waarbij gegevenspunten worden toegewezen aan deeltjes en afstanden (of ongelijkheid) tussen datapunten vertegenwoordigen een afstotelijke kracht. Naarmate het verdeelstuk geleidelijk in grootte groeit, koelt het multi-deeltjessysteem geleidelijk af en convergeert naar een configuratie die de afstandsinformatie van de gegevenspunten weerspiegelt.

Relationele perspectiefkaart werd geïnspireerd door een fysiek model waarin positief geladen deeltjes vrij op het oppervlak van een bal bewegen. Begeleid door de Coulomb kracht Tussen deeltjes zal de minimale energieconfiguratie van de deeltjes de sterkte van afstotende krachten tussen de deeltjes weerspiegelen.

De relationele perspectiefkaart werd geïntroduceerd in.^[28] Het algoritme gebruikte eerst de flat torus Als het beeldspruitstuk is het vervolgens uitgebreid (in de software Visumap om andere soorten gesloten verdeelstukken te gebruiken, zoals de gebied, projectieve ruimte, en Klein -fles, als beeldspruitstukken.

Besmettingskaarten

Besmettingskaarten gebruiken meerdere besmettingen op een netwerk om de knooppunten als een puntwolk in kaart te brengen.^[29] In het geval van de Globaal Cascades -model De snelheid van de spread kan worden aangepast met de drempelparameter ${\ displaystyle t \ in [0,1]}$. Voor ${\ displaystyle t = 0}$ De besmettkaart is gelijk aan de Isomap algoritme.

Curvilinear Component Analyse

Curvilinear Component Analysis (CCA) zoekt naar de configuratie van punten in de uitvoerruimte die de oorspronkelijke afstanden zoveel mogelijk behoudt, terwijl ze zich concentreert op kleine afstanden in de uitvoerruimte (omgekeerd naar Sammon's mapping die zich richten op kleine afstanden in de oorspronkelijke ruimte).^[30]

Opgemerkt moet worden dat CCA, als een iteratief leeralgoritme, eigenlijk begint met focus op grote afstanden (zoals het Sammon -algoritme), en vervolgens geleidelijk de focus in kleine afstanden verandert. De kleine afstandsinformatie zal de grote afstandsinformatie overschrijven, als er een compromis tussen de twee moeten worden gesloten.

De stressfunctie van CCA is gerelateerd aan een som van de rechter Bregman -afwijkingen.^[31]

Curvilineaire afstandsanalyse

CDA^[30] Train een zelforganiserend neuraal netwerk om bij het verdeelstuk te passen en probeert te behouden geodetische afstanden in zijn inbedding. Het is gebaseerd op Curvilinear Component -analyse (die de mapping van Sammon heeft uitgebreid), maar gebruikt in plaats daarvan geodetische afstanden.

Diffeomorfe dimensionaliteitsvermindering

Difeomorfe Dimensionaliteitsvermindering of Difeomap^[32] Leert een soepele diffeomorfe mapping die de gegevens naar een lager-dimensionale lineaire subruimte transporteert. De methoden lost op voor een soepele tijd geïndexeerd vectorveld zodat stromen langs het veld die beginnen bij de gegevenspunten eindigen op een lager-dimensionale lineaire subruimte, waardoor het probeert paarsgewijze verschillen te behouden onder zowel de voorwaartse als omgekeerde mapping.

Uitlijning van vele uitlijning

Uitlijning van vele uitlijning profiteert van de veronderstelling dat verschillende gegevenssets die door vergelijkbare genererende processen worden geproduceerd, een vergelijkbare onderliggende verstandelijke weergave zullen delen. Door de projecties van elke originele ruimte naar het gedeelde verdeelstuk te leren, worden correspondenties teruggewonnen en kunnen kennis van het ene domein worden overgedragen naar het andere. De meeste vele -uitlijningstechnieken overwegen slechts twee gegevenssets, maar het concept strekt zich uit tot willekeurig veel initiële gegevenssets.^[33]

Diffusiekaarten

Diffusiekaarten maakt gebruik van de relatie tussen warmte diffusie en een willekeurige wandeling (Markov -keten); Een analogie wordt getrokken tussen de diffusieoperator op een verdeelstuk en een Markov -overgangsmatrix die werkt op functies die zijn gedefinieerd op de grafiek waarvan de knooppunten werden bemonsterd uit het verdeelstuk.^[34] Laat een gegevensset in het bijzonder worden weergegeven door ${\ DisplayStyle \ Mathbf {x} = [x_ {1}, x_ {2}, \ ldots, x_ {n}] \ in \ omega \ subset \ mathbf {r^{d}}}$. De onderliggende veronderstelling van diffusiekaart is dat de hoog-dimensionale gegevens liggen op een laagdimensionaal verdeelstuk van dimensie ${\ DisplayStyle \ Mathbf {d}}$. Laten X vertegenwoordigen de gegevensset en ${\ DisplayStyle \ mu}$ vertegenwoordigen de verdeling van de gegevenspunten op X. Definieer verder een kernel die een idee van affiniteit van de punten in vertegenwoordigt X. De kernel ${\ DisplayStyle {\ Mathit {k}}}$ heeft de volgende eigenschappen^[35]

${\ displaystyle k (x, y) = k (y, x), \,}$

k is symmetrisch

${\ displaystyle k (x, y) \ geq 0 \ qquad \ forall x, y, k}$

k is positiviteit bewaren

Zo kan men de afzonderlijke gegevenspunten beschouwen als de knooppunten van een grafiek en de kernel k als het definiëren van een soort affiniteit op die grafiek. De grafiek is symmetrisch door constructie omdat de kernel symmetrisch is. Het is gemakkelijk om hier te zien dat van de tuple (X,k) Men kan een omkeerbaar construeren Markov -keten. Deze techniek is gebruikelijk voor verschillende gebieden en staat bekend als de grafiek Laplacian.

Bijvoorbeeld de grafiek K = (X,E) kan worden geconstrueerd met behulp van een Gaussiaanse kernel.

${\ displaystyle k_ {iJ} = {\ begin {cases} e^{-\ | x_ {i} -x_ {j} \ | _ {2}^{2}/\ sigma^{2}} & {{\ text {if}} x_ {i} \ sim x_ {j} \\ 0 & {\ text {anders}} \ end {cases}}}$

In de bovenstaande vergelijking, ${\ displaystyle x_ {i} \ sim x_ {j}}$ geeft dat aan ${\ DisplayStyle x_ {i}}$ is een naaste buur van ${\ DisplayStyle X_ {J}}$. Naar behoren, Geodetisch Afstand moet worden gebruikt om afstanden op de verdeelstuk. Aangezien de exacte structuur van het verdeelstuk niet beschikbaar is, wordt de geodetafstand voor de dichtstbijzijnde buren benaderd door Euclidische afstand. De keuze ${\ DisplayStyle \ Sigma}$ moduleert ons idee van nabijheid in de zin dat als ${\ displaystyle \ | x_ {i} -x_ {j} \ | _ {2} \ gg \ sigma}$ dan ${\ displaystyle k_ {ij} = 0}$ en als ${\ displaystyle \ | x_ {i} -x_ {j} \ | _ {2} \ ll \ sigma}$ dan ${\ displaystyle k_ {ij} = 1}$. De eerste betekent dat er weinig diffusie heeft plaatsgevonden, terwijl deze laatste impliceert dat het diffusieproces bijna voltooid is. Verschillende strategieën om te kiezen ${\ DisplayStyle \ Sigma}$ kan gevonden worden in.^[36]

Om trouw een Markov -matrix te vertegenwoordigen, ${\ displaystyle k}$ moet worden genormaliseerd door de overeenkomstige graadmatrix ${\ DisplayStyle D}$:

${\ displaystyle p = d^{-1} K. \,}$

${\ displaystyle p}$ vertegenwoordigt nu een Markov -keten. ${\ displaystyle p (x_ {i}, x_ {j})}$ is de kans om over te schakelen van ${\ DisplayStyle x_ {i}}$ tot ${\ DisplayStyle X_ {J}}$ in een tijdstap. Evenzo de waarschijnlijkheid van overgang van ${\ DisplayStyle x_ {i}}$ tot ${\ DisplayStyle X_ {J}}$ in t Tijdstappen worden gegeven door ${\ displaystyle p^{t} (x_ {i}, x_ {j})}$. Hier ${\ displaystyle p^{t}}$ is de matrix ${\ displaystyle p}$ Vermenigvuldigd met zichzelf t keer.

De Markov -matrix ${\ displaystyle p}$ vormt een idee van lokale geometrie van de gegevensset X. Het grote verschil tussen diffusiekaarten en Hoofdcomponentanalyse is dat alleen lokale kenmerken van de gegevens worden overwogen in diffusiekaarten in plaats van het nemen van correlaties van de gehele gegevensset.

${\ displaystyle k}$ Definieert een willekeurige wandeling op de gegevensset, wat betekent dat de kernel enkele lokale geometrie van gegevensset vastlegt. De Markov -keten definieert snelle en langzame voortplantingsrichtingen door de kernelwaarden. Terwijl de wandeling zich in de tijd voortplant, aggregeert de lokale geometrie -informatie op dezelfde manier als lokale overgangen (gedefinieerd door differentiaalvergelijkingen) van het dynamische systeem.^[35] De metafoor van diffusie komt voort uit de definitie van een familiediffusieafstand {${\ displaystyle d_ {t}}$}${\ displaystyle _ {t \ in n}}$

${\ displaystyle d_ {t}^{2} (x, y) = || p_ {t} (x, \ cdot) -p_ {t} (y, \ cdot) ||^{2}}$

Voor vaste t, ${\ displaystyle d_ {t}}$ Definieert een afstand tussen twee punten van de gegevensset op basis van padconnectiviteit: de waarde van ${\ displaystyle d_ {t} (x, y)}$ zal kleiner zijn, hoe meer paden die verbinding maken x tot y en vice versa. Omdat de hoeveelheid ${\ displaystyle d_ {t} (x, y)}$ omvat een som van alle paden van lengte t, ${\ displaystyle d_ {t}}$ is veel robuuster voor ruis in de gegevens dan geodetische afstand. ${\ displaystyle d_ {t}}$ houdt rekening met alle relatie tussen punten X en Y terwijl de afstand wordt berekend en dient als een beter idee van nabijheid dan alleen Euclidische afstand of zelfs geodetische afstand.

Lokale multidimensionale schaal

Lokale multidimensionale schaalvoordelen presteert multidimensionale schaling in lokale regio's, en gebruikt vervolgens convexe optimalisatie om alle stukken in elkaar te passen.^[37]

Niet -lineaire PCA

Niet -lineaire PCA (NLPCA) gebruikt backpropagatie om een ​​meerlagige perceptron (MLP) te trainen om in een verdeelstuk te passen.^[38] In tegenstelling tot typische MLP -training, die alleen de gewichten bijwerkt, werkt NLPCA zowel de gewichten als de ingangen bij. Dat wil zeggen, zowel de gewichten als de ingangen worden als latente waarden behandeld. Na de training zijn de latente inputs een laag-dimensionale weergave van de waargenomen vectoren, en de MLP-kaarten van die lage-dimensionale weergave naar de hoog-dimensionale observatieruimte.

Gegevensgestuurde hoog-dimensionale schaling

Gegevensgestuurde hoge dimensionale schaalverdeling (DD-HDS)^[39] is nauw verwant aan Sammon's mapping en curvilineaire componentanalyse behalve dat (1) het tegelijkertijd valse buurten en tranen bestraft door zich te concentreren op kleine afstanden in zowel originele als uitvoerruimte, en dat (2) het is goed meetconcentratie Fenomeen door de wegingsfunctie aan te passen aan de afstandsverdeling.

Mevendeel beeldhouwen

Mevendeel beeldhouwen^[40] toepassingen Afgestudeerde optimalisatie om een ​​inbedding te vinden. Net als andere algoritmen berekent het de k-Enerste buren en probeert een inbedding te zoeken die relaties in lokale buurten behoudt. Het schaalt langzaam de variantie uit hogere dimensies, terwijl het tegelijkertijd punten in lagere dimensies aanpast om die relaties te behouden. Als de schaalsnelheid klein is, kan het zeer precieze inbeddings vinden. Het heeft een hogere empirische nauwkeurigheid dan andere algoritmen met verschillende problemen. Het kan ook worden gebruikt om de resultaten te verfijnen van andere algoritmen voor het leren van verdeelstukken. Het worstelt echter om enkele verdeelstukken te ontvouwen, tenzij een zeer langzame schaalsnelheid wordt gebruikt. Het heeft geen model.

Rankvisu

Rankvisu^[41] is ontworpen om de rang van buurt in plaats van afstand te behouden. Rankvisu is vooral nuttig voor moeilijke taken (wanneer het behoud van afstand niet bevredigend kan worden bereikt). De rang van de buurt is inderdaad minder informatief dan afstand (rangen kunnen worden afgeleid van afstanden, maar afstanden kunnen niet uit de gelederen worden afgeleid) en het behoud ervan is dus gemakkelijker.

Topologisch beperkte isometrische inbedding

Topologisch beperkte isometrische inbedding (TCIE)^[42] is een algoritme gebaseerd op het benaderen van geodetische afstanden na het filteren van geodesica dat niet consistent is met de Euclidische metriek. Gericht op het corrigeren van de vervormingen die worden veroorzaakt wanneer Isomap wordt gebruikt om intrinsiek niet-convexe gegevens in kaart te brengen, gebruikt TCIE het gewicht van de minste kwadraten van het gewicht om een ​​meer accurate mapping te verkrijgen. Het TCIE -algoritme detecteert eerst mogelijke grenspunten in de gegevens, en tijdens de berekening van de geodetische lengte markeert inconsistente geodesica, om een ​​klein gewicht te krijgen in de gewogen Stressmajoralisatie dat volgt.

Uniforme verdeelstukbenadering en projectie

Uniforme verdeelstukbenadering en projectie (UMAP) is een niet -lineaire dimensionaliteitsreductietechniek.^[43] Visueel is het vergelijkbaar met t-SNE, maar het gaat ervan uit dat de gegevens uniform zijn verdeeld over een lokaal verbonden Riemanniaans verdeelstuk en dat de Riemanniaanse metriek is lokaal constant of ongeveer lokaal constant.^[44]

Methoden op basis van nabijheidsmatrices

Een methode gebaseerd op nabijheidsmatrices is er een waarbij de gegevens worden gepresenteerd aan het algoritme in de vorm van een gelijkenismatrix of een afstandsmatrix. Deze methoden vallen allemaal onder de bredere klasse van Metrische multidimensionale schaling. De variaties zijn meestal verschillen in hoe de nabijheidsgegevens worden berekend; bijvoorbeeld, Isomap, Lokaal lineaire inbeddings, Maximale variantie die zich ontvouwt, en Sammon Mapping (wat in feite geen kaart is) zijn voorbeelden van metrische multidimensionale schaalmethoden.

Zie ook

• Meventegale hypothese
• Spectraal submanifold
• Takens stelling
• Whitney Inbedding theorem
• Discriminerende analyse
• Elastische kaart
• Feature leren
• Groeiende zelforganiserende kaart (GSOM)
• Zelforganiserende kaart (Som)

Referenties

Externe links

• Isomap
• Generatieve topografische mapping
• Mike Tipping's scriptie
• Gaussiaans proces latente variabel model
• Lokaal lineaire inbedding
• Relationele perspectiefkaart
• Wafels is een open source C ++ -bibliotheek met implementaties van LLE, verdeelstuksculpting en enkele andere algoritmen voor verdeelstukken.
• DD-HDS HOMEPAGE
• RANKVISU HOMEPAGE
• Kort overzicht van diffusiekaarten
• Niet -lineaire PCA door Autoencoder neurale netwerken