Rangkuman untuk Pertemuan 22 Natural Language Processing

1. Text Classification / Text Categorization

Salah satu contoh pemanfaatan teks mining adalah text categorization yaitu proses pengelompokan dokumen, yang dalam tugas akhir ini adalah konten web page, ke dalam beberapa kelas yang telah ditentukan. Jika tidak ada overlap antar kelas, yaitu setiap dokumen hanya dikelompokan kedalam satu kelas maka text categorization ini disebut single label text categorization . Text categorization bertujuan untuk menemukan model dalam mengkategorisasikan teks natural language. Model tersebut akan digunakan untuk menentukan kelas dari suatu dokumen.
Beberapa metode text categorization yang sering dipakai antara lain : k- Nearest Neighbor, Naïve Bayes, Support Vektor Machine, Decision Tree, Neural Networks, Boosting. Dalam pengaplikasian text categorization terdapat beberapa tahap, yaitu : preprocessing, training phase dan testing phase.

Preprocessing
Tahap pertama dalam text categorization adalah dokumen preprocessing adalah :
1. Ekstrasi Term
Ekstrasi term dilakukan untuk menentukan kumpulan term yang mendeskripsikan dokumen. Kumpulan dokumen di parsing untuk menghasilkan daftar term yang ada pada seluruh dokumen. Daftar term yang dihasilkan disaring dengan membuang tanda baca, angka, simbol dan stopwords. Dalam tugas akhir ini akan dibahas juga mengenai pengaruh stopwords removal terhadap hasil klasifikasi. Berikut ini merupakan penjelasan singkat mengenai stopwords.

Kebanyakan bahasa resmi di berbagai negara memiliki kata fungsi dan kata sambung seperti artikel dan preposisi yang hampir selalu muncul pada dokumen teks. Biasanya kata-kata ini tidak memiliki arti yang lebih di dalam memenuhi kebutuhan seorang searcher di dalam mencari informasi. Kata-kata tersebut (misalnya a, an, dan on pada bahasa Inggris) disebut sebagai Stopwords.

Sebuah sistem Text Retrieval biasanya disertai dengan sebuah Stoplist. Stoplist berisi sekumpulan kata yang ‘tidak relevan’, namun sering sekali muncul dalam sebuah dokumen. Dengan kata lain Stoplist berisi sekumpulan Stopwords.

Stopwords removal adalah sebuah proses untuk menghilangkan kata yang ‘tidak relevan’ pada hasil parsing sebuah dokumen teks dengan cara membandingkannya dengan Stoplist yang ada.

2. Seleksi Term
Jumlah term yang dihasilkan pada feature ekstrasi dapat menjadi suatu data yang berdimensi cukup besar. Karena dimensi dari ruang feature merupakan bag-of-words hasil pemisahan kata dari dokumennya. Untuk itu perlu dilakukan feature selection untuk mengurangi jumlah dimensi.

3. Representasi Dokumen
Supaya teks natural language dapat digunakan sebagai inputan untuk metode klasifikasi maka teks natural language diubah kedalam representasi vektor. Dokumen direpresentasikan sebagai vektor dari bobot term, dimana setiap term menggambarkan informasi khusus tentang suatu dokumen. Pembobotan dilakukan dengan melakukan perhitungan TFIDF. Term beserta bobotnya kemudian disusun dalam bentuk matrik.

Training Phase
Tahap kedua dari text categorization adalah training. Pada tahap ini system akan membangun model yang berfungsi untuk menentukan kelas dari dokumen yang belum diketahui kelasnya. Tahap ini menggunakan data yang telah diketahui kelasnya (data training) yang kemudian akan dibentuk model yang direpresantasikan melalui data statistik berupa mean dan standar deviasi masing-masing term pada setiap kelas.

Testing Phase
Tahap terakhir adalah tahap pengujian yang akan memberikan kelas pada data testing dengan menggunakan model yang telah dibangun pada tahap training. Tujuan dilakukan testing adalah untuk mengetahui performansi dari model yang telah dibentuk. Dengan beberapa parameter pengukuran yaitu akurasi, precision, recall, dan f-measure.

 

