Segmentacija i klasifikacija pomoću difuzijskih preslikavanja

diplomski rad

• Naslov (engleski): Segmentation and classification using diffusion mapping
• Autor: Hrvoje Olić
• Mentor: Zlatko Drmač (mentor)
• Mentor: Ivica Nakić (sumentor)
• Član povjerenstva: Ivica Nakić (predsjednik povjerenstva)
• Član povjerenstva: Zoran Vondraček (član povjerenstva)
• Član povjerenstva: Pavle Goldstein (član povjerenstva)
• Član povjerenstva: Sanja Varošanec (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2023-11-30, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Difuzijska preslikavanja su metoda transformacije koordinata s ciljem učenja nelinearnih ploha u visokodimenzionalnim prostorima. Osnovna ideja iza ove metode je na novi način definirati udaljenosti među podacima, onu koja će u svojoj definiciji koristiti sve podatke, a ne samo onaj par između kojih mjerimo udaljenost, kako bi globalnu strukturu imali sadržanu u lokalnoj funkciji. S tom mjerom udaljenosti, želimo koordinate transformirati tako da standardna euklidska udaljenost u novim koordinatama odgovara novo definiranoj mjeri udaljenosti. U ovom radu dajemo vjerojatnosnu interpretaciju difuzijskih preslikavanja preko Markovljevih lanaca, s fokusom na slučajne šetnje na grafu. Za dane podatke, koristeći difuzijsku jezgru, definiramo matricu prijelaza koja odgovara slučajnoj šetnji na grafu, te pri računu transformacije koordinata u difuzijske, računamo svojstvene vrijednosti i vektore pripadne matrice. Taj se problem pokazuje prezahtjevnim za egzaktan račun, stoga pribjegavamo numeričkim metodama za rješavanje svojstvenog problema, s fokusom na simetrične matrice, kako bismo u konačnici dobili algoritam za računanje difuzijskih preslikavanja koji je i brz i točan. Jednom kada imamo potreban algoritam, primjenjujemo ga u klasifikaciji i segmentaciji. Za klasifikaciju imamo nekoliko kandidata s kojima možemo usporediti našu metodu, te biramo vrlo popularan PCA i metodu koja je suštinski vrlo povezana s difuzijskim preslikavanjima - lokalno linearna ulaganja. U primjeni za segmentaciju, javlja nam se problem s količinom podataka, koji u ovom slučaju uspješno rješavamo koristeći Nyströmovu aproksimaciju, te za obje primjene dobivamo kvalitetne rezultate.

Sažetak (engleski)

Diffusion maps are a coordinate transformation method with the goal of learning nonlinear manifolds in a high dimensional ambient space. The main idea behind this method is to redefine the distance between our data points, using a measure which will incorporate all available data points instead of focusing simply on the two points of interest, so that the global structure can be reflected locally. With this new measure of distance, we transform the coordinates so that the standard euclidean distance equates to newly defined distance measure. In this paper we present the probabilistic interpretation of diffusion maps based on Markov chains, specifically, random walks on a graph. For a given dataset, by using a diffusion kernel, we define a transition matrix for a random walk on a graph, for which we calculate corresponding eigenvalues and eigenvectors needed to transform starting coordinates to diffusion coordinates. The eigenproblem proves to be too challenging for exact calculation, which compels us to use numerical methods for eigenvalues, with symmetrical matrices as our main focus, which in the end gives us an efficient and precise algorithm for calculating diffusion maps. With our algorithm in hand, we apply it to problems of classification and segmentation. For classification we compare our algorithm to a very popular and widely used algorithm known as PCA, and we also compare it to a very theoretically similar method to diffusion maps known as Locally Linear Embedding method. When it comes to segmentation, the problem of data size arises, with which we deal with using Nyström approximation, so that finally we obtain an algorithm which provides decent results.

• Ključne riječi: nelinearne plohe; visokodimenzionalni prostori; Markovljevi lanaci; euklidska udaljenost; PCA
• Ključne riječi (engleski): nonlinear manifolds; high dimensional ambient space; euclidean distance; Markov chains; PCA
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:911265
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-13 07:45:43