Clustering

Clustering atau klasterisasi adalah metode pengelompokan data. Menurut Tan, 2006 clustering adalah sebuah proses untuk mengelompokan data ke dalam beberapa cluster atau kelompok sehingga data dalam satu cluster memiliki tingkat kemiripan yang maksimum dan data antar cluster memiliki kemiripan yang minimum.

K-means

K-Means termasuk dalam partitioning clustering yaitu setiap data harus masuk dalam cluster tertentu dan memungkinkan bagi setiap data yang termasuk dalam cluster tertentu pada suatu tahapan proses, pada tahapan berikutnya berpindah ke cluster yang lain. K-Means memisahkan data ke "k" daerah bagian yang terpisah, dimana "k" adalah bilangan integer positif

Algoritma K-Means sangat terkenal karena kemudahan dan juga serta kemampuannya untuk mengklasifikasi data besar dan outlier dengan sangat cepat.

Dan berikut ini adalah langkah-langkah algoritma K-Means :

1. Penentuan pusat cluster awal

   Dalam menentukan "n" buah pusat cluster awal, dilakukan pembangkitan bilangan acak atau random yang merepresentasikan urutan data input.

   Pusat awal cluster didapatkan dari data itu sendiri, bukan dengan menentukan titik baru, yaitu dengan me-random pusat awal dari data

2. Perhitungan jarak dengan pusat cluster

   Untuk mengukur jarak antara data dengan pusat cluster digunakan Euclidian distance. Algoritma perhitungan jarak data dengan pusat cluster

   1. Ambil nilai data dan nilai pusat cluster
   2. Hitung Euclidian distance data dengan tiap pusat cluster

3. Pengelompokkan data

   Jarak hasil perhitungan akan dilakukan perbandingan dan dipilih jarak terdekat antara data dengan pusat cluster, jarak ini menunjukkan bahwa data tersebut berada dalam satu kelompok dengan pusat cluster terdekat.

   Algoritma pengelompokkan data :

   1. Ambil nilai jarak tiap pusat cluster dengan data
   2. Cari nilai jarak terkecil
   3. Kelompokkan data dengan pusat cluster yang memiliki jarak terkecil

4. Penentuan pusat cluster baru

   Untuk mendapatkan pusat cluster baru bisa dihitung dari rata-rata nilai anggota cluster dan pusat cluster. Pusat cluster yang baru digunakan untuk melakukan iterasi selanjutnya, jika hasil yang didapatkan belum konvergen. Proses iterasi akan berhenti jika telah memenuhi maksimum iterasi yang dimasukkan oleh User atau hasil yang dicapai sudah konvergen (pusat cluster baru sama dengan pusat cluster lama).

   Algoritma penentuan pusat cluster baru :

   1. Cari jumlah anggota tiap cluster
   2. Hitung pusat baru dengan rumus :
      Pusat cluster baru :
      
      Dimana :
      x1, x2, x3, ...xn = anggota cluster
      xp = pusat lama

 

Contoh perhitungan algoritma k-means clustering

Berikut ini adalah uraian dari Implementasi Data Mining Dengan Algoritma K-Means Clustering dalam pengelompokan data

Berikut Contoh Kasus nya:
Diambil 12 alternatif saja sebagai contoh. Percobaan dilakukan dengan menggunakan parameter-parameter sebagai berikut :

1. Jumlah cluster : 2
2. Jumlah data : 12
3. Jumlah atribut : 8

Menentukkan kriteria yang nantinya digunakan sebagai parameter nilai buat masing-masing alternatif, dengan kriteria nya sebagai berikut :

1. P1 = Pedagodik
2. P2 = Kepribadian
3. P3 = Sosial
4. P4 = Profesional
5. P5 = Kehadiran
6. P6 = Disiplin
7. P7 = Kerajinan
8. P8 = IQ

Iterasi ke-1

1. Penentuan pusat awal cluster
   Untuk penentuan awal pusat cluster di asumsikan sebagai berikut :

   Diambil data ke - 2 sebagai pusat Cluster Ke - 1 :
   C1 = 84; 76; 79; 77; 76; 77; 75; 81
   
   Diambil data ke - 5 sebagai pusat Cluster Ke - 2 :
   C2 = 82; 82; 81; 91; 90; 82; 79; 91

2. Perhitungan matrix jarak pusat cluster
   Untuk mengukur jarak antara data dengan pusat cluster digunakan Euclidian distance, kemudian akan didapatkan matrik jarak sebagai berikut :

   Rumus Euclidian distance :

   
   Dimana :
   x = pusat cluster
   y = data
   
   Sebagai contoh, perhitungan jarak ke A-1 terhadap pusat cluster adalah :
   
   
   Dan seterusnya dilanjutkan untuk data ke 2, 3, ... n

   Kemudian akan didapatkan matrik jarak sebagai berikut :

   D¹ =

   A-1	A-2	A-3	A-4	A-5	A-6	A-7	A-8	A-9	A-10	A-11	A-12
   10.44	0	24.15	14.18	24.02	15.65	16.46	11.87	11.14	6.86	12.29	6.56	C1
   21.73	24.02	14.56	26.04	0	28.81	22.14	26.23	22.47	27.09	25.85	22.98	C2

   Setiap kolom pada matrik menunjukkan nilai jarak data terhadap pusat cluster. Baris pertama pada matrik menunjukkan nilai jarak data terhadap titik pusat cluster pertama, baris kedua pada matrik menunjukkan nilai jarak data terhadap titik pusat cluster kedua dan seterusnya.

