K-Nearest Neighbors (KNN)

R Code for Data Generation and Analysis

# Generate synthetic data with different patterns
set.seed(123)
library(ggplot2)

# Cluster pattern
n <- 200
cluster1 <- data.frame(
  x1 = rnorm(n/2, mean=-1, sd=0.5),
  x2 = rnorm(n/2, mean=-1, sd=0.5),
  y = "Class1"
)
cluster2 <- data.frame(
  x1 = rnorm(n/2, mean=1, sd=0.5),
  x2 = rnorm(n/2, mean=1, sd=0.5),
  y = "Class2"
)
df_cluster <- rbind(cluster1, cluster2)

# Checkerboard pattern
x1 <- runif(n, -2, 2)
x2 <- runif(n, -2, 2)
df_checker <- data.frame(
  x1,
  x2,
  y = factor(ifelse((x1 > 0 & x2 > 0) | (x1 < 0 & x2 < 0), "Class1", "Class2"))
)

# Visualize datasets
ggplot(df_cluster, aes(x1, x2, color=y)) + geom_point() + ggtitle("Cluster Pattern")
ggplot(df_checker, aes(x1, x2, color=y)) + geom_point() + ggtitle("Checkerboard Pattern")

# Train-test split
set.seed(456)
train_idx <- sample(1:n, 0.7*n)
train_cluster <- df_cluster[train_idx, ]
test_cluster <- df_cluster[-train_idx, ]
train_checker <- df_checker[train_idx, ]
test_checker <- df_checker[-train_idx, ]

# Scale features
scale_fn <- function(train, test) {
  means <- apply(train[,1:2], 2, mean)
  sds <- apply(train[,1:2], 2, sd)
  train_scaled <- as.data.frame(scale(train[,1:2], center=means, scale=sds))
  test_scaled <- as.data.frame(scale(test[,1:2], center=means, scale=sds))
  train_scaled$y <- train$y
  test_scaled$y <- test$y
  list(train=train_scaled, test=test_scaled)
}

cluster_scaled <- scale_fn(train_cluster, test_cluster)
checker_scaled <- scale_fn(train_checker, test_checker)

# Fit KNN models with different k
library(class)
k_values <- c(1, 3, 5, 10, 20)
results <- data.frame()

for (k in k_values) {
  # Cluster pattern
  pred_cluster <- knn(
    train = cluster_scaled$train[,1:2],
    test = cluster_scaled$test[,1:2],
    cl = cluster_scaled$train$y,
    k = k
  )
  acc_cluster <- mean(pred_cluster == cluster_scaled$test$y)
  
  # Checkerboard pattern
  pred_checker <- knn(
    train = checker_scaled$train[,1:2],
    test = checker_scaled$test[,1:2],
    cl = checker_scaled$train$y,
    k = k
  )
  acc_checker <- mean(pred_checker == checker_scaled$test$y)
  
  results <- rbind(results, data.frame(
    k = k,
    accuracy_cluster = acc_cluster,
    accuracy_checker = acc_checker
  ))
}

# Plot accuracy vs k
ggplot(results, aes(k)) +
  geom_line(aes(y=accuracy_cluster, color="Cluster Pattern")) +
  geom_line(aes(y=accuracy_checker, color="Checkerboard Pattern")) +
  labs(title="KNN Performance by k Value", y="Accuracy", color="Pattern") +
  scale_x_continuous(breaks=k_values)

# Create decision boundary plots
library(gridExtra)

generate_boundary_plot <- function(df, k, title) {
  # Create grid
  rng <- apply(df[,1:2], 2, range)
  x1_seq <- seq(rng[1,1], rng[2,1], length=100)
  x2_seq <- seq(rng[1,2], rng[2,2], length=100)
  grid <- expand.grid(x1=x1_seq, x2=x2_seq)
  
  # Predict on grid
  grid$pred <- knn(
    train = df[,1:2],
    test = grid[,1:2],
    cl = df$y,
    k = k
  )
  
  # Plot
  ggplot(grid, aes(x1, x2, fill=pred)) +
    geom_tile(alpha=0.3) +
    geom_point(data=df, aes(color=y), size=2) +
    ggtitle(paste(title, "(k =", k, ")")) +
    theme_minimal()
}

p1 <- generate_boundary_plot(cluster_scaled$train, 3, "Cluster Pattern")
p2 <- generate_boundary_plot(checker_scaled$train, 10, "Checkerboard Pattern")
grid.arrange(p1, p2, ncol=2)

# Print results
cat("Accuracy by k value:\n")
print(results)