ISSN : 1979 -911X
|ffi.t].."l
DAFTARISIBIDANG INFORMATIKA / KOMPUTER Aprk
sr
NaruEr Lanquase
p6ess
rndones a.1\r'nang Berbas s N€ws
ns Denqan Merode Rue
web
Aq€ unlrr.Pen.a,a^
E6ed pada rsFmahan
oan
15-U
Rancangan sistem Pame€n onrh€ Menggunakzn Merode
uco
(User cenrered
Ap kasi Aloor lma D,lksta Unluk P uhins Les,an
5
Percncansan Dan Pombualai oalaWarchou* pada Perpusrakaan stm kAm kom
npl.lFrlas
oo(fel
oo,ecrModeturtrkoedrj1ganLaooa.Daldoase[rysol
lhp ementasiJXTA sebaqa Plafom Jaingan PeeETo,Peor pada Mobite Device unluk
hplehenla si Ki
owred
g
e Maiagemont unruk Meninskalken Knerta peEu.uan T nqs
Desa n Algortma Pemec.han OpeEsiOasar Oata Tedisribusi Berbasis Web
Di!"ntu c@ Jahan serdwn dan kdEj i Ap (as BLLL Ere, ,o r {C-Boo., Berbass 'DoclMenlad'Pdf
A,iina[ka Dan pemodetan Sisrem Akulsisi
Weo oenolrLno
(onreN tormal D.^_men
EkaHandqqfuzllsnanta'ddnRehaArfuA
lmpem6niasr Melode Funcrion poht Unluk MensukuVotume sofh'ar€
E.Cove'lTea S'sFnDatar FitieryDanE,ernlEsp.'pJa-",
i penoadopsian Etecroni Penqatuhiya Terhadap Kinera petusahaan (srudipae peruehan K
ana risis Fa kro tsFa ktor Yang Mempensaruh
vidiAn]nyhalddrAucdinusselhEn lekn . a- Tas l1oesee...q oens a 1 TEnrformas' 2D Peoa G ar'. o1n rt 15
algorirr" Co.pan on
Oun Co"lurion untuk peioadan Halaman web
yaio TedGir
Penalaan Ulang Soltware Requ ementSpeciticalion (sRs)Sislem tnfomas Dengan P€ndekaian Rav€ree Enqinennq Eka K B'atkdia dan y.nr andiyani Aprikasi Pe
ng orah a
n
c 16 Distar
Pad a
Totopoi setu
ter
AkadeDik i5o.i56
151
-16s
htemmb, rerL Pedand
nsa
25 Mecrsur
h,oha
^emu1
Kn€rja Mdd-Mode
ap[a3'
Dan MlsOL
w* sllt
cfu]sw{ryfub*m*ali
Edlifu*hi@hhaAfun*hali) ci1ha.
hw*
*
Btd ctanne tc8c)
susuti, sFr]t, ekt,
Ratu
rM{.aE,r
ftuitM Mr
a
tuhmhd
sharett
en ttuanad Mudah
atuwahyd) hn satu anas\tuitu
oeg'iApr'ka3endngo*306
(sbdi K6.us P'od rern I rnromatl a tsr Akonnd'
PERBANDINGAN KINERJA MODEL-MODEL TEMU KEMBALI PADA SISTEM TEMU KEMBALI INFORMASI DOKUMEN BERBAHASA INDONESIA 1)
2)
2)
3)
Amir Hamzah , F. Soesianto , Adhi Susanto , dan Jazi Eko Istiyanto , 1)
Jurusan Teknik Informatika, Institut Sains & Teknologi AKPRIND Yogyakarta E-mail :
[email protected],
[email protected] 2) Jurusan Teknik Elektro, Fakultas Teknik, Universitas Gadjah Mada 2
[email protected],
[email protected] 3) Jurusan Fisika, Fakultas MIPA, Universitas Gadjah Mada
ABSTRACT In a text information retrieval system, a huge volume of text and language characteristic has caused search system faced difficulties. Many models has been proposed to find an effective retrieval system, such as vector space model (VSM), probabilistic model (PM), Latent Semantic Indexing (LSI), artificial neural network model, Boolean model, fuzzy set model and genetic algorithm model. Among those models three models i.e. VSM, PM and LSI were considered to have many advantages. VSM model view document and query as vectors and retrieval results as document list ranked according to similarity between document voctor and query vector. PM model ranks document based on relevance probability of document to the query. LSI model transforms term-document matrix using SVD and projected document vectors and query vectors into lower dimension with higher accuracy. This research was conducted to compare the performances of those three retrieval model. VSM model was tested not only based on term matching but also extended to concept matching using clustering technique. In the PM model the maximum entropy approach was used. For LSI model, term-document matrix X was transformed according to [U,S,V]=svd(X) and k dimension was chosen so that document vector and query vector was transformed into k dimension. The parameters for measure the performance were recall, precision and F-measure. The test data collections were 1009 and 3000 news documents and 450 abstract documents. The results showed that the performance of VSM using concept approach was outperformed LSI model and probability model. Key word : retrieval model, concept-matching, clustering
INTISARI Dalam Sistem Temu Kembali Informasi (STKI) dokumen teks, volume teks yang sangat besar dan karakteristik bahasa telah menyebabkan sistem pencarian mengalami kesulitan. Banyak model telah diajukan untuk menemukan sistem temu kembali yang efektif, antara lain model ruang vektor (vector space model=VSM), model probabilistik (probabilistic model=PM), model semantik Latent Semantic Indexing (LSI), model jaringan syaraf tiruan, model boolean, model himpunan fuzzy dan model pendekatan algoritma genetika. Di antara banyak model tersebut tiga model, yaitu VSM, PM dan LSI dipercaya memiliki banyak keunggulan. Model VSM melihat dokumen dan query sebagai vektor dan hasil temu kembali merupakan daftar dokumen yang diranking berdasar kesamaan vektor query dan vektor dokumen. Model PM meranking dokumen berdasarkan probabilitas relevansi suatu dokumen terhadap query tertentu. Model LSI melakukan transformasi matriks kata dokumen menggunakan svd, dan memproyeksikan vektor dokumen dan vektor query pada dimensi yang lebih rendah dengan akurasi yang lebih tinggi. Penelitian ini bertujuan untuk melakukan studi perbandingan unjuk kerja tiga model tersebut. Model VSM diuji tidak hanya dalam formula dasar berbasis term tetapi dikembangkan dengan temu kembali berbasis konsep menggunakan teknik clustering. Untuk model PM digunakan pendekatan maximum entropy (ME) untuk menurunkan parameter-parameter modelnya. Sedangkan untuk model LSI, faktorisasi matrix kata-dokumen X menjadi tiga matriks U, S dan V yang memenuhi [U,S,V]=svd(X). Selanjutnya dipilih k tertentu sehingga vektor dokumen dan vektor query diproyeksikan dalam dimensi k tersebut. Parameter yang digunakan untuk membandingkan kinerja algoritma adalah recall, precision dan parameter F-measure. Data dokumen teks diambil koleksi dokumen berita sebanyak 1009 dokumen dan 3000 dokumen, serta dokumen abstrak akademik sebanyak 450 dokumen. Hasil penelitian menunjukkan bahwa baik pada koleksi dokumen berita maupun dokumen abstrak pendekatan VSM dengan pendekatan konsep lebih unggul dari pada model LSI dan model probabilitas. Kata kunci : model temu kembali, pencocokan konsep, clustering
220
PENDAHULUAN Sumber informasi teks on-line yang berkembang pesat telah menimbulkan kesulitan dalam organisasi, navigasi, temu kembali (Information Retrieval = IR). Melimpahnya data dalam koleksi juga telah menyebabkan tidak akuratnya retrieval oleh sistem IR (Zamir, 1999). Banyak model Sistem Temu Kembali Informasi (STKI) atau sistem IR telah diajukan dalam riset-riset di bidang IR. Menurut Grossman and Frieder (2004), sampai saat ini belum ada studi yang intensif membandingkan keseluruhan modelmodel retrieval, kecuali sebagian model-model saja. Perbandingan model inference network dengan model probabilistic dilakukan oleh Turtle (1991). Beberapa studi perbandingan LSI dengan VSM pernah dilakukan antara lain oleh Dumais (1994) dengan koleksi dokumen TIPSTER dan Karypis and Hong (2000) dengan koleksi dokumen CRANFIELD. Saat ini masih sangat sedikit penelitian dibidang sistem IR yang berbasis bahasa Indonesia (Nazief, 2000; Vega, 2001). Menurut Asian et.al.(2004), Indonesia dengan jumlah penduduk diatas dua ratus juta saat ini sangat memerlukan penelitian untuk optimasi sistem IR berbasis bahasa Indonesia. Beberapa kajian sistem IR bahasa Indonesia antara lain Mustangimah (1998) dengan objek teks dari abtrak penelitian BATAN. Penelitian lain adalah oleh Vega (2001) yang menggunakan model ruang vektor dan Anung (2002) yang menggunakan model jaringan syaraf tiruan. Penelitian yang membandingkan tiga model, yaitu Vector Space Model (VSM), Latent Semantic Indexing (LSI) dan Probabilistic Model (PM) belum pernah dilakukan. Ketiga model tersebut dipilih karena merupakan model-model yang banyak digunakan dan dianggap memiliki keunggulan masing-masing. Penelitian ini bertujuan untuk mengkaji unjuk kerja model-model retrieval dari tiga model yang paling banyak dikaji dan digunakan dalam sistem IR dengan menggunakan basis dokumen teks bahasa Indonesia. Hal-hal yang ingin dicapai dalam penelitian ini antara lain: 1. Mengkaji dan membandingkan model ruang vektor (VSM) pendekatan word-matching dan concept-matching dengan model LSI yang memiliki keunggulan reduksi dimensi dan pendekatan konsep pada operasi matching query dengan dokumen. 2. Mengkaji dan membandingkan VSM dan LSI dengan model pendekatan probabilistic yang memiliki cara pandang yang berbeda dalam merangking dokumen, yaitu relevansi diukur dengan tingkat probabilitas. Problem mendasar dalam IR terletak antara lain dalam persoalan pengindeksan term yang mewakili dokumen (Salton and Wong, 1975), teknik pencocokan query dengan dokumen (Rijsbergen,1979), dan penyajian hasil query (Zamir,1999). Dari tiga problem tersebut pencocokan query dengan dokumen untuk mendapatkan dokumen yang relevan merupakan persoalan yang melahirkan berbagai model retrieval. Sedikitnya sembilan model strategi retrieval telah diajukan, antara lain secara kronologis : strategi vector space model (VSM) (Salton and Wong 1975), probabilistic model (PM) (Robertson ,1977; Rijsbergen, 1979), extended boolean model (Fox,1983), neural network (Belew, 1989), Latent Semantic Indexing (LSI)(Deerwaster et.al, 1990), fuzzy set retrieval model (Lucarella and Morara, 1991), genetic algorithm (Yang and Korfhage, 1994; Chen, 1995), inference networks (Greift,1996), dan language model (Ponte and Croft, 1998). Dalam model ruang vektor (VSM) yang pertama kali diajukan oleh Salton and Wong (1975), baik dokumen maupun query diwakili oleh suatu vektor dalam ruang T, dimana T adalah cacah term terindeks yang diekstraksi dari koleksi dokumen setelah dibuang stop-word. Selanjutnya koleksi dokumen dapat diekspresikan dalam bentuk matriks Term-document berordo TxN berikut: X={xij} i =1,2,...,T; j =1,2,...,N
(1)
dengan T = cacah term terindeks N = cacah dokumen dalam koleksi xij= frekuensi kemunculan term ke-i dalam dokumen ke-j. Penggunaan frekuensi kemunculan term sebagai bobot kepentingan term dalam dokumen ternyata tidak cukup memadai. Penelitian tentang pengaruh pembobotan term dilakukan oleh Chisholm and Kolda (1999). Dari berbagai kombinasi fungsi pembobotan tersebut fungsi yang paling banyak digunakan adalah bentuk ntf atau TF-IDF ternormalisasi (Dhillon et.al., 2001), yaitu bobot term ke-i dalam dokumen ke-j diwakili oleh faktor TF, faktor IDF dan normalisasi di mana TF= ln( f ij ) +1, IDF = log N n i dan normalisasi adalah upaya agar vektor TF-IDF memiliki panjang 1. Sehingga formula pembobotan adalah :
221
wij=
N (ln( f ij ) 1).log ni (ln( f ij ) 1).log N n i
(2) 2
dengan : fij= frekuensi term ke-i dalam dokumen ke-j N = cacah dokumen dalam koleksi ni=cacah dokumen dalam koleksi yang memuat term ke-i Dalam model VSM relevansi dokumen D terhadap suatu query Q diranking berdasarkan similaritas vektor dokumen dengan vektor query. Dari berbagai macam fungsi similaritas yang ada seperti Dice, Jaccard, Overlap, asimmetric, Minowski distance, Euclidean distance, Pearson Correlation dan Cosine, ternyata fungsi similaritas yang terbaik adalah fungsi cosine (Rijsbergen, 1979; Strehl et.al., 2000). Fungsi similaritas cosine untuk 2 buah vektor satuan juga memiliki keuntungan dalam kompleksitas komputasi yang rendah karena hanya berupa perkalian dot-product dari vektor dokumen D dengan vektor query Q. T
sim(D,Q) =
D Q i 1
i
i
(3)
Model temu kembali VSM berbasis term memiliki kelemahan mendasar terkait dengan karakteristik bahasa yaitu persoalan synonimy dan polysemy. Sinonymy adalah karakter bahasa bahwa suatu konsep atau pengertian dapat diwakili oleh lebih dari satu kata (term). Hal ini berefek pada pemanggilan dokumen yang tidak relevan hanya karena dokumen tersebut mengandung term dalam query yang memiliki pengertian berbeda dengan user. Polysemy adalah karakter bahasa bahwa satu kata dapat memiliki lebih dari satu makna, hal ini juga berakibat tidak terpanggilnya dokumen relevan dalam koleksi karena query menggunakan ungkapan kata yang berbeda dengan dokumen. Untuk problem ini solusi yang dapat diajukan adalah menggunakan pendekatan retrieval berbasis konsep sebagai pengganti retrieval berbasis kata (Oscan and Aslandogan, 2004). Persoalan yang dihadapi dalam model terakhir ini terletak pada kenyataan bahwa mengekstrak konsep dari koleksi dokumen tidak semudah mengekstrak kata. Beberapa cara yang ditempuh untuk mengekstrak konsep dari koleksi dokumen antara lain dengan cara menyusun jaringan konsep (Zeng and Yang, 2003), menggunakan ontologi (Khan ,2000), atau memanfaatkan clustering dokumen (Karypis and Han, 2000). Penelitian Hamzah dkk (2007) menunjukkan bahwa dengan membuat model temu kembali berbasis konsep dapat meningkatkan efektivitas temu kembali dibandingkan dengan temu kembali berbasis term saja secara signifikan. Dalam penelitian ini konsep diekstrak dengan menggunakan clustering dokumen. Pusat kluster digunakan sebagai konsep dan disusun matriks konsep-dokumen. Selanjutnya score ranking relevansi dokumen dengan query digunakan formula : Document score = ( x ConceptScore) + ((1- ) x TermScore)
(4)
dengan adalah parameter bernilai 0 sampai 1 yang menunjukkan bobot relevansi konsep. TermScore adalah similaritas query dengan dokumen dengan term-matching (rumus (3)), sedangkan conceptScore adalah similaritas query dengan dokumen jika dokumen diwakili oleh vektor konsep. Model LSI mengkritisi model VSM karena matching antara query dan dokumen dilakukan dlam level kata (term), yang memiliki kelamahan karena faktor problem sinonimy dan polysemy. Dalam model LSI, matriks term-dokumen dalam rumus (1) didekomposisi dengan faktorisasi matriks SVD (Singular Value Decomposition) (Deerwaster et.al, 1990). Transformasi ini akan membuang noise (karena problem sinonimy dan polysemy) dalam dokumen sehingga dua dokumen yang relatif sama secara semantic akan berdekatan dalam ruang vektor hasil transformasi baru meskipun mereka menggunakan term yang berbeda. Proses transformasi SVD dapat dilakukan secara langsung dari matriks X={xij} dengan xij adalah frekuensi term-i dalam dokumen ke-j, yaitu : X = UV
T
(5)
Matriks adalah diagonal matriks yang elemennya adalah nilai-nilai singular. Sejumlah nilai k singular value terbesar dapat dipilih sedemikian sehingga representasi “latent semantic” berdimensi k digunakan 222
untuk mewakili matriks X. Nilai singular yang lain kemudian diset 0, dan hanya k kolom pertama dari T T matriks U dipertahankan (Uk), dan hanya k baris pertama dari V dipertahankan, dinotasikan dengan V k. Matriks baru Xk dibangkitkan sebagai aproksimasi X dengan k dimensi, sehingga menjadi : Xk = UkkV T
T k
(6)
T
Untuk memetakan dokumen d dan query q dalam dimensi T kedalam ruang dimensi k dilakukan T -1 T -1 dengan cara : dk=d Ukk dan qk=q Ukk . Proses selanjutnya untuk ranking dokumen dihitung dengan fungsi similaritas cosine dengan menggunakan vektor dokumen dan vektor query dalam dimensi k. Model PM mendefinisikan relevansi berdasarkan prinsip Probability Ranking Principle (PRP), yaitu efektivitas optimal akan dicapai jika dokumen diranking berdasarkan estimasi probabilitas relevan suatu dokumen terhadap suatu query (Robertson, 1977). Prinsip ini direalisir dengan menetapkan estimasi terhadap probabilitas dari komponen-komponen penyusun query (term-term) dan kemudian menggunakan untuk estimasi probabilitas relevansi dokumen terhadap query. Tiap term dalam query diberi bobot yang sebanding dengan probabilitas bahwa tiap satu term akan memanggil dokumen yang relevan. Andaikan suatu dokumen di mengandung T term dengan bobot (w1,w2,...,wT), dimana wi adalah estimasi probabilitas bahwa jika term ini muncul maka dokumen i akan relevan. Untuk tiap term dalam query, bobot (“odds”) bahwa dokumen akan relevan adalah :
P( wi | rel ) P( wi | nonrel)
(7)
Dengan asumsi term-term dalm query adalah independent maka estimasi bobot dokumen akan relevan adalah : T
log( i 1
T P( wi | rel ) P( wi | rel ) log P( wi | nonrel) i 1 P( wi | nonrel)
bahwa
(8)
Jika informasi relevansi suatu koleksi dokumen terhadap suatu query diketahui, maka rumus (8) dapat diestimasi dengan rumus sebagai berikut (Robertson and Jones, 1976) :
r 0.5 ( R r 0 . 5 ) wi = (n r 0.5) ( N n) ( R r ) 0.5
(9)
dengan : N = cacah dokumen dalam koleksi n = cacah dokumen yang memuat term ke i R = cacah dokumen yang relevan terhadap query r = cacah dokumen yang relevan terhadap query yang memuat term ke Skor relevansi dokumen terhadap query selanjutnya diperoleh dengan menjumlahkan bobot wi untuk tiap term dalam query jika dokumen tersebut mengandung term dalam query. Apabila informasi relevansi dokumen terhadap query tidak diketahui maka skor relevansi dokumen Dj dengan query Q dapat diestimasi dengan (Croft and Harper, 1979) : SC(Q,Dj) = C
dengan
T
T
i 1
i 1
qi d ij qi d ij log
N ni ni
(10)
N = cacah dokumen dalam koleksi ni=cacah dokumen yang memuat term ke i R = cacah dokumen yang relevan terhadap query r= cacah dokumen yang relevan terhadap query yang memuat term ke i
Untuk mengevaluasi kinerja berbagai algoritma temu kembali digunakan ukuran F-measure seperti berikut : 223
F-measure =
2 PR PR
(11)
dengan P = Precision, yaitu : Precision =
T otalcacah dokumen relevan yangdipanggil T otalCacah dokumen yangdipanggil
(12)
Dan R = Recall, yaitu : Recall =
Total cacah dokumen relevan yang dipanggil Total Cacah Relevan dalam koleksi
(13)
Bahan Penelitian berupa test-collection dokumen teks yang terdiri dari: a). Koleksi dokumen berita yang diambil dari Kompas Januari 2002-Juni 2002, berupa koleksi 1009 buah dokumen dan koleksi 3000 dokumen dengan statistik sebagai berikut : Tabel 1. Statistik Koleksi dokumen Test untuk Dokumen Berita Nama Koleksi Cacah Cacah Cch Kata Rerata juml dokumen cluster Uniq kata/dok Nws1009.dok 1009 21 18.259 425 Nws1370.dok 1370 25 23.398 411 Nws3000.dok 3000 35.282 397 b). Koleksi berupa abstrak dari artikel ilmiah yang diambil dari bidang teknologi Informasi pada berbagai seminar di Indonesia. Statistik untuk koleksi ini adalah sebagai berikut :
Nama Koleksi ABS.dok
Tabel 2. Nama Koleksi Dokumen Teks Akademik Abstrak Cacah Cacah Cch Kata Rerata juml dokumen cluster Unik kata/dok 450 30 84.690 203
Format identitas tiap dokumen adalah seperti pada Gambar 1. berikut :
news10513-html mayjen syafrie samsuddin akan jadi kapuspen tni jakarta media mantan pangdam jaya mayjen syafrie samsuddin akan menjadi kapuspen tni menggantikan 1. Format Koleksi Dokumen untuk Tes marsekal Gambar muda graito husodo menurut berita informasi yang Gambar 1. Formatkamis dokumen dalam koleksi diperoleh antara jakarta syafrie samsuddin menjadi kapuspen tni dan serah terima jabatan akan dilakukan pada akhir februari 2002 m-1
Gambar 1. Format Koleksi Dokumen berita untuk Tes
Dari koleksi tersebut dilakukan langkah-langkah pre-procesising berikutnya, yang terdiri dari parsing, pembuangan stop-word (stop-word filtering) dan pembobotan term (term-weighting). Setiap koleksi dilengkapi dengan daftar query dan relevance judgement untuk tiap dokumen terhadap query yang bersangkutan. Adapun daftar query tersebut seperti Tabel 3, Tabel 4, Tabel 5 dan Tabel 6.
224
No 1 2 3 4 5 6 7 8 9 10
Tabel 3 Daftar Query untuk Koleksi Dokumen Berita Nws1009.dok Query Num of Relevan Doc pemberangkatan jamaah haji pertandingan piala dunia pasar uang dolar penumpasan gam aceh kerusuhan ambon maluku pertandingan tinju tyson lewis tki indonesia di malaysia penyelesaian kaus tommy suharto pertandingan tenis junior penyelesaian kasus bulog akbar tanjung
38 183 67 61 51 21 30 67 30 83
Tabel 4. Daftar Query untuk Koleksi Dokumen Berita Nws1370.dok No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Query pemberangkatan jamaah haji pertandingan piala dunia kerusuhan ambon maluku penumpasan gam aceh tki indonesia di malaysia obligor pkps tidak kooperatif pasar uang dolar kerjasama anti terorisme pertandingan tinju tyson lewis pertandingan tenis junior pertandingan piala thomas penyelesaian kasus bulog akbar tanjung penyelesaian kasus tommy suharto bppn, konglomerat dan tender bca sikap dpr dan pemerintah pada kunjungan pm australia howard ke indonesia kecelakaan peswat terbang korban air bah dan banjir jakarta dan sekitarnya Presiden ke timtim hadiri pelantikan xanana kunjungan megawati ke luar negeri dampak kenaikan harga bbm Program dan krisis nuklir iran kunjungan bush ke Indonesia kasus dan skandal blbi anggaran pendidikan nasional krisis karena langka minyak tanah
Num of Relevan Doc 40 183 51 62 30 34 67 83 21 30 20 84 67 32 12 22 42 35 41 18 150 96 53 36 61
225
Tabel 5. Daftar query untuk koleksi Nws3000.dok No 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Query "hubungan indonesia australia setelah timor timur" "kecelakaan pesawat udara indonesia" "pemberantasan narkoba" "situasi banjir jakarta" "duta besar indonesia" "nama suami megawati" "pemenang pertandingan piala thomas jenis apapun asal indonesia" "nama bos manchester united" "laporan piala dunia" "nilai tukar rupiah terhadap dolar as" "aktor aktris calon atau pemenang oscar" "akibat kenaikan harga bbm" "persidangan tommy soeharto" "kunjungan luar negeri megawati"
Rel Doc 10 22 17 40 31 32 8 27 60 74 3 19 45 36
Tabel 6. Daftar Query untuk Koleksi Dokumen Akademik Abs2.dok No 1 2 3 4 5 6 7 8 9 10
Query Aplikasi logika fuzy Sistem informasi Jaringan syaraf tiruan Pengolahan citra Algoritma genetika Database Sistem pendukung keputusan GPS GPRS komunikasi data Rekayasa perangkat lunak Keamanan system informasi
Num of Rel Doc 20 45 17 10 17 15 16 29 24 21
HASIL DAN PEMBAHASAN Contoh hasil temu kembali (retrieval) berbasis konsep untuk koleksi Nws1009.dok untuk query “pertandingan piala dunia” tersaji seperti dalam Gambar 2. Terlihat jika output dibatasi dengan 150 dokumen metode VSM CptBR memberikan dokumen relevan yang terpanggil adalah 149, sedangkan metode Prob memberikan 146 dokumen relevan.
Gambar 2. Pemrosesan query 2:”pertandingan piala dunia” dengan CptBR
226
Gambar 3. Pemrosesan query 2:”pertandingan piala dunia” dengan Prob Perbandingan CptBR, metode Prob (model PM) dan metode LSI untuk koleksi Nws1009.dok digunakan nilai Cut-Off sebanyak nilai dokumen relevan dalam koleksi sehingga nilai Precision dan Recall akan bernilai sama dan nilai F-measure adalah nilai tersebut. Pada model VSM-CptBR koleksi dikluster dengan jumlah kluster tertentu dengan bobot konsep tertentu. Dalam hal ini jumlah kluster dan bobot konsep ditentukan secara eksperimental. Dengan jumlah kluster sama dengan jumlah topik dalam koleksi optimasi untuk koleksi Nws1009.dok adalah sebagai Gambar 4 berikut. Terlihat dari Gambar 4 tersebut bahwa nilai 0,5 keatas akan menyebabkan nilai rerata F-measure tinggi sedangkan untuk di bawah 0,5 nilai rerata F-measure akan menurun. Ini menunjukkan bahwa bobot konsep akan memperbaiki retrieval jika ditetapkan nilai >0,5.
Rerata F seluruh query
0,95
0,92
0,93 0,93 0,93 0,93 0,93
0,90
0,90 0,85
0,88 0,84 0,82
0,80 0,75 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Beta
Gambar 4. Optimasi untuk koleksi Nws1009.dok dengan kluster 21 Pada retrieval dengan LSI juga diperlukan optimasi nilai k yang hanya dapat ditentukan dengan eksperimen. Untuk koleksi Nws1009.dok optimasi nilai k diperoleh dengan percobaan pada beberapa nilai k yang hasilnya seperti pada Gambar 5 berikut.
227
Rerata F-measure
1,00 0,80
0,89 0,86 0,84 0,83 0,86 0,81 0,67
0,67
0,60
0,58 0,55
0,40 0,20 -
10
15
21
25
30
40
50
100 150 200
Nilai k
Gambar 5. Optimasi nilai k dalam LSI untuk koleksi Nws1009.dok Perbandingan nilai-nilai F-measure untuk seluruh query adalah sebagai Tabel 7 berikut. Dan rata-rata F-measure untuk semua query disajikan dalam grafik Gambar 5.
No
Tabel 7 Efektifitas temu kembali PM, LSI dan CptBR koleksi Nws1009.dok Query Num of F-PM F-LSI F-CptBr Rel Doc
1
pemberangkatan jamaah haji
38
0,8158
0,4474
0,8421
2
pertandingan piala dunia
183
0,8579
0,9454
0,9454
3
pasar uang dolar
67
0,9851
0,9851
0,9851
4
penumpasan gam aceh
61
0,9672
0,9508
0,9672
5
kerusuhan ambon maluku
51
0,8824
0,8431
0,9608
6
pertandingan tinju tyson lewis
21
1,0000
1,0000
1,0000
7
tki indonesia di malaysia
30
0,7667
0,9667
0,9000
8
penyelesaian kasus tommy suharto
67
0,7612
0,9104
0,9552
9
pertandingan tenis junior
30
0,4000
0,8000
0,9333
10
penyelesiaian kasus bulog akbar tanjung
83
0,8313
0,8916
0,9518
0,8268
0,8740
0,9441
Rata-rata
Tabel 8 Hasil Uji statistik Retrieval CptBR-PM dan CptBR-LSI Nws1009.dok
Dari tabel 8 terlihat bahwa perbedaan metode CptBR dengan metode PM adalah signifikan secara statistik pada alpha 0,044 sedangkan perbedaan metode CptBR dengan LSI tidak berbeda signifikan.
228
Rerata F-measure
Rerata F-measure kol:Nws1009.dok 1,0000 0,9500 0,9000 0,8500 0,8000 0,7500 PM
LSI
CptBR
Metode retrieval
Gambar 5. Perbandingan efektivitas retrieval koleksi Nws1009.dok Pada koleksi Nws1370.dok dengan query sebanyak 25 buah menghasilkan perbandingan nilai F-measure seperti terlihat pada Tabel 9 berikut. Dari pengujian dengan uji t pada uji beda rata-rata antara CptBR dan PM terlihat bahwa perbedaan signifikan terjadi pada taraf signifikansi 0,02 dan untuk perbandingan CptBR dengan LSI perbedaan tidak sgnifikan . Uji beda dapat dicermati pada Tabel 10.
No
Query
Tabel 9 Efektifitas temu kembali PM, LSI dan CptBR koleksi Nws1370.dok Num of Temu kembali (F-measure) Rel Doc IFS LSI CptBR
1
pemberangkatan jamaah haji
40
0,8000
0,8250
0,8250
2
pertandingan piala dunia
183
0,8689
0,9290
0,9235
3
kerusuhan ambon maluku
51
0,8824
0,9020
0,9216
4
penumpasan gam aceh
62
0,9677
0,9839
0,9839
5
tki indonesia di malaysia
30
0,7667
0,7667
0,7667
6
obligor pkps tidak kooperatif
34
0,6765
0,7647
0,7059
7
pasar uang dolar
67
0,9851
0,9851
0,9851
8
kerjasama anti terorisme
83
0,5663
0,7229
0,7470
9
pertandingan tinju tyson lewis
21
1,0000
1,0000
1,0000
10
pertandingan tenis junior
30
0,3333
0,9667
0,9667
11
pertandingan piala thomas
20
0,3500
0,1500
0,3500
12
penyelesaian kasus bulog akbar tanjung
84
0,8333
0,9643
0,9405
13
penyelesaian kasus tommy suharto
67
0,7463
0,9701
0,9701
14
bppn, konglomerat dan tender bca
32
0,6563
0,6875
0,6875
15
12
0,8333
0,8333
0,9167
16
sikap dpr dan pemerintah pada kunjungan pm australia kecelakaan peswat terbang
22
0,8182
0,6364
0,8182
17
korban air bah dan banjir jakarta dan sekitarnya
42
0,9524
0,9762
0,9762
18
presiden ke timtim hadiri pelantikan xanana
35
0,6000
0,5714
0,7143
19
kunjungan megawati ke luar negeri
41
0,5610
0,5366
0,7317
20
dampak kenaikan harga bbm
18
0,6667
0,3333
0,6111
21
program dan krisis nuklir iran
150
0,9933
1,0000
1,0000
22
kunjungan bush ke Indonesia
96
0,8958
0,9375
0,9479
23
kasus dan skandal blbi
53
0,9434
0,9811
0,9057 0,8333 0,9836
24
anggaran pendidikan nasional
36
0,8611
0,9167
25
krisis karena langka minyak tanah
61
0,9508
0,9836
0,7803
0,8130
rata-rata
0,8485
229
Tabel 10 Hasil Uji statistik Retrieval CptBR-PM dan CptBR-LSI Nws1370.dok
Pada koleksi Nws3000.dok dengan query sebanyak 14 buah menghasilkan perbandingan nilai Fmeasure seperti terlihat pada Tabel 11 berikut.
No 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Tabel 11 Efektifitas temu kembali PM, LSI dan CptBR koleksi Nws3000.dok Query PM LSI CptBR 0,700 "hubungan indonesia australia setelah timor timur" 0,200 0,545 "kecelakaan pesawat udara indonesia" 0,273 0,455 0,824 "pemberantasan narkoba" 0,647 0,706 0,225 "situasi banjir jakarta" 0,150 0,125 0,355 "duta besar indonesia" 0,226 0,258 0,344 "nama suami megawati" 0,188 0,125 "pemenang pertandingan piala thomas jenis apapun asal indonesia" 0,125 0,500 0,500 0,556 "nama bos manchester united" 0,259 0,444 0,317 "laporan piala dunia" 0,150 0,167 0,932 "nilai tukar rupiah terhadap dolar as" 0,770 0,905 "aktor aktris calon atau pemenang oscar" 0,667 0,667 "akibat kenaikan harga bbm" 0,579 0,579 0,526 0,822 "persidangan tommy soeharto" 0,711 0,756 0,528 "kunjungan luar negeri megawati" 0,306 0,167 0,518 0,324 0,463 Tabel 12 Hasil Uji statistik Retrieval CptBR-PM dan CptBR-LSI Nws3000.dok
Tabel 12 yang menyajikan uji beda rata-rata F-measure menunjukkn hasil yang konsisten dengan koleksi sebelumnya, yaitu perbedaan antara CptBR dengan PM signifikan sedangkan uji beda antara CptBR dengan LSI tidak berbeda signifikan. Pada koleksi Abs.dok yang memiliki keragaman topik cukup tinggi menyebabkan struktur kluster tidak sebaik koleksi berita. Jika konsep yang diambil disandarkan pada struktur kluster maka bobot konsep yang tepat juga harus dilakukan optimasi. Gambar 6 menunjukkan bahwa pad nilai =0,5 bukan bobot konsep yang tepat, tetapi nilai =0,2 adalah bobot konsep yang mengoptimalkan hasil retrieval berdasarkan rata-rata nilai F-measure. Untuk itu pada koleksi abstrak ini digunakan nilai =0,2 sebagai bobot konsep. Nilai yang rendah menunjukkan bahwa pemberian bobot konsep yang tinggi akan cenderung menurunkan hasil temu kembali basis kata, sedangakn jika digunakan bobot =0 yang berarti temu kembali hanya berbasis kata saja maka nilai efektivitas tidak optimal. Ini menunjukkan bahwa pada struktur kluster yang jelek sekalipun dengan memilih yang tepat akan dapat meningkatkan kinerja temu kembali. 230
Rerata F seluruh query
0,53
0,54
0,52
0,52
0,52 0,51
0,50
0,50
0,48 0,47
0,48
0,46 0,45
0,46
0,45
0,44 0,42 0,40 IFS 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Beta
Gambar 6. Optimasi untuk koleksi Abs.dok dengan kluster 30 Pada koleksi abstrak Abs.dok dengan query sebanyak 10 buah menghasilkan perbandingan nilai F-measure seperti terlihat pada Tabel 13 berikut. Uji statistik pada koleksi ini ditunjukkan pada Tabel 14.
Tabel 13 Efektifitas temu kembali PM, LSI dan CptBR koleksi Nws3000.dok No Query DocRel PM LSI CptBR 1 Aplikasi logika fuzzy 32 0,8438 0,4375 0,6875 2
Sistem informasi
46
0,4130
0,5435
0,5217
3
Jaringan syaraf tiruan
20
0,7000
0,6500
0,7000
4
Pengolahan citra
12
0,6667
0,5833
0,6667
5
Algoritma genetika
18
0,3889
0,3889
0,7222
6
Database
22
0,5000
0,5455
0,5909
7
Sistem pendukung keputusan
21
0,4286
0,5714
0,6667
8
GPS GPRS komunikasi data
34
0,2059
0,1765
0,3235
9
Rekayasa perangkat lunak
29
0,5172
0,5172
0,5517
10
keamanan sistem informasi
18
0,3889
0,3889
0,4444
0,4647
0,5053
0,6032
Average
Tabel 14 Hasil Uji statistik Retrieval CptBR-PM dan CptBR-LSI Nws3000.dok
Dari Tabel 14 uji statistik menunjukkan konsisten dengan tiga koleksi sebelumnya. Metode temu kembali CptBR berbeda signifikan baik dengan LSI maupun dengan metode PM. Menguraikan hasil analisis kualitatif dan/atau kuantitatif dengan penekanan pada jawaban atas permasalahan.
KESIMPULAN Dari uraian sebelumnya dapat disimpulkan bahwa model retrieval berbasis ruang vektor dengan pendekatan konsep dengan melakukan clustering terlebih dahulu mengungguli dua pendekatan lain yang memiliki landasan teori cukup kokoh, yaitu model retrieval pendekatan probabilitas (model probability) dan model retrieval dengan pendekatan transformasi matriks dengan SVD, yakni model LSI. Perbedaan efektivitas ini cukup berbeda secara statistik untuk semua koleksi pada perbandingan kinerja antara model CptBR dengan model PM sedangkan untuk perbandingan CPtBR dengan LSI pada ketiga koleksi berita ternyata tidak signifikan secara statistik tetapi pada koleksi abstrak berbeda secara statistik. 231
DAFTAR PUSTAKA Anung, B.A., 2001, “Pendekatan Multi-dimensi Dokumen dalam Sistem Temu-kembali Informasi Menggunakan Model Spreading Activation”, Thesis S2, Program Studi Ilmu Komputer, Fakultas Ilmu Komputer Universitas Indonesia. Asian, J., H. E. Williams, and S. M. M. Tahaghoghi, 2004, “Tesbed for Indonesian Text Retrieval”, 9th Australian Document Computing Symposiom, Melbourne December, 13 2004. Belew, R., 1989, “Adaptive Information Retrieval”, Proceeding of the Twelfth Annual International ACM SIGIR Concference on Research and Development in Information Retrieval, pages 11-20. Chisholm, E. and T. G. Kolda, 1999, “New Term Weighting Formula for the Vector Space Method in Information Retrieval”, Research Report, Computer Science and Mathematics Division, Oak Ridge National Library, Oak Ridge, TN 3781-6367, March 1999. Croft, W.B. and Harper, D.J., 1979, “Using Probabilistic Models of Document Retrieval without Relevance Information”, Journal of Documentation, 35(4):282-295. Croft, W.B., 1980, “A Model of Cluster Searching based on Classification”, Information System, 5:189-195 Dhillon, S. I., J. Fan, and Y. Guan, 2001, “Efficient Clustering of Very Large Document Collection”, www.citeseer.ist.psu.edu/dhillon01.html Dumais, S.T., Latent Semantic Indexing, :TREC-3 report. In Proceeding of the Third Text Retrieval Conference (TREC-3), pages 219-230 Fox, E.A., 1983, “Extending the Boolean and Vector Space Models of Information Retrieval with P-Norm Queries and Multiple Concept Types”, PhD Thesis, Cornell University. Grossman, D. A. and O. Frieder, 2004, Information Retrieval Algorithms and Heuristics, Springer, 2 edition, 2004.
nd
Hamzah, A, A. Susanto, F. Soesianto, and J.E. Istiyanto, 2007, Concept-Based Information Retrieval for Text Document in Bahasa Indonesia, International Conceference on Instrumentation, Communication, and Information Technology, ICICI2007, Grand Aquila Hotel, ITB-Bandung August 8-9, 2007 Karypis, G. and Han Eui-Hong,2000, “Concept Indexing A Fast Dimensionality Reduction Algorithm with Applications to Document Retrieval and Categorization”, Technical Report TR-00-0016, University of Minnesota. www.cs.umn.edu/karypis Khan,L., R., 2000, “Ontology-Based Information Selection”, PhD Dissertation, Faculty of the Graduate School, University of Southern California. Lucarella, D. and R. Morara, 1991, FIRST: Fuzzy Information Retrieval System, Journal of Informatiuon Science, 17(2):81-91 Mustangimah,1998, “Efektivitas Sistem Temu-Kembali Informasi dan Analisis Bibliomterik: Aplikasi pada Dokumen Bidang Nuklir Berbahasa Indonesia”, Thesis S2, Program Studi Ilmu Komputer, Fakultas Ilmu Komputer Universitas Indonesia Nazief, B., 2000, Development of Computational Linguistic Research: a Challenge for Indonesia”, Computer Science Center, University of Indonesia. Oscan, R. and Y.A. Aslandogan, 2004, “Concept Based Information Access Using Ontologies and Latent Semantic Analysis”, Technical Report CSE-2004-8, Dept. of Computer Science and Engineering, Universitas of Texas at Arlington. Rijsbergen, C.J. van, 1979, Information Retrieval, Infomation Retrieval Group, University of Glasgow, UK.
232
Robertson, S.E. and K.S. Jones, 1976, Relevance Weighting of Search Term, Journal of American Society of Information Science, 27(3):129-146. Robertson, S.E.,1975, “The Probability Ranking Principle in IR”, Journal in Documentation, 33(4):294304. Salton, G., A. Wong, and C.S. Yang, 1975, “A Vector Space Model for Automatic Indexing”, Communication of the ACM, Vol.18. Num.11, Nov 1975. Strehl, A., J. Ghosh, and R. Mooney, 2000, “Impact of Similarity Measures on Web-Page Clustering”, th Proceeding of the Workshop of Artificial Intelligent for Web Search, 17 National Conference on Artificial Intelligence, July 2000. Tala, F. Z., 2004, “A Study of Stemming Effect on Information Retrieval in Bahasa Indonesia”, Master Thesis, Universiteit van Amsterdam, The Netherlands. Tombros, A., 2002, The Effectiveness of Query-Based Hierarchic Clustering of Documents for Information Retrieval, PhD Thesis, Univerity of Glasgow. Turtle H., 1991, Inference Network for Document Retrieval, PhD Thesis, University of Massachusetts, Amhherst. Vega, V. B. , 2001, Information Retrieval for the Indonesian Language, Master's thesis, National University of Singapore. Yang , J.J. and R. Korfhage, 1994, Query Modification Using Genetic Algorithm in Vector Space Models, International Journal of Expert System, 7(2):165-191. Zamir, O.E., 1999, Clustering Web Document : A Phrase-Based Method for Grouping Search Engine Result, PhD. Dissertation, University of Washington. Zeng, J. and Yang, Y., “Information Retrieval Based on Conceptual Network”, Internet Research & Development Center, Institute of Automation, Chinese Academy of Sciences, Beijing 100080, China, 2003
233