Pembobotan
Vector space model merepresentasikan dokumen dengan term yang memiliki bobot. Bobot tersebut menyatakan kepentingan/kontribusi term terhadap suatu dokumen dan kumpulan dokumen. Kepentingan suatu kata dalam dokumen dapat dilihat dari frekuensi kemunculannya terhadap dokumen. Biasanya term yang berbeda memiliki frekuensi yang berbeda. Dibawah ini terdapat beberapa metode pembobotan :

1. Term Frequency
Term frequency merupakan metode yang paling sederhana dalam membobotkan setiap term. Setiap term diasumsikan memiliki kepentingan yang proporsional terhadap jumlah kemunculan term pada dokumen. Bobot dari term t pada dokumen d yaitu :

TF(d,t) = f (d, t)

Dimana f(d,t) adalah frekuensi kemunculan term t pada dokumen d

2. Inverse Document Frequency (IDF)
Bila term frequency memperhatiakan kemunculan term didalam dokumen, maka IDF memperhatikan kemunculan term pada kumpulan dokumen. Latar belakang pembobotan ini adalah term yang jarang muncul pada kumpulan dokumen sangat bernilai. Kepentingan tiap term diasumsikan memilki proporsi yang berkebalikan dengan jumlah dokumen yang mengandung term. Faktor IDF dari term t yaitu :

IDF(t) = log( n / df(t) )

Dimana N adalah jumlah seluruh dokumen, df(t) jumlah dokumen yang mengandung term t.

3. TFIDF
Perkalian antara term frequency dan IDF dapat menghasilkan performansi yang lebih baik. Kombinasi bobot dari term t pada dokumen d yaitu :

TDIF(d,t) = TF(d,t) x IDF(t)

Term yang sering muncul pada dokumen tapi jarang muncul pada kumpulan dokumen memberikan nilai bobot yang tinggi. TFIDF akan meningkat dengan jumlah kemunculan term pada dokumen dan berkurang dengan jumlah term yang muncul pada dokumen.

2. Information Retrieval

 
Information Retrieval (IR) adalah pekerjaan untuk menemukan dokumen yang relevan dengan kebutuhan informasi yang dibutuhkan oleh user. Contoh sistem IR yang paling popular adalah search engine pada World Wide Web. Seorang pengguna Web bisa menginputkan query berupa kata apapun ke dalam sebuah search engine dan melihat hasil dari pencarian yang relevan. Karakteristik dari sebuah sistem IR (Russel & Norvig, 2010) diantaranya adalah:

• A corpus of documents. Setiap sistem harus memutuskan dokumen yang ada akan diperlakukan sebagai apa. Bisa sebagai sebuah paragraf, halaman, atau teks multipage.
• Queries posed in a query language. Sebuah query menjelaskan tentang apa yang user ingin peroleh. Query language dapat berupa list dari kata-kata, atau bisa juga menspesifikasikan sebuah frase dari kata-kata yang harus berdekatan
• A result set. Ini adalah bagian dari dokumen yang dinilai oleh sistem IR sebagai yang relevan dengan query.
• A presentation of the result set. Maksud dari bagian ini adalah tampilan list judul dokumen yang sudah di ranking.

Gambar 2. Proses dari Information Retrieval

