BAB II TINJAUAN PUSTAKA

BAB II

TINJAUAN PUSTAKA

Pada bab ini akan dibahas mengenai information retrieval, similarity (kemiripan), similarity measure (ukuran kemiripan), algoritma genetika kemudian dilanjutkan dengan teknik-teknik yang telah digunakan sebelumnya.

2.1 INFORMATION RETRIEVAL Rahman [25] mendefinisikan Information Retrieval (IR) sebagai tindakan, metode dan prosedur untuk menemukan kembali data yang tersimpan, dan selanjutnya menyediakan informasi mengenai subyek yang dibutuhkan. Tindakan tersebut mencakup text indexing, inquiry analysis, dan relevance analysis. Data mencakup teks, tabel, gambar, ucapan, dan video. Informasi yang ditemukan adalah merupakan pengetahuan terkait yang dibutuhkan untuk mendukung penyelesaian masalah dan akuisisi pengetahuan [7]. Sistem Temu Kembali Informasi merupakan sistem yang berfungsi untuk menemukan informasi yang relevan dengan kebutuhan pemakai. Salah satu hal yang perlu diingat adalah bahwa informasi yang diproses terkandung dalam sebuah dokumen yang bersifat tekstual. Dalam konteks ini, temu kembali informasi berkaitan dengan representasi, penyimpanan, dan akses terhadap dokumen representasi dokumen. Dokumen yang ditemukan tidak dapat dipastikan apakah relevan dengan kebutuhan informasi pengguna yang dinyatakan dalam

Universitas Sumatera Utara

query. Pengguna Sistem Temu Kembali informasi sangat bervariasi dengan kebutuhan informasi yang berbeda-beda. Tujuan dari sistem IR (Information Retrieval) adalah memenuhi kebutuhan informasi pengguna dengan me-retrieve semua dokumen yang mungkin relevan, pada waktu yang sama me-retrieve sesedikit mungkin dokumen yang tak-relevan. Dokumen sebagai objek data dalam Sistem Temu Kembali Informasi merupakan sumber informasi. Dokumen biasanya dinyatakan dalam bentuk indeks atau kata kunci. Kata kunci dapat diekstrak secara langsung dari teks dokumen atau ditentukan secara khusus oleh spesialis subjek dalam proses pengindeksan yang pada dasarnya terdiri dari proses analisis dan representasi dokumen. Pengindeksan dilakukan dengan menggunakan sistem pengindeksan tertentu, yaitu himpunan kosa kata yang dapat dijadikan sebagai bahasa indeks sehingga diperoleh informasi yang terorganisasi. Sementara itu, pencarian diawali dengan adanya kebutuhan informasi pengguna. Dalam hal ini Sistem Temu Kembali Informasi berfungsi untuk menganalisis pertanyaan (query) pengguna yang merupakan representasi dari kebutuhan informasi untuk mendapatkan pernyataan-pernyataan pencarian yang tepat. Selanjutnya pernyataan-pernyataan pencarian tersebut dipertemukan dengan informasi yang telah terorganisasi dengan suatu fungsi penyesuaian (matching function) tertentu sehingga ditemukan dokumen atau sekumpulan dokumen. Menurut Grossman and Ophir [10], sistem ini menggunakan fungsi heuristik untuk mendapatkan dokumen-dokumen yang relevan dengan query pengguna. Sistem IR yang baik memungkinkan pengguna menentukan secara cepat dan akurat apakah isi dari dokumen yang diterima memenuhi kebutuhannya. Dengan tujuan dokumen lebih baik dan lebih representasi, maka dokumendokumen tersebut dikelompokkan secara bersama yang sesuai dengan topiknya atau isi yang mirip dikelompokkan. Menurut Frakes and Baeza-Yates [7], ada dua pekerjaan yang ditangani oleh sistem ini, yaitu melakukan pre-processing terhadap database dan kemudian menerapkan metode tertentu untuk menghitung kedekatan (relevansi atau similarity) antara dokumen di dalam database yang telah dipreprocess dengan


