Chapter 8: Evaluation of Classifiers Flashcards
1
Q
The CRISP Data Mining Process
A
2
Q
Precision of Classifier Performance
A
- Holdout procedure - split data into two sets
- E.g. 66% training, 33% testing (aka holdout procedure)
- The more training instances, the better (after a certain size the performance might stagnate)
- The more test data, the better the estimation of the error rate
- Use k-fold cross validation
- Split into k sets
- Generate k models with k-1 sets (leave one set out)
- Test each model on kth set
- Use leave-one-out (jackknife)
- Generate n models on (n-1) instances
- Apply model to nth instance
3
Q
Holdout Procedures
A
- Holdout procedure:
- Reserve some data for testing (usually ~1/3) [ select random}
- Use remaining data for training
- Plentiful data - no problem!
- Common case: data set is limited
- Problems:
- Want both sets as large as possible
- Want both sets to be representative
4
Q
“Smart” Holdout
A
- Simple check: Are the proportions of classes about the same in each data set?
- Stratified holdout
- Guarantee that classes are (approximately) proportionally represented in the test and training set
- Repeated holdout (in addition) Do with different sets and multiple time to get independent Test data
- Randomly select holdout set several times and average the error rate estimates
5
Q
Cross Validation
A
6
Q
Holdout w/ Cross-Validation
A
- Fixed number of k partitions of the data (folds)
- In turn: each partition is used for testing and the remaining
- instances for training
- Finally each instance is used for testing once
- May use stratification
- Standard practice: stratified tenfold cross-validation Error rate is estimated by taking the average of error rates
7
Q
Leave-One-Out Holdout
A
- n-Fold Cross-Validation
- n instances are in the data set
- Use all but one instance for training
- Each iteration is evaluated by predicting the omitted instance
- Advantages / Disadvantages
- Maximum use of the data for training
- Deterministic (no random sampling of test sets)
- High computational cost
- Non-stratified sample!
8
Q
Comparing Mining Algorithms
A
- Suppose we have two algorithms
- Obtain two different models
- Estimate the error rates for the two models
- Compare estimates
- e(1) < e(2)?
- Select the better one
- Problem?
- Are there “significant” differences in the error rates?
9
Q
Comparing Random Estimates
A
- Estimated error rate is just an estimate (random)
- Student’s paired t-test tells us whether the means of two samples are significantly different
- Construct a t-test statistic
- Need variance as well as point estimates
10
Q
Counting the Costs of comparing classification errors
A
- In practice, different types of classification errors often incur different costs Examples:
- Predicting when customers leave a company for competitors (attrition/churn prognosis)
- Much more costly to lose a valuable customer
- Much less costly to act on a false customer
- Predicting when customers leave a company for competitors (attrition/churn prognosis)
- Loan decisions
- Oil-slick detection
- Fault diagnosis
- Promotional mailing
11
Q
Direct Marketing Paradigm
A
- Find most likely prospects to contact
- Not everybody needs to be contacted
- Number of targets is usually much smaller than number of prospects
- Typical applications (You are only looking for small part)
- retailers, catalogues, direct mail (and e-mail)
- customer acquisition, cross-sell, attrition prediction
- …
12
Q
Direct Marketing Evaluation
A
- Accuracy on the entire dataset is not the right measure (in decision tree leaf node provides propability)
- Approach
- develop a target model
- score all prospects and rank them by decreasing score
- select top P% of prospects for action
- How to decide what is the best selection?
13
Q
Generating a Gain Curve
A
- Instances are sorted according to their predicted probability:
- In a gain curve
- x axis is sample size
- y axis is number of positives
14
Q
Gain Curve: Random List vs. Model-ranked List
A
15
Q
Lift Curve
A
16
Q
ROC Curves
A
- Differences to gain chart:
- y axis shows percentage of true positives in sample (rather than absolute number):
- TP=(#T predicted T)/#T
- x axis shows percentage of false positives in sample (rather than sample size):
- FP=(#F predicted T)/#F
- provided by true but false
- y axis shows percentage of true positives in sample (rather than absolute number):
- ROC curves are similar to gain curves
- “ROC” stands for “receiver operating characteristic”
- Used in signal detection to show tradeoff between hit rate and false alarm rate over noisy channel
- Go throught all sizes of a sample and plot FP vs. TP
17
Q
ROC Curves for Two Classifiers
A
24
Q
Inductive Learning Systems
A
25
Q
Randomness vs. Regularity
A
- 0110001101…
- random string=incompressible=maximal information
- 010101010101010101
- regularity of repetition allows compression
- If the training set is ‘representative’ then regularities in the training set will be representative for regularities in an unseen test set.
- A lot of forms of learning can be described as data compression in the following sense:
27
Q
Kolmogorov Complexity
A
- Let x be a finite length binary string and U a universal computer.
- Let U(p) be the output of U when presented with program p.
- The Kolmogorov complexity of string x is the minimal description length of x.
30
Q
Indexing
A
Before compression, the pieces of text from the breaking- down process are indexed from 1 to n:
31
Q
LZ
A
- Indices are used to number the pieces of data.
- The empty string (start of text) has index 0.
- The piece indexed by 1 is a. Thus a, together with the initial string, must be numbered Oa.
- String 2, aa, will be numbered 1a, because it contains a, whose index is 1, and the new character a.
