Data Mining - Lecture k-Nearest Neighbor

Question 1

What is the k-Nearest Neighbor in short?

Answer 1

A classification model.
You specify k records. For every new records, your model looks at the closest k records. The predominant class of those records will be the class for the new record.

The distance can be computed with the Euclidean Distance or the Manhattan distance.

Question 2

What are the three steps of the Nearest Neighbor model?

Answer 2

1. Determining the item’s neighbors
2. Choosing the number of neighbors (k)
3. Computing the classification (categorical) or prediction (numerical)

Question 3

How is the distance between records written down?

Answer 3

If you have two records, record i and record j, these will be abbreviated to ri and rj.

The distance between those records is dij.

Question 4

Student number

Answer 4

2064381

Question 5

What are the properties of the distance between records?

Answer 5

1. the distance needs to be positive. (dij > o)
2. distance between a single record is 0 ( dii = 0)
3. Symmetry in distance (dij = dji)
4. The distance of a pair has to be smaller than the sum of two pair distances

Question 6

What is the Euclidean distance and how do you compute it?

Answer 6

It is a measure to compute distances between variables.
If a record has multiple independent variables (Xn) you compute it by:

dij = Root( (Xi1 - Xj1)^2 + (Xi2 - Xj2)^2 ……)

= Je haalt xj1 van xi1 en doet dat antwoord in het kwadraat. Dat doe je voor alle variabelen. Deze tel je bij elkaar op en daar neem je de wortel van.

Question 7

What is the problem with the euclidean distance and how do you solve that issue?

Answer 7

1. It is highly scale dependent.
   - >You can normalize all measurements by subtracting the average from the x and divide it by the standard deviation.
2. It is sensitive to outliers
   - > Use Manhatten distance

Question 8

What is the Manhattan distance?

Answer 8

You look at the absolute values.

dij = |xi1 - xj1| + |xi2 - xj2| ……..

= Je haalt xj1 van xi1 af. Je haalt het teken voor het cijfer weg (absoluut), en je telt ze allemaal bij elkaar op.

Question 9

What happens if K is too low?

Answer 9

The model might take into account outliers, weird values (=noise of the model) and will not classify well.

Question 10

What happens if k it too high?

Answer 10

You miss out on the methods ability to capture the local structure in the dataset.

Question 11

What happens if k is the exact same as the number of records in the training set?

Answer 11

All records will be assigned to the majority class in the training data -> model will suck

Question 12

What is the normal range for k?

Answer 12

Between 1 and 20.

You try to use odd numbers to avoid ties.

Question 13

How do you choose k?

Answer 13

You can use the k-nearest neighbor algorithm. You use the testing data set to see the performance for different values of k.

The one with the best classification performance (and thus the lowest error rate) is the best k.

As you use the testing set for the improvement of your model, you should actually use a validation set instead. We did not learn how to do that though.

Question 14

What do you do if you use k-nearest neighbor on numerical outcomes instead of categorical outcomes?

(So the class is not green or red, but a value)

Answer 14

You do everything the same, except you do not use majority voting for the class based on the neigbors.

-> you calculate the average of those neigbors value and then you take the average.

Question 15

What are the shortcomings of this model?

Answer 15

1. Computing the nearest neighbors can be time consuming.
2. We only compute the distance at the time of prediction -> lazy learner.
3. If predictors increase, the number of records in training set needs to increase exponentially.