Information Retrieval adalah “studi tentang sistem pengindeksan, pencarian, dan mengingat data, khususnya teks atau bentuk tidak terstruktur lainnya.”
[virtechseo.com]

 
“Information Retrieval adalah seni dan ilmu mencari informasi dalam dokumen, mencari dokumen itu sendiri, mencari metadata yang menjelaskan dokumen, atau mencari dalam database, apakah relasional database itu berdiri sendiri atau database hypertext jaringan seperti Internet atau intranet, untuk teks , suara, gambar, atau data “
[Wikipedia]

 
Information Retrieval adalah “bidang di persimpangan ilmu informasi dan ilmu komputer. Berkutat dengan pengindeksan dan pengambilan informasi dari sumber informasi heterogen dan sebagian besar-tekstual. Istilah ini diciptakan oleh Mooers pada tahun 1951, yang menganjurkan bahwa diterapkan ke “aspek intelektual” deskripsi informasi dan sistem untuk pencarian (Mooers, 1951). “
[Hersh, 2003]

 
Secara prinsip, penyimpanan informasi dan penemuan kembali informasi adalah hal yang sederhana. Misalkan terdapat tempat penyimpanan dokumen-dokumen dan seseorang (user) merumuskan suatu pertanyaan (request atau query) yang jawabannya adalah himpunan dokumen yang mengandung informasi yang diperlukan yang diekspresikan melalui pertanyaan user. User bisa saja memperoleh dokumen-dokumen yang diperlukannya dengan membaca semua dokumen dalam tempat penyimpanan, menyimpan dokumen-dokumen yang relevan dan membuang dokumen lainnya. Hal ini merupakan perfect retrieval, tetapi solusi ini tidak praktis. Karena user tidak memiliki waktu atau tidak ingin menghabiskan waktunya untuk membaca seluruh koleksi dokumen, terlepas dari kenyataan bahwa secara fisik user tidak mungkin dapat melakukannya.

 
Information Retrieval merupakan bagian dari computer science yang berhubungan dengan pengambilan informasi dari dokumen-dokumen yang didasarkan pada isi dan konteks dari dokumen-dokumen itu sendiri. Information Retrieval merupakan suatu pencarian informasi (biasanya berupa dokumen) yang didasarkan pada suatu query (inputan user) yang diharapkan dapat memenuhi keinginan user dari kumpulan dokumen yang ada. Sedangkan, definisi query dalam Information Retrieval menurut referensi merupakan sebuah formula yang digunakan untuk mencari informasi yang dibutuhkan oleh user, dalam bentuk yang paling sederhana, sebuah query merupakan suatu keywords (kata kunci) dan dokumen yang mengandung keywords merupakan dokumen yang dicari dalam IRS.

 
Proses yang terjadi di dalam Information Retrieval System terdiri dari 2 bagian utama, yaitu Indexing subsystem, dan Searching subsystem (matching system). Proses indexing dilakukan untuk membentuk basisdata terhadap koleksi dokumen yang dimasukkan, atau dengan kata lain, indexing merupakan proses persiapan yang dilakukan terhadap dokumen sehingga dokumen siap untuk diproses. Proses indexing sendiri meliputi 2 proses, yaitu document indexing dan term indexing. Dari term indexing akan dihasilkan koleksi kata yang akan digunakan untuk meningkatkan performansi pencarian pada tahap selanjutnya.

 
Tahap-tahap yang terjadi pada proses indexing ialah:

1. Word Token,yaitu mengubah dokumen menjadi kumpulan term dengan cara menghapus semua karakter dalam tanda baca yang terdapat pada dokumen dan mengubah kumpulan term menjadi lowercase.
2. Stopword Removal. Proses penghapusan kata-kata yang sering ditampilkan dalam dokumen seperti: and, or, not dan sebagainya.
3. Stemming. Proses mengubah suatu kata bentukan menjadi kata dasar.
4. Term Weighting. Proses pembobotan setiap term di dalam dokumen.

Model IR ada tiga jenis, yaitu :

• Model Boolean : merupakan model IR sederhana yang berdasarkan atas teori himpunan dan aljabar boolean
• Model Vector Space : merupakan model IR yang merepresentasikan dokumen dan query dalam bentuk vektor dimensional
• Model Probabilistic : merupakan model IR yang menggunakan framework probabilistik
Model ruang vektor dan model probabilistik adalah model yang menggunakan pembobotan kata dan perangkingan dokumen. Hasil retrieval yang didapat dari model-model ini adalah dokumen terangking yang dianggap paling relevan terhadap query.
Dalam model ruang vektor, dokumen dan query direpresentasikan sebagai vektor dalam dalam ruang vektor yang disusun dalam indeks term, kemudian dimodelkan dengan persamaan geometri. Sedangkan model probabilistik membuat asumsi-asumsi distribusi term dalam dokumen relevan dan tidak relevan dalam orde estimasi kemungkinan relevansi suatu dokumen terhadap suatu query.

3. HITS Algorithm

Algoritma Hyperlink Induced Topic Search (HITS) Kleinberg memberikan gagasan baru tentang hubungan antara hubs dan authorities. Dalam algoritma HITS, setiap simpul (situs) p diberi bobot hub (xp) dan bobot authority (yp) melalui operasi

