# =====================================================================
# ANALISIS SPATIAL CLUSTERING DENGAN METODE SKATER
# Revisi: penambahan eksperimen Euclidean vs Heaviside,
# perbandingan MST Prim vs Kruskal, dan pencarian jumlah cluster terbaik.
# Dataset: Columbus (package spData)
# =====================================================================

# ---------------------------------------------------------------------
# 1. MEMUAT PACKAGE DAN DATA
# ---------------------------------------------------------------------
library(sf)
## Linking to GEOS 3.14.1, GDAL 3.12.1, PROJ 9.7.1; sf_use_s2() is TRUE
library(spData)
## To access larger datasets in this package, install the spDataLarge
## package with: `install.packages('spDataLarge',
## repos='https://nowosad.github.io/drat/', type='source')`
library(spdep)
library(igraph)
## 
## Attaching package: 'igraph'
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union
library(ggplot2)
library(dplyr)
## 
## Attaching package: 'dplyr'
## The following objects are masked from 'package:igraph':
## 
##     as_data_frame, groups, union
## The following objects are masked from 'package:stats':
## 
##     filter, lag
## The following objects are masked from 'package:base':
## 
##     intersect, setdiff, setequal, union
library(cluster)

# Membaca data geometri Columbus
columbus_sf <- sf::st_read(
  system.file("shapes/columbus.gpkg", package = "spData"),
  quiet = TRUE
)

# Variabel yang digunakan dalam analisis
variabel <- c("CRIME", "INC", "HOVAL")

data_asli <- columbus_sf |>
  sf::st_drop_geometry() |>
  dplyr::select(dplyr::all_of(variabel))

# Jumlah wilayah dan ID node
n <- nrow(columbus_sf)
columbus_sf$node <- seq_len(n)

stopifnot(nrow(data_asli) == n)
stopifnot(all(complete.cases(data_asli)))

cat("Dimensi data:", dim(data_asli), "\n")
## Dimensi data: 49 3
print(head(data_asli))
##      CRIME    INC  HOVAL
## 1 15.72598 19.531 80.467
## 2 18.80175 21.232 44.567
## 3 30.62678 15.956 26.350
## 4 32.38776  4.477 33.200
## 5 50.73151 11.252 23.225
## 6 26.06666 16.029 28.750
# Peta awal
plot(
  sf::st_geometry(columbus_sf),
  col = "grey85",
  border = "white",
  lwd = 0.8,
  main = "Peta Wilayah Columbus",
  axes = FALSE
)
mtext(
  paste(n, "wilayah sebagai unit analisis spatial clustering"),
  side = 1, line = 1, cex = 0.8
)

# ---------------------------------------------------------------------
# 2. MEMBENTUK CONNECTIVITY GRAPH DENGAN QUEEN CONTIGUITY
# ---------------------------------------------------------------------
nb <- spdep::poly2nb(columbus_sf, queen = TRUE)

adj_matrix <- spdep::nb2mat(
  nb,
  style = "B",
  zero.policy = TRUE
)

edge_adj <- which(
  upper.tri(adj_matrix) & adj_matrix == 1,
  arr.ind = TRUE
)

# Pastikan graf ketetanggaan terhubung
if (any(lengths(nb) == 0)) {
  stop("Ada wilayah yang tidak memiliki tetangga. Periksa geometri dan Queen Contiguity.")
}

g_connect <- igraph::graph_from_data_frame(
  data.frame(
    from = as.character(edge_adj[, 1]),
    to = as.character(edge_adj[, 2])
  ),
  directed = FALSE,
  vertices = data.frame(name = as.character(seq_len(n)))
)

jumlah_node <- igraph::vcount(g_connect)
jumlah_edge <- igraph::ecount(g_connect)
jumlah_komponen <- igraph::components(g_connect)$no

cat("Jumlah node connectivity graph:", jumlah_node, "\n")
## Jumlah node connectivity graph: 49
cat("Jumlah edge connectivity graph:", jumlah_edge, "\n")
## Jumlah edge connectivity graph: 118
cat("Jumlah komponen connectivity graph:", jumlah_komponen, "\n")
## Jumlah komponen connectivity graph: 1
stopifnot(jumlah_node == n)
stopifnot(jumlah_komponen == 1)

