---
title: "Solution / Implement kNN"
author: "Martin Schedlbauer, PhD"
subtitle: A.3.204
output:
  html_document:
    df_print: paged
---

### Load Data

We will download the data directly from its URL rather than downloading the data.

```{r}
u <- "https://s3.us-east-2.amazonaws.com/artificium.us/datasets/Prostate_Cancer.csv"

df <- read.csv(u,
               header = T,
               stringsAsFactors = F)

## save copy of data frame in case it is needed
df.raw <- df
```

### Inspect Data

Inspect the data set:

```{r}
head(df, 3)
```

```{r}
str(df)
```

### Indentify Missing Values

In the code chunk below, we iterate through each of the columns. This code is generic and will work on detecting missing values in any dataframe.

```{r}
# get vector of column name
cols <- colnames(df)

## missing values in each column: iterate
for (c in cols) {
  missing.rows <- which(is.na(df[,c]))
  
  num.missing <- length(missing.rows)
  
  s <- "no"
  
  if (num.missing > 0)
    s <- num.missing
  
  print(paste0("Column '", c, "' has ", 
                 s, " missing values"))
    
}
```

There are no missing values, but if there were, Lesson [3.204 -- Managing Missing Values in Data](http://artificium.us/lessons/03.ml/l-3-204-missing-values/l-3-204.html) contains strategies for dealing with them.

### Feature Normalization

Normalize all numeric features (features 3 through *n*). To help us do this faster, we'll write a function that normalizes a vector of numeric values.

```{r}
## normalizes the numeric vector v using z-score standardization
zNormalize <- function (v) {
  m <- mean(v)
  s <- sd(v)
  
  z <- ((v - m) / s)
  
  return (z)
}
```

```{r}
## iterate over each numeric column (3:n)

cols <- ncol(df)

for (c in 3:cols) {
  # z-score standardize a column
  z.norm <-zNormalize(df[,c])
  
  # replace column with normalized values
  df[,c] <- z.norm
}
```

To see if the normalization worked as expected, we'll display the first four rows of the original and the transformed dataframe.

```{r}
head(df.raw, 4)
head(df, 4)
```

### Sample Training Data

Next, we'll split the data into two random samples: 80% for training and 20% for validation. We'll save the subsets in different dataframe: `df.train` and `df.val`. The sampling is based on row numbers and is without replacement, *i.e.*, the same row cannot be more than once in training or validation and cannot be in both. There are other splitting techniques that do allow for a row to be in a sample more than once, *e.g.*, k-fold cross validation and bagging.

```{r}
## randomly sample 80% of rows for training data
r <- nrow(df)
train.rows <- sample(1:r, floor(0.8*r), replace = F)

## copy sampled rows into a new dataframe
df.train <- df[train.rows,]

## choose all other rows for validation
df.val <- df[-train.rows,]
```

### Implement kNN

Next, we will implement our own version of *kNN* to predict the categorical variable "diagnosis_result", using Euclidean distance for the distance measure.

The function `xkNN()` takes four arguments:

-   `labels`: a vector for the target labels in the training data
-   `features`: a dataframe for the features of the training data
-   `k`: a value for *k* (the number of nearest neighbors to consider)
-   `unknown`: a vector of variables for which to make a prediction

The function returns the predicted value of the categorical target variable.

We will need a few support functions:

-   find the mode of a vector of categorical values
-   calculate the Euclidean distance between two vectors of arbitrary length.
-   calculate distance to all neighbors
-   find closest *k* neighbors

```{r}
## mode function
kNNMODE <- function(x) 
{
  ux <- unique(x)
  return (ux[which.max(tabulate(match(x, ux)))])
}

## Euclidean distance function
kNNDIST <- function(p, q)
{
  d <- 0
  for (i in 1:length(p)) {
    d <- d + (p[i] - q[i])^2
  }
  
  return(sqrt(d))
}

## find closest k neighbors
k.closest <- function(neighbors,k)
{
  # uses the order function from R to sort the vector 
  # of neighbors by distance
  ordered.neighbors <- order(neighbors)
  
  # extracts only the top k neighbors
  # returns the indexes of those closest neighbors
  k.closest <- ordered.neighbors[1:k]
}

## find distances to all neighbors
kNNNeighbors <- function (train, u)
{
   m <- nrow(train)
   ds <- numeric(m)
   for (i in 1:m) {
     p <- train[i,]
     ds[i] <- unlist(kNNDIST(p,u))
   }
   
   return(ds)
}

## kNN algorithm
xkNN <- function (labels, 
                  features,
                  k,
                  unknown) {
  nb <- kNNNeighbors(features, unknown)
  f <- k.closest(nb,k)
  predicted.label <- kNNMODE(labels[f])
  
  return (predicted.label)
}
```

### Evaluate kNN

We will use our function to calculate the accuracy (percentage of correct classifications) by predicting the validation data target using our version of *kNN*. For now, we will arbitrarily set *k = 3*.

```{r}
nrows.val <- nrow(df.val)
ncols <- ncol(df.val)

# vector of predictions for accuracy calculation
v <- c("M")

## get features for training data
training.features <- df.train[,3:ncols]

## get the labels for the training data
training.lables <- df.train[,2]

## iterate over each row in validation data
for (r in 1:nrows.val) {
  ## get just the features of one row in validation data (columns 3 and beyond)
  unknown <- df.val[r,3:ncols]
 
  ## predict using our algorithm using k = 3
  k = 3
  label.predicted <- xkNN(training.lables, training.features, k, unknown)
  
  ## add prediction to vector for later use in evaluation
  v[r] <- label.predicted
}
```

Now that we have the predicted values for the validation data, we can evaluated the accuracy of the algorithm (percent of corrected predicted labels).

```{r}
## get the label from the validation data
labels.actual <- df.val[,2]

accuracy <- (length(which(v == labels.actual))) / nrows.val

print(paste0(
  "The accuracy for k = ", k, " is ",
  round(accuracy * 100,0), "%."
))
```

Rather than only calculating accuracy, we can also calculate the number of true positive (TP) and true negatives (TN) and several associated metrics.

In evaluating classification algorithms in machine learning, a true positive means that the model correctly predicts the positive class or label when it is actually positive in the validation data and a true negative means that it correctly predicts a negative.

To evaluate machine learning algorithms, we use various metrics based on the concept of true positives. Here are a few commonly used evaluation metrics that utilize true positives:

1.  **Accuracy**: Accuracy measures the overall correctness of the model's predictions. It is calculated as the ratio of the number of correct predictions (true positives and true negatives) to the total number of predictions.

    Accuracy = (True Positives + True Negatives) / (True Positives + True Negatives + False Positives + False Negatives)

2.  **Precision**: Precision assesses the model's ability to correctly identify positive predictions among all the positive predictions it made. It is computed as the ratio of true positives to the sum of true positives and false positives.

    Precision = True Positives / (True Positives + False Positives)

    Precision is useful when we want to minimize false positives, such as in spam email detection.

3.  **Recall or Sensitivity**: Recall measures the model's ability to correctly identify positive instances from all the actual positive instances. It is calculated as the ratio of true positives to the sum of true positives and false negatives.

    Recall = True Positives / (True Positives + False Negatives)

    Recall is valuable when we want to minimize false negatives, such as in cancer diagnosis.

4.  **F1 Score**: The F1 score combines precision and recall into a single metric. It is the harmonic mean of precision and recall, giving equal weight to both measures.

    F1 Score = 2 \* (Precision \* Recall) / (Precision + Recall)

    The F1 score provides a balanced evaluation when you want to consider both precision and recall simultaneously.

These metrics leverage true positives to measure the performance of classification algorithms. By examining the number of true positives and comparing them with false positives and false negatives, we can gain insights into how well the model is performing in identifying positive instances accurately.

For this data set, a positive is the presence of disease, *i.e.*, a malignant tumor indicated with the label "M". So, a true positive (TP) is when the algorithm predicts positive when the actual data is also positive ("M").

```{r}
TP <- (v == "M" & labels.actual == "M")
FP <- (v == "M" & labels.actual == "B")
TN <- (v == "B" & labels.actual == "B")
FN <- (v == "B" & labels.actual == "M")

NTP <- length(which(TP == TRUE))
NFP <- length(which(TP == FALSE))

precision <- NTP / (NTP + NFP)
```

### Find Optimal k

Next, we will try different values of *k* (from 3 to $\sqrt(d)$) where *d* are the number of dimensions in your data, *i.e.*, the number of predictor features). For each value of *k*, we'll calculate *accuracy*, although, depending on the domain, we might also choose to evaluate based on *precision*, *recall*, or *F1* score.

