IMPLEMENTASI VECTOR SPACE MODEL UNTUK PENCARIAN DOKUMEN

IMPLEMENTASI VECTOR SPACE MODEL UNTUK PENCARIAN DOKUMEN Abdul Azis Abdillah1, Indra Bayu Muktyas2 Program Studi Pendidikan Matematika, STKIP Surya, Tangerang, Banten [email protected], [email protected] ABSTRAK Memiliki banyak dokumen terkadang sangat merepotkan, terutama disaat ingin mencari dokumen yang dibutuhkan secara cepat dan tepat. Salah satu cara untuk mencari dokumen dari tumpukan dokumen adalah dengan me-ranking. Ranking merupakan salah satu cabang ilmu dari information retrieval. Information retrieval yaitu menemukan materi (biasanya dokumen) dari sebuah kumpulan data yang tidak terstruktur (biasanya teks) untuk memenuhi kebutuhan informasi dari koleksi yang besar (Manning dkk, 2008). salah satu metode pencarian dokumen adalah dengan menggunakan Vector Space Model (VSM). VSM menggunakan konsep yang terdapat pada aljabar linear yaitu ruang vektor. Berdasarkan konsep yang digunakan tersebut, dikembangkan pemodelan dokumen untuk melakukan pencarian terhadap dokumen yang dibutuhkan. Representasi vektor kolom dimanfaatkan dalam pengkonversian dokumen input. Konsep lain yang digunakan adalah dengan mengetahui kedekatan antara dua buah vektor, yaitu dengan cara menghitung besarnya sudut yang terbentuk antara dua vektor dan kemudian diurutkan dari data yang memiliki besar sudut yang terkecil hingga yang terbesar yang menandakan urutan data hasil ranking dari yang paling relevan hingga tidak relevan. Pada paper ini dijelaskan tentang pencarian dokumen dengan menggunakan VSM dan implementasinya pada 50 judul buku yang terdapat pada database perpustakaan STKIP Surya. Kata kunci : ranking, information retrieval, Vector Space Models. ABSTRACT we have many documents are sometime very inconvenient, especially when we want to search for document that we need quickly and accurately. One way to search for document from the pile of documents is with ranking. Ranking is one of science in information retrieval. Information retrieval is finding material (especially documents) from unstructured dataset (especially text) to fulfill information needs from large collection (Manning et al, 2008). Vector Space Model (VSM) is one of method to search document that uses ranking. VSM uses vector space concept in linear algebra. Based on the concepts used, developed modeling documents to conduct a search of the necessary documents. Column vector representation used in the conversion of input document. Another concept that is used to determine the proximity between two vectors, by calculating the angle formed between the two vectors and then sorted from the data that has a large measure of angle the smallest to the largest. That point indicates the results of ranking from relevant document to irrelevant document. This paper described vector space model implementation in finding document using 50 books from STKIP Surya library database. Keywords : ranking, information retrieval, Vector Space Models. PENDAHULUAN Memiliki banyak dokumen terkadang sangat merepotkan, terutama disaat ingin mencari dokumen yang kita butuhkan secara cepat dan tepat. Pada tahun 2005, Yahoo! mengumumkan bahwa Search Engine Yahoo! telah mengindeks lebih dari 19.2 milyar dokumen (www.iht.com/articles/2005/08/15/business/we b.php). Dokumen dengan jumlah yang sangat banyak tersebut, tentu memerlukan suatu mekanisme agar pengguna dapat melakukan pencarian atau mendapatkan kembali dokumen

yang sesuai dengan kebutuhan secara cepat dan mudah. Tanpa hal tersebut, maka informasi yang terdapat dalam dokumen akan tanpa guna. Salah satu cara untuk mendapatkan kembali informasi yang terdapat dalam dokumen yang sesuai dengan kebutuhan pengguna adalah dengan melakukan Ranking. Ranking merupakan salah satu cabang ilmu dari information retrieval. Ranking merupakan bagian penting dari masalah pencarian informasi, seperti pengambilan dokumen, penyaringan informasi, penempatan iklan online, dan lain-lain. Salah satu aplikasi ranking terdapat pada search engine, contohnya

Abdul Azis Abdillah