# ---------------------------------------------------------------------
# 3. MENYIAPKAN KOORDINAT NODE DAN FUNGSI VISUALISASI EDGE
# ---------------------------------------------------------------------
titik <- sf::st_point_on_surface(columbus_sf)
## Warning: st_point_on_surface assumes attributes are constant over geometries
koordinat <- sf::st_coordinates(titik)

data_node <- data.frame(
  node = seq_len(n),
  x = koordinat[, 1],
  y = koordinat[, 2]
)

buat_edge_plot <- function(edges) {
  edges <- as.matrix(edges[, 1:2, drop = FALSE])

  hasil <- data.frame(
    from = as.integer(edges[, 1]),
    to = as.integer(edges[, 2])
  )

  hasil |>
    dplyr::mutate(
      x = koordinat[from, 1],
      y = koordinat[from, 2],
      xend = koordinat[to, 1],
      yend = koordinat[to, 2]
    )
}

edge_graph <- buat_edge_plot(edge_adj)

plot(
  sf::st_geometry(columbus_sf),
  col = "grey95", border = "grey75", lwd = 0.5,
  main = "Connectivity Graph Columbus", axes = FALSE
)
segments(
  x0 = edge_graph$x, y0 = edge_graph$y,
  x1 = edge_graph$xend, y1 = edge_graph$yend,
  col = "steelblue", lwd = 1
)
points(data_node$x, data_node$y, col = "darkblue", pch = 19, cex = 0.8)
legend(
  "bottomleft",
  legend = c("Node (Wilayah)", "Edge (Hubungan Ketetanggaan)"),
  col = c("darkblue", "steelblue"),
  pch = c(19, NA), lty = c(NA, 1), bty = "n", cex = 0.8
)
mtext(
  paste(jumlah_node, "node dan", jumlah_edge, "edge (Queen Contiguity)"),
  side = 1, line = 1, cex = 0.8
)

# ---------------------------------------------------------------------
# 4. STANDARDISASI DATA
# ---------------------------------------------------------------------
data_std <- as.data.frame(scale(data_asli))
stopifnot(all(complete.cases(data_std)))

cat("Ringkasan data terstandardisasi:\n")
## Ringkasan data terstandardisasi:
print(summary(data_std))
##      CRIME               INC              HOVAL        
##  Min.   :-2.08883   Min.   :-1.7355   Min.   :-1.1121  
##  1st Qu.:-0.90128   1st Qu.:-0.7736   1st Qu.:-0.6897  
##  Median :-0.06741   Median :-0.1744   Median :-0.2673  
##  Mean   : 0.00000   Mean   : 0.0000   Mean   : 0.0000  
##  3rd Qu.: 0.80424   3rd Qu.: 0.6924   3rd Qu.: 0.2634  
##  Max.   : 2.01787   Max.   : 2.9272   Max.   : 3.1389
# ---------------------------------------------------------------------
# 5. DEFINISI FUNGSI JARAK EUCLIDEAN DAN HEAVISIDE
# ---------------------------------------------------------------------
# Euclidean:
# d(x,y) = sqrt(sum((x_j-y_j)^2))

# Heaviside:
# H(u) = 1 jika u >= 0, dan 0 jika u < 0.
# Jarak Heaviside operasional di bawah ini menghitung banyaknya atribut
# yang memiliki selisih absolut >= ambang_heaviside.
#
# PENTING: ambang 1.0 adalah nilai awal pada data yang sudah distandardisasi.
# Pastikan nilai ambang ini sesuai dengan definisi/referensi yang disepakati
# kelompok. Uji sensitivitas ambang dapat dilakukan jika diperlukan.
ambang_heaviside <- 1.0

fungsi_heaviside <- function(u) {
  as.numeric(u >= 0)
}

jarak_heaviside_dua_node <- function(x, y, ambang = ambang_heaviside) {
  sum(fungsi_heaviside(abs(x - y) - ambang))
}

# Fungsi untuk nbcosts(): menerima data, ID node, dan ID tetangga.
# Menghasilkan satu bobot untuk setiap tetangga dari node yang sedang diproses.
metode_biaya_heaviside <- function(data, id, id.neigh) {
  data <- as.matrix(data)
  vapply(
    id.neigh,
    function(j) jarak_heaviside_dua_node(data[id, ], data[j, ]),
    numeric(1)
  )
}

