Zero - Center

Belajar, Berilmu dan Beramal

Digilib: Sistem Temu Kembali Informasi

17 December 2012 - dalam Digilib Oleh zero-fisip

2.1. Materi

Salah satu aplikasi umum dari sistem temu kembali informasi adalah search engine atau mesin pencarian yang terdapat pada jaringan internet. Pengguna dapat mencari halaman-halaman web yang dibutuhkannya melalui search engine. Google, Yahoo!, MSN, AOL, dan Altavista merupakan mesin pencari (search engine) berbasis web yang paling popular saat ini. Dengan memasukkan kueri berupa kata kunci kedalam mesin pencari, informasi yang inginkan dapat ditampilkan. Bagaimana mesin pencari melakukan pencarian informasi tersebut sementara jumlah informasi yang tersedia sangat banyak dan tidak terstruktur ? Adalah temu kembali informasi ( information retrieval ) bidang ilmu yang dapat menjelaskan bagaimana pencarian informasi tersebut dilakukan.

 

 

Gambar 1.  Bagian-bagian Sistem Temu Kembali Informasi

 

Gambar 1 memperlihatkan bahwa terdapat dua buah alur operasi pada sistem temu kembali informasi. Alur pertama dimulai dari koleksi dokumen dan alur kedua dimulai dari query pengguna. Alur pertama yaitu pemrosesan terhadap koleksi dokumen menjadi basis data indeks tidak tergantung pada alur kedua. Sedangkan alur kedua tergantung dari keberadaan basis data indeks yang dihasilkan pada alur pertama.

Sistem temu kembali informasi menerima query dari pengguna, kemudian melakukan perangkingan terhadap dokumen pada koleksi berdasarkan kesesuaiannya dengan query. Hasil perangkingan yang diberikan kepada pengguna merupakan dokumen yang menurut sistem relevan dengan query. Namun relevansi dokumen terhadap suatu query merupakan penilaian pengguna yang subjektif dan dipengaruhi banyak faktor seperti topik, pewaktuan, sumber informasi mapun tujuan pengguna.

Pada tulisan ini kami akan mengemukakan tentang pengaksesan dan penemuan kembali informasi. Dalam ranah teknologi informasi, kedua aspek ini terpadu dalam sistem temu kembali informasi. Sistem itu diciptakan guna memudahkan pengelola maupun pengguna informasi dalam mengakses informasi apapun seketika.

 

Model Temu Kembali Informasi

            Masalah utama dalam sistem temu kembali adalah menentukan dokumen yang relavan dengan dokumen yang tidak relavan berdasarkan kueri yang dimasukkan. Berikut ini dijelaskan perkembangan beberapa model sistem temu kembali yang telah ditemukan.

1. Formal karakteristik Sistem Temu Kembali

    Berikut ini adalah model temu kembali informasi yang terdiri dari notasi [D, Q, F, R(qi, dj)].

  • D adalah himpunan yang terdiri dari logical view bagi koleksi-koleksi dokumen
  • Q adalah himpunan yang terdiri dari logical view bagi kebutuhan informasi user. Representasi tersebut disebut query.
  • F adalah framework bagi representasi dokumen, query, dan hubungannya
  • R(qi, dj) adalah fungsi rangking (peringkat) yang berasosiasi antara bilangan real dengan query qi  Q dan representasi dokumen dj   D. Rangking tersebut mendefinisikan urutan di antara dokumen-dokumen yang diambil dengan menggunakan query qi.

2. Taksonomi Model Temu Kembali

            Secara garis besar, pengelompokkan model sistem temu kembali dapat digambarkan secara berikut :

 

Keterangan :

Ext Boolean  :  extended Boolean                              prox nodes  :  proximal nodes

Vec               :   vector                                                 HT               :  hypertext

Gen vec      :   generalized vector

LSI             :    lat. Semantic index

NN             :    neural networks

Prob            :    probabilistic

Inf netw     :    inference network

 

2.1 Model Klasik Temu Kembali

Ada beberapa hal yang harus diperhatikan dalam model klasik untuk sistem temu kembali diantaranya :

  1. Konsep
    1. Dokumen direpresentasikan dengan menggunakan indeks term
    2. Bobot indeks term menunjukkan spesifikasi untuk dokumen tertentu
  2. Model klasik terdiri dari : Model Boolean, Model Vektor dan Model Probabilistik

 

