K-Means

K-Means adalah suatu metode penganalisaan data atau metode Data Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi. Metode k-means berusaha mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama satu sama lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok yang lain. Dengan kata lain, metode ini berusaha untuk meminimalkan variasi antar data yang ada di dalam suatu cluster dan memaksimalkan variasi dengan data yang ada di cluster lainnya.

Objective function yang berusaha diminimalkan oleh k-means adalah:

J (U, V) = SUM (k=1 to N) SUM (i=1 to c) (a_ik * (x_k, v_i)^2)

dimana:
U : Matriks keanggotaan data ke masing-masing cluster yang berisikan nilai 0 dan 1
V : Matriks centroid/rata-rata masing-masing cluster
N : Jumlah data
c : Jumlah cluster
a_ik : Keanggotaan data ke-k ke cluster ke-i
x_k : data ke-k
v_i : Nilai centroid cluster ke-i

Prosedur yang digunakan dalam melakukan optimasi menggunakan k-means adalah sebagai berikut:
Step 1. Tentukan jumlah cluster
Step 2. Alokasikan data ke dalam cluster secara random
Step 3. Hitung centroid/rata-rata dari data yang ada di masing-masing cluster.
Step 4. Alokasikan masing-masing data ke centroid/rata-rata terdekat
Step 5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai centroid, ada yang di atas nilai threshold yang ditentukan atau apabila perubahan nilai pada objective function yang digunakan, di atas nilai threshold yang ditentukan

Centroid/rata-rata dari data yang ada di masing-masing cluster yang dihitung pada Step 3. didapatkan menggunakan rumus sebagai berikut:

v_ij = SUM (k=0 to N_i) (x_kj) / N_i

dimana:
i,k : indeks dari cluster
j : indeks dari variabel
v_ij : centroid/rata-rata cluster ke-i untuk variabel ke-j
x_kj : nilai data ke-k yang ada di dalam cluster tersebut untuk variabel ke-j
N_i : Jumlah data yang menjadi anggota cluster ke-i

Sedangkan pengalokasian data ke masing-masing cluster yang dilakukan pada Step 4. dilakukan secara penuh, dimana nilai yang memungkinkan untuk a_ik adalah 0 atau 1. Nilai 1 untuk data yang dialokasikan ke cluster dan nilai 0 untuk data yang dialokasikan ke cluster yang lain. Dalam menentukan apakah suatu data teralokasikan ke suatu cluster atau tidak, dapat dilakukan dengan menghitung jarak data tersebut ke masing-masing centroid/rata-rata masing-masing cluster. Dalam hal ini, a_ik akan bernilai 1 untuk cluster yang centroidnya terdekat dengan data tersebut, dan bernilai 0 untuk yang lainnya.

Referensi:
J. B. MacQueen (1967): “Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability”, Berkeley, University of California Press, 1:281-297
J. A. Hartigan (1975) “Clustering Algorithms”. Wiley.
J. A. Hartigan and M. A. Wong (1979). “A K-Means Clustering Algorithm”. Applied Statistics 28 (1): 100–108.

Cluster Validity Criterion

Untuk menentukan jumlah cluster yang paling tepat, saat menggunakan metode k-means dapat dilakukan dengan beberapa cara. Salah satunya adalah dengan cara manual yang saya jelaskan dalam posting saya tentang Akurasi Hasil Pemodelan K-Means yang sering juga direfer sebagai Bootstrapped Method. Selain itu ada beberapa cara yang lain yang juga bisa digunakan seperti di bawah ini.

Elbow Criterion (RMSSDT dan RS)

Elbow criterion adalah salah satu cara untuk menentukan jumlah cluster yang paling tepat untuk pemodelan k-means. Elbow criterion untuk k-means ini mengkombinasikan antara nilai RMSSTD dan RS statistics, dimana cluster yang paling tepat untuk suatu dataset ditentukan apabila perbedaan nilai antara RMSSTD dan RS menjadi berbanding terbalik dengan keadaan sebelumnya.

RMSSTD (Root Means Square Standard Deviation) merupakan alat ukur tingkat kemiripan (homogeneity) data yang terdapat di dalam cluster yang ditemukan (within clusters). Makin rendah nilai RMSSTD makin mirip data di dalam cluster yang ditemukan. RMSSDT dihitung menggunakan rumus sebagai berikut:

RMSSTD = SQRT (SUM(i=1 to k) SUM(j=1 to d) (SUM(k=1 to N_i) ((x_kj – mu_j)^2)) /
SUM(i=1 to k) SUM(j=1 to d) (N_i – 1))

RS (R Squared) digunakan untuk mengukur tingkat kesamaan atau ketidaksamaan antara cluster (between clusters). RS mempunyai nilai antara 0 dan 1. Nilai 0 untuk cluster yang sama dan 1 untuk cluster yang benar-benar berbeda. RS dihitung dengan rumus:

RS = (SS_t – SS_w) / SS_t

SS_t = SUM(j=1 to d) (SUM(k=1 to N) ((x_kj – mu_j)^2) dan
SS_w = SUM(i=1 to k) SUM(j=1 to d) (SUM(k=1 to N_i) ((x_kj – mu_j)^2))

Notasi:
x_kj : data ke-k yang ada di dalam cluster untuk dimensi ke-j
mu_j : means/rata-rata nilai dari variabel dimensi ke-j
N_i : jumlah data di dalam cluster ke-i
N : jumlah data keseluruhan
d : jumlah dimensi dari data
k : jumlah cluster

Elbow criterion adalah suatu modelling criterion yang bisa digunakan untuk menentukan jumlah cluster dengan melihat perubahan perbandingan antara nilai RMSSTD dan RS. Hal ini dilihat dengan membandingkan persentase tingkat perubahan kedua nilai (RMSSTD dan RS). Apabila muncul suatu keadaan yang berbanding terbalik dengan keadaan sebelumnya, maka titik sebelum terjadinya perubahan tersebut dianggap sebagai jumlah cluster yang paling tepat.

Referensi:
Subhash Sharma: Applied Multivariate Techniques, John Wiley & Sons, Inc., 1996.

G-Means (Gaussian Means)

G-Means berusaha menentukan jumlah cluster secara gradual dengan melihat apakah suatu cluster sudah dalam keadaan terdistribusi secara normal atau tidak. Kalau masih dianggap belum normal, maka akan dilihat apakah cluster tersebut masih bisa displit untuk dijadikan dua cluster. Hipotesis yang digunakan adalah:

H0: Data di sekitar centroid disample dari suatu distribusi Gaussian.
H1: Data di sekitar centroid tidak disample dari suatu distribusi Gaussian.

Adapun algoritma yang digunakan untuk menentukan split atau tidak adalah sebagai berikut:
1. Tentukan confidence level Alpha untuk testing.
2. Tentukan dua centroid baru c1 dan c2.
3. Jalankan k-means terhadap dua centroid baru tersebut.
4. Tentukan vektor v yang menghubungkan antara centroid c1 dan c2 dimana v = c1 – c2. Kemudian proyeksikan data X ke v dengan rumus x’ = (x,v)/||v||^2. X’ merupakan representasi satu dimensi dari data yang diproyeksikan ke v. Hitung z = F(x’), dimana z adalah bentuk normalisasi x’.
5. Hitung nilai A_2*(Z) dengan rumus di bawah. Apabila A_2*(Z) berada di wilayah nilai non-critical pada confidence level Alpha, maka H0 diterima, dan centroid awal tetap digunakan dan centroid baru c1 dan c2 dihapus. Untuk keadaan sebaliknya, H0 harus ditolak dan centroid baru c1 dan c2 digunakan sebagai pengganti centroid awal.

A_2*(Z) = A_2(Z)(1+4/n-25/(n^2)) dan
A_2(Z) = -1/n * SUM (i=1 to n) ((2*i – 1)(log(z_i)+log(1-z_(n+1-i))) – n

dimana:
n : Jumlah data

Referensi:
G. Hamerly and C. Elkan (2003). Learning the k in k-means. In Proceedings of 17th Neural Information Processing Systems.

X-Means
Merupakan suatu pengembangan k-means untuk menentukan jumlah cluster yang paling tepat untuk suatu dataset yang dianalisa. Adapun algoritma yang diterapkan di dalam metote ini adalah dengan menggabungkan algoritma k-means murni dan salah satu modelling criterion seperti Bayesian Information Criterion (BIC) atau Akaike Information Criterion (AIC) – penjelasan tentang kedua criteria ini ada di My Mixture Modelling Page. Algoritma yang diterapkan adalah sebagai berikut:
Step 1: Tentukan jumlah cluster
Step 2: Lakukan optimasi dengan k-means murni
Step 3: Untuk setiap cluster yang dihasilkan split cluster menjadi dua dan bandingkan modelling score antara model dengan satu cluster dan model dengan dua cluster. Model dengan score yang lebih baik dipilih menjadi perwakilan model yang displit.

Referensi
Pelleg D. and Moore A. (2000). X-means: Extending K-means with Efficient Estimation of the Number of Clusters. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML). 727-734.

K-Means Variances

Fuzzy c-Means
Variasi dalam hal penentuan nilai keanggotaan data ke masing-masing cluster.

Fuzzy c-Means merupakan perkembangan dari metode k-means dengan memperhitungkan bahwa data dapat tergabung ke dalam ke dalam beberapa cluster dengan tingkat keanggotaan yang berbeda-beda. Tetapi sum total dari nilai keanggotaan data tersebut harus sama dengan 1. Misalnya data x1 bisa tergabung dengan cluster I dengan tingkat keanggotaan 0,7, dengan cluster II dengan tingkat keanggotaan 0,2 dan dengan cluster III dengan tingkat keanggotaan 0,1. Hal ini berbeda dengan k-means karena metode tersebut mengharuskan suatu data untuk menjadi anggota atau tidak sekalian.

Algoritma yang digunakan dalam fuzzy c-means sama dengan algoritma yang digunakan dalam k-means. Tetapi objective function dan rumus yang digunakan untuk menghitung centroid/rata-rata berbeda. Di samping itu, dalam fuzzy c-means, tingkat keanggotaan, yang sering disebut dengan membership function, juga perlu di hitung. Objective function dan rumus-rumus yang digunakan adalah sebagai berikut:

Objective function:

J (U, V) = SUM (k=1 to N) SUM (i=1 to c) (u_ik^m * (x_k, v_i)^2)

dimana:
u_ik = membership function data ke i ke cluster ke k
m = weighting exponent
U, V, N, c, x_k dan v_i : sudah dijelaskan di objective function untuk k-means

Rumus menghitung rata-rata/centroid:

v_ij = SUM (k=1 to N_i) (u_ik^m * x_kj) / SUM (k=1 to N_i) (u_ik^m)

Rumus menghitung membership function:

u_ik = SUM (j=1 to c) ((x_k – v_i)/(x_k – v_j))^(2/(m-1))

Referensi:
Bezdek, J.C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York.

K Harmonic Means
Variasi dalam hal objective function yang digunakan.

K Harmonic Means menggunakan suatu objective function untuk menghindarkan pengaruh yang besar dari data-data yang ada di sekitar cluster center. Untuk keperluan tersebut, di samping nilai keanggotaan dari data terhadap cluster, setiap data juga mempunyai nilai weight yang digunakan untuk meng-harmoni-kan pengaruh masing-masing data dalam pemodelan. Adapun objective function yang digunakan dalam metode ini adalah sebagai berikut:

J (V) = SUM (k=1 to N) (c / (SUM (i=1 to c) (1/ (x_k- v_i)^p)))

dimana:
V : Matriks centroid/rata-rata masing-masing cluster
N : Jumlah data
c : Jumlah cluster
v_i : Nilai centroid cluster ke-i
p : suatu input parameter yang besarnya lebih dari atau sama dengan 2

Nilai membership function u_ik dan weight w_k dihitung dengan rumus sebagai berikut:

u_ik = SUM (j=1 to c) ((x_k – v_i)/(x_k – v_j))^(-p-2)

w_k = SUM (j=1 to c) (x_k – v_j)^(-p-2) / (SUM (j=1 to c) (x_k – v_j)^(-p))^2

Referensi:
G. Hamerly and C. Elkan (2002). Altenatives to the k-means algorithm that find better clusterings. In Proceedings of the 11th International Conference on Information and Knowledge Management. pp. 600-607.

Kernel K-means
Variasi untuk sekumpulan data yang ‘dianggap’ terkelompok secara non-linear.

K-means yang standar umumnya digunakan untuk mengelompokkan data yang secara umum datanya dipisahkan secara linear. Kalau data ‘dianggap’ terkelompok secara non-linear, k-means perlu dimodifikasi untuk dapat mengakomodasi ke-non-linear-an tersebut. Adapun metode yang diimplementasikan di dalam menyelesaikan permasalahan ini adalah dengan mengadopsi Kernel Trick dalam proses pengelompokan yang dilakukan.

Perlu diketahui di sini, untuk bisa menerapkan Kernel Trick, data perlu untuk dipetakan terlebih dahulu ke bentuk data dengan dimensi yang lain, yang umumnya jumlah dimensinya lebih tinggi dengan fungsi THETA(x), yang artinya data x dipetakan dari dimensi awal ke dimensi yang lain (umumnya dimensi yang lebih tinggi).

Adapun objective function yang digunakan untuk Kernel K-Means adalah:

J (U, V) = SUM (k=1 to N) SUM (i=1 to c) (a_ik * (THETA(x_k), v_i)^2)

dimana:
U : Matriks keanggotaan data ke masing-masing cluster yang berisikan nilai 0 dan 1
V : Matriks centroid/rata-rata masing-masing cluster
N : Jumlah data
c : Jumlah cluster
a_ik : Keanggotaan data ke-k ke cluster ke-i
v_i : Nilai centroid cluster ke-i

Rumus menghitung rata-rata/centroid:

v_ij = SUM (k=0 to N_i) THETA (x_kj) / N_i

yang tentunya tidak bisa dihitung, karena kita tidak bisa mengetahui nilai THETA (x_kj) secara langsung. Hal ini bisa diakali, dengan langsung menentukan nilai a_ik (yang nilainya adalah 1 atau 0), dimana a_ik bernilai 1 untuk data yang mempunyai jarak terdekat dengan centroid dan 0 untuk yang lainnya. Adapun jarak antara data dengan centroid dihitung dengan rumus berikut ini:

(THETA(x_l),v_i)^2 = SUM (l=0 to N_i) THETA(x_lj)*THETA(x_lj) -
2*SUM (k,l=0 to N_i) THETA (x_lj)*THETA (x_kj)/ N_i +
SUM (k=0 to N_i) THETA (x_kj)*THETA (x_kj)/ N_i

Disini fungsi kernel disubstitusikan, sehingga jarak antara data dengan centroid dapat dihitung dengan rumus berikut ini:

(THETA(x_l),v_i)^2 = SUM (l=0 to N_i) K(x_lj,x_lj) -
2*SUM (k,l=0 to N_i) K (x_lj,x_kj)/ N_i + SUM (k=0 to N_i) K (x_kj,x_kj)/ N_i

Data di-assign ke dalam kelompok yang jarak antara centroid dan data tersebut diminimalkan. Prosedur yang digunakan tetap sama dengan prosedur yang diterapkan pada standar k-means.

Referensi
M Girolami (2002). Mercer kernel-based clustering in feature space. Neural Networks, IEEE Transactions on, Vol. 13, No. 3., pp. 780-784.
Inderjit S Dhillon, Yuqiang Guan, Brian Kulis (2004).Kernel k-means: spectral clustering and normalized cuts. pp. 551-556

K-Modes
Variasi dalam hal data yang dianalisa bukan continuous, tapi categorical.

Untuk data categorical, k-means tidak bisa digunakan karena data categorical tidak bisa dicari nilai means (rata-rata)-nya. Untuk keperluan tersebut K-Modes dapat digunakan sebagai gantinya. Adapun algoritma yang digunakan sama dengan k-means dengan beberapa modifikasi sebagai berikut:
Step 1. Tentukan jumlah cluster
Step 2. Alokasikan data ke dalam cluster secara random
Step 3. Hitung modes dari data yang ada di masing-masing cluster.
Step 4. Alokasikan masing-masing data ke cluster terdekat menggunakan Hemming Distance
Step 5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai modes atau apabila perubahan nilai pada objective function yang digunakan, di atas nilai threshold yang ditentukan

Objective function yang digunakan k-modes adalah:

J (A, M) = SUM (k=1 to N) SUM (i=1 to c) (a_ik * D(x_k, m_i))

dimana:
A : Matriks keanggotaan data ke masing-masing cluster yang berisikan nilai 0 dan 1
M : Matriks modes masing-masing cluster
N : Jumlah data
c : Jumlah cluster
a_ik : Keanggotaan data ke-k ke cluster ke-i
x_k : data ke-k
m_i : Nilai modes cluster ke-i
D(x_k, m_i) : Hemming Distance antara data x dan modes m

Referensi:
Chaturvedi, A.D., Green, P.E. and Carroll, J.D. (2001). K-Modes Clustering. Journal of Classification, 18, 35-56.