Ujian Tugas Akhir Laboratorium Sistem Pendukung Keputusan dan Business Intelligence
PENERAPAN METODE GA-KMEANS UNTUK PENGELOMPOKAN PENGGUNA PADA BADAN PERPUSTAKAAN DAN KEARSIPAN (BAPERSIP) PROVINSI JAWA TIMUR Ferlyna K Wardhani 5208100130
Dosen Pembimbing I: Erma Suryani, S.T., M.T., Ph.D Dosen Pembimbing II: Ahmad Mukhlason, S.Kom, M.Sc
Latar Belakang Rendahnya tingkat kesadaran minat baca masyarakat Surabaya • Berdasarkan penelitian Bapersip dan sebuah lembaga survey hanya sebanyak 54% warga Surabaya membaca kurang dari tiga buah buku dalam sebulan (Humas Pemkot Surabaya, 2011). • Dari 3.024.321 warga Surabaya hanya tercatat sebanyak lebih dari 40000 orang anggota Bapersip, dengan rata-rata jumlah kunjungan mencapai 100-175 per hari, namun jumlah aktifitas peminjaman dari pelayanan sirkulasi Bapersip dari hari senin-jumat hanya sekitar 165 buku/ hari (Bapersip, 2010) • Dapat disimpulkan, perbandingan jumlah penduduk dengan jumlah pengguna yang terdaftar pada Bapersip hanya sebesar 1:73.
Rumusan Masalah •
• •
•
Bagaimana melakukan praproses data untuk menghasilkan pengelompokan pengguna berdasarkan data informasi personal pengguna, data histori transaksi peminjaman buku. Bagaimana menggunakan algoritma klasterisasi GA-Kmeans untuk melakukan pengelompokan pengguna. Bagaimana melakukan analisis untuk menghasilkan rekomendasi berupa kategori buku yang tepat bagi tiap-tiap kelas pengguna berdasarkan hasil pengelompokan ke dalam klaster. Bagaimana mengukur kinerja algoritma GA-Kmeans.
Visi Bapersip : “Jawa Timur Membaca dan Tertib Arsip 2012” Tingkat minat baca masyarakat Surabaya yang masih rendah
Layanan Bapersip yang kurang spesifik kepada kebutuhan pengguna
Bagaimana meningkatkan minat baca masyarakat??
Marketing perpustakaan
Segmentasi pengguna Bapersip Surabaya
Analisis rekomendasi buku bagi pengguna Bapersip yang sesuai dengan karakteristik pengguna
Batasan •
•
• •
Data yang digunakan : data pada Bapersip pada tahun 2009 – 2012, terbatas pada buku saja, tidak mencakup koleksi lainnya dan data kearsipan. Pengelompokan mempertimbangkan data informasi anggota (berupa gender, umur, profesi, dsb), data informasi kepustakaan/ buku (berupa subject buku, pengarang, penerbit, dsb), serta historis transaksi peminjaman buku. Software MATLAB digunakan untuk membantu proses klasterisasi dan analisis data. Output : kelompok-kelompok (klaster-klaster) pengguna dan karakteristiknya serta analisis rekomendasi kategori buku yang sesuai dengan klaster pengguna.
Tujuan menerapkan metode klasterisasi GA-Kmeans untuk pengelompokan pengguna Bapersip Provinsi Jawa Timur untuk menghasilkan analisis rekomendasi kategori buku yang sesuai dengan karakteristik pengguna (berdasarkan transaksi peminjaman, informasi pengguna, serta informasi buku) pada setiap klaster.
Manfaat • •
Meningkatkan jumlah peminjaman buku pada tiap transaksinya di Bapersip Jawa Timur. Menghasilkan rekomendasi buku yang sesuai dengan karakteristik pengguna.
Sekilas Bapersip Jawa Timur Bapersip Jawa Timur •
Bapersip Provinsi Jawa Timur merupakan lembaga yang dibentuk sebagai salah satu pelaksana kebijakan daerah dalam melaksanakan fungsinya dalam bidang Perpustakaan dan Kearsipan (Bapersip, 2008).
Visi •
Badan Perpustakaan dan Kearsipan Provinsi Jawa Timur menetapkan visi yang sesuai dengan tugas dan fungsinya, yaitu: “Jawa Timur Membaca dan Tertib Arsip Tahun 2014”
Sekilas Bapersip Jawa Timur (Lanjutan) Bapersip Jawa Timur Misi •
•
• •
Membangun sinergi dengan seluruh lapisan dan stakeholder di Provinsi Jawa Timur untuk meningkatkan pembinaan, pengembangan dan pendayagunaan serta pengawasan sumber daya perpustakaan dan kearsipan di Jawa Timur. Meningkatkan pemasyarakatan dan pelayanan publik bidang jasa perpustakaan dan kearsipan. Memfasilitasi peningkatan kesejahteraan masyarakat melalui program penanggulangan kemiskinan. Meningkatkan upaya penyelamatan, pelestarian bahan pustaka dan arsip yang bernilai guna.
Pengelompokan pada perpustakaan Bapersip Jawa Timur • •
•
Merupakan salah satu bagian dari marketing perpustakaan (Guilano,2009) Menurut de Saez (2002) pentingnya pengelompokan dalam perpustakaan didefinisikan sebagai pembagian dari pasar atau informasi perpustakaan menjadi bagian yang lebih kecil, lebih dapat diatur, menjadi kelompok yang mempunyai karakteristik. Menurut Simkin (2007) variabel yang digunakan dapat dibagi menjadi variabel yang berhubungan dengan karakteristik pengguna dan yang berhubungan dengan produk. Karakteristik pengguna meliputi demografi, sosio-ekonomi, lokasi geografis, dan gaya hidup. Sedangkan yang berhubungan dengan produk meliputi perilaku pembelian, peluang pembelian, perilaku konsumsi, dan perilaku terhadap produk.
Data Mining Mengapa melakukan data mining?? • • •
Data yang berjumlah besar (data Bapersip dari tahun 2009-2012 menghasilkan lebih dari 50000 transaksi peminjaman) Teknologi pemrosesan data yang semakin canggih Diperlukan analisis untuk mengubah data mentah menjadi pengetahuan
Customer data
Customer knowledge
Analisis klaster Analisis Clustering •
•
Cluster analysis membagi sejumlah data ke dalam kelompok-kelompok yang memberi arti dan berguna, berdasarkan informasi yang terdapat di dalamnya yang mendefinisikan objek-objek dan hubungannya (Tan, Steinbach, & Kumar, 2006). Manfaat penerapan analisis clustering dalam sistem perpustakaan, • • •
membantu meningkatkan kualitas pelayanan, menyediakan dukungan pembuatan keputusan yang lebih efektif, membuat perpustakaan memainkan peran yang lebih aktif dalam melayani pengguna.
GAGA-Kmeans K-means •
•
Merupakan modifikasi dari algoritma K-means dengan menggunakan Genetic Algorithm (GA) sebagai alat pemilihan initial seeds pada tahap klasterisasi K-means. Lu, dkk (2004) mengembangkan proses algoritma genetika dalam penentuan titik pusat klaster yang memiliki performa yang lebih cepat dan menghasilkan klaster yang lebih baik, yang disebut dengan algoritma genetika cepat (Fast Genetic K-means Algorithm).
Mengapa menggunakan GA-kmeans Mengapa menggunakan GA K-means? • • •
Kekurangan algoritma K-means sederhana karena tidak ada proses pemilihan initial seeds pada fase inisialisasi Pada algoritma K-means sederhana initial seeds ditentukan secara random Perbedaan pemilihan initial seeds dapat menyebabkan perbedaan yang besar dalam hasil klasterisasi
Diagram alir kerja GA-Kmeans Flowchart GA-Kmeans START
Inisialisasi Populasi (jmlpopulasi, jmlgenerasi)
Perhitungan nilai fitness
Termination condition? Tidak Seleksi
Mutasi
Elitisme
Hasil Fitness terbaik
Menggunakan hasil initial centroid optimal untuk klasterisasi k-means
Ya
Hasil Fitness terbaik
METODOLOGI
Metode Pengerjaan TA Metodologi pengerjaan TA Mulai
Pengumpulan Data
Identifikasi Permasalahan
Studi Literatur
Praproses data
Implementasi klasterisasi dengan menggunakan algoritma GA K-means
TIDAK Uji coba dan validasi hasil klasterisasi
YA Analisis hasil klasterisasi
Penyusunan buku TA
MODEL DAN IMPLEMENTASI
Atribut yang digunakan untuk klasterisasi • Pengelompokan berdasarkan pada aspek demografis dan behaviour pengguna No
Atribut
Keterangan atribut
1
Gender
Demografis
2
Usia
Demografis
2
Pekerjaan
Demografis
3
Jumlah transaksi peminjaman buku
Behavioural
4
Jumlah buku yang dipinjam kategori a
Behavioural
5
Jumlah buku yang dipinjam kategori b
Behavioural
6
Jumlah buku yang dipinjam kategori b, dst
behavioural
Praproses data Data integration • Integrasi tabel yang diperlukan dalam clustering
Data cleaning • Pembersihan data duplikat • Penyelesaian data inkonsisten • Menghilangkan missing value • Menghilangkan outlier
Data transformation • Transformasi data field usia • Transformasi field subject • Transformasi field jumlah buku
Data reduction • Pengambilan sampel data tanpa mengurangi integritas data asli
Integrasi data Data integration Tabel katalog.tra nspinjam
Tabel katalog.bib _mst_katal og
Tabel katalog.tra nspinjam_ dtl
Tabel katalog.bib _mst_katal og_dtl
Query postgresql: pilih ang_id dan nomor_pinjam yang sama
Query postgresql: pilih controlnum yang sama
Tabel1
Tabel2
Query postgresql: Pilih nomor_item yang sama Tabel katalog.sir_ mst_anggo ta
Tabel3
Query postgresql: Pilih ang_id yang sama
Tabel4
Pembersihan data Data cleaning Menghilangkan data duplikat Penanganan missing values Memperbaiki data yang tidak konsisten Menghapus outlier
Transformasi data Data transformation Transformasi field usia Transformasi field subject menjadi kategori_buku Transformasi field jumlah buku yang dipinjam Transformasi field jumlah transaksi peminjaman
MODEL DAN IMPLEMENTASI IMPLEMENTASI GA-KMEANS
Representasi kromosom
• Panjang kromosom = jumlah atribut*jumlah klaster • Tiap gen mewakili titik pusat klaster
Inisialisasi Populasi Inisialisasi Populasi START
User menginputkan parameter algoritma genetika
Data yang ingin dilakukan proses klasterisasi
Menghitung nilai maksimum dalam satu atribut
Menghitung nilai minimum dalam satu atribut
Membangkitkan bil random dalam range max-min
Hasil : populasi
Proses hitung nilai fitness
• Nilai gen dibangkitkan dari bilangan random yang terletak antara range nilai maksimum dan nilai minimum atribut.
Perhitungan fungsi fitness Inisialisasi populasi awal
Menghitung jarak tiap data asli terhadap centroid yang direpresentasikan dalam kromosom
Ambil nilai minimum dari jarak tiap data terhadap centroid ke i
Menjumlahkan jarak terpendek data terhadap centroid yg dimiliki masing2 kromosom sebagai nilai fitness
Hasil fitness masing2 kromosom
Proses seleksi
• setiap titik dalam data asli dihitung jaraknya dengan setiap titik pusat klaster yang direpresentasikan dalam individu/ kromosom pada populasi.
Proses seleksi Proses seleksi Perhitungan nilai fitness
•
fi = nilai fitness individu ke i
•
Hitung nilai fitness relatif tiap kromosom fki ϵ p dan fki+n>p
Hitung nilai fitness kumulatif tiap kromosom (fki)
Kromosom ke (k+n) tdk trpilih sbg kndidat induk
Bangkitkan bilangan acak p Ya Pilih kromosom ke (k+n) sbg kandidat induk
Hasil : individuterpilih
Proses mutasi
Tidak
• •
menggunakan metode seleksi roda roulette. menghitung nilai frekuensi relatif dan frekuensi kumulatif dari fitness setiap kromosom. Dibangkitkan suatu bilangan acak p. Kromosom yang memiliki nilai yang lebih kecil dari nilai p akan dipilih sebagai kandidat induk yang melakukan mutasi.
Proses mutasi •
Proses seleksi
Membangkitkan bilangan random p
•
Menentukan posisi gen yang dimutasi secara random
Tidak p < ProbMut
Ya Lakukan mutasi (tambahkan dgn nilai geser)
Hasil : populasi baru hasil mutasi
Proses elitisme
Tidak dilakukan mutasi pd gen tsb
•
proses mutasi menggunakan mutasi geser, yaitu dengan menggeser nilai gen pada gen yang terpilih untuk dimutasikan. Nilai geser dapat bernilai positif atau negatif. Proses mutasi geser dilakukan berdasarkan probabilitas mutasi yang ditentukan oleh user.
Proses Elitisme elitisme Proses Proses mutasi
Gabungan populasi induk dan populasi anak (2p)
Hitung fitness anak dan fitness induk
Sort fitness masingmasing indivdu
Pilih sebanyak p individu terbaik
Hasil : populasi baru
Pilih individu terbaik u/ centroid k-means
• •
Metode elitisme yang dipakai adalah sistem elitisme ranking. Meranking nilai fitness populasi induk dan anak, kemudian dipilih sejumlah kromosom sebagai populasi baru
Hasil Algoritma Genetika • Hasil algoritma genetika berupa initial centroid yang akan digunakan untuk clustering k-means • Proses selanjutnya adalah clustering menggunakan metode k-means menggunakan initial centroid hasil algoritma genetika
UJI COBA DAN ANALISIS HASIL
Uji coba parameter algoritma genetika •
•
Uji parameter ini dilakukan dengan cara mengganti parameter input algoritma genetika yaitu ukuran populasi, probabilitas mutasi, dan maksimum iterasi Uji coba parameter ini digunakan untuk mengetahui pengaruh parameter algoritma genetika terhadap solusi yang dihasilkan.
Uji coba parameter ukuran populasi dan probabilitas mutasi
Uji coba parameter maksimum generasi • Nilai untuk maksimal generasi dibuat berbeda mulai dari 100 hingga 1000 generasi. Sedangkan nilai untuk parameter lainnya ditetapkan sama, dengan probabilitas mutasi sebesar 0.3 dan ukuran populasi sebesar 100.
Uji coba penentuan jumlah cluster • •
• •
Terdapat suatu metode untuk menentukan jumlah klaster berdasarkan nilai silhoutte. (Rousseuw & Kauffman, 1987) Nilai silhoutte dari setiap titik adalah ukuran seberapa besar kemiripan suatu titik terhadap titik dalam klasternya sendiri dibandingkan dengan titik pada klaster yang lain. Nilai rata-rata silhouette terbesar pada jumlah klaster (k) menunjukkan bahwa k merupakan jumlah klaster yang optimal. Jumlah klaster yang optimal adalah 4 klaster
Uji Coba Perbandingan Klasterisasi GA-Kmeans dengan Simple K-means •
Uji coba dilakukan dengan membandingkan nilai within cluster sum of distances antara metode pengelompokan yang telah dioptimasi dengan menggunakan algoritma genetika dan metode pengelompokan menggunakan algoritma k-means sederhana.
UJI COBA DAN ANALISIS HASIL ANALISIS HASIL KLASTERISASI
Hasil final centroid tiap klaster
Hasil klaster dan analisis Klaster
Analisis
Klaster 1
Terdiri dari 156 pengguna berjenis kelamin perempuan dengan usia rata-rata 24 tahun. Pengguna pada klaster ini adalah mahasiswa dengan jumlah transaksi peminjaman antara 23-33 kali . Pengguna pada klaster ini memiliki frekuensi peminjaman yang tinggi pada buku dengan kategori literatur.
Klaster 2
Klaster ini meliputi 107 orang pengguna berjenis kelamin laki-laki, dengan usia rata-rata 44 tahun. Jenis pekerjaan pengguna beragam. Rekomendasi kategori buku yang sesuai untuk klaster ini adalah buku yang termasuk dalam kategori agama, selain itu kategori psikologi serta buku dengan kategori kedokteran dan kesehatan
Hasil klaster dan analisis Klaster
Analisis
Klaster 3
Meliputi 151 pengguna adalah laki-laki dengan usia rata-rata 27 tahun. Pengguna adalah mahasiswa. Rekomendasi kategori buku yang sesuai adalah kategori psikologi, sosial politik,ekonomi, serta manajemen.
Klaster 4
Terdiri dari 57 pengguna adalah laki-laki dengan rata-rata usia 20 tahun. Pengguna pada klaster ini adalah mahasiswa. jenis kategori buku yang sebaiknya direkomendasikan untuk pengguna pada klaster ini adalah buku dengan kategori bahasa dan ilmu alam.
KESIMPULAN Kesimpulan 1) Praproses data yang digunakan untuk proses pengelompokan pengguna Bapersip terdiri dari lima tahap, yaitu tahap penentuan atribut yang digunakan untuk klasterisasi, tahap integrasi data, tahap pembersihan data, tahap transformasi data, dan tahap reduksi data. 2) Algoritma GA-Kmeans mampu menghasilkan pengelompokan dengan tingkat variasi di dalam klaster yang lebih baik dibandingkan dengan algoritma K-means sederhana. Dengan nilai total within cluster sum of distances yang dihasilkan adalah sebesar 7553.459 dibandingkan dengan nilai yang diperoleh K-means sebesar 8896.303. 3) Dari hasil pengelompokan pengguna Bapersip menggunakan algoritma GAKmeans, terbentuk empat buah klaster pengguna.
KESIMPULAN (Lanjutan) Kesimpulan 4) Pengukuran kinerja algoritma GA-Kmeans dilakukan dengan mengubah parameter algoritma genetika. Performansi algoritma GA-Kmeans dipengaruhi oleh beberapa parameter sebagai berikut: •
•
•
Ukuran populasi: semakin besar ukuran populasi tidak berarti nilai fitness yang dihasilkan semakin besar pula. Hal ini dikarenakan sifat algoritma genetika yang membangkitkan ukuran populasinya secara acak. Maksimum generasi: jumlah maksimum generasi berbanding lurus dengan nilai solusi yang dihasilkan. Semakin besar jumlah generasi, maka semakin baik solusi yang dihasilkan. Hal ini dikarenakan semakin besar jumlah generasi maka ruang observasi akan semakin besar pula. Probabilitas mutasi: probabilitas mutasi juga berbanding lurus dengan nilai solusi yang dihasilkan. Probabilitas mutasi yang tinggi akan memungkinkan gen yang terpilih untuk dimutasi lebih banyak.
Saran •
Atribut yang digunakan untuk pengelompokan sebaiknya ditambahkan, tidak hanya menggunakan atribut demografis dan behavioural saja, namun juga atribut psikografis. Pengelompokan berdasarkan atribut psikografis merupakan pendekatan pengelompokan yang memisahkan pelanggan berdasarkan kepribadian, gaya hidup, maupun opini (Browne, 2011).
Daftar Pustaka Pustaka Daftar • • • • • • • • •
Al-Shboul, B., & Sung, H. M. (2010). Initializing K-Means Using Genetic Algorithm. World Academy of Science, Engineering and Technology , 114-118. Bapersip. (2008). Badan Perpustakaan dan Kearsipan Provinsi Jawa Timur. Dipetik March 22, 2012, dari Profil: http://www.bapersip.jatimprov.go.id Bapersip. (2008). Profil. Dipetik Maret 22, 2012, dari Badan Perpustakaan dan Kearsipan Provinsi Jawa Timur: http://www.bapersip.jatimprov.go.id Bapersip. (2010, December 23). Statistik Perpustakaan. Dipetik Maret 22, 2012, dari Badan Perpustakaan dan Kearsipan Propinsi Jawa Timur PNRI: http://bpadjawatimur.pnri.go.id/?q=node/67 Barakbah, A. R. (2006). Optimasi Titik Pusat K-means dengan GA. Workshop on Soft Computing. Browne, M. (2011). Communicating value through strategic alignment. de Saez, E. (2002). Marketing concepts for libraries and information services (2nd ed.). London: Facet Publishing. Dispendukcapil. (2012, Februari 20). Jumlah Penduduk Surabaya Tahun 2011. Dipetik Maret 28, 2012, dari Dispendukcapil Surabaya: http://dispendukcapil.surabaya.go.id/index.php/media-apublik/statistik-penduduk/43-pergerakan-penduduk/167-jumlah-penduduk-surabaya-2011 Guilano, S. J. (2009). Library system Journal. We have books and computers: libraries and the importance of marketing .
Daftar Pustaka
Daftar Pustaka • • • • • • • • • • • •
Han, J., Kamber, M., & Pei, J. (2011). Data Mining Concepts and Techniques 3rd edition. United States: Morgan Kaufmann Publisher. Humas Pemkot Surabaya. (2011, September 15). Release. Dipetik Maret 2012, 27, dari Humas Surabaya, Informasi Cepat, Tepat, dan Obyektif: http://humas.surabaya.go.id/index.php?option=pressd&det=39 Khrisna, K., & Murty, N. M. (1999). Genetic K-means algorithm. IEEE Transactions on Systems, Man, and Cybernetics. Kim, K. J., & Ahn, H. (2008). A recommender system using GA-Kmeans klasterisasi in an online shopping market. Expert Systems with Applications , 1201-1209. Kusumadewi, S., & Purnomo, H. (2005). Penyelesaian Maslah Optimasi dengan Teknik-teknik Heuristik. Yogyakarta: Graha Ilmu. Li, J. W., & Chen, P. H. (2008). The application of cluster analysis in Library System. IEEE , 907-910. MathWorks. (t.thn.). Silhouette plot. Dipetik July 23, 2012, dari MathWorks Inc: http://www.mathworks.com/help/toolbox/stats/silhouette.html Rousseuw, J. P., & Kauffman. (1987). Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis. Computational and Applied Mathematics . Simkin, L. (2007). Marketing is marketing- maybe! . Marketing Intelligence & Planning . Suyanto. (2005 ). Algoritma Genetika dalam Matlab. Yogyakarta: Penerbit Andi. Tan, P. N., Steinbach, M., & Kumar, V. (2006). Introduction to Data Mining. United States: Pearson Education Inc. Wicaksono, H. (2008). Pasarkan Layanan Perpustakaan Anda dengan Tepat.
