1. Persiapan Package dan Dataset

# Memuat package yang digunakan
library(sf)
library(spData)
library(spdep)
library(igraph)
library(ggplot2)
library(dplyr)
library(cluster)

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

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

# Mengambil data atribut tanpa geometri
data_asli <- columbus_sf |>
  st_drop_geometry() |>
  dplyr::select(all_of(variabel))

# Jumlah wilayah
n <- nrow(columbus_sf)

# Memberikan ID untuk setiap node
columbus_sf$node <- seq_len(n)

# Memastikan jumlah observasi konsisten
stopifnot(nrow(data_asli) == n)

# Memeriksa data
head(data_asli)
dim(data_asli)
## [1] 49  3

2. Visualisasi Peta Awal Columbus

plot(
  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
)

3. Identifikasi Node dan Edge: Connectivity Graph

Setiap wilayah direpresentasikan sebagai node. Dua wilayah dianggap bertetangga apabila berbagi sisi atau titik sudut (Queen Contiguity).

# Membentuk daftar ketetanggaan Queen Contiguity
nb <- poly2nb(
  columbus_sf,
  queen = TRUE
)

# Membuat matriks ketetanggaan
adj_matrix <- nb2mat(
  nb,
  style = "B",
  zero.policy = TRUE
)

# Mengambil pasangan node yang bertetangga
edge_adj <- which(
  upper.tri(adj_matrix) & adj_matrix == 1,
  arr.ind = TRUE
)

# Membentuk connectivity graph
g_connect <- 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))
  )
)

# Menghitung jumlah node, edge, dan komponen graf
jumlah_node <- vcount(g_connect)
jumlah_edge <- ecount(g_connect)
jumlah_komponen <- components(g_connect)$no

jumlah_node
## [1] 49
jumlah_edge
## [1] 118
jumlah_komponen
## [1] 1
# Memastikan seluruh wilayah terhubung dalam connectivity graph
stopifnot(jumlah_node == n)
stopifnot(jumlah_komponen == 1)

4. Menyiapkan Koordinat untuk Visualisasi Graf

Titik representatif setiap poligon digunakan sebagai posisi node pada visualisasi graf.

# Mengambil titik representatif setiap poligon
titik <- st_point_on_surface(columbus_sf)
## Warning: st_point_on_surface assumes attributes are constant over geometries
# Mengambil koordinat X dan Y
koordinat <- st_coordinates(titik)

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

# Fungsi untuk mengubah pasangan edge menjadi koordinat garis
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 |>
    mutate(
      x = koordinat[from, 1],
      y = koordinat[from, 2],
      xend = koordinat[to, 1],
      yend = koordinat[to, 2]
    )
}

5. Visualisasi Connectivity Graph

# Mengubah pasangan edge menjadi koordinat garis
edge_graph <- buat_edge_plot(edge_adj)

# Menggambar peta wilayah
plot(
  st_geometry(columbus_sf),
  col = "grey95",
  border = "grey75",
  lwd = 0.5,
  main = "Connectivity Graph Columbus",
  axes = FALSE
)

# Menggambar edge
segments(
  x0 = edge_graph$x,
  y0 = edge_graph$y,
  x1 = edge_graph$xend,
  y1 = edge_graph$yend,
  col = "steelblue",
  lwd = 1
)

# Menggambar node
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
)

6. Standardisasi Atribut

Variabel CRIME, INC, dan HOVAL memiliki skala pengukuran yang berbeda. Oleh karena itu, dilakukan standardisasi menggunakan z-score sebelum menghitung jarak atribut.

data_std <- as.data.frame(scale(data_asli))

# Memastikan tidak terdapat nilai hilang
stopifnot(all(complete.cases(data_std)))

head(data_std)
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

7. Menghitung Bobot Edge

Bobot edge dihitung berdasarkan jarak Euclidean antarwilayah yang bertetangga. Jarak yang lebih kecil menunjukkan atribut wilayah yang relatif lebih mirip.

