Dalam matematika, ruang produk dalam (inner product space) pada bilangan real (R) adalah ruang vektor yang dilengkapi dengan operasi dalam produk dalam, yang sering disebut sebagai “inner product”. Inner product adalah fungsi bilinear simetris yang memetakan dua vektor menjadi bilangan real.

Dalam ruang produk dalam pada R, kita dapat mendefinisikan inner product antara dua vektor u dan v sebagai hasil perkalian skalar antara kedua vektor tersebut. Inner product ini memenuhi beberapa sifat penting, yaitu simetri, linearitas dalam faktor pertama, konjugat linearitas dalam faktor kedua, dan positif definit.

Dengan adanya inner product, kita dapat mendefinisikan konsep norma (panjang) vektor. Norma vektor dapat dihitung sebagai akar kuadrat dari hasil inner product vektor itu dengan dirinya sendiri. Dengan demikian, norma memberikan ukuran panjang atau jarak antara vektor dalam ruang produk dalam.

Untuk bagian ini, kami menggunakan set data “USArrests” yang kami gunakan sebagai Contoh Pendahuluan untuk Bab 4. Pada Bab 4, kita telah menggunakan pengelompokan hirarkis untuk menemukan klaster dalam set data. Pada bagian ini kita akan menggunakan metode k-means clustering untuk menemukan cluster pada data set dengan menggunakan fungsi kmeans() pada R. K-means clustering merupakan metode tanpa pengawasan yang menggunakan rata-rata cluster untuk menemukan cluster.

Pada dasarnya metode ini meminimalkan jumlah jarak antara titik data dengan rata-rata untuk setiap cluster. Pada pembahasan di bagian ini, kita akan membahas bagaimana prosedur k-means clustering bekerja. Namun, pertama-tama, kami akan menunjukkan bagaimana cara menghitung cluster melalui k-means clustering di R dengan menggunakan dataset “USArrests”.

df <- USArrests 
df <- na.omit(df) 
df <- scale(df)

Lalu kita gunakan fungsi kmeans() untuk mencari cluster pada data set :

# nstart is the number of random starting points 
clusters <- kmeans(df, 4, nstart = 10)

Sekarang kita memplot hasil dari fungsi kmeans(). Seperti yang telah kita lakukan pada bahasan sebelumnya, kita akan menggunakan fungsi fviz cluster() dari paket factoextra. Pertama kita unggah paket tersebut:

library(factoextra)
## Warning: package 'factoextra' was built under R version 4.2.3
## Loading required package: ggplot2
## Warning: package 'ggplot2' was built under R version 4.2.3
## Welcome! Want to learn more? See two factoextra-related books at https://goo.gl/ve3WBa
fviz_cluster(clusters, df)

Algoritma dari metode k-means clustering adalah menghitung rata-rata secara berulang-ulang dan menetapkan anggota baru untuk setiap cluster dengan menghitung jarak antara rata-rata dan observasi. Jarak antara rata-rata dan pengamatan didefinisikan sebagai ||µi -xj||, di mana µi adalah rata-rata cluster i dan xj adalah pengamatan ke-j. Secara lebih spesifik, garis besar algoritmanya adalah sebagai berikut:

  1. Inisialisasi rata-rata µi untuk i = 1,…,k dengan memilih pengamatan acak dalam set data input.
  2. Tetapkan anggota xj untuk j = 1,…,n ke dalam klaster ke-i dari kumpulan data jika (||µi -x1||+ … +||µi -xn||) diminimalkan.
  3. Hitung ulang rata-rata µi untuk cluster i dan ulangi prosesnya. Jika Anda tertarik dengan bagaimana fungsi kmeans() dituliskan dalam R, kita dapat menggunakan fungsi print().
