Hub selection for hub based clustering algorithms

Hubs are the data instances appearing frequently on the nearest neighbours lists. As the hubs of a high-dimensional dataset are close to the centres of clusters or sub-clusters, some of them are selected as the centres of clusters by hub based clustering algorithms. In the process of hub selection, these algorithms rank data instances in terms of their global hubness scores computed upon their nearest neighbours lists, ignoring cluster related information such as their labels, their and their related instances´ clustering quality. As a result, some suitable hubs may be neglected. To solve this problem, we suggest evaluating instances by their relative hubness scores. Moreover, we propose a weighted relative hubness score computed upon nearest neighbours lists and silhouette information. Besides, we suggest selecting the instance of the highest silhouette information when two or more instances tie for first place. Experimental results on real datasets and synthetic datasets suggest that both the relative hubness score and the weighted relative hubness score can improve hub based clustering, and the weighted relative hubness score often plays better.