Back to search

University of Ioannina

Clustering using similarity and kernel matrices

Abstract

dc:description

This thesis studies the (unsupervised) clustering problem, which aims at partitioning a dataset into groups, called clusters, such that instances falling in the same cluster are similar to each other and dissimilar to those of other clusters according to some similarity/dissimilarity measure. Specifically, this thesis concerns the development, implementation and evaluation of clustering methodologies, mainly focusing on three different axes: i) proximity-based clustering, where only the pairwise proximity matrix (i.e. similarity or distance matrix) of the data is available during training and not the instances themselves, ii) multi-view learning, where for the same instances multiple representations (views) are available, coming from different sources and/or feature spaces and iii) multiple kernel learning, where a kernel that suits the data is learned together with the cluster assignments. Usually, the kernel is parametrized as a combination of some predefined kernels, called basis kernels, and we wish to infer appropriate values for the combination parameters.We begin, by presenting an approach that tackles the initialization problem of the k-means algorithm by altering its sum of the intra-cluster variances objective. Weights are assigned to the clusters in proportion to their variance, which predispose the optimization towards primarily minimizing those clusters, that in the current iteration, exhibit large intra-cluster variance. In this way, the solution space is gradually restricted towards clusters with similar variances, allowing our method to systematically produce higher quality partitionings than k-means, while restarted from random initial centers. Moreover, we adapt our approach to perform clustering in kernel space, by altering the objective of the kernel k-means algorithm. The kernel space extension requires only the kernel matrix and not the instances as input, i.e. it is a proximity-based method.Afterward, we consider the problem of unsupervised multi-view learning. Our main contribution in this field is the assignment of weights to the views, which are automatically tuned to reflect the quality of the views and determine their contribution to the clustering solution accordingly. The majority of multi-view approaches treat all available views as being equally important, which may lead to a considerable drop in performance if degenerate views (e.g. noisy views) exist in the dataset. Analytically, we present two different methodologies for the above problem. In the first case, views are represented by convex mixture models and we develop an algorithm that associates a weight with each view and another that does not employ view weights. In the second case, each view is represented by a kernel matrix and a weighted combination of those kernel matrices is learned. This formulation includes a parameter that controls the sparsity of the weights, allowing its adaptation to the dataset.Finally, we focus on multiple kernel learning, where most of the existing clustering approaches of this type exploit the large margin principle of SVM and perform learning by maximizing the margin. Instead, here, we propose an objective that utilizes the ratio between the margin and the intra-cluster variance. Since the objective explicitly takes into account both the separation (margin) and the compactness (intra-cluster variance) of the clusters, higher quality solutions can be possibly attained compared to approaches that rely solely on either of the two. Moreover, it has been shown that the margin alone is an unsuitable measure of the goodness of the learned kernel, as it can become arbitrary large by simply scaling the kernel. We prove that our ratio-based objective is invariant to kernel scaling and, also, that its global optimum solution is invariant to the type of norm constraint on the kernel parameters. Experiments verify the properties of our objective and reveal the superior clustering performance of the proposed multiple kernel formulation.

Degree

thesis:*
Grantor dc:publisher
University of Ioannina
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Tzortzis, Grigorios
  • Τζώρτζης, Γρηγόριος

Subjects

dc:subject × 16

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/37387

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Tzortzis, Grigorios; Τζώρτζης, Γρηγόριος. Clustering using similarity and kernel matrices. University of Ioannina, 2014. http://hdl.handle.net/10442/hedi/37387