yang dalam hal ini nilai xp diperoleh dari jumlah seluruh nilai yq di mana q adalah situs-situs yang menunjuk (mengandung hyperlink) ke situs p (notasi q  p menunjukkan bahwa q menunjuk ke p). Sementara nilai yp diperoleh dari jumlah seluruh nilai xq. Dari operasi tersebut, dapat dilihat bahwa antara hubs dan authorities terdapat sebuah hubungan yang saling memperkuat satu sama lain, yaitu: sebuah hub yang bagus menunjuk ke banyak authorities yang juga bagus, sementara sebuah authority yang bagus ditunjuk oleh banyak hubs yang juga bagus.

Untuk melakukan update secara berkala dari nilai-nilai tersebut, terdapat cara yang lebih singkat dibanding dengan melakukan perhitungan ulang dari rumus yang telah dibahas sebelumnya. Pertama-tama, nomori situs-situs hasil pencarian dengan angka {1,2,…,n} dan tentukan matriks ketetanggaan A yang berukuran n x n dari situs-situs tersebut. Lalu, himpun seluruh nilai x dalam sebuah vektor x = (x1,x2,…,xn) , lakukan hal yang serupa pada seluruh nilai y. Selanjutnya, update nilai x dan y dapat dilakukan melalui operasi

Di bawah ini adalah gambaran keseluruhan dari algoritma HITS.

langkah 1: Kumpulkan sejumlah r situs hasil pencarian sebuah topik yang terletak paling atas (highest-ranked) dari sebuah search engine. Sejumlah r situs ini dikumpulkan dalam sebuah himpunan akar (root) R.

langkah 2: Buatlah sebuah himpunan basis (base) S yang berukuran n, dengan cara memperbesar himpunan R (yaitu, menambah anggota himpunan dengan semua situs yang ditunjuk oleh situs-situs di R dan paling banyak sejumlah d situs tambahan tersebut menunjuk ke situs-situs di R).
langkah 3: Buatlah graf G[S] yang dihasilkan oleh situs-situs pada himpunan S sebagai simpul. Terdapat dua jenis links dalam graf G[S] ini, yaitu: transverse links (links antara situs-situs yang alamat domainnya berbeda) dan intrinsic links (links antara situs-situs yang berdomain sama). Semua sisi yang terbentuk dari intrinsic links dihapus dari graf G[S], sehingga yang tersisa hanyalah sisi-sisi dari transverse links.

langkah 4: Buat matriks ketetanggaan A yang berukuran n x n dan juga matriks transposnya AT. Normalisasikan vektor eigen ε1 dari ATA yang bersesuaian dengan nilai eigen λ1 terbesar.

langkah 5: Temukan elemen-elemen dengan nilai absolut dari hasil normalisasi vektor eigen yang besar. Kemudian, definisikan elemen-elemen tersebut sebagain authorities.

Pada akhirnya, algoritma HITS ini menghasilkan sebuah daftar singkat yang terdiri dari situs-situs dengan bobot hub terbesar serta situs-situs dengan bobot authority terbesar. Yang menarik dari algoritma HITS adalah: setelah memanfaatkan kata kunci (topik yang dicari) untuk membuat himpunan akar (root) R, algoritma ini selanjutnya sama sekali tidak mempedulikan isi tekstual dari situs-situs hasil pencarian tersebut. Dengan kata lain, HITS murni merupakan sebuah algoritma berbasis link setelah himpunan akar terbentuk. Walaupun demikian, secara mengejutkan HITS memberikan hasil pencarian yang baik untuk banyak kata kunci. Sebagai contoh, ketika dites dengan kata kunci ”search engine”, lima authorities terbaik yang dihasilkan oleh algoritma HITS adalah Yahoo!, Lycos, AltaVista, Magellan, dan Excite − padahal tidak satupun dari situs-situs tersebut mengandung kata ”search engine”.

4. Prolog

Sejarah Prolog

– Prolog singkatan dari Programming in Logic.
– Dikembangkan oleh Alain Colmenraurer dan P.Roussel di Universitas Marseilles Perancis, tahun1972.
– Prolog populer di Eropa untuk aplikasi artificial intelligence, sedangkan di Amerika peneliti mengembangkan aplikasi yang sama, yaitu LISP.

