Manually K-Means Cluster Analysis

Hello guys, today I'm gonna show you how to manually calculate k-means cluster analysis, it looks like i have posted about k-means cluster analysis before, but it was calculated by using R programming, and this is special edition for you, step by step will be explained in brief on this post. I will simulate the clustering process using 1 variable and even 3 variables. Therefore, please read this article to completion. I hope you have known and familiar about k-means cluster analysis in advance, it is one of method used to classify the data into some groups without labeling first (unsupervised).

Singkatnya, proses / cara kerja metode k-means cluster adalah mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama satu dengan yang lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok yang 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.

Adapun algoritma k-means cluster adalah sebagai berikut:

Menentukan jumlah cluster
Menentukan nilai centroid awal (initial centroid)
Menghitung jarak masing-masing data terhadap centroid pada masing-masing cluster
Mengidentifikasi data yang memiliki jarak terkecil/terdekat terhadap cluster centroid dan mengalokasikan masing-masing data ke cluster dengan jarak terdekat
Menghitung rata-rata centroid yang baru pada masing-masing cluster
Kembali ke step-3 untuk menghitung jarak masing-masing data terhadap centroid yang baru
Dilakukan secara berulang hingga diperoleh hasil cluster yang konsisten (data tidak berubah posisi clusternya)
Untuk menghitung jarak, dapat dilakukan dengan berbagai macam cara (method), beberapa rumus jarak yang biasa dipakai dalam analisis cluster diantaranya :

1. Jarak Eucledian

2. Jarak Manhattan

3. Jarak Mahalanobis

4. Jarak Pearson

5. Jarak Korelasi

6. Jarak Korelasi Mutlak

Dalam analisis k-means cluster, jarak yang paling sering dipakai adalah jarak Eucledian, namun hal ini bukan berarti jarak yang lain tidak dapat dipakai dalam analisis cluster, selain rumus jarak diatas juga masih banyak lagi rumus jarak yang lain yang dapat digunakan.

Tanpa banyak cerita, mari kita memulai simulasi perhitungan Cluster K-Means:

1. Clustering Process by using one variable

For example, I have the following data :

2, 9, 10, 1, 11, 8, 13, 7, 3, 6, 13, 7, 5, 7, 15, 14, 7, 15, 8, 4

From these, the first step is to determine the number of cluster (k)

Saya ingin mengelompokkan data tersebut kedalam 2 cluster (k=2)

Kemudian, setelah ditentukan jumlah clusternya, tentukan nilai centroid (initial centroid) pada cluster 1 dan cluster 2 berdasarkan data diatas. Misal saya pilih 6 sebagai centroid pada cluster 1 dan 13 sebagai centroid pada cluster 2.

C1 = 6
C2 = 13

Hitung jarak setiap data terhadap masing-masing cluster centroid, dalam hal ini saya ingin menggunakan rumus jarak Manhattan, kemudian pilih jarak terdekat/terkecil dari kedua centroid.

Proses perhitungannya adalah :

Misal untuk menghitung jarak data pertama terhadap C1 dan C2 adalah sebagai berikut :

| 2 – 6 | = 4 → Jarak dengan C1

| 2 – 13 | = 11 → Jarak dengan C2

Karena 4 < 11, maka jarak terdekat untuk data pertama adalah terhadap C1, dan seterusnya.

Sehingga diperoleh data sebagai berikut :

Data	C1	C2	Jarak C1	Jarak C2	Jarak Terdekat
2	6	13	4	11	1
9	6	13	3	4	1
10	6	13	4	3	2
1	6	13	5	12	1
11	6	13	5	2	2
8	6	13	2	5	1
13	6	13	7	0	2
7	6	13	1	6	1
3	6	13	3	10	1
6	6	13	0	7	1
13	6	13	7	0	2
7	6	13	1	6	1
5	6	13	1	8	1
7	6	13	1	6	1
15	6	13	9	2	2
14	6	13	8	1	2
7	6	13	1	6	1
15	6	13	9	2	2
8	6	13	2	5	1
4	6	13	2	9	1

Kemudian hitung kembali nilai centroid pada masing-masing cluster dengan cara menghitung rata-rata data setiap cluster yang terbentuk yakni menjumlahkan semua data pada masing-masing cluster dan membaginya dengan banyaknya data/anggota cluster. Cara ini dilakukan untuk menemukan nilai centroid yang konsisten, sehingga data cluster tidak berpindah dari satu cluster ke cluster yang lain.

Berdasarkan data diatas, diketahui bahwa data yang menjadi cluster 1 ada sebanyak 13 data, dan cluster 2 sebanyak 7 data, sehingga untuk menghitung nilai centroid baru dapat dilakukan dengan cara:

C1 = (2 + 9 + 1 + 8 + 7 + 3 + 6 + 7 + 5 + 7 + 7 + 8 + 4)/13 = 5,6923

C2 = (10 + 11 + 13 + 13 + 15 + 14 + 15)/7 = 13

Kemudian lakukan kembali langkah diatas (proses iterasi) untuk menghitung jarak terdekat dengan menggunakan nilai centroid yang baru seperti berikut :

