PENENTUAN RUTE TERPENDEK BERSEPEDA

DI AREA KOTA MALANG MENGGUNAKAN ALGORITMA SEMUT

Dian Eka Ratnawati, Sindy Yudi Prakoso, Yusi Tyroni Mursityo

Program Studi Ilmu Komputer, Program Teknologi Informasi dan Ilmu Komputer, Universitas

Brawijaya, Jl. Veteran Malang, Jawa Timur, 65141

Email: dian_ilkom@ub.ac.id ,jimmz.mail@gmail.com, yusi.tyro@gmail.com

Abstrak

Bersepeda dianggap sebagai transportasi bebas polusi dan menyehatkan, namun diperlukan adanya suatu informasi perjalanan. Informasi perjalanan ini sangat erat kaitannya dengan rute yang dipilih sehingga dapat menghasilkan solusi yang optimal, dalam hal ini adalah meminimalkan jarak perjalanan dari tempat asal menuju tempat tujuannya.

Penelitian ini bertujuan membangun sebuah sistem penentuan jalur terpendek bersepeda di area kota Malang menggunakan algortima semut. Pada penelitian ini ingin diketahui apakah hasil jalur terpendek yang dihasilkan oleh algoritma semut lebih baik dari solusi yang dihasilkan algoritma Dijkstra atau sebaliknya. Dari ujicoba dengan membandingkan algoritma semut dengan Dijkstra diperoleh nilai MSE 0.490746 yang membuktikan bahwa algoritma semut memiliki tingkat akurasi yang cukup tinggi.

Kata Kunci: Algoritma Semut, Ant Colony System, Algoritma Dijkstra, Rute Terpendek.

Abstract

Cycling is considered to be a healthy and pollution-free tranportation, but it needs some kind of travel information. This travel Information is very closely related with the selected route so that it can provide optimal solution, in this case to minimize distance from starting point to the desired destination.

This study aims to build a shortest cycling path determination in Malang City using ant algorithm system. In this study wanted to know whether the results generated by the shortest path ant algorithm is better than Dijkstra algorithm generated solutions. From the test by comparing the ant algorithm Dijkstra is obtained MSE 0.490746 which proved that the ant algorithm has a fairly high degree of accuracy.

Keyword : Ant Algorithm, Dijkstra Algorithm, Shortest Route

PENDAHULUAN

Salah satu inovasi untuk mengurangi polusi dalam transportasi darat yaitu dengan adanya program car free day yang diharapkan bisa memberikan ruang bagi masyarakat Kota Malang untuk bisa berolahraga serta menikmati udara segar bebas asap[1]. Dengan ditunjang dengan slogan Bike to Work ternyata banyak diminati oleh warga kota Malang.

Kebutuhan akan suatu informasi atau petunjuk tentang suatu lokasi baik itu lokasi jalan ataupun lokasi obyek-obyek tertentu sangat diperlukan bagi pengguna sepeda untuk menentukan jalur terpendek dari suatu tempat

ke tempat lainnya. Shortest path problem merupakan salah satu permasalahan optimasi yang dapat diselesaikan dengan menggunakan metode heuristik, seperti algoritma genetika (Genetic Algorithm, GA) dan algoritma semut (Ant Colony, AntCo)[2]. Algoritma semut adalah solusi universal dan fleksibel yang awalnya digunakan pada permasalahan optimasi Traveling Salesman Problem. Analogi pencarian rute terpendek oleh semut-semut, telah menjadi stimulus terciptanya suatu metode untuk menentukan jarak terpendek dari suatu tempat ke tempat lain, Jarak terpendek yang dimaksud adalah hasil dari perhitungan beberapa parameter melalui Ant Colony Optimization [3].

Dalam penelitian ini, pencarian rute terpendek mempunyai tujuan membantu dalam menentukan jalur terpendek dari dan menuju suatu tempat tertentu di Malang khususnya Malang Kota, dengan ditentukannya jalur terpendek maka diharapkan dapat meminimalisasi waktu tempuh perjalanan

TINJAUAN PUSTAKA

2.1 Konsep Dasar Ant Colony Optimization (ACO)

Algoritma Ant Colony Optimization diinspirasikan oleh lingkungan koloni semut pada saat mencari makanan [3]. Semut-semut mempunyai penyelesaian yang unik dan sangat maju yaitu dengan menggunakan jejak pheromone, proses peninggalan pheromone ini dikenal sebagai stigmergy, yaitu sebuah proses memodifikasi lingkungan yang tidak hanya bertujuan untuk mengingat jalan pulang ke sarang, tetapi juga memungkinkan para semut berkomunikasi dengan koloninya pada suatu jalur dan membangun solusi, semakin banyak jejak pheromone ditinggalkan, maka jalur tersebut akan diikuti oleh semut lain.

Dalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah untuk menentukan jalur terpendek, yaitu[3]:

a. Inisialisasi Parameter

Dalam ACO terdapat beberapa parameter masukan sebagai inisialisasi awal untuk melakukan proses optimasi. Beberapa parameter tersebut adalah:

1.            iij : Intensitas jejak semut antar kota dan perubahannya

2.            n : Banyak titik atau dij (jarak antar kota)

3.            Penentuan kota berangkat dan kota tujuan

4.            Q : Tetapan siklus semut

5.            a : Tetapan pengendali intensitas jejak semut

6.            R : Tetapan pengendali visibilitas

7.            ilij : Visibilitas antar titik (1/dij)

8.            m : Jumlah semut

9.            p : Tetapan penguapan jejak semut

10.         Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan.

11.         Inisialisasi kota pertama setiap semut.

m semut ditempatkan pada kota pertama yang telah ditentukan.

b. Pengisian Tabu List

Pengisian kota pertama ke dalam tabu list. Hasil dari langkah ini adalah terisinya elemen tabu list oleh setiap semut.

c. Pemilihan Rute Perjalanan Semut

Perjalanan koloni semut berlangsung terus menerus hingga mencapai kota yang telah ditentukan. Perhitungan nilai probabilitas kota untuk dikunjungi seperti pada persamaan 1:

N`]^Oa .Nb]^Oc

\]^ _ = ∑ _defghijkl_m     .Nb]_dOc (1)

N`]_dOa

dimana :

Pij : probabilitas verteks i ke verteks j

i              : verteks ke-i

j              : verteks ke-j

iij : pheromone dari verteks i ke verteks j R : tetapan pengendali visibilitas

a : tetapan pengendali intensitas jejak semut ilij : visibilitas dari verteks i ke verteks j

k : jumlah jalur kemungkinan yang dilalui

d. Perhitungan Panjang Jalur Setiap Semut Perhitungan dilakukan berdasarkan tabuk masing-masing dengan menggunakan persamaan 2:

nk = otapuq (n),tapuq(r)

ntr

+ s otapuq(s),tapuq(sRr) S+r

(2)

dimana :

Lk : panjang lintasan yang dilalui semut k

n : banyak titik

67!E/k(=),7!E/k(=R1) : bobot antara titik ke s

dan s+1 pada tabu list

e. Perhitungan Perubahan Harga Intensitas Pheromone Semut

Persamaan (3) digunakan untuk menghitung perubahan intensitas pheromone semut :

∆v&) = ∑ ∆v&)

' ~ ~+~

dimana : ∆v&) : Intensitas jejak semut antar kota dan perubahannya

∆v&)~ : perubahan harga intensitas jejak kaki semut antar kota setiap semut

m            : jumlah semut

k             : jumlah jalur yang mungkin dilewati

f. Pengosongan Tabu List

Tabu list perlu dikosongkan untuk diisi lagi dengan urutan kota yang baru pada siklus selanjutnya, jika jumlah siklus maksimum belum tercapai atau belum terjadi konvergensi.

2.2.Ant Colony System (ACS)

Algoritma Ant Colony System (ACS) merupakan pengembangan dari Algoritma ACO. Algoritma ini tersusun atas sejumlah m semut yang bekerjasama dan berkomunikasi secara tidak langsung melalui komunikasi Pheromone[4].Peranan utama dari penguapan Pheromone pada ACS adalah untuk mencegah stagnasi.

