Weighted Complete Graphs for Condensing Data

Abstract

In many real-world problems (such as industrial applications, chemistry models, social network analysis, among others), their solution can be obtained by transforming the problem in terms of vertices and edges, that is to say, using graph theory. Data Science applications are characterized by processing large volumes of data, in some cases, the data size can be higher than the resources for their processing, situation that makes prohibitive to use the traditional methods. In this way, to develop solutions based on graphs for condensing data can be a good strategy for handling big datasets. In this paper we include two methods for condensing data based on graphs, the two proposals consider a weighted complete graph by acquiring an induced subgraph or a minimum spanning tree from the whole datasets. We conducted some experiments in order to validate our proposals, using 24 benchmark real-datasets for training the 1NN, C4.5, and SVM classifiers. The results prove that our methods condensed the datasets without reducing the performance of the classifier, in terms of geometric means and the Wilcoxon’s test.