Dapatan Semula Maklumat Bahasa Melayu Menggunakan Pengindeksan Semantik Terpendam

.

Jurnal Antarabangsa (Teknologi Maklutnat) 3(2002): 1-10

Dapatan Semula Maklumat Bahasa Melayu Menggunakan

Pengindeksan Semantik Terpendam

MUHAMAD TAUFIK ABDULLAH. FATIMAH AHMAD,

RAMLAN MAHMOD & TENGKU MOHAMMED TENGKU SEMBOK

ABSTRAK

Pengindeksan semantik terpendam ialah satu varian daripada kaedah ruang

vektor iaitu satu anggaran pangkat-rendah kepada perwakilan ruang vektor

untuk pangkalan data digunakan. Idea utama dalam model pengindeksan

semantik terpendam adalah untuk memetakan setiap vektor dokumen dan

pertanyaan ke dalam satu ruang berdimensi lebih rendah yang berkaitan

dengan konsep-konsep. Ini dilaksanakan dengan memetakan vektor-vektor

istilah indeks ke dalam ruang berdimensi lebih rendah tersebut. Dakwaannya,

capaian di dalam ruang yang dikecilkan mungkin lebih baik daripada

capaian di dalam ruang istilah-istilah indeks. Dalam makalah ini, sebagai

tambahan kepada kaedah ruang vektor, kaedah pengindeksan semantik

terpendam digunakan untuk membina sistem dapatan semula maklumat

bahasa Melayu.

Kata Kunci: dapatan semula maklumat bahasa Melayu, pengindeksan semantik

terpendam, dapatan semula maklumat, kaedah ruang vektor.

ABSTRACT

Latent semantic indexing is a variant of the vector space method in which a

low-rank approximation to the vector space representation of the database is

employed. The main idea in latent semantic indexing model is to map each

document and query vector into a lower dimensional space which is associated

with concepts. This is accomplished by mapping the index term vectors into

this lower dimensional space. The claim is that retrieval in the reduced space

may be superior to retrieval in the space of index terms. In this paper, in

addition to vector space method, latent semantic indexing method is applied

to develop Malay language information retrieval system.

Keywords: Malay language information retrieval, latent semantic indexing,

information retrieval, vector space method.

PENGENALAN

Dapatan semuia maklumat (IR) melibatkan perwakilan, simpanan, organisasi

dan capaian item maklumat. IR mempunyai paradigma seperti berikut:

pengguna ingin mendapatkan dokumen tentang tajuk tertentu; pengguna

memberikan penerangan teks dalam bentuk bebas tentang tajuk untuk menjadi

pertanyaan; daripada pertanyaan tersebut enjin IR mendapatkan istilah-istilah

indeks; semua istilah indeks dipadankan dengan istilah indeks yang diperolehi

dari dokumen yang telah diproses terdahulu; dokumen yang mempunyai

padanan terbaik diberikan kepada pengguna dalam susunan berpangkat [BaezaYates 1999; Grefenstette 1998].

Penilaian IR ke atas kejayaan ialah kepersisan dan panggilan semuia.

Kepersisan ialah berapa banyak dokumen dalam senarai berpangkat yang

berkaitan dengan pertanyaan. Manakala panggilan semuia ialah berapa banyak

dokumen yang berkaitan yang mungkin boleh dijumpai dalam koleksi dokumen

yang berada dalam senarai capaian.

Antara kaedah popular dapatan semuia maklumat yang dibangunkan

ialah kaedah yang berasaskan ruang vektor. Data dimodelkan sebagai satu

matriks dan pertanyaan pengguna terhadap pangkalan data diwakilkan sebagai

satu vektor. Dokumen-dokumen yang berkenaan dalam pangkalan data

ditentukan melalui operasi vektor. Setiap dokumen diwakilkan dengan satu

vektor, dengan setiap komponen menunjukkan kepentingan untuk suatu

istilah dalam mewakili semantik atau makna bagi dokumen. Vektor untuk

semua dokumen dalam pangkalan data disimpan sebagai lajur bagi satu

matriks.

Kaedah pengindeksan semantik terpendam (LSI) ialah satu variasi daripada