pada Google dan Yahoo! yang sudah sangat familiar di masyarakat. salah satu metode untuk me-ranking dokumen adalah dengan menggunakan Vector Space Model (VSM). VSM menggunakan konsep yang terdapat pada aljabar linear yaitu ruang vektor. Berdasarkan konsep yang digunakan tersebut, dikembangkan pemodelan dokumen untuk melakukan pencarian terhadap dokumen yang dibutuhkan. Representasi vektor kolom dimanfaatkan dalam pengkonversian dokumen input. Konsep lain yang digunakan adalah dengan mengetahui kedekatan antara dua buah vektor, dengan cara menghitung besarnya sudut yang terbentuk antara dua vektor dan kemudian diurutkan dari data yang memiliki besar sudut yang terkecil hingga yang terbesar yang menandakan urutan data hasil ranking dari yang paling relevan hingga yang tidak relevan. Pada paper ini akan dibahas implementasi Vector Space Model untuk pencarian dokumen.

2. Vector Space Model Vector Space Model (VSM) mempresentasikan setiap dokumen yang terdapat dalam database dan query ke dalam vektor multidimensi. Dimensi dari vektor berkorespondensi dengan jumlah setiap term dalam database dan kumpulan term tersebut membentuk suatu ruang vektor. Pada VSM setiap term, , di dalam dokumen maupun query, , diberikan suatu bobot (weight) yang bernilai real . Dokumen dan query diekspresikan sebagai vektor -dimensi =( , ,…, ) dan diasumsikan terdapat dokumen di dalam database, yaitu = 1,2, … , . Contoh dari VSM dengan tiga dimensi untuk dua dokumen dan , satu query , dan tiga term , , dan dapat dilihat pada gambar 2.

Sumber : Krzysztof J. Cios, 2007

Gambar 2. Representasi dokumen dan query pada ruang vektor Sumber : C.J. van Rijsbergen, 1979

Gambar 1. Diagram alur Information Retrieval LANDASAN TEORI 1. Information Retrieval Information Retrieval (IR) adalah menemukan materi (biasanya dokumen) dari sebuah kumpulan data yang tidak terstruktur (biasanya teks) untuk memenuhi kebutuhan informasi dari koleksi yang besar (Manning dkk, 2008). Tujuan IR adalah untuk memenuhi kebutuhan informasi pengguna dengan meretrieve semua dokumen yang relevan, dan pada waktu yang sama me-retrieve sesedikit dokumen yang tak relevan. Secara umum diagram alur information retrieval dapat dilihat pada gambar 1.

Selain itu pada VSM, database dari semua dokumen direpresentasikan oleh matriks termdocument (atau matriks term-frequency). Dimana setiap sel pada matriks berkorespondensi dengan bobot yang diberikan dari suatu term dalam dokumen yang ditentukan. Nilai nol berarti bahwa term tidak terdapat dalam dokumen. Inverse Document Frequency (IDF). IDF didefinisikan sebagai = log (

dimana merupakan frekuensi dokumen dari term atau sama dengan jumlah dokumen yang mengandung term dan adalah total dokumen di dalam database. Log digunakan untuk memperkecil pengaruh relative untuk . Bobot dihitung menggunakan ukuran tf-idf (term frequency-inversed document frequency) didefinisikan sebagai =

2

)

×

Prodi Pendidikan Matematika, STKIP Surya, Tangerang, Banten

Implementasi Vector Space Model untuk Pencarian Dokumen

3. Similarity

2. Software

Salah satu ukuran kemiripan teks yang popular digunakan pada VSM untuk pencarian dokumen adalah cosine similarity (Krzysztof J. Cios, dkk. 2007). Konsep dari cosine similarity yaitu menghitung nilai cosinus sudut antara dua vektor yaitu jika diberikan dokumen yang dipresentasikan oleh vektor dan query , dan term yang diekstrak dari database, maka nilai cosine similarity didefinisikan sebagai

Software yang digunakan adalah macro VBA yang terdapat pada Microsoft Excel dan OS Windows Vista Ultimate.

,

=

=

Spesifikasi hardware yang digunakan pada eksperimen ini adalah Processor Intel Pentium(R) Dual-Core T4200 @ 2.0GHz 1.20 GHz, RAM 3.5 GB.

⋅ ⋅| |

atau dapat ditulis sebagai ,

3. Hardware

∑

⋅

∑

⋅∑

dimana representasi grafis sudut antara dokumen dan query dapat dilihat pada gambar 3.

Sumber : Krzysztof J. Cios, 2007

Gambar 3. Representasi grafis sudut antara dokumen dan query Secara geometris, sudut yang merentang antara vektor dan query dapat diukur. Semakin kecil sudut diantara kedua vektor dan query , maka akan semakin tinggi derajat kesamaan. Cosinus dari sudut tersebut merupakan koefisien yang dapat mewakili kemiripan antara vektor dan query . EKSPERIMEN 1. Dataset Dataset yang digunakan adalah kumpulan 50 judul buku yang terdapat pada database perpustakaan STKIP Surya. Dataset ini dapat dilihat pada tabel 10.

