Comparative Study Of Learning From Imbalanced Data

Project and Seminar Material for Computer Science and Computer Engineering

Comparative Study Of Learning From Imbalanced Data


Abstract


The automation of most of our activities has led to the continuous production of data that arrive in the form of fast-arriving streams. In a supervised learning setting, instances in these streams are labeled as belonging to a particular class. When the number of classes in the data stream is more than two, such a data stream is referred to as a multi-class data stream. Multi-class imbalanced data stream describes the situation where the instance distribution of the classes is skewed, such that instances of some classes occur more frequently than others. Classes with the frequently occurring instances are referred to as the majority classes, while the classes with instances that occur less frequently are denoted as the minority classes.

Classification algorithms, or supervised learning techniques, use historic instances to build models, which are then used to predict the classes of unseen instances. Multi-class imbalanced data stream classification poses a great challenge to classical classification algorithms. This is due to the fact that traditional algorithms are usually biased towards the majority classes, since they have more examples of the majority classes when building the model. The research conducted in this thesis aims to address this research gap by proposing a novel online learning methodology that combines oversampling of the minority classes with cluster-based majority class under-sampling, without decomposing the data stream into multiple binary sets. Sampling involves continuously selecting a balanced number of instances across all classes for model building.

Our focus is on improving the rate of correctly predicting instances of the minority classes in multi-class imbalanced data streams, through the introduction of the Synthetic Minority Over-sampling Technique (SMOTE) and Cluster-based Under-sampling Technique – Data Streams (CUT-DS) methodologies. In this work, we dynamically balance the classes by utilizing a windowing mechanism during the incremental sampling process. Our CUT-DS algorithms are evaluated using six different types of classification techniques, followed by comparing their results against a state-of-the-art algorithm. Our contributions are tested using both synthetic and real data sets. The experimental results show that the approaches developed in this thesis yield high prediction rates of minority instances as contained in the multiple minority classes within a non-evolving stream.


Chapter One


Introduction

1.1 Background to the Study

In recent years, information and its transformation into Knowledge became crucial as more and more data is being generated in real world situations which is drastically varying the provision of services for use of predictive analytics or other certain advanced methods to extract value from such data, and seldom to a particular size of data set. However providing a scientific discipline that explores the construction and study of algorithms that can learn from data. Such algorithms operate by building a model from example inputs and using that to make predictions or decisions, rather than following strictly static program instructions. Machine Learning has become one of the mainstays of information technology and with that, a rather central, albeit usually hidden, part of our life. With the ever increasing amounts of data becoming available there is good reason to believe that smart data analysis will become even more pervasive as a necessary ingredient for technological progress.

With this rapid growth several difficult machine learning “real-world” problems are posed, these problems are being characterized by imbalanced learning data, where at least one class is under-represented relative to others. Examples include (but are not limited to): fraud/intrusion detection, medical diagnosis/monitoring, bioinformatics, and text categorization. The imbalanced learning problem has drawn a significant amount of interest from academia, industry, and government funding agencies. The fundamental issue with the imbalanced learning problem is the ability of imbalanced data to significantly compromise the performance of most standard learning algorithms. Most standard algorithms assume or expect balanced class distributions or equal misclassification costs. Therefore, when presented with complex imbalanced data sets, these algorithms fail to properly represent the distributive characteristics of the data and resultantly provide unfavorable accuracies across the classes of the data. When translated to real-world domains, the imbalanced learning problem represents a recurring problem of high importance with wide-ranging implications, warranting increasing exploration.

On these basis this Project seeks to provide a detailed comparative study of the current understanding of the imbalanced learning problem and the state-of-the-art solutions created to address this problem providing ensembles to address class imbalance, the assessment metrics for imbalanced learning and highlighting the major opportunities and challenges for learning from imbalanced data.


1.2 Statement of the Problem

In recent years the problem of imbalanced data has being recognized and is being considered as a very crucial problem in data mining and machine learning, this problem occurs when there is significantly fewer training instances of one class compared to another class often associated with asymmetric costs of misclassifying elements of different classes. Additionally the distribution of the test data may differ from that of the learning sample and the true misclassification costs may be unknown at learning time. The problem with class imbalances is that standard learners are often biased towards the majority class and that is because these classifiers attempt to reduce global quantities such as the error rate, not taking the data distribution into consideration. Although much awareness of the issues related to data imbalance has been raised, many of the key problems still remain open and are in fact encountered more often, especially when applied to massive datasets. In this project, we concentrate on the two class case.


