BAB II DASAR TEORI
Pada bab ini dibahas teori mengenai focused crawler dengan algoritma genetik, text mining, vector space model, dan generalized vector space model.
2.1.
Focused Crawler
2.1.1. Definisi Web crawler adalah suatu program penelusur web yang mampu bekerja secara otomatis menelusuri halaman halaman web di internet. Proses penelusuran ini biasa disebut proses crawling. Hasil penelusuran dari proses crawling biasanya berupa URL atau dapat juga berupa halaman web yang diunduh oleh crawler. Jika proses pengunduhan dimodifikasi maka dapat juga didapat sebagian isi dari web tanpa mengunduh halaman web secara keseluruhan. Proses pengambilan isi halaman web dilakukan dengan berpatokan pada URL yang didapat dari proses crawling. Focused crawler adalah modifikasi dari web crawler biasa yaitu web crawler yang memiliki proses seleksi dalam penelusuran halaman-halaman web. Focused crawler bisa membedakan hasil yang relevan dan tidak relevan. Focused crawler pada umumnya membutuhkan suatu masukan untuk dijadikan patokan pencarian. Masukan yang sangat mempengaruhi focused crawler adalah link yang menjadi acuan pencarian. Dengan berpatokan pada link tersebut maka crawler akan mencari halaman yang memiliki kemiripan tinggi dengan halaman pada link tersebut. Kemiripan bisa dilihat dari domain link yang ditelusuri atau juga dari isi halaman yang ditelusuri.
2.1.2. Focused Crawler dengan Algoritma Genetik [2] Focused crawler menggunakan algoritma genetik sebagai metode dalam proses seleksi halaman web [2]. Masukan yang menjadi patokan pencarian pada crawler adalah domain lexicon dan keyword. Proses pencarian pada focused crawler adalah bersifat antrian halaman web. Crawler akan menelusuri halaman web satu per satu secara bergantian. Crawler memiliki output dari web berupa halaman web yang diunduh oleh crawler beserta informasi dari halaman web tersebut (judul, dan URL). Crawler juga dapat melakukan 12
13
parsing HTML dari halaman web untuk mendapatkan isi dari web tersebut. Meskipun pada akhirnya hasil parsing tidak disimpan dalam database. Domain lexicon adalah sebuah URL dimana isi dan juga URL dari halaman dengan URL tersebut akan dijadikan kamus pencarian. Kamus pencarian digunakan dalam membandingkan isi web yang ditelusuri dengan kamus. Semakin mirip dengan kamus maka semakin besar tingkat relevansi dari halaman web yang sedang ditelusuri. Focused crawler ini menggunakan metode TF-IDF untuk melakukan pembobotan isi halaman web. Metode TF-IDF yang digunakan menghasilkan nilai total fungsi kemiripan Jaccard (Jscore). Jscore adalah penentu seberapa relevan suatu halaman terhadap kata kunci dan juga domain lexicon yang diberikan oleh user. Penerapan algoritma genetik pada focused crawler adalah pada pembentukan populasi baru dari populasi awal hasil pencarian. Populasi awal yang dimaksud adalah kumpulan halaman-halaman web hasil pencarian yang paling pertama. Setelah itu dilakukan dua proses yaitu mutasi dan rekombinasi (cross over) untuk mendapatkan populasi baru yang juga memiliki relevansi dengan masukan. Proses rekombinasi dari halaman halaman web menggunakan sebuah variabel cross over sebagai salah satu patokan. Masing masing URL akan memiliki cross-over rate sendiri. Variabel cross-over adalah total nilai Jscore dari semua web yang memuat URL yang sedang dihitung nilai cross-over rate-nya. URL dengan cross-over rate terbesar kembali masuk ke dalam antrian crawler. Proses mutasi adalah proses pencarian secara meta-search. Potongan potongan kata kunci dari halaman-halaman web pada populasi awal akan digunakan sebagai patokan. Potongan potongan tersebut kemudian dijadikan query dalam pencarian pada tiga mesin pencari yaitu Bing, Yahoo, dan Google. Sepuluh hasil terbaik dari setiap mesin pencari akan dimasukkan ke dalam antrian crawler. Proses mutasi menggunakan variabel mutation rate sebagai variabel kemungkinan terjadinya mutasi. Berdasarkan hasil penelitian dan pengujian, nilai mutation rate yang besar akan menambah halaman web hasil pencarian di mesin pencari menjadi lolos seleksi. Sementara nilai cross-over rate yang besar akan menambah kemungkinan halaman-halaman web baru yang saling berkaitan.[2]
14
Secara singkat urutan dari proses crawling adalah melalui tahapan-tahapan yang dijabarkan sebagai berikut :
Telusuri halaman web dan lakukan seleksi.
Halaman web yang sudah terseleksi akan diunduh dan juga disimpan dalam database crawler.
2.2.
Setelah semua halaman web diunduh maka dibuat laporan proses crawling.
Text Mining Text mining adalah suatu metode yang banyak digunakan dalam information
retrieval dan machine learning. Tujuan utama dari text mining bukanlah mengambil keseluruhan teks melainkan mengambil pola-pola kalimat atau bahasa pada suatu teks atau dokumen sehingga didapat suatu informasi. Dalam melakukan text mining dibutuhkan langkah langkah secara urut yaitu: tokenizing, filtering, stemming, analyzing. Tokenizing adalah tahap pemecahan kalimat menjadi kata-kata penyusun. Sementara filtering adalah proses seleksi kata-kata yang dianggap penting dan kemudian akan dilakukan stemming yaitu diambil kata dasar dari kata- kata hasil filtering. Analyzing adalah proses analisa keterhubungan kata-kata dengan dokumen atau paragraf. Proses analyzing inilah yang membutuhkan metode-metode natural language processing (NLP) untuk mendapatkan hasil yang tepat dan sesuai dengan tata bahasa yang berlaku [1, h.1]. Proses tokenizing dapat dilakukan secara berbeda-beda tergantung pada jenis text mining yang digunakan. Jika dilakukan terhadap suatu kalimat maka proses tokenizing adalah memecah kalimat tersebut menjadi kata. Akan tetapi jika dilakukan pada suatu paragraf maka proses tokenizing memecah paragraf menjadi beberapa kalimat terlebih dahulu baru kemudian kalimat dipecah menjadi kata. Proses filtering dan stemming hampir sama dalam eksekusinya terhadap kata-kata yang didapat dari proses tokenizing. Filtering secara keseluruhan menghilangkan kata-kata yang tidak bermakna yang penting seperti preposisi (di, ke ,
dan, dari). Sementara
stemming menghilangkan imbuhan-imbuhan yang ada pada setiap kata sehingga menjadikan kata tersebut kembali ke bentuk dasar.
15
Proses analyzing adalah proses yang menentukan sejauh mana proses text mining berhasil mendapatkan hasil yang relevan dari suatu teks. Umunya proses analyzing menentukan tingkat relevansi antar satu kata terhadap kata-kata lain dan juga terhadap keseluruhan dokumen. Tingkat relevansi dapat ditentukan banyak faktor seperti kemiripan, jumlah, dan keterkaitan kata. Proses analyzing yang baik bisa dilakukan dengan menganalisa kata-kata yang sudah melewati tiga tahap pertama text mining secara semantik dan juga matematis.
2.3.
Metode Vector Space Model (VSM)
2.3.1. Definisi Vector space model (VSM) adalah salah satu bentuk pemodelan aljabar yang biasa digunakan untuk menggambarkan teks dan dokumen ke dalam bentuk vektor. Metode ini biasa digunakan untuk menentukan nilai kemiripan dokumen terhadap suatu kata query. Nilai kemiripan suatu string atau kata akan semakin besar jika string tersebut semakin sering muncul dalam suatu dokumen. VSM biasa digunakan pada information filtering, indexing, dan relevancy ranking. Sesuai dengan namanya VSM menggunakan vektor sebagai perumpamaan dari dokumen dan query. Dokumen dimisalkan dengan vektor d (di1,di2,…dit) dan query dimisalkan dengan vektor q (wq1,wq2,…wqt). Setiap vektor berkaitan dengan suatu term yang dapat didefinisikan secara berbeda-beda tergantung pada penggunaan dari VSM. Definisi term pada umumnya adalah kata, frasa, atau kata kunci. Jika term didefinisikan sebagai kata maka dimensi dari ruang vektor adalah jumlah kata pada keseluruhan teks. Penghitungan nilai dari term dan kaitannya dengan masing-masing vektor disebut juga pembobotan term. Metode pembobotan term yang biasa digunakan adalah metode TF-IDF yang akan dibahas pada sub-bab 2.3.2. Kelebihan metode VSM adalah sebagai berikut :
Model yang sederhana dengan basis aljabar linear yang mudah dihitung
Bobot dari term tidak dalam bentuk biner
Dapat menentukan peringkat relevansi antara query dengan dokumen
16
Mampu melakukan perhitungan tingkat kemiripan secara terus menerus pada banyak dokumen
Kekurangan dari metode VSM antara lain adalah :
Semakin besar ukuran dokumen maka tingkat kemiripan akan diukur semakin kecil sehingga rawan terhadap kesalahan perhitungan
Kata kunci (query) tidak boleh sedikitpun berbeda
Tidak sensitif secara semantik
2.3.2. Metode Term Frequency-Inverse Document Frequency (TF-IDF) TF-IDF adalah suatu metode pembobotan relevansi sebuah term dengan dokumen. Dalam metode TF-IDF elemen yang diperhitungkan adalah frekuensi kemunculan term terhadap suatu dokumen (TF) dan juga inverse document frequency yang mengandung kata tersebut. Dalam hal perhitungan TF-IDF pada dokumen tunggal maka ada juga kalimat sebagai patokan perhitungan. IDF dari suatu kata menunjukkan tingkat kepentingan suatu kata terhadap keseluruhan dokumen. Semakin kecil nilai IDF maka kata tersebut semakin tidak dianggap penting bagi dokumen secara keseluruhan. Sementara TF dari suatu kata menandakan seberapa banyak kata tersebut diucapkan dalam satu kalimat. Dengan kata lain suatu kata akan semakin tinggi relevansinya terhadap suatu kalimat jika kata tersebut banyak muncul pada kalimat yang bersangkutan dan tidak ada atau sedikit kemunculannya pada kalimatkalimat lain di dokumen yang sama. Persamaan 2.1 berikut adalah persamaan untuk perhitungan TF-IDF. 𝑑
𝑡𝑓 − 𝑖𝑑𝑓𝑖𝑗 = 𝑡𝑓𝑖𝑗 × log 𝑑
𝑖
(2.1)
tf-idfij = bobot kata tj terhadap kalimat di tfij
= jumlah kemunculan kata tj dalam kalimat di
d
= jumlah semua kalimat yang ada dalam dokumen
di
= jumlah kalimat dari dalam dokumen yang mengandung kata tj (minimal ada satu kemunculan kata tj)
17
2.3.3. Similarity Coefficient Pada metode VSM hasil akhir yang merupakan nilai kemiripan atau relevansi suatu dokumen dinyatakan dalam suatu nilai yaitu similarity coefficient. Rumus dari penghitungan nilai kemiripan atau dikenal dengan istilah similarity coefficient (SC) adalah dengan menggunakan rumus seperti berikut: SC q,𝒅𝑖 =
t j=1 (𝒘𝑞𝑗 *𝒅𝑖𝑗 ) t (𝒘 )2 𝑞𝑗 j=1
(2.2)
t (𝒅 )2 j=1 𝑖𝑗
Dimana: SC
= similarity coefficient (koefisien kemiripan suatu kalimat tehadap query)
wqj
= nilai kata j terhadap query q = tfqj *idfj
dij
= nilai kata j pada kalimat i = tfij * idfj
tfij
= term frequency = kemunculan kata j pada kalimat di
idfj
= inverse document frequency = log
d
= jumlah total kalimat
dj
= jumlah kalimat yang mengandung kata j 𝑡 𝑗 =1
𝒘𝑞𝑗
2 t j=1 (𝒅𝑖𝑗 )
2
d dj
= Lwqj = panjang vektor query = Ldij = panjang vektor kalimat
i
= indeks kalimat
j
= indeks kata
q
= indeks query Persamaan 2.2 diatas adalah rumus yang digunakan untuk mencari SC pada banyak
dokumen. Semakin besar nilai SC maka semakin mirip kalimat tersebut dengan query. Pada penggunaanya untuk mencari kalimat atau ringkasan pada suatu dokumen saja maka dilakukan beberapa perubahan. Perubahan yang dimaksud adalah dengan menambah beberapa langkah dan mengubah beberapa istilah. Istilah yang diubah adalah dengan mengubah istilah dokumen menjadi kalimat sebagai perwujudan dari pecahan pecahan atau daerah daerah dari dokumen. Langkah yang perlu dilakukan adalah memecah dokumen menjadi paragraf-paragraf dan kemudian disimpan secara terpisah per paragraf, dan melakukan tokenizing kalimat per paragraf.
18
Tokenizing dilakukan dengan cara memisahkan kalimat berdasarkan tanda titik yang diasumsikan sebagai akhir kalimat. Permasalahan utama dari menjadikan tanda titik sebagai patokan adalah ada kalanya tanda titik tidak menandakan akhir kalimat. Sebagai contoh pada penggunaan tanda titik pada singkatan, gelar, ataupun akronim. Dengan metode VSM maka akan didapat ranking dari setiap kalimat terhadap query. Sehingga akan bisa dipilih kalimat mana yang bisa dihilangkan sehingga menghasilkan berita yang lebih ringkas. Query yang akan digunakan adalah judul dari berita yang diringkas.
2.4.
Metode Generalized Vector Space Model (GVSM) Generalized vector space model (GVSM) adalah metode pengembangan dari VSM.
Awal pengembangan dimulai karena dalam penelitian didapatkan bahwa metode VSM memiliki beberapa kelemahan besar yaitu sangat kakunya metode dalam segi perhitungan [4]. Metode perhitungan dikatakan kaku karena hanya mempertimbangkan frekuensi kemunculan dari suatu kata saja. Hubungan antara kata secara makna baik itu jauh, sama, atau dekat seharusnya menjadi pertimbangan juga. Oleh karena itu dalam penghitungan menggunakan rumus perhitungan SC ditambahkan vektor baru yaitu tj dan ts. Sehingga rumus perhitungan SC yang baru pada GVSM adalah sebagai berikut : SC q,𝒅𝑖 =
(( nj=1 ni=1 (𝒘𝑞𝑗 *𝒅𝑖𝑗 ))*(𝒕𝑠 𝒕𝑗 )) n (𝒘 )2 𝑞𝑗 j=1
n (𝒅 )2 j=1 𝑖𝑗
(2.3)
Dimana ts dan tj bisa ditentukan secara berbeda beda dalam setiap penggunaannya. Beberapa penelitian menggunakan korelasi antar istilah pada indeks istilah sebagai inputan. Sementara pada penelitian Tsatsaronis menggunakan pembobotan tambahan yaitu keterkaitan secara semantik menggunakan aplikasi Thesaurus yaitu wordnet [4, h.70]. Sehingga metode GVSM menjadi metode VSM yang memiliki nilai tambah dari segi keterkaitan secara bahasa dan tidak hanya menghitung similarity coefficient secara matematis berdasarkan pada jumlah kemunculan tapi juga berdasarkan kepada kaitannya dengan tata bahasa. Dalam penelitian ini vektor ts dan tj ditentukan sebagai vektor frekuensi kata pada kalimat (tj) pada suatu kalimat yang sedang dalam proses perhitungan nilai SC dan vektor jumlah sinonim (ts) dari masing-masing kata pada vektor tj, Kata yang dimasukkan hanya
19
jika kata tersebut juga berkaitan dengan query. Jika kata tidak berkaitan maka kata tidak dimasukkan ke dalam vektor. Nilai perkalian titik (skalar) kedua vektor tersebut akan dijadikan pengali pada pembilang dari perhitungan SC. Dimensi vektor sinonim disamakan dengan dimensi vektor kata. Dengan kata lain semakin banyak sinonim dari kata yang frekuensinya besar dan juga berkaitan dengan query pada suatu kalimat akan menyebabkan kalimat tersebut memiliki nilai SC yang lebih besar. Berikut rumus dari perhitungan ts.tj 𝒕𝑠 . 𝒕𝑗 =
𝑘 𝑎 (𝑒𝑎𝑠
× 𝑒𝑎𝑗 )
(2.4)
ts.tj
= nilai perkalian titik ti dan tj
e
= elemen pada tiap vektor
k
= besar dimensi vektor = jumlah kata pada kalimat yang berkaitan dengan query
ej
= elemen vektor kata
es
= elemen vektor sinonim
a
= indeks elemen vektor
2.5
Contoh Perhitungan Nilai SC Perhitungan VSM dapat menentukan besarnya SC antara query (keyword) dengan
kalimat dalam suatu paragraf atau dokumen. Sebagai contoh akan dilakukan penghitungan dengan masukan kalimat yang dikutip dari sebuah berita sebagai berikut.
Ribuan pengusaha seluruh pedagang Indonesia berkumpul dalam Musyawarah Nasional ke IX Asosiasi Pengusaha Indonesia di Jakarta, Senin (8/4/2013). Presiden Susilo Bambang Yuhoyono akan membuka munas pedagang yang bertema “Dunia Usaha Maju, Indonesia Kuat” ini. [12]
Kedua kalimat tersebut akan dicari kecocokannya dengan query berupa judul dari berita tersebut yaitu pengusaha, berkumpul, munas, dan Apindo. Perhitungan nilai SC dibagi ke beberapa tahap antara lain menghitung nilai IDF dan TF, menghitung panjang vektor, dan menghitung nilai SC.
20
2.5.1
Menghitung Nilai IDF dan TF Langkah langkah perhitungan adalah sebagai berikut : 1. Buat tabel kata-kata yang ada dalam dokumen dan tentukan inverse document frequency (idf) untuk masing-masing kata yaitu log
d dfj
dimana d adalah total
kalimat dan dfj adalah kalimat yang mengandung kata tersebut. 2. Hitung frekuensi kemunculan (tf) dari masing masing kata di tiap tiap kalimat. 3. Hitung tf*idf untuk setiap kalimat. 4. Hitung tf*idf dari query dimana tf adalah jumlah kata yang bersangkutan dengan query yang ada pada query dibagi frekuensi kemunculan kata yang bersangkutan dengan query pada keseluruhan dokumen. Pada langkah pertama hingga ketiga sebagai contoh diambil kata “ribuan” untuk dihitung nilai idf dan tf dari kata “ribuan”. Untuk menghitung nilai idf dari kata ribuan perlu dilihat nilai dfj dari kata “ribuan” yaitu bernilai 1. Nilai dfj bernilai 1 karena hanya ada satu kalimat yang mengandung kata “ribuan” dari total dua kalimat. Sesudah nilai d dan dfj didapat maka dapat dihitung nilai idf dari kata “ribuan” sesuai dengan yang tercantum pada persamaan 2.1 yaitu log
d dfj
.
Tabel 2.1 Perhitungan tf, idf kalimat dan query (bersambung)
Kata
idf
Kalimat 1 (d1) Kalimat 2 (d2) tf
tf*idf
tf
Query
tf*idf
Ribuan
0.301
1
0.301
0
0
Pengusaha
0.301
2
0.602
0
0 0.1505
Seluruh
0.301
1
0.301
0
0
pedagang
0.301
1
0.301
Indonesia
0
2
0
0
0
Berkumpul
0.301
1
0.301
0
0
Musyawarah
0.301
1
0.301
0
0
Nasional
0.301
1
0.301
0
0
Asosiasi
0.301
1
0.301
0
0
Jakarta
0.301
1
0.301
0
0
0.301
21
Tabel 2.1 Perhitungan tf, idf kalimat dan query (lanjutan)
Kata
idf
Kalimat 1 (d1) Kalimat 2 (d2) tf
tf*idf
tf
Query
tf*idf
Senin
0.301
1
0.301
0
0
Presiden
0.301
0
0
1
0.301
Susilo
0.301
0
0
1
0.301
Bambang
0.301
0
0
1
0.301
Yudhoyono
0.301
0
0
1
0.301
Membuka
0.301
0
0
1
0.301
munas
0.301
0
0
1
0.301
bertema
0.301
0
0
1
0.301
dunia
0.301
0
0
1
0.301
usaha
0.301
0
0
1
0.301
maju
0.301
0
0
1
0.301
kuat
0. 301
0
0
1
0.301
0.301
Pada Tabel 2.1 dapat dilihat bahwa query Apindo sama sekali tidak muncul dalam tabel. Hal ini disebabkan tidak dimuatnya kata Apindo pada kedua kalimat yang ada. Penjelasan dari langkah 4 adalah pada kata pengusaha yang ada pada query dan juga pada kalimat. Kata pengusaha memiliki tf total pada kedua kalimat sejumlah 2 sementara di dalam query kata pengusaha muncul sebanyak satu kali sehingga tf untuk kata pengusaha dari query adalah ½.
2.5.2. Menghitung Panjang Vektor Kalimat dan Query Penghitungan yang harus dilakukan berikutnya adalah penghitungan dari panjang vektor dari dokumen atau dalam konteks di perhitungan ini adalah kalimat yaitu panjang dokumen d1 dan d2 masing-masing mewakili kalimat 1 dan kalimat 2. Selain panjang vektor dokumen juga dihitung panjang vektor dari query. 2 t j=1 (𝒅1j ) =
=
2 t j=1 (tf*idf)
0.3012 +0.6022+0.3012 +02+0.3012 +0.3012 +0.3012+0.3012 +0.3012+0.3012 +0.3012
22
= 1.085 2 t j=1 (𝒅2𝑗 ) =
2 t j=1 (tf*idf)
= 0.3012 +0.3012+0.3012 +0.3012 +0.3012+0.3012 +0.3012+0.3012 +0.3012+0.3012 +0.3012 +0.3012 =1.042 2 t j=1 (𝒘𝑞𝑗 )
=
0.3012 +0.15052+0.3012
= 0.451
2.5.3. Menghitung Nilai SC Setelah didapat panjang dari semua vektor maka langkah terakhir adalah menghitung SC kalimat terhadap query. Yaitu dengan menggunakan rumus pada persamaan 1. Dilakukan perhitungan SC masing masing kalimat sesuai dengan persamaan 1. SC dari kalimat 1 terhadap query. SC q,𝒅𝟏 =
0.602*0.1505+0.301*0.301 =0.385 1.085*0.451
SC dari kalimat 2 terhadap query. SC q,𝒅𝟐 =
0.301*0.301 =0.201 0.998*0.451
Dari kedua hasil SC didapat nilai yang lebih besar yaitu kalimat 1. Karena kalimat 1 mempunyai SC yang lebih besar dari kalimat 2 maka dapat dikatakan bahwa kalimat 1 adalah kalimat utama dari paragraf tersebut. Pada skripsi ini akan dilakukan pembobotan total keseluruhan kalimat tanpa melihat bagian per paragrafnya. Hal ini disebabkan banyaknya berita yang hanya memuat satu kalimat per paragraf.
2.5.4. Mengembangkan Nilai SC dengan GVSM Pada metode GVSM langkah-langkah awal yang dilakukan sama dengan metode VSM. Hanya saja pada perhitungan SC ada sebuah variabel pengali tambahan yaitu variabel t yang berisi nilai tambahan jika ditemukan kata-kata dari query yang berbeda tapi
23
memiliki makna sama juga. Akan tetapi dalam percobaan ini tidak ditemukan makna sama maka variabel t akan bernilai 1 yaitu tidak akan mempengaruhi perkalian antara nilai tf*idf query dengan kata.