In the code below, we'll go one above the $\sqrt(d)$ as the number of dimensions is small and we'd only go to *k = 4*.

```{r}
nrows.val <- nrow(df.val)
ncols <- ncol(df.val)
dimensions <- (ceiling(sqrt(ncols)) + 1)

# vector of predictions for accuracy calculation
v <- data.frame(
  k = 1,
  predicted.label = c("M")
)

## get features for training data
training.features <- df.train[,3:ncols]

## get the labels for the training data
training.lables <- df.train[,2]

## iterate over each row in validation data
for (r in 1:nrows.val) {
  ## get just the features of one row in validation data (columns 3 and beyond)
  unknown <- df.val[r,3:ncols]
 
  ## predict using our algorithm using various values for k
  for (k in 3:dimensions) {
    label.predicted <- xkNN(training.lables, training.features, k, unknown)
  
    ## add prediction to vector for later use in evaluation
    v[k,r] <- label.predicted
  }
}
```

Now we can calculate the accuracy for each value of *k*.

```{r}
## get the label from the validation data
labels.actual <- df.val[,2]

## calculate accuracy for each k
for (k in 3:dimensions) {
  accuracy <- (length(which(v[k,] == labels.actual))) / nrows.val
  
  print(paste0(
    "The accuracy for k = ", k, " is ",
    round(accuracy * 100,0), "%."
  ))
}
```

### Effect of Outliers

*kNN* can be sensitive to outliers, although a z-score standardization attentuates their impact. However, removing extreme outliers (more than 3 standard deviations from mean, *i.e.*, absolute value of z-score \> 3) is advisable and should be done after z-score standardization (when we have the z-scores).