1.3 Objectives of the Study

In this project, we seek to;

  1. Provide a survey of the current understanding of the imbalanced learning problem and the state-of-the-art solutions created to address this problem.
  2. Recognize and state crucial real world problems with imbalanced data.
  3. Provide strategies of dealing with data in imbalanced domain.
  4. Provide a critical review of the innovative research developments targeting the imbalanced learning problems
  5. Stimulate future research in this field, highlighting the major opportunities and challenges for learning from imbalanced data.
  6. To comparatively study and determine the most efficient algorithm in learning from imbalanced data.
  7. Provides various suggested methods that are used to compare and evaluate the performance of different imbalanced learning algorithms.
  8. Provide Strategies to deal with imbalanced data sets.

1.4 Significance of the Study

With the constant expansion of data availability in many large-scale, complex, and networked systems, such as surveillance, security, Internet, and finance, it becomes critical to advance the fundamental understanding of knowledge discovery and analysis from raw data to support decision-making processes. Hence a great influx of attention needs to be devoted to the imbalanced learning problem and the high activity of advancement in this field, remaining knowledgeable of all current developments can be an overwhelming task. Due to the relatively young age of this field and because of its rapid expansion, consistent assessments of past and current works in the field in addition to projections for future research are essential for long-term development. In this work, we will analyze the imbalanced learning problem which is concerned with the performance of learning algorithms in the presence of underrepresented data and severe class distribution skews, providing a comprehensive review of the development of research in learning from imbalanced data. Our focus is to provide a critical review of the nature of the problem, the state-of-the-art technologies, and the current assessment metrics used to evaluate learning performance under the imbalanced learning scenario. Furthermore, in order to stimulate future research in this field, we also highlight the major opportunities and challenges, as well as potential important research directions for learning from imbalanced data.


1.5 Scope of the Study

The study is restricted to the nature of Imbalanced data, providing comparative study of learning schemes for learning from imbalanced data. The scope of the study in broad terms of other than learning from imbalanced data. Few among them are;

Machine Learning algorithmic approach to learning from imbalanced data such as decision Trees (The Naïve Bayes Tree), and Artificial Neural network (The Multilayer Perceptron )

Machine learning performance evaluation measures.

Performance and monitoring measures used in evaluating imbalanced data learning.

Model Creation that would be used for learning from imbalanced data


1.6 Project Management

The work involved in the development of this project has been broken down into several steps and allocated across, considerably. The details are contained in (appendix A).


1.7 Organization of the Study

This study consist of the following sections:

Chapter 1 – Introduction

This chapter gives the introduction of the entire report, presenting the historical background of the study, the rationale behind the work, imbalanced data and learning for such data giving the problem definition and aims/ objectives of the study

Chapter 2 – Literature Review

In this section a detail review of related study is being carried out hence discovering the theoretical framework upon which this research is built.

Chapter 3 – Research Methodology and Application

In this section we have considered few methodologies used in the analysis of imbalanced data, focusing on the imbalanced data learning algorithms. Data-sets from the Keel repository with different imbalance ratios (IRs).

Chapter 4 – Implementation and Evaluation

In this section machine learning algorithms the Naïve Bayes tress and the Multi-Layer Perceptron are used for learning on imbalanced datasets which are evaluated and implemented, providing evaluation metrics for imbalanced data classification problem. Hence we will show the experimental study carried out on the behavior of some algorithms, it also examine the use of non-parametric test for statistical comparisons of the results of the classifiers. In this section we will analyze the behaviors of the best combination of components under different IR levels.

Chapter 5 – Discussion, Evaluation and conclusion

This section gives a detailed summary of the results are indicated and some conclusions and recommendations based on the findings will be made also providing suggestion (s) for future research, made for other investigations to carry out research in the related field or area.


1.8 Operational Definition

1.7.1 Concepts
Algorithm

It is a step by step finite sequence of well-defined set of instructions used to solve problems on a computer, a computational procedure that takes values as input and produces values as output, in order to solve a well-defined computational problem

Data

Numbers, characters, images, or other method of recording, in a form which can be assessed by a human or (especially) input into a computer, stored and processed there, or transmitted on some digital channel.

Data Mining

Is an analytic process designed to explore data (usually large amounts of data – typically business or market related – also known as “big data”) in search of consistent patterns and/or systematic relationships between variables, and then to validate the findings by applying the detected patterns to new subsets of data

Imbalanced Dataset

A dataset is imbalanced if the classification categories are not approximately equally represented that is the classes are not approximately equally represented.

