Ensemble learning for optimal cluster estimation

Abstract

This thesis addresses the importance of understanding the underlying structure of high-dimensional datasets through clustering, considering the vast amount of unlabelled available content on the internet and electronic sources. While clustering ensembles have been proposed in the past, the potential of heuristic search-based ensembles has been relatively unexplored. The thesis presents a novel computational method that combines heuristic search and clustering ensembles, focusing on two crucial issues. Firstly, it establishes a representative solution by effectively subsetting ensembles. The thesis introduces a Gray code implementation that maximises the spread across subsets while minimising differences between them. Secondly, the exhaustive search for the best solution from the representative pool becomes computationally expensive as the dimension and volume increase. An alternative approach based on heuristic search is suggested. This approach evaluates subsets incrementally, similar to the implementation of Gray code, resulting in significant speed gain. However, random mutation hill climbing (RMHC) in heuristic search suffers from finding a suitable solution without guidance, particularly in larger search spaces. The thesis presents an innovative seeding technique that leverages Fiedler vector decomposition and minimum spanning tree (MST) to address this challenge. This technique significantly improves both the quality of solutions and computational efficiency. The proposed methodology is extensively evaluated using simulated and benchmark clustering datasets, employing theoretical and empirical examples. The results demonstrate the high effectiveness of the proposed approach. The key contributions of this thesis include the introduction of Gray code subsetting of ensembles, the incorporation of heuristic-search-based techniques into clustering ensembles, and the novel improvement in search space convergence through effective seeding.