A Constraint-Programming-Based Oversampling Method for Imbalanced Datasets (CP-SMOTE)

Class imbalance is a pervasive challenge in machine learning and data mining, particularly in real-world applications such as fraud detection, medical diagnosis, and industrial anomaly detection. The traditional Synthetic Minority Over-sampling Technique (SMOTE) and its variants heavily rely on linear interpolation between existing minority instances to generate new data points. However, this empirical, data-driven interpolation entirely overlooks the underlying business logic, physical laws, and explicit domain constraints inherent to the datasets, thereby frequently generating invalid or impossible samples that corrupt the classifier's decision boundaries. To address this critical limitation, this paper proposes a novel over-sampling framework named Constraint-Programming SMOTE (CP-SMOTE). Instead of spatial interpolation, CP-SMOTE reformulates the generation of synthetic samples as a Constraint Satisfaction Problem (CSP). By explicitly defining domain expertise, feature boundaries, and logical relationships as mathematical constraints, a constraint solver is leveraged to systematically search and generate legitimate minority samples within the valid solution space. Simulation evaluations demonstrate that CP-SMOTE strictly guarantees 100% validity of the synthesized samples while achieving competitive or superior performance in terms of F1-score and G-mean compared to traditional over-sampling methods.