Nama : I Wayan Pio PratamaNim : 1208605033

Algoritma Hybrid GA K-Means Clustering

ClusteringProses pengelompokan sekumpulan obyek kedalam kelas-kelas obyek yang sama disebut clustering / pengelompokan. Pengklasteran merupakan satu dari sekian banyak fungsi proses data mining untuk menemukan kelompok atau identifikasi kelompok obyek yang hampir sama. Analisis kluster (Clustering) merupakan usaha untuk mengidentifikasi kelompok obyek yang mirip-mirip dan membantu menemukan pola penyebaran dan pola hubungan dalam sekumpulan data yang besar. William ([8]) membagi algoritma clustering ke dalam kelompok besarseperti berikut:1. Partitioning algorithms: algoritma dalam kelompok ini membentuk bermacam partisi dan kemudian mengevaluasinya dengan berdasarkan beberapa kriteria.2. Hierarchy algorithms: pembentukan dekomposisi hirarki dari sekumpulan data menggunakan beberapa kriteria.3. Densitybased: pembentukan cluster berdasarkan pada koneksi dan fungsi densitas.4. Gridbased: pembentukan cluster berdasarkan pada struktur multiplelevel granularity5. Modelbased: sebuah model dianggap sebagai hipotesa untuk masing-masing cluster dan model yang baik dipilih diantara model hipotesa tersebut.Algoritma K-Means K-means merupakan salah satu metode data klustering non hirarki yang berusaha mempartisi data yang ada ke dalam bentuk satu atau lebih cluster / kelompok.Adapun K-Means clustering memiliki keuntungan sebagai berikut : Cukup efisien dari sudut pandang kompleksitas yakni O(tkn), dengan n adalah banyak data, t merupakan banyaknya iterasi, dan k adalah jumlah cluster yang terbentuk. Cukup mudah digunakan.Namun kelemahan dari algoritma ini adalah : Sangat bergantung pada pemilihan centroid awal Sering terjebak pada local optimum Hanya bekerja pada tipe data numerikAdapun algorimat K-Means adalah sebagai berikut :

Atau dalam bentuk list sebagai berikut :1. Tentukan centroid secara random2. Hitung jarak masing-masing titik ke centroid menggunakan rumus ecludean

3. Kelompokan objek berdasarkan jarak terdekat4. Tentukan centroid kembali dengan cara menghitung rata-rata kluster yang baru.5. Jika centroid tersebut tidak berubah maka proses berhenti, jika tidak ulangi langkah 2 sampai 4.Contoh :Lakukan clustering untuk data sebagai berikut, dengan jumlah cluster sebanyak 2 buah.

Centroid awal dipilih secara random yakni (10,10) dan (8,20). Setelah dihitung jarak setiap titik terhadap centroid, yakni sebagai berikut untuk contoh row data pertama dan kedua terhadap centroid (10,10) :

Tentukan jarak d untuk semua data nilai (x, y) terhadap titik centroid (10,10) dan centroid (8,20). Sehingga didapat table sebagai berikut.

Perhatikan data yang dicetak tebal di iterasi 1 yang merupakan hasil cluster adalah data ke 1, 2, 5 yang masuk ke centroid 1 dan data objek ke 3,4,6 masuk ke centroid 2. Nah untuk cluster (1, 2, 5) maka akan dihitung rata-rata nya sebagai berikut :

Jadi (12, 11.3) menjadi centroid yang baru untuk iterasi 2.Untuk cluster (3, 4, 6) juga dihitung rata-ratanya sehingga diperoleh centroid 2 yang baru yakni (18, 22.6). ulangi langkah pada iterasi 1 sehingga didapat table diatas. Sampai pada iterasi 2 diperoleh center yang baru yakni (11, 13.5) dan (23, 24), dan pada center 3 jika dihitung centernya juga akan memiliki nilai yang sama seperti center yang dihasilkan pada iterasi 2, jadi iterasi akan dihentikan dengan hasil cluster data (1, 2, 4, 5) dan (3, 6) karena center sudah tidak bergeser.Kelemahan K-Means clustering adalah pada kemungkinan terjebaknya pada local optimum, untuk itu K-Means clustering akan di hybrid dengan evolutionary metode GA(Genetic Algorithm). Dengan menggabungkan metode genetika diharapkan memperoleh centroid yang lebih baik sehingga local optimum dapat diminimalisir walaupun akan mengorbankan pada sisi kompleksitas.Sebelum melangkah lebih jauh ada baiknya saya akan coba menjelaskan kembali metode genetika secara umum : Representasi individu dan inisialisasi populasi Hitung nilai fitness Seleksi Cross Over MutasiSaya akan coba langsung jelaskan pada contoh untuk masing-masing langkah :

Pada tahap ini terdapat inisialisasi kromosom yang didapat dengan cara random terhadap data objek yang kita punya.Sehingga pada initial kromosom dipilih random dari objek 1, 3, 5, dan 1 kembali seperti table dibawah.

Kemudian lakukan proses seperti pada K-Means clustering, akan saya contohkan untuk centroid (10,10) dan (20,12)

Jika dihitung hasil centroid yang dihasilkan dari iterasi 1 dan 2 akan sama sehingga proses K-Means dihentikan diperoleh centroid baru (8, 14) dan (22, 20). Kemudian bisa kita hitung nilai finess nya adalah . Lakukan pula untuk setiap centroid yang lain. Hasil lengkapnya diperoleh sebagai berikut :

Kemudian akan dilakukan proses cross over dimana dalam melakukan cross over digunakan one cut point cross over yakni dengan memilih bilangan random antara 1 sampai 4 sesuai jumlah gen yang terdapat pada kromosom. Misalkan diperoleh bilangan random = 3, maka yang akan dicross adalah gen pada posisi Xcen2 dan Ycen2. Sehingga didapat hasil sebagai berikut :

Kemudian dilakukan proses mutasi dengan persamaan v=v, dimana bilangan random antara [0 1], dengan v adalah nilai pada gen tertentu yang dipilih secara random. Sehingga diperoleh table sebagai berikut :

Lalu lakukan lagi proses yang sama seperti proses awal.

Lakukan lagi proses cross over dan mutasi dan hitung kembali nilai fitnessnya, Sampai akhirnya diperoleh hasil sebagai berikut ;

Sampai disini proses berhenti karena nilai fitness sudah minimum pada centroid (8, 14) dan (22, 20). Dengan centroid ini diperoleh kluster sebagai berikut : (1, 4, 5) dan (2, 3, 4).