Spektralne metode za računanje meta-stabilnih stanja Markovljevih lanaca

diplomski rad

• Naslov (engleski): Spectral methods for computing meta-stable states of Markov chains
• Autor: Ivana Blažeka
• Mentor: Zlatko Drmač (mentor)
• Član povjerenstva: Zlatko Drmač (predsjednik povjerenstva)
• Član povjerenstva: Boris Širola (član povjerenstva)
• Član povjerenstva: Miljenko Huzak (član povjerenstva)
• Član povjerenstva: Pavle Pandžić (č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: 2021-04-29, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ovaj rad obrađuje tri metode za klasteriranje konačnog skupa stanja Markovljevog lanca. Sve tri metode bazirane su na spektralnoj analizi, odnosno Perron-Frobeniusovom klasteru svojstvenih vrijednosti matrice prijelaza. Metode su prvo teorijski obrađene, a zatim testirane na odabranim primjerima. Kao najbolju metodu izdvojila bih metodu GenPCCA. Za početak, ona daje najviše korisnih informacija - prijelaznu matricu koja pripada novodobivenom Markovljevom lancu i matricu članstva iz koje se jasno iščtava kojem klasteru pripada koje stanje uz vjerojatnosti drugih, manje izglednih mogućnosti. Dalje, čini se i najpreciznijom. Uz analizu spectra i Schurovih vektora, slijedi i postupak optimizacije koji rješenje dodatno približava onom idealnom. Metoda koja pri analizi pristupa Markovljevom lancu kao grafu je također vrlo precizna. Koristi metode optimizacije uz samu analizu spektra. Nedostatak je da daje i najmanje informacija. Dobivena matrica članstva jednoznačno svakom stanju daje jedinstveni klaster bez informacije o drugim mogućim varijantama, a nemamo novu matricu prijelaza ili nešto slično tome. Rezultati su se uglavnom poklapali s onima dobivenim metodom GenPCCA. Metoda bazirana na analizi singularnih vrijednosti je u sva tri primjera vrlo lijepo klasterirala stanja i rezultati su se poklapali s onima dobivenim metodom GenPCCA. Također nam daje i matricu veza koja općenito nema Markovljevo svojstvo, ali je korisna informacija. Metoda je vjerojatno najmanje precizna s obzirom da koristi samo spektalnu analizu, bez dodatnih optimizacija.

Sažetak (engleski)

This thesis deals with three methods of clustering a finite set of states of the Markov chain. All three methods are based on spectral analysis, i.e., on Perron-Frobenius cluster of eigenvalues of transition matrix. Each method is first theoretically analyzed and then tested on selected examples. As the best method, I would single out the GenPCCA method. First, it provides more useful infomation than other methods - the transition matrix of newly acquired Markov chain, the membership matrix which gives us clear information about how likely each state is to belong to a particular cluster. Furthermore, it seems to be the most accurate. In addition to the analysis of the spectrum and Schur vectors, the optimization procedure follows, which brings the solution even closer to the ideal one. The method that approaches to the Markov chain as a graph is also very precise in the analysis. It uses optimization methods in addition to the spectral analysis itself. However, the disadvantage is that it gives even the least information. The resulting membership matrix uniquely gives each state a unique cluster without information about other possible variants, and we do not get a new transition matrix or anything similar to that. The results mostly coincided with those obtained by the GenPCCA method. The method based on the analysis of singular values clustered the states very nicely in all three examples and the results coincided with those obtained by the GenPCCA method. It also gives us a coupling matrix that generally does not have a Markov property, but is a useful information. The method is probably intended to be the least precise as it uses only spectral analysis, without additional optimizations.

• Ključne riječi: Perron-Frobeniusov klaster; metoda GenPCCA; Schurovi vektori
• Ključne riječi (engleski): Perron-Frobenius cluster; GenPCCA method; Schur vectors
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:095482
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-05-18 10:41:47