# Menghitung ketidakmiripan atribut antarwilayah bertetangga
biaya <- nbcosts(
  nb,
  as.matrix(data_std),
  method = "euclidean"
)

# Membentuk spatial weights list
nb_w <- nb2listw(
  nb,
  glist = biaya,
  style = "B",
  zero.policy = TRUE
)

# Memeriksa jumlah bobot pada setiap wilayah
length(biaya)
## [1] 49

8. Membangun Spanning Tree Ilustratif dengan BFS

Spanning tree berikut dibangun menggunakan Breadth-First Search (BFS). Pohon ini hanya digunakan untuk memperlihatkan konsep spanning tree dan bukan merupakan MST yang digunakan dalam algoritma SKATER.

hasil_bfs <- igraph::bfs(
  g_connect,
  root = 1,
  parent = TRUE
)

# Mengambil parent setiap node
parent <- as.integer(hasil_bfs$parent)

# Mengidentifikasi node yang memiliki parent
node_anak <- which(
  !is.na(parent) & parent > 0
)

# Membentuk pasangan edge spanning tree
edge_tree <- cbind(
  parent[node_anak],
  node_anak
)

# Membentuk graf spanning tree
g_tree <- graph_from_data_frame(
  data.frame(
    from = as.character(edge_tree[, 1]),
    to = as.character(edge_tree[, 2])
  ),
  directed = FALSE,
  vertices = data.frame(
    name = as.character(seq_len(n))
  )
)

# Memastikan spanning tree memiliki n - 1 edge
stopifnot(vcount(g_tree) == n)
stopifnot(ecount(g_tree) == n - 1)
stopifnot(components(g_tree)$no == 1)

vcount(g_tree)
## [1] 49
ecount(g_tree)
## [1] 48

9. Visualisasi Spanning Tree

edge_tree_plot <- buat_edge_plot(edge_tree)

plot(
  st_geometry(columbus_sf),
  col = "grey95",
  border = "grey75",
  lwd = 0.5,
  main = "Spanning Tree Columbus (BFS)",
  axes = FALSE
)

segments(
  x0 = edge_tree_plot$x,
  y0 = edge_tree_plot$y,
  x1 = edge_tree_plot$xend,
  y1 = edge_tree_plot$yend,
  col = "darkgreen",
  lwd = 1.5
)

points(
  data_node$x,
  data_node$y,
  col = "darkgreen",
  pch = 19,
  cex = 0.8
)

legend(
  "bottomleft",
  legend = c("Node (Wilayah)", "Edge (Spanning Tree)"),
  col = c("darkgreen", "darkgreen"),
  pch = c(19, NA),
  lty = c(NA, 1),
  bty = "n",
  cex = 0.8
)

mtext(
  "Satu contoh pohon rentang yang menghubungkan seluruh node",
  side = 1,
  line = 1,
  cex = 0.8
)

10. Membangun Minimum Spanning Tree (MST)

MST dibangun berdasarkan bobot edge pada graf ketetanggaan. MST menghubungkan seluruh node dengan total bobot edge minimum tanpa membentuk siklus.

mst <- mstree(
  nb_w,
  ini = 1
)

# Mengambil pasangan node pada MST
edge_mst <- mst[, 1:2, drop = FALSE]

# Membentuk graf MST
g_mst <- graph_from_data_frame(
  data.frame(
    from = as.character(edge_mst[, 1]),
    to = as.character(edge_mst[, 2])
  ),
  directed = FALSE,
  vertices = data.frame(
    name = as.character(seq_len(n))
  )
)

# Menambahkan bobot pada edge MST
E(g_mst)$weight <- mst[, 3]

# Memastikan MST memiliki n - 1 edge dan satu komponen
stopifnot(vcount(g_mst) == n)
stopifnot(ecount(g_mst) == n - 1)
stopifnot(components(g_mst)$no == 1)

vcount(g_mst)
## [1] 49
ecount(g_mst)
## [1] 48
components(g_mst)$no
## [1] 1
# Menyiapkan koordinat edge MST untuk visualisasi
edge_mst_plot <- buat_edge_plot(edge_mst)

