IMPLEMENTASI PEREKOMENDASIAN KATA KUNCI DOKUMEN MENGGUNAKAN ALGORITMA GOOGLE LATENT SEMANTIC DISTANCE Novario Jaya Perdana1, Diana Purwitasari2 Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Surabaya email:
[email protected] rekomendasi kata kunci tersebut tidak selalu sesuai dengan keinginan pengguna itu sendiri. Beberapa peneliti telah mengembangkan teknikteknik dalam pemberian rekomendasi kata kunci, antara lain ekpansi kata kunci dan re-ranking. Kedua teknik ini menggunakan perangkat-perangkat seperti semantic nets, ontology, dan Markov chains untuk memodelkan ciri dan perilaku pengguna (Borges & Lavene, 2007). Beberapa informasi berkaitan dengan profil pengguna akan dikumpulkan untuk mengetahui kecenderungan perilaku pengguna. Padahal pengguna sering kali mencari berbagai macam informasi dari berbagai bidang sehingga mempersulit penggambaran ciri perilaku pengguna. Peneliti lainnya menggunakan Google Similarity Distance (NGD) untuk memprediksikan kata kunci yang akan dimasukan oleh pengguna (Chen & Lin, 2010). Cara kerja algoritma ini adalah dengan menghitung hubungan antar kata kunci, lalu menggunakan hasil perhitungan tersebut untuk menyajikan peringkat k teratas rangkaian kata kunci terpenting kepada pengguna. Sayangnya, algoritma ini hanya dapat menyediakan informasi dengan satu kata kunci. Padahal agar dapat menemukan informasi yang lebih relevan, rangkaian kata kunci harus diperpanjang (Chen, Lin, & Chu, 2011). Keakuratan hasil pencarian menggunakan rangkaian kata kunci yang terdiri dari tiga kata lebih besar dibandingkan dengan penggunaan rangkaian kata kunci yang hanya terdiri dari satu kata (Chen, Lin, & Chu, 2011). Selain itu, kelas kata yang paling baik digunakan untuk membentuk rangkaian kata kunci adalah kata benda atau kata sifat (Chen & Lin, 2010). Rangkaian kata kunci yang baik adalah gabungan dari kedua kelas kata tersebut. Perpanjangan rangkaian kata kunci dapat dilakukan dengan mengambil intisari dari informasi yang terdapat pada suatu dokumen. Pengambilan intisari tersebut dapat menggunakan algoritma Google Latent Semantic Distance (GLSD). Dengan menggunakan intisari yang diambil dari suatu artikel, pencarian informasi dapat dilakukan dengan lebih akurat dan cepat. Implementasi dari algoritma GLSD inilah yang menjadi perhatian utama dalam tugas akhir ini.
ABSTRAKSI Keakuratan hasil pencarian pada mesin pencari bergantung pada kata kunci yang digunakan. Kurangnya informasi yang diberikan pada kata kunci dapat menyebabkan berkurangnya akurasi hasil pencarian. Hal ini berakibat pencarian informasi dalam internet menjadi pekerjaan yang berat. Dalam tugas akhir ini, penulis membangun sebuah perangkat lunak untuk membuat rangkaian kata kunci dokumen. Perangkat lunak tersebut menggunakan algoritma Google Latent Semantic Distance. Algoritma ini dapat mengekstrak informasi dari dokumen. Informasi tersebut diekspresikan dalam bentuk rangkaian kata-kata khusus yang digunakan dalam dokumen. Rangkaian tersebut dapat digunakan sebagai rekomendasi kata kunci untuk pencarian dokumen menggunakan mesin pencari. Hasil dari implementasi perekomendasian kata kunci dokumen menggunakan Google Latent Semantic Distance ini memperlihatkan akurasi yang tinggi dan dapat menemukan informasi yang relevan pada hasil pencarian teratas. Pada akhirnya, diharapkan sistem ini dapat membantu pengguna dalam membaca dan menulis artikel dengan lebih efektif.
Kata Kunci: Ekstraksi Informasi, Rangkaian Kata Kunci, Google Latent Semantic Distance
1. PENDAHULUAN Keakuratan hasil pencarian menggunakan mesin pencari bergantung pada kata kunci yang dimasukkan oleh pengguna. Kurangnya informasi yang dimasukkan sebagai kata kunci dapat mempengaruhi hasil pencarian. Contohnya saat ingin menemukan informasi mengenai “Matahari Department Store”, tetapi yang dimasukan sebagai kata kunci adalah kata “Matahari”, sehingga hasil yang dikeluarkan adalah informasi yang berkaitan dengan matahari sebagai pusat tata surya. Oleh Google, permasalahan ini dipecahkan dengan memberikan beberapa rekomendasi rangkaian kata kunci yang terkait. Sayangnya, kombinasi kata kunci yang diberikan sangat banyak dan merupakan rangkaian kata kunci yang sering dimasukkan oleh para pengguna lainnya (Chen, Lin, & Chu, 2011). Hal ini mengakibatkan
2. METODE Pada tugas akhir ini digunakan algoritma Google Latent Semantic Distance (GLSD). Algoritma ini dapat
1
digunakan untuk merangkai kata kunci dari teks suatu dokumen. Terdapat beberapa tahap dalam algoritma ini. Gambaran mengenai tahapan tersebut dapat dilihat pada Gambar 1. Pembahasan mengenai tahapan tersebut terdapat pada bagian selanjutnya.
2.1. Ekstraksi Dokumen Elemen yang dibutuhkan seluruh proses dalam perangkat lunak ini adalah teks dari suatu dokumen. Oleh karena itu, teks dalam dokumen harus diambil terlebih dahulu agar dapat diolah lebih lanjut. Proses tersebut adalah proses ekstraksi dokumen. Kegiatan utama yang terjadi dalam proses ini adalah pengambilan isi dokumen PDF sebagai data masukan. Bagian yang diambil dari dokumen tersebut sesuai dengan masukan dari pengguna. Perangkat lunak sudah menyediakan pilihan bagian yang ingin dijadikan sebagai sumber ekstraksi. Pilihan tersebut adalah bagian abstrak dan semua bagian pada dokumen kecuali abstrak. Selain isi dokumen, yang juga diambil dari dokumen adalah metadata dokumen tersebut. Metadata tersebut antara lain judul makalah ilmiah, dan penulis makalah tersebut. Proses pengambilan isi dokumen PDF ini memanfaatkan bantuan pustaka pdf parser. Pustaka tersebut adalah PDFBox. Proses ini dimulai dari membaca metadata dokumen untuk mendapatkan judul dan penulis makalah ilmiah. Setelah itu, memeriksa data masukan pengguna berupa bagian dokumen yang akan dijadikan sebagai sumber ekstraksi. Jika pengguna memilih abstrak sebagai bagian yang dijadikan sumber ekstraksi, maka perangkat lunak akan membaca isi dokumen yang termasuk dalam bagian
abstrak. Perangkat lunak akan mengenali bagian abstrak sebagai isi dokumen antara kata “abstrak” dan “elsevier”. Jika pengguna memilih pilihan lainnya, yaitu seluruh bagian kecuali abstrak, maka perangkat lunak akan meringkas dahulu seluruh isi dokumen tersebut. Setelah selesai meringkas, perangkat lunak akan membaca hasil peringkasan sebagai isi dokumen. Hasil akhir dari proses ini adalah kumpulan kalimat yang merupakan teks isi dokumen.
2.2. Pemecahan Teks Dokumen Menjadi Kata-Kata Proses selanjutnya adalah pemecahan teks menjadi kata-kata. Dalam proses ini, teks dipecah per kata. Selain itu, di dalam proses ini juga terdapat proses penyaringan karakter. Proses tersebut bertujuan untuk menghilangkan karakter-karakter selain huruf, seperti angka, simbol dan tanda baca. Hal ini dimaksudkan agar kata-kata tersebut siap diolah pada proses selanjutnya. Proses ini dimulai dari pemecahan teks menjadi satuan-satuan kata. Satuan-satuan kata tersebut kemudian diubah ke dalam bentuk huruf kecil semua (lower case). Setelah itu adalah proses tokenisasi, yaitu proses penghilangan karakter-karakter selain huruf dan tanda sambung seperti angka, simbol dan tanda baca lainnya. Hasil akhir dari proses ini adalah kumpulan kata-kata terpisah yang bersih dari karakter aneh selain huruf kecil dan tanda sambung. Kumpulan kata ini akan menjadi data masukan bagi proses selanjutnya, yaitu proses penyaringan.
Gambar 1. Tahapan pada Google Latent Semantic Distance.
2
2.3. Identifikasi Jenis Kata Sesuai Kelas Kata Menggunakan POS Tagger Proses berikutnya adalah identifikasi jenis kata berdasarkan kelas kata. Hal ini dimaksudkan agar didapatkan kata-kata yang dapat menggambarkan hal yang dibicarakan dalam dokumen. Kata-kata yang dipilih untuk dimasukkan dalam daftar kata adalah kata-kata yang termasuk dalam kelas kata benda dan kata sifat. Proses identifikasi jenis kata ini menggunakan bantuan pustaka penanda part-of-speech (POS tagger). Pustaka tersebut adalah Stanford Log-Linear Part-OfSpeech Tagger, yaitu sebuah pustaka untuk mengenali kelas kata dari suatu kata dalam kalimat. Proses identifikasi jenis kata sesuai dengan kelas kata ini dimulai dengan menandakan kata-kata dalam kumpulan kata dengan kelas kata masing-masing. Setelah itu, setiap kata diperiksa kelas katanya. Jika kata tersebut termasuk ke dalam kata benda dan kata sifat serta jumlah karakter dalam kata tersebut lebih dari tiga, maka kata tersebut ditambahkan ke dalam daftar kata. Hasil akhir dari proses ini adalah daftar kata-kata yang termasuk ke dalam kata benda dan kata sifat. Daftar kata ini akan menjadi data masukan bagi proses pembentukan frasa.
2.4. Pembentukan Frasa Agar rangkaian kata kunci yang dibangun lebih bermakna, elemen dari rangkaian kata kunci tersebut harus dapat mewakilkan isi dokumen lebih baik lagi. Salah satu caranya adalah dengan membentuk frasa dari kata-kata yang telah diekstrak. Frasa dibentuk dari kombinasi antara kata benda dengan kata benda atau kata sifat dengan kata benda. Proses ini memerlukan data masukan berupa daftar kata yang telah dikenali kelas katanya. Daftar kata tersebut didapatkan dari proses identifikasi jenis kata berdasarkan kelas kata. Terdapat beberapa kondisi yang harus dipenuhi oleh suatu kata jika kata tersebut ingin ditambahkan ke dalam daftar kata kunci. Kondisi pertama adalah kata tersebut termasuk ke dalam kelas kata benda, kata sifat atau determiner. Jika kata tersebut tidak memenuhi kondisi tersebut, maka kata tersebut tidak dapat ditambahkan ke dalam daftar kata kunci. Jika kata tersebut memenuhi kondisi tersebut, maka kondisi kedua harus diperiksa. Kondisi kedua adalah kata yang muncul setelah kata tersebut harus termasuk ke dalam kelas kata benda saja. Jika kondisi ini dapat dipenuhi, maka frasa dapat dibentuk dari kombinasi antara kata pertama dan kata kedua. Namun jika kondisi ini tidak dapat dipenuhi, maka frasa tidak dapat dibentuk tetapi kata pertama dimasukan ke dalam daftar kata kunci. Hasil akhir dari proses pembentukan frasa ini adalah daftar kata dan frasa yang berpotensial menjadi salah satu
anggota dalam rangkaian kata kunci. Daftar kata dan frasa ini menjadi data masukan bagi proses identifikasi kata khusus menggunakan jumlah hasil pencarian pada mesin pencari.
2.5. Identifikasi Kata Khusus Menggunakan Jumlah Hasil Pencarian Pada Mesin Pencari Daftar kata dan frasa dari hasil proses pembentukan frasa masih mengandung kata-kata dan frasa-frasa yang bersifat umum dan belum menggambarkan isi dokumen secara lebih baik. Oleh karena itu, diperlukan adanya proses penyaringan tambahan untuk mendapatkan katakata yang lebih khusus. Proses penyaringan tersebut adalah identifikasi kata khusus dengan memanfaatkan jumlah hasil pencarian pada mesin pencari. Kata/frasa yang secara khusus dipergunakan dalam suatu bidang tertentu biasanya hanya terkandung dalam sedikit dokumen. Hal ini dapat dilihat dari jumlah pencarian menggunakan kata tersebut pada mesin pencari. Proses identifikasi ini menggunakan bantuan API (Application Programming Interface) dari mesin pencari Yahoo! Search. Proses identifikasi kata khusus dengan menggunakan jumlah hasil pencarian dimulai dari penentuan batas ambang. Batas ambang ini digunakan sebagai batas maksimal jumlah hasil pencarian. Setiap kata kunci yang berada dalam daftar kata kunci dicari jumlah hasil pencariannya. Jika jumlah hasil pencarian lebih besar dari batas ambang, maka kata kunci tersebut tidak dapat ditambahkan ke dalam daftar kata khusus. Hasil akhir dari proses ini adalah daftar kata/frasa khusus yang dapat digunakan sebagai salah satu anggota dalam rangkaian kata kunci. Daftar kata khusus ini akan menjadi data masukan bagi proses perhitungan bobot rangkaian kata kunci.
2.6. Pembentukan Kata Kunci Menggunakan Google Latent Semantic Distance Tahapan terakhir adalah pembentukan kata kunci. Pembentukan kata kunci menggunakan algoritma GLSD. Proses yang terdapat dalam tahap perangkaian ini adalah perangkaian kata kunci yang kemudian dilanjutkan dengan perhitungan bobot rangkaian untuk mendapatkan rangkaian yang paling baik. Rangkaian kata kunci dibentuk dari kombinasi katakata dan frasa yang terdapat dalam daftar kata khusus hasil proses penyaringan sebelumnya. Rangkaian tersebut terdiri dari tiga buah kata/frasa khusus. Proses perangkaiannya adalah dengan memasangkan satu kata/frasa dengan 2 kata/frasa lainnya. Perangkaian kata kunci boleh membentuk rangkaian yang telah ada sebelumnya. Hal ini tergantung pada letak kata kunci pada rangkaian yang akan dibentuk. Setelah
3
rangkaian kata kunci telah dibuat, rangkaian tersebut perlu dihitung bobotnya. Bobot tersebut menunjukan hubungan antar anggota dalam rangkaian tersebut. Setelah semua rangkaian kata kunci telah dibuat dan dihitung bobotnya, rangkaian-rangkaian tersebut perlu diurutkan secara menurun sesuai hasil perhitungan GLSD. Hal ini dikarenakan rangkaian kata kunci yang diperlukan adalah rangkaian dengan nilai GLSD tertinggi.
3. Modifikasi Distance
Google
Latent
Semantic
Konsep utama GLSD berasal dari Sequential Google Similarity Distance (NGD). Algoritma tersebut dapat merangkai dua buah kata menjadi kata kunci (Cilibrasi & Vitanyi, 2007). Algoritma ini kemudian dimodifikasi sedemikian rupa untuk mendapatkan rangkaian kata kunci yang dapat menemukan kembali dokumen secara lebih baik.
3.1. Sequential Google Similarity Distance NGD pertama kali dikenalkan oleh Cilibrasi & Vitányi pada tahun 2007. Tujuan dari algoritma ini adalah untuk mencari jarak makna antar objek (kata atau frasa) dengan memanfaatkan jumlah dokumen yang mengandung kata tersebut. Pada penelitiannya, Cilibrasi & Vitányi menggunakan world-wide-web sebagai database dan Google sebagai mesin pencari. Algoritma ini memanfaatkan hasil pencarian kata kunci menggunakan mesin pencari seperti Google dan Yahoo! Search untuk mendapatkan hubungan makna antar kata. Seperti yang telah diketahui, hasil pencarian suatu kata kunci dalam mesin pencari akan menghasilkan banyak sekali halaman-halaman web yang mengandung kata tersebut. Cilibrasi & Vitányi menanggap halaman-halaman web yang mengandung kata kunci tersebut memiliki hubungan semantik yang mereka sebut sebagai Google semantics. Oleh karena itu, hubungan antar kata dapat dicari dengan menggunakan persamaan (1).
suatu dokumen dengan menggunakan konsep Google semantics. Persamaan tersebut dapat dilihat pada (2).
(2) Pada persamaan (2), adalah jumlah halaman yang mengandung pada hasil pencarian, dan adalah jumlah halaman yang mengandung dan pada hasil pencarian. adalah jumlah total dokumen yang tersimpan dalam database, dalam hal ini adalah total halaman web yang telah diindeksasi oleh mesin pencari. Algoritma ini tidak hanya dapat bekerja menggunakan Google, tetapi juga dapat menggunakan mesin pencari lainnya. Hasil perhitungan menggunakan algoritma NGD berkisar antara 0 hingga ∞. Jika nilai NGD sama dengan satu, maka hal tersebut menandakan bahwa kedua kata yang dihitung memiliki hubungan yang sangat kuat. Hal ini artinya kata dan akan selalu muncul bersama di hampir semua dokumen (Chen & Lin, 2010).
3.2. 2-Gram Google Similarity Distance Rumus dasar NGD hanya dapat mengetahui hubungan antar 2 kata. Agar dapat membuat suatu rangkaian kata kunci yang terdiri dari 3 kata, diperlukan adanya modifikasi pada rumus dasar tersebut. Dalam modifikasi NGD ini, Chen et al (2011) menggunakan probabilitas untuk mengetahui hubungan antara 2 kata kunci dan jika keduanya berada dalam suatu artikel. Terdapat sebuah peraturan yang dibuat oleh Chen et al (2011) yaitu jika terdapat dalam suatu artikel, maka juga akan terdapat dalam artikel tersebut. Hubungan keduanya dinyatakan dalam notasi . Karena menggunakan probabilitas, maka jumlah hasil pencarian kata kunci - yang digunakan dalam rumus NGD sebelumnya harus diubah ke dalam bentuk probabilitas. Hal ini dapat dicapai dengan cara membagi dengan banyaknya dokumen yang berada dalam database ( ). Notasi persamaan ini dapat dilihat pada (3).
(1) (3) Sesuai dengan persamaan (3), kata kunci dan akan digunakan sendiri-sendiri dan berpasangan. Dengan demikian, halaman web akan dihitung sebanyak tiga kali. Kali pertama adalah saat , kali kedua adalah saat dan terakhir adalah saat . Cilibrasi & Vitányi membuat sebuah persamaan yang dapat digunakan mencari hubungan antar kata di dalam
adalah probabilitas banyaknya dokumen yang mengandung kedua kata kunci dan di dalamnya. Cara yang sama juga dapat diaplikasikan untuk mencari probabilitas dokumen yang mengandung suatu kata. Probabilitas banyaknya dokumen yang hanya dan probabilitas mengandung disimbolkan dengan
4
banyaknya dokumen yang hanya mengandung disimbolkan dengan . Sehingga perhitungan mencari hubungan antara 2 kata kunci dengan menggunakan rumus NGD yang telah dimodifikasi (2NGD) menjadi seperti pada persamaan (4).
(4) Jika nilai yang dipilih pada algoritma NGD adalah yang mendekati 0, maka tidak halnya dengan algoritma 2NGD. Pasangan kata kunci yang dipilih adalah pasangan dengan nilai 2NGD tertinggi (Chen, Lin, & Chu, 2011).
yang harus diperiksa saat akan menggunakan GLSD. Kondisi-kondisi ini terkait jumlah dokumen yang berhasil ditemukan untuk setiap kata kunci. Kondisi-kondisi tersebut antara lain: 1. Kondisi pertama adalah saat jumlah hasil pencarian dokumen yang mengandung lebih besar dibandingkan yang mengandung dan keduanya lebih besar dibandingkan dengan hasil pencarian menggunakan kata . Hubungan antara ketiga kata tersebut dalam rangkaian dapat menggunakan (5).
(5)
3.3. Google Latent Semantic Distance Perumusan NGD yang asli hanya mencakupi 2 kata kunci, padahal 2 kata kunci tidak cukup bagus untuk mendapatkan dokumen yang diinginkan (Chen, Lin, & Chu, 2011). Oleh karena itu, dibutuhkan modifikasi dari rumus NGD yang asli. Modifikasi kali ini dibuat agar didapatkan rangkaian kata kunci yang terdiri dari 3 kata. Modifikasi NGD menjadi GLSD menggunakan bantuan pendekatan PLSA. Pada dasarnya, PLSA digunakan untuk menemukan hubungan antara kata, topik (latent variabel), dan dokumen. GLSD menggunakan konsep tersebut untuk menemukan hubungan antara kata, kata dan kata (Chen, Lin, & Chu, 2011).
2. Kondisi kedua adalah saat jumlah hasil pencarian dokumen yang mengandung lebih besar dibandingkan yang mengandung , namun hasil pencarian menggunakan kata lebih besar dibandingkan dengan hasil pencarian yang menggunakan kata . Hubungan antara ketiga kata tersebut dalam rangkaian dapat menggunakan (6).
(6) 3.
Bill Gates
Microsoft
Kondisi ketiga adalah saat jumlah hasil pencarian dokumen yang mengandung lebih besar dibandingkan yang mengandung , dan hasil pencarian menggunakan kata lebih besar dibandingkan dengan hasil pencarian yang menggunakan kata . Hubungan antara ketiga kata tersebut dalam rangkaian dapat menggunakan (7).
Computer
Gambar 2. Hubungan Antar Kata Kunci dalam Satu Rangkaian.
Gambarannya seperti terlihat pada Gambar 2. Gambar tersebut melukiskan hubungan yang terjadi antara 3 buah kata. Contohnya, hubungan antara kata Microsoft, Computer, dan Bill Gates. Kata Bill Gates dan Computer sangat erat hubungannya karena sudah banyak yang mengenali bahwa Bill Gates merupakan nama seseorang yang berperan aktif dalam bidang komputer. Jika diantara kedua kata tersebut ditambahkan kata Microsoft, maka hubungan antara kedua kata tersebut akan semakin erat. Hal ini disebabkan makna kata Microsoft yang sudah dikenal umum bahwa Microsoft merupakan perusahaan tempat Bill Gates berkerja dan merupakan perusahaan pembuat sistem operasi komputer. Hal ini akan meningkatkan akurasi karena terdapat hubungan tersembunyi antar kata kuncinya. Modifikasi NGD dimaksudkan untuk mengakomodasi tujuan tersebut. Terdapat enam kondisi
(7) 4. Kondisi keempat adalah saat jumlah hasil pencarian dokumen yang mengandung lebih besar dibandingkan yang mengandung , dan hasil pencarian menggunakan kata lebih besar dibandingkan dengan hasil pencarian yang menggunakan kata . Hubungan antara ketiga kata tersebut dalam rangkaian dapat menggunakan (8).
(8)
5