print(kmeans)
## function (x, centers, iter.max = 10L, nstart = 1L, algorithm = c("Hartigan-Wong", 
##     "Lloyd", "Forgy", "MacQueen"), trace = FALSE) 
## {
##     .Mimax <- .Machine$integer.max
##     do_one <- function(nmeth) {
##         switch(nmeth, {
##             isteps.Qtran <- as.integer(min(.Mimax, 50 * m))
##             iTran <- c(isteps.Qtran, integer(k))
##             Z <- .Fortran(C_kmns, x, m, p, centers = centers, 
##                 as.integer(k), c1 = integer(m), c2 = integer(m), 
##                 nc = integer(k), double(k), double(k), ncp = integer(k), 
##                 D = double(m), iTran = iTran, live = integer(k), 
##                 iter = iter.max, wss = double(k), ifault = as.integer(trace))
##             switch(Z$ifault, stop("empty cluster: try a better set of initial centers", 
##                 call. = FALSE), Z$iter <- max(Z$iter, iter.max + 
##                 1L), stop("number of cluster centres must lie between 1 and nrow(x)", 
##                 call. = FALSE), warning(gettextf("Quick-TRANSfer stage steps exceeded maximum (= %d)", 
##                 isteps.Qtran), call. = FALSE))
##         }, {
##             Z <- .C(C_kmeans_Lloyd, x, m, p, centers = centers, 
##                 k, c1 = integer(m), iter = iter.max, nc = integer(k), 
##                 wss = double(k))
##         }, {
##             Z <- .C(C_kmeans_MacQueen, x, m, p, centers = as.double(centers), 
##                 k, c1 = integer(m), iter = iter.max, nc = integer(k), 
##                 wss = double(k))
##         })
##         if (m23 <- any(nmeth == c(2L, 3L))) {
##             if (any(Z$nc == 0)) 
##                 warning("empty cluster: try a better set of initial centers", 
##                   call. = FALSE)
##         }
##         if (Z$iter > iter.max) {
##             warning(sprintf(ngettext(iter.max, "did not converge in %d iteration", 
##                 "did not converge in %d iterations"), iter.max), 
##                 call. = FALSE, domain = NA)
##             if (m23) 
##                 Z$ifault <- 2L
##         }
##         if (nmeth %in% c(2L, 3L)) {
##             if (any(Z$nc == 0)) 
##                 warning("empty cluster: try a better set of initial centers", 
##                   call. = FALSE)
##         }
##         Z
##     }
##     x <- as.matrix(x)
##     m <- as.integer(nrow(x))
##     if (is.na(m)) 
##         stop("invalid nrow(x)")
##     p <- as.integer(ncol(x))
##     if (is.na(p)) 
##         stop("invalid ncol(x)")
##     if (missing(centers)) 
##         stop("'centers' must be a number or a matrix")
##     nmeth <- switch(match.arg(algorithm), `Hartigan-Wong` = 1L, 
##         Lloyd = 2L, Forgy = 2L, MacQueen = 3L)
##     storage.mode(x) <- "double"
##     if (length(centers) == 1L) {
##         k <- centers
##         if (nstart == 1L) 
##             centers <- x[sample.int(m, k), , drop = FALSE]
##         if (nstart >= 2L || any(duplicated(centers))) {
##             cn <- unique(x)
##             mm <- nrow(cn)
##             if (mm < k) 
##                 stop("more cluster centers than distinct data points.")
##             centers <- cn[sample.int(mm, k), , drop = FALSE]
##         }
##     }
##     else {
##         centers <- as.matrix(centers)
##         if (any(duplicated(centers))) 
##             stop("initial centers are not distinct")
##         cn <- NULL
##         k <- nrow(centers)
##         if (m < k) 
##             stop("more cluster centers than data points")
##     }
##     k <- as.integer(k)
##     if (is.na(k)) 
##         stop(gettextf("invalid value of %s", "'k'"), domain = NA)
##     if (k == 1L) 
##         nmeth <- 3L
##     iter.max <- as.integer(iter.max)
##     if (is.na(iter.max) || iter.max < 1L) 
##         stop("'iter.max' must be positive")
##     if (ncol(x) != ncol(centers)) 
##         stop("must have same number of columns in 'x' and 'centers'")
##     storage.mode(centers) <- "double"
##     Z <- do_one(nmeth)
##     best <- sum(Z$wss)
##     if (nstart >= 2L && !is.null(cn)) 
##         for (i in 2:nstart) {
##             centers <- cn[sample.int(mm, k), , drop = FALSE]
##             ZZ <- do_one(nmeth)
##             if ((z <- sum(ZZ$wss)) < best) {
##                 Z <- ZZ
##                 best <- z
##             }
##         }
##     centers <- matrix(Z$centers, k)
##     dimnames(centers) <- list(1L:k, dimnames(x)[[2L]])
##     cluster <- Z$c1
##     if (!is.null(rn <- rownames(x))) 
##         names(cluster) <- rn
##     totss <- sum(scale(x, scale = FALSE)^2)
##     structure(list(cluster = cluster, centers = centers, totss = totss, 
##         withinss = Z$wss, tot.withinss = best, betweenss = totss - 
##             best, size = Z$nc, iter = Z$iter, ifault = Z$ifault), 
##         class = "kmeans")
## }
## <bytecode: 0x0000005739714598>
## <environment: namespace:stats>
library(animation)
## Warning: package 'animation' was built under R version 4.2.3
kmeans.ani(df, 4)

fviz_nbclust(df, kmeans, method = "wss")