In this thesis, we address a number of challenges in cluster analysis. We begin by investigating one of the oldest and most challenging problems: determining the number of clusters, k. For this problem, we propose a novel solution that, unlike previous techniques, delivers both the number of clusters and the clusters in one-shot (in contrast, conventional techniques run a given clustering algorithm several times for different values of k, and/or for several initialization with the same k). The second challenge we treat is the drawback, briefly mentioned above, of many conventional iterative clustering algorithms: how should they be initialized? We propose an initialization scheme that is applicable to multiple iterative clustering techniques that are widely used in practice (e.g., spectral clustering, EM-based, k-means). Numerical simulations demonstrate a significant improvement compared to many state-of-the-art initialization techniques. Third, we consider the computation of pairwise similarities between datapoints. A matrix of such similarities (the similarity matrix) constitutes the backbone of many clustering as well as unsupervised learning algorithms. In particular, for a given similarity metric, we propose a similarity transformation that promotes high similarity between the points within the cluster and deceases the similarity within the cluster overlapping regions. The transformation is particularly well-suited for many clustering and dimensionality reduction techniques, which we demonstrate in extensive numerical experiments. Finally, we investigate the application of clustering algorithms to image and video datasets (also known as superpixel segmentation). We propose a segmentation algorithm that significantly outperforms current state-of-the-art algorithms; both in terms of runtime as well as standard accuracy metrics. Based on this algorithm, we develop a tool for fast and accurate image annotation. Our findings show that our annotation technique accelerates the annotation processes by up to 20 times, without compromising the quality. This indicates a big opportunity to significantly speed up all AI computer vision tasks, since image annotation forms a crucial step in creating training data. / Den här avhandlingen behandlar en rad utmaningar inom klusteranalys. Till att börja med undersöker vi ett av de äldsta och mest utmanande problemen: att bestämma antalet kluster k utifrån data. Vi föreslår en ny algoritm som, till skillnad från tidigare algoritmer, ger antalet kluster (samt själva klustren) från enbart en körning. (Tidigare algoritmer kräver att dessa algoritmer körs flera gånger för olika värden på k, eller från olika startpunkter för samma värde på k.) Den andra utmaningen vi behandlar är hur de idag vanligast förekommande klusteringsalgoritmerna (e.g., spektral-, EM-baserad-, samt k-means-klustering) bör initialiseras. Vi föreslår en initialiseringsmetod, och demonstrerar i numeriska simulationer att denna ger signifikant bättre resultat jämfört med de nuvarande bästa metoderna. Som tredje del i avhandlingen studerar vi konstruktionen av mått på parvis likhet mellan datapunkter. En matris bestående av sådana likheter ligger till grund för många klusteringsalgoritmer, samt metoder för oövervakad inlärning inom maskininlärning. Mer specifikt så demonstrerar vi hur en likhetstransformation kan tillämpas på ett givet likhetsmått för att främja likhet mellan datapunkter inom samma kluster och undertrycka likhet för punkter som ligger i områden där kluster överlappar. Transformationen vi föreslår är speciellt lämpad för klusterings- och dimensionsreduceringsalgoritmer, vilket vi demonstrerar i omfattande numeriska experiment. Till sist studerar vi tillämpningar av klusteringsalgoritmer på bild- och videodata. Vi föreslår en segmenteringsalgoritm med signifikant bättre prestanda än de nuvarande bästa algoritmerna; både i termer av beräkningskomplexitet samt precision. Vidare så utvecklar vi en mjukvara baserad på vår algoritm för snabb och precis bildsegmentering. Våra studier visar att bildsegmentering och -annotering kan utföras upp till 20 gånger snabbare än med nuvarande mjukvaror, utan att vi kompromissar på kvalit´en. Detta pekar mot stora möjligheter att snabba upp många applikationer inom datorseende, eftersom segmenterad bilddata ligger till grund som träningsdata för många algoritmer.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-238512 |
| Date | January 2018 |
| Creators | Petrosyan, Vahan |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS), Stockholm |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Licentiate thesis, monograph, info:eu-repo/semantics/masterThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-AVL ; 2018:86 |
Page generated in 0.0024 seconds