Classification - Part 1

Question 1

What is the Goal of Classification

Answer 1

Previously unseen records should be assigned a class from a given set of classes as accurate as possible

Question 2

Explain the Approach of Classification

Answer 2

• You have a training set consisting of
  -attributes
  
  • a class attribute (label) with positive and negative
    examples
• Class attribute should be predicted based
• Learn a model as a function of the values of the other attributes to predict the class attribute

Question 3

Which variants of Classification exist

Answer 3

• Binary classification (fraud / no fraud)
• Multi-class classification (low, medium, high)
• Multi-label classification (more than one class per record e.g. user interests)

Question 4

What are the steps in the Model Learning and Model Application Process?

Answer 4

Training Set -> (Induction) -> Learn Model -> Model

-> Apply Model -> Deduction -> Unseen records

Question 5

Give some classification examples

Answer 5

• Credit Risk Assessment
  
  • Attributes: age, income, debts
  • Class: Credit (yes/no)
• Marketing:
  
  • Attributes: previously bought products
  • Class: Target Customer (yes/no)
• SPAM detection:
  
  • Attributes: words and header fields of e-mail
  • Class: Spam (yes/no)

Question 6

List seven classification techniques

Answer 6

• K-nearest-neighbours
• Decision Trees
• Rule Learning
• Naive Bayes
• Support Vector Machines
• Artificial Neural Networks
• Deep Neural Networks

Question 7

Explain the approach of K-nearest-neighbor

Answer 7

It requires:

• A set of stored records
• Distance measure
• k value (number of nearest neighbors to consider)

Approach:
For each unknown record:
1. Compute distance to each training record
2. Identify k-nearest neighbors
3. Use class labels of nearest neighbors to determine class of unknown record
- majority vote or
- weighting vote according to distance

Question 8

What is a k-nearest neighbor ?

Answer 8

If you have a unknown record x the k-nearest neighbors are data points that have the k smallest distance to x

Question 9

How to choose a good value for K?

Answer 9

Role of Thumb: Test k values between 1 and 20

If k too small: result is sensitive to noise points
If k is too large: neighborhood may include points from other classes

Question 10

What are the pros and cons of k-nearest-neighbor classification

Answer 10

+ Often very accurate (for optical character recognition)
- but slow (unseen records are compared to all training examples)

Neutral aspects:

• Results depend on choosing a good proximity measure
• KNN can handle decision boundaries which are not parallel to the axes

Question 11

Describe Lazy Learning

Answer 11

• Instance based learning approaches
• No explicit model is learned
• -> Less time to learn but long time to classify

Single Goal: Classify unseen records as accurately as possible

Example: KNN

Question 12

Describe Eager Learning

Answer 12

• Eager learning generate models that might be interpretable by humans
• -> Longer time for learning but less time to classify

Compared to lazy learning, eager learning has two goals:

• classify unseen records
• understand the application domain as a human

Examples: decision tree learning, rule learning

Question 13

What are the components of a decision tree classifier

Answer 13

• Root of tree
• Attribute tests (splitting attributes)
• Leaf nodes (decision - no tests / splits)

Question 14

Why are the decision boundaries of a decision tree parallel to the axes?

Answer 14

Because the test condition involves a single attribute at-a-time

-> It is a step by step division of the space into areas parallel to the axes

Question 15

How to learn a decision tree from training data?

Answer 15

1. Training data with attributes and class attribute
2. Apply Learning Algorithm
3. Decision Tree Model

• Finding optimal decision tree is NP-hard
• Algorithms use greedy, top-down, recursive partitioning to induce a reasonable solution

Example Algorithms

• Hunts Algorithm
• ID3
• CHAID

Question 16

Explain Hunt’s algorithm (decision tree)

Answer 16

• You have a training set and need to generate either leaf nodes or attribute tests
  Dt: set of training records that reach a node t

O1 ) If Dt only contains records of the same class then t is a leaf node.
O2 ) If Dt contains records with more than one class use attribute test in order to split data into subsets with a higher purity

Recursively apply procedure to each subset

Question 17

What are the design issues for learning decision trees?

Answer 17

1. How should training records be split?
   How to specify attribute test condition
   - Depends on number of splits: Binary, Multi-way split
   - Depends on attribute data type: nominal, ordinal, continuous
   How to determine the best split
   - Can use different purity measures
2. When should the splitting procedure stop?
   - Shallow trees might generalize better to unseen records
   - Fully grown trees might overfit training data

Question 18

How can you split nominal attributes in decision trees

Answer 18

• Multi-way split: use as many partitions as distinct values

- Binary split: Divides values into two subsets

Question 19

How can you split ordinal attributes in decision trees

Answer 19

• Multi-way split: use as many partitions as distinct values

- Binary split: Divides values into two subsets while keeping the order

Question 20

How can you split continuous attributes in decision trees

Answer 20

• Discretization: form an ordinal categorical attribute
• equal-interval binning
• equal-frequency binning
• user-provided boundaries binning
• Binary Decision: A > v or A <= v
• often sufficient in practice
• find best splitting border v based on purity measure
• compute intensive

Question 21

Explain equal-interval binning (decision tree splitting based on continuous attributes)

For values of the attribute age of a person:
0, 4, 12, 16, 16, 18, 24, 26, 28

Answer 21

Specify a bin width e.g. 10
Bin 1: [-,10)
Bin 2: [10,20]
Bin 3: [20,+]

Question 22

