MCMSTClustering: defining non-spherical clusters by using minimum spanning tree over KD-tree-based micro-clusters

Clustering is a technique for statistical data analysis and is widely used in many areas where class labels are not available. Major problems related to clustering algorithms are handling high-dimensional, imbalanced, and/or varying-density datasets, detecting outliers, and defining arbitrary-shaped clusters. In this study, we proposed a novel clustering algorithm named as MCMSTClustering (Defining Non-Spherical Clusters by using Minimum Spanning Tree over KD-Tree-based Micro-Clusters) to overcome mentioned issues simultaneously. Our algorithm consists of three parts. The first part is defining micro-clusters using the KD-Tree data structure with range search. The second part is constructing macro-clusters by using minimum spanning tree (MST) on defined micro-clusters, and the final part is regulating defined clusters to increase the accuracy of the algorithm. To state the efficiency of our algorithm, we performed some experimental studies on some state-of-the-art algorithms. The findings were presented in detail with tables and graphs. The success of the proposed algorithm using various performance evaluation criteria was confirmed. According to the experimental studies, MCMSTClustering outperformed competitor algorithms in aspects of clustering quality in acceptable run-time. Besides, the obtained results showed that the novel algorithm can be applied effectively in solving many different clustering problems in the literature.

Automated summary

In this study, a novel clustering algorithm called MCMSTClustering is proposed to handle high-dimensional, imbalanced, and/or varying-density datasets. The algorithm defines micro-clusters using KD-Tree data structure, constructs macro-clusters using minimum spanning tree on micro-clusters, and regulates defined clusters to improve accuracy. Experimental results confirm the success of the proposed algorithm in terms of clustering quality and acceptable run-time, and its effectiveness in solving various clustering problems in the literature.