Chapter - 2
Medicines result
Category Medicine – A Medicine – B
Male 02/10 30/90
Female 48/90 10/10
Category Medicine – A Medicine - B
Male 20.00 % 33.33 %
Female 53.33 % 100.00 %
Which medicine is overall better? 2
1
Trees for numeric prediction
1. Regression: the process of computing an
expression that predicts a numeric quantity
2. Regression tree: “decision tree” where
each leaf predicts a numeric quantity
3. Predicted value is average value of training
instances that reach the leaf
Constructing decision trees
Strategy: top down
1. Recursive divide and conquer fashion
2. First: select attribute for root node
3. Create branch for each possible attribute value
4. Then: split instances into subsets
5. One for each branch extending from the node
6. Finally: repeat recursively for each branch,
using only instances that reach the branch
Stop if all instances have the same class
2
Data mining process
Problem
Definition
Acquisition of
Background
Knowledge
Selection of Data
Pre-processing of data
Analysis and
Interpretation
Reporting and
use
Applications
• Fraud detection and risk analysis
• Medical diagnosis & treatment
• Biomedical & DNA data analysis
• Credit card fraud detection
• Gambling
• Identifying criminals & profiling
• Insurance coverage
• Money laundry detection
• Risk of loan payment
• Sale, promotion and marketing
• Stock market analysis
• Telecommunications
3
Credibility:
Evaluating what’s been learned
• Issues: training, testing, tuning
• Predicting performance – Confidence Limit
• Holdout, cross-validation, bootstrap, leave-
one-out
• Cost-sensitive measures
Costs assigned to different types of errors
Many practical applications involve costs
• The Minimum Description Length principle
Training and testing I
• Natural performance measure for classification
problems: error rate
– Success: instance’s class is predicted correctly
– Error: instance’s class is predicted incorrectly
– Error rate: proportion of errors made over the
whole set of instances
• How predictive is the model we learned?
• Error on the training data is not a good
indicator of performance on future data
4
Training and testing II
• Test set: independent instances that have played no
part in formation of classifier
– Assumption: both training data and test data are
representative samples of the underlying problem
• Test and training data may differ in nature
– Example: classifiers built using customer data from
two different towns A and B
– To estimate performance of classifier from town A
in completely new town, test it on data from B
Note on parameter tuning
• It is important that the test data is not used in
any way to create the classifier
• Some learning schemes operate in two stages:
– Stage 1: build the basic structure
– Stage 2: optimize parameter settings
• The test data can’t be used for parameter
tuning!
• Proper procedure uses three sets: training data,
validation data, and test data
– Validation data is used to optimize parameters
10
5
Making the most of the data
• Once evaluation is complete, all the data can be used
to build the final classifier
• Generally, the larger the training data the better the
classifier
• The larger the test data the more accurate the error
estimate
• Holdout procedure: method of splitting original data
into training and test set
– Dilemma: ideally both training set and test set should be
large!
11
Holdout estimation
• What to do if the amount of data is limited?
• The holdout method reserves a certain amount for
testing and uses the remainder for training
– Usually: one third for testing, the rest for
training
• Problem: the samples might not be representative
– Example: class might be missing in the test data
• Advanced version uses stratification
– Ensures that each class is represented with
approximately equal proportions in both
subsets
12
6
Repeated holdout method
• Holdout estimate can be made more reliable by
repeating the process with different subsamples
– In each iteration, a certain proportion is
randomly selected for training (possibly with
stratification)
– The error rates on the different iterations are
averaged to yield an overall error rate
• This is called the repeated holdout method
• Still not optimum: the different test sets overlap
– Can we prevent overlapping?
13
Cross-validation
• Cross-validation avoids overlapping test sets
– First step: split data into k subsets of equal size
– Second step: use each subset in turn for
testing, the remainder for training
• Called k-fold cross-validation
• Often the subsets are stratified before the cross-
validation is performed
• The error estimates are averaged to yield an
overall error estimate
14
7
More on cross-validation
• Standard method for evaluation: stratified tenfold
Cross validation
Why ten?
• Extensive experiments have shown that this is the best
choice to get an accurate estimate
• There is also some theoretical evidence for this
• Stratification reduces the estimate’s variance
• Even better: repeated stratified cross validation
• E.g. Tenfold Cross validation is repeated ten times and
results are averaged (reduces the variance)
15
Leave-One-Out cross-validation
• Leave-One-Out:
a particular form of cross-validation:
– Set number of folds equal to number of training
instances
– I.e., for n training instances, build classifier n times
• Makes best use of the data
• Involves no random sub sampling
• Very computationally expensive
16
8
Leave-One-Out-CV and stratification
• Disadvantage of Leave-One-Out-CV:
stratification is not possible
– It guarantees a non-stratified sample because
there is only one instance in the test set!
• Extreme example: random dataset split
equally into two classes
17
The bootstrap
• CV uses sampling without replacement
– The same instance, once selected, can not be selected
again for a particular training/test set
• The bootstrap uses sampling with replacement to
form the training set
– Sample a dataset of n instances n times with
replacement to form a new dataset
of n instances
– Use this data as the training set
– Use the instances from the original
dataset that don’t occur in the new
training set for testing
18
9
The 0.632 bootstrap
Also called the 0.632 bootstrap
• A particular instance has a probability of 1–1/n
of not being picked
• Thus its probability of ending up in the test data is:
n −1
(1−1/n) ≈ e ≈ 0.368
• This means the training data will contain
approximately 63.2% of the instances
19
Comparing data mining schemes
Frequent question: which of two learning schemes
performs better?
● Note: this is domain dependent!
● Obvious way: compare 10 fold CV estimates
● Generally sufficient in applications (we don't
loose if the chosen method is not truly better)
● However, what about machine learning research?
Need to show convincingly that a particular
method works better
20
10
Interpreting the result
• All our cross-validation estimates are
based on the same dataset
• Samples are not independent
• Should really use a different dataset
sample for each of the k estimates used in
the test to judge performance across
different training sets
21
Cost-sensitive learning
• Most learning schemes do not perform cost-
sensitive learning
– They generate the same classifier no matter
what costs are assigned to the different
classes
– Example: standard decision tree learner
• Simple methods for cost-sensitive learning:
– Resampling of instances according to costs
– Weighting of instances according to costs
22
11
Model selection criteria
• Model selection criteria attempt to find a good
compromise between:
1. The complexity of a model
2. Its prediction accuracy on the training data
• Reasoning: a good model is a simple model
that achieves high accuracy on the given data
• Also known as Occam’s Razor :
the best theory is the smallest one
that describes all the facts
William of Ockham, born in the village of Ockham in Surrey
(England) about 1285, was the most influential philosopher of the
14th century and a controversial theologian.
23
Elegance vs. errors
• Theory 1: very simple, elegant theory that
explains the data almost perfectly
• Theory 2: significantly more complex theory
that reproduces the data without mistakes
• Theory 1 is probably preferable
24
12
THANK YOU
25
13