2.2.1.State Transition Rule

Aturan transisi status yang berlaku pada ACS[5] adalah seperti persamaan 4 :

)

= wjxCyjzf[v&,/O.[{&,/]|}, €,        )&k! ~ ≤ ~G (5k=204&7!=&)

)&k! 7&6!k (5k=2043!=&)

(4)

dimana :

j : titik yang akan dituju. Jumlah Pheromone yang terdapat pada edge antara titik r dan titik s.

q : sebuah bilangan random.

β : parameter pengendali jarak (p > 0 )

Jika q ≤ q0 maka pemilihan titik yang akan dituju menerapkan aturan eksploitasi sedangkan jika q > q0 maka menerapkan eksplorasi.

2.2.2.Update Pheromone Lokal

Lokal updating rule dengan mengubah tingkat pheromone pada edge-edge yang telah dikunjungi semut[5], menggunakan persamaan 5 :

v&) ← (1 − ‚). v&) + ‚. vG

dimana :

‚             : parameter evaporasi lokal.

i0            : nilai awal jejak pheromone.

dengan

1

vG = n.ƒnn

dimana :

n             : jumlah titik.

Cnn : panjang sebuah tour terbaik.

2.2.3.Update Pheromone Global

Global updating rule [5], menggunakan persamaan 7 :

v&) ← (1 − ‚). v&) + ‚. ∆v&)~        (7)

1 wƒE=

G            dengan: „v&)~ =

)&k!(3, =)… 74/3 753E!&k k5=50/3/1!n =5E!0&kn†!

dimana :

ρ : parameter evaporasi global.

Cbs : panjang lintasan terbaik keseluruhan.

iij            : intensitas jejak pheromone pada garis

(i,j)

2.3. Algoritma Dijkstra

Algoritma Dijkstra merupakan salah satu varian dari algoritma greedy, yaitu salah satu algoritma untuk pemecahan persoalan yang terkait dengan masalah optimasi. Algoritma greedy ini hanya memikirkan solusi terbaik yang akan diambil pada setiap langkah tanpa memikirkan konsekuensi ke depan. Algoritma greedy ini berupaya membuat pilihan nilai optimum lokal pada setiap langkah dan berharap agar nilai optimum lokal ini mengarah kepada nilai optimum global[6].

Fungsi objektif akan memaksimalkan atau meminimalkan nilai solusi. Tujuannya adalah memilih satu saja solusi terbaik dari masing¬masing anggota himpunan solusi

Penggunaan strategi greedy pada algoritma Dijkstra adalah Pada setiap langkah, ambil sisi berbobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan yang terpendek di antara semua lintasannya ke simpul-simpul yang belum terpilih.

2.4 Akurasi

Untuk menghitung akurasi menggunakan metode Mean Square Error (MSE). Semakin kecil nilai MSE mengindikasikan bahwa hasil prediksi semakin akurat[7]. Nilai MSE dapat diperoleh dengan persamaan 8.

nMSE = (Dig − Dik )2

n             (8)

dimana :

‡&8 : jarak aktual semut pada periode i ‡&k : jarak aktual dijkstra pada periode i n : jumlah percobaan

METODOLOGI

3.1. Perancangan Sistem

Gambar 1 merupakan flowchart pencarian rute terpendek menggunakan algoritma semut: 1. Inisialisasi parameter awal, yaitu:

a.            Parameter yang digunakan dalam penentuan rute terpendek yaitu nama jalan, titik penyusun jalan, dan panjang jalan

b.            Parameter algoritma semut, yaitu :

1.            Jumlah semut yang akan digunakan

(m)

2.            Jumlah iterasi yang akan digunakan (NCmax)

3.            Tetapan penguapan jejak semut (p)

4.            Tetapan pengendali intensitas jejak semut (a)

5.            Tetapan pengendali visibilitas (0)

6.            Intensitas jejak semut antar kota (i)

Gambar 1. Flowchart Membangun Rute

Perjalanan

2.            Hasil dari inisialisasi tersebut akan dimasukkan ke dalam tabu list sebagai node awal semut.

3.            Proses simulate ant yaitu mensimulasikan perjalanan semut sampai semua semut tiba pada tujuan tertentu secara random.

4.            Update pheromone lokal dimana setiap semut setelah menuju titik selanjutnya akan selalu melakukan update pheromone untuk membuat tingkat ketertarikan ruas¬ruas yang ada berubah secara dinamis.

5.            Simpan hasil terbaik dari setiap perjalanan semut kedalam tabulist.

6.            Update pheromone global.

7.            Reset tabulist.

8.            Jika kondisi terpenuhi, berhenti dan hasilnya adalah solusi rute terpendek

3.2 Perancangan Basis Data

Gambar 2 merupakan tabel-tabel dalam basisdata digunakan untuk menyimpan seluruh data yang digunakan oleh sistem. Tabel yang dapat disusun berdasarkan kebutuhan sistem ini yaitu tabel Jalan, tabel Cabang, tabel LampuLantas, dan tabel Koordinat Penyusun.

Gambar 2 Entity Relationship Diagram HASIL DAN PEMBAHASAN

Pada penelitian ini dilakukan dua skenario ujicoba. Pada uji coba yang pertama dilakukan pengujian pengaruh parameter semut untuk mendapatkan nilai parameter terbaik dari algoritma semut. Data yang digunakan pada pengujian pertama adalah data jalan kota malang. Uji coba ini dilakukan sebanyak 5 kali pada setiap perubahan nilai parameter. Dari uji coba tersebut akan diperoleh nilai terbaik yang kemudian akan di rata-rata sebagai nilai parameter yang optimal.

Pada ujicoba yang kedua,untuk mengetahui tingkat keoptimalan algoritma ant colony system, dilakukan perbandingan antara algoritma ant colony system dengan algoritma Dijkstra. Dalam melakukan perbandingan ini, parameter yang digunakan algoritma ant colony system adalah nCmax=20, m=500, i0=0.5, a=4, 0=4, p=0.9, dan Q0=0.3.

4.1.Pengujian Parameter Semut

4.1.1.Pengujian Jumlah Semut (m) dan Pheromone Awal(i0)

Pada pengujian ini nilai m antara 100 - 500 dan nilai i0 antara 0,1 - 0,9 didapatkan hasil seperti pada gambar 3.

4.1.2. Pengujian Parameter a dan R

Pengujian untuk mencari nilai a dan R yang terbaik dari nilai 1 sampai dengan 5, didapatkan hasil nilai a dan R terbaik adalah 4 seperti yang ditunjukkan pada gambar 4.

Gambar 4. Grafik Uji a dan R

4.1.3. Pengujian Parameter p

Pengujian untuk mencari nilai p yang terbaik dari nilai 0.1 - 0.9. Setelah 5 kali pengujian, didapatkan hasil nilai p terbaik adalah 0.9 seperti yang ditunjukkan pada gambar 5.

Gambar 5. Grafik Uji p

4.1.4. Pengujian Parameter Q0

Parameter ini merupakan konstanta yang digunakan untuk pemilihan titik-titik yang akan dilalui oleh semut. Didapatkan nilai konstanta Q0 yang terbaik adalah 0.3.seperti pada gambar 6.

Gambar 6. Grafik Uji Q0

4.1.5.Pengujian Konvergensi

Pengujian dengan beberapa generasi dilakukan untuk menghasilkan solusi yang konvergen. Hasil dari pengujian ini digunakan untuk mencari siklus awal terjadinya kestabilan nilai / jarak dengan pengecekan 20 iterasi terakhir yang menghasilkan jarak yang sama.

Gambar 7. Grafik Uji Konvergensi

Berdasarkan gambar 7, dapat diketahui bahwa pada generasi ke 20 sampai 50 memiliki nilai yang sama. Dapat dikatakan bahwa pada generasi ke 20 telah didapatkan hasil yang konvergen.

4.2 Pengujian ACS dengan algoritma Dijkstra

Hasil dari pengujian antara ACS dengan algoritma Dijkstra dapat dilihat pada gambar 8

