Algoritma pohon batang untuk robot pemanen informasi daring

Algoritma pohon batang untuk robot pemanen informasi daring
L.T. Handoko (GFTK LIPI)

Sempat hampir terlupa, saya diingatkan oleh satu pesan internal di forum grup kecil saya (GFTK LIPI) di Intra LIPI. Pesan tersebut ditulis oleh Zaenal Akbar yang saat ini sedang melanjutkan riset di Kontanz University, Jerman, bahwa salah satu paper kami telah terbit [1]. Paper tersebut memuat riset kecil kami berdua terkait algoritma pemanenan data situs secara otomatis (web harvesting) pada periode 2009 [2].
Penelitian kecil tersebut merupakan awal saya belajar “agak serius” masalah akuisisi data dari halaman situs secara daring dan melakukan proses rekonstruksi database sesuai dengan kebutuhan. Kebutuhan yang memotivasi studi ini adalah pengumpulan data-data ilmiah di Indonesia. Usaha ini telah dilakukan dengan cukup sukses oleh grup kami dengan motor utama Hadiyanto sebagai bagian dari proyek Kementerian Riset dan Teknologi (KRT) pada tahun 2007. Proyek ini menghasilkan database nasional dengan tajuk Database Riset, Ilmu pengetahuan dan teknologi (DBRIpTek) [3].
DBRIpTek merealisasikan pengumpulan database dengan pendekatan desentralisasi pengelola di seluruh lembara terkait. Untuk itu diperlukan pelatihan, pembagian akses serta pemantauan proses pemasukan data secara berkesinambungan. Meski pendekatan ini masih lebih baik daripada sistem tersentralisasi dengan metode pengumpulan data secara manual, dengan mudah bisa ditebak bahwa DBRIpTek akhirnya berakhir stagnan dan terhenti setelah proyek usai. Meskipun akses dan koneksi terus dipertahankan sampai saat ini. Ini merupakan kebijakan umum dari pengelola jaringan LIPI sebagai penyedia infrastruktur jaringan.

Robot pemanen informasi situs

Bermula dari pengalaman riil selama proses pengembangan serta pemeliharaan DBRIpTek, muncul gagasan untuk memanfaatkan teknologi web crawling alias akuisisi halaman situs secara otomatis ala mesin pencari Google. Tetapi berbeda dengan mesin pencari yang bersifat general, teknologi yang dikembangkan harus memenuhi kebutuhan pembaruan sarana semacam DBRIpTek.
Beberapa prinsip dasar serta kebutuhan yang mutlak harus dipenuhi adalah :
  • Konten informasi yang diakuisisi bersifat homogen dan fokus. Misal : informasi terkait iptek seperti kasus DBRIpTek.
  • Target akuisisi spesifik dan tidak sebarang situs. Bahkan bila perlu, untuk meningkatkan akurasi, situs target harus ditetapkan secara manual dan melalui proses review. Target spesifik tidak hanya mencakup situs utama, tetapi sampai pada level jenis informasi apa yang akan diakuisisi dari situs tersebut. Sehingga tidak semua halaman di situs tersebut perlu dipanen.
  • Lebih dari sekedar mengambil informasi dari sebuah halaman situs, sistem harus mampu mengambil hanya bagian inti dari halaman situs. Misal untuk kasus halaman yang berisi informasi publikasi pada gambar : bagian inti berupa informasi yang berisi informasi judul, penulis, abstrak dan sejenisnya. Sebaliknya bagian aneka menu, iklan dan sejenisnya harus dibuang.
  • Selanjutnya sistem harus mampu memilah bagian inti tersebut menjadi sub-sub-bagian yang relevan. Misal untuk kasus diatas : bagian judul, penulis, abstrak dan sebagainya.

Dengan sistem diatas, robot akan mampu membuat data terstruktur dalam bentuk database baru sesuai dengan keinginan. Database ini yang kemudian bisa diakses serta dimanfaatkan publik secara daring seperti direalisasikan di Indonesian Scientific Index (ISI) [4]. Seluruh poin diatas mutlak diperlukan untuk menjaga akurasi konten, setidaknya mendekati 95 persen. Berbeda dengan mesin pencari generik seperti Google, tujuan pemanenan situs adalah untuk membuat database topik tertentu. Sehingga apabila database hanya sekedar mengumpulkan hasil pencarian dari seluruh halaman dan bagian-bagiannya, konten tersebut sama sekali tidak bermanfaat. Bayangkan : Anda mencari konten “peneliti fisika” di Google, maka akan ditampilkan banyak sekali halaman yang 90 persen diantaranya sama sekali tidak relevan.

Algoritma pohon batang

