Using Shadowed Clustering and Breeder GA in the Imbalanced Data Classication Problems [Extended Abstract] Ante Panjkota Department of Economics and Department of Maritime Studies, University of Zadar Splitska 1 Zadar, Croatia apanjkot@unizd.hr Ivo Stancic, Josip Music Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture, University of Split Rudjera Boskovica 32 Miha Drole Faculty of Computer and Information Science, University of Ljubljana Vecna pot 113 Ljubljana, Slovenia miha.drole@fri.uni-lj.si Petar Vracar Faculty of Computer and Information Science, University of Ljubljana Vecna pot 113 Ljubljana, Slovenia Split, Croatia istancic@fesb.hr, jmusic@fesb.hr Igor Kononenko Faculty of Computer and Information Science, University of Ljubljana Vecna pot 113 Ljubljana, Slovenia lj.si Matjaz Kukar Faculty of Computer and Information Science, University of Ljubljana Vecna pot 113 Ljubljana, Slovenia petar.vracar@fri.uni-lj.si igor.kononenko@fri.uni matjaz.kukar@fri.uni-lj.si ABSTRACT We discuss possibilities and advantages of using a novel oversampling approach based on the synthetic minority instances generation by using shadowed clustering and Breeder genetic algorithm for dealing with imbalanced classication problems. Viability of the proposed oversampling method is conrmed through comparison with state-of-the-algorithms in experiments on four imbalanced datasets obtained from a Blender-based simulator. In all conducted experiments the proposed oversampling approach performs at least as well as state-of-the-art algorithms. Our results indicate a great potential for future ensemble algorithm formed from orthogonal projections and oversampled as proposed in this. Categories and Subject Descriptors G.4.1 [Computing methodologies]: Cluster Analysis; G.4.1 [Computing methodologies]: Feature selection General Terms Imbalanced data classication, minority class oversampling, ensembles for classication INTRODUCTION 1. With huge advancement in technology, modern society is focusing on raising the quality of the life for vulnerable individuals and groups in everyday situations. People with low vision/blindness are in focus of our work. Activities of daily living are often very dicult and in some cases impossible for such groups. One such activity is independent travel between two points (indoor or outdoor). Self-adapting machine learning techniques can be used in such situations [1] to identify potentially dangerous situations. Outdoor navigation is generally the more challenging task since surroundings are highly dynamic with little or no regular structure. Related approaches dealing with similar problems include utilizing Bayesian statistic to aid in navigation through indoor environment, crosswalk and stairs detection with RGBD cameras using Hough transform and line tting with geometric constraints [2], and multi-sensory learning [1]. However, often they are plagued by a great number of false alarms due to oversimplied input space. There are in general few cases of the potentially dangerous trajectories that can cause injury to visually impaired person. From machine learning perspective these tasks are usually characterized with: (1) signicant imbalance between class sizes, and (2) large penalty for wrong classication which can lead to serious injury. Among most successful methods for dealing with class imbalance are sampling methods, more precisely minority class oversampling methods [3, 4]. One of the limiting factors of such systems is environmental complexity resulting in large amounts of data much of which can not be used for intended application. In our paper we present a novel approach for dealing with binary imbalanced data classication problems based on minority class oversampling by combining shadowed clustering [5] and Breeder GA algorithm [6]. Our research is directed toward development of reliable and accurate algorithm that can be used in assistive systems for visually impaired in tasks of obstacles/objects avoidance.We use a Blender-based simulator to obtain depth-sensor data as proposed in [7]. The use of 3D surface scanners in simulation environments has already been successfully achieved which makes this sensing technology a good candidate for both our current testing and future system. Data obtained from simulator are used to create four scenarios that emulate real-life situations. Viability and perspectives of the proposed minority oversampling method based on a shadowed clustering and Breeder GA is demonstrated through comparison with several stateof-the-art machine learning algorithms for handling imbalanced data classication. Finally, we analyze and discuss obtained results and highlight the road-map toward future ensemble algorithms which will implement the oversampling method proposed in this paper. 2. SHADOWED CLUSTERING AND BREEDER GA OVERSAMPLING APPROACH Sections obtained from shadowed clustering in the minority class are oversampled by synthetically generated minority instances using Breeder GA algorithm. Every region in minority class is oversampled proportional to its size. This means that in the case of two clusters from the shadowed clustering phase (with joint ratio of 1:3) we automatically have dened the number of synthetically produced instances in every cluster so in nale all oversampled clusters are producing desired relation between majority and minority class size (commonly 1:1). In this way unchanged ratio in relative size of the all produced clusters is secured. At the end of the section pseudo code for the minority class oversampling technique based on shadowed clustering and Breeder GA (Shadowed Clustering based Minority Oversampling Technique SCMOT) are presented. 2.1 Shadowed clustering Shadowed clustering is based on shadowed set theory. This theory developed out of the simplied view on fuzzy sets. Shadowed set can be obtained from fuzzy set via BZM V dM algebra which uniquely denes transformation operator from shadowed to fuzzy set while reverse does not hold. Shadowed sets are introduced as necessary tool for observing and analyzing problem sets for which classical set theory does not provide satisfactory interpretation. Shadowed clustering is derived from fuzzy clustering with introduction of threshold [0, 1] on the membership function [5]. In this manner cluster structure can be determined more reasonably. Shadowed set A is dened as mapping A : X (cid:55) {0, (0, 1), 1} (where X is observed space). Codomain interpretation has the following meaning: elements for which A(x) = 1 represent shadowed set (cluster) kernel fully reecting set A concept, elements for which A(x) = 0 do not belong to set A, while elements which have membership function value in the interval (0, 1) do not have membership dened and are members of a shadowed set. 2.2 Basic principles of synthetic data sample generation using Breeder GA algorithm Widely used group of algorithms for synthetic oversampling of minority class are from family of SMOTE algorithms [8, 9]. Main drawback of such algorithms is reduced exibility in synthetic data generation. More exibility potentially could be achieved with algorithms from evolutionary computing (i.e. genetic algorithms). However, basic Breeder GA algorithm [6] can be modied in a way as to generate new, synthetic data from some initial data set. In the process only two operations will be used: recombination and mutation. Selection phase in a way also exist here, but since all individuals have same tness function, all pairs from input data will be taken into account in the next recombination phase. Recombination process generates new instances by combining data from two or more parents (in our proposal we conne ourselves with only two parents). Depending on a way in which parent variable values are represented, different recombination can be achieved. We propose use of discrete and line recombination. So, two possible synthetic samples generation approaches are dened: (1) parents in Breeder GA algorithm are all possible pairs within the same core CORE Breeding (CB), or (2) parents in the Breeder GA algorithm are all possible shadow-core combinations for the same cluster CORE and SHADOW Breeding (CSB) In case that insucient number of cluster instances are obtained for balancing out classes, required number could be obtained with mutations on osprings. It is worth noting that this situation should not happen since with randomness in recombination process arbitrarily large number of osprings can be obtained. Thus, mutation procedure only enables more exibility in the synthetic data generation. Figure 1: Mutation results after discrete recombination. Note that after line recombination, all possible osprings would lie roughly on a line connecting the parents. As in case of discrete recombination this procedure outputs synthetic instances within the hyper-cube along the coordinate axis. Results of mutation after discrete and line recombination are depicted in Figure 1. 2.3 SCMOT algorithm After oversampling, shadowed clustering method is performed on the all minority instances with certain number of clusters. For relatively few dimensions ( 6) number of clusters can be estimated with known methods, e.g. Davies-Bouldin index and Silhouette method. The rst oversampling mode (CB) has all pairs of the particular core as a recombination parents in the Breeder GA algorithm, while in the second mode (CSB) parents in the Breeder GA algorithm are all possible pairs from core and shadow of the dened clusters. In the existence of the outliers only CORE Breeding mode is at our disposal. Upon selection of the oversampling mode each cluster has been populated in a relative size to dened clusters. At the end of the oversampling procedure the desired ratio between majority and minority class is achieved. The described procedure is depicted in Algorithm 1. Algorithm 1 SCMOT 1: procedure SCMOT(data) Ensure: Extraction of the minority class from data Ensure: Choose number of clusters (numCLS) OR evaluate point distortion, change in point intensity level etc. Based on video stream data 3D locations of projected points were calculated. 4. EXPERIMENTAL PROCEDURE Basic information of the data sets used in four Experiments 1-4 are given in the Table 1. Table 1: Basic data set informations used in experiments 2: 3: 4: 5: number of clusters in minority class SCM v, , u (cid:46) Performing SCM on minority class with numCLS if N umOutliers = 0 then for do(k = 1 : numCls) synthetic (CB) OR (CSB) and Mutation (cid:46) Recombination else end for 6: 7: 8: 9: 10: 11: 12: 13: 14: end procedure end for for do(k = 1 : numCls) synthetic (CB) (cid:46) Recombination and Mutation end if ovsamM in merge all minority and all synthetic return ovsamM in 3. SIMULATOR The simulator used in this paper is based on adaptive robot 3D scanner [7]. It operates as a simple stereo vision system, consisting of a laser pattern projector as the active component, and a camera as the passive component. The laser projector projects a star-like structural light pattern (consisting of 21 points) on the surface of the target area (Figure 2 right). The three-dimensional shape and location of the sensed object is reconstructed by comparing the known locations of each projected point (projector Ppr) with the corresponding point on camera image (Pcam), as seen in left of Figure 2. Scanners output data is a point cloud, which represents 3D locations of all projected points (surface points). Figure 2: Blender model of robot with 3D scanner (left), projected patterns as seen from scanners camera (right) Up to two 3D sphere-like objects that represent potentially dangerous obstacles for the robot are simulated. In the simulations, in total four scenarios were simulated: miss (object is passing far from the robot) DS1, near hit (object is passing near the robot) DS2, hit (object is on a collision course with the robot) DS3 and hit with 2 objects (one object is missing, while second object is colliding with the robot) DS4. Each scenario was repeated 6 times, with random object placements, movement speeds and directions. Output of Blender simulation is video stream. Simulation inherits some of scanners defects like projection errors, projected data set Nmin Nmaj 1000 500 665 320 DS1 DS2 DS3 DS4 125 100 95 80 imbalance ratio 8 5 7 4 In all 2D combinations and one 3D case (of the primary 3D data) class balance have been produced with ratio 1:1 by using SCMOT approach described with Algorithm 1. Class balance is only performed on the training folds in classical 10-folds CV procedure, while test folds are kept in the originally imbalanced ratio [10]. SCMOT oversampling approach was combined with known algorithms Naive Bayes (NB), Support Vector Machines (SVM), Multi Layer Perceptron (MLP), Nearest Neighbor Search (NNS), Ripper, C45 and Decision Stump (DS). Quality of the proposed oversampling approach (SCMOT) was conrmed through comparison with the state-of-the-art algorithms for handling imbalanced data classication. For that purpose IIVOTES, OverBagging, SMOTEBoost, MSMOTEBoost and standard SMOTE procedure were used. Combinations of all 2D orthogonal projections and one 3D projection were oversampled by using SCMOT approach to produce classication ensemble. Final decision of a such ensemble is dened with majority voting process. These ensembles were also compared with the mentioned state-of-the-art algorithms. 5. RESULTS AND DISCUSSION Results presentation and corresponding discussions is performed for all four experiments on datasets in Table 1. Experiment 1 corresponds to dataset 1 (DS1), Experiment 2 to dataset 2 (DS2) and so on. Table 2: Classication results of the data set DS1 to DS4 best ensemble from all orthogonal projections with SCMOT and best classier among state-of-the-art algorithms ACC F-measure AUC Experiment 1 DS1 Ripper + SCMOT 0,9680 SMOTEBoost 0,9493 0,8571 0,7782 Experiment 2 DS2 Ripper + SCMOT SMOTEBoost 0,9667 0,9667 0,8980 0,8913 Experiment 3 DS3 Ripper + SCMOT 0,9737 SMOTEBoost 0,9711 0,8969 0,8791 Experiment 4 DS4 0,9680 0,8843 0,9618 0,9100 0,9872 0,9158 Ripper + SCMOT 0,9525 SMOTEBoost 0,9625 0,8774 0,9007 0,9771 0,9203 As can be seen from Table 2 we only reported results of the best performing ensemble with SCMOT procedure and best classier from state-of-the-art group. For Experiments 1 to 4 obtained results on DS1-DS4 indicate Ripper as the best base learner for ensemble based on using SCMOT on orthogonal projections while best state-of-the-art algorithm was SMOTEBoost. Results in the Table 2 are showing comparable values in all performed Experiments (1-4) between SMOTEBoost and ensemble with Ripper + SCMOT procedure. Overall results on all four datasets, without calculation of statistical signicance, and with highlighted number of highest values for ACC, F-measure and AUC parameter are presented in Table 3. Data in Table 3 veried our main intention to demonstrate feasibility of application of the SCMOT procedure on orthogonal projections and ensemble construction from such areas for the purpose of imbalanced set classication. Table 3: Aggregate number of wins/ties/losses of each algorithm against others over datasets in Table 1 based only on maximal values for particular evaluation measure ACC F-measure AUC 0/0/4 0/0/4 0/0/4 0/0/4 0/0/4 0/0/4 0/0/4 1/1/2 0/0/4 SMOTE 0/0/4 Ensemble with SCMOT 2/1/1 4/0/0 IIVOTES MSMOTEBoost OverBagging SMOTEBoost 0/0/4 0/0/4 0/0/4 1/0/3 0/0/4 3/0/1 6. CONCLUSIONS In this paper we discuss possibilities and features of a novel approach for imbalance data classication based on minority class oversampling by using shadowed clustering in combination with Breeder GA. Viability of the proposed Shadowed Clustering based Minority Oversampling Technique (SCMOT) has been conrmed by comparison with several state-of-the-art algorithms in classication of four imbalanced datasets obtained from Blender based simulator. In all experiments SCMOT approach had comparable quality with chosen state-of-the-art algorithms evaluated through ACC, F-measure and AUC. Besides comparing favorably in quantitative terms, SCMOT also has the following advantages like high exibility in synthetic instances generation because of the shadowed clustering combination with Breeder GA and possibility for producing quality ensemble multiple diverse through data level (synthetic data generation exibility) and on the features multiplicity by combining SCMOT in dierent orthogonal projections. By combining all orthogonal projections oversampled by SCMOT in one ensemble, with majority voting policy, a good solution for classication of the imbalanced datasets was obtained. Ensembles built in this way achieved the highest number of top performance results. This is a good guarantee for its perspectives in classication of the imbalanced datasets. The benets of balancing the data sets are not limited to propositional learning approaches, but also apply to relational learning (e.g. inductive logic programming). Since relational learning approaches often guide their search by rewarding a hypothesis (correct) coverage and penalizing its complexity, they are likely to nd sub-optimal solutions when presented with imbalanced datasets, since the minority class severely limits the maximal allowed complexity of the produced hypothesis. A basic assumption for the further development of ensembles based on the SCMOT method in orthogonal projections is multidimensionality of the input data. For this purpose some sub-problems need to be addressed, such as nding the upper projection dimensionality where shadowed clustering can be used, discovering favorable orthogonal projections (good attributes) and fast estimation of the number of clusters. These sub-problems are among main directions of our further research. 7. REFERENCES [1] S. Krishnas and K. Sujitha, Machine Learning approach for Assisting Visually Impaired, International Journal for Trends in Engineering and Technology, vol. 3, pp. 119122, 2015. [2] Y. Tian, RGB-D sensor-based computer vision assistive technology for visually impaired persons, in Computer Vision and Machine Learning with RGB-D Sensors, pp. 173194, Springer, 2014. [3] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, SMOTE: synthetic minority over-sampling technique, Journal of articial intelligence research, pp. 321357, 2002. [4] Z. Xie, L. Jiang, T. Ye, and X. Li, A synthetic minority oversampling method based on local densities in low-dimensional space for imbalanced learning, in Database Systems for Advanced Applications, pp. 318, Springer, 2015. [5] S. Mitra, W. Pedrycz, and B. Barman, Shadowed c-means: Integrating fuzzy and rough clustering, Pattern Recognition, vol. 43, pp. 12821291, Apr. 2010. [6] D. Schlierkamp-Voosen and H. Muhlenbein, Predictive models for the Breeder genetic algorithm, Evolutionary Computation, vol. 1, no. 1, pp. 2549, 1993. [7] I. Stancic, J. Music, and M. Cecic, A novel low-cost adaptive scanner concept for mobile robots, Ingeniera e Investigacion, vol. 34, no. 3, pp. 3743, 2014. [8] K. Li, W. Zhang, Q. Lu, and X. Fang, An improved SMOTE imbalanced data classication method based on support degree, in Identication, Information and Knowledge in the Internet of Things (IIKI), 2014 International Conference on, pp. 3438, IEEE, 2014. [9] J. A. Saez, J. Luengo, J. Stefanowski, and F. Herrera, SMOTE-IPF: Addressing the noisy and borderline examples problem in imbalanced classication by a re-sampling method with ltering, Information Sciences, vol. 291, pp. 184203, 2015. [10] D. Kosir, Z. Bosnic, and I. Kononenko, The use of prediction reliability estimates on imbalanced datasets: A case study of wall shear stress in the human carotid artery bifurcation, in Medical Applications of Intelligent Data Analysis: Research Advancements, 2012.