Gambar 8. Pengujian ACS dengan algoritma Dijkstra

Dari hasil pengujian yang ditunjukkan pada gambar 8, jarak yang dihasilkan oleh ACS dan Dijkstra adalah sama.

Pada Gambar 9 terdapat rute yang dihasilkan oleh ACS dan Dijkstra.

Gambar 9. Rute yang dihasilkan oleh ACS dan Djikstra

Dari beberapa percobaan, algoritma Dijkstra selalu mendapat rute yang optimal untuk semua data uji karena algoritma hanya memikirkan solusi terbaik dengan langsung mengambil jarak terpendek pada saat itu tanpa memikirkan jarak total yang dihasilkan.

0 + 0.7225 + 1.162084 + 0.0784

MSE =

MSE = 0.490746

MSE yang dihasilkan tersebut membuktikan bahwa algoritma semut memiliki tingkat akurasi yang cukup tinggi untuk penyelesaian masalah.

KESIMPULAN

Kesimpulan yang dapat diambil daripenelitian ini adalah:

1.            Pencarian rute terpendek dengan metode

Ant         Colony  System  dapat

diimplementasikan. Proses pencarian rute terpendek di mulai dengan menyebarkan semut ke suatu titik, kemudian semut akan berjalan bebas menuju tujuan perjalanan. Dalam pemilihan jalur terpendek, metode ini tergantung dari nilai parameter yang dimasukkan antara lain jumlah semut, i0, a, R, P, dan Q0.

2.            Perbandingan jarak terpendek yang dihasilkan algoritma Ant Colony System dengan Dijkstra menghasilkan jarak yang relative sama. Hanya saja rute yang dihasilkan oleh algoritma Ant Colony System lebih bervariatif, karena dipengaruhi oleh beberapa parameter.

3.            Dari ujicoba diketahui bahwa algoritma Ant Colony System memiliki tingkat akurasi yang cukup tinggi,

DAFTAR PUSTAKA

[1]          Nugraha, D., & dkk. (2006). Diagnosis Gangguan Sistem Urinari pada Anjing dan Kucing menggunakan VFI 5. Bandung: IPB.Surya Post, 30 November 2011

[2]          Mutakhiroh, I., Saptono, F., Hasanah, N., & Wiryadinata, R. (2007). Pemanfaatan Metode Heuristik Dalam Pencarian Jalur Terpendek Dengan Algoritma Semut dan Algoritma Genetik. Yogyakarta: Seminar

Nasional              Aplikasi Teknologi

Informasi. ISSN: 1907-5022

[3]          M. Dorigo, V. Maniezzo, dan A. Colorni. (1996). The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man,and Cybernetics— Part B, 26(1), , pp.1-13.

[4]          Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. England: The MIT Press Cambridge, Massachusetts Institute of Technology.

[5]          Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the traveling

salesman             problem.              Belgium:

Tech.Rep/IRIDIA/1996-003, Université Libre de Bruxelles.

[6]          Novandi, R. A. (2007). Perbandingan Algoritma Dijkstra dan Algoritma Floyd-Warshall dalam Penentuan Lintasan Terpendek (Single Pair Shortest Path). Bandung: Institut Teknologi Bandung.

[7]          Kaur Parvinder, Shakti Kumar,

dalam Pengaplikasian Lintasan Terpendek pada Link-State Routing Protocol. Bandung: Institut Teknologi Bandung

[9] Mutakhiroh, I., Saptono, F., Hasanah, N., & Wiryadinata, R. (2007). Pemanfaatan Metode Heuristik Dalam

Amarpartap        Singh, Optimization of     Pencarian            Jalur Terpendek Dengan

Membership       Functions             Based    on          Algoritma            Semut    dan        Algoritma

AntColony           Algorithm,           (IJCSIS)  Genetik.               Yogyakarta:        Seminar

International      Journal  of Computer       Nasional              Aplikasi Teknologi

Science and Information Security,Vol. 10, No. 4, April 2012, tanggal akses Agustus 2012

[8] Handaka, M. S. (2010). Perbandingan

Algoritma            Dijkstra (Greedy),

Bellman-Ford(BFS-DFS), dan Floyd-Warshall (Dynamic Programming)

Informasi. ISSN: 1907-5022.

[10] Wardy, I. S. (2007). Penggunaan graph dalam algoritma semut untuk melakukan optimasi. Bandung : Institut Teknologi Bandung.

SISTEM PEROLEHAN CITRA BERBASIS ISI MENGGUNAKAN GRAY LEVEL DIFFERENCE METHOD BERDASARKAN CIRI TEKSTUR PADA POLA BATIK

Nansy Lovitasari*, Fitri Damayanti**

*Program Studi Teknik Informatika, Fakultas Teknik

**Program Studi Manajemen Informatika, Fakultas Teknik

Universitas Trunojoyo

E-mail : *echi_dunkz@yahoo.com, **fitri2708@yahoo.com

Abstrak

Batik adalah kerajinan yang memiliki nilai seni tinggi dan telah menjadi bagian dari budaya Indonesia sejak lama. Batik di Indonesia mempunyai beragam jenis tekstur batik, warna batik, dan pola batik yang mencerminkan asal usul daerah dari batik tersebut. Saat ini pencarian citra berbasis teks sudah tidak efektif lagi karena adanya penilaian subjektif dari pengguna dalam merepresentasikan suatu citra. Karena itu diperlukan suatu sistem yang dapat menangani pencarian citra menggunakan query berupa citra atau disebut Sistem Perolehan Citra berbasis Isi (SPCI) atau Content Based Image Retrieval (CBIR). Penelitian ini menggunakan ciri tekstur sebagai proses pencarian kemiripan dari delapan kelas citra batik yang berbeda yaitu: Cirebon, Bali, Bangkalan, Pamekasan, Sumenep, Yogyakarta, Solo, dan Pekalongan sebagai objek perolehan citra berbasis isi. Sistem dibangun dengan proses utamanya yaitu ekstraksi fitur tekstur dengan menggunakan metode Gray Level Difference Method (GLDM) menggunakan empat arah utama. GLDM menghitung perbedaan mutlak antara sepasang derajat keabuan yang terpisah oleh jarak dan arah tertentu. Hasil ekstraksi fitur dilakukan pengukuran jarak kemiripan menggunakan metode Euclidean Distance. Dari uji coba aplikasi menggunakan pengukuran kemiripan Euclidean Distance dengan nilai threshold=7 diperoleh akurasi presisi sebesar 61% pada data pelatihan 168 dan data uji coba 32 dengan 10 citra yang ditampilkan.

Kata Kunci : Tekstur, Sistem Perolehan Citra berbasis Isi, Gray Level Difference Method, Euclidean Distance.

Abstract

Batik is a craft that has high artistic value and has become part of the culture of Indonesia for a long time. Batik in Indonesia has a wide range of batik texture, color batik and batik patterns. Current text-based image search is no longer effective because of the subjective assessment of the user in representing an image. What is needed a system that can handle image search using the query form or image of the so-called Content-based Image Acquisition System or Content Based Image Retrieval. This study using texture features as similarity search process of batik images of eight different classes, namely: Cirebon, Bali, Jakarta, Pamekasan, Sumenep, Yogyakarta, Solo, and Pekalongan as content-based image acquisition objects. The system is built with the main process is the extraction of texture features using the Gray Level Difference Method using the four cardinal directions. The results of feature extraction will be measured using the method of Euclidean distance similarity Distance. Of a pilot application using Euclidean Distance similarity measurement threshold = 7 with the value obtained by 61% precision accuracy on 168 training data and trial data 32 by the number of displayed image 10.

Keywords: Texture, Content-based Image Acquisition System, Gray Level Difference Method, Euclidean Distance.

CI - 32

PENDAHULUAN