Perbedaan Prolog dengan Bahasa Lainnya

– Bahasa Pemrograman yang Umum (Basic, Pascal, C, Fortran):

o diperlukan algoritma/prosedur untuk memecahkan masalah (procedural languange)
o program menjalankan prosedur yang sama berulang-ulang dengan data masukan yang berbeda-beda.
o Prosedur dan pengendalian program ditentukan oleh programmer dan perhitungan dilakukan sesuai dengan prosedur yang telah dibuat.

– Bahasa Pemrograman Prolog :

o Object oriented languange atau declarative languange.
o Tidak terdapat prosedur, tetapi hanya kumpulan data-data objek (fakta) yang akan diolah, dan relasi antar objek tersebut membentuk aturan yang diperlukan untuk mencari suatu jawaban
o Programmer menentukan tujuan (goal), dan komputer menentukan bagaimana cara mencapai tujuan tersebut serta mencari jawabannya.
o Dilakukan pembuktian terhadap cocok-tidaknya tujuan dengan data-data yang telah ada dan relasinya.
o Prolog ideal untuk memecahkan masalah yang tidak terstruktur, dan prosedur pemecahannya tidak diketahui, khususnya untuk memecahkan masalah non numerik.
o Prolog bekerja seperti pikiran manusia, proses pemecahan masalah bergerak di dalam ruang masalah menuju suatu tujuan (jawaban tertentu).
o Contoh : Pembuatan program catur dengan Prolog

Aplikasi Prolog :

– Sistem Pakar (Expert System)
Program menggunakan teknik pengambilan kesimpulan dari data-data yang didapat, layaknya seorang ahli.
Contoh dalam mendiagnosa penyakit
– Pengolahan Bahasa Alami (Natural Languange Processing)
Program dibuat agar pemakai dapat berkomunikasi dengan komputer dalam bahasa manusia sehari-hari, layaknya penterjemah.
– Robotik
Prolog digunakan untuk mengolah data masukanyang berasal dari sensor dan mengambil keputusan untuk menentukan gerakan yang harus dilakukan.
– Pengenalan Pola (Pattern Recognition)
Banyak digunakan dalam image processing, dimana komputer dapat membedakan suatu objek dengan objek yang lain.
– Belajar (Learning)
Program belajar dari kesalahan yang pernah dilakukan, dari pengamataqn atau dari hal-hal yang pernah diminta untuk dilakukan.

Fakta dan Relasi

– Prolog terdiri dari kumpulan data-data objek yang merupakan suatu fakta.
– Fakta dibedakan 2 macam :

o Menunjukkan relasi.
o Menunjukkan milik/sifat.

– Penulisannya diakhiri dengan tanda titik “.”
– Contoh :

Aturan (“Rules”)

– Aturan adalah suatu pernyataan yang menunjukkan bagaimana fakta-fakta berinteraksi satu dengan yang lain untuk membentuk suatu kesimpulan.
– Sebuah aturan dinyakatakan sebagai suatu kalimat bersyarat.
– Kata “if” adalah kata yang dikenal Prolog untuk menyatakan kalimat bersyarat atau disimbolkan dengan “:-“.
– Contoh :

– Setiap aturan terdiri dari kesimpulan(kepala) dan tubuh.
– Tubuh dapat terdiri dari 1 atau lebih pernyataan atau aturan yang lain, disebut subgoal dan dihubungkan dengan logika “and”.
– Aturan memiliki sifat then/if conditional
“Kepala(head) benar jika tubuh (body) benar”.

– Contoh : Silsilah keluarga :

Pertanyaan (“Query”)

– Setelah memberikan data-data berupa fakta dan aturan, selanjutnya kita dapat mengajukan pertanyaan berdasarkan fakta dan aturan yang ada.
– Penulisannya diawali simbol “?-“ dan diakhiri tanda “.”.

– Contoh :

Predikat (“Predicate”)

