rSSN 1.693-1629 Jurnal IImiah Edisi ilmu kompute

rSSN 1.693-1629~--~."J

Jurnal IImiah Edisi

ilmu kompute

1AnalisisAlgoritma Triple-DES untuk Penyandian PesanSony Hortono Wijoyo, Sugi Guritmon don Wisnu Anonto Kusuma

11Evaluasi Penambahan Dokumen dalamSistemTemu Kembali InformasiJulio Adisantoso, Yeni Herdiyeni, don Ika Kartika

22Kontrol Kongesti TeP-Friendly, Survei dan TaksonomiHeru Sukoco

30Pemetaan BerbasisWeb dengan MenggunakanMap Server dan PHP Script(Studi Kasus Kampus Institut Pertanian Bogar Oarmaga)Julio Adisantoso, Firman Ardiansyah don Leny Riajelito

40Pencarian Pola Data Audio dalam Interval TertentuMenggunakan Jaringan Syaraf Tiruan RekurenMushthofo, Prapto TriSupriyo don Agus Buono

51Probabilistic Neural Network Based on Multinomial Modeland EMAlgorithm in Classification, Fusionand ChangeDetection Contex of Optical and SARImagesWawan Setiawan, Aniati Murni, Benyamin Kusumoputro dan Selly Feranie

64Sistem Pakar Penentuan Metode Statistika padaPeubah Tunggal(Expert System for Selecting Statistical Techniques for Univariate)Yani Nurhadryani, Marimin, Bambang Sumantri don Hendra Yufit Riskiawan

Vol.3 no.2 / Oktober 2005

Jurnal IImiah ilnm komputerDiterbitkan oleh: Departemen Ilmu Komputer

Fakultas Matematikadan Ilmu Pengetahuan Alam - Institut Pertanian Bogor

Edisi 5 / Vol. 3. No.2 Oktober 2005

ISSN: 1693-1629. Tanggal 4 April 2003

Susunatt ~cfak§i

Penanggung Jawa6 :Ketua Departemen Ilmu Komputer FMIPA IPB

( Dr.Ir. Sri Nurdiyati, M.Sc )

Pemimpin !Rt-aaR§i:Irman Hermadi, S.Kom, MS

'Dewan 2?gaa!&i:Prof. Dr. Ir. Marimin, M.5c

Dr. Ir. Kudang Boro Seminar, M.5cDr. Ir. Sugi Guritman

!Rt-aak.tur 'Pelaksana :Irman Hermadi, S.Kom, MS

Ors. WO. PrabowoBambang Soetedjo iProduksi)

Sekretariat Jurnal IImiah Urnu ImrnpUler :

Departemen Ilmu Komputer FMIPA IPBJIn. Raya Pajajaran, Kampus Baranangsiang Bogor 16144

Telp/Fax: 0251-356653, E-mail: jurnaleilkom.fmipa.ipb.ac.idRekening : Tabungan Taplus BN! Pajaiaran Bogor.No: 3031184 a.n.: AnnisalJurnal Ilkom

Jurnal Ilmian IImu l\Omputer diterbitkan dua kali setahun, memuat tulisan ilmiah yangberhubungan dengan bidang Ilmu Komputer. Jurnal ini merupakan media publikasi ilmiahdan menerima tulisan dari luar IPB, berupa hasil penelitian atau bahasan ten tang meiodologi.

Pihak perorangan / alumni yang telah memperoleh Jurnal Ilmu Komputer mohon mengganti biaya cetak Rp.50.000,-/expl,