Model Boolean

     Model Boolean dalam sistem temu kembali merupakan model yang paling sederhana. Model ini berdasarkan teori himpunan dan aljabar Boolean. Dokumen adalah himpunan dari istilah (term) dan kueri adalah pernyataan Boolean yang ditulis pada term. Dokumen diprediksi apakah relevan atau tidak. Model ini menggunakan operator boolean. Istilah (term) dalam sebuah kueri dihubungkan dengan menggunakan operator AND, OR atau NOT. Metode ini merupakan metode yang paling sering digunakan pada`mesin penelusur (search  engine) karena kecepatannya.

            Keuntungan menggunakan model Boolean :

  1. Model Boolean merupakan model sederhana yang menggunakan teori dasar himpunan sehingga mudah diimplementasikan.
  2. Model Boolean dapat diperluas dengan menggunakan proximity operator dan wildcard operator.
  3. Adanya pertimbangan biaya untuk mengubah software dan struktur database, terutama pada sistem komersil.

            Kerugian menggunakan Model boolean :

  1. Model Boolean tidak menggunakan peringkat  dokumen yang terambil. Dokumen yang terambil hanya dokumen yang benar-benar sesuai dengan pernyataan boolean/kueri yang diberikan Sehingga dokumen yang terambil bisa sangat banyak atau bisa sedikit. Akibatnya ada kesulitan dalam mengambil keputusan.
  2. Teori himpunan memang mudah, namun tidak demikian halnya dengan pernyataan Boolean yang bisa kompleks. Akibatnya pengguna harus memiliki pengetahuan banyak mengenai kueri dengan boolean agar pencarian menjadi efisien.
  3. Tidak bisa menyelesaikan partial matching pada kueri

 

Untuk mengatasi masalah ini, maka dikembangkan operasi pembobotan dokumen berdasarkan frekuensi kemunculan istilah (term) pada dokumen tersebut. Model Boolean juga dikombinasikan dengan content based navigation dengan menggunakan konsep lattice, dimana shared term dari dokumen yang terambil sebelumnya digunakan untuk memperbaiki dan mengexpand kueri.

Model Boolean dibagi menjadi 2 yaitu :

1. Model Himpunan Fuzzy

            Misalkan U adalah himpunan semesta. Fuzzy subset dari U dikarakteristikkan dengan fungsi keanggotaan (membership function) A, dimana :

                                         μA : U → [0,1]

setiap uU dipetakan kedalam nilai biner [0,1], atau μA : U → [0,1]. Dengan demikian setiap elemen diberikan nilai biner yang mengindikasikan nilai keanggotaan elemen didalam himpunan.

            Pada sistem temu kembali, model himpunan fuzzy merupakan perluasan dari model Boolean retrieval. Ada beberapa perluasan yang diperoleh dengan menggunakan model himpunan fuzzy :

  1. Partially matching, berdasarkan term-term correlation matrix
  2. Direpresentasikan seperti thesaurus
  3. Melakukan perhitungan berdasarkan perbandingan antara dokumen yang mengandung pasangan term (pair of terms) dengan jumlah dokumen yang mengandung term tersebut.

 

2. Model Extended Boolean

            Prinsip utama dari teknik Extended Boolean adalah :

  1.  
    1. Dokumen direpresentasikan dalam ruang term berdimensi n
    2. Koordinat x, y dan z ditentukan dengan menggunakan bobot term
    3. Tergantung pada conjunction atau disjunction :
  1.                                                               i.      Menentukan vektor jarak dari (0,0)
  2.                                                             ii.      Menentukan vektor jarak dari (1,0)
  3.                                                               i.      Menggunakan konsep p-norm
  4.                                                             ii.      Perluasan karakteristik dari extended boolean
  1.  
    1. Menghitung jarak

 

Model Vektor

Beberapa karakteristik dari Model vektor dalam sistem temu kembali adalah

  1. Model vektor berdasarkan keyterm
  2. Model vektor mendukung partial matching dan penentuan peringkat dokumen
  3. Prinsip dasar vektor model adalah sebagaii berikut :

(a)    dokumen direpresentasikan dengan menggunkan vektor keyterm

(b)   Ruang dimensi ditentukan oleh keyterms

(c)    Kueri direpresentasikan dengan menggunakan vektor keyterm

(d)   Kesamaan document-keyterm dihitung berdasarkan jarak vektor

  1. Model vektor memerlukan

(a)    Bobot keyterm untuk vektor dokumen

(b)   Bobot keyterm untuk kueri

(c)    Perhitungan jarak untuk vektor document-keyterm

  1. Kinerja

(a)    Efisien

(b)   Mudah dalam representasi

(c)    Dapat diimplementasikan pada document-matching

 

Prosedur model ruang vektor dapat dikelompokkan menjadi tiga tahap yaitu :

  1. Pengideks-an dokumen
  2. Pembobotan indeks, untuk menghasilkan dokumen yang relevan
  3. Memberikan peringkat dokumen berdasarkan ukuran kesamaan (similarity measure)

Kesimpulan model vektor

  1. Muncul sejak tahun 1960
  2. Sangat efisien

(a)    menggunakan metode matrik sparse

(b)   Menggunkan aljabar linier yang sederhana

(c)    Mudah dibuktikan

  1. Fleksibel

(a)    Digunakan dalam resolusi kueri

(b)   Menggunakan kesamaan dokumen (document to document similarity)

(c)    Menggunakan kluster

  1. Sangat populer dan sering digunakan
  2. Kerugian

(a)    Teoritical Frameworknya tidak jelas

(b)   Menghasilkan indeks  yang berdekatan

(c)    Asumsi yang digunakan adalah independensi index term

 

 Pengindeks-an dokumen

Beberapa kata dalam sebuah dokumen, tidak menggambarkan isi dari dokumen tersebut, seperti kata the, is. Kata-kata tersebut dikenal dengan nama kata-kata buagan. Dengan menggunakan automatic document indexing, kata-kata buangan tersebut dihilangkan dari dokumen

Pembuatan indeks tersebut dapat berdasarkan

  • frekuensi kemunculan istilah dalam sebuah dokumen.
  • Metode Non Linguistic : Probabilistic Indexing

 

 Pembobotan Indeks (Term Weighting)

Pembobotan istilah dalam ruang vektor secara keseluruhan berdasarkan single term statistic. Ada tiga faktor utama dalam pembobotan istilah dengan menggunakan ruang vektor :

  1. Term frequency factor
  2. Collection frequency factor
  3. Length normalization factor

Ketiga faktor tersebut diatas dikalikan untuk menghasilkan bobot istilah. Skema pembobotan yang paling umum untuk istilah dalam sebuah dokumen adalah dengan menggunakan frekuensi kemunculan.

 

 Peringkat Dokumen

Ukuran kesamaan (similarity) istilah dalam model ruang vektor ditentukan berdasarkan assosiative coefficient berdasarkan inner product dari document vector dan query vector, dimana word overlap menunnjukkan kesamaan istilah. Inner product umumnya sudah dinormalisasi. Metode ukuran kesamaan yang paling populer adalah cosine coefficient, yang menghitung sudut antara vektor dokumen dengan vektor kueri. Metode ukuran kesamaan lainnya adalah Jaccard and Dice Coeeficient.

Model ini dibagi menjadi 3, yaitu:

1.  Generalized Vector Space Model

Terdapat himpunan t index term dinyatakan dengan (k1,k2,…,kt). Asumsikan bahwa wi,j adalah bobot term dalam dokumen dj [Ki,dj] dan wi,j {0,1} (binary). Dan gi(mj) merupakan bobot index term ki dalam minterm m1. Terdapat 2t minterms merupakan pola yang mungkin muncul.

2. Latent Semantic Indexing Model

Metode temu kembali yang sudah berkembang sebelumnya tidak mampu menangani masalah sinomin dan polysemi. Sinomim adalah kata yang berbeda namun memiliki makna yang sama. Misalnya pengguna menggunakan kata yang berbeda untuk mencari objek yang sama, sebagai contoh kata “car” dan “automobile”. Polysemi adalah kata yang sama, namun memiliki makna  yang berbeda, sebagai contoh kata “jaguar” bisa bermakna tipe kendaraan atau nama binatang.

Latent Semantic Indexing (LSI) adalah model temu kembali yang mampu memecahkan macalah sinomim. Dengan menggunakan Singular Value Decomposition (SVD) pada sebuah term dengan menggunakan matrik frekuensi term dari  dokumen. Dimensi transformasi ruang direduce dengan cara memilih nilai singular (singular value).

Keuntungan menggunakan model LSI adalah model ini fully automatic dan tidak menggunakan language expertise, akibatnya panjang vektor dokumen menjadi lebih pendek. Dengan membandingkan Model LSI dengan multidimensional scaling, ternyata ruang dokumen (document space) dengan model LSI lebih optimal pada saat menggunakan inner product similarity function demikian juga dengan menggunakan ukuran kesamaan lainnya.

3. Neural Network Model

            Model Neural Network dapat digambarkan sebagai berikut :

 

 

Dengan asumsi yang sama, maka untuk sistem temu kembali model neural network dapat digambarkan sebagai berikut :

 

 

Dari gambar diatas, Model Neural Network pada sistem temu kembali dapat dijelaskan sebagai berikut :

  1. Temu Kembali (Retrieval)
  1.  
    1. Level aktivasi terdiri dari lapisan query term
    2. Level Aktivasi dihubungkan dengan lapisan document term
    3. Dilakukan pembobotan pada query term
    4. Melakukan aktivasi Propagasi  terhadap lapisan dokumen
    5. Dilakukan pembobotan pada istilah dalam dokumen
    6. Merupakan esensial dari VSM
  1. Iterative Procedure

(a)      Aktivasi berlangsung dari lapisan dokumen ke lapisan term dokumen

(b)     Aktifasi balik dilakukan kembali ke dalam lapisan term

(c)      Aktifasi akan berhenti jika bobot (weight) <0

 

 Model Probabilistic

Karakteristik model probabilistik dalam sistem temu kembali adalah sebagai berikut :

  1. Melakukan pendugaan page relevansi dengan menggunakan probabilistik
  2. Mempunyai teoritical framework yang jelas
    1. Berdasarkan prinsip statistik
    2. Relevansi dokumen dapat diupdate
    3. Adanya feed back dari user
  3. Ide dasar
    1. Kueri dapat menghasilkan jawaban yang benar
    2. Menggunkan indeks term
    3. Menggunakan pendugaan awal
    4. Menggunakan initial hasil
    5. Feed back dari user dapat memperbaiki probabilitas dari relavansi.

Model ini juga dibagi menjadi 2 model lagi, yaitu :

1. Inference Network Model

    ► Prinsip Dasar :

  1. random variable digunakan untuk
    1.                                                                           i.      dokumen
    2.                                                                         ii.      index terms
    3.                                                                       iii.      user queries
    4. random variable untuk dokumen dj
      1.                                                                           i.      event of observing document
      2.                                                                         ii.      observing document  random variable merupakan index term

► Query Random Variable

  1. kejadian dimana permintaan informasi sudah terpenuhi
  2. dipengaruhi oleh random variable yang menyatakan dokumen dan index term

► Peringkat dokumen

 

Berikut ilustrasi model inference Network :

 

Berdasarkan ilustrasi diatas, Model Inference Network pada sistem temu kembali dapat  dijelaskan sebagai berikut :

  1. Model Inference Network memungkinkan adanya multiple composite queries:
    1. Operasi boolean pada query node
    2. Menggunakan prinsip operasi yang sama

 

  1. Tujuan model ini adalah untuk menentukan probability of relevance berdasarkan kueri yang diberikan

2. Belief Network Model

  1. Model ini menggunakan prinsip yang sama dengan inference network
  2. Graph : terms, document, queries adalah node dan edge menyatakan relationship atau  degree of belief
  3. Retrieval  dan peringkat (ranking)
    1. Konsep node
    2. Peringkat dokumen : konsep matching relationship antara kueri dengan dokumen


Read More | Respon : 0 komentar

Tinggalkan Komentar

Nama :
E-mail :
Web : tanpa http://
Komentar :
Verification Code :