Learning

Is the act of acquiring new, or modifying and reinforcing, existing knowledge, behaviors, skills, values, or preferences and may involve synthesizing different types of information

Machine

An apparatus using mechanical power and having several parts, each with a definite function and together performing a particular task.

Machine Learning

A scientific discipline that explores the construction and study of algorithms that can learn from data and make/take decision on unseen data based on what they have learned from previous data.

Mining

A term explaining the process of finding a small set of precious patterns from a great deal of raw material (big data)

Comparative

Comparative study is a research methodology that aims to make comparisons across different field in this case algorithms used in learning from imbalanced data.

Attribute

A piece of information which determines the properties of a field or tag in a database or a string of characters in a display.

1.7.2 Technology
Decision Tree

A predictive model which maps observations about an item to conclusions about the item’s target value. It is one of the predictive modelling approaches used in statistics, data mining and machine learning.

Cross Validation

Cross validation sometimes called rotation estimation is a model validation technique for assessing how accurate and valid the result of a statistical analysis method will be.

Artificial Neural Network

Family of statistical learning algorithms inspired by biological neural networks (the central nervous systems of animals, in particular the brain) and are used to estimate or approximate functions that can depend on a large number of inputs and are generally unknown. Artificial neural networks are generally presented as systems of interconnected “neurons” which can compute values from inputs, and are capable of machine learning as well as pattern recognition, what makes them interesting is their adaptive nature.

1.8.3 Tools
Keel (Knowledge Extraction based on Evolutionary Learning)

Is an open source (GPLv3) Java software tool which empowers the user to assess the behavior of evolutionary learning and Soft Computing based techniques for different kinds of Data Mining problems: regression, classification, clustering, Pattern mining and so on.

Datasets

A data set corresponds to the contents of a single database table, or a single statistical data matrix, where every column of the table represents a particular variable, and each row corresponds to a given member of the data set in question. The data set lists values for each of the variables, such as height and weight of an object, for each member of the data set.

WEKA (Waikato Environment for Knowledge Analysis)

WEKA is a collection of machine learning algorithms for data mining tasks. The algorithms can either be applied directly to a dataset or called from your own Java code. WEKA contains tools for data pre-processing, classification, regression, clustering, association rules, and visualization. It is also well-suited for developing new machine learning schemes.


1.8 Conclusion

Machine learning is growing and expanding in a very rapid pace. Its importance and bewildered growth helps in combining of collaborative activities with sophisticated pattern recognition, intelligent decisions self-modifying and self-learning has brought about computing without infrastructure flexibility and ideal Power. This Section gives an overview and preliminary study on the study of learning pattern using imbalanced datasets evaluating algorithms that helps in the learning process.


Chapter Five


Conclusion and Future Work

In the previous chapter, we presented the experimental design of the methodologies in this study and analyzed the results of our extensive experimental evaluations. In this thesis, the focus was to develop a methodology for learning from multi-class imbalanced data stream. To this end, we extended the existing CUT algorithm from a static to the streaming environment, with the aim of yielding high recognition rates for minority instances. Experiments were performed in order to compare the performance of the two algorithms in this thesis against a benchmarking algorithm, in terms of the average recall of all minority classes in the data stream. The impacts of the choice of base learners, or classifiers, on the designed methodologies were monitored. In addition, the resilience of the algorithms to noise was investigated.

Furthermore, comparisons between the ability of the two approaches, CUT-DS and CUTDS++ to generalize on incoming streams were made. In this chapter we draw a general conclusion to the thesis by discussing the contribution of the thesis and making suggestions for future work.


5.1 Thesis Contribution

Existing studies do not directly address multi-class imbalanced data stream classification. The developed methodologies in this study were intended to address the research gap in imbalanced data set classification, more specifically in multi-class imbalanced classification in the nonstationary environment. CUT was designed for multi-class imbalanced data set in static environment, thus the need for extending to the streaming environment as researched in this thesis.

The two approaches developed in this study, which actualized our main contribution, led to the improvement in the recognition rates of the instances of the minority classes by standard classifiers through the use of our resampling technique. This enabled the direct prediction of the minority instances in multi-class imbalanced data stream, without class reduction. We focused on improving the average recalls of all minority classes present in the data set because traditional classifiers have high recall on the majority labels. Thus, the first contribution, which is the main contribution, is to extend CUT from static environments to streaming environments. Secondly, most of the methods in literature used to address imbalanced data set decompose the data set; these approaches may introduce bias to the result. The sampling approaches used in CUT-DS and CUT-DS++ directly addressed multiclass imbalanced data stream classification without resorting to class decomposition. This eliminated the bias introduced when computing the results.