query pengguna. Pada tahapan preprocessing, sistem yang berurusan dengan dokumen semi-structured biasanya memberikan tag tertentu pada term-term atau bagian dari dokumen; sedangkan pada dokumen tidak terstruktur proses ini dilewati dan membiarkan term tanpa imbuhan tag. Query yang dimasukkan oleh pengguna dikonversi sesuai aturan tertentu untuk mengekstrak term-term penting yang sejalan dengan term-term yang sebelumnya telah diekstrak dari dokumen dan menghitung relevansi antara query dan dokumen berdasarkan pada term-term tersebut [24]. Sebagai hasilnya, sistem mengembalikan suatu daftar dokumen terurut descending (ranking) sesuai nilai kemiripannya dengan query pengguna [18]. Menurut Tata [30], setiap dokumen (termasuk query) direpresentasikan menggunakan model bag-of-words yang mengabaikan urutan dari kata-kata di dalam dokumen, struktur sintaktis dari dokumen dan kalimat. Dokumen ditransformasi ke dalam suatu “tas“ berisi kata-kata independen. Term disimpan dalam suatu database pencarian khusus yang ditata sebagai sebuah inverted index. Index ini merupakan konversi dari dokumen asli yang mengandung sekumpulan kata ke dalam daftar kata yang berasosiasi dengan dokumen terkait dimana katakata tersebut muncul.

2.2 SIMILARITY (KEMIRIPAN) Menurut Guo [13], definisi dari similarity adalah sesuatu yang penting dan merupakan konsep yang digunakan secara luas. Similarity mempunyai beberapa pendekatan, yaitu: a. Perkiraan 1: kesamaan antara A dan B adalah berhubungan dengan kesamaannya secara umum. Semakin banyak kesamaan umum yang dibagikan, semakin banyak pula kesamaan mereka.


b.

Perkiraan 2: kesamaan antara A dan B adalah berhubungan dengan perbedaan-perbedaan yang dimilikinya. Semakin banyak perbedaan yang dimiliki, semakin kecil tingkat kemiripannya.

c. Perkiraan 3: kesamaan maksimum antara A dan B akan tercapai ketika A dan B adalah serupa atau identik, berapa banyak kesamaan umum yang mereka bagikan tidak berpengaruh.

2.3 SIMILARITY MEASURE ( UKURAN KEMIRIPAN) Menurut Salton [26], model ruang vektor dan pembobotan tf-idf digunakan untuk merepresentasikan nilai numerik dokumen sehingga kemudian dapat dihitung kedekatan antar dokumen. Semakin dekat dua vektor di dalam suatu ruang vektor maka semakin mirip dua dokumen yang diwakili oleh vektor tersebut. Kemiripan antar dokumen dihitung menggunakan suatu fungsi ukuran kemiripan (similarity measure). Ukuran ini memungkinkan perankingan dokumen sesuai dengan kemiripan (relevansi)nya terhadap query. Setelah dokumen diranking, sejumlah tetap dokumen top-scoring dikembalikan kepada pengguna. Alternatifnya, suatu threshold dapat digunakan untuk memutuskan berapa banyak dokumen akan dikembalikan. Threshold dapat digunakan untuk mengontrol tarik-ulur antara presisi dan recall. Nilai threshold tinggi biasanya akan menghasilkan presisi tinggi dan recall rendah. Ada beberapa metode pengukuran kemiripan yaitu cosine, dice, hsinchun chen, dan jaccard. Metode yang sering digunakan untuk pengukuran kemiripan adalah ukuran kemiripan (similarity measure) cosine. Salah satu ukuran kemiripan dokumen adalah faktor Hsinchun Chen [32]. Menurut Chen et al [4] ukuran kemiripan dengan Hsinchun Chen adalah setiap istilah dapat diwakili oleh satu simpul (node), dimana hubungan antar istilah ini dapat dihitung dengan menggunakan rumusan yang diajukannya seperti pada persamaan 2.1 :


................................... (2.1) Dengan dijk bernilai 1 (satu) apabila dokumen ke-i memuat istilah j dan istilah k bersama-sama, dan bernilai 0 (nol) pada kasus lainnya. Nilai dij bernilai 1 apabila dokumen ke-i memuat istilah j, dan 0 apabila dokumen ke-i tidak memuat istilah j. Rumus di atas menyatakan kemiripan antara istilah j dan istilah k yaitu perbandingan antara jumlah dokumen yang memuat istilah j dan istilah k bersamasama, dengan jumlah dokumen yang memuat istilah j saja. Nilai n adalah jumlah keseluruhan dokumen yang ada dalam koleksi. Nilai kemiripan (Tj, Tk) mungkin berbeda dengan nilai kemiripan (Tk, Tj), karena nilai pembagi dalam rumus di atas untuk kemiripan (Tk, Tj) adalah jumlah dokumen yang memuat istilah k saja (dik). Ini berarti ada perbedaan nilai keterhubungan dari istilah k ke istilah j dengan nilai keterhubungan dari istilah j ke istilah k.