– Predikat adalah nama simbolik untuk relasi.
– Contoh : ayah(slamet,amin).
Predikat dari fakta tersebut ditulis : ayah(simbol,simbol).
dimana ayah adalah nama predikat, sedangkan slamet dan amin adalah menujukkan argumen.
Sebuah predikat dapat tidak memiliki atau memiliki argumen dengan jumlah bebas. Jumlah argumen suatu predikat disebut aritas (arity).
ayah(nama) …… aritas-nya 1
ayah(nama1,nama2) ….. aritasnya 2
– Syarat-syarat penulisan nama predikat :

o Harus diawali dengan huruf kecil dan dapat diikuti dengan huruf, bilangan atau garis bawah.
o Panjang nama predikat maksimum 250 karakter.
o Tidak diperbolehkan menggunakan spasi, tanda minus, tanda bintang dan garis miring.
Variabel

– Varibel adalah besaran yang nilainya dapat berubah-ubah.

– Tata cara penulisan variabel :

1. Nama varibel harus diawali huruf besar atau garis bawah(_)
2. Nama variabel dapat terdiri dari huruf, bilangan, atau simbol dan merupakan kesatuan dengan panjang maksimum 250 karakter.
3. Nama variabel hendaknya mengandung makna yang berkaitan dengan data yang dinyatakannya.

– Contoh : dari silsilah di atas :

?- ayah(slamet,Anak).
Anak=budi ;
Anak=badu
No

Dari query di atas akan dicari siapakah anak dari ayah yang bernama Slamet. Karena mempunyai relasi yang sama (yaitu ayah), variabel Anak akan mencari nilai dari konstanta suatu fakta/aturan yang sepadan.
Tanda “;” digunakan bila terdapat kemungkinan ada lebih dari satu jawaban.
“No” berarti tidak ada lagi kemungkinan jawaban.

Contoh : dari silsilah di atas :

?- ayah(slamet,X),ayah(X,Y).
X=amin
Y=budi ;
X=amin
Y=badu ;
X=anang
Y=didi ;
X=anang
Y=didi
No

Contoh : Silsilah Keluarga

%% FAKTA */

%%orang tua */
ayah(slamet,amin).
ayah(slamet,anang).
ayah(amin,budi).
ayah(amin,badu).
ayah(anang,didi).
ayah(anang,dadi).
ayah(santoso,bu_amin).
ayah(supardi,bu_anang).
ibu(bu_slamet,amin).
ibu(bu_slamet,anang).
ibu(bu_amin,budi).
ibu(bu_amin,badu).
ibu(bu_anang,didi).
ibu(bu_anang,dadi).
ibu(bu_santoso,bu_amin).
ibu(bu_santoso,bu_anang).

%% ATURAN */

%% Kakek adalah kakek Cucu */

kakek(Kakek,Cucu) :-
ayah(Ayah,Cucu),
ayah(Kakek,Ayah).
kakek(Kakek,Cucu) :-
ibu(Ibu,Cucu),
ayah(Kakek,Ibu).
%% Nenek adalah nenek Cucu */

nenek(Nenek,Cucu) :-
ayah(Ayah,Cucu),
ibu(Nenek,Ayah).
nenek(Nenek,Cucu) :-
ibu(Ibu,Cucu),
ibu(Nenek,Ibu).
%% Nama1 adalah saudara kandung Nama2

saudara_kandung(Nama,Name) :-
ayah(Ayah,Nama),
ayah(Ayah,Name),
ibu(Ibu,Nama),
ibu(Ibu,Name),
Nama \= Name.

%% Sdr1 adalah saudara sepupu Sdr2

saudara_sepupu(Sdr1,Sdr2) :-
ayah(Ayah1,Sdr1),
ayah(Ayah2,Sdr2),
saudara_kandung(Ayah1,Ayah2).

saudara_sepupu(Sdr1,Sdr2) :-
ayah(Ayah,Sdr1),
ibu(Ibu,Sdr2),
saudara_kandung(Ayah,Ibu).

saudara_sepupu(Sdr1,Sdr2) :-
ibu(Ibu,Sdr1),
ayah(Ayah,Sdr2),
saudara_kandung(Ibu,Ayah).

saudara_sepupu(Sdr1,Sdr2) :-
ibu(Ibu1,Sdr1),
ibu(Ibu2,Sdr2),
saudara_kandung(Ibu1,Ibu2).

————————————————————————————————————————–———-—–

www.binus.ac.id