# An Oversampling Method for Class Imbalance Problems on Large Datasets
## 1 Introduction  
One of the current research topics of interest in supervised classification is the class imbalance problem that frequently appears in several real-world datasets [1; 2; 3; 4; 5]. The class imbalance problem occurs when, in a dataset, one of the classes has fewer objects, usually called the minority class, than the other class, usually called the majority class. This problem produces a poor classification rate for the minority class, which is usually the most important. Consequently, it becomes difficult for a classifier to effectively discriminate between the minority and majority classes, especially if the class imbalance is extreme. For example, among several patients with a suspicious disease, very few are likely to have cancer, i.e., minority class, while most are likely not to have cancer, i.e., majority class. Here, a false negative means a patient with cancer is misclassified as not having the disease, which is a severe error. Another example of the class imbalance problem is distinguishing between 100 spam emails from 100,000, given that most emails are non-spam. Like these examples, the class imbalance problem is widespread and appears in many areas such as industrial, medical, and social, among others. In the literature, we can find different types of solutions like class decomposition [6; 7] or oversampling methods that are the most frequently used solutions reported in the literature for solving the class imbalance problem. SMOTE (Synthetic Minority Oversampling Technique) [8] is the most widely used and referenced method among the oversampling methods. SMOTE addresses the class imbalance problem by increasing the number of objects of the minority class by generating synthetic objects for this class. Due to its success, many other oversampling methods based on SMOTE have been proposed in the literature [9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30]; these methods are characterized by modifications of some of the SMOTE steps and/or addition of new steps. Other oversampling methods that do not follow the SMOTE's approach have also been proposed [22; 23; 26; 31; 32; 33]. However, most of the oversampling methods reported in the literature require computing the \(k\)-nearest neighbors of objects from the minority class or other slow steps, making them unsuitable for balancing large datasets. This paper will use the term large datasets to refer to those bigger than the conventional datasets used in the literature of oversampling, which have less than 10K objects. Among those oversampling methods not based on the \(k\)-nearest neighbors' search, we can highlight LMCMO [34], ROS (Random OverSampling), and NDO [35]. However, LMCMO needs to find the minimum distance between the minority class and the majority class objects, becoming very slow for large datasets. On the other hand, although ROS is fast, it produces low oversampling quality because ROS only generates exact copies of the objects of the minority class [36; 37; 38; 39]. Meanwhile, NDO is an oversampling method that is not based on the search for the \(k\)-nearest neighbors, but in a fast generation of synthetic objects; showing good oversampling results. Therefore, NDO can be applied to large datasets with imbalanced classes. The above shows that the development of fast oversampling methods not based on the \(k\)-nearest neighbors' search or other slow steps has been little studied in the literature. For his reason, this paper introduces a method that follows this approach, making it applicable to large datasets with imbalanced classes. Our experiments with large datasets show that the proposed method is at least twice as fast as the fastest method reported in the literature while obtaining similar oversampling quality. The rest of the paper is organized as follows: In Section 2, we present the related work. In Section 3, our oversampling method for class imbalance problems on large datasets is introduced.