Approximate spectral clustering ensemble methods for clustering of large data sets

Clustering as an unsupervised approach is used to group or extract the natural taxonomy (clusters) of any data or entities. Thanks to its unsupervised nature, it is popular in knowledge extraction from large datasets. Various methods of clustering have been proposed in different fields. Among them, spectral clustering (SC) is one of the most favored and successful algorithms. SC is a manifold learning method based on eigendecomposition of graph Laplacian matrix constructed from pairwise similarities of data samples. It has advantages such as, significant ability in extracting irregularly shaped clusters, nonparametric modality and easy implementation. Therefore SC is commonly used in various areas such as image processing, computer vision and information retrieval. Although the eigendecomposition stage produces more accurate results, it causes high computational and memory costs which make the direct use of SC infeasible for large datasets. To address this challenge, approximate spectral clustering (ASC), which applies spectral clustering on a reduced set of data points (data representatives) selected either by sampling or quantization (SOVQ), has been proposed. The ASC not only makes spectral clustering feasible for large datasets but also provides some useful information like local density distribution of data points around representatives and sub-manifolds information to measure the similarity between representatives. However, ASC requires selection of sampling/quantization (SOVQ) methods together with an optimal similarity definition. In this study (supported by TUBITAK career grant no 112E195) we use selective sampling as sampling method, k-means++ and neural gas as quantization methods to obtain the representatives, since these methods outperformed other approaches for ASC in recent works. To utilize all available information for accurate similarity definition, this study uses various similarity measures such as Euclidean distance, local density distribution, geodesic distance and their hybrid variants. Based on SOVQ method or similarity criteria, the resulting clusters may differ since each method utilizes a different information. In addition, randomness in SOVQ and SC may also produce different partitionings. Moreover, these methods have parameters which must be set optimally through experiments. To adress these challenges we propose ensemble methods which merge the advantages of all methods. In this study, we propose two ensemble algorithms for ASC. The first method is to use the traditional majority voting among all ASC partitionings. Alternatively the second approach is a two-level graph based ensemble depending on similarity matrix which is defined by the number of samples extracted in the same clusters among all partitionings. We use three artificial benchmark datasets with five datasets from the UCI machine-learning repository, six medical datasets consisting of several diseases, patients' data and brain tumor images, as well as four remote sensing images for performance evaluation. We applied the SOVQ based ASC with various similarity criteria on these datasets. Then we merged all individual results with our proposed ensemble methods to reach a consensus and optimal clustering. We evaluated the individual and ensemble results by accuracy, cluster validity indices (CVI) and adjusted rand index (ARI). Thanks to exploitation of all possible information types, ensemble of clustering results demonstrates considerable improvement on accuracy while removing the need of selection the optimum similarity criterion or related parameters.