ditransfer melalui Tabungan Taplus BNI Pajajaran Bogar. No.Rek: 3031184 a.n.: Annisa / [urnal Ilkom.

Se~apurSinli

Pernbaca yang budiman,

Alhamdulillah, Jurnal I1miahllmu kompu'er Volume 3 N~.2 atau Edisi ke-5 telah terbitdan sampai di hadapan pembaca.

Selamat Dies Natalis IPB ke 42, pada tanggal l September 2005.

Selamat datang Kami ucapkan kepada lbu Dr. Ir. Sri Nurdiati, M.Sc yang telah terpilihmenjadi Ketua Departemen Ilmu Komputer FMIPA IPB periode 2005-2009. Kami haturkanpula terima kasih kepada Bapak Jr. Agus Buono, M.Si, M.Kom atas pengabdian beJiau selamaini dalam mengelola Departemen Ilmu Komputer FMIP A IPB.

Pada terbitan kali ini, Kami menyajikan tujuh hasil penelitian dengan topik yang cukupberagam, antara lain tentang: analisis algoritma kriptografi, temu kembali informasi, network-related, aplikasi neural network dalam pencarian pola data audio dan pengenalan citra, sistempakar, dan web-based mapping. Semoga materi yang disajikan dapat menambah khasanahpembaca tentang dunia Ilmu Komputer.

Untuk kedua kalinya Redaksi menerima tulisan dari luar Iingkungan IPB, yaitukolaborasi antara penulis dari Jurnsan Ilmu Komputer Universitas Pendidikan Indonesia clanJurusan Ilmu Komputer Fakultas Ilmu Komputer Universitas Indonesia.Terima kasih atas kepercayaan yang diberikan kepada Kami untuk mempublikasikan karyanya.Selanjutnya, kami mengundang pembaca untuk mengirimkan tulisan hasil penelitian untukditerbitkan dalam jurnal ini. Pedoman penulisan dapat dibaca di halaman sampul belakang

Kritik clan saran Kami harapkan untuk dapat terns melakukan perbaikan. Silakan tulisdan sampaikan lewat email kealamat:[email protected]. Atas partisipasi Anda,kami haturkan terima kasih.

Kampus IPB Baranangsiang, BogorAwal Oktober 2005

Salam,

Daftar Isi

Sekapur Sirih ,. I

Daftar Isi........................................................................................ iii

Analisis Algoritma Triple-DES untuk Penyandian PesanSony Hartono Wijaya, Sugi Guritman dan WisnuAnanta Kusuma.......................................................... 1

Evaluasi Penambahan Dokumen dalam Sistem Temu Kembali InformasiJulioAdisantoso, YeniHerdiyenidan IkaKartika 11

Kontrol Kongesti TCP-Friendly, Survei dan TaksonomiHeruSukoco . 22

Pemetaan Berbasis Web dengan Menggunakan Map Server dan PHP Script(Studi Kasus Kampus Institut Pertanian Bogor Darmaga)Julio Adisantoso, Firman Ardiansyah dan Leny Riajelita ... 30Pencarian Pola Data Audio dalam Interval TertentuMenggunakanJaringan Syaraf Tiruan RekurenMushthofa, Prapto Tri Supriyo dan Agus Buono " " . 40

Probabilistic Neural Network Based on Multinomial Modeland EM Algorithm in Classification, Fusion and Change Detection Contexof Optical and SAR'ImagesWawan Setiawan, Aniati Mumi, Benyamin Kusumoputro dan Selly Feranie........................................ 51

Sistem Pakar Penentuan Metode Statistika pada Peubab Tunggal(Expert System for Selecting Statistical Techniques for Univariate)Yani Nurhadryani, Marimin, Bambang Sumantri dan Hendra Yufit Riskiawan . 64

iii

Evaluasi Penainbahan Dokumen dalamSistem Temu Kembali Informasi

Julio Adisantoso', Yeni Herdiyeni' dan Ika Kartika-

1 Staf Pengajar Departemen Ilmu Komputer, FMIPA IPB2 Mahasiswa Departemen Ilmu Komputer, FMIPA !PB

Abstrak

Saat ini pengguna cenderung menyukai pencarian berdasarkan makna. Hal ini disebabkan oleh adanya masalah sinonim danpolisemi dalam pemilihan penggunaan kata. Salah satu teknik yang mencoba mengatasi masalah tersebut Latent SemanticIndexing (LSI). Dalam pengaplikasiannya. LS! dapat menggunakan Singular Value Decomposition untuk mengestimasi strukturpenggunaan kata dalam dokumen. Cara yang paling tepat untuk menambohkan dokumen atau istilah adalah melaluipenghitungan ulang SVD (recomputing SVD). Namun hal tni menjadi kendala karena dibutuhkannya memory yang cukup besardan waktu yang semakin lama untuk menghitung ulang matriks istilah-dokumen yang semakin besar. Cara lain yang dapatdigunakan untuk mengatasi kendala tesebut adaloh dengan menggunakan teknik folding-in. Tujuan penelitian ini adalah untukmelihat pengaruh penambahan dokumen terhadap hubungan tersembunyi antara semua istilah yang secara kontekstualberdekatan artinya dengan menggunakan teknik folding-in.

Tercakup didalamnya proses pembentukan matriks istilah-dokumen dengan menggunakan parsing. penghilangan stop list.serta stemming. Pembobotan istilah untuk dokumen menggunakan skema pembobotan lxn. sedangkan pembobotan istilah untukkuen menggunakan skema pembobotan eft. Pengujian menggunakan 150 dokumen untuk membangkitkan matriks istilah-dokumen asal dan 110 dokumen untuk evaluasi penambahan dokumen. Pengukuran kinerja temu kembali dilakukan denganmenggunakan average precision untuk mengetahui rank optimal terhadap sepuluh kueri. Temyata pada penelitian ini denganpemilihan rank yang kecil akan memberikan hasil dengan tingkat akurasi yang cukup tinggi dengan tertanganinya masalahsinonim. Penambahan dokumen dengan folding-in memberikan hasil yang memuaskan. Melalui penambahan 110 dokumen kedalam koleksi sebogian besar nilai recall bisa dipertahankan apabila menggunakan rank yang kecil. meskipun terdapat distorsiseiring dengan penambahan dokumen.

Kala kunci : Temu Kembali lnformasi. Folding-in. Latent Semantic. Indexing. Singular Value Decomposition.

PENDAHULUAN

Latar BelakangSaat ini banyak sekali informasi yang

dikembangkan secara digital, namun apabila tidakdiiringi dengan kemampuan untuk bisa diorganisasi,dimanipulasi ataupun dilakukan pencarian informasiyang diinginkan secara akurat dan cepat, makainformasi tersebut bisa menjadi tidak bennanfaat(Witter & Berry 1998). Oleh karena itu dibutuhkanlahsuatu sistem yang mampu menangani permasalahantersebut yaitu sistem temu kembali informasi.

Sistem temu kembali informasi bertujuan untukmemberikan data yang relevan terhadap permintaanatau kueri yang diberikan oleh pengguna secaraotomatis dan akurat. Salah satu pendekatan yang biasa

digunakan adalah metode pencocokan secara leksikalyaitu melalui pencocokan antara istilah (term) dalamkoleksi dokumen dengan istilah pada kueri yangdimasukan oleh pengguna Namun, metodepencocokan secara leksikal tersebut bisa memberikanhasil yang tidak tepat. Hal ini disebabkan oleh dua halyaitu:

• adanya ketidakcocokan antara istilah yangdigunakan oleh pengguna dengan istilah yang adadi dalam koleksi karena banyaknya kata yang bisadigunakan untuk menyatakan suatu konsep(sinonim),

• adanya makna ganda yang terdapat pada suatu katatertentu (polisemi) sehingga dapat menghasilkandokumen yang tidak relevan dengan istilah dalamkueri yang dimasukkan oleh pengguna.

Salah satu teknik dalam temu kembali informasiyang mencoba menjembatani masalah-masalahtersebut adalah menggunakan pendekatan Latent

11

Semantic Indexing (LSI). LSI mengasumsikan bahwaterdapat hubungan tersembunyi dalam penggunaankata yang sebagian disamarkan dengan pemilihan katayang beragam (Deerwester et al. 1990). Dalampengaplikasiannya, LSI dapat menggunakan SingularValue Decomposition sebagai salah satu cara untukmengestimasi struktur penggunaan kata dalamdokumen. Pencarian kemudian dilakukan pada nilaisingular yang dihasilkan oleh SVD yang tersimpandalam basis data (Berry et al. 1994).

Apabila terdapat dokumen dan atau istilah yangingin ditambahkan ke dalam basis data, maka carayang paling tepat adalah melalui penghitungan ulangSVD (recomputing SVD), disertai penambahandokumen atau istilah yang barn (Berry & Fierro 1995).Kendala yang dihadapi dalam proses penghitunganulang SVD tersebut adalah dibutuhkannya memoryyang cukup besar dan waktu yang semakin lama untukmenghitung ulang matriks istilah-dokumen yangsemakin besar.

Cara lain yang dapat digunakan untuk mengatasikendala tesebut adalah dengan menggunakan teknikfolding-in. Dengan teknik ini maka waktu yangdibutuhkan untuk menambahkan dokumen dan istilahbaru tidak terlalu lama. Begitu juga denganpenggunaan memori yang tidak terlalu besar (0 'Brien1994).

TujuanPenelitian ini bertujuan untuk melihat pengaruh

penambahan dokumen terhadap hubungan tersembunyiantara semua istilah yang secara kontekstualberdekatan artinya, dengan menggunakan teknikfolding-in.

Ruang LingkupPenelitian ini terbatas pada evaluasi jumlah rank

dan nilai cut-off. Proses yang terlibat dalam pem-bentukan matriks istilah-dokumen secara spesifik,penggunaan memori dan penghitungan kecepatantidak termasuk dalam penelitian ini.

TINJAUAN PUSTAKA

Sistem Temu Kembali InformasiSistem temu kembali informasi adalah suatu bentuk

sistem yang melakukan proses penemuan kembali

12

Jurnal IImiah - IImu Komputer, Edisi 5, Vo/.3 No.2 Oktober 2005: 11 - 21

informasi yang diperlukan. Secara konseptual sistemtemu kembali informasi dibagi menjadi tiga komponenutama (Gambar 1) yaitu:• kueri, merepresentasikan permintaan informasi

(information need),• proses komputasi, melakukan proses pengujian

antara dokumen yang sesuai dengan permintaaninformasi,

• koleksi dokumen (corpus), yaitu kumpulandokumen yang berbasis vektor, yang menjadi objekpencarian dari sistem temu kembali informasi.

Sistem temu kembali informasi memerlukanmasukan dari pengguna berupa kueri. Melalui kueriinilah diharapkan dapat menghasilkan keluaran yangrelevan dengan permintaan pengguna. Salah satupendekatan dalam merepresentasikan kueri tersebutadalah dengan mengolahnya menjadi bentuk vektor.Dengan menggunakan bentuk vektor diharapkan dapatmenentukan kemiripan atau kesesuaian antara kueriyang ada dengan dokumen yang terdapat dalamkoleksi.

Gambar 1. Konseptual Sistem Temu Kembalilnformasi (Salton 1989).

Metode Ruang VektorMenurut Salton (1989), metode ruang vektor adalah

suatu metode untuk menerapkan sistem temu kembaliinformasi. Misalkan sudah tersedia sekumpulan istilahyang dapat mendeskripsikan sejumlah dokumen, makarepresentasi dokumen dan kueri dalam model ruangvektor ini dinyatakan dalam bentuk:

1. vektor istilah dokumen

2. vektor istilah kueri

Evaluasi Penambahan Dokumen Temu Kembali Informasi

Dengan aik dan q,k merepresentasikan nilai dariistilah ke-k pada kueri .q. dan dokumen tli' Biasanya

-J

aik (atau Cf;J bemilai I jika istilah ke-k muncul dalamdokumen tli (atau kueri IJ.J) dan bemilai 0 jika

sebaliknya. Nilai a,k (atau q,k) bisa juga lebih besardari 1 untuk menyatakan seberapa penting istilahtersebut dalam dokumen atau kueri.

Keuntungan penggunaan metode ruang vektordalam sistem temu kembali informasi :

I. Dapat menentukan peringkat dari dokumen yangditemukembalikan berdasarkan nilai kemiripanyang diperoleh dokumen tersebut.

2. Jumlah dokumen yang ditemukembalikan dapatdisesuaikan dengan kebutuhan pengguna.

Matriks istilah-dokumenDalam model ruang vektor (vector space model),

matriks istilah-dokumen digunakan untukmerepresentasikan sekumpulan dokumen (corpus).Matriks inl menyatakan hubungan antar istilahdengan dokurnen dalam sistem temu kembaliinformasi.

Jika ail menyatakan elemen matriks istilah-dokumen A pada baris ke-i dan kolom ke-j, maka salahsatu representasi yang paling sering digunakan adalahfrekuensi kemunculan istilah ke-i dalam dokumen ke-jsebagai nilai ai]' Setiap baris pada matriks Amenyatakan vektor istilah dan setiap kolomnyamenyatakan vektor dokumen. Jelas sekali bahwa Amerupakan matriks yang berukuran besar dan jarang(banyak terdapat angka 0).

dokumen

la" a," jA = term .

alii ami

PembobotanFungsi utama dari pembobotan adalah untuk

meningkatkan efektifitas penemukembalian informasi.Dokumen yang relevan dengan kebutuhan penggunaharus terambil dan dokumen yang tidak relevan tidakakan terambil.

Pembobotan ini dapat dilakukan dengan berbagaimacam cara. Jika ai; menyatakan elemen matriksistilah-dokumen A pada baris ke-r dan kolom ke-),maka salah satu cara yang dapat digunakan untukpembobotan adalah dengan menghitung frekuensikemunculan istilah ke-z (hj) dalam dokumen ke-)sebagai nilai aij(aij =fij).