4. Implementasi Pada implementasi ini ditampilkan 10 dokumen teratas berdasarkan hasil pencarian dokumen dengan 10 query berbeda. Untuk setiap query dilakukan pencarian dokumen dengan VSM tanpa pembobotan tf-idf dan VSM tf-idf dan kemudian dibandingkan hasil pencariannya. Tabel 1 menunjukkan daftar query yang digunakan pada percobaan. Tabel 1. Daftar query yang digunakan Query Detail Query ID Q1 Indonesia Q2 Filsafat Q3 Teknik teknologi Q4 Teknik Internet Q5 Internet Q6 Matematika Teknik Q7 Teknik Analisis Data Q8 Nasionalisme Indonesia Q9 Indonesia Mengajar Q10 Teknologi Indonesia Tabel 2 menunjukkan hasil pencarian 10 dokumen teratas menggunakan query “Indonesia”. Sedangkan tabel 3 menunjukkan hasil pencarian 10 dokumen teratas menggunakan query “filsafat”. Pada VSM dan VSM tf-idf dokumen pertama dan dokumen kedua yang dimunculkan saat di input query “Indonesia” sama yaitu “ceritalah Indonesia” sebagai dokumen pertama dan “Indonesia/proses” sebagai dokumen ke dua, sedangkan untuk dokumen ke tiga dokumen yang dimunculkan berbeda. Dapat dilihat dari kedua dokumen teratas yang ditampilkan memiliki panjang dokumen yang paling pendek jika dibandingkan dengan dokumen lain hasil perangkingan.

Prosiding Seminar Nasional Matematika dan Pendidikan Matematika 2013

3

Abdul Azis Abdillah

Tabel 2. Hasil Pencarian Dokumen Menggunakan Query “indonesia” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D2 0.707107 D2 0.209113 2 D3 0.707107 D3 0.209113 3 D4 0.57735 D5 0.180553 4 D5 0.57735 D19 0.163052 5 D6 0.57735 D45 0.153284 6 D7 0.57735 D49 0.150458 7 D8 0.5 D4 0.149508 8 D9 0.5 D6 0.149508 9 D11 0.5 D7 0.149508 10 D19 0.5 D9 0.136205 Tabel 3. Hasil Pencarian Dokumen Menggunakan Query “Filsafat” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D24 0.866025 D24 0.515841 2 D25 0.755929 D25 0.466161 3 D26 0.707107 D26 0.328367 4 D27 0.57735 D27 0.296367 5 D28 0.57735 D28 0.271456 6 D29 0.5 D49 0.245171 7 D30 0.447214 D29 0.236578 8 D49 0.408248 D30 0.195586 9 D48 0.353553 D48 0.147371 10 D1 0 D1 0 Tabel 4 menunjukkan hasil pencarian 10 dokumen teratas menggunakan query “teknik teknologi”. Sedangkan tabel 5 menunjukkan hasil pencarian 10 dokumen teratas menggunakan query “teknik internet”. Pada VSM dokumen pertama yang muncul adalah “matematika teknik” dimana “matematika teknik” merupakan dokumen dengan panjang terpendek jika dibandingkan dengan dokumen yang lain hasil perangkingan. Sedangkan pada VSM tf-idf dokumen pertama yang dimunculkan jika menggunakan query “teknik teknologi” adalah “teknologi warung internet”, “matematika teknik” berada pada urutan ke empat. Pada VSM dan VSM tf-idf sama-sama menampilkan dokumen “internet” pada urutan pertama saat diinput query “teknik internet”, pada pada VSM dokumen “internet sehat” berada pada urutan ke dua dan “matematika teknik” berada pada urutan ke tiga. Sedangkan VSM tf-idf dilanjutkan dengan dokumen “matematika teknik” pada urutan ke dua dan “teknik dasar autocad”

4

