PENGUKURAN TINGKAT KEMIRIPAN DOKUMEN TEKS DENGAN PROSES ALGORITMA GENETIKA MENGGUNAKAN POSI FORMULATION
TESIS
DARWIS ROBINSON MANALU 127038077
PROGRAM STUDI S2 TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
PERSETUJUAN
Judul
: Pengukuran Tingkat Kemiripan Dokumen Teks Dengan Proses Algoritma Genetika Menggunakan POSI Formulation
Kategori
: Tesis
Nama
: Darwis Robinson Manalu
NIM
: 127038077
Program Studi
: S2 Teknik Informatika
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing Pembimbing 2,
Pembimbing 1,
Dr. Poltak Sihombing, M.Kom
Prof. Dr. Muhammad Zarlis
Diketahui/Disetujui oleh Program Studi S2 Teknik Informatika Ketua,
Prof. Dr. Muhammad Zarlis NIP : 195707011986011003
i
Universitas Sumatera Utara
PERNYATAAN
PENGUKURAN TINGKAT KEMIRIPAN DOKUMEN TEKS DENGAN PROSES ALGORITMA GENETIKA MENGGUNAKAN POSI FORMULATION
TESIS
Saya mengakui semua tesis ini adalah hasil karya saya sendiri kecuali beberapa kutipan dan ringkasan yang masing-masing telah di disebutkan sumbernya.
Medan, Februari 2015
Darwis Robinson Manalu 127 038 077
ii
Universitas Sumatera Utara
Telah diuji pada Tanggal : 3 Februari 2015
PANITIA PENGUJI TESIS Ketua
: Prof Dr. Muhammad Zarlis
Anggota
: Dr. Poltak Sihombing, M.Kom : Prof. Dr. Herman Mawengkang : Dr. Erna Budhiarti Nababan : Prof . Dr. Drs. Iriyanto, M.Si
iii
Universitas Sumatera Utara
PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS Sebagai civitas akademika Universitas Sumatera Utara, saya yang bertanda tangan di bawah ini: Nama NIM Program Studi Jenis Karya Ilmiah
: Darwis Robinson Manalu : 127038077 : S2 Teknik Informatika : TESIS
Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Sumatera Utara Hak Bebas Royalti Non-Eksklusif (Non-Exclusive Royalty free Right) atas Tesis saya yang berjudul: Pengukuran Tingkat Kemiripan Dokumen Teks Dengan Proses Algoritma Genetika Menggunakan Posi Formulation Beserta perangkat yang ada (jika diperlukan). Dengan Hak Bebas Royalti NonEksklusif ini, Universitas Sumatera Utara berhak menyimpan, mengalih media, memformat, mengelola dalam bentuk database, merawat dan mempublikasikan Tesis saya tanpa meminta izin dari saya selama tetap mencantumkan nama saya sebagai penulis dan sebagai pemegang dan atau sebagai pemilik hak cipta. Demikian pernyataan ini dibuat dengan sebenarnya.
Medan, Februari 2015
Darwis Robinson Manalu 127 038 077
iv
Universitas Sumatera Utara
RIWAYAT HIDUP
DATA PRIBADI Nama
: Darwis Robinson Manalu, S.Kom,MM
Tempat dan Tanggal Lahir
: Nagurguran 10 April 1976
Alamat Rumah
: Jl Serimpi III No 6 Medan Permai, Kelurahan Namo Gajah, Medan Tuntungan
Telepon / HP
: 081264960001
Email
:
[email protected]
Instansi Tempat Bekerja
: Kopertis Wilayah I Dpk UMI-Medan
Alamat Kantor
: Jlan Hang tuah No 8 Medan
DATA PENDIDIKAN Nama Institusi
Status
Tahun
SD
: SD Negeri 3 No. 173395 Doloksanggul
Tamat
1988
SMP
: SMP Negeri 1 Doloksangul
Tamat
1991
SMU
: SMA Negeri 1 Doloksanggul
Tamat
1994
D-3
: Teknik Komputer Universitas Sisingamangaraja XII Medan
Tamat
1998
S-1
: Teknik Informatika STMIK Sisingamangaraja XII Medan
Tamat
2001
S-2
: Magister Manjemen Universitas HKBP Nommensen
Tamat
2007
S-2
: Teknik Informatika Universitas Sumatera Utara
Tamat
2015
v
Universitas Sumatera Utara
UCAPAN TERIMAKASIH Puji Syukur kehadirat Tuhan Yang Maha Kuasa yang telah memberikan berkat dan lindunganNya kepada penulis sehingga Tesis ini dapat diselesaikan dengan judul “Pengukuran Tingkat Kemiripan Dokumen Teks Dengan Proses Algoritma Genetika Menggunakan POSI Formulation”. Tesis merupakan salah satu syarat yang harus dipenuhi oleh setiap mahasiswa untuk mendapat gelar Magister Komputer pada Program Studi Teknik Informatika Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. Pada kesempatan ini pula penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada berbagai pihak yang telah banyak membantu peneliti baik secara moril maupun material, langsung dan tidak langsung sehingga penulisan tesis ini selesai tepat pada waktunya. Untuk itu semua saya ingin mengucapkan terima kasih kepada : 1. Bapak Prof. Dr. dr. Syahril Pasaribu,DTMH,M.Sc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara 2. Bapak Prof. Dr. H. Muhammad Zarlis sebagai Dekan FASILKOM-TI dan Ketua Program Studi S2 Teknik Informatika sekaligus Pembimbing 1 yang telah banyak memberikan masukan dan arahan dalam perkuliahan dan pengerjaa tesis ini. 3. Bapak M. Andri Budiman, ST, M.Comp.Sc, MEM selaku sekretaris Program Studi S2 Teknik Informatika. 4. Bapak Dr. Poltak Sihombing, M.Kom selaku pembimbing 2 yang telah banyak memotivasi dan mengarahkan selama perkuliahan serta memberikan dorongan dalam penulisan tesis ini. 5. Bapak Prof. Dr. Herman Mawengkang selaku ketua komisi Penguji . 6. Bapak Prof Dr. Iriyanto, M.Si , selaku anggota komisi Penguji . 7. Ibu Dr. Erna Budhiarti Nababan selaku anggota komisi Penguji . 8. Bapak/Ibu Dosen Program Studi S2 Teknik Informatika 9. Staf dan Pegawai yang telah baik melayani selama perkuliahan tentang administrasi dan informasi. 10. Bapak Prof. Dian Armanto, M.Sc,M.Pd, Ph.D. selaku Pimpinan Saya di Kopertis Wilayah I
vi
Universitas Sumatera Utara
11. Bapak Ir. Pantas Simanjuntak,MM Selaku Rektor Universitas Methodist Indonesia yang telah memberikan dukungan dan kesempatan untuk melanjutkan perkuliahan di Universitas Sumatera Utara baik moril dan material. 12. Bapak Drs. Humuntal Rumapea, M.Kom Selaku Dekan Fakultas Ilmu Komputer Universitas Methodist Indonesia yang selalu memberikan dukungan dalam perkuliahan. 13. Rekan-rekan Dosen Fakultas Ilmu Komputer Universitas Methodist Indonesia 14. Rekan-rekan mahasiswa S2 Teknik Informatika Angkatan 2012 Kelas C. 15. Kepada Ibunda tercinta B br Purba yang selalu memberikan dukungan moril, materil serta doa kepada penulis sampai saat ini. 16.
Kepada istriku tercinta Dessy Rumika Napitupulu, SE dan anak-anakku tercinta Grace Romasta Manalu dan Geraldo Cakra Buana
Manalu yang selalu
memberikan dorongan dan dukungan selama perkuliahan. 17. Semua pihak yang telah memberikan bantuan moral dan material dalam penyelesaian tesis ini. Penulis menyadari bahwa kemampuan dan pengalaman penulis masih sangat terbatas. Oleh karena itu, semoga kekurangan yang ada pada penulis dapat diperbaiki dan harapan saya Tesis ini bermanfaat bagi semua pihak,
Medan, Februari 2015 Penulis,
Darwis Robinson Manalu 127 038 077
vii
Universitas Sumatera Utara
DAFTAR ISI
PENGESAHAN…………………………………………………………...
i
PERNYATAAN ORISINALITAS………………………………………..
ii
PANITIA PENGUJI...……………………………………………………..
iii
BAB 1 PERSETUJUAN PUBLIKASI.......................................................................
iv
BAB 1 RIWAYAT HIDUP ....…………………………………………………….. UCAPAN BAB 1 TERIMAKASIH.....……………………………………………
v vi
DAFTAR ISI ......................…..……………………………………………
viii
DAFTAR BAB 1 TABEL. …………………………………………………………
xi
DAFTAR GAMBAR……………………………………………………….
xii
ABSTRAK.………………………………………………………………...
xiii
ABSTRACT………………………………………………………………...
xiv
BAB 1 PENDAHULUAN ...........................................................................
1
1.1. Latar Belakang Masalah ............................................................
1
1.2. Rumusan Masalah......................................................................
2
1.3. Batasan Masalah ........................................................................
2
1.4. Tujuan dan Manfaat.....................................................................
3
1.5. Sistematika Penelitian ...............................................................
3
BAB 2 TINJAUAN PUSTAKA ................................................................ 2.1. Information Retrieval ………………………………………….
5
2.1.1 Definisi…………………………………………………..
5
2.1.2 Arsitektur Information Retrieval System…………………
6
2.2. Algoritma Genetika……………………………………………...
8
BAB 1
5
2.2.1. Pengertian Dasar Metode Algoritma Genetika………….
9
2.2.2 Operator Algoritma Genetika ……………………………
14
2.3 Algoritma Umum pada Algoritma Genetika ……………………
18
2.3.1
Membentuk Model Kromosom. ……………………..
19
2.3.2
Membentuk Populasi Awal Secara Acak……………
19
2.3.3
Mengevaluasi Fitness Untuk Setiap Kromosom. ……
20
2.3.4
Penentuan Populasi Generasi Berikutnya. ………...
21
viii
Universitas Sumatera Utara
2.3.5
Melakukan Crossover dan Mutasi………………….
22
2.3.6
Evaluasi Generasi Berikutnya. …………………….
25
2.4 Fungsi Cosine Similaritas ……………………………………..
25
2.5 POSI Formulation …………………………………………….
26
2.6 Teks Mining …………………………………………………..
27
2.6.1 Pengertian Teks Mining …………………………….
27
2.6.2 Ruang Lingkup Teks Mining ……………………….
28
2.6.3. Ekstraksi Dokumen ………………………………….
30
2.6.3.1 Case folding dan Tokenizing
31
…………………. 2.6.3.2 Filtering …………………………………….
31
2.7 String Matching... ……………………………………………...
32
2.8 Penelitian Terdahulu ………………………………………….
32
2.9 Kontribusi Penelitian…………………………………………..
33
BAB 3 METODOLOGI PENELITIAN .................................................... 3.1 Tahapan Penelitian…………………………………………….
34
3.2 Jenis dan Sumber Data…………………………………………. …………………………………………………. 3.3 Pengumpulan Data………………………………………………
30
3.4 Metode Pengujian Data…………………………………………
32
29
30
3.4.1
Kerangka Pengujian……………………………….
31
3.4.2
Proses Kompetisi Kata Kunci ……………………..
33
3.4.3
Pembentukan Kromosom …………………………
34
3.4.3
POSI Formulation………. ………………………..
36
BAB 4 PEMBAHASAN DAN HASIL
44
4.1 Pembahasan …………………………………………………….
44
4.2 Kromosom Kata Kunci………………………………………….
45
4.3 Representasi Kata Kunci…………………………………………
48
4.4 Evaluasi Fitness Kata Kunci ……………………………………
48
4.4.1 Jaccard'sfunction………………………………………….
52
4.4.2 Fungsi Cosine Similarity………………………………..
67
4.5 Proses Pemilihan Kata Kunci……………………………………
66
4.6 Crossover Kromosom Kata Kunci………………………………
69
ix
Universitas Sumatera Utara
4.7 Mutasi Kromosom Kata Kunci…………………………………..
70
4.8 Rekombinasi Kromosom Kata Kunci…………………………..
72
4.9 Kromosom Kata Kunci Solusi ………………………………….
73
4.10 Pengujian Dan Hasil …………………………………………..
74
4.10.1 Prototipe Aplikasi ……………………………………
74
4.10.2 Pengujian Kemiripan Dokumen………………………
75
4.10.3 Perhitungan Persentase Kemiripan…………………
76
BAB 5 SIMPULAN DAN SARAN
77
5.1 Simpulan……………………………………………………….
77
5.2 Saran…………………………………………………………
77
DAFTAR PUSTAKA
78
x
Universitas Sumatera Utara
DAFTAR TABEL
Tabel 2.1
Perhitungan Nilai Fitness………………………………………….
12
Tabel 4.1
Kata Kunci Dari Permintaan User ………………………….
45
Tabel 4.2
Mutasi Kromosom Kata Kunci ……………………………….
73
Tabel 4.3
Sumber Dokumen Yang Diuji ………………………………..
77
Tabel 4.4
Pengujian Dan Hasil …………………………………………
78
Tabel 4.5
Perhitungan Kata Kunci Solusi……………………………….
79
.
xi
Universitas Sumatera Utara
DAFTAR GAMBAR
Gambar 2.1 Sistem Temu Kendali Informasi……………………….…………
8
Gambar 2.2 Proses Algoritma Genetika ……………………………………….
12
Gambar 2.3 Individu Dalam Algoritma Genetika ………………………………
13
Gambar 2.4 Seleksi Berdasarkan Pada Regular Sampling Space …………….
15
Gambar 2.5 Seleksi Dilakukan Pada Enlarge Sampling Space ……………….
16
Gambar 2.6 Tahap Preprocessing………………………………………………
31
Gambar 2.7 Proses Tokenizing…………………………………………………
31
Gambar 2.8 Proses Filtering……………………………………………………
31
Gambar 3.1 Metodologi Pengelolaan Pengukuran Kemiripan Dokumen …….
30
Gambar 3.1 Skema Proses Dan Aliran Data …………………………………..
34
Gambar 3.2 Flowchart Preprocessing …………………………………………
37
Gambar 3.3 Skema Kompetisi Kata Kunci ……………………………………
38
Gambar 3.4 Proses Pembentukan Kromosom ………………………………..
40
Gambar 3.5 Proses Pengujian Kemiripan ……………………………………..
41
Gambar 3.4 Perhitungan Persentase Kemiripan ……………………………….
43
Gambar 4.1 Diagram Lingkaran ………………………………………………
69
Gambar 4.2 Tampilan Daftar Dokumen ……………………………………….
76
Gambar 4.3 Tampilan Pemilihan Dokumen yang Akan Diuji ……………..…
76
Gambar 4.4 Laporan Proses Pengujian Dan Kemiripan ………………………
77
xii
Universitas Sumatera Utara
