Reduction Through Homogeneous Clustering: Variations for Categorical Data and Fast Data Reduction

Abstract

Reduction through Homogeneous Clustering (RHC) and its editing variant (ERHC) represent effective methods for reducing data in the context of instance-based classification. Both RHC and ERHC are based on an iterative k-means clustering procedure that builds homogeneous clusters. Therefore, they are inappropriate for data reduction tasks that need to be performed quickly, especially, when run over large training datasets. Moreover, since they are based on k-means clustering, they are inappropriate for categorical data. This paper introduces a set of variations to the RHC and ERHC algorithms. More specifically, addressing the iterative nature of k-means clustering in RHC and ERHC, we present new adaptations known as RHC2 and ERHC2. These variations strategically replace the complete execution of k-means clustering with a streamlined task, demonstrating significant improvements in speed. Additionally, we extend the scope of our study to address categorical data by introducing new variations of RHC and ERHC. The adaptations designed for handling categorical data are denoted as RHCM and ERHCM and are based on k-modes clustering. Our experimental study spans diverse datasets and includes statistical tests. The findings reveal a notable performance improvement in execution time for adaptations we propose compared to RHC, ERHC and two other prominent data reduction techniques. Moreover, RHC2 and ERHC2 are found to outperform their predecessors in data reduction effectiveness. Concerning RHCM and ERHCM, performance evaluations conducted on various categorical datasets indicate that these variations efficiently minimize the dataset size, with a relatively modest compromise in accuracy.