11. Visualisasi Minimum Spanning Tree

plot(
  st_geometry(columbus_sf),
  col = "grey95",
  border = "grey75",
  lwd = 0.5,
  main = "Minimum Spanning Tree Columbus",
  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", ecount(g_mst), "edge"),
  side = 1,
  line = 1,
  cex = 0.8
)

12. Implementasi Algoritma SKATER

Jumlah region ditetapkan sebanyak 4 sehingga jumlah edge yang dipotong adalah \(K-1=3\).

# Menentukan jumlah region
k <- 4

# Menjalankan algoritma SKATER
hasil_skater <- spdep::skater(
  edges = edge_mst[, 1:2, drop = FALSE],
  data = data_std,
  ncuts = k - 1,
  method = "euclidean"
)

# Menambahkan label cluster ke data spasial
columbus_sf$cluster <- factor(hasil_skater$groups)

# Ukuran setiap region
ukuran_region <- table(hasil_skater$groups)

# Memeriksa konsistensi hasil
stopifnot(length(hasil_skater$groups) == n)
stopifnot(length(unique(hasil_skater$groups)) == k)
stopifnot(sum(ukuran_region) == n)

ukuran_region
## 
##  1  2  3  4 
## 37  4  6  2

13. Menyiapkan Edge Hasil SKATER

Bagian ini mengidentifikasi edge MST yang dipertahankan dan edge yang dipotong oleh algoritma SKATER. Objek edge_skater_plot dibentuk di sini sebelum digunakan pada visualisasi graf.

# Mengambil edge yang dipertahankan pada setiap region
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]
  }
)

# Menggabungkan seluruh edge yang dipertahankan
edge_tersisa_list <- Filter(
  Negate(is.null),
  edge_tersisa_list
)

edge_tersisa <- do.call(rbind, edge_tersisa_list)

# Membuat identitas edge yang 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 = "-")
  })
}

# Membandingkan edge MST dengan edge hasil SKATER
edge_mst_key <- edge_key(edge_mst)
edge_tersisa_key <- edge_key(edge_tersisa)

# Mengidentifikasi edge yang dipotong
edge_potong <- setdiff(
  edge_mst_key,
  edge_tersisa_key
)

# Memberikan status pada setiap edge MST
edge_skater_plot <- edge_mst_plot |>
  mutate(
    status = ifelse(
      edge_mst_key %in% edge_potong,
      "Dipotong",
      "Dipertahankan"
    )
  )

# Memeriksa jumlah edge
table(edge_skater_plot$status)
## 
## Dipertahankan      Dipotong 
##            45             3
length(edge_potong)
## [1] 3
# Memastikan jumlah edge yang dipotong sesuai dengan K - 1
stopifnot(length(edge_potong) == k - 1)

14. Visualisasi Peta Hasil SKATER

warna_region <- rainbow(k)

plot(
  st_geometry(columbus_sf),
  col = warna_region[as.integer(columbus_sf$cluster)],
  border = "white",
  lwd = 0.8,
  main = "Hasil Spatial Clustering SKATER",
  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
)

15. Visualisasi Graf Hasil SKATER

Edge yang dipertahankan ditampilkan dengan garis abu-abu, sedangkan edge yang dipotong ditampilkan dengan garis merah putus-putus. Warna node menunjukkan region hasil clustering.

# Menambahkan informasi cluster pada node
data_node$cluster <- factor(hasil_skater$groups)

warna_cluster <- rainbow(k)

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

# Edge yang dipertahankan
edge_dipertahankan <- edge_skater_plot |>
  filter(status == "Dipertahankan")

segments(
  x0 = edge_dipertahankan$x,
  y0 = edge_dipertahankan$y,
  x1 = edge_dipertahankan$xend,
  y1 = edge_dipertahankan$yend,
  col = "grey40",
  lwd = 1
)

# Edge yang dipotong
edge_dipotong <- edge_skater_plot |>
  filter(status == "Dipotong")

