Difuzijska preslikavanja s primjenom

master's thesis

• Author: Tatjana Ramljak
• Mentor: Zlatko Drmač (mentor)
• Committee member: Zlatko Drmač (predsjednik povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Committee member: Tina Bosner (član povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-07-20, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES

Abstract

Spektralno ulaganje i grupiranje podataka metode su nelinearne redukcije dimenzije i grupiranja kompleksnih visoko dimenzionalnih podataka. Kako bismo uspješno proveli ove metode, ponekad je ključno prikazati skup podatka s pomoću odgovarajućeg skupa koordinata. Jedan od načina kojim to možemo postići jesu difuzijska preslikavanja. Povezanosti izmedu točaka mjerimo s pomoću jezgrene funkcije koja definira lokalnu mjeru sličnosti točaka. Za danu matricu susjedstva svih točaka u određenom skupu podataka definiramo slučajnu šetnju po grafu u kojem su vrhovi točke podataka. Nadalje, pronalazimo tranzicijsku matricu pripadnog Markovljeva lanca, čije svojstvene vrijednosti i vektore koristimo za konstrukciju difuzijskih koordinata. One preslikavaju podatke u difuzijski prostor, gdje je definirana difuzijska udaljenost jednaka euklidskoj. Odbacivanjem nekih difuzijskih koordinata, tako da ne gubimo informacije o strukturi podataka, pronalazimo parametre koji opisuju strukturu u nekom nižedimenzionalnom prostoru. Promatranjem većih potencija matrice prijelaza Markovljeva lanca možemo dobiti bolji uvid u globalnu strukturu skupa podataka te se upravo u nekim većim vremenskim skalama otkriva njihova dinamika. Ovaj rad pruža vjerojatnosnu analizu difuzijskih preslikavanja. Dobivamo povezanost spektralnih svojstava Markovljevih procesa s njihovom geometrijskom prirodom. Za razliku od drugih popularnih metoda redukcije dimenzije, kao što je analiza glavnih komponenti difuzijska preslikavanja mogu otkriti nelinearne strukture. Pokazano je da je ova tehnika otporna na šumove i računski brza. U radu su obrađeni mnogi primjeri koji ilustriraju glavne teorijske principe.

Abstract (english)

Spectral embedding and data clustering are methods for nonlinear dimensional reduction and grouping of complex high - dimensional data. For a successful application of these methods, sometimes it is crucial to display set of data using an appropriate set of coordinates. One way to achieve this is by using diffusion mapping. The connection between points is measured using a kernel function that defines a local measure of point similarity. For a given neighborhood matrix of all points in certain data set, we define random walk on graph in which vertices are data points. Furthermore, in that way we find the transition matrix of the Markov chain, whose eigenvalues and eigenvectors are used for a construction of the diffusion coordinates. Those coordinates map the data in the diffusion space, where the defined diffusion distance is equal to Euclidean distance. By discarding some diffusion coordinates, information about data structure does not get lost and therefore, we can find parameters that describe the structure in some lower-dimensional space. By observing the greater potentials of the Markov chain transition matrix we can gain a better insight into the global structure of the data set whose dynamics can be revealed in some greater time scales. This thesis provides a probabilistic analysis of diffusion maps. We obtain the connection of the spectral properties of Markov processes with their geometric nature. Unlike other popular dimensional reduction methods, such as the principal component analysis, diffusion maps can detect nonlinear structures. It has been proven that this techniques is noise resistant and that is computationally fast. The thesis provides many case study examples that illustrate the main theoretical principles.

• Keywords: nelinearna redukcija dimenzije; difuzijska preslikavanja; Markovljev lanac
• Keywords (english): nonlinear dimensional reduction; diffusion mapping; Markov chain
• Language: croatian
• URN:NBN: urn:nbn:hr:217:018050
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-11-30 13:07:51