# Fungsi untuk skater()/ssw(): menghitung jumlah penyimpangan atribut
# dari centroid cluster yang melewati ambang Heaviside.
metode_ssw_heaviside <- function(data, id) {
  data <- as.matrix(data)
  pusat <- colMeans(data[id, , drop = FALSE])
  selisih <- abs(sweep(data[id, , drop = FALSE], 2, pusat, "-"))
  sum(fungsi_heaviside(selisih - ambang_heaviside))
}

# Matriks jarak Heaviside untuk evaluasi silhouette.
buat_matriks_jarak_heaviside <- function(data, ambang = ambang_heaviside) {
  data <- as.matrix(data)
  n_data <- nrow(data)
  hasil <- matrix(0, nrow = n_data, ncol = n_data)

  if (n_data >= 2) {
    for (i in seq_len(n_data - 1)) {
      for (j in (i + 1):n_data) {
        nilai <- jarak_heaviside_dua_node(data[i, ], data[j, ], ambang)
        hasil[i, j] <- nilai
        hasil[j, i] <- nilai
      }
    }
  }

  as.dist(hasil)
}

# Jarak untuk evaluasi silhouette masing-masing metode
jarak_euclidean <- stats::dist(data_std, method = "euclidean")
jarak_heaviside <- buat_matriks_jarak_heaviside(data_std)

# ---------------------------------------------------------------------
# 6. FUNGSI PEMBENTUKAN MST PRIM DAN KRUSKAL
# ---------------------------------------------------------------------
# Prim menggunakan spdep::mstree(). Dokumentasi spdep menyatakan bahwa
# mstree() mengimplementasikan algoritma Prim.

# Fungsi bobot untuk pasangan edge tertentu.
hitung_bobot_edge <- function(edges, data, metode = c("euclidean", "heaviside")) {
  metode <- match.arg(metode)
  edges <- as.matrix(edges[, 1:2, drop = FALSE])

  if (metode == "euclidean") {
    return(vapply(seq_len(nrow(edges)), function(i) {
      x <- as.numeric(data[edges[i, 1], ])
      y <- as.numeric(data[edges[i, 2], ])
      sqrt(sum((x - y)^2))
    }, numeric(1)))
  }

  vapply(seq_len(nrow(edges)), function(i) {
    x <- as.numeric(data[edges[i, 1], ])
    y <- as.numeric(data[edges[i, 2], ])
    jarak_heaviside_dua_node(x, y)
  }, numeric(1))
}

# Identitas edge tidak bergantung pada urutan node.
edge_key <- function(x) {
  x <- as.matrix(x[, 1:2, drop = FALSE])
  apply(x, 1, function(z) paste(sort(as.integer(z)), collapse = "-"))
}

# Algoritma Kruskal manual dengan struktur Union-Find.
kruskal_mst <- function(edges, weights, n_nodes) {
  edges <- as.matrix(edges[, 1:2, drop = FALSE])
  stopifnot(nrow(edges) == length(weights))

  parent <- seq_len(n_nodes)

  find_root <- function(x) {
    while (parent[x] != x) {
      x <- parent[x]
    }
    x
  }

  urutan <- order(weights)
  terpilih <- integer(0)

  for (i in urutan) {
    a <- find_root(edges[i, 1])
    b <- find_root(edges[i, 2])

    if (a != b) {
      parent[a] <- b
      terpilih <- c(terpilih, i)
    }

    if (length(terpilih) == n_nodes - 1) break
  }

  if (length(terpilih) != n_nodes - 1) {
    stop("Kruskal tidak menghasilkan n-1 edge. Periksa konektivitas graf.")
  }

  edges[terpilih, , drop = FALSE]
}

# ---------------------------------------------------------------------
# 7. EKSPERIMEN EUCLIDEAN VS HEAVISIDE DAN PRIM VS KRUSKAL
# ---------------------------------------------------------------------
# 7a. Bobot edge Euclidean
biaya_euclidean <- spdep::nbcosts(
  nb,
  as.matrix(data_std),
  method = "euclidean"
)

nb_w_euclidean <- spdep::nb2listw(
  nb,
  glist = biaya_euclidean,
  style = "B",
  zero.policy = TRUE
)

# 7b. Bobot edge Heaviside
biaya_heaviside <- spdep::nbcosts(
  nb,
  as.matrix(data_std),
  method = metode_biaya_heaviside
)

