Segmentacija i klasifikacija pomoću difuzijskih preslikavanja

master's thesis

• Title (english): Segmentation and classification using diffusion mapping
• Author: Hrvoje Olić
• Mentor: Zlatko Drmač (mentor)
• Mentor: Ivica Nakić (sumentor)
• Committee member: Ivica Nakić (predsjednik povjerenstva)
• Committee member: Zoran Vondraček (član povjerenstva)
• Committee member: Pavle Goldstein (član povjerenstva)
• Committee member: Sanja Varošanec (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-11-30, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: nelinearne plohe; visokodimenzionalni prostori; Markovljevi lanaci; euklidska udaljenost; PCA
• Keywords (english): nonlinear manifolds; high dimensional ambient space; euclidean distance; Markov chains; PCA
• Language: croatian
• URN:NBN: urn:nbn:hr:217:911265
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-13 07:45:43