model ruang vektor dengan anggaran pangkat rendah kepada perwakilan

ruang vektor untuk pangkalan data digunakan. Matriks asal digantikan

dengan matriks lain yang hampir sama dengan matriks asal tetapi ruang

lajumya hanya subruang daripada ruang lajur matriks asal.

PERWAKILAN ISTILAH DAN DOKUMEN

Dalam model ruang vektor dan LSI, istilah dan dokumen diwakilkan oleh

satu matriks m x n, A. Setiap istilah unik m dalam koleksi dokumen diberikan

satu bans dalam matriks, manakala setiap dokumen n dalam koleksi diberikan

satu lajur dalam matriks. Elemen bukan sifar aij, iaitu A = [aij] menunjukkan

istilah / wujud dalam dokumen; dan memberikan bilangan kewujudan istilah

dalam dokumen tersebut. Memandangkan bilangan istilah dalam sesuatu

dokumen biasanya begitu sedikit berbanding dengan bilangan istilah dalam

seluruh koleksi dokumen, matriks A adalah sangat jarang.

2

Gambaran SVD ditunjukkan dalam Rajah 1. Kawasan gelap U, V dan garisan

dalam X mewakili Ak

.

KAEDAH RUANG VEKTOR

Kaedah ruang vektor digunakan dalam penyeiidikan dapatan semula makiumat lebih

30 tahun lalu [Salton dan McGill 1983]. Selepas matriks istilah-dokumen dibina,

pengiraan persamaan boleh dilakukan antara dua objek teks. Satu objek teks q

diwakilkan dengan satu vektor n x 7, seperti satu lajur daripada matriks A dan

dengan jenis pemberat istilah yang sama digunakan. Seterusnya persamaan antara

objek teks qt dan q2 dapat dikira dengan nilai kosinus, iaitu:

PENGINDEKSAN SEMANTIK TERPENDAM

Pengindeksan semantik terpendam direka bentuk untuk mengatasi masalah

dalam kaedah vektor [Deerwester et al. 1990; Berry, Dumais dan O'Brien

1995]. Idea utama LSI ialah pemetaan setiap dokumen dan pertanyaan ke

dalam ruang dimensi yang lebih rendah yang berkaitan dengan konsep. LSI

4

juga bermula dengan pembentukan matriks istilah-dokumen. Kemudian matriks

ini dianalisis menggunakan penghuraian nilai singular untuk mengekstrak

struktur berkenaan hubung kait antara dokumen-dokumen dan istilah-istilah.

Proses ini boleh mengenalpasti, misalnya "car" dan "automobile" bila

digunakan dalam konteks yang sama dalam seluruh koleksi, dan maklumat

ini boleh diguna untuk meningkatkan dapatan semula.

Pertanyaan dibentuk menjadi dokumen-pseudo yang memberikan lokasi

pertanyaan dalam ruang istilah-dokumen yang dikecilkan. Dengan q, satu

vektor elemen bukan sifar mengandungi pemberat (menggunakan skema

pemberat tempatan dan global yang sama dengan koleksi dokumen) frekuensi

istilah dalam pertanyaan, dokumen-pseudo, q diwakilkan sebagai:

Persamaan di antara dua dokumen di dalam koleksi dokumen adalah

menggunakan vektor dokumen, Vk

iaitu:

EKSPERIMEN MENGGUNAKAN KAEDAH VEKTOR DAN LSI

Eksperimen dijalankan terhadap satu koleksi dokumen bahasa Inggeris dan

dokumen bahasa Melayu. Capaian kepada koleksi dokumen ini dibuat melalui

pertanyaan daripada bahasa Melayu dan Inggeris dengan menggunakan

kaedah vektor dan LSI.

5

Koleksi dokumen bahasa Melayu terdiri dari teks terjemahan Al-Quran

bahasa Melayu yang mempunyai 6,236 dokumen. Koleksi dokumen ini

mengandungi 196,071 patah perkataan dengan 7,526 perkataan yang unik.

Manakala koleksi dokumen bahasa Inggeris terdiri daripada teks terjemahan

