Clustering with Multi-Focal Clusters

Abstract

We present one and develop two heuristic algorithms for multi-focal clustering. The first algorithm is a local search algorithm based on the Partition Around Medoids (PAM) algorithm. The second algorithm is a modification of the sparse spatial selection (SSS) to add multi-focality. The third algorithm uses single link cluster analysis (SLCA) to form the clusters. Further we develop a Mixed Integer Program to find the optimal solution. We show that these algorithms have different applicable properties that can be utilized for different data sets and with different preconditions. We compare the heuristics and the multi-focal solutions to existing heuristics and uni-focal, ball-regions, and show that the multi-focal regions can be advantageous to reduce the number of comparisons by using a Monte Carlo algorithm to simulate searching in the indexes.