Transcript Classification

Data Mining:
Concepts and Techniques
— Chapter 4 —
Classification
April 5, 2016
Data Mining: Concepts and Techniques
1
1
What Is Classification?
• The goal of data classification is to organize and
categorize data in distinct classes
– A model is first created based on the data distribution
– The model is then used to classify new data
– Given the model, a class can be predicted for new data
• Classification = prediction for discrete and nominal
values
– With classification, I can predict in which bucket to put the ball,
but I can’t predict the weight of the ball
2
Prediction, Clustering, Classification
• What is Prediction?
– The goal of prediction is to forecast or deduce the value of an attribute
based on values of other attributes
– models continuous-valued functions, i.e., predicts unknown or missing values
– A model is first created based on the data distribution
– The model is then used to predict future or unknown values
• Supervised vs. Unsupervised Classification
– Supervised Classification = Classification
• We know the class labels and the number of
classes
– Unsupervised Classification = Clustering
• We do not know the class labels and may not know
the number of classes
3
Classification and Prediction
• Typical applications
–
–
–
–
Credit approval
Target marketing
Medical diagnosis
Fraud detection
4
Classification: 3 Step Process
• 1. Model construction (Learning):
– Each record (instance) is assumed to belong to a predefined class, as
determined by one of the attributes, called the class label
– The set of all records used for construction of the model is called training set
– The model is usually represented in the form of classification rules, (IF-THEN
statements) or decision trees
• 2. Model Evaluation (Accuracy):
–
–
–
–
Estimate accuracy rate of the model based on a test set
The known label of test sample is compared with the classified result from model
Accuracy rate: percentage of test set samples correctly classified by the model
Test set is independent of training set otherwise over-fitting will occur
• 3. Model Use (Classification):
– The model is used to classify unseen instances (assigning class labels)
– Predict the value of an actual attribute
5
Process (1): Model Construction
Training
Data
NAME
M ike
M ary
B ill
Jim
D ave
Anne
RANK
YEARS TENURED
A ssistan t P ro f
3
no
A ssistan t P ro f
7
yes
P ro fesso r
2
yes
A sso ciate P ro f
7
yes
A ssistan t P ro f
6
no
A sso ciate P ro f
3
no
Classification
Algorithms
Classifier
(Model)
IF rank = ‘professor’
OR years > 6
THEN tenured = ‘yes’
6
Process (2): Using the Model in Prediction
Classifier
Testing
Data
Unseen Data
(Jeff, Professor, 4)
NAME
Tom
M erlisa
G eo rg e
Jo sep h
RANK
YEARS TENURED
A ssistan t P ro f
2
no
A sso ciate P ro f
7
no
P ro fesso r
5
yes
A ssistan t P ro f
7
yes
Tenured?
7
Accuracy of Supervised Learning
• Holdout Approach
– A certain amount of data (Usually, one-third) for testing and
remainder (two-third) for training
• K-Fold cross validation
– Split the data into k subsets of equal size, then each subset is turn is
used for testing and remainder for training
8
Issues: Data Preparation
• Data cleaning
– Preprocess data in order to reduce noise and handle missing values
• Relevance analysis (feature selection)
– Remove the irrelevant or redundant attributes
• Data transformation
– Normalize data
9
Issues: Evaluating Classification Methods
• Accuracy
– classifier accuracy: predicting class label
– predictor accuracy: guessing value of predicted attributes
• Speed
– time to construct the model (training time)
– time to use the model (classification/prediction time)
• Robustness: handling noise and missing values
• Scalability: efficiency in disk-resident databases
• Interpretability
– understanding and insight provided by the model
• Other measures, e.g., goodness of rules, such as decision tree
size or compactness of classification rules
10
Other Issues
• Function complexity and amount of training data
– If the true function is simple then an learning algorithm will be able to
learn it from a small amount of data, otherwise the function will only
be learnable from a very large amount of training data.
• Dimensionality of the input space
• Noise in the output values
• Heterogeneity of the data.
– If the feature vectors include features of many different kinds
(discrete, discrete ordered, counts, continuous values), some
algorithms are easier to apply than others.
• Dependency of features
11
Decision Tree - Review of Basics
What exactly is a Decision Tree?
A tree where each branching node represents a choice between two or
more alternatives, with every branching node being part of a path to a
leaf node (bottom of the tree). The leaf node represents a decision,
derived from the tree for the given input.
● How can Decision Trees be used to classify instances of data?
Instead of representing decisions, leaf nodes represent a particular
classification of a data instance, based on the given set of attributes (and
their discrete values) that define the instance of data, which is kind of like
a relational tuple for illustration purposes.
12
Review of Basics (cont’d)
• It is important that data instances have boolean or discrete
data values for their attributes to help with the basic
understanding of ID3, although there are extensions of ID3
that deal with continuous data.
13
How does ID3 relate to Decision Trees, then?
• ID3, or Iterative Dichotomiser 3 Algorithm, is a Decision Tree learning
algorithm. The name is correct in that it creates Decision Trees for
“dichotomizing” data instances, or classifying them discretely through
branching nodes until a classification “bucket” is reached (leaf node).
•
By using ID3 and other machine-learning algorithms from Artificial
Intelligence, expert systems can engage in tasks usually done by human
experts, such as doctors diagnosing diseases by examining various
symptoms (the attributes) of patients (the data instances) in a complex
Decision Tree.
• Of course, accurate Decision Trees are fundamental to Data Mining and
Databases.
14
Other Decision Trees
• ID3
• J48
• C4.5
•
•
•
•
•
•
SLIQ
SPRINT
PUBLIC
RainForest
BOAT
Data Cube-based Decision Tree
15
Tree Presentation
16
Decision Tree Induction: Training Dataset
age
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
income student credit_rating
high
no fair
high
no excellent
high
no fair
medium
no fair
low
yes fair
low
yes excellent
low
yes excellent
medium
no fair
low
yes fair
medium
yes fair
medium
yes excellent
medium
no excellent
high
yes fair
medium
no excellent
buys_computer
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no
17
Output: A Decision Tree for “buys_computer”
age?
<=30
31..40
overcast
student?
no
no
yes
yes
yes
>40
credit rating?
excellent
fair
yes
18
Algorithm for Decision Tree Induction
• Basic algorithm (a greedy algorithm)
– Tree is constructed in a top-down recursive divide-and-conquer manner
– At start, all the training examples are at the root
– Attributes are categorical (if continuous-valued, they are discretized in
advance)
– Examples are partitioned recursively based on selected attributes
– Test attributes are selected on the basis of a heuristic or statistical measure
(e.g., information gain)
• Conditions for stopping partitioning
– All samples for a given node belong to the same class
– There are no remaining attributes for further partitioning – majority voting is
employed for classifying the leaf
– There are no samples left
19
Entropy
• S is the training example
•
is the proportion of positive examples in S
•
is the proportion of negative examples in S
• Entropy measures the impurity of S
• For Non-Boolean classification :
P 
6
2
P