Furthermore, the direct multi-class imbalanced classification algorithms for data streams in literature accumulated too much minority instances that may over overburden the system. The third contribution was the use of cluster-based under-sampling of the minority instances and the generation of synthetic minority examples to address this issue. The synthetic and accumulated past minority instances were used to increase the data space of the minority classes. The accumulation of past minority instances prevented some earlier encountered instances from being forgotten and the reliance on only the recent window. Thus, aiding the generation and selection of relevant training sets that will generalize on incoming data stream via cluster-based under-sampling.

Moreover, the use of the average of instances of the classes in the window as the sampling rate prevented excessive oversampling or under-sampling, it also reduced the computational time and resources when sampling methods are used in highly imbalanced dataset. Recall the discussion from Chapter 3 about the drawback of some methodologies that directly addressed multi-class imbalanced learning in data stream which were said to be unsuitable for highly imbalanced data sets. The adopted resampling rate removes the need to compute imbalance ratio.

Finally, the flexibility of the multi-class imbalanced algorithm is addressed because the need to assign weight, cost or the requirement for domain knowledge are eliminated. The results of the experimentation indicates that CUT-DS and CUT-DS++ successfully increased the recognition rates of the minority instances in the data stream. Typically, we have higher average recalls when compared with INTER, although this was achieved in longer time. However, as evident in the individual recalls of the minority classes in Appendix B, the individual minority recalls were higher.


5.2 Future Work

The approach in this study may be extended in order to improve further on our methodologies and to address multi-class imbalanced data stream learning in other domains. Thus, the next few points explain the areas that may be considered for improvement. We have experimented with three groups of learning algorithms, namely, HT, NB and metalearners; however, extending the study to other classification algorithms will help to observe the behavior of the other classification algorithms on the CUT-DS methodologies. We also believe this work may be extended by using other clustering algorithms apart from K-means. Experimenting with more data streams shows the flexibility and robustness of a methodology, thus the need to experiment with more data stream from other domains.
It was observed in the results of the experiments that the individual recall of some classes of minority instances were low compared to others. Hence, in a future study, the optimal sampling ratio that will be beneficial to all minority classes present in the data stream based on the distribution of instances per class in the data stream may be investigated. Another possible extension is in terms of the evaluation method used. The evaluation technique used in this project was on chunk-by-chunk bases, which could be further studied by extending the resampling and model updating approach to the instance-by-instance scenario. Thus, this would provide the option of chunk-by-chunk and instance-by-instance evaluation.

Considering that this thesis focused on only the recall of the minority instances, we will like to extend performance evaluation to the majority instances in future studies. In our implementation, we assumed that we always have a preponderance of the majority instances, thus, we under sampled the majority instances. However, in future works, it would be worth investigating how to resolve situations where majority classes may become minority classes in some windows.

As an extension to this study, which has focused on non-evolving streams, it would be worth conducting a similar research on evolving data streams. Evolving data streams are data streams with concept drift where the underlying concept may change. Hence, instances in a recent window may not be applicable to predicting incoming streams. Relying on models built from the recent chunks only, as done in CUT-DS, or accumulating minority instances from earlier chunks in CUT-DS++ may be detrimental to learning. Therefore, in future studies the goal might be to experiment on the optimal technique to use in resampling the training set in evolving data streams.


Get Complete Project Material

5,000 5000

The Complete Material Will Be Sent to You in Just 2 Steps

Quick & Simple…


Step One Purchase

Make Payment (Through Transfer) of ₦5,000 to the Account Below

Zenith BankAcc No: 1225513212
Samphina Academy
Current Account

Or CLICK HERE To Pay With Debit Card


FOR STUDENTS OUTSIDE NIGERIA
CLICK HERE To Purchase Material ($15)

Step Two Purchase

Send the Following Details on WhatsApp ( 08143831497) After Payment

  1. Payment Details

  2. TOPIC: Comparative Study Of Learning From Imbalanced Data

The Complete Material Will Be Sent To You On WhatsApp After Receiving Your Details
T & C Apply


  Contact Our Help Desk


Need a Different Topic? Perform a Quick Search



List of Related Works

Click on Any Topic to Preview the Content

samphina.academy

Samphina Academy

Samphina Academy is an Online Educational Resource Center that is aimed at providing students with quality information and materials to aid them in succeeding in their academic pursuit.