pada urutan ke tiga. Dokumen teratas yang ditampilkan memiliki panjang dokumen yang lebih pendek jika dibandingkan dengan dokumen yang lain hasil perangkingan. Tabel 4. Hasil Pencarian Dokumen Menggunakan Query “teknik teknologi” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D46 0.5 D34 0.390351 2 D34 0.408248 D49 0.338462 3 D44 0.408248 D9 0.305483 4 D50 0.408248 D46 0.24154 5 D23 0.377964 D23 0.222077 6 D9 0.353553 D50 0.201658 7 D45 0.353553 D45 0.190325 8 D47 0.316228 D44 0.178207 9 D43 0.288675 D47 0.15852 10 D49 0.288675 D43 0.145957 Tabel 5. Hasil Pencarian Dokumen Menggunakan Query “teknik internet” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D31 0.707107 D31 0.597577 2 D32 0.5 D46 0.323639 3 D46 0.5 D50 0.270202 4 D33 0.408248 D45 0.255017 5 D34 0.408248 D44 0.23878 6 D35 0.408248 D47 0.212401 7 D44 0.408248 D43 0.195568 8 D50 0.408248 D32 0.186651 9 D36 0.353553 D34 0.158988 10 D37 0.353553 D48 0.150125 Berdasarkan tabel 6, tabel 7, dan tabel 8 jika dipilih suatu query yang dimana query tersebut tepat ada pada database maka dokumen tersebut akan memiliki nilai similarity satu dan akan ditempatkan pada posisi teratas pada setiap pencarian dokumen.



Tabel 6. Hasil Pencarian Dokumen Menggunakan Query “internet” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D31 1 D31 1 2 D32 0.707107 D32 0.312346 3 D33 0.57735 D34 0.266054 4 D34 0.57735 D33 0.245987 5 D35 0.57735 D35 0.245987 6 D36 0.5 D38 0.216527 7 D37 0.5 D39 0.215398 8 D38 0.5 D40 0.196965 9 D39 0.5 D36 0.1865 10 D40 0.5 D37 0.1865

Tabel 9. Hasil Pencarian Dokumen Menggunakan Query “nasionalisme indonesia” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D2 0.5 D17 0.257088 2 D3 0.5 D2 0.052545 3 D4 0.408248 D3 0.052545 4 D5 0.408248 D5 0.045369 5 D6 0.408248 D19 0.040971 6 D7 0.408248 D45 0.038517 7 D17 0.377964 D49 0.037807 8 D8 0.353553 D4 0.037568 9 D9 0.353553 D6 0.037568 10 D11 0.353553 D7 0.037568

Tabel 7. Hasil Pencarian Dokumen Menggunakan Query “matematika teknik” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D46 1 D46 1 2 D44 0.408248 D50 0.159105 3 D50 0.408248 D45 0.150163 4 D45 0.353553 D44 0.140602 5 D47 0.316228 D47 0.12507 6 D43 0.288675 D43 0.115157 7 D48 0.25 D48 0.088399 8 D23 0.188982 D23 0.062545 9 D1 0 D1 0 10 D2 0 D2 0

Tabel 10. Hasil Pencarian Dokumen Menggunakan Query “indonesia mengajar” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D2 0.5 D1 0.318409 2 D3 0.5 D2 0.052545 3 D1 0.471405 D3 0.052545 4 D4 0.408248 D5 0.045369 5 D5 0.408248 D19 0.040971 6 D6 0.408248 D45 0.038517 7 D7 0.408248 D49 0.037807 8 D8 0.353553 D4 0.037568 9 D9 0.353553 D6 0.037568 10 D11 0.353553 D7 0.037568

Tabel 8. Hasil Pencarian Dokumen Menggunakan Query “teknik analisis data” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D44 1 D44 1 2 D46 0.408248 D46 0.142956 3 D50 0.333333 D50 0.119352 4 D45 0.288675 D45 0.112644 5 D47 0.258199 D47 0.09382 6 D43 0.235702 D43 0.086385 7 D48 0.204124 D48 0.066312 8 D23 0.154303 D23 0.046918 9 D1 0 D1 0 10 D2 0 D2 0

Tabel 9 menunjukkan hasil pencarian 10 dokumen teratas menggunakan query “nasionalisme indonesia”, tabel 10 menunjukkan hasil pencarian 10 dokumen teratas menggunakan query “Indonesia mengajar”, dan tabel 11 menunjukkan hasil pencarian 10 dokumen teratas menggunakan query “teknologi informasi”. Pada VSM dokumen yang mengandung query “nasionalisme Indonesia” berada pada urutan ke tujuh, sedangkan pada VSM tf-idf berada pada urutan pertama. Pada VSM dokumen yang mengandung query “Indonesia mengajar” berada pada urutan ke tiga, sedangkan pada VSM tf-idf berada pada urutan pertama. Dokumen yang pertama adalah “ceritalah Indonesia” dan diikuti oleh “Indonesia/proses”. Pada VSM dokumen yang mengandung query “teknologi Indonesia” berada pada urutan pertama, sedangkan pada VSM berada pada urutan ke tiga.


5

Abdul Azis Abdillah