Sistem pencarian citra yang ada sekarang ini pada umumnya menggunakan metode tradisional dalam menyimpan dan mengelola citra [1]. Metode tradisional yang biasa digunakan dalam pencarian citra sudah tidak mungkin lagi digunakan, misalnya pencarian citra dengan kata kunci (teks) karena nama dari sebuah file tidak dapat mempresentasikan isinya. Sebagai contoh bila ingin mencari citra kuda, dimana citra kuda itu mempunyai banyak informasi antara lain mungkin yang akan dihasilkan adalah makanan kuda, atau area pacuan kuda, atau informasi lain yang ada unsur kuda dan yang pasti suatu citra itu bisa berbicara seribu kata. Selain itu adanya persepsi manusia yang berbeda- beda terhadap suatu citra dapat mengakibatkan hasil pencarian citra tidak sesuai dengan yang diinginkan.

Untuk menghindari pencarian citra dengan kata kunci, maka digunakan metode lain sebagai pengganti atau ditambahkan pada sistem kata kunci yaitu sistem perolehan citra berbasis isi (SPCI) atau Content Based Image Retrieval (CBIR) yang mencari citra hanya berdasarkan informasi yang ada pada citra. Informasi dari citra yang didapatkan merupakan ciri dari citra, pada level primitif dapat berupa warna, bentuk, tekstur [2].

CBIR merupakan teknologi pencarian citra dengan membandingkan citra yang ada pada contoh citra dengan yang ada pada basis data citra (Query By Example). CBIR dilakukan dengan membandingkan nilai jarak citra query dengan citra pada basis data (image distance measure). Pengukuran nilai jarak citra dapat dikelompokkan dengan tiga kelas utama yaitu pertama kemiripan warna, kedua kemiripan pada bentuk dan yang ketiga kemiripan pada tekstur [3].

Penelitian ini menentukan fitur tekstur batik dalam SPCI dengan mendapatkan atribut-atribut dari metode statistical Gray Level Difference Method (GLDM), yaitu Contrast, Angular Second Moment (ASM), Entropy, Inverse Different Moment (IDM), Mean dan menghitung kemiripan antara citra query dengan citra yang ada dalam basis data dengan menggunakan metode Euclidean Distance. Data citra yang digunakan untuk objek penelitian adalah beberapa citra batik dari delapan kelas, yaitu: Bangkalan,

Pamekasan,        Sumenep,            Yogyakarta,

Pekalongan, Solo, Cirebon, dan Bali. Citra query dan citra basis data yang digunakan berupa citra statis sebanyak 200 citra dengan format *bmp dan berukuran 200x200 pixel.

METODE

Gray Level Difference Method (GLDM)

Pada Gray Level Difference Method, peristiwa dari perbedaan mutlak dihitung antara sepasang derajat keabuan yang terpisah oleh jarak tertentu dengan arah tertentu. Maka akan dihasilkan sebuah kemungkinan dari kumpulan variable distribusi. Misal I(m, n) sebagai fungsi intensitas gambar. Untuk setiap pergeseran 6=(Am, An), I`(m, n)=| I(m, n)¬ I(m+ Am, n+ An)|, untuk Am dan An bernilai integer. Misal g(•|6) sebagai estimasi ”probability density function” dari I`(m, n), g(i|6)=#(I`(m, n)=i). Jika terdapat derajat keabuan m, ”probability density function” adalah vektor berdimensi m yang mana komponen ke-i adalah probabilitas bahwa I`(m, n) akan memiliki nilai i. Pada citra digital fungsi intensitas I(m, n) adalah fungsi diskrit, oleh karena itu g(•|6) dihitung sebagai banyaknya nilai I`(m, n) yang terjadi. Jika pergeseran menggunakan empat arah utama (Ө=0°,45°,90°,135°) dengan jarak 1 (δ=1) [4].

Terdapat beberapa ciri tekstural yang dapat diekstraksi darai Gray Level Difference Method diantaranya adalah: Contrast, Angular Second Moment, Entropy, Inverse Difference Moment, dan Mean [4].

a. Contrast

Contrast menunjukkan ukuran penyebaran (momen inersia) elemen-elemen matriks citra. Contrast menentukan kecerahan pada citra. Semakin besar nilai contrast maka akan terlihat tingkat kecerahannya.

CON = E[i2 x P′(g(ij6, 0))] (1)

b.            Angular Second Moment (ASM)

Angular Second Moment menunjukkan ukuran sifat homogenitas citra. Nilai ASM besar memiliki variasi bentuk yang homogen atau tidak bervariasi.

AS M = E[P′(g(ij6,0)2)]      . (2)

c.            Entropy

Entropy menyatakan        ukuran

ketidakteraturan bentuk atau pola. Nilai entropy besar memiliki tingkat keteracakan homogen (teratur) dan bernilai kecil jika struktur citra tidak teratur

ENT =