Cara lainnya adalah seperti yang dipaparkan olehSalton & Buckley (1998). Setiap kombinasipembobotan dideskripsikan dengan menggunakan duabuah triplet. Triplet pertama digunakan untukmemboboti istilah dalam dokumen (document term)dan triplet kedua digunakan untuk memboboti istilahdalam kueri (query term). Masing-masing triplet initerdiri dari tiga buah komponen yaitu komponen lokal,global dan normal dengan hubungan sebagai berikut :

dengan ti]: komponen istilah lokal (hanya berdasarkaninformasi di dalam dokumen ke-f), gi: komponen istilahglobal (berdasarkan irformasi mengenai istilah ke-i diseluruh dokumen), dan ~ : komponen normalisasi yangmenyatakan apakah kolorn-kolorn (dalam hal inidokumen-dokumen) dinormalisasi

Setiap komponen tersebut memiliki berbagaiformula. Formula untuk setiap komponen dapat dilihatdalam Tabel 1,2 dan 3. Semua formula tersebutmenggunakan basis 2 untuk perhitungan logaritma Xbernilai 1 jika t > 0 dan bernilai 0 jika t =O.

Tabe/I. Komponen istilah lokal

Sirnbol Formula untuk t, Deskripsi

b XV:) Binary

t ~ Term Frequency

