BAB 3 ANALISA DAN PERANCANGAN
3.1
Gambaran Umum Pada masa sekarang ini, proses pencarian dokumen dalam web seperti Google,
Yahoo, dan sebagainya dilakukan dengan menginput query yang diinginkan pada kotak pencarian. Search engine akan melakukan pencarian dalam basis data yang dimiliki dengan cara mencocokkan query yang diinput dengan setiap dokumen yang terdaftar. Jika ditemukan minimal satu buah kata pada suatu dokumen yang sama dengan query yang diinput, maka dokumen ditampilkan pada hasil pencarian berupa sederetan link. Pada umumnya, hasil pencarian ditampilkan dalam bentuk link yang terdiri atas ratusan dokumen bahkan lebih. Urutan link dalam tampilan hasil pencarian didasarkan pada seberapa sering halaman web dikunjungi. Yang menjadi masalah bagi user adalah jumlah dari hasil pencarian yang cukup banyak tanpa adanya urutan relevansi yang jelas sehingga user cenderung untuk membuka satu per satu hasil pencarian untuk mendapatkan dokumen yang relevan dengan keinginan user, seperti yang dialami penulis saat melakukan pencarian dokumen yang berkaitan dengan topik penulisan skripsi ini. Perhitungan tingkat kekerabatan query dengan dokumen hasil pencarian belum dapat dilakukan oleh search engine yang umum ada saat ini. Hal ini memotivasi penulis untuk menggali suatu teknologi baru yang akan memberikan manfaat besar bagi user yang ingin melakukan pencarian dokumen dengan search engine dimasa mendatang.
31
3.2
Alternatif Pemecahan Masalah Klasifikasi dan visualisasi teks dengan algoritma Lingo memberikan hasil
pencarian dokumen dalam search engine berupa pengelompokan sejumlah dokumen yang memiliki kekerabatan erat dan pengurutan dokumen dalam kelompok yang sama sesuai skor kekerabatan dengan kelompoknya. Kata “klasifikasi” direalisasikan dengan pengelompokan dokumen, dan kata “visualisasi” direalisasikan dengan melakukan visualisasi dalam urutan yang tepat sesuai dengan tingkat kekerabatan antara dokumen dan frase. Menurut pengamatan Penulis, masih sangat sedikit sekali search engine yang menerapkan teknologi pencarian dokumen dengan algoritma Lingo. Karena manfaat yang dirasakan sangat besar, maka penulis tertarik untuk menggali algoritma Lingo dalam melakukan pengembangan pencarian dokumen dengan search engine yang sedang marak digemari dalam dunia internet di seluruh dunia saat ini. Proses pencarian dokumen dalam web dengan algoritma Lingo tidak hanya menggunakan disiplin ilmu komputer seperti yang selama ini dipakai dalam search engine yang ada. Algoritma Lingo menggabungkan teknik komputer dan matematika dalam setiap tahapannya, di mana dalam bidang matematika digunakan ilmu tentang matriks yang berkaitan dengan disiplin ilmu dalam Aljabar Linear. Algoritma Lingo yang menggunakan disiplin ilmu matematika memberikan kelebihan tersendiri dalam proses pencarian dokumen dalam web. Seluruh dokumen yang ada direpresentasikan dalam bentuk satu buah matriks yang disebut dengan term document matrix yang menggambarkan kekerabatan antara seluruh dokumen yang dimiliki oleh mesin pencari.
32
Query sebagai sejumlah kata yang diinput oleh user direpresentasikan oleh algoritma Lingo dalam bentuk matriks yang disebut dengan phrase matrix, di mana baris merepresentasikan sejumlah kata dan kolom merepresentasikan sejumlah frase. Phrase matrix sebagai matriks yang mewakili seluruh frase yang ada, term document matrix mewakili seluruh dokumen yang dimiliki mesin pencari. Secara garis besar, perkalian term document matrix dengan phrase matrix menghasilkan sebuah matriks yang akan menggambarkan kekerabatan antara query yang diinput dengan seluruh dokumen yang ada. Skor diberikan untuk setiap kelompok untuk menggambarkan seberapa dekat hubungan antara kelompok dengan frase yang dicari, skor juga diberikan pada setiap dokumen untuk menggambarkan seberapa dekat hubungan suatu dokumen dengan kelompoknya. Skor didapat dari perhitungan lewat pengolahan term document matrix dan phrase matrix. Skor yang diperoleh, baik skor masing–masing kelompok, maupun skor masing– masing dokumen terhadap kelompoknya digunakan untuk mendapatkan tampilan hasil pencarian yang terurut mulai dari skor pencarian yang paling tinggi hingga paling rendah. Tampilan dari hasil pencarian yang berurut sesuai skor yang didapat, mempermudah user dalam melihat hasil pencarian, karena tingkat kekerabatan dokumen dengan frase terepresentasi dalam bentuk nyata yaitu skor yang diperoleh.
33
3.3 3.3.1
Perancangan Program Aplikasi Perumusan Objek Penelitian Dalam tahapan awal perancangan, penulis menemui Kepala Unit Pelayanan
Teknis perpustakaan Universitas Bina Nusantara untuk mengajukan usulan teknologi baru pencarian dokumen dalam web untuk dapat diaplikasikan lebih lanjut oleh ATL Bina Nusantara, juga untuk mengajukan beberapa pertanyaan seputar sistem pencarian dokumen yang telah berjalan pada web milik perpustakaan Universitas Bina Nusantara. Kenyataan di lapangan belum mendukung untuk dijalankannya teknologi terbaru ini dikarenakan jumlah jurnal yang masih sedikit, sehingga belum perlu dilakukan proses pencarian jurnal, meski sebenarnya tetap disediakan oleh web milik perpustakaan Universitas Bina Nusantara, yaitu pencarian berdasarkan bidang jurnal, apakah Teknologi Informasi, Matematika, dan sebagainya. Selain jumlah jurnal yang sedikit, kebanyakan jurnal pada web milik perpustakaan Universitas Bina Nusantara tidak saling memiliki keterkaitan satu sama lain, sehingga melakukan pengelompokan pada jurnal–jurnal yang ada belum dapat direalisasikan. Oleh karena beberapa hambatan yang telah disebutkan, maka dalam melakukan pengembangan teknologi pencarian dokumen dalam web terbaru ini, penulis menggunakan data buatan, selain juga dengan pertimbangan bahwa analisa lebih mudah dilakukan pada data yang jumlahnya belum terlalu besar. Penulis tetap optimis bahwa suatu saat dengan berkembangnya jurnal yang ada di web milik perpustakaan Universitas Bina Nusantara, baik dari segi jumlah maupun keberagaman, juga disertai dengan penataan jurnal dengan cara yang baik, maka teknologi terbaru dengan algoritma Lingo ini dapat digunakan lebih lanjut dalam pengembangan web milik perpustakaan Universitas. Bina Nusantara. 34
3.3.2
Data Yang Digunakan Dipergunakan data buatan dalam program aplikasi yang dirancang dengan
pertimbangan bahwa analisa lebih mudah dilakukan pada data yang jumlahnya belum terlalu besar. Perhitungan secara manual terhadap seluruh data yang ada dalam setiap tahapan algoritma Lingo telah dicantumkan pada teori sebagai contoh soal. Pencocokan hasil akan dilakukan pada setiap tahap algoritma Lingo antara program aplikasi dengan perhitungan manual yang telah dikerjakan. Dilakukan analisa singkat terhadap hasil pencocokkan hasil perhitungan antara manual dan program aplikasi untuk membuktikan keakuratan hasil program aplikasi. Disediakan 7 buah dokumen dengan ekstensi .txt di mana isi dari masing-masing dokumen sebagai berikut: D1 : Large Scale Singular Value Computations D2 : Software for the Sparse Singular Value Decomposition
D3 : Introduction to Modern Information Retrieval D4 : Linear Algebra for Intelligent Information Retrieval
D5 : Matrix Computations D6 : Singular Value Analysis of Cryptograms D7 : Automatic Information Organization User melakukan input 2 buah frase ke dalam kotak pencarian. Dua buah frase yang ingin dicari sebagai berikut: P1 : Singular Value P2 : Information Retrieval
35
Setelah melalui proses Stop Words Removal dan Stemming akan dihasilkan sejumlah kata terpilih dari seluruh kata yang berada pada 7 buah dokumen. Diharapkan 5 buah kata yang terpilih sebagai berikut: T1 : Information T2 : Singular
T3 : Value T4 : Computations
T5 : Retrieval Hanya kata yang telah melalui Stop Words Removal dan Stemming tersebut yang akan diproses lebih lanjut dalam tahap algoritma Lingo selanjutnya. Setelah melalui setiap tahap algoritma Lingo, diharapkan pencarian dokumen akan mengembalikan hasil dalam bentuk pengelompokan dan urutan relevansi sebagai berikut: Information Retrieval [skor: 0.97] D3 : Introduction to Modern Information Retrieval D4 : Linear Algebra for Intelligent Information Retrieval
D7 : Automatic Information Organization Singular Value [skor: 0.92] D2 : Software for the Sparse Singular Value Decomposition
D6 : Singular Value Analysis of Cryptograms D1 : Large Scale Singular Value Computations
Others: [yang tidak ditandai kedalam kelompok manapun] D5 : Matrix Computations Pada
kelompok
“Singular
Value”,
dokumen
D2
disebutkan
terlebih
dahulusebelum D6 dan D1 , karena skor kekerabatan antara frase “Singular Value”
36
dengan dokumen D2 yang diperoleh lebih tinggi daripada skor frase “Singular Value” dengan D6 dan D1 .
3.3.3
Perancangan Program Aplikasi Program aplikasi dirancang untuk memperkenalkan tahapan-tahapan “Klasifikasi
dan Visualisasi Teks Dengan Algoritma Lingo” hingga didapatkannya hasil pencarian yang relevan. User diminta untuk menginput query ke dalam kotak pencarian dan menekan satu persatu tombol secara berurut mulai dari atas ke bawah. Setiap tombol yang ditekan akan menampilkan informasi pada Papan Informasi sebelah kiri tombol mengenai tahapan dalam proses yang sedang dilalui yang ditandai dengan setiap tombol yang ada hingga penemuan hasil pencarian. Hasil pencarian sesuai dengan query yang diinput akan ditampilkan setelah penekanan tombol “Penandaan File Ke Kelompok”, berupa kelompok–kelompok yang terbentuk beserta seluruh dokumen yang ada yang telah tergabung dalam kelompok tersebut dalam urutan relevansi yang jelas. Hanya ada satu layar pada program aplikasi yang terdiri atas sepuluh buah tombol. Berikut akan dijelaskan spesifikasi dari tombol–tombol yang ada. a) Tombol “Baca Seluruh File” menjalankan modul di mana dilakukan pembacaan terhadap seluruh dokumen, sekaligus dilakukan penyimpanan dalam sebuah array dinamis akan setiap kata yang dibaca, juga dari dokumen mana kata itu berasal. Papan Informasi akan menampilkan seluruh kata yang terdapat pada seluruh dokumen.
37
b) Tombol “Baca Daftar Stop Words” menjalankan modul di mana dilakukan pembacaan terhadap sebuah dokumen khusus yang menyimpan kata yang termasuk dalam daftar Stop Words. Papan Informasi akan menampilkan daftar kata yang termasuk daftar Stop Words. c) Tombol “Buang Kata Stop Words” menjalankan modul di mana setiap kata yang tersimpan dari pembacaan file akan disaring dengan melakukan pembuangan kata dari array dinamis jika termasuk dalam daftar Stop Words. Papan Informasi akan menampilkan daftar seluruh kata yang dikumpulkan dari dokumen yang lolos setelah melalui proses Stop Words Removal. d) Tombol “Stemming” menjalankan modul di mana setiap kata yang tersimpan dari pembacaan file yang telah lolos dalam penyaringan pertama, akan disaring kedua kalinya dengan mengubah kata menjadi kata dasarnya, misalkan kata “cars” menjadi kata “car”. e) Tombol “Buat Vektor Dokumen dan Normalisasi” menjalankan modul yang membentuk term document matrix, sebuah matriks yang merepresentasikan seluruh dokumen, di mana kolom mendeskripsikan dokumen dan baris mendeskripsikan kata. Proses pembentukan term document matrix dapat dilakukan dengan memproses array dinamis berupa sejumlah kata dan dokumen asal kata tersebut yang telah melalui dua kali penyaringan. Sebelum dibentuknya term document matrix sebagai satu matriks yang mewakili seluruh dokumen, dibentuk terlebih dahulu vektor dokumen yang merepresentasikan masingmasing dokumen yang hanya terdiri dari satu buah kolom, di mana baris mewakili kata, dan untuk setiap dokumen digunakan urutan kata yang sama. Setelah vektor dokumen terbentuk, normalisasi dilakukan untuk mendapatkan 38
panjang vektor sama untuk setiap dokumen. Papan Informasi menampilkan seluruh vektor dokumen sebelum dan sesudah dilakukan normalisasi. f) Tombol “SVD” menjalankan modul SVD (Singular Value Decomposition) yang memecah matriks A sebagai term document matrix menjadi 3 buah matriks, yaitu U , ∑ , V . di mana A = U ∑ V T . Papan Informasi akan menampilkan matriks A dan U , ∑ , V yang merupakan hasil perhitungan SVD dari term
document matrix A . g) Tombol “Hitung Banyaknya Kelompok” menjalankan modul yang menghitung jumlah kelompok yang akan terbentuk. Dilakukan iterasi hingga mencapai kondisi perhentian yaitu q hitung > batas ambang kandidat label, di mana q berasal dari pengolahan terhadap nilai yang didapat dari diagonal matriks ∑ . Papan Informasi menampilkan matriks ∑ kembali dan proses iterasi dalam melakukan perhitungan jumlah kelompok yang akan terbentuk.
h) Tombol “Buat Vektor Frase dan Normalisasi” menjalankan modul di mana setiap frase yang diinput oleh user, masing-masingnya diolah menjadi sebuah vektor frase. Frase tersebut yang nantinya akan digunakan sebagai kelompok. Sebuah vektor frase terdiri atas 1 kolom dan sejumlah baris yang mewakili kata. Setelah vektor frase terbentuk, lakukan normalisasi untuk mendapatkan panjang yang sama pada setiap vektor frase. Papan Informasi menampilkan seluruh vektor frase sebelum dan sesudah dilakukan normalisasi. i) Tombol “Hitung Deskripsi Kelompok” menjalankan modul yang mengalikan transpos dari sejumlah k (jumlah kelompok) kolom dari matriks U
39
hasil
perhitungan SVD, dengan matriks frase P dengan rumus M = U kT P . Nilai maksimum pada setiap baris M mendeskipsikan setiap kelompok yang akan terbentuk. Papan Informasi menampilkan matriks U kembali, U kT , P , dan M sebagai hasil perkalian keduanya, juga kesimpulan yang dapat ditarik dengan melihat pada hasil yang diperoleh pada matriks M . j) Tombol “Penandaan File Ke Kelompok” menjalankan modul yang mengalikan transpos dari matriks frase Q dengan matriks awal term document matrix A dengan rumus C = Q T ⋅ A . Matriks C menggambarkan tingkat kekerabatan antara frase sebagai baris dan dokumen sebagai kolom, sehingga pemilihan satu nilai yang maksimum dari setiap kolomnya menjadi penentu kelompok frase mana yang paling relevan untuk suatu dokumen. Papan informasi menampilkan matriks Q T , A , dan C sebagai hasil perkalian keduanya, juga kesimpulan yang dapat ditarik dengan melihat pada hasil yang diperoleh pada matriks C yang merupakan hasil akhir pencarian.
40
Masukkan kata yang ingin dicari:
Baca Seluruh File Baca Daftar Stop Words Buang Kata Stop Words Stemming Buat Vektor Dokumen & Normalisasi Gambar 3.1 Rancangan tampilan layar “Klasifikasi SVD dan Visualisasi Teks Dengan Algoritma HitungLingo” Banyaknya Kelompok Buat Vektor Frase & Normalisasi Hitung Deskripsi Kelompok Penandaan File Ke Kelompok
Gambar 3.1 Rancangan Tampilan Layar
3.3.4
Diagram Alur Tahapan Algoritma Lingo Berikut tahapan alur algoritma Lingo beserta diagramnya..
1. Dimulai dari pembacaan kata yang terdapat seluruh file/dokumen untuk dilakukan proses Stop Words Removal dan Stemming. Ini semua merupakan sub bagian dari tahap Preprocessing. 2. Lakukan pengekstrakan kata yang sering muncul untuk mendapatkan kandidat kata. Tahap selanjutnya lakukan perhitungan vektor dokumen, kemudian normalisasi. Vektor dokumen yang telah normal merupakan satuan kolom dari 41
term document matrix. Ini semua merupakan sub bagian dari tahap Frequent Phrase Extraction. 3. Langkah selanjutnya, a) Lakukan
perhitungan
SVD
(Singular
Value
Decomposition)
untuk
mendapatkan konsep abstrak dari term document matrix yang dilambangkan dengan matriks U . b) Hitung jumlah kelompok yang terbentuk dari pengolahan hasil perhitungan SVD. c) Hitung vektor frase dan lakukan normalisasi. Vektor frase yang telah normal merupakan satuan kolom dari phrase matrix. d) Kemudian hitung deskripsi kelompok (label beserta skor dari kelompok) yang akan terbentuk dari pengolahan hasil SVD dan phrase matrix dengan jumlah kelompok sesuai hasil perhitungan 3b. Ini semua merupakan sub bagian dari tahap Cluster Label Induction. 4. Lakukan penandaan file ke dalam kelompoknya masing-masing yang terbentuk dari pengolahan hasil perhitungan term document matrix dan phrase matrix. Proses ini merupakan sub bagian dari tahap Cluster Content Discovery.
Baca seluruh file sejumlah kata Lakukan proses Stop Words Removal sejumlah kata Lakukan proses Stemming sejumlah kata 42
Gambar 3.2 Diagram Alur Preprocessing
Buat vektor dokumen
document vector not normal Lakukan normalisasi vektor dokumen
document vector normal Buat term document matrix
term document matrix Gambar 3.3 Diagram Alur Frequent Phrase Extraction
Lakukan perhitungan SVD
U , ∑, V matriks Hitung jumlah kelompok yang akan terbentuk dengan iterasi jumlah kelompok = k Buat vektor frase
phrase vector not normal Lakukan normalisasi vektor frase
phrase vector normal Buat phrase matrix
phrase matrix normal Hitung deskripsi kelompok skor per kelompok Gambar 3.4 Diagram Alur Cluster Label Induction
43
Penandaan file ke kelompok Hasil pencarian dokumen dalam bentuk pengelompokan dan urutan Gambar 3.5 Diagram Alur Cluster Content Discovery
Preprocessing
Frequent Phrase Extraction
Cluster Label Induction
Cluster Content Discovery Gambar 3.6 Diagram Alur Tahapan Algoritma Lingo
44