2.4 ALGORITMA GENETIKA Menurut Kusumadewi [16] menyatakan bahwa algoritma genetika (AG) adalah suatu algoritma pencarian yang berbasis pada mekanisme seleksi alam dan genetika. Algoritma genetika merupakan salah satu algoritma yang sangat tepat digunakan dalam menyelesaikan masalah optimasi kompleks, yang sulit dilakukan oleh metode konvensional. Menurut Desiani dan Arhami [6], sifat algoritma genetika adalah mencari kemungkinan-kemungkinan dari calon solusi untuk mendapatkan yang optimal bagi penyelesaian masalah. Ruang cakupan dari semua solusi yang layak


(feasible), yaitu objek-objek diantara solusi yang sesuai, dinamakan ruang pencarian (search space). Tiap titik dalam ruang pencarian merepresentasikan satu solusi yang layak. Tiap solusi yang layak ditandai dengan nilai fitness-nya bagi masalah. Ciri-ciri permasalahan yang dapat dikerjakan dengan menggunakan algoritma genetika adalah [1]: •

Mempunyai fungsi tujuan optimalisasi non linear dengan banyak kendala yang juga non linear.

•

Mempunyai kemungkinan solusi yang jumlahnya tak berhingga.

•

Membutuhkan solusi “real-time” dalam arti solusi bisa didapatkan dengan cepat sehingga dapat diimplementasikan untuk permasalahan yang mempunyai perubahan yang cepat seperti optimasi pada pembebanan kanal pada komunikasi seluller.

•

Mempunyai multi-objective dan multi-criteria, sehingga diperlukan solusi yang dapat secara bijak diterima oleh semua pihak.

2.4.1 Struktur Umum Algoritma Genetika Goldberg [9] mengemukakan bahwa algoritma genetika mempunyai karakteristikkarakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain, yaitu : 1. Algoritma genetika bekerja dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dan bukan parameter itu sendiri. 2. Algoritma genetika melakukan pencarian pada sebuah populasi dari sejumlah individu-individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu.