Tabel 11. Hasil Pencarian Dokumen Menggunakan Query “teknologi Indonesia” VSM VSM tf-idf Rank Doc. Doc. Sim Sim Id id 1 D9 0.707107 D34 0.458116 2 D49 0.57735 D49 0.449881 3 D2 0.5 D9 0.405945 4 D3 0.5 D23 0.167092 5 D4 0.408248 D2 0.071184 6 D5 0.408248 D3 0.071184 7 D6 0.408248 D5 0.061462 8 D7 0.408248 D19 0.055505 9 D34 0.408248 D45 0.05218 10 D8 0.353553 D4 0.050894

KESIMPULAN Berdasarkan hasil eksperimen yang diperoleh selama percobaan, dapat diambil beberapa kesimpulan sebagai berikut : 1. Metode Vector Space Model dapat digunakan untuk melakukan pencarian dokumen.

6

2.

3.

Hasil pencarian dokumen menggunakan VSM tanpa pembobotan tf-idf bergantung kepada panjang dokumen. Semakin pendek suatu dokumen yang relevan maka akan ditampilkan pada urutan teratas. Secara umum pencarian dokumen mengunakan VSM tf-idf lebih relevan jika dibandingkan dengan menggunakan VSM tanpa pembobotan tf-idf.

REFERENSI [1] Cios, Krzysztof J., dkk. (2007). Data Mining a Knowledge Discovery Approach. Springer. [2] Manning, Christopher D., Raghavan, Prabhakar,. Schutze. (2008). Introduction to Information Retrieval. Cambridge University Press, New York, USA. [3] Salton, G., Wong, A., Yang, C. S. (1975). A Vector Space Model for Automatic Indexing. Communications of the ACM, Nov 1975, volume 18, Number 11, Pp. 613-620 [4] Van Rijsbergen, C.J. (1979). Information Retrieval. Butterworths, London.



LAMPIRAN

No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

24 25

Tabel 12. Dataset yang digunakan pada eksperimen Doc. Judul Buku No. Judul Buku ID Indonesia mengajar-kisah para D1 26 Filsafat modern pengajar muda di pelosok negeri Ceritalah indonesia D2 27 Filsafat pendidikan islam Indonesia/proses D3 28 Pengantar filsafat barat Menuju indonesia swadaya D4 29 Pengantar filsafat ilmu pengetahuan Kamus inggris-indonesia D5 30 Filsafat ilmu sebuah pengantar populer Korupsi mengorupsi indonesia D6 31 Internet Digital camera indonesia D7 32 Internet sehat Direktori open source indonesia D8 33 Mari mengenal internet Teknologi indonesia akan kemana? D9 34 Teknologi warung internet Godot di amerika dan indonesia D10 35 Belajar sendiri internet Bantuan likuiditas bank indonesia D11 36 Konferensi video melalui internet Indonesia habis gelap terbitlah D12 37 Bisnis Sukses lewat Internet terang The internet in indonesia's new D13 38 Belajar internet untuk anak democracy Munju sejarah sumatra antara D14 39 Internet Wireless dan Hotspot indonesia dan dunia Tanah air bahasa (seratus jejaqk D15 40 Mengenal internet for beginners pers indonesia) Kamus inggris - indonesia: pilihan D16 41 Internet governance asia-pasific kata lain penerjemah perspektif Nasionalisme-kenali indonesia-mu, D17 42 Arah kebijakan penyelenggaraan temukan passion-mu berkaryalah jasa internet teleponi (VOIP) di untuk masa depan bangsamu Indonesia Politik pendidikan D18 43 Dasar-dasar Teknik Pemrograman Revolusi pendidikan di indonesia D19 44 Teknik analisis data Pendidikan tanpa kekerasan D20 45 Teknik membangun indonesia jaya Setia budhi: jurnal pendidikan D21 46 Matematika teknik Potensi kekayaan intelektual D22 47 Teknik pengawetan tanah dan air departemen pendidikan nasional Pengembangan sekolah teknik D23 48 Filsafat teknik dan pikiran elektro dan informatika institut spiritualis dari siswa pemula teknologi bandung sebagai institusi pendidikan berbasis riset Filsafat kantian, filsafat jacobian, D24 49 Filsafat dan teknologi untuk filsafat fictean membangun indonesia Filsafat jiwa dan filsafat ilmu D25 50 Teknik dasar autocad


Doc. ID D26 D27 D28 D29 D30 D31 D32 D33 D34 D35 D36 D37 D38 D39 D40 D41 D42 D43 D44 D45 D46 D47 D48

D49 D50

7

IMPLEMENTASI VECTOR SPACE MODEL UNTUK PENCARIAN DOKUMEN

Recommend Documents