Al-Quran bahasa Inggeris yang terdiri mempunyai 6,236 dokumen yang

setara dengan dokumen-dokumen bahasa Melayu. Koleksi dokumen ini

mengandungi 167,477 patah perkataan dengan 6,383 perkataan yang unik.

Set pertanyaan bahasa Melayu mengandungi 36 pertanyaan dalam bentuk

bahasa tabii. Manakala pertanyaan bahasa Inggeris adalah 36 pertanyaan

dalam bentuk bahasa tabii yang merupakan terjemahan daripada pertanyaan

bahasa Melayu.

Empat eksperimen dijalankan terhadap setiap koleksi dokumen iaitu:

a) eksperimen menggunakan kaedah vektor tanpa penggunaan pengakar

bahasa

b) eksperimen menggunakan kaedah LSI tanpa penggunaan pengakar bahasa

c) eksperimen menggunakan kaedah vektor dengan penggunaan pengakar

bahasa

d) eksperimen menggunakan kaedah LSI dengan penggunaan pengakar

bahasa

Eksperimen dijalankan bermula dengan pembentukan matriks istilahdokumen dan matriks istilah-pertanyaan. Elemen bagi matriks ini ialah

frekuensi istilah dalam dokumen atau pertanyaan yang berkenaan. Seterusnya

diumpukkan nilai pemberat log-entropi kepada setiap elemen bukan sifar

matriks tersebut.

Capaian menggunakan kaedah vektor melibatkan langkah seperti berikut:

a) kira persamaan setiap pertanyaan dengan setiap dokumen menggunakan

nilai kosinus

b) susun senarai dokumen berkenaan mengikut nilai kosinus dalam tertib

menurun untuk setiap pertanyaan

Manakala capaian menggunakan kaedah LSI pula melibatkan langkah

seperti berikut:

a) kira SVD untuk matriks istilah-dokumen pada nilai k sebanyak 200

b) bina dokumen-pseudo untuk matriks istilah-pertanyaan

c) gabung dokumen-pseudo dengan vektor dokumen

d) kira persamaan dokumen-pseudo dengan setiap dokumen

e) susun senarai dokumen berkenaan mengikut nilai persamaan dalam tertib

menurun untuk setiap pertanyaan

Seterusnya eksperimen diulang dengan menggunakan pengakar bahasa

yang berkenaan atas indeks koleksi dokumen dan set pertanyaan. Pengakar

Ahmad (1995) digunakan untuk koleksi bahasa Melayu dan pengakar Porter

(1980) digunakan untuk koleksi bahasa Inggeris.

6

KEPUTUSAN DAN PERBINCANGAN

Keputusan yang diperolehi daripada empat eksperimen untuk dua koleksi

dokumen ditunjukkan dalam bahagian berikut. Keputusan untuk dapatan

semula maklumat bahasa Melayu ditunjukkan pada Jadual 1. Jadual ini

menunjukkan kepersisan untuk capaian dokumen bahasa Melayu menggunakan

kaedah ruang vektor (VBM); capaian dokumen bahasa Melayu menggunakan

kaedah pengindeksan semantik terpendam (LSIBM); capaian dokumen bahasa

Melayu menggunakan kaedah ruang vektor dan pengakar (VBM-P); dan

capaian dokumen bahasa Melayu menggunakan kaedah pengindeksan semantik

terpendam dan pengakar (LSIBM-P).

Graf kepersisan lawan panggilan semula untuk capaian dokumen bahasa

Melayu diplotkan pada Rajah 2. Secara purata didapati tanpa menggunakan

pengakar, capaian menggunakan kaedah LSI ialah 8.5% lebih tinggi

kepersisannya berbanding kaedah vektor. Manakala capaian menggunakan

kaedah LSI ialah 7.5% lebih tinggi kepersisannya berbanding kaedah vektor

dengan menggunakan pengakar. Didapati penggunaan pengakar telah dapat

meningkatkan kepersisan sebanyak 15.4% untuk kaedah vektor dan kepersisan

meningkat sebanyak 14.3% bagi kaedah LSI.

Keputusan untuk dapatan semula maklumat bahasa Inggeris ditunjukkan