Explain equal-frequency binning (decision tree splitting based on continuous attributes)

For values of the attribute age of a person:
0, 4, 12, 16, 16, 18, 24, 26, 28

Answer 22

Specify a din density e.g. 3:

Bin 1: [-,14]
Bin 2: [14,21]
Bin 3: [21,+]

Question 23

How to find the best attribute split for decision trees?

Answer 23

Greedy approach: Test all splits and choose the one with the most homogenous (pure) nodes (the one with the lowest impurity measure after splitting)

Requires: measure of node impurity

Common Measure:

• GINI Index
• Entropy

Question 24

Which bucket has the higher degree of impurity?

C0: 5 C0:9
C1: 5 C1: 1

Answer 24

The left one

Question 25

How is the purity gain defined?

Answer 25

Gain = P - M ``` P = impurity measure before splitting M = impurity measure after splitting ```

Question 26

How is the GINI Index calculated?

Answer 26

1 - the sum of the squared relative frequency of a class j at node t

Question 27

How to interpret the GINI Index

Answer 27

Minimum: 0.0 (all records belong to one class) Maximum: 1-(1/nc) (if records are equally distributed among all class) nc = number of classes For two classes: 1-1/2 = 1/2 Gini increases if the buckets are less pure

Question 28

What is the difference between the GINI index and the GINI split

Answer 28

GINI Index: Measure for node impurity GINI Split: Measures the quality of the overall split (GINI Index of each partition is weighted according to its size)

Question 29

How to compute the GINI Index for categorical attributes

Answer 29

For each distinct attribute value count for each class

Question 30

How to find the best binary split for continuous attributes by using the GINI index

Answer 30

1. Sort the attribute on values 2. linearly scan the values and update count matrix and compute GINI index 3. choose the split position with smallest GINI index

Question 31

What is Entropy?

Answer 31

An alternative impurity measure. Entropy measure the homogeneity of a node. ``` Minimum: 0.0 when all records belong to one class Maximum: log2 nc when records are equally distributed among all classes ```

Question 32

How to split nodes based on information gain (with entropy)?

Answer 32

- Information gain measure the entropy reduction of a split | - Choose the split with the largest reduction (maximal GAIN -> partition with the smallest entropy)

Question 33

What is the disadvantage of splitting based on information gain (entropy)

Answer 33

Tends to prefer splits that result in large number of partitions; each partition is small but pure like by ID attribute

Question 34

What is GainRATIO

Answer 34

- Designed to overcome the tendency of Information Gain to generate a large number of small partitions - GainRatio adjusts information gain by entropy of partitioning (SplitINFO) Penalizes large number of small partitions (higher entropy of the partitioning)

Question 35

What is the difference between GINI Index and Entropy

Answer 35

Gini Index measure impurity | Entropy measures information gain

Question 36

What does overfitting mean

Answer 36

A model trains patterns that are specific to the training data set thus the model performs poor on unseen (test) data Goal: Find a compromise between a specific and a general model

Question 37

What are symptoms and causes of an overfitted tree?

Answer 37

Symptoms: - Decision tree is too deep - Too many branches - Model works well on training set but performs bad on test set Causes: 1. Too little training data 2. Noise / outliers in training data 3. High model complexity An overfitted model does not generalize well to unseen data.

Question 38

Describe the characteristics of underfitting and overfitting.

Answer 38

Underfitting: Model is too simple; both training an test errors are large Overfitting: Model is too complex; training error is small but test error is large

Question 39

How can you prevent Overfitting?

Answer 39

- Use more training data - Pre-Pruning - Post-Pruning - Ensembles

Question 40

How can you prevent overfitting with more training data?

Answer 40

- If training data is under-representative, testing errors increase on increasing number of nodes - With more training data you can reduce the difference between training and testing errors at a given number of nodes Expensive prevention method

Question 41

How can you prevent overfitting with pre-pruning?

Answer 41

Stop the algorithm before tree becomes fully grown because shallower trees potentially generalize better (Occams razor) Early stopping conditions = Pre-pruning: - Number of instances in leaf node below threshold - Impurity improvement below a threshold

Question 42

How can you prevent overfitting with post-pruning?

Answer 42

1. Grow decision tree fully 2. Trim nodes of the decision tree bottom up 3. Estimate generalization error before and after trimming (with Test data) 4. If generalization error improves after trimming - replace subtree (by leaf node or most frequent used branch)

Question 43

How to prevent overfitting with ensembles

Answer 43

- Learn different models - Each model votes on the final classification decision Idea: Wisdom of the crowds - A single classifier might focus too much on one aspect - Multiple classifiers can focus on different aspect

Question 44

What are random forests?

Answer 44

Ensemble consisting of a large number of different decision trees. They usually outperform single decision trees.

Question 45

How can you achieve independence of trees at a random forest

Answer 45

You need to use randomness in the learning process: - Randomly use different attributes of the training set for each tree - Randomly remove records from the training data (bagging)

Question 46

What are the advantages of decision trees?

Answer 46

Advantages: - Inexpensive to construct - Very fast at classifying unseen records - Easy to interpret for small trees - Can handle redundant or irrelevant attributes (good in feature selection) - Good accuracy for low dimensional data sets (not texts and images)

Question 47

What are the disadvantages of decision trees?

Answer 47

Disadvantages: - Space of possible decision trees is exponentially large (Greedy approaches are often unable to find the best tree) - Trees don't take into account interactions between attributes