Dari seluruh kebutuhan di sistem diatas, proses pertama dan kedua dilakukan secara manual, meski cukup hanya satu kali pada saat awal saja. Dalam istilah teknologi informasi (TI) ini biasa disebut sebagai targeted web harvesting, yang merupakan lawan dari general web harvesting seperti Google.
Tantangan dari sistem ini ada di proses ketiga dan keempat. Meski sejauh ini telah banyak algoritma yang dikembangkan untuk melakukan tugas semacam ini, sebagian besar fokus pada proses otomasi “pengenalan konten”, dan hanya sebagian kecil yang fokus pada “pengenalan struktur konten”. Padahal, seperti dijelaskan diatas, kebutuhan utama untuk sistem semacam DBRIpTek maupun ISI adalah pengenalan struktur konten, karena konten (target pemanenan) telah dipilih sejak awal. Sebagian besar algoritma populer untuk pengenalan struktur konten berbasis Document Object Model (DOM) [5], khususnya DOM tree (pohon DOM), dengan memanfaatkan karakteristik tag pembuka dan penutup dari kode-kode HTML [6]. Sayangnya aneka algoritma ini tidak peka pada perubahan struktur yang terjadi setelah proses inisiasi awal. Sehingga bila suatu saat, misalnya ditambahkan iklan di tengah menu, sistem tidak mampu melakukan antisipasi dan perbaikan.
Untuk itu kami melakukan penyempurnaan atas algoritma pohon DOM. Penyempurnaan utamanya dilakukan pada :
  1. Penyusunan pohon DOM tidak hanya dari level teratas, tetapi juga dari level terbawah secara simultan. Ini memastikan pengenalan dini perubahan pohon dari sebuah halaman situs secara akurat.
  2. Karakterisasi pohon DOM tidak hanya secara vertikal, tetapi juga horisontal. Sehingga tidak hanya kedalaman tetapi juga lebar dari pohon DOM turut diperhitungkan. Kesemuanya direpresentasikan dengan algoritma matematis dan digambarkan dalam bentuk diagram batang seperti pada gambar.

Algoritma ini kemudian disebut sebagai algoritma bar tree (pohon batang). Penyempurnaan ini memungkinkan tidak hanya pengenalan perubahan pohon di semua level, tetapi juga tidak terpengaruh oleh penambahan iklan dsb selama terjadi di level kedalaman yang sama. Hasil

Dari hasil percobaan yang dilakukan oleh Z. Akbar untuk memanen data-data terkait iptek dari aneka situs di Indonesia, diperoleh hasil yang cukup mengesankan dengan tingkat akurasi mencapai rata-rata diatas 95 persen [4].
Algoritma dan sistem yang telah diaplikasikan di ISI secara prinsip dengan mudah bisa diimplementasikan untuk aneka kasus yang lain. Lebih jauh, sistem ini telah dirilis sebagai open source (sumber terbuka) di SourceForge.net [7]. Dilain pihak algoritma ini telah terdaftar hak ciptanya sejak 2010 [8] dan terpilih menjadi salah satu dari 101 Inovasi Indonesia Paling Prospektif tahun 2009 [9].
Lebih jauh lagi, saat ini algoritma kami juga telah diimplementasikan secara global, salah satunya adalah Slovak Environmental Index di NESIS Project Eropa.

Referensi

  1. Z. Akbar, L.T. Handoko, “Pattern discovery for semi-structured web pages using bar-tree representation”, International Journal of Computer Theory and Engineering 3 (2011) 261-269.
  2. Z. Akbar, L.T. Handoko, “Reverse method for labeling the information from semi-structured web pages”, Proceeding of the International Conference on Signal Processing Systems (2009) pp. 551-555 (DOI 10.1109/ICSPS.2009.86).
  3. Hadiyanto, L.T. Handoko, “Database Riset, Ilmu pengetahuan dan Teknologi – DBRIpTek”, http://dbriptek.lipi.go.id (2007).
  4. Z. Akbar, L.T. Handoko, “Indonesian Scientific Index – ISI”, http://www.isi.lipi.go.id (2009).
  5. W3 Consortium, “The Document Object Model”, http://www.w3.org/DOM/ (2005).
  6. Contoh : J. Wang, F.H. Lochovsky, “Data extraction and label assignment for web databases”, Proceedings of the 12th international conference on World Wide Web (2003) pp. 187-196.
  7. Z. Akbar, L.T. Handoko, “openISI” http://sourceforge.net/projects/openisi/ (2008).
  8. Z. Akbar, L.T. Handoko, “Integrasi Data dengan Algoritma Pemanenan Web Terfokus”, Hak Cipta no. 045143 (25 Januari 2010).
  9. Z. Akbar, I. Firmansyah, B. Hermanto, L.T. Handoko, “Aplikasi TI Publik Berbasis Komputasi dan Data Terdistribusi”, 101 Inovasi Indonesia Paling Prospektif (2009).