3. Algoritma genetika merupakan informasi fungsi objektif(fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik bukan turunan dari suatu fungsi. Algoritma genetika secara umum dapat diilustrasikan dalam diagram alir gambar 2.1 berikut :

Gambar 2.1. Diagram Alir Algoritma Genetika

Kusumadewi dan Purnomo [17] menyatakan variabel dan parameter yang digunakan pada algoritma genetika adalah : 1. Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai. 2. Populasi jumlah individu dilibatkan pada setiap generasi.


3. Probabilitas terjadinya persilangan (crossover) pada suatu generasi. 4. Probabilitas terjadinya mutasi pada setiap individu 5. Jumlah generasi yang akan dibentuk menentukan lama penerapan algoritma genetika.

Secara umum, Thiang et al. [31] mengemukakan bahwa struktur dari suatu algoritma genetika dapat didefenisikan dengan langkah-langkah sebagai berikut : 1. Membangkitkan populasi awal Populasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi ini sendiri terdiri atas sejumlah kromosom untuk merepresentasikan solusi yang diinginkan. 2. Membentuk generasi baru Untuk membentuk generasi baru, digunakan operator reproduksi/seleksi, crossover dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan sejumlah kromosom yang cukup untuk membentuk generasi baru di mana generasi baru ini merupakan representasi dari solusi baru. Generasi baru in dikenal dengan istilah anak (offspring). 3. Evaluasi solusi Pada tiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang dinamakan fitness. Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut. Proses ini mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya dampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulang langkah 2. Beberapa kriteria berhenti yang sering digunakan antara lain: berhenti pada generasi tertentu, berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi


tidak berubah, berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi.

2.4.2 Pengkodean Algoritma Genetika Pengkodean adalah suatu teknik untuk menyatakan populasi awal sebagai calon solusi suatu masalah ke dalam suatu kromosom [8] sebagai suatu kunci pokok persoalan ketika menggunakan algoritma genetika. Berdasarkan jenis simbol yang digunakan sebagai nilai suatu gen, metode pengkodean dapat diklasifikasikan sebagai berikut: pengkodean biner, bilangan riil, bilangan bulat dan struktur data [8]. Pengkodean biner merupakan cara pengkodean yang paling umum digunakan karena adalah yang pertama kali digunakan dalam algoritma genetika oleh Holland. Keuntungan pengkodean ini adalah sederhana untuk diciptakan dan mudah dimanipulasi. Pengkodean biner memberikan banyak kemungkinan untuk kromosom walaupun dengan jumlah nilai-nilai yang mungkin terjadi pada suatu gen yang sedikit (0 atau 1). Di pihak lain, pengkodean biner ini sering tidak sesuai untuk banyak masalah dan kadang pengkoreksian harus dilakukan setelah operasi crossover dan mutasi. Pengkodean bilangan riil adalah suatu pengkodean bilangan dalam bentuk riil. Masalah optimasi fungsi dan optimalisasi kendala lebih tepat diselesaikan dengan pengkodean bilangan riil karena struktur topologi ruang genotif untuk pengkodean bilangan riil identik dengan ruang fenotifnya, sehingga mudah membentuk operator genetika yang efektif dengan cara memakai teknik yang dapat digunakan yang berasal dari metode konvensional [8].


Pengkodean bilangan bulat merupakan metode yang mengodekan bilangan dalam bentuk bilangan bulat. Pengkodean ini baik digunakan untuk masalah optimasi kombinational [8]. Pengkodean struktur data adalah model pengkodean yang menggunakan struktur data. Pengkodean ini digunakan untuk masalah kehidupan yang lebih kompleks seperti perencanaan jalur robot dan masalah pewarnaan grap [6].

2.4.3 Operator Genetika Algoritma genetika merupakan proses pencarian yang heuristik dan acak sehingga penekanan pemilihan operator yang digunakan sangat menentukan keberhasilan algoritma genetika dalam menemukan solusi optimum suatu masalah yang diberikan. Operator genetika digunakan setelah proses evaluasi tahap pertama untuk membentuk suatu populasi baru dari generasi sekarang. Operator-operator tersebut adalah operator seleksi, crossover dan mutasi.

1. Seleksi Seleksi bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang paling fit. Langkah pertama dalam seleksi ini adalah pencarian nilai fitness. Masing-masing individu dalam wadah seleksi akan menerima probailitas reproduksi yang bergantung pada nilai objektif dirinya sendiri terhadap nilai objektif dari semua individu dalam wadah seleksi tersebut. Nilai fitness inilah yang nantinya akan digunakan pada tahap-tahap seleksi berikutnya [16]. Beberapa jenis seleksi yang umum dipakai adalah:


a. Rank-based Fitness Pada rank-based fitness, populasi diurutkan menurut nilai objektifnya. Nilai fitness tiap-tiap individu hanya tergantung pada posisi individu tersebut dalam urutan, dan tidak dipengaruhi oleh nilai objektifnya. b. Seleksi Roda Roulette (Roulette Wheel Selection) Pada metode ini, individu-individu dipetakan dalam sebuah segmen garis secara berurutan sedemikian sehingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran fitness-nya. Sebuah bilangan random dibangkitkan dan individu yang memiliki segmen dalam kawasan bilangan random tersebut akan terseleksi. Proses ini diulang hingga diperoleh sejumlah individu yang diharapkan. Pada tabel 2.1 dan gambar 2.2 menunjukkan probabilitas seleksi dari 11 individu. Individu pertama memiliki fitness terbesar, dengan demikian dia juga memiliki individu terbesar. Sedangkan individu ke-10 memiliki fitness terkecil kedua.

Tabel 2.1 Probabilitas Seleksi Dan Nilai Fitness Individu ke-

1

2

3

4

5

6

7

8

9

10

11

Nilai Fitness

2.0

1.8

1.6

1.4

1.2

1.0

0.8

0.6

0.4

0.2

0.0

Probabilitas

0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.02 0.0

Seleksi

Gambar 2.2 Seleksi Roda Roulette


Setelah dilakukan seleksi, maka individu-individu yang terpilih adalah: 1

2

3

5

6

9

c. Stochastic universal sampling Pada metode ini, individu-individu dipetakan dalam suatu segmen garis secara berurutan sedemikian hingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran fitnessnya seperti halnya pada seleksi roda roulette. Kemudian diberikan sejumlah pointer sebanyak individu yang ingin diseleksi pada garis tersebut. Andaikan N adalah jumlah individu yang akan diseleksi, maka jarak antar pointer adalah 1/N, dan posisi pointer pertama diberikan secara acak pada range [1,1/N]. d. Seleksi dengan pemotongan (Truncation selection) Seleksi ini biasanya digunakan oleh populasi yang jumlahnya sangat besar. Pada metode ini, individu-individu diurutkan berdasarkan nilai fitnessnya. Hanya individu-individu yang terbaik saja yang akan diseleksi sebagai induk. Parameter yang digunakan dalam metode ini adalah suatu nilai ambang trunc yang mengindikasikan ukuran populasi yang akan diseleksi sebagai induk yang berkisar antara 50%-10%. Individu-individu yang ada di bawah nilai ambang ini tidak akan menghsilkan keturunan. e. Seleksi dengan turnamen (Turnament Selection) Pada metode seleksi dengan turnamen ini, akan ditetapkan suatu nilai tour untuk individu-individu yang dipilih secara random dari suatu populasi. Individu-individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk. Parameter yang digunakan pada metode ini adalah ukuran tour yang bernilai 2 sampai N (jumlah individu dalam suatu populasi).

2. Crossover Operator persilangan merupakan operasi yang bekerja untuk menggabungan dua kromosom orang tua (parent) menjadi kromosom baru (offspring). Tidak semua


kromosom mengalami persilangan. Jumlah kromosom dalam populasi yang mengalami persilangan ditentukan oleh paramater yang disebut dengan crossover rate (probabilitas persilangan) . Beberapa jenis crossover tersebut adalah a. Crossover satu titik Proses crossover dilakukan dengan memisahkan suatu string menjadi dua bagian dan selanjutnya salah satu bagian dipertukarkan dengan salah satu bagian dari string yang lain yang telah dipisahkan dengan cara yang sama. Misalkan ada 2 kromosom dengan panjang 12 : Induk 1 : 0 1 1 1 0 | 0 1 0 1 1 1 0 Induk 2 : 1 1 0 1 0 | 0 0 0 1 1 0 1 Posisi yang dipilih : 5 Kromosom baru yang terbetuk: Anak 1 : 0 1 1 1 0 | 0 0 0 1 1 0 1 Anak 2 : 1 1 0 1 0 | 0 1 0 1 1 1 0 b. Crossover banyak titik Proses crossover ini dilakukan dengan memisahkan suatu string menjadi beberapa bagian dan selanjutnya dipertukarkan dengan bagian dari string yang lain yang telah dipisahkan dengan cara yang sama sesuai dengan urutannya. Misalkan ada 2 kromosom dengan panjang 12 : Induk 1 : 0 1 | 1 1 0 0 | 1 0 1 1 | 1 0 Induk 2 : 1 1 | 0 1 0 0 | 0 0 1 1 | 0 1 Posisi yang dipilih : 5


Kromosom baru yang terbetuk: Anak 1 : 0 1 | 0 1 0 0 | 1 0 1 1 | 0 1 Anak 2 : 1 1 | 1 1 0 0 | 0 0 1 1 | 1 0

c. Crossover seragam Kromosom seragam menghasilkan kromosom keturunan dengan menyalin bit-bit secara acak dari kedua orang tuanya. Misalkan ada 2 kromosom dengan panjang 12 Induk 1 : 0 1 1 1 0 0 1 0 1 1 1 0 Induk 2 : 1 1 0 1 0 0 0 0 1 1 0 1 Kromosom baru yang terbentuk: Anak 1 : 0 1 0 1 0 0 0 0 1 1 1 0 Anak 2 : 1 1 1 1 0 0 1 0 1 1 0 1

3. Mutasi Mutasi merupakan proses mengubah nilai dari satu atau beberapa gen dalam suatu kromosom. Beberapa cara operasi mutasi diterapkan dalam algoritma genetika menurut jenis pengkodean terhadap phenotype, antara lain: a. Mutasi dalam pengkodean biner Mutasi pada pengkodean biner merupakan operasi yang sangat sederhana. Proses yang dilakukan adalah menginversi nilai bit pada posisi tertentu yang dipilih secara acak (atau dengan menggunakan skema tertentu ) pada kromosom, yang disebut inversi bit. Contoh mutasi pada pengkodean biner


Kromosom sebelum mutasi : 1 0 0 1 0 1 1 1 Kromosom sesudah mutasi : 1 0 0 1 0 0 1 1 b. Mutasi dalam pengkodean permutasi Proses mutasi yang dilakukan dalam pengkodean biner dengan mengubah langsung bit-bit pada pada kromosom tidak dapat dilakukan pada pengkodean permutasi karena konsistensi

urutan permutasi harus

diperhatikan. Salah satu cara yang dapat dilakukan adalah dengan memilih dua posisi (locus) dari kromosom dan kemudian nilainya saling dipertukarkan. Contoh mutasi dalam pengkodean permutasi

Kromosom sebelum mutasi : 1 2 3 4 6 5 8 7 9 Kromosom sesudah mutasi : 1 2 7 4 6 5 8 3 9 c. Mutasi dalam pengkodean nilai Proses mutasi dalam pengkodean nilai dapat dilakukan dengan berbagai cara, salah satunya yaitu dengan memilih sembarang posisi gen pada kromosom, nilai yang ada tersebut kemudian ditambahkan atau dikurangkan dengan suatu nilai kecil tertentu yang diambil secara acak. Contoh mutasi dalam pengkodean nilai riil dengan nilai yang ditambahkan atau dikurangkan adalah 0,1 Kromosom sebelum mutasi : 1,43 1,09 4,51 9,11 6,94 Kromosom sesudah mutasi : 1,43 1,19 4,51 9,01 6,94


2.5 TEKNIK YANG DIGUNAKAN SEBELUMNYA Terdapat beberapa teknik yang telah dikembangkan oleh para peneliti sebelumnya untuk menyelesaikan permasalahan dalam sistem pencarian kembali dokumen. Beberapa teknik yang telah dipergunakan sebelumnya adalah: • Pendekatan jaringan syaraf tiruan untuk temu kembali informasi. • Pendekatan operator boolean untuk temu kembali informasi • Pendekatan bibliometrik untuk temu kembali informasi.

2.5.1 Pendekatan Jaringan Syaraf Tiruan Untuk Temu-Kembali Informasi Jaringan syaraf tiruan terinspirasi dari sistem pengorganisasian otak manusia yang terdiri dari beratus milyar sel syaraf dengan tipe yang bervariasi. Sihombing [27,28] menerapkan jaringan syaraf tiruan untuk temu kembali informasi dengan menggunakan beberapa ukuran kemiripan. Dalam terminologi dan konsep jaringan syaraf tiruan untuk sistem temu kembali informasi, dibangun node-node (neuron-neuron) yang merepresentasikan objek-objek dan links yang merepresentasikan hubungan objek-objek tersebut. Pendekatan sifat struktur JST dibangun didasarkan pada pengertian sebagai berikut : a. Objek: adalah sesuatu yang memiliki identitas atau entity konseptual untuk sistem temu kembali informasi. b. Connection:

menyatakan

hubungan

diantara

dua

objek,

dimana

keterhubungan ini dapat memiliki bobot, yang menentukan kekuatan (kemiripan) hubungan diantara objek tersebut .

Pendekatan pada pengertian dasar struktur ini dapat dilihat pada gambar 2.3 (a) dan (b) berikut ini :


Gambar 2.3 (a) kueri dan istilah aktivasi. (b) dokumen memuat istilah teraktivasi dan kumpulan dokumen Crestani and Rijsbergen [5]

Pada gambar 2.3 ditunjukkan bahwa dalam jaringan syaraf tiruan suatu kueri (

) bisa mengaktivasi beberapa istilah lain menjadi istilah teraktivasi (

),

dan kueri yang berbeda dapat mengaktivasi istilah yang sama. Pada beberapa dokumen yang memuat istilah teraktivasi, dapat memiliki persamaan dengan suatu dokumen dari kumpulan dokumen. Pendekatan jaringan syaraf tiruan dapat memformulasikan suatu istilah (j) yang diwakili oleh suatu simpul (node atau neuron), dan hubungan antar istilah diantara istilah (j) dengan istilah lain (k) dalam kumpulan dokumen yang dihitung dengan menggunakan ukuran kemiripan (similarity measure). Hasil dari penerapan jaringan syaraf tiruan pada sistem temu kembali informasi adalah jaringan syaraf tiruan mampu mengakomodir istilah lain yang tidak disajikan kueri dan dapat mengatasi kekakuan sistem kueri Boolean. Dokumen yang diperoleh adalah dokumen yang sebagian relevan yang memuat kueri dan yang memuat istilah teraktivasi yang terurut berdasarkan bobotnya. Jumlah istilah teraktivasi berbanding lurus dengan dokumen yang memuat teraktivasi. Peringkat dokumen adalah konsisten, artinya dokumen yang berada


pada peringkat atas, juga tetap berada pada range tersebut pada pengukuran kemiripan lainnya, walaupun ada perubahan bobot.

2.5.2 Pendekatan Operator Boolean Untuk Kembali Informasi Mustangimah [21] melakukan penelitian menggunakan operator boolean untuk mengetahui efektivitas pencarian kembali dokumen, dengan cara mengajukan pertanyaan-pertanyaan. Metode yang paling banyak digunakan dalam mengajukan pertanyaan adalah logika aljabar Boole yaitu dengan melakukan operasi dengan operator

AND,

OR,

dan

NOT.

Kesederhanaan

pengolahan

data

dan

kemampuannya dalam membangun konsep dari beberapa istilah merupakan alasan dalam penggunaan logika Boole. Salton [26] menjelaskan operasi dengan operator AND antara dua himpunan atau lebih menghasilkan hasil logis (logical product), irisan (intersection)

atau

disjungsi

(disjunction)

antara

himpunan-himpunan

sebelumnya. Operasi dengan operator OR antara dua himpunan atau lebih menghasilkan jumlah logis (logical sum), gabungan (union), atau konjungsi (conjunction) antara himpunan-himpunan sebelumnya, sedangkan operasi dengan operator NOT antara dua himpunan menghasilkan perbedaan logis (logical difference) antara kedua himpunan sebelumnya. Dalam proses temu-kembali informasi operator Boole digunakan untuk membantu pembentukan konsep pencarian dari beberapa istilah pencarian. Namun menunjukkan bahwa penggunaan operator AND, OR, dan NOT bervariasi antara pemakai yang satu dengan yang lainnya. Ditemukan bahwa operator AND hampir hanya sekali digunakan oleh pemakai, OR sangat banyak digunakan, dan NOT hampir tidak pernah digunakan. Mustangimah [21] menggunakan operator boolean untuk menggabungkan istilah dan konsep pencarian. Untuk meningkatkan ketaatazasan dalam


pembentukan

konsep

pencarian,

penggabungan

istilah-istilah

yang

menggambarkan konsep yang sama dilakukan dengan operator OR. Sedang penggabungan istilah-istilah yang menggambarkan konsep yang berbeda dilakukan dengan operator AND dan NOT. Proses pencarian harus dilakukan dengan strategi tertentu yang disesuaikan dengan fasilitas yang disediakan oleh sistem. Strategi pencarian merupakan himpunan keputusan atau tindakan yang dilakukan dalam proses pencarian, dengan tujuan untuk menemukan sejumlah cantuman yang relevan, menghindari

ditemukannya

cantuman

yang

tidak

relevan,

menghindari

ditemukannya jumlah cantuman yang terlalu banyak, dan menghindari ditemukannya jumlah cantuman yang terlalu sedikit atau tidak ditemukan cantuman sama sekali. Dalam pencarian berbasis logika boolean, strategi pencarian dibangun berdasarkan istilah pencarian yang telah dipilih yang dikoordinasikan dengan AND, OR, atau NOT. Pendekatan ini telah dikembangkan oleh peneliti lainnya seperti Hasibuan dan Andri [11] dengan melakukan

penerapan berbagai teknik sistem temu-

kembali informasi berbasis hiperteks seperti teknik Boolean biasa, teknik Boolean berperingkat dan teknik Extended Boolean.

2.5.3. Pendekatan Bibiometrik Untuk Temu Kembali Informasi Bibliometrika merupakan studi mengenai produksi dan penyebaran informasi yang secara operasional dikaji melalui produksi dan penyebaran media yang merekam informasi untuk disimpan dan disebarluaskan. Bibliometrik merupakan bagian dari informatika yang mengkaji aspek kuantitatif informasi terekam (recorded) dengan tujuan untuk mencari bentuk-bentuk keteraturan dalam proses komunikasi formal.


Metode bibliometrik banyak digunakan untuk mengukur kesamaan atau hubungan antara pasangan dokumen. Menurut Ikpaahindi [14] metode bibliometrik dapat dilakukan dengan cara perhitungan sitiran langsung (direct citation counting), pasangan bibliografi (bibliograhic coupling), dan analisis kositiran (co-citation analysis). Metode tersebut didasarkan pada hubungan antara dokumen yang disisir dengan dokumen yang menyitir. Hubungan antara dokumen yang disisr dengan dokumen yang menyitir dapat ditelusuri melalui motivasi, tujuan, dan fungsi sitiran dalam berbagai jenis ilmu. Liu [20] mengemukakan bahwa fungsi sitiran dalam bidang humaniora dapat diklasifikasikan sebagai dokumentasi sumber primer dan sekunder untuk baik di dalam maupun di luar topik dokumen yang menyitir, untuk menyatakan kesetujuan atau ketidaksetujuan pengarang yang menyitir terhadap dokumen yang disitir, dan untuk menyediakan informasi bibliografi. Liu [20] mengidentifikasi indikator hubungan antara dokumen yang disitir dengan dokumen yang menyitir yaitu sebagai penjelasan, memberikan informasi umum, hubungan historis, hubungan “saudara kandung”, hubungan oposisional, hubungan koroboratif, memberikan informasi spesifik, dokumentasi, hubungann metodologis, dan hubungan korektif. Menurut Liu [20] bahwa antara dokumen yang disitir dan dokumen yang menyitir terdapat hubungan subjek pada tingkat tertentu. Berdasarkan hubungan tersebut maka dapat dicari hubungan antara 2 (dua) dokumen yang menyitir dokumen yang sama. Menurut Grosman and Ophir [10] bahwa hubungan dua dokumen berdasarkan bibliografi yang digunakan bersama oleh kedua dokumen dengan menggunakan konsep pasangan bibliografi (bibliographic coupling). Bila 2 dokumen menyitir paling sedikit satu dokumen yang sama, maka kedua dokumen tersebut berpasangan secara bibliografi dengan pengindeksan subjek diperoleh kesimpulan bahwa ada hubungan yang nyata antara pasangan bibliografi dengan pengindeksan subjek secara analitik .


Banyaknya dokumen yang disitir secara bersama oleh pasangan dokumen disebut sebagai frekuensi pasangan atau kekuatan pasangan (coupling strength). Beberapa penelitian menunjukkan adanya hubungan antara kekuatan pasangan dengan keterhubungan subjek. Adanya

hubungan

antara

pasangan

pasangan

bibliografi

dengan

keterhubungan subjek dimanfaatkan untuk memperbaiki efektivitas temu kembali informasi. Ditemukan bahwa efektivitas temu kembali informasi meningkat dengan menggunakan pencarian berdasarkan kata kunci atau indeks dan pencarian berdasarkan sitasi.

Dari uraian sebelumnya mengenai beberapa pendekatan dalam sistem temu kembali informasi, maka dapat disimpulkan seperti tabel 2.2 di bawah ini: Tabel 2.2 Perbandingan Teknik dalam Sistem Temu Kembali Informasi Pendekatan Sistem Temu Kembali Informasi Jaringan Syaraf Tiruan • Sistem

Operator Boolean

Bibliometrik

• Sistem

• Sistem

melakukan

memformulasikan

diformulasikan

perhitungan

suatu istilah (j) yang

dengan mengajukan

langsung,

diwakili oleh suatu

pertanyaan-

bibliografi, dan analisis

simpul, dan hubungan

pertanyaan,

antar

pertanyaan

istilah

baik

maupun

sitiran pasangan

ko-sitiran,

dan

didasarkan

pada

hubungan

antara

direpresentasikan oleh

sederhana

neural network links.

pertanyaan

dokumen

kompleks.

dengan dokumen yang

yang

disitir

menyitir.

• Sistem


• Sistem

yang

• Sistem

diimplementasikan

diimplementasikan

menggunakan logika

melalui

mampu mengaktivasi

aljabar

boolean

bibliografi

istilah-istilah lainnya

dengan

operator

memberikan

yang tidak dijadikan

AND,OR dan NOT

hubungan

kueri oleh pemakai.

yang

dokumen, bukan dalam

mampu

membantu

bentuk

pembentukan

subjek.

konsep

pasangan yang indikasi antara

dua

keterhubungan

pencarian

dari beberapa istilah pencarian

• Hasil dari sistem adalah • Hasil dari sistem adalah

dokumen

yang memuat kueri dan dokumen yang memuat teraktivasi, memuat

istilah dan nilai

dokumen

• Hasil dari sistem adalah dokumen yang memiliki

memuat

kueri

hubungan

pasangan

dengan

nilai

bibliografi,

sehingga

ketepatan di atas 50

memberikan

kontribusi

%,

yang

baik

dengan

pemasangan

pertanyaan sederhana kompleks

lemah

maupun

terhadap dokumen

karena tidak berdasarkan subjek dokumen.

ketepatan lebih baik dari operator bolean.

Menurut Grossman and Ophir [10], sistem temu kembali informasi menggunakan fungsi heuristik untuk mendapatkan dokumen-dokumen yang relevan dengan query pengguna. Kekäläinen [15] melakukan penelitian pencarian kembali dokumen dengan melakukan pendekatan binary.


Penulis mencoba melakukan penelitian pencarian kembali dokumen dengan salah satu metode optimasi heuristik yaitu algoritma genetika dan memanfaatkan binary untuk pengkodean kromosom, dengan tujuan mampu memberikan hasil yang efektif dalam pencarian kembali dokumen selain pendekatan-pendekatan

sistem

temu

kembali

dokumen

yang

diuraikan

sebelumnya. Pada bab selanjutnya akan dijelaskan tentang metode penelitian dari pencarian

kembali

dokumen

menggunakan

algoritma

genetika

dengan

memanfaatkan ukuran kemiripan Hsinchun Chen.


BAB II TINJAUAN PUSTAKA

Recommend Documents