Classification
Classification
• Classification is a form of data analysis that extracts models describing important data classes.
• Such models, called classifiers, predict categorical (discrete, unordered) class labels.
• For example, we can build a classification model to categorize bank loan applications as either
safe or risky.
• Such analysis can help provide us with a better understanding of the data at large.
• Many classification methods have been proposed by researchers in machine learning, pattern
recognition, and statistics.
Classification
Most algorithms are memory resident, typically assuming a small data size.
Recent data mining research has built on such work, developing scalable classification and
prediction techniques capable of handling large amounts of disk-resident data.
Classification has numerous applications, including fraud detection, target marketing,
performance prediction, manufacturing, and medical diagnosis.
What is classification?
A bank loans officer needs analysis of her data to learn which loan applicants are “safe”
and which are “risky” for the bank.
A marketing manager at AllElectronics needs data analysis to help guess whether a customer
with a given profile will buy a new computer.
A medical researcher wants to analyze breast cancer data to predict which one of three
specific treatments a patient should receive.
In each of these examples, the data analysis task is classification, where a model or classifier is
constructed to predict class (categorical) labels, such as “safe” or “risky” for the loan application
data; “yes” or “no” for the marketing data; or “treatment A,” “treatment B,” or “treatment C” for
the medical data.
What is classification?
These categories can be represented by discrete values, where the ordering among values has
no meaning.
For example, the values 1, 2, and 3 may be used to represent treatments A, B, and C, where
there is no ordering implied among this group of treatment regimes.
What is classification?
Suppose that the marketing manager wants to predict how much a given customer will spend
during a sale at AllElectronics.
This data analysis task is an example of numeric prediction, where the model constructed
predicts a continuous-valued function, or ordered value, as opposed to a class label. This model
is a predictor.
Regression analysis is a statistical methodology that is most often used for numeric prediction;
hence the two terms tend to be used synonymously, although other methods for numeric
prediction exist.
Classification and numeric prediction are the two major types of prediction problem.
“How does classification work?”
Data classification is a two-step process, consisting of a learning step (where a
classification model is constructed) and a classification step (where the model is
used to predict class labels for given data).
The process is shown for the loan application data of Figure 8.1. (The data are
simplified for illustrative purposes. In reality, we may expect many more
attributes to be considered.
Classification
In the first step, a classifier is built describing a predetermined set of data classes
or concepts.
This is the learning step (or training phase), where a classification algorithm
builds the classifier by analyzing or “learning from” a training set made up of
database tuples and their associated class labels.
A tuple, X, is represented by an n-dimensional attribute vector, X = (x1, x2, … , xn ),
depicting n measurements made on the tuple from n database attributes,
respectively, A1, A2, … , An .
Classification
Each tuple, X, is assumed to belong to a predefined class as determined by
another database attribute called the class label attribute.
The class label attribute is discrete-valued and unordered.
It is categorical (or nominal) in that each value serves as a category or class.
The individual tuples making up the training set are referred to as training
tuples and are randomly sampled from the database under analysis.
In the context of classification, data tuples can be referred to as samples,
examples, instances, data points, or objects.
Classification
Because the class label of each training tuple is provided, this step is also known
as supervised learning (i.e., the learning of the classifier is “supervised” in that it
is told to which class each training tuple belongs).
It contrasts with unsupervised learning (or clustering), in which the class label
of each training tuple is not known, and the number or set of classes to be
learned may not be known in advance.
Fig 8.1 Classification process (a) Learning
Fig 8.1 Classification process (b) training
“What about classification
accuracy?”
In the second step (Figure 8.1b), the model is used for classification.
First, the predictive accuracy of the classifier is estimated.
If we were to use the training set to measure the classifier’s accuracy, this estimate would likely
be optimistic, because the classifier tends to overfit the data (i.e., during learning it may
incorporate some particular anomalies of the training data that are not present in the
general data set overall).
Therefore, a test set is used, made up of test tuples and their associated class labels.
They are independent of the training tuples, meaning that they were not used to construct the
classifier.
“What about classification
accuracy?”
The accuracy of a classifier on a given test set is the percentage of test set
tuples that are correctly classified by the classifier.
The associated class label of each test tuple is compared with the learned
classifier’s class prediction for that tuple.
If the accuracy of the classifier is considered acceptable, the classifier can be
used to classify future data tuples for which theclass label is not known. (Such
data are also referred to in the machine learning literature as “unknown” or
“previously unseen” data.)
Decision Tree Induction
Decision tree induction is the learning of decision trees from class-labeled training
tuples.
A decision tree is a flowchart-like tree structure, where each internal node (non-leaf node)
denotes a test on an attribute, each branch represents an outcome of the test, and each leaf
node (or terminal node) holds a class label.
Decision Trees
The topmost node in a tree is the root node.
A typical decision tree is shown in Figure 8.2.
It represents the concept buys computer, that is, it predicts whether a
customer at AllElectronics is likely to purchase a computer.
Internal nodes are denoted by rectangles, and leaf nodes are denoted by ovals.
Some decision tree algorithms produce only binary trees (where each internal
node branches to exactly two other nodes), whereas others can produce non-
binary trees.
“How are decision trees used for
classification?”
Given a tuple, X, for which the associated class label is unknown, the attribute
values of the tuple are tested against the decision tree.
A path is traced from the root to a leaf node, which holds the class prediction
for that tuple.
Decision trees can easily be converted to classification rules.
Decision tree induction
algorithm
During tree construction, attribute selection measures are used to select the
attribute that best
partitions the tuples into distinct classes.
We will discuss popular measures of attribute selection.
When decision trees are built, many of the branches may reflect noise or
outliers in the training data.
Tree pruning attempts to identify and remove such branches, with the goal of
improving classification accuracy on unseen data.
Decision tree induction
algorithm
Decision tree learning employs a divide and conquer strategy by conducting a
greedy search to identify the optimal split points within a tree.
This process of splitting is then repeated in a top-down, recursive manner until
all, or the majority of records have been classified under specific class labels.
Advantages
Decision trees have a number of characteristics, which make it more flexible
than other classifiers.
It can handle various data types—i.e. discrete or continuous values, and
continuous values can be converted into categorical values through the use of
thresholds.
Additionally, it can also handle values with missing values, which can be
problematic for other classifiers, like Naïve Bayes.
Their representation of acquired knowledge in tree form is intuitive and
generally easy to assimilate by humans.
Advantages
The learning and classification steps of decision tree induction are simple and
fast.
In general, decision tree classifiers have good accuracy.
Decision tree induction algorithms have been used for classification in many
application areas such as medicine, manufacturing and production, financial
analysis, astronomy, and molecular biology.
Decision trees are the basis of several commercial rule induction systems.
Disadvantages
Prone to overfitting:
Complex decision trees tend to overfit and do not generalize well to new data. This
scenario can be avoided through the processes of pre-pruning or post-pruning.
Pre-pruning halts tree growth when there is insufficient data while post-pruning
removes subtrees with inadequate data after tree construction.
High variance estimators: Small variations within data can produce a very different
decision tree.
More costly: Given that decision trees take a greedy search approach during
construction, they can be more expensive to train compared to other algorithms.