Kvantklustring

Ej att förväxla med Quantum Computing .

Quantum Clustering (QC) är en klass av dataklustringsalgoritmer som använder konceptuella och matematiska verktyg från kvantmekaniken . QC tillhör familjen av densitetsbaserade klustringsalgoritmer , där kluster definieras av regioner med högre täthet av datapunkter.

QC utvecklades först av David Horn och Assaf Gottlieb 2001.

Original Quantum Clustering Algoritm

Givet en uppsättning punkter i ett n-dimensionellt datautrymme, representerar QC varje punkt med en flerdimensionell Gauss-fördelning , med bredd (standardavvikelse) sigma, centrerad vid varje punkts plats i rummet. Dessa Gausser läggs sedan ihop för att skapa en enda distribution för hela datamängden. (Detta steg är ett särskilt exempel på kärndensitetsuppskattning , ofta kallad en Parzen-Rosenblatt-fönsterestimator.) Denna fördelning anses vara den kvantmekaniska vågfunktionen för datamängden. Löst sett är vågfunktionen en generaliserad beskrivning av var det sannolikt finns datapunkter i rymden.

QC introducerar sedan idén om en kvantpotential ; med hjälp av den tidsoberoende Schrödinger-ekvationen konstrueras en potentiell yta som har datamängden vågfunktion som en stabil lösning. Detaljer i den potentiella ytan är mer robusta mot förändringar i sigma (bredden på Gausserna) än motsvarande detaljer i vågfunktionen; denna fördel är en av de första motiven för utvecklingen av QC.

Den potentiella ytan anses vara datauppsättningens 'landskap', där 'låga' punkter i landskapet motsvarar områden med hög datatäthet. QC använder sedan gradientnedstigning för att flytta varje datapunkt "nedåt" i landskapet, vilket gör att punkter samlas i närliggande minima , vilket avslöjar kluster i datamängden.

QC har en enda huvudhyperparameter , som är sigmabredden för den Gaussiska fördelningen runt varje datapunkt. För tillräckligt liten sigma kommer varje datapunkt att definiera sin egen fördjupning i landskapet, och inga punkter kommer att röra sig, vilket skapar inga kluster. För tillräckligt stor sigma blir landskapet en enda slät skål, och varje datapunkt kommer att samlas vid det enda globala minimumet i landskapet. Att utforska intervallet av sigmavärden mellan dessa ytterligheter ger information om datauppsättningens inneboende struktur, inklusive strukturhierarki; mindre sigmavärden avslöjar mer finkornig lokal struktur, och större sigmavärden avslöjar övergripande global struktur. QC-algoritmen specificerar inte ett föredraget eller "korrekt" värde för sigma.

Dynamisk kvantkluster

Dynamic Quantum Clustering (DQC ) utvecklades av Marvin Weinstein och David Horn 2009 och utökar den grundläggande QC-algoritmen på flera sätt.

Quantum Evolution, Non-Local Gradient Descent och Tunneling

DQC använder samma potentiella landskap som QC, men det ersätter klassisk gradientnedstigning med kvantutveckling. För att göra detta representeras varje datapunkt återigen av sin individuella vågfunktion (en flerdimensionell Gauss-fördelning med breddsigma). Den tidsberoende Schrödinger-ekvationen används sedan för att beräkna varje vågfunktions utveckling över tiden i den givna kvantpotentialen. Närmare bestämt introduceras ett litet tidsstegsvärde, och utvecklingen av vågfunktionen beräknas upprepade gånger vid varje tidssteg, med en ny förväntad plats för datapunkten beräknad efter varje steg. Denna process bygger en bana genom datautrymmet för varje punkt; utvecklingen fortsätter tills alla punkter har slutat röra sig.

Viktigt är att Ehrenfest-satsen från kvantmekaniken säger att denna kvantevolution faktiskt motsvarar punkten som rör sig nedför i det potentiella landskapet, i förväntan. Delen "i förväntan" är viktig eftersom, till skillnad från i klassisk fysik, punktens rörelse inte bara påverkas av gradienten av potentialen vid punktens plats; istället sträcker sig punktens vågfunktion över hela landskapet (med Gauss centrerad vid punktens läge), och en komplex interaktion mellan vågfunktionen och potentialen bestämmer punktens rörelse. Som en lös analogi: regioner i landskapet som är under punktens nuvarande läge "attraherar" punkten - ju mer desto lägre är regionen, men desto mindre desto längre bort från punkten är den. På samma sätt "avvisar" högre delar av landskapet punkten.