8  8
2
2
6
6
E  ( log 2 )  ( log 2 )
8
8
8
8
20
Attribute Selection Measure: Information Gain
(ID3/C4.5)
Gain (S,A) = Expected reduction in entropy due to sorting on A
21
Attribute Selection: Information Gain
age
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
income student credit_rating buys_computer
high
no fair
no
high
no excellent
no
high
no fair
yes
medium
no fair
yes
low
yes fair
yes
low
yes excellent
no
low
yes excellent
yes
medium
no fair
no
low
yes fair
yes
medium yes fair
yes
medium yes excellent
yes
medium
no excellent
yes
high
yes fair
yes
medium
no excellent
no

vvalue( A )
sv
S
Entropy( S v ) 

Gain for Age
S 30
S
Entropy( S 30 ) 
• Class P: buys_computer = “yes”
• Class N: buys_computer = “no”
Entropy( S )  
S 31..40
S
9
9
5
5
log 2 ( )  log 2 ( ) 0.940
14
14 14
14
Entropy( S 31..40 ) 
S  40
S
Entropy( S  40 )
2
3
4
3
2
5
2
3
4
4
5
3
2
( Log 2 5  Log 2 5 )  ( Log 2 4 )  ( Log 2 5  Log 2 5 )  0.694
14 5
5
14 4
14 5
5
22
Attribute Selection: Information Gain
age
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
income student credit_rating
high
no
fair
high
no
excellent
high
no
fair
medium
no
fair
low
yes fair
low
yes excellent
low
yes excellent
medium
no
fair
low
yes fair
medium
yes fair
medium
yes excellent
medium
no
excellent
high
yes fair
medium
no
excellent
buys_computer
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no
Gain( S , age)  0.940  0.694  0.246
Gain( S , income)  0.029
Gain( S , student )  0.151
Gain( S , credit _ rating )  0.048
23
ID3 Algorithm
24
Computing Information-Gain for ContinuousValue Attributes
• Let attribute A be a continuous-valued attribute
• Must determine the best split point for A
– Sort the value A in increasing order
– Typically, the midpoint between each pair of adjacent values is considered as
a possible split point
• (ai+ai+1)/2 is the midpoint between the values of ai and ai+1
– The point with the minimum expected information requirement for A is
selected as the split-point for A
• Split:
– D1 is the set of tuples in D satisfying A ≤ split-point, and D2 is the set of tuples
in D satisfying A > split-point
25
Gain Ratio for Attribute Selection and Cost of Attributes
What happens if you choose Day as root ??
Attribute with Cost
26
Overfitting and Tree Pruning
• Overfitting: An induced tree may overfit the training data
– Too many branches, some may reflect anomalies due to noise or outliers
– Poor accuracy for unseen samples
• Two approaches to avoid overfitting
– Prepruning: Halt tree construction early—do not split a node if this would result in the
goodness measure falling below a threshold
•
Difficult to choose an appropriate threshold
– Postpruning: Remove branches from a “fully grown” tree—get a sequence of progressively
pruned trees
•
Use a set of data different from the training data to decide which is the “best pruned tree”
27
Enhancements to Basic Decision Tree Induction
• Allow for continuous-valued attributes
– Dynamically define new discrete-valued attributes that partition the continuous
attribute value into a discrete set of intervals
• Handle missing attribute values
– Assign the most common value of the attribute
– Assign probability to each of the possible values
• Attribute construction
– Create new attributes based on existing ones that are sparsely represented
– This reduces fragmentation, repetition, and replication
28
Instance Based Learning
• Lazy learning (e.g., instance-based learning): Simply stores
training data (or only minor processing) and waits until it is
given a test tuple
• Eager learning (eg. Decision trees, SVM, NN): Given a set of
training set, constructs a classification model before receiving
new (e.g., test) data to classify
29
Instance-based Learning
Its very similar to a
Desktop!!
30
Example
Image Scene Classification
31
Instance-based Learning
When To Consider IBL
• Instances map to points
• Less than 20 attributes per instance
• Lots of training data
Advantages:
• Learn complex target functions(Class)
• Don't lose information
Disadvantages:
• Slow at query time
• Easily fooled by irrelevant attributes
32
K-Nearest Neighbor Learning (k-NN)
• k-NN is a type of instance-based learning, or lazy learning
where the function is only approximated locally and all
computation is deferred until classification.
• The k-nearest neighbor algorithm is amongst the simplest of
all machine learning algorithms: an object is classified by a
majority vote of its neighbors, with the object being assigned
to the class most common amongst its k nearest neighbors (k
is a positive integer, typically small).
– If k = 1, then the object is simply assigned to the class of its nearest
neighbor.
33
K-Nearest Neighbor Learning (k-NN)- Cont.
• Usually Euclidean distance is used as the distance metric;
however this is only applicable to continuous variables. In
cases such as text classification, another metric such as the
overlap metric (or Hamming distance: it measures the minimum
number ofsubstitutions required to change one string into the other, or the
number of errors that transformed one string into the other. ) can be
used.
34
Distance or Similarity Measures
• Common Distance Measures:
– Manhattan distance:
– Euclidean distance:
– Cosine similarity:
dist ( X , Y )  1  sim( X , Y )
sim( X , Y ) 
 ( xi  yi )
