PENERAPAN METODE GA-KMEANS UNTUK PENGELOMPOKAN PENGGUNA PADA BADAN

PERPUSTAKAAN DAN KEARSIPAN (BAPERSIP) PROVINSI JAWA TIMUR

Ferlyna K Wardhani

5208100130

Ujian Tugas Akhir Laboratorium Sistem Pendukung Keputusan dan Business Intelligence

Dosen Pembimbing I: Erma Suryani, S.T., M.T., Ph.D Dosen Pembimbing II: Ahmad Mukhlason, S.Kom, M.Sc

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.

Latar Belakang

• 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.

Rumusan Masalah

Analisis rekomendasi buku bagi pengguna Bapersip yang sesuai dengan karakteristik pengguna

Segmentasi pengguna Bapersip Surabaya

Marketing perpustakaan

Bagaimana meningkatkan minat baca masyarakat??

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

• 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.

Batasan

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.

Tujuan

• Meningkatkan jumlah peminjaman buku pada tiap transaksinya di Bapersip Jawa Timur.

• Menghasilkan rekomendasi buku yang sesuai dengan karakteristik pengguna.

Manfaat

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

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.

Sekilas Bapersip Jawa Timur (Lanjutan)

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.

Pengelompokan pada perpustakaan

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

Data Mining

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.

Analisis klaster

GA 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).

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

Mengapa menggunakan GA-kmeans

Flowchart GA-Kmeans

Diagram alir kerja GA-Kmeans

START

Inisialisasi Populasi

(jmlpopulasi,

jmlgenerasi)

Perhitungan nilai fitness

Seleksi

Mutasi

Elitisme

Termination

condition?

Menggunakan hasil initial

centroid optimal untuk

klasterisasi k-means

Tidak

Ya

Hasil Fitness

terbaik

Hasil

Fitness

terbaik

METODOLOGI

Metode Pengerjaan TA Metodologi pengerjaan TA

Mulai

Pengumpulan

Data

Identifikasi

Permasalahan

Studi Literatur

Implementasi klasterisasi dengan

menggunakan algoritma GA K-means

Analisis hasil klasterisasi

Uji coba dan validasi

hasil klasterisasi

Penyusunan buku

TA

YA

TIDAK

Praproses data

MODEL DAN IMPLEMENTASI

• Pengelompokan berdasarkan pada aspek demografis dan behaviour pengguna

Atribut yang digunakan untuk klasterisasi

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

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

Praproses data

Data integration Tabel

katalog.tra

nspinjam

Tabel

katalog.tra

nspinjam_

dtl

Tabel1

Tabel

katalog.bib

_mst_katal

og

Tabel

katalog.bib

_mst_katal

og_dtl

Tabel2

Tabel3

Query postgresql:

pilih ang_id dan

nomor_pinjam yang

sama

Query postgresql:

pilih controlnum

yang sama

Query postgresql:

Pilih nomor_item

yang sama

Query postgresql:

Pilih ang_id yang

sama

Tabel

katalog.sir_

mst_anggo

ta

Tabel4

Integrasi data

Data cleaning

Menghilangkan data duplikat

Penanganan missing values

Memperbaiki data yang tidak konsisten

Menghapus outlier

Pembersihan data

Data transformation

Transformasi field usia

Transformasi field subject menjadi kategori_buku

Transformasi field jumlah buku yang dipinjam

Transformasi field jumlah transaksi peminjaman

Transformasi data

MODEL DAN IMPLEMENTASI

IMPLEMENTASI GA-KMEANS

• Panjang kromosom = jumlah atribut*jumlah klaster

• Tiap gen mewakili titik pusat klaster

Representasi kromosom

Inisialisasi Populasi

• Nilai gen dibangkitkan dari bilangan random yang terletak antara range nilai maksimum dan nilai minimum atribut.

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

• setiap titik dalam data asli dihitung jaraknya dengan setiap titik pusat klaster yang direpresentasikan dalam individu/ kromosom pada populasi.

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

Proses seleksi

Menjumlahkan jarak terpendek

data terhadap centroid yg dimiliki

masing2 kromosom sebagai nilai

fitness

Hasil fitness

masing2

kromosom

Proses seleksi

• 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.

Perhitungan

nilai fitness

fi = nilai

fitness

individu ke i

Hitung nilai fitness

relatif tiap kromosom

Hitung nilai fitness

kumulatif tiap

kromosom (fki)

Bangkitkan

bilangan acak p

fki ϵ p dan fki+n>p

Pilih kromosom ke (k+n)

sbg kandidat induk

Ya

Proses mutasi

Hasil :

individuterpilih

Kromosom ke

(k+n) tdk trpilih

sbg kndidat induk

Tidak

Proses seleksi

• 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 mutasi

Proses

seleksi

Membangkitkan

bilangan random p

Menentukan posisi gen

yang dimutasi secara

random

p < ProbMut

Lakukan mutasi

(tambahkan dgn nilai

geser)

Ya

Hasil : populasi

baru hasil mutasi

Proses elitisme

Tidak dilakukan

mutasi pd gen tsbTidak

Proses Elitisme

• Metode elitisme yang dipakai adalah sistem elitisme ranking.

• Meranking nilai fitness populasi induk dan anak, kemudian dipilih sejumlah kromosom sebagai populasi baru

Proses elitisme

Proses

mutasi

Gabungan populasi

induk dan populasi

anak (2p)

Hitung fitness anak

dan fitness induk

Sort fitness masing-

masing indivdu

Pilih sebanyak p

individu terbaik

Hasil :

populasi baru

Pilih individu terbaik u/

centroid k-means

• 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

Hasil Algoritma Genetika

UJI COBA DAN ANALISIS HASIL UJI COBA DAN ANALISIS HASIL

• 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 algoritma genetika

Uji coba parameter ukuran populasi dan probabilitas mutasi

• 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 parameter maksimum generasi

• 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 penentuan jumlah cluster

• 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 Perbandingan Klasterisasi GA-Kmeans dengan Simple K-means

UJI COBA DAN ANALISIS HASIL

ANALISIS HASIL KLASTERISASI

Hasil final centroid tiap klaster

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.

Hasil klaster dan analisis

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 GA-Kmeans, terbentuk empat buah klaster pengguna.

KESIMPULAN

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.

KESIMPULAN (Lanjutan)

• 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).

Saran

Daftar Pustaka Daftar Pustaka

• 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://bpad-jawatimur.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-a-publik/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 • 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.

Daftar Pustaka