o.s(XVij)+ fij 1. J Augmentedc Normalized Term

rnax , " Frequency

I log ({,j + I) Log

Tabel Z:Komponen istilah globalSirnbol Forrnula untuk gi Deskripsi

x I No Change

[ n 1f log Term FrequencyLjXU,,)

(n-L,xCf.)]Augmented

p Jog Normalized TermLjXCf.) Frequency

13

Tabel3. Komponen normal istilahSirnbol Formulauntuk d Deskripsi

x 1 No Change

n ~:JglJJl 2 Normal

Kombinasi dari ketiga huruf tersebut nantinya akandigunakan untuk memberi bobot pada istilah.Pembobotan juga dilakukan terhadap istilah dalamkueri yang dimasukkan oleh pengguna yangdirepresentasikan dalam bentuk vektor fJ. ,yaitu:

dengan qi merepresentasikan bobot dari istilah i dalamkueri. Pembobotan istilah untuk kueri tidak sarnadengan pembobotan untuk dokumen-dokumen. Padapemrosesan kueri, berlaku :

qi=gi tj

g; dihitung berdasarkan frekuensi dari istilah-istilahdalam koleksi dokumen 'sedangkan i . dihitung

J

rnenggunakan rurnus yang sarna dengan rurnus yangdigunakan untuk tij yang diberikan pada Tabel 1dengan r, diganti menjadifi yaitu frekuensi istilah ke- idalarn kueri.

Latent SemanticLatent Semantic adalah suatu hubungan makna

tersembunyi antara dua string yang berbeda, meliputihubungan sinonim dan polisemi yang maknanyamenyertakan dua string tersebut, kesamaan konsep,dan konsep yang berhubungan. Sistem temu kembaliinformasi yang mampu mengatasi latent semantic akanmengembalikan dokumen-dokumen yang beberapaistilahnya memiliki hubungan tersembunyi denganstring yang diberikan pada kueri, tanpa harusmemberikan string yang sarna dengan string yangterdapat dalam dokumen tersebut sehingga dapatmenambah efektifitas sistem temu kembali informasisebesar 30% dibandingkan penggunaan metode biasa(Deerwester et al. 1990).

Apabila nilai recall untuk kueri yang dipilih cukuptinggi, rnaka suatu dokumen akan memilikikemungkinan yang semakin besar untuk ikut terambildalam pemrosesan kueri, termasuk dokumen yangmemiliki kasus latent semantic. Latent semantic

14

Jurnailimiah - IImu Komputer, Edisi 5, Vol.3 No.2 Oktober 2005: 11 - 21

memiliki kemungkinan lebih besar teratasi jika ada duaistilah yang memiliki hubungan makna, sering munculdalam dekumen secara bersamaan.

Singular Value Decomposition (SVD)SVD adalah salah satu teknik eksplorasi data yang

dapat mereduksi dimensi matriks tanpa menyebabkankehilangan informasi yang berarti. Jika A adalahmatriks berukuran m x n dengan rank r dan 0 < k < r,dekomposisi nilai singular dapat digunakan untukmendapatkan sebuah matriks dalam R mxn dengan rankk yang paling dekat dengan matriks A, relatif terhadapnorma Frobenius. Norma Frobenius merupakan normayang diturunkan dari hasil kali dalam untuk ruangvektor berdimensi R mxn.

Misalkan A adalah matriks istilah-dokumen, makaSVD dari A adalah A = U .E VT, dengan U adalahmatriks ortogonal m x n, Vadalah matriks ortogonal nx 11 dan 1:adalah matriks diagonal yang mengandungnilai singular pada diagonal utamanya dalam urutanrnenurun

E = diag (0"1, .... O"min(m.n))