i
 xi   yi
2
i
2
i
35
KNN - Algorithm
• Key Idea: Just store all training examples
• Nearest Neighbour :
– Given query instance Xq , First locate nearest training example Xn ,
Then estimate
• K Nearest Neighbour :
– Given xq , take vote among its K nearest nbrs ( If discrete-value for
class)
– Take mean of f Values of k nearest nbrs (if real-value)
36
Figure K Nearest Neighbors Example
X
Stored training set patterns
X input pattern for classification
--- Euclidean distance measure to
the nearest three patterns
37
one
two
three
four
five
six
Which one belongs to Mondrian ?
seven
Eight ?
38
Training data
Number Lines Line types Rectangles Colours Mondrian?
1
6
1
10
4
No
2
4
2
8
5
No
3
5
2
7
4
Yes
4
5
1
8
4
Yes
5
5
1
10
5
No
6
6
1
8
6
Yes
7
7
1
14
5
No
Test instance
Number Lines Line types Rectangles Colours Mondrian?
8
7
2
9
4
39
Normalization
•
Min-max normalization: to [new_minA, new_maxA]
v' 
•
v  minA
(new _ maxA  new _ minA)  new _ minA
maxA  minA
Z-score normalization (μ: mean, σ: standard deviation):
v' 
•
v  A