Data	C1	C2	Jarak C1	Jarak C2	Jarak Terdekat
2	5,6923	13	3,6923	11	1
9	5,6923	13	3,3077	4	1
10	5,6923	13	4,3077	3	2
1	5,6923	13	4,6923	12	1
11	5,6923	13	5,3077	2	2
8	5,6923	13	2,3077	5	1
13	5,6923	13	7,3077	0	2
7	5,6923	13	1,3077	6	1
3	5,6923	13	2,6923	10	1
6	5,6923	13	0,3077	7	1
13	5,6923	13	7,3077	0	2
7	5,6923	13	1,3077	6	1
5	5,6923	13	0,6923	8	1
7	5,6923	13	1,3077	6	1
15	5,6923	13	9,3077	2	2
14	5,6923	13	8,3077	1	2
7	5,6923	13	1,3077	6	1
15	5,6923	13	9,3077	2	2
8	5,6923	13	2,3077	5	1
4	5,6923	13	1,6923	9	1

Berdasarkan hasil iterasi yang kedua, diketahui bahwa anggota cluster tidak mengalami perubahan (konsisten), sehingga proses iterasi berikutnya tidak diperlukan, karena hasil cluster sudah terbentuk yakni sebagai berikut :

Cluster	Anggota Cluster	Centroid
Cluster 1	1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 8, 8, 9	5,6923
Cluster 2	10, 11, 13, 13, 14, 15, 15	13

Berikut hasil perhitungan menggunakan program R :

2. Clustering Process by using 2 variables

For example, I have the following data :

No	X	Y
1	185	72
2	170	56
3	168	60
4	179	68
5	182	72
6	188	77

Tentukan nilai centroid awal (initial centroid)

Misal :

C1 = (170,56)

C2 = (188,77)

Hitung jarak masing-masing data terhadap centroid, dan pilih jarak terdekat data terhadap masing-masing centroid sehingga diperoleh tabel iterasi pertama sebagai berikut:

X	Y	C1		C2		Jarak 1	Jarak 2	Cluster Terdekat
185	72	169	58	183,5	72,25	21,26	1,52	2
170	56	169	58	183,5	72,25	2,24	21,13	1
168	60	169	58	183,5	72,25	2,24	19,76	1
179	68	169	58	183,5	72,25	14,14	6,19	2
182	72	169	58	183,5	72,25	19,10	1,52	2
188	77	169	58	183,5	72,25	26,87	6,54	2

Perhitungan jarak pada tabel di atas saya menggunakan jarak euclidian, adapun proses perhitungannya adalah sebagai berikut :

Misal untuk dataset pertama (185, 72), maka jarak euclidiannya adalah :

Jarak terahadap C1

Jarak terhadap C2

Kemudian hitung nilai centroid yang baru pada setiap cluster, dan diperoleh nilai centroid yang baru yakni :

C1 = (169, 58 )

C2 = (183.5, 72.25 )

Lakukan iterasi kedua:

X	Y	c1		c2		Jarak 1	Jarak 2	Cluster Terdekat
185	72	170	56	188	77	21,93	5,83	2
170	56	170	56	188	77	0,00	27,66	1
168	60	170	56	188	77	4,47	26,25	1
179	68	170	56	188	77	15,00	12,73	2
182	72	170	56	188	77	20,00	7,81	2
188	77	170	56	188	77	27,66	0,00	2

Karena anggota cluster tidak berpindah (konsisten), maka tidak perlu dilakukan proses iterasi ketiga, dan diperoleh hasil final cluster sebagai berikut :

Cluster	Data	Centroid
Cluster 1	(170, 56), (168, 60)	(169, 58)
Cluster 2	(185, 72), (179,68), (182,72), (188, 77)	(183.5, 72.5)

Berikut hasil perhitungan menggunakan program R:

3. Clustering Process by using 3 variables

For Example, I have the following data:

Objects	X	Y	Z
OB-1	1000	4	200
OB-2	2133	2	134
OB-3	2223	4	123
OB-4	1245	1	565
OB-5	3001	1	343
OB-6	1234	4	234
OB-7	2320	1	122
OB-8	1102	1	453

Choose randomly one of data as initial centroid

C1 = (1234, 4, 234)

C2 = (2320, 1, 122)

Calculate the distance between the initial centroid and determine the nearest distance :

First iteration process

Objects	X	Y	Z	Distance 1	Distance 2	Nearest Distance
OB-1	1000	4	200	268	1401	1
OB-2	2133	2	134	1001	200	2
OB-3	2223	4	123	1100	101	2
OB-4	1245	1	565	345	1518	1
OB-5	3001	1	343	1879	902	2
OB-6	1234	4	234	0	1201	1
OB-7	2320	1	122	1201	0	2
OB-8	1102	1	453	354	1549	1

The distance is caculated by using Manhattan distance :

For example:

Process of calculating distance of dataset 1 with C1

| 1000 - 1234 | + | 4 - 4 | + | 200 - 234 | = 268

Process of calculating distance of dataset 1 with C2

| 1000 - 2320 | + | 4 - 1 | + | 200 - 122 | = 1401

Second iteration process

Objects	X	Y	Z	Distance 1	Distance 2	Nearest Distance
OB-1	1000	4	200	309,75	1440,75	1
OB-2	2133	2	134	1217,25	332,75	2
OB-3	2223	4	123	1319,25	255,75	2
OB-4	1245	1	565	303,25	1559,75	1
OB-5	3001	1	343	1877,25	745,25	2
OB-6	1234	4	234	219,25	1240,75	1
OB-7	2320	1	122	1417,25	158,75	2
OB-8	1102	1	453	134,75	1590,75	1