Archive for May, 2014

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.

1. 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.

1. 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.

1. 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 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]

3. HITS ALGHORITM

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 y_q 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 x_q. 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 = (x₁,x₂,…,x_n) , 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.

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 merupakan singkatan dari “Programing In Logic” pertama kali dikembangkan oleh Alain Colmetrouer dan P.Roussel di Universitas Marseilles Prancis tahun 1972. Selama tahun 70an, prolog populer di Eropa untuk aplikasi AI. Sedangkan di Amerika Serikat, para peneliti juga mengembangkan bahasa lain untuk aplikasi yang sama yaitu LISP. LISP mempunyai kelebihan dibandingkan prolog , tetapi LISP lebih sulit dipelajari.

Pada awalnya, Prolog dan LISP sangat lambat dalam eksekusi program dan memakan memori yang besar sehingga hanya kalangan tertentu yang menggunakannya. Dengan adanya Compiler Prolog, kecepatan eksekusi program dapat ditingkatkan, namun Prolog masih dipandang sebagai bahasa yang terbatas (hanya digunakan di kalangan perguruan tinggi dan riset).

Pandangan tersebut tiba-tiba berubah di tahun 1981 pada konverensi internasional I dalam sistem generasi kelima di Tokyo, Jepang. Jepang yang saat itu mengalami kesulitan bersaing dalam pemasaran komputer dengan Amerika Serikat, mencanangkan rencana pengembangan teknologi hardware dan software untuk tahun 1990an. Dan bahasa yang dipilih adalah Prolog.

Sejak saat itu, banyak orang menaruh minat pada prolog dan saat itu telah dikembangkan versi prolog yang mempunyai kecepatan dan kemampuan yang lebih tinggi, lebih murah dan lebih mudah digunakan, baik untuk komputer mainframe maupun komputer pribadi sehingga Prolog menjadi alat yang penting dalam program aplikasi kecerdasan buatan (AI) dan pengembangan sistem pakar (expert sistem).

Perbedaan Prolog dengan Bahasa Pemrograman Lainnya

Hampir semua bahasa pemrograman yang ada pada saat ini seperti Pascal, C, Fortran, disebutprocedural language untuk menggunakan bahasa tersebut diperlukan algoritma atau prosedur yang dibuat untuk menyelesaikan masalah. Program dapat menjalankan prosedur yang sama berulang-ulang dengan data masukkan yang berbeda-beda. Prosedur serta pengendalian program sepenuhnya ditentukan oleh programmer dan perhitungan yang dilakukan sesuai dengan prosedur yang telah dibuat. Dengan kata lain, Pemrograman harus memberi tahu komputer bagaimana komputer harus menyelesaikan masalah.

Prolog mempunyai sifat-sifat yang berbeda dengan bahasa yang disebutkan diatas, prolog disebut sebagai object oriented language atau declarative language. Dalam prolog tidak terdapat prosedur, tapi hanya tampilan data-data object (fakta) yang akan diolah dengan relasi antar object tersebut yang membentuk suatu aturan. Aturan-aturan ini disebut heuristik dan diperlukan dalam mencari suatu jawaban, dengan kata lain, prolog dalam prolog adalah database.
Pemrogram menentukan tujuan (Goal) dan komputer akan menentukan bagaimana cara mencapai tujuan tersebut serta mencari jawabannya. Caranya dengan menggunakan “Formal Reasoning” yaitu membuktikan cocok tidaknya tujuan dengan data-data yang telah ada dan relasinya. Prolog memecahkan masalah seperti yang dilakukan oleh pikiran manusia.
Dengan demikian, Prolog sangat ideal untuk memecahkan masalah yang tidak terstruktur dan yang procedure pemecahannya tidak diketahui, khusunya untuk memecahkan masalah non numeric.
Keampuhan Prolog

Terletak pada kemampuannya dalam mengambil kesimpulan (jawaban) dari data-data yang ada. Karena program dalam bahasa prolog tidak memerlukan prosedur (algoritma). Prolog sangat ideal untuk memecahkan masalah yang tidak terstruktur dan yang prosedur pemecahannya tidak diketahui, khususnya untuk memecahkan masalah non numerik.

Misalnya, dalam pembuatan program catur dengan prolog untuk menentukkan gerakan catur anda tidak perlu menganalisis semua kemungkinan atau menentukkan suatu prosedur tertentu untuk untuk menentukan gerakan berikutnya. Tetapi anda cukup menuliskan aturan umum permainan catur dan lebih baik lagi jika ditambah dengan aturan yang diperoleh dari pengalaman. Prolog akan menentukan sendiri langkah yang akan diambil berdasarkan data-data yang ada saat itu dan aturan-aturan yang diberikan.

Aplikasi Prolog

Prolog digunakan khususnya dibidang kecerdasan buatan (Artificial Intelegent) meliputi bidang:

1. Sistem Pakar (Expert System)

adalah program yang menggunakan teknik pengambilan kesimpulan dari data-data yang didapat seperti yang dilakukan oleh seorang ahli dalam memecahkan masalah. sebagai contoh program mendiagnosa penyakit. Pemakai menentukan tujuan (goal) yaitu penyakit yang diderita, untuk mendapatkan jawaban, program akan memberi pertanyaan yang harus dijawab oleh pemakai program.

2. Pengolahan bahasa alami (Natural Language Processing)

Natural Language Processing adalah program yang dibuat agar pemakai dapat berkomunikasi dengan komputer dalam bahasa manusia sehari-hari. Sebagai contoh adalah Lotus HAL, yaitu program Bantu untuk Lotus 1-2-3 agar dapat menerima perintah bahasa inggris seperti bahasa biasa. Program pengolahan bahasa alami menggunakan teknik AI dalam analisis input bahasa yang dimasukan melalui keyboard, program tersebut berusaha mengidentifikasi sintak, semantik dan konteks yang terkandung dalam suatu kalimat agar bisa sampai pada kesimpulan untuk bisa memberikan jawaban.

3. Robotik

Dalam robotik, Prolog digunakan untuk mengolah data masukan yang berasal dari sensor dan mengambil keputusan untuk menentukan gerakan yang harus dilakukan. Apalagi kalau robot menemukan peristiwa yang tidak diharapkan atau situasi yang berbeda.

4. Pengenalan Pola (Pattern Recognition)

Pengenalan pola banyak diterapkan dalam bidang robotik dan pengolahan citra (image processing). Misalkan, bagaimana komputer dapat membedakan gambar sebuah benda dan gambar benda yang lain, atau sebuah obyek yang berada diatas obyek lain.