# 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
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
)
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)
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]
)
}
# 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
)
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
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
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
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
)
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)
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
)
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
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)
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
)
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
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)
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)
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
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"
)
# 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