Search

Klasteranalüüsis on laialt levinud k-keskmiste meetod, mis võimaldab andmeid grupeerida nende tunnuste järgi, seejuures minimeerides ruutvigade summat klastrites olevate andmeobjektide ja vastava klastri keskpunktide vahel. Kuna k-keskmiste meetodi kui optimeerimisülesandele täpse lahenduse leidmine on NP-raske, siis on probleemi lahendamiseks võetud kasutusele mitmeid lähendeid otsivaid algoritme. Bakalaureusetöö eesmärgina valmis rakendus, mis lubab kasutada viit k-keskmiste klasterdusalgoritmi ja nelja algsete keskpunktide valimise meetodit. Kasutades nii reaalelulisi kui ka sünteetilisi andmestikke antakse ülevaade rakenduses implementeeritud algoritmide jõudlusest, mälukasutusest ja edukusest leida hea lähend k-keskmiste optimeerimisülesandele., In cluster analysis k-means method is a method popularly used for grouping data by their features. The method aims to minimize within-cluster sum of squared errors between data objects in clusters and their corresponding center means. Because solving k-means optimization task exactly is NP-hard there have been introduced several heuristic algorithms for finding approximations. As the goal of the thesis a software was made, which enables use of nine different algorithms, which are 5 k-means clustering algorithms and 4 methods for choosing initial centers. Using real life and synthetic datasets an overview of the application’s capabilities is given by measuring algorithms performance, memory use and approximation capabilities.

Uute sekveneerimistehnoloogiate abil genereeritakse palju erineva taustaga bioloogilisi andmeid. Olulise info leidmiseks tuleb neid andmeid analüüsida. Antud töös koostame meetodi, mis suudab tuvastada motiive suurest hulgast lühikestest aminohapete järjestustest ehk peptiididest, mis sisaldavad infot konkreetse inimese organismis olevate antikehade kohta. On alust arvata, et leitud motiivide abil võib olla võimalik tuvastada, milliseid haiguseid inimene on põdenud. Kuna ükski uuritud olemasolevatest tööriistadest selle probleemi lahendamiseks ei sobinud, koostasime motiivide tuvastamiseks uue meetodi. Meetodi esimene osa, sarnaste peptiidigruppide tuvastamine, põhineb hierarhilisel klasterdamisel ning sisaldab kahte erinevat võimalust hierarhilise klasterduse puust automaatselt klastrite eraldamiseks. Meetodi teine osa on sarnaste peptiidide klastritest motiivide tuvastamine. Kuna pärisandmetes olevad motiivid ei ole teada, genereerisime sünteetilised andmed, mille peal koostatud meetodit valideerida. Koostatud meetod suutis vastavalt sünteetiliste andmete omadustele tuvastada 50% kuni 100% sinna sisestatud motiividest, pärisandmetele eeldatavalt kõige sarnasema andmestiku peal 86%. Motiivide lugemise meetod töötas samamoodi hästi, etteantud mürata klastrite pealt suudetakse tuvastada 100% motiividest ning müraga klastrite pealt 90% motiividest. Koostatud meetodit on võimalik rakendada ka teistest bioloogilistest andmetest motiivide otsimiseks. Sel juhul peaks muutma teatud parameetreid, mis selles töös kasutatava andmestiku jaoks on seatud. Edaspidiseks tööks võiks olla meetodi töötamise valideerimine teiste omadustega andmete peal., With the help of new sequencing technologies we can generate a lot of biological data of different backgrounds. These data need to be analysed in order to extract the most important information from them. In this work we develop a method for extracting motifs from a large amount of short amino acid sequences called peptides that contain information about antibodies in that organism. Motifs found from these peptides could be linked to diseases that a person has had. Since none of the tested existing methods were suitable for solving this problem, we developed our own method that consists of two parts. First part, finding groups of similar peptides, is based on hierarchical clustering and has two different options for automatically extracting clusters from the hierarchical clustering tree. Second part is reading motifs from groups of similar peptides. Since we cannot validate the method on real data due to the lack of knowledge about the true motifs in them, we generate synthetic datasets that we validate the developed method on. The percentage of motifs the developed method could identify from synthetic data with different properties ranged from 50% to 100%, with 86% on the data that should be most similar to the real data. Method that reads motifs from group of similar peptides worked also very well. It could identify 100% of motifs from groups of peptides where no noise was added and 90% of motifs from noisier peptide groups. The developed method could be also used for motif discovery on different biological datasets. In that case we would have to change some parameters that were specifically chosen for this problem. Future work could be to test how well this method performs on different biological datasets.

Klasteranalüüs on laia kasutusvaldkonnaga andmeanalüüsi tehnika, mille rakendamiseks on olemas mitu erinevat algoritmi. Käesoleva töö eesmärk on anda ülevaade kolme levinuma klasteranalüüsi meetodi tööpõhimõtetest ja eripäradest, rakendades hierarhilise klasterda-mise, k-keskmiste klasterdamise ja Kohoneni võrgu algoritme näidisandmestiku peal. Li-saks algoritmide tööpõhimõtetele on kirjeldatud ka põhjus, miks näidisandmestikuks on valitud visuaalsed andmed ehk pildid ning kuidas on implementeeritud klasteranalüüsi meetodite rakendamiseks kasutatav skript. Töö sisaldab ka skripti rakendamisel saadud klasterduste analüüsi., Cluster analysis is a widely used data analysis technique that can be applied by using sev-eral different algorithms. This thesis aims to give an overview of the working principles and specifics of the three most commonly used cluster analysis methods by applying hier-archical clustering, k-means clustering and self-organizing map algorithms on sample data. In addition to the description of working principles of the clustering algorithms, there is also a description of how the script used for applying the clustering methods is implement-ed and an explanation for why visual data or pictures are chosen as the sample data. The thesis also includes an analysis of the clustering results produced by the script.

https://www.ester.ee/record=b5403736*est

https://www.ester.ee/record=b5397513*est