A
Normalization by decimal scaling
v' 
v
10 j
Where j is the smallest integer such that Max(|ν’|) < 1
40
Normalised training data
Number Lines
1
Line
types
0.632
-0.632
2
-1.581
3
Rectangles Colours Mondrian?
0.327
-1.021
No
1.581
-0.588
0.408
No
-0.474
1.581
-1.046
-1.021
Yes
4
-0.474
-0.632
-0.588
-1.021
Yes
5
-0.474
-0.632
0.327
0.408
No
6
0.632
-0.632
-0.588
1.837
Yes
7
1.739
-0.632
2.157
0.408
No
Test instance
Number Lines
8
Line
types
1.739
1.581
Rectangles Colours Mondrian?
-0.131
-1.021
41
Distances of test instance from training data
Example Distance Mondrian?
of test
from
example
1
No
2.517
2
3.644
No
3
2.395
Yes
4
3.164
Yes
5
3.472
No
6
3.808
Yes
7
3.490
No
Classification
1-NN
Yes
3-NN
Yes
5-NN
No
7-NN
No
42
Example
Classify Theatre ?
43
Nearest neighbors algorithms: illustration
e1
+
-
-
q1
+
+
+
1-nearest neighbor:
the concept represented by e1
5-nearest neighbors:
q1 is classified as negative
44
Voronoi diagram
query
point qf
nearest neighbor qi
45
Variant of kNN: Distance-Weighted kNN
• We might want to weight nearer neighbors more heavily
w f (x )

) :
 w
k
f (x q
i 1
i
i
k
i 1
i
where wi 
1
d (x q , xi ) 2
• Then it makes sense to use all training examples instead of just k
46
Difficulties with k-nearest neighbour
algorithms
• Have to calculate the distance of the test case from all
training cases
• There may be irrelevant attributes amongst the attributes –
curse of dimensionality
• For instance , we have 20 attribute, however 2 of them are
appropriate attributes , non-relevant attributes effect to
results
• Solution : Assign appropriate Weight to the attributes by
using cross-validation method.
47
How to choose “k”
• Large k:
– less sensitive to noise (particularly class noise)
– better probability estimates for discrete classes
– larger training sets allow larger values of k
• Small k:
– captures fine structure of problem space better
– may be necessary with small training sets
• Balance must be struck between large and small k
• As training set approaches infinity, and k grows large, kNN
becomes Bayes optimal
48
‫تکليف‬
1.
2.
Use Weka to classify and evaluate Letter Recognition dataset through IBL
Write down 3 new challenges in KNN
49