Awalnya dekomposisi menghasilkan r nilaisingular. Dari r nilai singular ditentukan k nilaisingular signifikan yang akan menentukan rank darimatriks A (Kolda & 0 'Leary 1998). Perkalian matriks-matriks hasil dekomposisi oleh SVD dapat digunakanuntuk membangun sebuah aproksimasi rank-k untuk Adengan hanya menggunakan k ~ r, yaitu •

A "" Ak "" Uk.Ek V/,

dengan U; dan Vk terdiri dari k kolom pertama dari Udan V berturut-turut, 1:k adalah submatriks berukuran kx k yang elemen diagonalnya adalah k elemen diagonalpertama dari e1emen diagonal .E. Ak adalahaproksimasi terbaik untuk rank k dari A.

Penerapan SVD pada Sistem Temu KembaliInformasi

Pada sistem temu kembali informasi, digunakanaproksimasi rank-k dari matriks istilah-dokumen (A).Karena matriks hasil aproksimasi SVD cukup dekat kematriks asalnya, pengembalian dokumen menggunakanmatriks tersebut dapat diharapkan sarna baiknya sepertisaat menggunakan matriks asalnya.

Namun pada kenyataannya, bukan hanya lebih baikSVD juga dapat mengembalikan dokumen lebih banyak(Kolda & 0 'Leary 1998). Hal ini disebabkan karenastruktur tersembunyi (latent) bisa diperkirakan denganmembuang kata-kata yang tidak terlalu penting.

Evaluasi Penambahan Dokumen Temu Kembali Informasi

Penambahan Informasi dalam Basis DataMisalkan basis data yang dibangkitkan oleh LS!-

telah tersedia yaitu, koleksi dokumen yang telahdilakukan proses parsing, matriks istilah-dokumenyang telah dibangkitkan dan SVD dari matriks istilah-dokumen yang telah dihitung. Jika terdapat istilah dandokumen baru yang ingin ditambahkan maka terdapatdua altematif yang bisa dilakukan yaitu menghitungulang SVD (recomputing SVD) dengan menggunakanmatriks istilah-dokumen yang barn atau melakukannyalangsung tanpa menghitung ulang SVD. Updatingadalah proses penambahan istilah atau dokumen kedalam basis data yang telah dibangkitkan oleh LS!.Recomputing SVD bukan merupakan metode updatingkarena melakukan penghitungan ulang LS! denganmenggunakan istilah atau dokumen baru yang telahditambahkan (Berry & Fierro 1995).

Updating dapat berupa folding-in dan SVD-updating. SVD-updating merupakan metodepenambahan dokumen dengan menggunakan strukturlatent semantik yang telah ada dan terdiri dari tigatahap: updating terms, updating documents danupdating term weights (0 'Brian, 1994).

Seperti halnya Si/Ir-updating, folding-in jugamenggunakan struktur latent semantik yang telah adasehingga tidak menyebabkan penghitungan kembaliSf;D pada basis data yang telah diperbaharni.Penambahan dokumen dengan metode folding-indilakukan dengan cara menambahkan vektor dokumenbarn yang telah terboboti ke dalamhimpunan vektor-vektor dokumen yang telah ada atau kolom dari Vk

(Gambar 2).

p

pm x (0 + p) m x k k x (0 + p)kxk

Gambar 2. Representasi penambahan p dokumen

Seperti vektor kueri, 4. didefinisikan sebagaivektor dokumen baru yang telah terboboti denganukuran i x 1. Proyeksi d terhadap d ke dalam model

-p -

LS/ yang sudah ada, dapat dilakukan sebagai berikut(Berry & Fierro 1995) .-

Recall dan PrecisionSuatu sistem temu kembali informasi memiliki

kinerja yang diukur melalui efisiensi dan efektifitas.Efisiensi diukur melalui waktu pemrosesan kuerisampai selesai ditemukembalikan, sedangkanefektifitas diukur melalui recall dan precission.

Recall adalah rasio jumlah dokumen relevan yangditemukembalikan dan jumlah dokumen yang relevan.Recall mengukur seberapa lengkap suatu pencarian itu,apakah semua dokumen yang relevan telahditemukembalikan. Semakin tinggi nilai recall makasemakin sedikit pula dokumen yang hilang dalampengembalian.

Precision adalah rasio jumlah dokumen relevanhasil temu kembali terhadap seluruh jumlah dokumenhasil temu kembali. Precision mengukur seberapa tepatsuatu sistem dalam melakukan suatu pencarian, apakahsemua dokumen hasil temu kembali relevan atau tidak.Semakin tinggi nilai precision maka semakin sedikitpula sistem mengembalikan .dokumen yang tidakdiinginkan.

c Keterangan :

a =Materi rel evan hasiltemu kernbali

b = Hasi! temu kembalic =Materi yang tidak

ditemukembalikand = Materi rel evan

Gombar 3. Pembagian koleksi oleh sistem temukembali informasi.

Berdasarkan Gambar 3, recall (R) dan precision(P) dapat dinyatakan sebagai berikut :

R=_a_a+d

p=_a_a+b

Secara teori, recall dan prectsston tidak salingberhubungan. Namun pada prakteknya recall yangtinggi dapat dicapai dengan mengorbankan precission.Begitu juga sebaliknya, precission yang tinggi dapatdicapai dengan mengorbankan recall. Oleh sebab itu,

15

meningkatnya nilai recall seringkaJi berarti penurunannilai precission. Hal ini terjadi karena untukmeningkatkan kemungkinan terambilnya seluruhdokumen yang relevan, maka pengguna harusmemeriksa ban yak materi, diantaranya materi yangsebenarnya tidak relevan.

Average PrecisionAverage precision adalah suatu ukuran evaluasi

dalam sistern temu kembali informasi yang diperolehdengan menghitung rata-rata tingkat precision padaberbagai tingkat recall (Grossman, 2002). AveragePrecision dihitung dengan menggunakan rumus,

dengan P(r) adalah average precision pada tingkatrecall r, Nq adalah jumlah kueri yang digunakan serta~(r) adalah precision pada tingkat recall r (Baeza-Yates & Ribeiro-Neto 1999).

METODOLOGI

Gambaran Umum SistemSecara garis besar langkah-langkah pengerjaan

sistem tertera pada Gambar 4 berikut.

[KOI~kSi1;)kU~

~:::E;;~:"=

P~Js'r·19 Sf!:\') Cst Stem" JJil£}

IPenambaha~ Dokurnen

Gambar4. Gambaran Umum Sistem.

16

Jurnallimiah -limu Komputer, Edisi 5, Vol.3 No.2 Oktober 2005: 11 - 21

Koleksi DokumenKoleksi dokumen yang digunakan terdiri dari

abstrak skripsi dari fakultas MIPA dan fakultasTelmologi Pertanian IPB serta abstrak skripsi dan tesisdari Fakultas Ilmu Komputer, Universitas Indonesia.Koleksi pengujian ini terdiri dari berbagai bidangantara lain ; sistem pakar, sistem informasi, sistemtemu-kembali informasi, sistem kecerdasan buatan,sistern pengenalan wajah, pola analisis citra, analisisalgoritrna, jaringan komputer, pengolahan basis data,serta pembuatan desain alat. Jurnlah dokumen yangdigunakan adalah 260 buah, dengan perincian 150abstrak digunakan untuk membangkitkan matriksistilah-dokumen dan 110 abstrak lainnya digunakandalam proses penambahan dokumen.

Matriks Istilah-Dokumen

Pembentukan matriks istilah-dokumen dilakukandengan berbagai cara. Salah satunya adalah melaluilangkah-langkah sebagai berikut:

1. Melakukan proses parsing yaitu pemilahandokumen menjadi unit-unit yang lebih kecil berupakata. Proses stemming dilakukan untuk istilahdalam bahasa Indonesia sehingga istilah yangdigunakan adalah istilah yang bersih dari imbuhan(kata dasar). Hal ini dilakukan untukmemperkeciljumlah istilah yang digunakan dalam matriksistilah-dokumen. Untuk istilah dalam bahasaInggris tidak dilakukan stemming mengingat istilahdalam bahasa inggris tidak terlalu ban yak

2. Melakukan penghilangan kata-kata yang termasukdalam stop list yaitu istilah atau string yang seringmuncuI dalam koleksi dokumen dan tidak memilikiarti yang penting seperti kata tugas: ini, itu, danserta string yang berupa angka seperti angkatahun.dilanjutkan dengan menghilangkan kata-katayang tidak signifikan dalam membedakan dokumenatau kueri.

3. Melakukan pemotongan lebih lanjut melalui prosesstemming (dengan menggunakan kata dasar).Setelah didapatkan matriks istilah dokumen, maka

dilakukan pembobotan terhadap elemen matriksdengan menggunakan skema pembobotan Ixn (Salton&Buckley 1998) yaitu :

log(f!] + 1)au == --'==m===~==

L (log( fig + 1)2k=l

Evaluasi Penambahan Dokurnen Temu Kembali Informasi

yang berarti tiap istilah memiliki komponen lokal log,tidak ada komponen global, dan terdapat normalisasipada kolom-kolom dari matriks. Matriks istilah-dokumen yang telah terboboti kemudian diolah denganmenggunakan SVD sehingga didapatkan aproksimasimatriks Ak. Dengan menggunakan nilai k yang tepat,maka hubungan tersembunyi antar semua istilah dapatditemukan. Pemilihan nilai k dilakukan melaluiserangkaian percobaan (Berry et al. 1994). Nilai kyang digunakan dalam percobaan ini adalah: 5, 10, 20,30, 40, 50, 60, 70, 80, 90 dan 100

Pemrosesan kueriSebelum dilakukan pemrosesan, istilah pada kueri

juga hams diboboti terlebih dahulu. Skemapembobotan yang digunakan pada kueri adalah cfx(Salton & Buckley 1998) yaitu :

qj =[O'5x(lj)+O'5(~JJlogl-!--1max , i. I.Jij

j-l

dengan nilai xV) = 1 jika .~ > ° dan xV;) = 0 jika1; = O.. I

lumlah kueri yang digunakan untuk evaluasi adalah10 buah. Dalam sistem ternu-kembali informasiterdapat berbagai macam cara untuk melakukanpemrosesan kueri diantaranya dengan mengalikansuatu vektor kueri dengan matriks Ak,

! = (l Ak

sehingga menghasilkan suatu vektor ~ (score vector)yang menyatakan nilai (score) dokumen-dokumendalam sistem terhadap kueri. Jika vektor ! diurutkan.mengecil, maka didapatkan urutan relevansi dokumen-dokumen dalam sistem terhadap kueri tersebut. Untukmenentukan tingkat relevansi dokumen terhadap querydigunakan nilai cut-off yaitu 0.001, 0.005 dan 0.01.Kinerja temu kembali dievaluasi dengan menggunakanrecall-precision serta average precision pads tingkatrecall 0. I, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0.

Penambahan DokumenPenambahan dokumen dilakukan dengan

menggunakan met ode folding-in. Sebelumditambahkan, dokumen-dokumen tersebut jugamendapat perlakuan yang sarna seperti pada saatpembentukan matriks istilah-dokumen awal. Perlakuantersebut meliputi proses parsing, penghilangan stop listserta pembobotan dengan menggunakan skema

pembobotan Ixn, sehingga dihasilkan vektor dokumenyang siap untuk ditambahkan.

Penambahan vektor dokumen ke dalam matriks Akini dilakukan secara bertahap yaitu :

1. Penambahan 20 dokumen2. Penambahan 60 dokumen3. Penambahan 90 dokumen4. Penambahan 110 dokumen.

Penambahan bertahap ini dilakukan untuk melihatsampai sejauh mana pengaruh penambahan dokumenterhadap matriks Ak. Evaluasi dengan menggunakanaverage precision selanjutnya dilakukan untuk setiaptahap penambahan dokumen ke dalam matriks istilah-dokumen awal (Ak). Average precision ini dihitungdengan menggunakan tingkat recall yang sarna dengansebelum penambahan dokumen. Setelah dilakukanpenambahan maka akan dihasilkan aproksimasimatriks istilah dokumen yang barn yaitu matriks Ap.

OnogonalitasProses penambahan dokumen dengan

menggunakan metode folding-in ini dapat me-nyebabkan terjadinya distorsi terhadap ortogonalitasV", Hal ini terjadi karena ditambahkannya sub-matriksnon-ortogonal d ke dalam V", lumlah distorsi yang

-p

ditimbulkan ini dapat dihitung dengan menggunakanrumus:

Oleh karena itu, setelah dilakukan penambahandokumen maka langkah selanjutnya adalahmenentukan jumlah nilai ortogonalitas yang hilang(Berry et al 1994).

Lingkungan Pengembangan

Lingkungan pengembangan yang digunakan adalahsebagai berikut:

• Perangkat lunak: Windows XP Professional,MATLAB 6.05.

• Perangkat keras: Athlon XP 1GHz, 256 ME RAM

17

HASIL DAN PEMBAHASAN

Kueri

String pada kueri diusahakan dalam bentuk yangsingkat. Karena sinionim, polisemi dan kesamaankonsep biasanya terjadi pada string yang pendek, makapemilihan string yang pendek akan memudahkanterambilnya dokumen yang mengandung string yangmemiliki hubungan makna dengan string yang terdapatpada kueri. Kueri yang digunakan antara lain :

1. Algorithm Analysis2. Expert System3. Management Information System4. Information Retrival5. Human Computer Interaction6. Geographic Information System7. Computer Networking8. Pattern Recognition9. Face recognition10. Object Oriented

Kueri-kueri ini sengaja dipilih dalam bahasa inggrisyang merupakan sinonim dari kata-kata yang adadalam koleksi dokumen uji. Hal ini dilakukan untukmelihat apakah dokumen-dokumen yang tidakmengandung kata-kata dalam kueri namun sebenarnyarelevan, bisa ditemukembalikan. Pengategorian koleksidokumen dilakukan secara manual dengan membacaisi dokumen.

Matriksistilah-dokumenJumlah istilah yang digunakan dalam matriks

adalah 1529 sehingga didapatkan ukuran matrikssebelum dilakukan penambahan dokumen adalah 1529x 150 dengan jumlah elemen bukan nol (non-zeroelements) sebanyak 6670.

Pemrosesan KueriDari tiga nilai cut-off (O.OOJ, 0.005 danO.OJ) yang

diuji pad a kesepuluh kueri, ternyata tidak memberikanperbedaari yang besar apabila nilai k yang digunakankecil, baik dari segi recall maupun precision. Namununtuk nilai k yang besar dapat terlihat bahwapenggunaan nilai cut-off 0.001 dapat meningkatkannilai recall-precision (Gambar 5). Oleh karena itu nilaicut-off yang digunakan untuk percobaan selanjutnyaadalah.O. 001.

Hubungan tersembunyi antar istilah dalam matriksaproksimasi bisa muncul melalui pemilihan nilai kyang tepat. Misalkan pada percobaan denganmenggunakan kueri 'expert system', diharapkan

Jurnailimiah - IImu Komputer, Edisi 5, Vol.3 No.2 oktober 2005: 11 - 21

dokumen yang mengandung kata "sistem pakar ' akanikut terambil bahkan dokumen yang sama sekali tidakmengandung kata 'sistem pakar' namun masuk kedalam kelompok sistem pakar juga diharapkan ikutterambil. Dari percobaan yang dilakukan, terdapat 18dokumen dalam koleksi pengujian yang termasukdalam kelompoksistem pakar. Meskipun hanya Jdokumen yang didalamnya terdapat kata 'expertsystem' namun dengan pemilihan nilai k yang tepatmaka hubungan tersembunyi ini dapat dikenali sepertiyang bisa dilihat pada Gambar 6.

Gambar 5. Evaluasi dengan kueri 'managementInformation system'

"'d' Recall. cut-off 0 .001"0". Precision. cut-off 0.001-0- Recall. cut-off 0.06"''l:r~ Precision. cut-off 0.05"'~ Recall. cut-off 0.01..tr Precision. cut·off 0.01

Gambar 6. Evaluasi dengan kueri 'expert system'

Evaluasi Penambahan Dokumen Temu Kembali Informasi

Bahkan dengan memilih nilai k = 5 atau k = 10sebagai rank: yang digunakan, semua dokumen yangrelevan berhasiI ditemukembalikan. Data yangdigunakan dapat dilihat pada Gambar 6.

Dari percobaan dengan menggunakan sepuluhkueri, temyata diperoleh tingkat precision yang rendah.Salah satu faktor yang menyebabkannya adalah karenaadanva masalah polisemi. Kegagalan teriadi pada faktabahwa setiap istilah direpresentasikan hanya sebagaisatu titik dalam ruang (Deerwester et at. 1990).

Secara keseluruhan, grafik hasil penelitian dengansepuluh kueri terdapat pada Gam bar 7. Semakin besarnilai k yang digunakan, maka nilai average precisionyang dihasilkan cenderung semakin mengecil. Hal initerjadi karena terdapat banyak kata-kata yang tidakperlu dalam data yang digunakan. Oleh karena itu padapenilitian ini, penggunaan nilai k yang keci! cukupmemadai untuk menemukan hubungan tersembunyitanpa menghilangkan informasi yang penting.

Gambar 7. Average Precision sebelumpenambahan dokumen

Pengaruh penambahandokumenterhadap average precision

Dari pcrcobaan scbclumnya, nilai averageprecision yang tinggi sebagian besar dihasilkan padaselang k antara 5 sampai 50. Oleh karena itu padapercobaan selanjutnya prediksi nilai k yang digunakanadalah 5, 10, 20, 30, 40, 50.

Penambahan 20 dokumen ke dalam rnatriksaproksimasi awal cenderung rneningkatkan nilai recall-precision (Gambar 8). Meskipun terdapat penurunannilai recall-precision, namun tidak terlalu besar(Gambar 9). Ini berarti penarnbahan 20 dokumentersebut tidak rnerusak representasi rnatriksaproksimasi awal.

Pada setian proses penambahan dokumen,didapatkan nilai recall dan precision yang tidak jauhberbeda (memiliki pola yang mirip) antara sebelum dansesudah dilakukan penambahan .dokumen. Hal inidisebabkan karena ketepatan folding-in bergantungpada hubungan istilah-dokumen yang sarna antarasebelum dan sesudah penambahan dokumen (0 'Brien1994).

\\.,

"

'.\ Recall\\Q._._._ .

..Q.. R sebelum penambahan__ P sebelum penembahan

-e" R setelah penambanen dokumen-e- P setelah penambahan dokumen

Gambar 8. Penamoahan 20 dokumen dengankueri 'analysis algorithm

Dari Gambar 8 dan Gambar 9 diperoleh nilairecall-precision yang tinggi melalui penggunaan nilai kyang kecil. Nilai recall-precision yang dihasilkan jugacenderung meningkat untuk. semua kueri. Meskipunterdapat beberapa kali penurunan nilai recall-precision,namun penurunan tersebut tidak terlalu besar. Hasilevaluasi dengan menggunakan recall-precision danaverage precision untuk semua kueri pada berbagaitingkat penambahan dokumen

Terlihat bahwa niiai average precision yangdihasilkan cenderung mengecil untuk nilai k yangsernakin besar. Berdasarkan rataan geornetri diperolehnilai k optimal untuk sepuluh kueri adalah 5. Pengaruh

19

penambahan dokumen terhadap nilai average precisiondengan nilai k = 5 dapat dilihat pada Gambar 10.

-0- R sebelum penambehen-0- P sebelum penambahan-e- R setelah penambahan-11- P setelah penambahan

Gambar 9. Penambahan 20 dokumen dengan kueri'management information system'

Gambar 10. Average Precision pada nilai k = 5

OrtogonalitasDari Gambar 10, terdapat beberapa kali penurunan

nilai average prescision. Menurunnya nilai averageprecision In! karena metode folding-in tidak

20

Jurnalllmiah - IImu Komputer, Edisi 5, Vol.3 No.2 Oktober 2005: 11 - 21

mempertahankan ortogonalitas dari V. dengan

ditambahkannya sembarang vektor dokumen terbobotike dalam v•. Hal ini menyebabkan terjadinya distorsi

yang muncul setelah penambahan dokumen baru(Berry et al. 1994). Jumlah distorsi yang timbul akibatdilakukannya penambahan dokumen bisa dilihat padaGambar 11. .

Gambar 11. Jumlah distorsi ditimbulkanakibat penambahan dokumen

Meskipun terdapat distorsi, pengaruh penambahandokumen sampai dengan 110 buah dapat menghasilkannilai recall yang cukup tinggi apabila menggunakanpemilihan nilai k yang tepat Dengan demilikianhubungan tersembunyi antara semua istilah yangsecara konseptual berdekatan artinya tetap dapatditemukan walaupun telah dilakukan penambahandokumen. Oleh karena itu secara keseluruhanpenambahan dokumen dengan met ode folding-in dapatmemberikan hasil yang memuaskan.

KES~PULANDANSARANKesimpulan

Melalui pemilihan rank yang tepat maka akandihasilkan sebuah aproksimasi matriks istilah-dokumenbaru yang dapat memberikan hasil dengan tingkatakurasi yang cukup tinggi. Hal ini bisa teriadi karenapenerapan LS! berbasis SVD terbukti dapatmeningkatkan hasil temu kembali sehingga bisa

Evaluasi Penambahan Dokumen Temu Kembali Informasi

menangani masalah sinonim dalam pemasukan kueri.Tertanganinya masalah sinonim ini bisa dilihat daritingginya nilai recall yang dihasilkan

Penambahan dokumen dengan menggunakan teknikfolding-in bisa dijadikan sebagai alternatif yang baik.Hal ini bisa dilihat dari pengaruh penambahan 110dokumen ke dalam koleksi yang telah ada, meskipunterdapat distorsi seiring dengan penambahan dokumen,namun melalui pemilihan rank yang tepat makasebagian besar nilai recall bisa dipertahankan.

SaranPenelitian ini bisa dikembangkan lebih lanjut

dengan menggunakan teknikfolding-in pada penerapanLSI berbasis lainnya seperti Semi-DiscreteDecomposition atau probability PCA.

DAFTAR PUSTAKA

Baeza-Yates, R & B. Ribeiro-Neto. 1999. ModernInformation Retrieval. England: Addison-Wesley.

Berry, M.W., Susan T. Dumais, Gavin W. O'Brien.1994. Using Linear Algebra jor IntelligentInformation retrieval. Department of ComputerScience. University of Tennessee, Knoxville, T.N.

Berry, M. W. & RD Fierro. 1995. Low-RankOrthogonal Decompositions jor InformationRetrieval Applications. Department of ComputerScience. University of Tennessee, Knoxville, T.N.

Berry, M. W., Susan T. Dumais, Todd A. Letsche.1995. Computational Methods for IntelligentInformation Access. Proceedings ofSupercomputing 1995.

Berry, M. W., Z. Drmac & E. R Jessup. 1998.Matrices, Vector Space, and Information Retrieval.SIAM REVIEW. Vol. 41, No.2, pp. 335-362.

Deerwester, Scott. S. Dumais, G. Furnas & RHarshman. 1990. Indexing by Latent SemanticAnalysis. Journal of the American Society forInformation Science, 41(6):391-40.

Grossman, D. IR Book. http://www.ir.iit.edu/-dagr/cs529/files/ir book! [7Maret 2002]

Kolda, T. & D. O'Leary. 1998. A semi-discretematrix decomposition for latent semantic indexingin information retrieval. ACM Trans. Inform.Systems, pp. 322-346.

Lancaster, F. & A. Warner. 1993. InformationRetrieval Today. Arlington: Information ResourcesPress.

O'Brien, G. W. 1994. Information ManagementsTools for Updating an SVD-Encoded IndexingScheme. Department of Computer ScienceUniversity of Tennessee, Knoxville, T.N.

Salton, G & c. BUCkley. 1988. Term Weightingapproaches in automatic text retrieval. Inf Process~anage.24, pp. 512-523.

Salton, G. 1989. Automatic Text Processing: TheTransformation, Analysis, and Retrieval ofIrformation by Computer. England: Addison-Wesley.

Witter, D. I & Michael W. Berry. 1998.Downdating the Latent Semantic Indexing Modelfor Conceptual Information retrieval. Departmentof Computer Science. University of Tennessee,Knoxville, T.N.

21