Rough neighborhood graph: A method for proximity modeling and data clustering

This paper introduces the novel concept of a rough neighborhood graph as a method for proximity modeling and data clustering. Unlike previous research in applying rough sets in graph theory, we decided to use an undirected graph, which will be a convenient structure for community discovery algorithms. Simultaneously, the approach proposed in this paper is closer to spectral clustering from the perspective of dataset representation. Our approach is also not a variation of rough fuzzy K-means; namely, the clusters detected by our method do not have to be concentric, and we do not need to define a specific number of clusters we want to discover. We also use a rough set-inspired framework to represent proximity relations between object pairs in the dataset. Our definition of the neighborhood is distance-based, not approximation-based. Due to this, we can process any dataset in which objects are in metric space (a defined metric allows pairwise comparison). We have validated our approach on various benchmark datasets, achieving nearly perfect clustering results that overcome the limitations of other popular algorithms. All required data and source codes for the proposed method can be downloaded from an online repository, and the results presented in this paper can be reproduced. • The novel concept of a rough neighborhood graph is proposed. • We use a rough set-inspired framework to represent proximity relations. • A new rough set-based clustering method utilizing proximity is introduced. • We have validated our approach on various benchmark datasets.