nb_w_heaviside <- spdep::nb2listw(
  nb,
  glist = biaya_heaviside,
  style = "B",
  zero.policy = TRUE
)

# MST Prim untuk masing-masing pendekatan bobot
mst_euclidean <- spdep::mstree(nb_w_euclidean, ini = 1)
mst_heaviside <- spdep::mstree(nb_w_heaviside, ini = 1)

edge_mst_euclidean <- mst_euclidean[, 1:2, drop = FALSE]
edge_mst_heaviside <- mst_heaviside[, 1:2, drop = FALSE]

# Validasi MST: n node, n-1 edge, dan terhubung.
validasi_mst <- function(edges, n_nodes) {
  g <- igraph::graph_from_data_frame(
    data.frame(from = as.character(edges[, 1]), to = as.character(edges[, 2])),
    directed = FALSE,
    vertices = data.frame(name = as.character(seq_len(n_nodes)))
  )
  stopifnot(igraph::vcount(g) == n_nodes)
  stopifnot(igraph::ecount(g) == n_nodes - 1)
  stopifnot(igraph::components(g)$no == 1)
  g
}

g_mst_euclidean <- validasi_mst(edge_mst_euclidean, n)
g_mst_heaviside <- validasi_mst(edge_mst_heaviside, n)

# Bobot seluruh edge connectivity graph untuk Kruskal
bobot_euclidean_semua <- hitung_bobot_edge(edge_adj, data_std, "euclidean")
bobot_heaviside_semua <- hitung_bobot_edge(edge_adj, data_std, "heaviside")

# MST Kruskal untuk masing-masing pendekatan bobot
edge_kruskal_euclidean <- kruskal_mst(
  edge_adj, bobot_euclidean_semua, n
)
edge_kruskal_heaviside <- kruskal_mst(
  edge_adj, bobot_heaviside_semua, n
)

# Perbandingan Prim dan Kruskal
hasil_perbandingan_mst <- data.frame(
  Metode_Bobot = c("Euclidean", "Heaviside"),
  Total_Bobot_Prim = c(
    sum(mst_euclidean[, 3]),
    sum(mst_heaviside[, 3])
  ),
  Total_Bobot_Kruskal = c(
    sum(hitung_bobot_edge(edge_kruskal_euclidean, data_std, "euclidean")),
    sum(hitung_bobot_edge(edge_kruskal_heaviside, data_std, "heaviside"))
  ),
  Edge_Prim_dan_Kruskal_Sama = c(
    setequal(edge_key(edge_mst_euclidean), edge_key(edge_kruskal_euclidean)),
    setequal(edge_key(edge_mst_heaviside), edge_key(edge_kruskal_heaviside))
  )
)

print(hasil_perbandingan_mst)
##   Metode_Bobot Total_Bobot_Prim Total_Bobot_Kruskal Edge_Prim_dan_Kruskal_Sama
## 1    Euclidean         50.23857            50.23857                       TRUE
## 2    Heaviside         17.00000            17.00000                      FALSE
# ---------------------------------------------------------------------
# 8. VISUALISASI MST EUCLIDEAN (PRIM)
# ---------------------------------------------------------------------
edge_mst_plot <- buat_edge_plot(edge_mst_euclidean)

g_mst <- g_mst_euclidean
mst <- mst_euclidean
edge_mst <- edge_mst_euclidean

plot(
  sf::st_geometry(columbus_sf),
  col = "grey95", border = "grey75", lwd = 0.5,
  main = "Minimum Spanning Tree Columbus (Euclidean - Prim)",
  axes = FALSE
)
segments(
  x0 = edge_mst_plot$x, y0 = edge_mst_plot$y,
  x1 = edge_mst_plot$xend, y1 = edge_mst_plot$yend,
  col = "darkblue", lwd = 1.5
)
points(data_node$x, data_node$y, col = "darkblue", pch = 19, cex = 0.8)
legend(
  "bottomleft", legend = c("Node (Wilayah)", "Edge (MST)"),
  col = c("darkblue", "darkblue"), pch = c(19, NA),
  lty = c(NA, 1), bty = "n", cex = 0.8
)
mtext(
  paste("MST dengan", igraph::ecount(g_mst), "edge"),
  side = 1, line = 1, cex = 0.8
)