segments(
  x0 = edge_dipotong$x,
  y0 = edge_dipotong$y,
  x1 = edge_dipotong$xend,
  y1 = edge_dipotong$yend,
  col = "red",
  lwd = 2,
  lty = 2
)

# Node berdasarkan region
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
)

# Pemeriksaan jumlah edge dan ukuran region
table(edge_skater_plot$status)
## 
## Dipertahankan      Dipotong 
##            45             3
table(hasil_skater$groups)
## 
##  1  2  3  4 
## 37  4  6  2

16. Evaluasi Hasil: Total Within-Region Sum of Squares

Nilai within-region sum of squares (SSW) menggambarkan total variasi atribut di dalam region. Nilai yang lebih kecil menunjukkan anggota region yang relatif lebih homogen berdasarkan atribut yang digunakan.

# Memeriksa komponen hasil SKATER
names(hasil_skater)
## [1] "groups"       "edges.groups" "not.prune"    "candidates"   "ssto"        
## [6] "ssw"          "crit"         "vec.crit"
# Mengambil nilai SSW dari hasil SKATER
if (is.null(hasil_skater$ssw)) {
  stop(
    "Komponen hasil_skater$ssw tidak tersedia. ",
    "Periksa names(hasil_skater) dan struktur objek hasil SKATER."
  )
}

nilai_Q <- as.numeric(hasil_skater$ssw)

# Membuat tabel nilai Q pada setiap jumlah region
tabel_Q <- data.frame(
  Jumlah_Region = seq_along(nilai_Q),
  Q = nilai_Q
)

tabel_Q
# Visualisasi perubahan nilai Q
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"
  ) +
  theme_minimal()

print(graf_Q)

17. Evaluasi Ukuran Region

tabel_ukuran <- as.data.frame(
  table(hasil_skater$groups)
)

colnames(tabel_ukuran) <- c(
  "Region",
  "Jumlah_Area"
)

# Menghitung proporsi wilayah pada setiap region
tabel_ukuran$Proporsi <- round(
  tabel_ukuran$Jumlah_Area / n * 100,
  2
)

tabel_ukuran
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)

18. Profil Atribut Setiap Region

Profil region dihitung menggunakan rata-rata variabel CRIME, INC, dan HOVAL pada setiap region.

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

profil_region <- data_hasil |>
  group_by(Region) |>
  summarise(
    across(
      all_of(variabel),
      ~ mean(.x, na.rm = TRUE)
    ),
    .groups = "drop"
  )

profil_region

19. Evaluasi Silhouette

Silhouette digunakan sebagai evaluasi tambahan berdasarkan jarak atribut. Ukuran ini tidak secara langsung mengukur kontiguitas spasial, sehingga perlu dibaca bersama hasil peta dan graf SKATER.

# Menghitung jarak antarwilayah berdasarkan atribut terstandardisasi
jarak <- dist(data_std)

# Menghitung silhouette
hasil_silhouette <- cluster::silhouette(
  as.integer(hasil_skater$groups),
  jarak
)

# Rata-rata silhouette
rata_silhouette <- mean(
  hasil_silhouette[, "sil_width"]
)

rata_silhouette
## [1] 0.1181675
# Visualisasi silhouette
plot(
  hasil_silhouette,
  main = "Silhouette Hasil Spatial Clustering SKATER"
)

20. Ringkasan Hasil Analisis

# Dimensi dataset
dim(data_asli)
## [1] 49  3
# Jumlah node dan edge connectivity graph
jumlah_node
## [1] 49
jumlah_edge
## [1] 118
jumlah_komponen
## [1] 1
# Jumlah node dan edge MST
vcount(g_mst)
## [1] 49
ecount(g_mst)
## [1] 48
# Jumlah region
length(unique(hasil_skater$groups))
## [1] 4
# Jumlah edge yang dipotong
length(edge_potong)
## [1] 3
# Ukuran setiap region
ukuran_region
## 
##  1  2  3  4 
## 37  4  6  2
# Nilai SSW
tabel_Q
# Profil atribut setiap region
profil_region
# Rata-rata silhouette
rata_silhouette
## [1] 0.1181675