− E[P′(g(i|’, “)) " 048 {U′(8(&|’, “))}] ...(3)

d. Invers Difference Moment (IDM)

Invers Difference Moment menunjukkan kehomogenan citra yang berderajat keabuan sejenis. Citra homogen akan memiliki nilai Inverse Difference Moment (IDM) yang besar.

—‡ A = ∑[U′#8(&|’, “)%/ (&2 + 1)] .... (4)

e. Mean

Menunjukkan ukuran dispersi dan menentukan tekstur permukaan dari suatu citra. Semakin besar nilai mean maka ukuran dispersi besar dan menghasilkan permukaan tekstur kasar.

Aˆ”$ = ∑[& " U′(8(&|’, “))]            (5)

dengan :

I(m, n) = fungsi intensitas gambar CON = Contrast

ASM = Angular Second Moment ENT = Entropy

IDM = Invers Difference Moment MEAN = Mean

i = selisih antara sepasang derajat keabuan δ = jarak pergeseran

P’ = probabilitas

Ө = arah pergeseran

g(iJδ,Ө) = estimasi probability density function

Euclidean Distance

Tahap terakhir dalam sistem temu kembali adalah pencarian kemiripan antara citra query dengan fitur dari citra yang sudah disimpan pada basis data. Dalam program aplikasi pencarian citra berdasarkan tekstur, similarity measure yang digunakan adalah Euclidean Distance. Pencarian dari suatu sistem pencarian citra secara signifikan. Euclidean Distance merupakan teknik yang paling sederhana untuk menghitung jarak di antara dua vektor. Misalkan diberikan dua buah feature vector p dan q, maka jarak di antara dua feature vector p dan q ditentukan sebagai berikut [1].

P = ( p1, p2, ...., pn)

Q = (q1, q2, ..., qn)

6 = ˜(2~ − ~~~~  + (2 − ~~~~ + ⋯ + (2n − ~n)2

= ˜∑~ (2& − ~&~~             (6)

&+~

dengan

d = ukuran jarak antara query citra P dan citra Q yang ada di dalam database.

p = feature vector pada image P

q = feature vector pada image Q

Desain Sistem

Dalam penelitian ini dibangun sistem perolehan citra berbasis isi dengan ekstraksi fitur tekstur menggunakan metode Gray Level Difference Method dengan proses pencocokan menggunakan metode Euclidean Distance. Sistem ini menggunakan model QBE (Query By Example) yaitu pengguna memberi masukan berupa citra kemudian sistem akan mencari citra- citra lain yang mirip dengan citra query. Proses pertama untuk mendapatkan feature vector suatu citra adalah konfersi citra true color ke grayscale, setelah itu dilakukan proses pengambilan nilai pixel dilanjutkan dengan proses kuantisasi pada citra grayscale. Dari hasil proses kuantisasi dilakukan proses ekstraksi fitur tekstur dengan menghitung empat arah GLDM (00, 450, 900 dan 1350) dan lima fitur GLDM (Contrast, Angular Second Moment (ASM), Entropy, Inverse Difference Moment (IDM), dan Mean). Bobot arah dan fitur inilah yang disebut hasil dari proses ekstraksi fitur. Proses-proses diatas dilakukan baik pada citra query maupun pada proses pembuatan Feature Vector citra basis data. Kemudian dilakukan proses pencocokan (matching) antara citra query dengan Feature vector citra basis data menggunakan metode pencarian nilai jarak yaitu Euclidean Distance. Proses ini bertujuan untuk mencari citra yang mempunyai fitur yang mirip dengan citra query. Sebagai hasil dari sistem maka pada dialog aplikasi menampilkan 10, 20 dan 30 citra terurut mulai dari yang paling mirip sampai yang tidak mirip. Blok diagram dari sistem dapat dilihat pada Gambar 1.

Garis besar sistem dibagi menjadi dua yakni proses pembuatan Feature Vector citra basis data dan proses pencocokan / pencarian citra. Hasil akhir dari dari pencarian citra tersebut adalah menampilkan 10, 20 dan 30 citra yang memiliki tingkat kecocokan paling tinggi yang terdapat dalam basis data. Berikut perincian proses pembuatan Feature Vector citra basis data:

a.            Citra masukan berupa citra statis dengan format .bmp

b.            Citra masukan diubah dari warna RGB ke grayscale

.Gambar 1. Desain sistem CBIR secara umum

c.            Pengambilan nilai piksel grayscale kemudian dilakukan proses kuantisasi untuk menyederhanakan nilai piksel citra.

d.            Kemudian dilakukan proses ekstraksi fitur tekstur dengan menggunakan Gray Level Difference Method

e.            Hasil ekstraksi fitur tekstur disimpan dalam basis data berbasis file di dalam folder CBIR.

Untuk proses pencocokan atau pencarian citra dilakukan proses sebagai berikut :

a.            Citra masukan berupa citra statis dengan format *bmp.

b.            Citra masukan diubah dari warna RGB ke grayscale

c.            Pengambilan nilai piksel grayscale kemudian dilakukan proses kuantisasi untuk menyederhanakan nilai piksel citra.

d.            Kemudian dilakukan proses ekstraksi fitur tekstur dengan menggunakan Gray Level Difference Method.

e.            Hasil ekstraksi fitur tekstur masukan citra kemudian dilakukan pencocokan dengan fitur tekstur yang terdapat dalam basis data dengan menggunakan Euclidean Distance

f.            Menampilkan citra yang mirip dengan citra masukan.

HASIL DAN PEMBAHASAN

Pada uji coba sistem ini data yang digunakan pada citra query dan proses pembuatan Feture Vector pada basis data berupa citra dengan format *bmp sebanyak 200 citra yang terdiri dari 8 kelas citra yaitu:

Bangkalan,          Pamekasan,        Sumenep,

Yogyakarta, Pekalongan, Solo, Cirebon, dan Bali.

Skenario uji coba merupakan perlakuan yang dilakukan untuk melakukan uji coba citra

query terhadap citra        basis data untuk

mengetahui tingkat pengenalan citra query. Skenario uji coba yang dilakukan seperti ditunjukkan pada Tabel 1.

Tabel 1 Skenario Uji Coba

Jumlah Skenario citra yang Uji Coba ditampilkan

10 Citra 1

120

(15 x 8)  8)            80

(10 x

Sebagai contoh, Gambar 2 merupakan uji coba pada skenario 5 dengan data pelatihan 184 (23 x 8) dan data uji coba 16 (2 x 8) dengan citra query merupakan bagian dari delapan kelas citra yang tersedia di basis data.

Citra query:

Gambar 2 Pekalongan_25.bmp

Pada Gambar 3 menampilkan 10 citra dalam basis data yang mirip dengan citra query Pekalongan_25.bmp pada skenario 4, sehingga hasil yang diperoleh dari nilai Recall 0,11 dan Precision 0,5.

Gambar 3 Percobaan citra query Pekalongan_25.bmp

Pada Gambar 4 menampilkan 20 citra dalam basis data yang mirip dengan citra query Cirebon_23.bmp pada skenario 9, sehingga hasil yang diperoleh dari nilai Recall 0,14 dan Precision 0,7.

Gambar 4 Percobaan citra query Cirebon_23.bmp

Setelah dilakukan uji coba terhadap sistem perolehan citra berbasis isi, Tabel 2, Tabel 3 dan Tabel 4 merupakan hasil rata- rata nilai recall dan precision berdasarkan tekstur dengan ukuran citra 200x200 piksel dan jumlah citra yang ditampilkan 10, 20, 30 dengan nilai threshold=7. Tabel 5 merupakan hasil rata-rata tingkat pengenalan dengan nilai threshold = 5 dan threshold =7 pada skenario 15.

CI - 36

Pada Tabel 2 menunjukkan hasil rata-rata nilai recall dan precision dengan nilai threshold=7 dengan 10 citra yang ditampilkan.

Tabel 2 Hasil rata-rata tingkat Pengenalan dengan jumlah citra yang ditampilkan 10

Pada Tabel 3 menunjukkan hasil rata-rata nilai recall dan precision dengan nilai threshold=7 dengan 20 citra yang ditampilkan.

Tabel 3 Hasil rata-rata tingkat Pengenalan dengan jumlah citra yang ditampilkan 20

Pada Tabel 4 menunjukkan hasil rata-rata nilai recall dan precision dengan nilai threshold=7 dengan 30 citra yang ditampilkan.

Tabel 4 Hasil rata-rata tingkat Pengenalan dengan jumlah citra yang ditampilkan 30

Tabel 5 Hasil rata-rata tingkat Pengenalan dengan nilai threshold = 5 dan threshold = 7

Pada Tabel 5 merupakan tingkat pengenalan dan hasil analisis dengan nilai threshold = 5 pada skenario 15 dengan jumlah data pelatihan 184 citra (23x8), data uji coba 16 citra (2x8) dan jumlah citra yang ditampilkan 30 memiliki nilai recall 0,16 dan nilai precision 0,53. Sedangkan tingkat pengenalan dan hasil analisis dengan nilai threshold =7 memiliki nilai recall 0,17 dan nilai precision 0,54. Pada proses perhitungan kemiripan antara citra query dan citra basis data digunakan nilai threshold =7 karena memiliki tingkat kecerahan yang lebih besar dan tingkat keteraturan yang tinggi pada citra Pekalongan_25. Sehingga tingkat pengenalan citra lebih baik dengan menggunakan nilai threshold= 7.

SIMPULAN

Pada sistem pengenalan citra berdasarkan tekstur berbasis Gray Level Difference Method didapatkan beberapa ciri tekstur yaitu Contrast, Angular Second Moment (ASM), Entropy, Inverse Different Moment (IDM), dan Mean. Pengukuran nilai kemiripan Euclidean Distance dengan nilai threshold = 7 dapat digunakan untuk mengenali citra dengan nilai precision terbaik sebesar 61%. Tingkat pengenalan dengan nilai threshold = 5

memiliki nilai precision lebih kecil. Jumlah citra yang ditampilkan sangat berpengaruh saat proses pengenalan citra terhadap precisionnya. Semakin banyak jumlah citra yang ditampilkan maka nilai precision semakin kecil dan nilai recall semakin besar. Jumlah data pelatihan terbaik pada jumlah data pelatihan 168 citra dan jumlah data uji coba 32 citra dengan10 jumlah citra yang ditampilkan.

DAFTAR PUSTAKA

[1]          Isa, S. M. Aplikasi Image Retrieval

Berdasarkan       Tekstur  dengan

Menggunakan Transformasi Haar Wavelet. Seminar Nasional Sistem dan Informatika. SNSI : 06-039. 221-226. 2007.

[2]          Bagus, B. Image Database Menggunakan Sistem Content Based Image Retrieval dengan Ekstraksi Fitur Terstruktur. Tugas Akhir. Surabaya: Institut Teknologi Sepuluh Nopember. 2007.

[3]          Ramadijanti, N. Content Based Image Retrieval Berdasarkan Ciri Tekstur Menggunakan Wavelet. Seminar Nasional Aplikasi Teknologi Informasi. ISSN: 1907-5022. 49-54. 2006.

[4]          Zahab, N. M. Analisis Tekstur Parket Kayu dengan Menggunakan Metode Statistikal Gray Level Difference Method. Tugas Akhir. Depok : Universitas Gunadarma. 2009.

IMPLEMENTASI SUPPORT VECTOR MACHINES UNTUK PENCARIAN INFORMASI BUKU DI PERPUSTAKAAN DAERAH BANDUNG PROVINSI JAWA BARAT

Nelly Indriani Widiastuti, Riki Hidayat

Teknik Informatika UNIKOM, Jl. Dipati Ukur no. 102-116 Bandung

E-Mail: indiwidi@gmail.com, riki.hidayat.91@gmail.com

Abstrak

Badan Perpustakaan dan Kearsipan Daerah (BAPUSIPDA) adalah lembaga

perpustakaan daerah ditingkat Provinsi Jawa Barat. Untuk memperoleh informasi buku

yang diperlukan, pengunjung perpustakaan harus mengetahui identitas buku tersebut.

Berdasarkan permasalahan tersebut perlu dikembangkan sistem pencarian informasi buku yang dapat menemukan informasi buku sesuai dengan kebutuhan pengunjung secara dinamis. Sistem tidak hanya terpaku kepada identitas buku seperti judul, pengarang, penerbit, dan lain-lain, melainkan gambaran kebutuhan pengunjung terhadap buku. Selain itu, pengunjung juga dapat menentukan relevan atau tidaknya informasi buku sebagai feedback untuk sistem agar sistem bisa menemukan informasi buku yang lebih relevan menurut pengunjung. Sistem ini dibangun dengan mengimplementasikan metode vector space model dan support vector machines.

Hasil penelitian dapat disimpulkan bahwa sistem pencarian informasi buku dapat mempermudah pengunjung untuk mencari informasi buku yang dibutuhkan.

Kata kunci : sistem pencarian informasi buku, vector space model, support vector machines

Abstract

Badan Perpustakaan dan Kearsipan Daerah (BAPUSIPDA) is the local library level, West Java Province. To obtain the necessary information books, library patrons visitors have to know the identity of the book.

Based on these problems, books information retrieval systems must be developed that can find information about the books that fit the needs of visitors dynamically. System, not only identity of the book such as title, author, publisher, etc., but the picture of the needs of visitors to the book. In addition, visitors can also determine whether or not the information relevant to the user as a feedback to the system so that the system can find the book more relevant information by visitors. The system is built by implementing methods of vector space model and support vector machines.

The research concluded that information retrieval systems to facilitate visitor books to find the information needed books.

Keyword : books Information Retrieval System, vector space model, support vector machines

PENDAHULUAN

Perpustakaan adalah salah satu tempat untuk memperoleh ilmu dengan cara yang sangat murah. Pengunjung hanya perlu mendaftarkan diri untuk dapat meminjam beberapa buku dengan nyaris tanpa biaya. Badan Perpustakaan dan Kearsipan Daerah (BAPUSIPDA) adalah perpustakaan daerah Bandung JawaBarat. Saat ini jumlah buku di

perpustakaan daerah tersebut sudah mencapai kurang lebih 180.000 eksemplar per tanggal 18 April 2012. Meskipun demikian dari sekian banyaknya jumlah buku yang ada di perpustakaan tersebut tetap masih belum bisa memenuhi kebutuhan masyarakat.

Untuk memperoleh buku yang diperlukan seseorang dapat datang langsung ke perpustakaan. Tetapi berdasarkan hasil wawancara terhadap beberapa pengunjung perpustakaan dapat disimpulkan bahwa untuk

mencari informasi buku yang diinginkan, hanya sedikit pengunjung yang sudah mengetahui identitas buku (judul, pengarang, subjek, dan lain-lain). Kebanyakan pengunjung justru tidak mengetahui informasi yang cukup tentang identitas buku yang akan dicari melainkan hanya mengetahui gambaran akan kebutuhannya mengenai informasi yang dibutuhkan terhadap buku.

Sistem pencarian yang ada di perpustakaan tidak dapat memecahkan solusi untuk permasalahan yang sudah dipaparkan sebelumnya karena masukan terhadap sistem masih sangat spesifik yaitu judul dan penulis buku tersebut. Berdasarkan uraian masalah tersebut perlu dikembangkan sistem pencarian informasi buku yang dapat menemukan informasi buku sesuai dengan gambaran kebutuhan pengunjung yang dinamis.

Information Retrieval System (IRS)

Information Retrieval (IR) atau pencarian informasi dapat didefinisikan sebagai upaya untuk menemukan materi atau dokumen yang sifatnya tidak terstruktur (misalnya teks) yang memenuhi kebutuhan informasi dari jumlah data yang sangat besar dalam sebuah sistem. Salah satu pengertian IR menurut Bill Frakes dan Ricardo Yates[1] adalah "sub bidang dari ilmu komputer yang mempelajari tentang pengumpulan data dan temu kembali dokumen". Dalam perkembangan selanjutnya IR dikembangkan menjadi automated IR systems yang menangani temu kembali data secara otomatis dalam jumlah data yang besar.

Tujuan dari sistem IR adalah memenuhi kebutuhan informasi pengguna dengan me-retrieve semua dokumen yang mungkin relevan, pada waktu yang sama me-retrieve sesedikit mungkin dokumen yang tidak relevan. Sistem IR yang baik memungkinkan pengguna menentukan secara cepat dan akurat apakah isi dari dokumen yang diterima memenuhi kebutuhannya. Agar representasi dokumen lebih baik, dokumen-dokumen dengan topik atau isi yang mirip dikelompokkan bersama¬sama [2].

Keefektifan dari temu kembali informasi yang diinginkan tergantung pada dua hal mendasar yaitu perilaku pengguna dan logical view. Perilaku pengguna berhubungan

dengan kegiatan pengguna menentukan query yang sesuai dengan informasi yang diinginkan. Logical view adalah representasi dokumen dalam bentuk koleksi keseluruhan kata-kata yang dikandungnya. Efektifitas dengan logical view dimana sistem harus dapat mereduksi kata yang disimpan dan mentransformasi logical view dari full text menjadi bentuk indeks. Hal ini dilakukan dengan meng-eliminasi stoplist (kata-kata yang terlalu umum seperti kata sandang, kata sambung, kata ganti, dll) dan melakukan proses stemming (pengubahan bentuk imbuhan ke bentuk dasar). Lebih jauh lagi adalah penggunaan metode-metode kompresi teks.

Gambar 1. Arsitektur IRS[3]

Proses yang ada didalam IRS dapat dilihat pada Gambar 1. Secara umum proses IRS adalah preprocessing, indexing, searching dan ranking.

Vector Space Model (VSM)

VSM adalah model sistem temu balik informasi yang mengibaratkan masing¬masing query dan dokumen sebagai sebuah vektor n-dimensi. Tiap dimensi pada vektor tersebut diwakili oleh satu term. Term yang digunakan biasanya berpatokan kepada term yang ada pada query, sehingga term yang ada pada dokumen tetapi tidak ada pada query biasanya diabaikan.

Secara umum prosedur VSM dibagi menjadi tiga tahap [4].

1.            Document           indexing yaitu kumpulan

term yang telah diekstrak dari teks dokumen.

2.            Weighting yaitu pembobotan dari term yang sudah di-indeks untuk meningkatkan kualitas pencarian.

3. Ranking document berdasarkan tingkat kemiripan antara query dengan dokumen.

Gambar 2. Vector Space Model[5]

Contoh dari model ruang vektor tiga dimensi untuk dua dokumen D1 dan D2, satu query pengguna Q1, dan tiga term T1, T2 dan T3 diperlihatkan pada gambar 2.

Support Vector Machines (SVM)

Rancangan dasar dari sistem IR dapat ditingkatkan untuk menaikkan presisi dan recall serta memperbaiki matriks term-document. Isu pertama sering diselesaikan

menggunakan    mekanisme         relevance

feedback. Beberapa term ditambahkan ke dalam query awal agar dapat menemukan dokumen yang lebih relevan. Relevance feedback dapat dikerjakan secara manual maupun otomatis. Pada pendekatan manual, pengguna mengidentifikasi dokumen yang relevan dan term baru dipilih secara manual atau otomatis. Pada pendekatan otomatis,

dokumen             relevan  diidentifikasi

menggunakan dokumen yang berada di rangking paling atas, kemudian term-term baru dipilih secara otomatis.

Takashi Onoda,  dkk         dalam

penelitiannya yang berjudul Relevance Feedback Document Retrieval using Support Vector Machines, telah berhasil melakukan peningkatan kualitas pencarian dengan memodifikasi vektor query.

Support Vector Machines (SVM) adalah suatu teknik yang relatif baru (1992) untuk melakukan prediksi, baik dalam kasus klasifikasi maupun regresi, yang sangat populer belakangan ini. SVM berada dalam satu kelas dengan Artificial Neural Network (ANN) dalam hal fungsi dan kondisi permasalahan yang bisa diselesaikan. Keduanya masuk dalam kelas supervised learning. SVM selalu mencapai solusi yang sama untuk setiap running. Dalam teknik

ini, SVM berusaha untuk menemukan hyperplane (pemisah/classifier) yang optimal yang bisa memisahkan dua set data dari dua kelas yang berbeda.

Dalam hal ini fungsi pemisah yang dicari adalah fungsi linier. Fungsi ini bisa didefinisikan sebagai g(x) := sgn(f(x)) dengan f(x) = wT x + b. Teknik SVM berusaha menemukan fungsi hyperplane terbaik diantara fungsi yang tidak terbatas jumlahnya untuk memisahkan dua macam obyek. Hyperplane terbaik adalah hyperplane yang terletak di tengah-tengah antara dua set obyek dari dua kelas. Mencari hyperplane terbaik ekuivalen dengan memaksimalkan margin atau jarak antara dua set objek dari kelas yang berbeda.

Untuk menentukan hyperplane-pendukung (supporting hyperplane) dari kelas +1 (wx1 + b = +1) digunakan rumus (1) dan rumus (2) untuk menentukan hyperplane-pendukung dari kelas -1(wx2 + b = -1)

wx1 + b = +1       (1)

wx2 + b = -1        (2)

Margin antara dua kelas dapat dihitung dengan mencari jarak antara kedua hyperplane-pendukung dari kedua kelas. Rumus (3) digunakan untuk menghitung margin.

(wx1 + b = +1) - (wx2 + b = -1)       (3)

= w(x1 – x2 ) = 2

= W

(IIWII (x1 − x2)) = 2

IIWII

Gambar 3 memperlihatkan bagaimana SVM bekerja untuk menemukan suatu fungsi pemisah dengan margin yang maksimal. Dengan memperbesar margin bisa meningkatkan probabilitas pengelompokkan suatu data secara benar.

ANALISA KEBUTUHAN DATA

Sistem yang dikembangkan adalah sistem pencarian hanya jika data pencarian tersedia. Data pencarian adalah identitas buku, dalam penelitian ini data yang dibutuhkan berupa judul, pengarang dan deskripsi.

Gambar 3. Mencari Fungsi Pemisah Optimal yang dapat Memisahkan Data Secara Linear[6]

Berdasarkan hasil analisa beberapa golongan buku, maka diperoleh karakteristik teks dari data buku yang perlu diperhatikan adalah sebagai berikut :

a.            Bahasa

Terdapat beragam bahasa yang digunakan dalam buku yang ada di perpustakaan. Pada penelitian ini data buku yang digunakan merupakan data buku dengan teks berbahasa Indonesia dan bahasa Inggris.

b.            Deskripsi Buku

Untuk mendapatkan deskripsi buku, dapat dilihat dari cover belakang buku. Alternatif lain yang bisa dijadikan deskripsi buku yaitu kata pengantar atau

daftar isi dari data buku.

c.            Jenis Kata

Terdapat beragam jenis kata yang ada data buku, yaitu :

1)            kata sesuai EYD,

2)            kata yang biasa digunakan sehari-hari,

3)            kata berimbuhan,

4)            kata dasar

ANALISA PROSES

Sistem dibagi menjadi dua proses penting, yaitu proses pencarian dan proses pengolahan data. Proses pencarian dapat digunakan oleh pengunjung untuk melakukan proses pencarian informasi buku dan lihat deskripsi dari buku itu sendiri. Proses pencarian dalam penelitian ini adalah proses pencarian dinamis, dimana pengguna juga dapat menentukan sesuai atau tidak nya query dengan informasi buku yang

ditampilkan dari hasil pencarian, setelah itu sistem akan mengklasifikasikan seluruh data buku yang terdapat dalam database kedalam kategori relevan dan tidak relevan. Data buku yang ditampilkan adalah data buku yang masuk dalam kategori relevan.

Proses pengolahan data, khusus digunakan oleh operator untuk melakukan proses pengolahan (tambah, ubah, lihat detail, cari, dan hapus) data buku, pengolahan (tambah dan ubah) data golongan, dan melakukan optimisasi pada sistem pencarian. Gambar 4. Berikut ini adalah gambaran dari aktivitas sistem pencarian informasi buku :

Pengunjung         Sistem

               _                           

Masukkan                                          Mencari dan Memberi Peringkat Data

Buku Berdasarkan Ukuran Kemiripan        

               Query                                 

                                            

                              1            

                              Menampilkan Maksimal 10 Informasi

Buku dengan Ukuran Kemiripan Tertinggi

Cek Data              Buku yang                                        

               Relevan

~                                          

                                                           

                                             Mengklasifikasi Seluruh Data Buku

Berdasarkan Hasil Cek Pengunjung            

                                                           

                                             1            

                                             Menampilkan Informasi Buku Hasil

Klasifikasi           

                                             0            

Gambar 4. Aktivitas Pencarian Informasi Buku

Analisa Keyword

Keyword yang dimaksud dalam penelitian ini adalah data buku yang merupakan gabungan dari judul, pengarang dan deskripsi buku yang sudah mengalami proses tokenizing, filtering dan stemming. Metode stemming yang digunakan dalam penelitian ini adalah Nazief & Adriani. Setiap data buku mempunyai keyword-nya masing¬masing yang akan digunakan sebagai poros data untuk proses pencarian informasi buku. Gambar 5. adalah gambaran proses pembuatan keyword.

Setelah keyword diperoleh, selanjutnya adalah tahapan yang ada dalam VSM yaitu

1. Memberikan bobot pada keyword. Pembobotan adalah proses merubah

keyword dan query menjadi bentuk vektor.

2.            Normalisasi

3.            Mengukur kemiripan yang dilakukan suatu perhitungan untuk mendapatkan ukuran kemiripan antara dokumen dengan query.

4.            Ukuran ini hasil pengukuran kemiripan digunakan untuk perankingan dokumen sesuai dengan kemiripan relevansinya terhadap query.

5.            Terakhir, sejumlah maksimal 10

dokumen,            ditampilkan         kepada

pengunjung[7].

Operator             Sistem

T            

Masukan Data Buku        

               Cek Isi Data

              

               [Ada Field Kosong]

               [Tidak Ada Field

               Kosong]

               Simpan Data Buku

              

               Tokenisasi dan Hapus

               Stopword

              

               "             Stemming            .

              

               Simpan Keyword

              

               Menampilkan Pesan

               Konfirmasi

              

Gambar 5. Pembuatan Keyword

Analisa Pelatihan

Pada proses pelatihan SVM bertujuan untuk menemukan vektor α dan konstanta b. Dalam proses pelatihan dibutuhkan satu set input-output data atau dalam kasus ini dibutuhkan dokumen relevan dan dokumen tidak relevan dimana penilaian relevan atau tidaknya suatu dokumen ditentutkan oleh pengguna. Dokumen-dokumen relevan diberi label 1 dan dokumen yang tidak relevan diberi label -1.

Sebagai contoh kasus, digunakan dokumen-dokumen yang terdapat dalam contoh kasus VSM dan diasumsikan D1 dan D2 sebagai dokumen relevan menurut pengguna dan D3 sebagai dokumen tidak

relavan. Maka, satu set input-output data dalam pelatihan bisa dilihat di tabel 1.

Tahap selanjutnya yaitu melakukan

kernelisasi           menggunakan    fungsi

polynomial kernel pangkat 2 yang didefinisikan sebagai K(xi , xi ) = (xi + xi’+12 ).

Tabel 1. Data Latih

               D1          D2          D3

x1           0,208     0             0,163

x2           0,564     0             0

x3           0,564     0             0

x4           0,564     0             0

x5           0             0,408     0

x6           0             0,408     0

x7           0             0,408     0

x8           0             0,408     0

x9           0             0,408     0

x10         0             0,408     0

x11         0             0             0,441

x12         0             0             0,441

x13         0             0             0,441

x14         0             0             0,441

x15         0             0             0,441

y             1             1             -1

Analisa Klasifikasi

Takashi Onoda, dkk[9], mengusulkan

penggunaan        SVM       sebagai

pengklasifikasian dokumen dengan tahap¬tahap berikut ini :

1.            Inisialisasi Pencarian

Hasil pencarian ini diperoleh dari metode VSM dengan cara menampilkan N peringkat teratas dokumen yang memiliki kemiripan terhadap query.

2.            Penilaian Dokumen oleh Pengguna Pengguna mengevaluasi N peringkat teratas dokumen dan mengklasifikasi dokumen tersebut ke dalam dokumen

relevan  atau tidak relevan. Setelah

pengguna selesai mengevaluasi, relevan dokumen dan dokumen yang tidak relevan diberi label +1 dan -1.

3.            Penentuan Optimal Hyper-plane

Optimal hyperplane          untuk

mengklasifikasikan relevan dan tidak relevan suatu dokumen dihasilkan oleh metode SVM.

4.            Diskriminasi Dokumen dan Pencarian Informasi

Dokumen yang diperoleh dari langkah 1 dipetakan ke dalam ruang fitur, SVM mengklasifikasikan dokumen-dokumen tersebut sebagai dokumen yang relevan

dan tidak relevan. Kemudian sistem akan memilih dokumen-dokumen berdasarkan jarak optimal hyperplane dan margin area.

5. Menampilkan Hasil Akhir dari Pencarian Dokumen yang didapat, di beri peringkat sesuai dengan jarak antara dokumen dengan fungsi pemisah hyperplane, dimana fungsi pemisah ini ditetapkan oleh SVM. Dokumen yang didapat di tampilkan berdasarkan peringkat.

ANALISA FUNGSIONAL

Mendefinisikan analisa kebutuhan fungsional dan operasional sistem dengan

mendefinisikan   skenario               penggunaan

aplikasi. Pada aplikasi ini yang akan bertindak sebagai aktor yaitu pengunjung dan operator. Operator berperan mengelola

seluruh  konten  perangkat            lunak.

Pengunjung berperan dalam melakukan proses pencarian.

Analisis yang dilakukan dimodelkan dengan menggunakan UML (Unified Modeling Language). Tahap-tahap pemodelan dalam analisa tersebut antara lain identifikasi aktor, use case diagram, skenario usecase, activity diagram, sequence diagram dan class diagram. Dalam jurnal yang ditampilan hanya usecase dan activity diagram.

Gambar 6. Use Case Diagram Sistem Pencarian

Informasi Buku

Untuk memperlihatkan hubungan-hubungan yang terjadi antara aktor-aktor dengan usecase dalam sistem dapat dilihat pada gambar 6. Operator dalam usecase adalah petugas perpustakaan yang bertugas memperbarui data buku,

Proses yang terjadi dalam pencarian informasi dalam sistem ini dapat dilihat pada gambar 7.

Pengunjung         Sistem

S                           

Masukan                                           

               Query    Cek Query          

                              [tidak kosong]   

                              ~             [kosong]              i             

                              Menampilkan Pesan         Melakukan Proses           

                              Kesalahan            Tokenization dan              Filtering

              

               Melakukan          Proses

               Stemming           

                             

                             

               Hitung Bobot Query         Baca Bobot Keyword      

                             

               [Data Buku]       

               Hitung Similiarity              /•A~

                             

               Menampilkan Pesan/      

               Data Tidak Ditemukan     [Tidak Ditemukan]           

                             

               [Ditemukan]      

               Menampilkan    

                             

               Informasi Buku  

                             

Gambar 7. Pencarian Data Buku

Aktivitas pencarian data buku lebih lanjut pada gambar 8. Merupakan aktivitas pengunjung untuk menemukan informasi buku yang lebih relevan dengan cara memilih beberapa informasi buku hasil dari proses pencarian data buku yang relevan berdasarkan penilaian pengunjung.

Aktivitas Optimisasi pada gambar 9. merupakan aktivitas operator untuk menghitung bobot dan normalisasi data buku serta membuat data tes untuk setiap data buku. Tahapan-tahapan aktivitas yang dilakukan pada saat optimisasi adalah :

Gambar 9. Optimasi Sistem Pencarian

IMPLEMENTASI DAN PENGUJIAN

Perangkat keras yang digunakan pada saat mengimplementasikan perangkat lunak dari Sistem Pencarian Informasi Buku di Perpustakaan Daerah Provinsi Jawa Barat adalah sebagai berikut :

1.            Processor Intel(R) Core i3 2.1 GHz,

2.            RAM 3GB,

3.            VGA ATI Radeon HD 530v,

4.            Hard Disk 320GB,

5.            Monitor 14”, dan

6.            Modem berkecepatan 153Kbps.

Perangkat lunak yang digunakan saat mengembangkan Sistem Pencarian Informasi Buku di Perpustakaan Daerah Provinsi Jawa Barat adalah sebagai berikut :

1.            Sistem operasi Windows 7 Professional,

2.            Bahasa pemrograman PHP 5.3.0,

3.            Database MySQL Server 5.0.37,

4.            Browser Maxthon 3.4.2.2000,

5.            Macromedia Dreamweaver CS5, dan

6.            UML Modeler Power Designer 12.

File-file yang berhasil diimplementasikan terdiri dari file-file tabel yang dibuat denganSQL, file kelas metode dan file antarmuka.

Pengujian perangkat lunak Sistem Pencarian Informasi Buku di Perpustakaan ini menggunakan dua data uji yaitu data buku dan data golongan. Pengujian dilakukan dengan metode Black Box untuk menguji fungsi-fungsi yang dapat dilihat pengguna. Metode Whitebox untuk menguji proses yang ada dalam metode SVM.

Dari        hasil       pengujian            proses

klasifikasi yang dilakukan, maka didapat kesimpulan bahwa seluruh node yang ada pada setiap independent path telah dikerjakan , serta tidak terjadi pengulangan tak terhingga.

Selain pengujian fungsional, respon pengguna juga diperlukan untuk mengetahui kepuasan pengguna terhadap sistem. Hasil dari pengujian beta dapat disimpulkan bahwa sistem pencarian informasi buku yang telah dibangun dapat membantu pengguna khususnya pengunjung perpustakaan untuk menemukan buku yang dibutuhkan, karena mudah untuk digunakan dan cukup cepat dalam proses pencarian.

DAFTAR PUSTAKA

[1]          Frakes, William B and Yates, Ricardo Baeza. Information Retrieval: Data Structures and Algorithms. 2004.

[2]          Murad,  AzmiMA.,             Martin,

Trevor.2007.Word           Similarity             for

Document Grouping using Soft Computing. IJCSNS International

Journal of Computer Science        and

Network Security, Vol.7 No.8, August 2007, pp.20-27.

[3]          Onoda T, Murata H , and Yamada S , Relevance feedback with active learning for document retrieval, in Proc. of IJCNN2003, pp. 1757–1762, 2003.

[4]          Larsen, Jan. 1998. Vector Space Model.http://cogsys.imm.dtu.dk/thor/proj ects/multimedia/textmining/node5.html. Diakses pada tanggal 4 Juni 2012.

[5]          Cios, Krzysztof J. Etc. Data Mining a Knowledge Discovery Approach, Springer. 2007.

[6]          Santosa. Budi. Tutorial Support Vector Machines. Institut Teknologi Sepuluh Nopember, Surabaya.

[7]          D. Harris, S. Behzad, G. C. David. Relevance Feedback using Support Vector Machines. AT&T Research.

CI-007 (wahyu)

CI-008 (wahyu)