# ---------------------------------------------------------------------
# 9. EKSPERIMEN JUMLAH CLUSTER k = 2 SAMPAI 6
# ---------------------------------------------------------------------
nilai_k <- 2:6

# Fungsi evaluasi k untuk satu kombinasi MST dan metode SKATER.
evaluasi_k <- function(edges_mst, data, metode_skater, jarak_evaluasi,
                       nama_metode, kandidat_k = 2:6) {
  hasil <- lapply(kandidat_k, function(kk) {
    model <- spdep::skater(
      edges = edges_mst[, 1:2, drop = FALSE],
      data = data,
      ncuts = kk - 1,
      method = metode_skater
    )

    jumlah_cluster <- length(unique(model$groups))
    if (jumlah_cluster < 2) {
      nilai_sil <- NA_real_
    } else {
      sil <- cluster::silhouette(as.integer(model$groups), jarak_evaluasi)
      nilai_sil <- mean(sil[, "sil_width"])
    }

    data.frame(
      Metode = nama_metode,
      k_diminta = kk,
      k_terbentuk = jumlah_cluster,
      SSW = tail(model$ssw, 1),
      Silhouette = nilai_sil,
      Ukuran_Cluster = paste(
        sort(as.vector(table(model$groups)), decreasing = TRUE),
        collapse = ", "
      )
    )
  })

  do.call(rbind, hasil)
}

# Eksperimen Euclidean
hasil_k_euclidean <- evaluasi_k(
  edges_mst = edge_mst_euclidean,
  data = data_std,
  metode_skater = "euclidean",
  jarak_evaluasi = jarak_euclidean,
  nama_metode = "Euclidean",
  kandidat_k = nilai_k
)

# Eksperimen Heaviside
hasil_k_heaviside <- evaluasi_k(
  edges_mst = edge_mst_heaviside,
  data = data_std,
  metode_skater = metode_ssw_heaviside,
  jarak_evaluasi = jarak_heaviside,
  nama_metode = "Heaviside",
  kandidat_k = nilai_k
)

tabel_perbandingan_k <- dplyr::bind_rows(
  hasil_k_euclidean,
  hasil_k_heaviside
)

cat("Hasil eksperimen jumlah cluster:\n")
## Hasil eksperimen jumlah cluster:
print(tabel_perbandingan_k)
##       Metode k_diminta k_terbentuk      SSW  Silhouette    Ukuran_Cluster
## 1  Euclidean         2           2 66.68724  0.25079935             43, 6
## 2  Euclidean         3           3 59.79749  0.13951867          37, 6, 6
## 3  Euclidean         4           4 55.77886  0.11816754       37, 6, 4, 2
## 4  Euclidean         5           5 51.78757  0.13176657    35, 6, 4, 2, 2
## 5  Euclidean         6           6 48.08042  0.15475188 34, 6, 4, 2, 2, 1
## 6  Heaviside         2           2 32.00000  0.21992016             41, 8
## 7  Heaviside         3           3 26.00000  0.11577642          35, 8, 6
## 8  Heaviside         4           4 21.00000  0.07471126       35, 6, 6, 2
## 9  Heaviside         5           5 18.00000  0.07586200    34, 6, 6, 2, 1
## 10 Heaviside         6           6 16.00000 -0.03881252 26, 8, 6, 6, 2, 1
# Menentukan k terbaik untuk masing-masing metode berdasarkan silhouette.
baris_terbaik_euclidean <- hasil_k_euclidean[
  which.max(hasil_k_euclidean$Silhouette), , drop = FALSE
]
baris_terbaik_heaviside <- hasil_k_heaviside[
  which.max(hasil_k_heaviside$Silhouette), , drop = FALSE
]

hasil_k_terbaik <- dplyr::bind_rows(
  baris_terbaik_euclidean,
  baris_terbaik_heaviside
)

cat("K terbaik untuk masing-masing metode:\n")
## K terbaik untuk masing-masing metode:
print(hasil_k_terbaik)
##      Metode k_diminta k_terbentuk      SSW Silhouette Ukuran_Cluster
## 1 Euclidean         2           2 66.68724  0.2507994          43, 6
## 2 Heaviside         2           2 32.00000  0.2199202          41, 8
# ---------------------------------------------------------------------
# 10. MENENTUKAN METODE DAN k UNTUK HASIL UTAMA
# ---------------------------------------------------------------------
# Pemilihan otomatis di bawah menggunakan nilai silhouette tertinggi
# dari dua pendekatan. Nilai silhouette dihitung berdasarkan jarak
# masing-masing metode. Karena metriknya berbeda, keputusan akhir tetap
# perlu mempertimbangkan interpretasi dan kesesuaian substantif.

