BAB I
1
PENDAHULUAN
1.1 Latar Belakang Masalah Clustering merupakan sebuah teknik pemrosesan data yang digunakan untuk menemukan pola-pola tersembunyi pada kumpulan data (Žalik, 2008). Clustering telah banyak diaplikasikan dalam berbagai bidang antara lain penambangan data, pengenalan pola, pengambilan keputusan, machine learning, dan segmentasi citra (Yi dan Yang, 2010). Proses penemuan pola data dilakukan dengan mengelompokkan data ke dalam klaster-klaster sehingga data-data yang memiliki kemiripan berada pada klaster yang sama dan data-data yang tidak memiliki kemiripan terletak pada klaster yang berbeda (Hasan dan Ramakrishnan, 2011). Salah satu cara untuk mengetahui tingkat kemiripan data adalah melalui perhitungan jarak antara data. Semakin kecil jarak antar data maka semakin tinggi tingkat kemiripan data tersebut dan sebaliknya semakin besar jarak antar data maka semakin rendah tingkat kemiripannya. K-means dan variannya merupakan jenis algoritma clustering partitionbased yang telah banyak digunakan dalam clustering data (Jain dan Lansing, 2010). K-means mengelompokkan kumpulan data ke dalam k klaster berdasarkan jarak terdekat antara data dengan pusat klaster (Žalik, 2008). Kelebihan dari algoritma K-means terletak pada kecepatan untuk mencapai konvergen serta kemudahan dalam pengimplementasian (Kao dan Lee, 2009). Pada sisi lain, algoritma K-means memiliki beberapa kelemahan seperti: (i) kecenderungan mengalami konvergensi prematur pada quantization error yang besar (van der Merwe dan Engelbrecht, 2003); (ii) hasil clustering yang sangat bergantung pada penentuan pusat klaster awal (Kao et al., 2008;Ye dan Chen, 2005); serta (iii) mengalami masalah dead-unit (Žalik, 2008).
12
13 Particle Swarm Optimization (PSO) merupakan jenis algoritma evolusi yang terinspirasi dari kawanan burung dan kawanan ikan (Eberhart dan Kennedy, 1995). Walaupun pada awalnya metode PSO dibuat untuk penyelesaian masalah optimasi, beberapa tahun terakhir metode PSO telah banyak diaplikasikan untuk memecahkan berbagai masalah yang berkaitan dengan clustering (Shen et al., 2010) . Hal ini disebabkan karena PSO mampu memberikan hasil clustering yang lebih stabil karena tidak adanya ketergantungan pada inisialisai pusat klaster awal (Hasan dan Ramakrishnan, 2011). Tetapi PSO juga memiliki kelemahan pada kecepatan konvergensinya yang cenderung lambat saat mendekati solusi optimum (Ahmadyfard dan Modares, 2008). Penerapan PSO pada clustering data pertama kali dilakukan oleh Van der Merwe dan Engelbrecht (2003). Proses clustering mula-mula dilakukan dengan K-means yang kemudian dilanjutkan oleh PSO. Hasil clustering dari metode Kmeans digunakan sebagai salah satu partikel awal pada metode PSO. Penggunaan hasil clustering K-means sebagai salah satu partikel awal PSO ternyata mampu meningkatkan performansi dari PSO clustering. Variasi lain dari Particle Swarm Optimization untuk melakukan clustering data adalah Particle Swarm Clustering (PSC) (Cohen dan Castro, 2006). Berbeda dari metode PSO yang merepresentasikan setiap partikel sebagai satu himpunan pusat klaster, pada PSC setiap partikelnya cukup merepresentasikan satu pusat klaster saja. Sehingga solusi akhir klaster-klaster dari pendekatan PSC diperoleh dengan menggabungkan keseluruhan partikel yang ada. Hasil penelitian ini menunjukkan bahwa performansi metode PSC lebih unggul dibandingkan dengan K-means karena PSC dapat terhindar dari stagnasi. Modified PSC (mPSC) merupakan metode yang diusulkan oleh Szabo et al. (2010) yang bertujuan untuk mempercepat kecepatan komputasi metode PSC. Metode mPSC mengusulkan ide mengganti velocity (V)
dengan Δx, untuk
mengeliminasi kebutuhan akan bobot inersia (ω). Dengan demikian, metode mPSC terbukti memiliki waktu komputasi yang sedikit lebih cepat dibandingkan
14 dengan PSC. Yuwono et al. (2012) mengusulkan metode yang dapat meningkatkan kinerja PSC dan mPSC bernama Rapid Centroid Estimation (RCE). RCE memodifikasi metode mPSC pada bagian frekuensi pembaruan posisi partikel, frekuensi pembaruan matriks jarak (partikel dan titik data) dan partikel terbaik, dan menambahkan global minimum computation untuk penyimpanan kombinasi posisi partikel terbaik. Metode RCE melakukan clustering dengan waktu komputasi yang jauh lebih cepat dibandingkan dengan kedua metode sebelumnya tanpa mempengaruhi kualitas skema clustering. Namun demikian, dibandingkan dengan PSC dan mPSC, standar deviasi kualitas skema clustering yang dihasilkan dari RCE lebih tinggi walaupun rata-rata hasil clustering RCE lebih unggul. Yuwono et al. (2012) menduga bahwa hal tersebut terjadi karena penentuan kriteria berhenti yang didasarkan pada tercapainya equilibrium state adalah kriteria berhenti yang kurang tepat. Equilibrium state merupakan keadaan dimana partikel sudah mencapai posisi terbaik yang diketahui melalui nilai fungsi fitness partikel. Pada penilitian ini digunakan metode clustering RCE-Kmeans. K-means akan dijadikan metode yang mendefinisikan kembali equilibrium state dari metode clustering RCE. Oleh karena itu, posisi partikel akhir yang merepresentasikan pusat klaster diperoleh setelah penerapan metode K-means. Kmeans dipilih karena memiliki kemampuan local search (Naik et al., 2012), yaitu kemampuan menemukan solusi optimum yang berada di sekitar nilai solusi awal yang didefinisikan. Kemampuan local search yang dimiliki K-means dibutuhkan karena kemampuan local search menjamin penemuan solusi optimum (posisi partikel optimum) di sekitar nilai solusi awal (posisi partikel berdasarkan equilibrium state RCE) bukan mencari ruang solusi baru yang memungkinkan diperoleh hasil clustering yang tidak lebih baik dari yang dihasilkan oleh RCE. Kmeans juga memiliki kelebihan pada kecepatan konvergensinya sehingga diharapkan penggunaan metode K-means untuk menemukan posisi partikel
15 optimum dari metode RCE tidak menambah waktu komputasi secara signifikan. Dengan demikian, penggunaan metode K-means dalam penentuan posisi partikel akhir metode RCE mampu menghasilkan posisi partikel yang dapat meningkatkan kualitas skema hasil clustering dan mampu memperkecil pengaruh equlibrium state terhadap kualitas skema clustering yang dilihat dari nilai standar deviasi kualitas skema clustering. 1.2 Rumusan Masalah Berdasarkan uraian latar belakang yang telah dipaparkan sebelumnya maka rumusan masalah yang akan diteliti adalah 1. Bagaimana meningkatkan kualitas hasil clustering dengan memperbaiki pusat klaster untuk mencari klaster yang padat ? 2. Bagaimana pengaruh penerapan K-means untuk menentukan pusat klaster akhir dari RCE dilihat dari variansi hasil clustering ? 1.3
Batasan Masalah Batasan masalah dari penelitian ini adalah 1. Jumlah partikel dan jumlah klaster yang akan dibangkitkan disesuaikan dengan jumlah kelas dataset. 2. Bobot inersia yang digunakan pada RCE sebasar 0.9 dengan decay rate sebesar 0.95. 3. Dataset diambil dari UCI Machine Learning Repository. Dataset tersebut adalah Iris, Wine, Glass, Dermatology, WDBC, CMC, Yeast, Texture, Optical Digits, Thyroid.
16 1.4 Keaslian Penelitian Berdasarkan beberapa studi pustaka yang telah dibaca dan ditinjau, penelitian mengenai clustering masih memiliki banyak pertanyaan yang dapat dikembangkan solusinya, diantaranya dengan melakukan penggabungan metode optimasi dan metode clustering seperti PSO dan K-means. Penggabungan metode Rapid Centroid Estimation (RCE) dan K-means belum pernah dilakukan. Beberapa penelitian lainnya yang telah melakukan penggabungan metode varian Particle Swarm Optimization (PSO) dengan K-means akan dipaparkan pada tinjauan pustaka. 1.5 Tujuan Penelitian Adapun tujuan penelitian yang ingin dicapai adalah sebagai berikut 1. Meningkatkan kualitas hasil clustering dengan memperbaiki pusat klaster untuk mencari klaster yang padat. 2. Mengevaluasi pengaruh penerapan metode K-means untuk menentukan pusat klaster akhir metode RCE dengan melihat variansi hasil clustering. 1.6 Manfaat Penelitian Penelitian ini diharapkan memberikan manfaat sebagai berikut 1. Dapat menjadi salah satu alternatif metode clustering data. 2. Dapat memberikan kontribusi pada bidang clustering khususnya yang memanfaatkan algoritma dari bidang swarm intelligence. 1.7 Metodologi Penelitian Tahapan yang dilakukan dalam penelitian ini adalah sebagai berikut : 1. Studi Literatur Pada tahapan ini dilakukan pembacaan paper dan buku yang terkait dengan topik penelitian dan masalah yang diangkat dan juga dilakukan penulisan resensi untuk paper yang mengangkat kasus serupa. Paper-paper dan buku yang dibaca adalah yang membahas mengenai metode Particle Swarm Optimization serta pemanfaatan algoritma yang tergolong dalam
17 swarm intelligence khususnya Particle Swarm Optimization untuk memecahkan masalah clustering. 2. Perancangan Metode Clustering Pada tahap ini dilakukan perancang metode clustering RCE-Kmeans untuk melakukan clustering data. 3. Implementasi Metode Clustering Pada tahap ini dilakukan pengimplementasian rancangan metode clustering yang diusulkan ke dalam baris program. Program hasil pengimplementasian metode yang diusulkan tersebut kemudian digunakan untuk melakukan clustering pada pada dataset yang diperoleh dari UCI Machine Learning Dataset. Proses clustering akan dilakukan sebanyak 50 kali untuk masing-masing dataset dan masing-masing metode clustering yang berbeda. 4. Pengujian Metode Clustering Pada tahap pengujian, setiap algoritma clustering yaitu RCE, K-means, dan algoritma clustering yang diusulkan dibandingkan kualitas skema clusteringnya menggunakan alat ukur Overall Entropy, Overall Purity, Overall Percentage Misclassification, serta waktu eksekusinya. Overall Entropy, Overall Purity, Overall Percentage Misclassification dihitung sebanyak jumlah percobaan clustering yang dilakukan untuk setiap dataset yaitu sebanyak 50 kali percobaan. 5. Analisa hasil Clustering Pada tahap ini dilakukan perbandingan kualitas skema clustering dari metode yang diajukan dengan metode K-means dan RCE. Kemudian akan dilakukan analisa terhadap hasil pengukuran kualitas skema clustering untuk masing-masing dataset.
18 6. Penarikan Kesimpulan Pada tahap ini dilakukan penarikan kesimpulan untuk menjawab rumusan masalah penelitian dan memenuhi tujuan penelitian yang telah dijabarkan. Kesimpulan diperoleh dari analisa kualitas skema clustering yang dilakukan. 1.8 Sistematika Penulisan Tesis ini berisi 7 (tujuh) bab dengan rincian masing-masing bab sebagai berikut : Bab I Pendahuluan Bab ini berisikan uraian singkat tentang latar belakang penelitian, rumusan masalah, batasan masalah, keaslian penelitian, tujuan penelitian, manfaat penelitian, metodologi penelitian, dan sistematika penulisan. Bab II Tinjauan Pustaka Bab ini berisi uraian penelitian-penelitian serupa yang sudah pernah dilakukan dan dijadikan referensi dalam penelitian ini. Bab III Landasan Teori Bab ini berisi uraian teori-teori dasar yang berkaitan dengan metodemetode yang digunakan dalam penelitian ini. Metode-metode tersebut antara lain : K-means, PSO, PSC, mPSC, dan RCE. Bab IV Analisis dan Perancangan Bab ini berisi analisa terhadap metode clustering RCE yang merupakan varian dari Particle Swarm Optimization yang dikhususkan untuk memecahkan masalah clustering dimana metode K-means akan digunakan dalam penentuan posisi partikel akhir dari RCE untuk mendapatkan hasil clustering yang lebih stabil. Perancangan yang diuraikan adalah perancangan metode clustering, antarmuka sistem, dan perancangan pengujian sistem.
19 Bab V Implementasi Bab ini berisi implementasi metode clustering dari hasil analisis dan hasil perancangan yang telah dilakukan. Bab VI Hasil dan Pembahasan Bab ini berisi hasil clustering yang diperoleh, analisis hasil clustering, dan analisis perbandingan kualitas hasil clustering dari metode K-means, RCE, dan RCE-Kmeans. Bab VII Penutup Bab ini berisi Kesimpulan hasil penelitian dan saran untuk penelitian lebih lanjut.