pada Jadual 2. Jadual ini menunjukkan kepersisan untuk capaian dokumen

bahasa Inggeris menggunakan kaedah ruang vektor (VBI); capaian dokumen

bahasa Inggeris menggunakan kaedah pengindeksan semantik terpendam

(LSIBI); capaian dokumen bahasa Inggeris menggunakan kaedah ruang vektor

7

dan pengakar (VBI-P); dan capaian dokumen bahasa Inggeris menggunakan

kaedah pengindeksan semantik terpendam dan pengakar (LSIBI-P).

Seterusnya graf kepersisan lawan panggilan semula untuk capaian

dokumen bahasa Inggeris diplotkan pada Rajah 3. Daripada niiai purata

didapati tanpa menggunakan pengakar, capaian menggunakan kaedah LSI

ialah 25.8% lebih tinggi kepersisannya berbanding kaedah vektor. Manakala

capaian menggunakan kaedah LSI ialah 11.7% lebih tinggi kepersisannya

8

berbanding kaedah vektor dengan menggunakan pengakar. Di samping itu,

didapati penggunaan pengakar dapat meningkatkan kepersisan sebanyak

47.1% untuk kaedah vektor dan kepersisan meningkat sebanyak 30.6% bagi

kaedah LSI.

Perbandingan hasil eksperimen untuk koleksi dokumen bahasa Melayu

dan Inggeris ditunjukkan pada Rajah 4.

Daripada perbandingan ini didapati capaian menggunakan kaedah LSI

menghasilkan kepersisan lebih tinggi berbanding kaedah vektor sama ada

9

tanpa menggunakan pengakar atau dengan menggunakan pengakar. Keputusan

ini adalah selaras untuk koleksi dokumen kedua-dua bahasa.

KESIMPULAN

Hasil kajian ini menunjukkan bahawa penggunaan kaedah LSI dalam sistem

dapatan semula maklumat dapat meningkatkan lagi kepersisan berbanding

kaedah vektor. Dengan ini pendekatan baru dalam membangunkan sistem

dapatan semula maklumat bahasa Melayu harus memanfaatkannya.

Penggunaan kaedah LSI juga perlu menggabungkan penggunaan pengakar

bahasa kerana penggunaannya terbukti dapat meningkatkan purata kepersisan

yang ketara.

RUJUKAN

Ahmad, F. 1995. A Malay language document retrieval system: an

experimental approach and analysis. Tesis Ijazah Doktor Falsafah.

Universiti Kebangsaan Malaysia.

Baeza-Yates, R. and Ribeiro-Neto, B. 1999. Modern Information

Retrieval. New York: Addison-Wesley.

Berry, M.W.; Dumais, S.T.; and O'Brien, G.W. 1995. Using linear

algebra for intelligent information retrieval. S1AM Review 37(4):573-

595.

Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K. and

Harshman, R.A. 1990. Indexing by latent semantic analysis. Journal

of the American Society for Information Science 41(6):391-407.

Dumais, S. 1991. Using the retrieval of information from external sources.

Behavior Research Methods, Instruments, & Computers, 23(2):229-

236.

Grefenstette, G. 1998. The Problem of Cross-Language Information

Retrieval. Dalam Cross-Language Information Retrival, ed. G.

Grefenstette, ms 1-9. Boston: Kluwer Academic Publishers.

Porter, M.F. 1980. An Algorithm for Suffix Stripping. Program 14(3):130-

137. Salton, G. dan McGill, M.J. 1983. Introduction to Modem

Information Retrieval. McGraw-Hill.

MAKLUMAT PENGARANG

Muhammad Taufik Abdullah,

Fatimah Ahmad, Ramlan Mahmod

Fakulti Sains Komputer dan Teknologi Maklumat

Universiti Putra Malaysia

43400 UPM Serdang, Selangor

Emel: {taufik,fatimah.ramlan} @fsktm.upm.edu.rny

Tengku Mohammed Tengku Sembok Fakulti Teknologi dan Sains

Maklumat Universiti Kebangsaan Malaysia 43600 Bangi, Selangor Emel:

tmts@ftsm.ukm.my

10

.