if (is.na(baris_terbaik_euclidean$Silhouette) ||
    is.na(baris_terbaik_heaviside$Silhouette)) {
  stop("Ada nilai silhouette yang tidak dapat dihitung. Periksa hasil clustering.")
}

if (baris_terbaik_heaviside$Silhouette > baris_terbaik_euclidean$Silhouette) {
  metode_utama <- "Heaviside"
  k <- baris_terbaik_heaviside$k_diminta
  edge_mst_utama <- edge_mst_heaviside
  metode_skater_utama <- metode_ssw_heaviside
  jarak_utama <- jarak_heaviside
  mst_utama <- mst_heaviside
} else {
  metode_utama <- "Euclidean"
  k <- baris_terbaik_euclidean$k_diminta
  edge_mst_utama <- edge_mst_euclidean
  metode_skater_utama <- "euclidean"
  jarak_utama <- jarak_euclidean
  mst_utama <- mst_euclidean
}

cat("Metode utama berdasarkan silhouette tertinggi:", metode_utama, "\n")
## Metode utama berdasarkan silhouette tertinggi: Euclidean
cat("Jumlah cluster utama (k):", k, "\n")
## Jumlah cluster utama (k): 2
# ---------------------------------------------------------------------
# 11. MENJALANKAN SKATER DENGAN METODE DAN k TERPILIH
# ---------------------------------------------------------------------
hasil_skater <- spdep::skater(
  edges = edge_mst_utama[, 1:2, drop = FALSE],
  data = data_std,
  ncuts = k - 1,
  method = metode_skater_utama
)

columbus_sf$cluster <- factor(hasil_skater$groups)
ukuran_region <- table(hasil_skater$groups)

stopifnot(length(hasil_skater$groups) == n)
stopifnot(length(unique(hasil_skater$groups)) == k)
stopifnot(sum(ukuran_region) == n)

print(ukuran_region)
## 
##  1  2 
## 43  6
# ---------------------------------------------------------------------
# 12. MENGIDENTIFIKASI EDGE YANG DIPOTONG OLEH SKATER
# ---------------------------------------------------------------------
edge_tersisa_list <- lapply(
  hasil_skater$edges.groups,
  function(x) {
    if (is.null(x$edge) || nrow(x$edge) == 0) return(NULL)
    x$edge[, 1:2, drop = FALSE]
  }
)

edge_tersisa_list <- Filter(Negate(is.null), edge_tersisa_list)
edge_tersisa <- do.call(rbind, edge_tersisa_list)

edge_mst_key <- edge_key(edge_mst_utama)
edge_tersisa_key <- edge_key(edge_tersisa)

edge_potong <- setdiff(edge_mst_key, edge_tersisa_key)
edge_mst_utama_plot <- buat_edge_plot(edge_mst_utama)

edge_skater_plot <- edge_mst_utama_plot |>
  dplyr::mutate(
    status = ifelse(edge_mst_key %in% edge_potong,
                    "Dipotong", "Dipertahankan")
  )

print(table(edge_skater_plot$status))
## 
## Dipertahankan      Dipotong 
##            47             1
stopifnot(length(edge_potong) == k - 1)

# ---------------------------------------------------------------------
# 13. VISUALISASI HASIL CLUSTERING
# ---------------------------------------------------------------------
warna_region <- grDevices::rainbow(k)

plot(
  sf::st_geometry(columbus_sf),
  col = warna_region[as.integer(columbus_sf$cluster)],
  border = "white", lwd = 0.8,
  main = paste("Hasil Spatial Clustering SKATER -", metode_utama),
  axes = FALSE
)
legend(
  "bottomleft", legend = levels(columbus_sf$cluster),
  fill = warna_region, title = "Region", bty = "n", cex = 0.9
)
mtext(paste("Columbus dengan", k, "region"), side = 1, line = 1, cex = 0.8)

# Graf hasil SKATER: edge dipertahankan dan dipotong.
data_node$cluster <- factor(hasil_skater$groups)
warna_cluster <- grDevices::rainbow(k)