Kvantutvecklingen för varje punkt fungerar således som en form av icke-lokal gradientnedstigning i potentialen. Denna icke-lokalitet skapar möjligheten till tunnling , där en punkt verkar ignorera eller passera genom en potentiell barriär på väg mot ett lägre minimum. Det största problemet vid icke-konvex gradientnedstigning är ofta förekomsten av många små och ointressanta lokala minima där punkter kan fastna när de sjunker. (Detta problem tenderar att bli värre när antalet dimensioner ökar, vilket är en del av dimensionalitetens förbannelse .) DQC:s användning av icke-lokal gradientnedstigning och tunnling presenterar en lösning på detta problem.

DQC introducerar två nya hyperparametrar: tidssteget och massan för varje datapunkt (som styr graden av tunnlingsbeteende). Medan inställning av sigma är en integrerad del för att förstå alla nya datamängder, kan både tidssteg och massa vanligtvis lämnas på rimliga standardvärden och fortfarande ge användbara resultat.

En viktig nackdel med kvantevolutionsmetoden är att tidskomplexiteten för evolutionen nu är i antalet datapunkter, eftersom den interagerar med hela det potentiella landskapet är för varje punkt. För stora datamängder skulle beräkningstiden snabbt bli svåröverskådlig. När det behövs åtgärdar DQC detta problem genom att välja ett begränsat antal punkter från datamängden som bas ( se nästa avsnitt).

Användning av begränsad grund

För en datamängd med n punkter skapar DQC en uppsättning av n kvantegentillstånd för användning i dess underliggande beräkningar; egentillstånden är ortonormala och var och en är en linjär kombination av Gaussfördelningarna som representerar varje datapunkt.

För stort n blir användningen av n egentillstånd beräkningsmässigt svårhanterlig, eftersom skapandet av potentialen och utvecklingen av individuella punkter båda är . För att lösa detta problem tillåter DQC valet av en mer begränsad grund, enligt följande. För att fungera som bas väljs b datapunkter (b < n) så att baspunkterna spänner över utrymmet som upptas av datamängden. (Detta kan göras på flera sätt; det väsentliga målet är att välja baspunkterna så att de är så långt borta från varandra som möjligt.) DQC konstruerar sedan b egentillstånd med hjälp av dessa b baspunkter. Dessa egentillstånd representerar baspunkterna perfekt; de används också för att representera alla icke-baspunkter, men dessa representationer kommer att vara ofullkomliga. Förlusten av information är relativt till sigma; för en given bas måste sigma väljas tillräckligt stor för att basen kan användas för att representera icke-baspunkter med någon rimlig grad av noggrannhet. På sätt och vis kan storleken på den valda basen ses som den "upplösning" som används för att "se" strukturen av datan.

Den största rimliga basstorleken beror på tillgängliga datorresurser och på hur länge man är villig att vänta på resultat. Från och med 2020, utan tillgång till datorresurser på företagsnivå, är den största möjliga basstorleken vanligtvis i intervallet 1 500-2 000 poäng.

Användning av dynamisk visualisering

DQC beräknar en bana för varje datapunkt, vilket möjliggör skapandet av en animerad ('dynamisk') visualisering där alla datapunkter rör sig längs sina banor samtidigt. Dessa animationer presenterar information inte bara i slutdestinationen för varje punkt, utan i varje hel bana längs vägen. Animeringar kan särskilt avslöja förekomsten av kanaler som leder till ett givet kluster. (I landskapsmetaforen kan dessa strukturer ses som flodbäddar och sjöar.) Även om en given visualisering är begränsad till högst 3 rumsliga dimensioner, skapar utseendet på kanaler och andra strukturer förmågan att "se" vad som händer i mer än 3 dimensioner.

Användning av ett PCA- koordinatsystem är till hjälp för dessa visualiseringar; att titta på banorna i de tre första PCA-dimensionerna packar så mycket information som möjligt i en enda visualisering.

En given 3D-visualisering av dessa banor är inte en inbäddning av banorna i 3 dimensioner. Banorna har samma dimensionalitet som datautrymmet, som ofta är mycket större än 3; visualiseringen är helt enkelt en 3D-vy till en högre dimensionell rörelse.

Kanalerna ('flodbäddar') kan ha betydelse på 2 olika sätt. För det första kan de behandlas som subkluster, där olika subkluster ansluter sig till huvudklustret från olika håll. För det andra kan de behandlas som regressioner: position längs kanalen vid en given tidpunkt (eller motsvarande ordning för ankomst till klustercentrum) kan korreleras med vissa metadata av intresse.

Ansökningar

Varianter av QC har tillämpats på verkliga data inom många områden, inklusive biologi, geologi, fysik, finans, teknik och ekonomi. Med dessa applikationer har också en omfattande matematisk analys för att hitta alla rötter till kvantpotentialen utarbetats.

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Quantum_clustering&oldid=1068865296 "