A Breadth First Search Algorithm for Data Clustering based on Space-time Curvature

In this paper, we present a novel data clustering approach, i.e., a Breadth First Search (BFS) algorithm based on space-time curvature, or BFS Curvature for short. Inspired by Einstein’s theory of General Relativity, we reformulated the clustering problem as a task of using a sophisticated algorithm to directly extract clusters from the curved space-time formed by the data. A Gaussian-like function is used to mimic the space-time curvature effect and a Breadth First Search algorithm is developed to uncover clusters one by one. The BFS curvature approach is able to solve problems of traditional clustering methods and does not require the number of clusters as input. Our experimental results have shown that it outperforms popular clustering algorithms and it is also scalable. To better measure the quality of the clusters and the corresponding algorithms, we utilize space-time curvature’s locality characteristic to design Curvature Density (CD), a novel metric that provides a more intuitive and robust score compared with the popular methods such as Silhouette score. Due to the unique features of our solution, BFS Curvature can also identify outliers, allow users to provide additional data insights to influence the clustering results and discover interesting data patterns.