Pengelompokan dokumen berbasis algoritma genetika

Abstract

Pengelompokan (clustering) merupakan sebuah metode untuk menggabungkan himpunan objek ke dalam kelompok-kelompok sedemikan rupa sehingga objek dalam kelompok (cluster) lebih mirip (karena suatu hal) satu sama lain daripada objek di kelompok lain [1]. Document clustering (pengelompokan dokumen) merupakan proses pengelompokan yang dilakukan terhadap suatu koleksi dokumen. Pengelompokan dokumen diterapkan dalam beberapa bidang seperti penambangan web, mesin pencari (search engine), dan temu kembali informasi (information retrieval) [3]. Hal yang dilakukan dalam pengelompokan dokumen adalah mengukur kemiripan (similarity) antar dokumen dan mengelompokan dokumen yang serupa. Salah satu algoritma pengelompokan yang paling sering digunakan adalah K-means. Namun, algoritma K-means memiliki kekurangan yaitu dapat terjebak dalam local optimum. Local optimum adalah suatu solusi yang optimal (baik maksimal maupun minimal) diantara kandidat solusi yang berdekatan dalam masalah optimasi. Dikatakan lokal karena solusi ini hanya optimal apabila dibandingkan dengan kandidat solusi yang berdekatan, tidak optimal secara keseluruhan (global optimum). Algoritma genetika atau biasa disebut Genetic Algorithm (GA) adalah suatu algoritma pencarian yang terinspirasi dari proses seleksi alam yang terjadi secara alami dalam proses evolusi. GA merupakan metode penyelesaian masalah yang menggunakan genetika sebagai pemodelannya. Dalam penelitian ini, GA akan digunakan sebagai solusi dari masalah local optimum. Local optimum dapat diatasi oleh GA yang sudah terbukti efektif dalam masalah pencarian dan optimasi. GA dapat digunakan untuk mengelompokkan dokumen dengan beberapa adaptasi terhadap representasi kromosom, fungsi fitness, seleksi, persilangan, dan mutasi. Algoritma genetika dan algoritma K-means diuji menggunakan suatu dataset berlabel untuk membandingkan waktu dan hasil pengelompokan dari kedua algoritma tersebut. Berdasarkan hasil eksperimen menggunakan dataset dalam penelitian ini, rata-rata nilai purity dari hasil pengelompokan menggunakan algoritma genetika adalah sebesar 0.799, lebih baik 56% dibandingkan dengan menggunakan algoritma K-means. Hal ini membuktikan bahwa algoritma genetika sudah dapat mengelompokan dokumen dengan hasil yang memuaskan. Namun dari segi waktu, algoritma genetika membutuhkan waktu 4365% lebih lama dibandingkan dengan algoritma K-means. Hal ini disebabkan oleh proses komputasi yang dilakukan pada algoritma genetika jauh lebih banyak dan kompleks dibandingkan dengan algoritma K-means.