3. Matrix Pengelompokkan data
   

   Jarak hasil perhitungan akan dilakukan perbandingan dan dipilih jarak terdekat antara data dengan pusat cluster, jarak ini menunjukkan bahwa data tersebut berada dalam satu kelompok dengan pusat cluster terdekat.

   Berikut hasil matriks pengelompokkan group, nilai 1 berarti data tersebut berada dalam group.

   G¹ =

   A-1	A-2	A-3	A-4	A-5	A-6	A-7	A-8	A-9	A-10	A-11	A-12
   1	1	0	1	0	1	1	1	1	1	1	1	C1
   0	0	1	0	1	0	0	0	0	0	0	0	C2

    

   Dan dari hasil matrix pengelompokkan itu kita mendapatkan pembagain kelompok alternatif sebagai berikut :

   No.	NIP	Nama	Hasil
   1.	A-1	Hendra Setiawan	Berada pada kelompok : C1
   2.	A-2	Roni Purba	Berada pada kelompok : C1
   3.	A-3	Joni Darmawan	Berada pada kelompok : C2
   4.	A-4	Dewi Roslina	Berada pada kelompok : C1
   5.	A-5	Haris Siregar	Berada pada kelompok : C2
   6.	A-6	Indra Wijaya	Berada pada kelompok : C1
   7.	A-7	Yuyun Sundari	Berada pada kelompok : C1
   8.	A-8	Safrizal	Berada pada kelompok : C1
   9.	A-9	Gilang Ramadhan	Berada pada kelompok : C1
   10.	A-10	Kiki Angreni	Berada pada kelompok : C1
   11.	A-11	Sandra Wahyuni	Berada pada kelompok : C1
   12.	A-12	Robert Sitorus	Berada pada kelompok : C1

4. Penentuan pusat cluster baru
   

   Setelah diketahui anggota tiap-tiap cluster, kemudian pusat cluster baru dihitung berdasarkan data anggota tiap-tiap cluster sesuai dengan rumus pusat anggota cluster.

   Karena C1 memiliki 10 anggota maka cluster baru untuk C1 menjadi :
   C1 = (78.5; 76.2; 75.3; 79.9; 76.9; 78.4; 76.4; 78.6)

   Dan begitu juga untuk C2. Karena C2 hanya mempunyai 2 anggota, maka cluster baru untuk C2 menjadi :
   C2 = (79.5; 83; 79.5; 88; 91; 85.5; 78; 86.5)

Iterasi ke-2

1. Untuk proses Iterasi ke-2, ulangi lagi langkah ke 2 (kedua) seperti Iterasi Ke-1 yaitu untuk mencari perhitungan matrix jarak pusat cluster hingga posisi data tidak mengalami perubahan, dan untuk Iterasi ke-2 matrix jarak pusat cluster nya menjadi seperti ini :

   D² =
   

   A-1	A-2	A-3	A-4	A-5	A-6	A-7	A-8	A-9	A-10	A-11	A-12
   5.5	7.9	21.1	14.08	23.3	9	10.6	6.7	5.1	5.6	10	3.4	C2
   20.5	22.9	7.2	23.13	7.2	26.6	19.5	23.3	19.8	24.9	23.8	21	C1

   Langkah selanjutnya sama dengan langkah pada nomer 3 iterasi ke-1 diatas, jarak hasil perhitungan akan dilakukan perbandingan dan dipilih jarak terdekat antara data dengan pusat cluster, jarak ini menunjukkan bahwa data tersebut berada dalam satu kelompok dengan pusat cluster terdekat

   Berikut ini akan ditampilkan data matriks pengelompokkan group, nilai 1 berarti data tersebut berada dalam group.

   G² =
   

   A-1	A-2	A-3	A-4	A-5	A-6	A-7	A-8	A-9	A-10	A-11	A-12
   1	1	0	1	0	1	1	1	1	1	1	1	C1
   0	0	1	0	1	0	0	0	0	0	0	0	C2

    

   Dan dari hasil matrix pengelompokkan itu kita mendapatkan pembagain kelompok alternatif sebagai berikut :

   No.	NIP	Nama	Hasil
   1.	A-1	Hendra Setiawan	Berada pada kelompok : C1
   2.	A-2	Roni Purba	Berada pada kelompok : C1
   3.	A-3	Joni Darmawan	Berada pada kelompok : C2
   4.	A-4	Dewi Roslina	Berada pada kelompok : C1
   5.	A-5	Haris Siregar	Berada pada kelompok : C2
   6.	A-6	Indra Wijaya	Berada pada kelompok : C1
   7.	A-7	Yuyun Sundari	Berada pada kelompok : C1
   8.	A-8	Safrizal	Berada pada kelompok : C1
   9.	A-9	Gilang Ramadhan	Berada pada kelompok : C1
   10.	A-10	Kiki Angreni	Berada pada kelompok : C1
   11.	A-11	Sandra Wahyuni	Berada pada kelompok : C1
   12.	A-12	Robert Sitorus	Berada pada kelompok : C1

   Karena G² = G¹ atau pengelompokkan group iterasi ke-1 dan iterasi ke-2 memiliki anggota yang sama maka tidak perlu dilakukan iterasi/perulangan lagi. Hasil clustering telah mencapai stabil dan konvergen.

   Begitulah perhitungan Data Mining Menggunakkan Algoritma K-Means Clustering Untuk Mengelompokkan Data ..

Screenshot Program

Page : Pengisian Nilai Alternatif

 

Page : Penentuan Pusat Cluster Untuk Melakukan Proses Iterasi

 

Page : Proses Pengulangan Iterasi Sampai Memperoleh Kesamaan Kelompok Cluster