plot(
  sf::st_geometry(columbus_sf),
  col = "grey97", border = "grey80", lwd = 0.5,
  main = "Graf Hasil SKATER", axes = FALSE
)

edge_dipertahankan <- edge_skater_plot |>
  dplyr::filter(status == "Dipertahankan")
edge_dipotong <- edge_skater_plot |>
  dplyr::filter(status == "Dipotong")

segments(
  x0 = edge_dipertahankan$x, y0 = edge_dipertahankan$y,
  x1 = edge_dipertahankan$xend, y1 = edge_dipertahankan$yend,
  col = "grey40", lwd = 1
)
segments(
  x0 = edge_dipotong$x, y0 = edge_dipotong$y,
  x1 = edge_dipotong$xend, y1 = edge_dipotong$yend,
  col = "red", lwd = 2, lty = 2
)
points(
  data_node$x, data_node$y,
  col = warna_cluster[as.integer(data_node$cluster)],
  pch = 19, cex = 1
)
legend(
  "bottomleft",
  legend = c("Edge dipertahankan", "Edge dipotong"),
  col = c("grey40", "red"), lty = c(1, 2), lwd = c(1, 2),
  bty = "n", cex = 0.8
)
legend(
  "topright", legend = levels(data_node$cluster),
  col = warna_cluster, pch = 19, title = "Region", bty = "n", cex = 0.8
)
mtext(
  "Edge merah putus-putus menunjukkan batas antarregion",
  side = 1, line = 1, cex = 0.8
)

# ---------------------------------------------------------------------
# 14. NILAI SSW / Q PADA PROSES PEMBENTUKAN CLUSTER
# ---------------------------------------------------------------------
if (is.null(hasil_skater$ssw)) {
  stop("Komponen hasil_skater$ssw tidak tersedia. Periksa versi package spdep.")
}

nilai_Q <- as.numeric(hasil_skater$ssw)
tabel_Q <- data.frame(
  Jumlah_Region = seq_along(nilai_Q),
  Q = nilai_Q
)
print(tabel_Q)
##   Jumlah_Region        Q
## 1             1 74.79781
## 2             2 66.68724
graf_Q <- ggplot(
  tabel_Q,
  aes(x = Jumlah_Region, y = Q)
) +
  geom_line(linewidth = 0.8) +
  geom_point(size = 3) +
  geom_text(aes(label = round(Q, 2)), vjust = -0.8) +
  scale_x_continuous(breaks = tabel_Q$Jumlah_Region) +
  labs(
    title = "Perubahan Nilai SSW pada Proses Pruning",
    x = "Jumlah Region",
    y = "Total Within-Region Sum of Squares / Dissimilarity"
  ) +
  theme_minimal()
print(graf_Q)

# ---------------------------------------------------------------------
# 15. UKURAN DAN PROFIL SETIAP REGION
# ---------------------------------------------------------------------
tabel_ukuran <- as.data.frame(table(hasil_skater$groups))
colnames(tabel_ukuran) <- c("Region", "Jumlah_Area")
tabel_ukuran$Proporsi <- round(tabel_ukuran$Jumlah_Area / n * 100, 2)
print(tabel_ukuran)
##   Region Jumlah_Area Proporsi
## 1      1          43    87.76
## 2      2           6    12.24
graf_ukuran <- ggplot(
  tabel_ukuran,
  aes(x = Region, y = Jumlah_Area, fill = Region)
) +
  geom_col() +
  geom_text(aes(label = Jumlah_Area), vjust = -0.5) +
  labs(
    title = "Distribusi Jumlah Area Setiap Region",
    x = "Region", y = "Jumlah Area"
  ) +
  theme_minimal() +
  theme(legend.position = "none")
print(graf_ukuran)

data_hasil <- data_asli |>
  dplyr::mutate(Region = factor(hasil_skater$groups))

profil_region <- data_hasil |>
  dplyr::group_by(Region) |>
  dplyr::summarise(
    dplyr::across(dplyr::all_of(variabel), ~ mean(.x, na.rm = TRUE)),
    .groups = "drop"
  )
print(profil_region)
## # A tibble: 2 × 4
##   Region CRIME   INC HOVAL
##   <fct>  <dbl> <dbl> <dbl>
## 1 1       37.6  13.1  36.5
## 2 2       17.1  23.7  52.6
# ---------------------------------------------------------------------
# 16. EVALUASI SILHOUETTE HASIL UTAMA
# ---------------------------------------------------------------------
hasil_silhouette <- cluster::silhouette(
  as.integer(hasil_skater$groups),
  jarak_utama
)

rata_silhouette <- mean(hasil_silhouette[, "sil_width"])
cat("Rata-rata silhouette hasil utama:", rata_silhouette, "\n")
## Rata-rata silhouette hasil utama: 0.2507994
plot(
  hasil_silhouette,
  main = paste("Silhouette SKATER -", metode_utama, "(k =", k, ")")
)

# ---------------------------------------------------------------------
# 17. RINGKASAN HASIL ANALISIS
# ---------------------------------------------------------------------
ringkasan_analisis <- list(
  dimensi_data = dim(data_asli),
  jumlah_node = jumlah_node,
  jumlah_edge_connectivity = jumlah_edge,
  jumlah_komponen_connectivity = jumlah_komponen,
  jumlah_node_MST = igraph::vcount(validasi_mst(edge_mst_utama, n)),
  jumlah_edge_MST = nrow(edge_mst_utama),
  metode_jarak_terpilih = metode_utama,
  jumlah_cluster_terpilih = k,
  ukuran_region = ukuran_region,
  jumlah_edge_dipotong = length(edge_potong),
  nilai_SSW_Q = tabel_Q,
  silhouette_rata_rata = rata_silhouette,
  profil_region = profil_region
)

cat("\n================ RINGKASAN ANALISIS ================\n")
## 
## ================ RINGKASAN ANALISIS ================
print(ringkasan_analisis)
## $dimensi_data
## [1] 49  3
## 
## $jumlah_node
## [1] 49
## 
## $jumlah_edge_connectivity
## [1] 118
## 
## $jumlah_komponen_connectivity
## [1] 1
## 
## $jumlah_node_MST
## [1] 49
## 
## $jumlah_edge_MST
## [1] 48
## 
## $metode_jarak_terpilih
## [1] "Euclidean"
## 
## $jumlah_cluster_terpilih
## [1] 2
## 
## $ukuran_region
## 
##  1  2 
## 43  6 
## 
## $jumlah_edge_dipotong
## [1] 1
## 
## $nilai_SSW_Q
##   Jumlah_Region        Q
## 1             1 74.79781
## 2             2 66.68724
## 
## $silhouette_rata_rata
## [1] 0.2507994
## 
## $profil_region
## # A tibble: 2 × 4
##   Region CRIME   INC HOVAL
##   <fct>  <dbl> <dbl> <dbl>
## 1 1       37.6  13.1  36.5
## 2 2       17.1  23.7  52.6
cat("\n================ PERBANDINGAN MST ================\n")
## 
## ================ PERBANDINGAN MST ================
print(hasil_perbandingan_mst)
##   Metode_Bobot Total_Bobot_Prim Total_Bobot_Kruskal Edge_Prim_dan_Kruskal_Sama
## 1    Euclidean         50.23857            50.23857                       TRUE
## 2    Heaviside         17.00000            17.00000                      FALSE
cat("\n================ PERBANDINGAN METODE DAN k ================\n")
## 
## ================ PERBANDINGAN METODE DAN k ================
print(tabel_perbandingan_k)
##       Metode k_diminta k_terbentuk      SSW  Silhouette    Ukuran_Cluster
## 1  Euclidean         2           2 66.68724  0.25079935             43, 6
## 2  Euclidean         3           3 59.79749  0.13951867          37, 6, 6
## 3  Euclidean         4           4 55.77886  0.11816754       37, 6, 4, 2
## 4  Euclidean         5           5 51.78757  0.13176657    35, 6, 4, 2, 2
## 5  Euclidean         6           6 48.08042  0.15475188 34, 6, 4, 2, 2, 1
## 6  Heaviside         2           2 32.00000  0.21992016             41, 8
## 7  Heaviside         3           3 26.00000  0.11577642          35, 8, 6
## 8  Heaviside         4           4 21.00000  0.07471126       35, 6, 6, 2
## 9  Heaviside         5           5 18.00000  0.07586200    34, 6, 6, 2, 1
## 10 Heaviside         6           6 16.00000 -0.03881252 26, 8, 6, 6, 2, 1