PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

HALAMAN JUDUL

PENGELOMPOKAN ARTIKEL BERBAHASA JAWA DENGAN HIERARCHICAL K MEANS CLUSTERING SKRIPSI Diajukan Untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Komputer Program Studi Teknik Informatika

Disusun Oleh : Aluisius Bachtiar Bayu Saputra 115314076

PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2015

i


HALAMAN JUDUL

JAVANESE LANGUAGE ARTICLES CLUSTERING USING HIERARCHICAL K MEANS

A Final Project Presented as Partial Fulfillment of The Requirements To Obtain Sarjana Komputer Degree In Informatics Engineering Study Program

By: Aluisius Bachtiar Bayu Saputra 115314076

INFORMATICS ENGINEERING STUDY PROGRAM DEPARTMENT OF INFORMATICS ENGINEERING FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2015 ii


HALAMAN PERSETUJUAN SKRIPSI

PENGELOMPOKAN ARTIKEL BERBAHASA JAWA DENGAN HIERARCHICAL K MEANS CLUSTERING

Disusun oleh: Aluisius Bachtiar Bayu Saputra 115314076

Telah disetujui oleh:

Dosen Pembimbing

Sri Hartati Wijono, S.Si., M.Kom.

iii

Tanggal:

Juli 2015


HALAMAN PENGESAHAN SKRIPSI

PENGELOMPOKAN ARTIKEL BERBAHASA JAWA DENGAN HIERARCHICAL K MEANS CLUSTERING

Dipersiapkan dan disusun oleh: Nama

: Aluisius Bachtiar Bayu Saputra

NIM

: 115314093

Telah dipertahankan di depan panitia penguji pada tanggal 23 Juli 2015 dan dinyatakan memenuhi syarat

Susunan Panitia Penguji: Nama Lengkap

Tanda Tangan

Ketua

: JB Budi Darmawan, S.T., M.Sc.

_____________

Sekretaris

: Eko Hari Parmadi, S.Si., M.Kom.

_____________

Anggota

: Sri Hartati Wijono, S.Si., M.Kom.

_____________

Yogyakarta,

Juli 2015

Fakultas Sains dan Teknologi Universitas Sanata Dharma Dekan,

(Paulina Heruningsih Prima Rosa, S.Si., M.Sc) iv


HALAMAN PERSEMBAHAN

Tugas akhir ini saya persembahkan untuk: Tuhan Yesus Yang Maha Baik Bapak dan Ibu tercinta Clothilde Arum ―si Gembul‖ Arzeta von A34 Renata Smile von Mentari Member of Inova Kenel

v


PERNYATAAN KEASLIAN KARYA Saya menyatakan dengan sesungguhnya bahwa skripsi saya tulis ini tidak memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan dalam kutipan dan daftar pustaka sebagaimana layaknya karya ilmiah.

Yogyakarta, 28 Juli 2015 Penulis

Aluisius Bachtiar Bayu Saputra

vi


LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma : Nama

: Aluisius Bachtiar Bayu Saputra

Nomor Mahasiswa

: 115314076

Demi pengembangan ilmu pengetahuan, saya memberikan kepada Perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul : Pengelompokan Artikel Berbahasa Jawa dengan Hierarchical K Means Clustering beserta perangkat yang diperlukan. Dengan demikian saya memberikan kepada Perpustakaan Universitas Sanata Dharma hak untuk menyimpan, me-ngalihkan dalam bentuk media lain, mengelolanya dalam bentuk pangkalan data, mendistribusikan secara terbatas, dan mempublikasikannya di Internet atau media lain untuk kepentingan akademis tanpa perlu meminta ijin dari saya maupun memberikan royalti kepada saya selama tetap mencantumkan nama saya sebagai penulis. Demikian pernyataan ini yang saya buat dengan sebenarnya. Dibuat di Yogyakarta Pada tanggal : 31 Juli 2015 Yang menyatakan

(Aluisius Bachtiar Bayu Saputra)

vii


ABSTRAK

PENGELOMPOKAN ARTIKEL BERBAHASA JAWA DENGAN HIERARCHICAL K MEANS CLUSTERING ABSTRAK Artikel memiliki berbagai jenis topik, sebagai contoh: berita ekonomi, kesehatan, dan sebagainya. Berdasarkan pada jenis artikel di atas ternyata dapat digali informasi yang dapat dimanfaatkan (knowledge discovery). Knowledge discovery pada data teks dapat dilakukan dengan proses awal berupa information retrieval. Proses dari information retrieval bertujuan untuk menemukan ciri dari dokumen, untuk selanjutnya dilakukan analisis keterhubungan antar dokumen dengan menggunakan metode pengelompokan. Sebelum dikelompokkan, data dokumen dari media cetak harus diubah ke bentuk text file. Selanjutnya masuk tahap information retrieval untuk memperoleh ciri dari suatu dokumen. Proses yang dilakukan adalah tokenizing, stop word, stemming, dan weighting. Berdasarkan proses information retrieval yang telah dilakukan, data dikelomopokan menggunakan Hierarchical K Means. Metode Hierarchical K Means terdiri dari dua buah algoritma utama, yaitu K Means dan agglomerative hierarchical clustering (AHC) khususnya teknik single linkage. Single linkage dilakukan mencari centroid yang paling baik. Proses selanjutnya dilakukan K Means dengan menggunakan centroid hasil single linkage, guna menghasilkan cluster terbaik. Setiap hasil cluster dievaluasi dengan metode evaluasi internal, metode yang digunakan adalah sum of square error (SSE). Cluster yang memiliki error minimum diuji kembali dengan evaluasi eksternal, yaitu dengan menggunakan (confusiion matrix). Berdasarkan percobaan pengelompokan yang dilakukan didapatkan pembentukan tiga cluster, yang memiliki error cluster minimum 19,84822 (evaluasi internal) dan memiliki akurasi maksimum 80% (evaluasi eksternal). Pembentukan tiga kelompok ini juga sesuai dengan tujuan yang ingin dicapai dalam tulisan ini, yaitu untuk mendapatkan pengelompokan dari artikel dan dapat membantu untuk mengetahui jenis topik artikel.

viii


ABSTRACT

JAVANESE LANGUAGE ARTICLES CLUSTERING USING HIERARCHICAL K MEANS ABSTRACT There are many kinds of topic article—economy, health, politic, etc. Within those articles, there is useful information that can be found (knowledge discovery). Knowledge discovery on the text data could be initiated by the initial process called information retrieval. The information retrieval process aimed to collect the characteristic of a document in order to analyze the connection between documents by using clustering method. Before conducting the clustering process, document’s data from printed media should be converted into text file. The next step is information retrieval. In this step, the information retrieval collected the characteristic of a document by using tokenizing, stop word, stemming, and weighting. Documents data clustered by using Hierarchical K Means method based on information retrieval. This method consisted of two main algorithms, which are K Means and agglomerative hierarchical clustering (AHC) with single linkage technic. Single linkage would collect the best centroid. In the next process, K Means was initiated using best centroid from AHC to produce best cluster. Every cluster produced would be evaluated by internal evaluation method. The internal evaluation method is sum of square error (SSE). Clusters with minimum error would be retested by external evaluation method using confusion matrix. There are three outcome of clusters based on the clustering trial, which have minimum error 19,84882 (internal evaluation) and maximum accuracy 80% (external evaluation). The forming of these three clusters was corresponded with this paper’s objectives, which are to cluster the article and to find out the type of the article topic.

ix


KATA PENGANTAR

Puji dan syukur penulis panjatkan atas kehadirat Tuhan Yang Maha Esa atas berkat, rahmat serta kasih-Nya sehingga penulis dapat menyelesaikan skripsi yang berjudul ―Pengelompokan Artikel Berbahasa Jawa dengan Hierarchical K Means Clustering‖. Penulisan skripsi ini bertujuan untuk memenuhi

sebagian syarat

memperoleh gelar sarjana komputer program studi S1 jurusan Teknik Informatika Universitas Sanata Dharma. Penulis menyadari bahwa skripsi ini masih jauh dari sempurna oleh sebab itu penulis mengharapkan kritik dan saran yang bersifat membangun dari semua pihak demi kesempurnaan skripsi ini. Selesainya skripsi ini tidak lepas dari peran penting berbagai pihak, sehingga pada kesempatan ini penulis dengan segala kerendahan hati serta rasa hormat mengucapkan terima kasih yang sebesar – besarnya kepada semua pihak yang telah memberikan dukungan baik secara langsung maupun tidak langsung kepada penulis dalam penyusunan skripsi ini hingga selesai. Pada proses penulisan tugas akhir ini, saya ucapkan banyak terima kasih kepada: 1. Tuhan Yesus selaku pembimbing iman dalam hidup yang selalu memberi solusi di atas segala solusi. 2. Ibu Sri Hartati Wijono, S.Si., M.Kom. selaku pembimbing yang memberikan pengarahan serta solusi dalam pengerjaan skripsi ini hingga selesai. 3. Romo Dr. Cyprianus Kuntoro Adi, SJ, MA, M.Sc. yang rela meluangkan waktunya untuk ngopi dan berbagi solusi. 4. Kedua orangtua, Bapak Y. Sumaryono dan Ibu Laurentina Suparmi yang selalu rela berkorban, mendoakan serta memberikan motivasi kepada penulis. 5. Romo Poldo Andreas Situmorang yang senantiasa tulus meluangkan waktunya untuk konsultasi mengenai penelitian ini. 6. Yang tergembul, Clothilde Arum JR yang rela ditinggal pergi pagi pulang pagi.

x


7. Semok Crew (Poldo, Ega, dan Nusa) yang senantiasa kompak dalam kerjasama team, baik siang, malam, maupun subuh menjelang, baik di kampus, base camp, maupun di bar. 8. Seluruh civitas akademika Teknik Informatika angkatan 2011, terutama anggota C++ yang telah berjuang bersama dan saling memberi semangat dan inspirasi. 9. Semua pihak, baik langsung maupun tidak, yang telah membantu dalam proses penyelesaian skripsi ini. Penulis menyadari bahwa masih banyak kekurangan yang terdapat dalam skripsi ini. Saran dan kritik diharapkan untuk perbaikan-perbaikan pada masa yang akan datang. Semoga bermafaat. Penulis menyadari masih banyak kekurangan dalam menyusun skripsi ini, namun penulis tetap berharap skripsi ini bermanfaat bagi pengembangan ilmu pengetahuan.

Yogyakarta, 28 Juli 2015 Penulis

Aluisius Bachtiar Bayu S

xi


DAFTAR ISI

HALAMAN JUDUL................................................................................................ i HALAMAN JUDUL............................................................................................... ii HALAMAN PERSETUJUAN ............................................................................... iii HALAMAN PENGESAHAN ................................................................................ iv HALAMAN PERSEMBAHAN ............................................................................. v PERNYATAAN KEASLIAN KARYA ................................................................ vi ABSTRAK ........................................................................................................... viii ABSTRACT ........................................................................................................... ix KATA PENGANTAR ............................................................................................ x DAFTAR ISI ......................................................................................................... xii DAFTAR GAMBAR ........................................................................................... xiv DAFTAR TABEL ................................................................................................. xv BAB I PENDAHULUAN ....................................................................................... 1 1.1

Latar Belakang ......................................................................................... 1

1.2

Rumusan Masalah .................................................................................... 3

1.3

Batasan Masalah ....................................................................................... 3

1.4

Tujuan ....................................................................................................... 4

1.5

Metodologi Penelitian .............................................................................. 4

1.6

Sistematika Penulisan ............................................................................... 5

BAB II LANDASAN TEORI ................................................................................. 7 2.1 Information Retrieval .................................................................................... 7 2.2 Clustering .................................................................................................... 19 2.3. Evaluasi ...................................................................................................... 30 BAB III METODOLOGI PENELITIAN.............................................................. 32 3.1 Data ............................................................................................................. 32 3.2 Teknik Analisis Data ................................................................................... 32 3.3 Desain User Interface ................................................................................. 42 3.4 Spesifikasi Software dan Hardware ............................................................ 42 BAB IV IMPLEMENTASI DAN ANALISIS HASIL ......................................... 43 4.1 Implementasi ............................................................................................... 43 4.1.1 User Interface........................................................................................... 43

xii


4.1.2 Pengolahan Data....................................................................................... 50 4.2 Analisis Hasil .............................................................................................. 64 BAB V PENUTUP ................................................................................................ 80 5.1.Kesimpulan ................................................................................................. 80 5.2 Saran ............................................................................................................ 82 DAFTAR PUSTAKA ........................................................................................... 83 LAMPIRAN .......................................................................................................... 84

xiii


DAFTAR GAMBAR Gambar 2.1 Proses Information Retrieval (Manning, 2008)................................... 8 Gambar 2.2 Distribusi Zipf (Manning, 2008) ....................................................... 12 Gambar 2.3 Ilustrasi Penentuan Keanggotaan Kelompok Berdasarkan Jarak (Turban dkk, 2005)................................................................................................ 20 Gambar 2.4 Dendrogram ....................................................................................... 24 Gambar 2.5 Dendrogram single linkage untuk 5 obyek data ................................ 29 Gambar 3.1 Diagram Block Proses Clustering. .................................................... 33 Gambar 3.2 Pembobotan tf-idf.............................................................................. 35 Gambar 3.3 Langkah Menghitung Jarak Minimum pada single linkage .............. 38 Gambar 3.4 Langkah Menghitung Menggabungkan Kelompok yang Berdekatan39 Gambar 3.5 Dendrogram ....................................................................................... 39 Gambar 3.6 Tampilan Menu Utama...................................................................... 42 Gambar 4.1 Implementasi User Interface Awal (sebelum proses dilakukan) ...... 44 Gambar 4.2 Implementasi User Interface (setelah dilakukan proses) .................. 44 Gambar 4.3 Button Preprocessing dan Button Proses .......................................... 45 Gambar 4.4 Hasil Kata Unik ................................................................................. 46 Gambar 4.5 Hasil Pengelompokan Terbaik .......................................................... 47 Gambar 4.6 Anggota Cluster dari Pengelompokan Terbaik ................................. 48 Gambar 4.7 Hasil Centroid Terbaik yang Digunakan Pengelompokan ................ 48 Gambar 4.8 Hasil Himpunan Centroid yang Divisualisasikan dengan Dendrogram ............................................................................................................................... 49 Gambar 4.9 Hasil Akurasi Berdasarkan Pengelompokan Terbaik........................ 49 Gambar 4.10 Peringatan/Informasi dari Aksi Menekan Button Preprocessing dan Proses .................................................................................................................... 50 Gambar 4.11 Jumlah Data Dokumen yang Digunakan ......................................... 51 Gambar 4.12 Salah Satu Contoh Data Dokumen .................................................. 51 Gambar 4.13 Hasil Tokenizing .............................................................................. 53 Gambar 4.14 Hasil Stop Word .............................................................................. 54 Gambar 4.15 Hasil Stemming................................................................................ 56 Gambar 4.16 Hasil Indexing ................................................................................. 57 Gambar 4.17 Dendrogram..................................................................................... 59 Gambar 4.18 Centroid Awal ................................................................................. 60 Gambar 4.19 Pembagian Cluster Beserta Anggotanya ......................................... 62 Gambar 4.20 Pembagian Anggotanya Cluster ..................................................... 62 Gambar 4.21 Pemilihan SSE Minimum ................................................................ 63 Gambar 4.22 Hasil Akurasi ................................................................................... 64 Gambar 4.23 Perbandingan Pemotongan Frekuensi Kata .................................... 78 Gambar 4.24 Gambar Tabel Percobaan ................................................................ 79

xiv


DAFTAR TABEL Tabel 2.1 Rule untuk Suffix ................................................................................... 14 Tabel 2.2 Rule untuk Prefix .................................................................................. 14 Tabel 2.3 Rule untuk Infix ..................................................................................... 15 Tabel 2.4 Contoh Data Perhitungan hierarchical clustering ................................ 25 Tabel 2.5 Matriks jarak ......................................................................................... 26 Tabel 2.6 Matriks Jarak Pertama single linkage ................................................... 27 Tabel 2.7 Matriks Jarak Kedua single linkage ...................................................... 27 Tabel 2.8 Matriks Jarak Ketiga single linkage ...................................................... 28 Tabel 3.1 Pembobotan ........................................................................................... 35 Tabel 3.2 Perhitungan Jarak antara Dokumen dengan Centroid........................... 37 Tabel 3.3 Hasil Himpunan Cluster Berdasarkan Pemotongan .............................. 40 Tabel 3.4 Hasil iterasi K Means yang Sudah Stabil .............................................. 41 Tabel 4.1 Percobaan 1 dengan range term frekuensi 0-152 (tanpa pemotongan term) dengan jumlah kata unik 2.358 .................................................................... 66 Tabel 4.2 Hasil Akurasi 1 dengan tf 0-152(tanpa pemotongan) dengan jumlah kata unik 2.358.............................................................................................................. 67 Tabel 4.3 Percobaan 2 dengan range term frekuensi 20-130, dengan jumlah kata unik 236................................................................................................................. 68 Tabel 4.4 Hasil Akurasi 2 dengan tf 20-130 dengan jumlah kata unik 236. ......... 69 Tabel 4.5 Hasil Percobaan 3 dengan c=2 dan range 70-90 dengan jumlah kata unik 11. .......................................................................................................................... 70 Tabel 4.6 Hasil Akurasi 3 c=2 dan range 70-90 dengan jumlah kata unik 11...... 70 Tabel 4.7 Hasil Percobaan 4 dengan c=4 dan range 70-90 dengan jumlah kata unik 11. .......................................................................................................................... 71 Tabel 4.8 Hasil Akurasi 4 c=4 dan range 70-90 dengan jumlah kata unik 11...... 71 Tabel 4.9 Hasil Percobaan 5 dengan c=2 dan range 50-150 dengan jumlah kata unik 40................................................................................................................... 72 Tabel 4.10 Hasil Akurasi 5 c=2 dan range 50-150 dengan jumlah kata unik 40.. 72 Tabel 4.11 Hasil Percobaan 6 dengan c=4 dan range 50-150 dengan jumlah kata unik 40................................................................................................................... 73 Tabel 4.12 Hasil Akurasi 6 c=4 dan range 50-150 dengan jumlah kata unik 40.. 73 Tabel 4.13 Percobaan 7 dengan range term frekuensi 75-85 dengan jumlah kata unik 4..................................................................................................................... 74 Tabel 4.14 Hasil Akurasi 7 dengan tf 75-85 dengan jumlah kata unik 4. ............. 75

xv


1. BAB I PENDAHULUAN

1.1 Latar Belakang Media cetak adalah sarana menuangkan gagasan dan buah pikiran. Salah satu jenis media cetak adalah majalah. Ada beberapa daerah yang memiliki majalah dengan bahasa daerahnya, sebagai contoh: Jaka Lodhang, Mekar Sari, Panjebar Semangat (Bahasa Jawa) dan Cupumanik, Manglé (Bahasa Sunda). Seperti halnya Bahasa Inggris dan Bahasa Indonesia, artikel berbahasa Jawa juga memiliki informasi tersembunyi yang dapat digali dan dimanfaatkan, yang membedakannya adalah proses stemming dan aturan-aturan setiap bahasa. Artikel memiliki berbagai jenis topik, sebagai contoh: berita ekonomi, kesehatan, dan sebagainya. Berdasarkan pada jenis-jenis artikel di atas ternyata dapat digali informasi yang dapat dimanfaatkan sebagai knowledge discovery. Knowledge discovery adalah kegiatan menggali informasi dan pola tersembunyi pada suatu sumber data. Knowledge discovery dengan data teks dapat dilakukan dengan proses information retrieval (Han, 2011). Information retrieval adalah sekumpulan algoritma dan teknologi untuk melakukan pemrosesan, penyimpanan, dan menemukan kembali informasi (tertstruktur) pada suatu koleksi data yang besar (Manning, 2008). Terdapat beberapa tahap yang harus dilakukan dalam information retrieval, secara umum dapat dibagi ke dalam tahap seperti berikut: tokenizing, stopword, stemming, indexing.

1


Pengelompokan dokumen dapat dikerjakan dengan metode tertentu, penelitian ini akan menggunakan salah satu metode clustering yaitu K Means. Pemilihan algoritma K Means karena memiliki banyak keunggulan daripada algoritma lainnya (Baswade, 2013), keunggulan K Means diantaranya: 1. Relatif efisien dengan O (knt) di mana k-jumlah cluster, n-jumlah objek, tjumlah iterasi. 2. Mudah untuk diimplementasikan dan dijalankan. 3. Waktu yang dibutuhkan untuk menjalankan pembelajaran ini relatif cepat. 4. Mudah untuk diadaptasi. Keunggulan yang ditawarkan K Means membuat banyak penelitian yang menggunakan metode tersebut, salah satu diantaranya: Analisa Perbandingan Metode Hierarchical Clustering, K-means dan Gabungan Keduanya dalam Cluster Data (Studi kasus : Problem Kerja Praktek Jurusan Teknik Industri ITS) (Alfina, Santosa, Ridho Barakbah, 2012), Klasterisasi, Klasifikasi dan Peringkasan Teks Berbahasa Indonesia (Raharjo dan Winarko, 2014), serta Deteksi Iris Mata untuk Menentukan Kelebihan Kolesterol Menggunakan Ekstraksi Ciri Moment Invariant dengan K-Means Clustering (Handini Rani, Supriyati,

Khotimah,

2014). Berdasarkan keunggulan keunggulan dan penelitian yang telah dilakukan, maka peneliti memilih metode K Means untuk digunakan sebagai metode pengelompokan data, pada penerapannya akan digunakan Hierarchical clustering untuk mengoptimalkan centroid awal sehingga diperoleh akurasi yang lebih tinggi dibandingkan dengan random K Means dan tentunya proses pencarian dan penggalian informasi dokumen tertentu semakin mudah dan akurat (Arai, 2007).

2


1.2 Rumusan Masalah Bertolak dari uraian latar belakang di atas, maka peneliti mengambil rumusan masalah sebagai berikut: 1. Bagaimana langkah mengelompokkan artikel berbahasa Jawa menurut topiknya? 2. Sejauh mana pendekatan metode hierarchical K Means mampu mengelompokkan artikel berbahasa Jawa dengan akurasi yang baik? 1.3 Batasan Masalah Batasan masalah sangat penting dalam membuat suatu sistem agar implementasinya nanti sesuai dengan yang diharapkan, maka batasan masalah yang akan dibahas dan diaplikasikan dalam penulisan ini yaitu: 1. Data artikel memiliki jumlah 75 dokumen dimana dibatasi sumber yang berasal dari majalah Djaka Lodhang, Praba, dan Mekarsari yang memiliki tiga kelompok topik, yaitu ekonomi, kesehatan, dan pendidikan. 2. Pengelompokan artikel Bahasa Jawa dilakukan secara manual dan belum melibatkan pakar atau ahli di bidang Bahasa Jawa. 3. Artikel menggunakan Bahasa Jawa. 4. Data artikel yang digunakan diubah dalam bentuk dokumen berekstensi .txt. 5. Pengelompokan data artikel menggunakan metode K Means dimana centroid awal ditentukan dengan metode Hierarichal Clustering (Single Lingkage).

3


1.4 Tujuan Penelitian ini diharapkan dapat : 1. Mengetahui kelompok dari artikel dan dapat membantu untuk mengetahui jenis topik artikel pada dokumen berbahasa Jawa. 2. Mengukur

akurasi

dari metode

Hierarichal

K Means

pada

pengelompokan dokumen berbahasa Jawa. 1.5 Metodologi Penelitian Metodologi penelitian yang digunakan dalam penelitian ini adalah studi kasus dengan langkah-langkah sebagai berikut : 1. Studi Pustaka Studi pustaka bertujuan untuk memberikan pengetahuan tentang hal-hal yang berkaitan dengan pengelompokan dokumen. Studi pustaka dilakukan dengan mempelajari buku referensi, jurnal dan artikel yang berkaitan dengan pengelompokan dokumen teks, metode Hierarchical K Means. 2. Pengumpulan Data Pada tahap ini dilakukan pencarian dan pengumpulan data. Data didapat dari majalah berbahasa Jawa Jaka Lodang, Mekarsari dan majalah Praba. 3. Perancangan Pada tahap ini dilakukan perancangan sistem.

4


4. Pembuatan Sistem Berdasarkan hasil analisis dan perancangan sistem, maka tahapan selanjutnya adalah membuat sistem yang akan digunakan. 5. Implementasi dan Pengujian Implementasi sistem dengan cara menjalankan sistem yang telah dibuat dan dilakukan pengujian dengan menampilkan pengelompokan dokumen teks dalam Bahasa Jawa untuk mengetahui pengklasifikasiannya. 6. Evaluasi Menganalisis hasil implementasi dan membuat kesimpulan terhadap penelitian yang telah dikerjakan. 1.6 Sistematika Penulisan Sistematika penulisan yang akan digunakan adalah sebagai berikut : 

BAB I PENDAHULUAN Bab ini akan menjelaskan latar belakang, perumusan masalah, batasan

masalah, tujuan penelitian, manfaat penelitian, dan sistematika penulisan. 

BAB II DASAR TEORI Bab ini akan menjelaskan dasar – dasar teori yang akan digunakan

sebagai landasan utama penelitian dan pembuatan sistem. 

BAB III METODOLOGI Bab ini membahas tentang teknik pengambilan, proses, hingga output sistem.

5




BAB IV IMPLEMENTASI DAN ANALISIS HASIL Bab ini berisi tentang implementasi berdasarkan metodologi yang telah dipaparkan di bab sebelumnya.



BAB V KESIMPULAN DAN SARAN Bab ini berisi tentang kesimpulan dan saran yang diberikan untuk perbaikan sistem sehingga menjadi lebih baik dan bermanfaat.

6


2. BAB II LANDASAN TEORI

2.1 Information Retrieval Information Retrieval merupakan sekumpulan algoritma dan teknologi untuk melakukan pemrosesan, penyimpanan, dan menemukan kembali informasi (tertstruktur) pada suatu koleksi data yang besar (Manning, 2008). Data yang digunakan dapat berupa teks, tabel, gambar maupun video. Sistem IR yang baik memungkinkan pengguna menentukan secara cepat dan akurat apakah isi dari dokumen yang diterima memenuhi kebutuhannya. 2.1.1 Arsitektur Information Retrieval 2.1.1.1 Proses Retrieval Proses information retrieval secara garis besar digambarkan dalam gambar 2.1 di bawah ini:

7


Gambar 2.1 Proses Information Retrieval (Manning, 2008) Secara detail, penjelasan mengenai arsitektur information retrieval terdiri dari beberapa langkah, yaitu : 1. Langkah pertama dalam proses retrieval adalah merancang dan memodelkan bentuk dari data yang akan digunakan untuk keperluan information retrieval. • Penentuan jenis dokumen yang akan digunakan (Semi Structured dan Unstructured) 

Semi–structured (dokumen yang memiliki struktur tree, misalnya dokumen XML) biasanya memberikan tag tertentu pada term – term pada dokumen.

8




Unstructured (dokumen yang tidak memiliki pola, misalnya artikel atau paragraf) proses ini akan dilewati dan term pada dokumen akan dibiarkan tanpa imbuhan tag.

• Operasi dasar yang akan dilakukan terhadap text pada isi dokumen. • Sistem akan membentuk indeks dari text. 2. Indeks merupakan bagian yang sangat kritikal karena akan berpengaruh pada proses pencarian yang cepat dalam volume data yang sangat besar. Struktur indeks dapat berbeda-beda, namun yang paling popular untuk digunakan adalah inverted index. 3. Ketika document data text selesai dibentuk, maka user sudah dapat melakukan pencarian. Langkah-langkah yang harus dilakukan pada pencarian adalah sebagai berikut : 

Pada suatu kebutuhan pencarian data atau kebutuhan informasi pengguna akan merepresentasikan kebutuhan tersebut dengan menggunakan query.



Query Operation akan dilakukan setelah user menginput query.



Proses searching pada query akan menghasilkan retrieved documents.

9




Sebelum data dikembalikan ke user, dokumen yang diretrieved akan diranking berdasarkan kedekatan dokumen dengan query.

2.1.1.2 Text Operation Text Operation berperan penting dalam proses information retrieval, karena seluruh proses yang berhubungan dengan penggalian informasi dari sumber dokumen ataupun teks dilakukan pada proses text operation. Text operation memilki beberapa langkah yang dapat dilakukan di dalam sebuah sistem Information Retrieval, berikut adalah langkahlangkah pada text operatrion: 

Tokenisasi



Penghilangan Stop-word



Stemming



Indexing

2.1.1.2.1 Tokenization Tokenisasi merupakan proses pemenggalan kata dalam suatu dokumen menjadi potongan – potongan kata yang berdiri sendiri (token). Proses ini juga akan menghilangkan tanda baca atau karakter yang melekat pada kata tersebut dan semua kata menjadi huruf kecil (Manning, 2008). Contoh tokenisasi : • Input :Friends, Romans, Countrymen, Lend, Me, Your, Eyes • Output : Friends Romans Countrymen Lend Me Your Eyes

10


Terkadang token dapat dikatakan juga sebagai term atau kata. Pemotongan kumpulan karakter biasanya berdasarkan karakter spasi, namun beberapa permasalahan yang terjadi dalam proses tokenisasi yaitu terdapat beberapa kata yang akan berbeda arti bila dipotong berdasarkan spasi seperti San Fransisco akan memiliki arti yang berbeda bila dipotong menjadi San dan Fransisco. Setiap dokumen dan query direpresentasikan dengan model bag-of-words, yaitu model yang mengabaikan urutan dari kata – kata dan struktur yang ada di dalam dokumen. Dokumen diubah menjadi sebuah wadah yang berisi kata – kata yang independen. 2.1.1.2.2 Penghilangan Stop Word Stop-word didefinisikan sebagai term yang tidak berhubungan (non-relevant) dengan subjek utama dari data meskipun kata tersebut sering muncul di dalam dokumen. Penghilangan stop-word tidak bersifat wajib pada beberapa desain dari modern information retrieval, dimana memliki cara sendiri untuk menyelesaikan masalah kata-kata yang sering digunakan dengan menggunakan data statistik. Contoh stop-word dalam Bahasa Inggris adalah : a, an, the, this, that, these, those, her, his, its, my, our, their, your, all, few, many, several, some, every, for, and, nor, bit, or, yet, so, also, after, although, if, unless, because, on, beneath, over, of, during, beside, dan etc. Contoh stop-word dalam bahasa Indonesia : yang, juga, dari, dia, kami, kamu, aku, saya, ini, itu, atau, dan, tersebut, pada, dengan, adalah, yaitu, ke, tak, tidak, di, pada, jika, maka, ada, pun, lain, saja, hanya, namun, seperti, kemudian, dan dll.

11


Stop-word juga bisa dilakukan dengan memotong kata berdasarkan distribusi kata (Zipf Distrubution). Zipf Distrubution merupakan pembagian/distribusi frekuensi kata, dapat digambarkan seperti gambar 2.2. Pada tahap ini dilakukan pemotongan kata yang memiliki frekuensi sangat tinggi maupun rendah, dengan demikian dapat dikatakan Zipf Distribution dapat memotong batas kata yang optimum untuk memberikan ciri atau key word dari suatu dokumen.

Gambar 2.2 Distribusi Zipf (Manning, 2008)

2.1.1.2.3 Stemming Sebuah kata kerja dalam dokumen sering kali memiliki banyak bentuk atau tata bahasa yang berbeda, untuk mengatasinya dilakukan stemming. Tujuan akhir dari stemming adalah mereduksi kata menjadi kata dasar, proses ini dilakukan dengan pemotongan akhiran dan awalan kata. Hasil dari langkah stemming diperoleh kelompok kata yang mempunyai makna serupa tetapi berbeda wujud sintaktis satu dengan lainnya. Kelompok tersebut dapat direpresentasikan oleh satu kata tertentu. Meskipun demikian stemming dan lemmatisasi memiliki perbedaan dalam

12


cara kerjanya. Stemming melakukan proses pemotongan akhiran dan awalan untuk mencapai tujuan tersebut, sedangkan lemmatisasi melihat penggunaan kata kerja serta analisis morfologi terlebih dahulu sebelum melakukan pemotongan, hasil dari lemmatisasi biasa disebut dengan lemma. Misalkan sebuah kata saw, stemming hanya akan mengembalikan kata see, sedangkan lemmatisasi akan memotongnya ke bentuk see atau saw tergantung pada penggunaan katanya sebagai verb atau noun. Setiap bahasa tentunya memiliki norma stemming yang berbeda, maka tahap stemming untuk Bahasa Jawa tentunya memiliki proses yang berbeda (Ledy Agusta, 2009), berikut adalah langkah stemming untuk Bahasa Jawa: 2.1.1.2.3.1 Aturan / Rule Stemming Sebelum membuat aturan stemming untuk bahasa Jawa, diuraikan terlebih dahulu penggunaan simbol-simbol dalam membuat stemmer rule (Widjono, dkk, 2011) : 1. Aturan substitusi/penghapusan menggunakan tanda =>. ny =>‖‖ ny => s

(ny dihapus) (ny diganti s)

2. Simbol <> digunakan untuk menyatakan tingkat affix yang mempengaruhi urutan pengecekan di algoritma stemming. Rule yang digunakan adalah sebagai berikut :

13


Tabel 2.1 Rule untuk Suffix SUFFIX <1> e=>"",n=>"",a=>"",i=>"",ing=>"", ku=>"",mu=>"" <2> ke=>"", ki=>"",wa=>"", ya=>"",na=>"",ne=>"",en=>"",an=>"",ni=>"",nira=>"", ipun=>"", on=>"u", ning=>"" <3> ake=>"", en=>"i", kna=>"n", kno=>"n", ana=>"", ono=>"", ane=>"", kne=>"", nan=>"", yan=>"", nipun=>"", oni=>"u", eni=>"i" <4> kake=>"n", ken=>"" ,kke=>"",nana=>"",nono=>"", nane=>"", nen=>"",kna=>"",kno=>"", ekne=>"i", onan=>"u",enan=>"i" <5> kake=>"",kken=>"",aken=>"",kke=>"n",enana=>"i",enono=>"i",onen=>"u",enen=>"i",onana=> "u",onono=>"u", ekna=>"i",ekno=>"i",okno=>"u",okna=>"u" <6> ekken=>"i",kaken=>"n",okken=>"u",ekake=>"i",ekke=>"i",okake=>"u",okke=>"u", kaken=>"", kken=>"n" <7> ekaken=>"i",okaken=>"u"

Tabel 2.2 Rule untuk Prefix PREFIX <1>

dipun=>"",peng=>"",peny=>"",pem=>"",pam=>"",pany=>"",pra=>"",kuma=>"",kapi=>"", bok=>"",mbok=>"",dak=>"",tak=>"",kok=>"",tok=>"",ing=>"",ang=>"",any=>"", am=>"", sak=>"", se=>"",su=>"",mang=>"",meng=>"",nge=>"",nya=>"",pi=>"",ge=>"",ke=>"",u=>"", po=>"u",ke=>"u"

<2>

mer=>"",mra=>"",mi=>"",sa=>"",ku=>"",an=>"",ka=>"",ny=>"s",ng=>"k",di=>"",peng=>" k",pang=>"k",pany=>"c", pam=>"p",ke=>"i",mang=>"k",meng=>"k"

<3>

a=>"",k=>"",pam=>"w",pan=>"t", pen=>"t",mang=>"w",meng=>"w", ny=>"c",ng=>""

14


<4>

n=>"t", pan=>"s", pen=>"s",man=>"s",men=>"s"

<5>

pan=>"",pen=>"",man=>"t",men=>"t",n=>""

<6>

pa=>"",pe=>"",man=>"",men=>""

<7>

p=>"",ma=>"",me=>""

<8>

m=>"w"

<9>

m=>"p"

<10>

m=>""

Tabel 2.3 Rule untuk Infix INFIX <1>

gum=>"b",gem=>"b",kum=>"p",kem=>"p"

<2>

kum=>"w", kem=>‖w‖

2.1.1.2.3.2 Algoritma Stemming Algoritma untuk melakukan proses stemming terhadap kata tunggal atau duplikasi. 1. Kata berimbuhan adalah word. Kata sebagai hasil adalah stemW 2. Cek jumlah karakter word, jika < 2. Keluar. 3. Jika word mengandung ―-―, maka pecah kata berdasar ―-― menjadi w1 dan w2. Dan lakukan langkah 4-13 4. w11 = w1 tanpa vokal dan w21 = w2 tanpa vokal. 5. Jika w11 = w21 dan panjang w1=w2 maka lakukan langkah 6-8 6. Jika w2 ada di kamus maka stemW=w2 dan keluar. 7. Jika w2 tidak ada di kamus, w22= hilangkan imbuhan(w2).

15


8. Jika w22 ada di kamus maka stemW=w22, jika tidak stemW=w1-w2 dan keluar. 9. Jika w11 != w21, lakukan langkah 10-13 10. ws11=hilangkan imbuhan(w1) dan ws21 = hilangkan imbuhan(w2). 11. Cek ws21 di kamus, jika ada maka stemW=ws21 dan keluar. 12. Cek ws11 di kamus, jika ada maka stemW=ws11 dan keluar. 13. Jika tidak maka stemW=ws11-ws21 dan keluar. 14. stemW = hilangkan imbuhan(stemW). Cek stemW di dictionary. Jika ada stemW dikembalikan dan keluar. Algoritma untuk menghilangkan afiks pada kata berimbuhan. 1. Kata yang akan dihilangkan imbuhan adalah word. 2. ws1=hapus suffix (word). Cek di dictionary. Jika ada kembalikan kata. 3. ws1s2=hapus suffix (ws1). Cek di dictionary. Jika ada kembalikan kata. 4. ws1i1=hapus infix (ws1). Cek di dictionary. Jika ada kembalikan kata. 5. dws1= pengulangan parsial (ws1). Cek di dictionary. Jika ada kembalikan kata. 6. dws1s2= pengulangan parsial (ws1s2). Cek di dictionary. Jika ada kembalikan kata. 7. wp1=hapus prefix (word). Cek di dictionary. Jika ada kembalikan kata.

16


8. dwp1= pengulangan parsial (wp1). Cek di dictionary. Jika ada kembalikan kata. 9. wp1s1=hapus suffix(wp1). Cek di dictionary. Jika ada kembalikan kata. 10. dwp1s1= pengulangan parsial (wp1s1). Cek di dictionary. Jika ada kembalikan kata. 11. wp1s1s2=hapus suffix (wp1s1). Cek di dictionary. Jika ada kembalikan kata. 12. wp1p2=hapus prefix (wp1). Cek di dictionary. Jika ada kembalikan kata. 13. wp1p2s1=hapus suffix (wp1p2). Cek di dictionary. Jika ada kembalikan kata. 14. wp1p2s1s2=hapus suffix (wp1p2s1). Cek di dictionary. Jika ada kembalikan kata. 15. wi1=hapus infix (word). Cek di dictionary. Jika ada kembalikan kata. 16. wi1s1=hapus suffix (wi1). Cek di dictionary. Jika ada kembalikan kata. 2.1.1.3 Indexing Proses indexing adalah proses yang merepresentasikan document collection ke dalam bentuk tertentu untuk memudahkan dan mempercepat proses pencarian dokumen yang relevan. Pembuatan index dari document collection adalah tugas pokok pada tahapan pre-processing di dalam information retrieval. Efektitifitas dan efisiensi information retrieval dipengaruhi oleh kualitas indeks-nya. Pengindeksan membedakan

17


dokumen satu dengan dokumen yang lain yang berada di dalam satu collection. Indeks dengan ukuran yang kecil dapat memberikan hasil yang kurang baik dan bisa saja beberapa dokumen yang seharusnya relevan terabaikan. Sementara indeks dengan ukuran yang besar memungkinkan ditemukannya dokumen yang tidak relevan dan menurunkan kecepatan pencarian. Pembuatan inverted index harus melibatkan konsep linguistic processing yang bertujuan mengekstrak term-term penting dari dokumen yang direpresentasikan sebagai bag-of-words. Pada tahap indexing, dapat dilakukam pengindeksan terhadap term frekuensi (tf), idf, tf-idf, atau fitur bobot tf-idf dapat dihitung sebagai berikut:

w i , j  (1  log tfi , j )  log10 ( N / df i )

(2.1)

df i = frekuensi dokumen dari kata i = jumlah dokumen yang berisi kata i idfi = inverse document frequency dari kata i, = log10 (N/ df i) (N: jumlah total dokumen). W=weight (bobot kata) 

Contoh pembobotan kata pada dokumen: Diberikan dokumen berisi kata A,B,C dengan frekuensi : A(3), B(2), C(1) Misal, ada koleksi berisi 10,000 dokumen dan frekuensi kata A, B, C untuk seluruh dokumen:

18


A(50), B(1300), C(250) Maka : A: tf = 3; idf = log(10000/50) = 2.3;

tf-idf = 6.9

B: tf = 2; idf = log(10000/1300) = 0.88;tf-idf = 1.77 C: tf = 1; idf = log(10000/250) = 1.6; tf-idf = 1.6 2.2 Clustering 2.2. K Means Clustering K Means clustering merupakan metode yang populer digunakan untuk mendapatkan deskripsi dari sekumpulan data dengan cara mengungkapkan kecenderungan setiap individu data untuk berkelompok dengan individuindividu data lainnya. Kecenderungan pengelompokan tersebut didasarkan pada kemiripan karakteristik tiap individu data yang ada. Ide dasar dari metode ini adalah menemukan pusat dari setiap kelompok data yang mungkin ada untuk kemudian mengelompokkan setiap data individu ke dalam salah satu dari kelompok-kelompok tersebut berdasarkan jaraknya (Turban dkk, 2005). Semakin dekat jarak data individual, sebut saja X1 dengan salah satu pusat dari kelompok yang ada , sebut saja A, maka semakin jelas bahwa X1 tersebut merupakan anggota dari kelompok yang berpusat di A dan semakin jelas pula bahwa X1 bukan anggota dari kelompok-kelompok yang lainnya (ilustrasi dapat dilihat pada gambar 1). Secara kuantitatif hal ini ditunjukkan melalui fakta bahwa d1A yaitu jarak dari X1 ke A mempunyai nilai yang paling kecil jika dibandingankan dengan d1B dan d1C.

19


Gambar 2.3 Ilustrasi Penentuan Keanggotaan Kelompok Berdasarkan Jarak (Turban dkk, 2005) Cara untuk menemukan pusat yang paling sesuai sebagai upaya merepresentasikan posisi dari sebuah kelompok data terhadap kelompok data yang lainnya dilakukan sebuah proses perulangan. Proses perulangan ini dimulai dengan menentukan secara sembarang posisi dari pusat-pusat kelompok yang telah ditetapkan. Selanjutnya ditentukan keanggotaan setiap individu data berdasarkan jarak terpendek terhadap pusat-pusat tersebut. Pada iterasi kedua dan seterusnya dilakukan pembaharuan posisi pusat untuk semua kelompok. Langkah selanjutnya dilakukan pembaharuan keanggotaan untuk setiap kelompok. 2.2.1 Langkah K Means Clustering Metode pengelompokkan K Means pada dasarnya melakukan dua proses yakni proses pendeteksian lokasi pusat cluster dan proses pencarian anggota dari tiap-

20


tiap cluster dan proses pencarian anggota dari tiap-tiap cluster. Proses Algoritma K Means sebagai berikut : 1. Tentukan K sebagai jumlah cluster yang ingin dibentuk. 2. Bangkitkan K centroid (titik pusat cluster) awal secara random. 3. Hitung jarak setiap data ke masing-masing centroid. 4. Setiap data memilih centroid yang terdekat. 5. Tentukan posisi centroid baru dengan cara menghitung nilai rata-rata dari data-data yang terletak pada centroid yang sama. 6. Kembali ke langkah 3 jika posisi centroid baru kurang dari centroids lama. Berdasarkan cara kerjanya Algoritma K Means memiliki karakteristik sebagai berikut : 1. K Means sangat cepat dalam proses clustering. 2. K Means sangat sensitif dalam proses pembangkitan centroid awal secara random. 3. Memungkinkan suatu cluster tidak mempunyai anggota. 4. Hasil clustering dengan K Means bersifat tidak unik. Proses pengelompokkan data ke dalam suatu cluster dapat dilakukan dengan cara menghitung jarak terdekat dari suatu data ke sebuah titik centroid. Rumus untuk menghitung jarak tersebut menggunakan euclidean matrix: (2.3) dimana:

21


g = 2, untuk menghitung jarak euclidean xi , xj adalah dua buah data yang akan dihitung jaraknya p = dimensi dari sebuah data Pembaharuan suatu titik centroid dapat dilakukan dengan rumus berikut:

(2.4) dimana: µk = titik centroid dari cluster ke-K Nk = banyaknya data pada cluster ke-K xq = data ke-q pada cluster ke-K

2.2.2 Hierarchical Clustering Metode agglomerative hierarchical clustering adalah metode yang menggunakan strategi disain bottom-up yang dimulai dengan meletakkan setiap obyek sebagai sebuah cluster tersendiri (atomic cluster) dan selanjutnya menggabungkan atomic cluster – atomic cluster tersebut menjadi cluster yang lebih besar dan lebih besar lagi sampai akhirnya semua obyek menyatu dalam sebuah cluster atau proses berhenti jika telah mencapai batasan kondisi tertentu (Arai ,2007). Sebelum dibentuknya sebuah cluster perlu melalui langkah menghitung jarak antara obyek data untuk mengetahui kemiripan data. Salah satu cara yang

22


banyak digunakan adalah dengan perhitungan euclidean distance. Euclidean distance sendiri adalah: (

)

√(|

|

|

|

|

|

|

| ) (2.5)

dapat disederhanakan dengan: (

)

√∑

(

)

(2.6)

Keterangan: 

adalah jumlah atribut atau dimensi



dan

adalah data

Hierarchical clustering memiliki beberapa cara untuk perhitungan jarak antar cluster, di antaranya adalah single linkage, average linkage, dan complete linkage. Berikut ini adalah pendevinisian perhitungan jarak dengan cara single linkage: Perhitungan dengan teknik single linkage adalah untuk mencari jarak minimum antar cluster. Dengan single linkage jarak antara dua cluster didevinisikan sebagai berikut: (

)

*

+

(2.7)

Keterangan: *

+ adalah jarak antara data

dan y dari masing-masing cluster A dan B.

Berdasarkan perhitungan rumus di atas akan didapatkan jarak antar cluster. Jarak minimum antar data yang ditemukan pertama akan menjadi cluster yang pertama. Perhitungan selanjutnya juga akan dilakukan untuk pembentukan cluster selanjutnya. Berdasarkan hasil perhitungan akan diperoleh dendrogram.

23


2

J a r ak

1,5 1

0,5 0

a

b

c

e

d

f

Data

Gambar 2.4 Dendrogram Penggunaan metode hierarchical clustering untuk mengelompokkan n obyek data adalah sebagai berikut : 1. Hitung Matrik Jarak antar data. 2. Ulangi langkah 3 dan 4 higga hanya satu kelompok yang tersisa. 3. Gabungkan dua kelompok terdekat berdasarkan parameter kedekatan yang ditentukan. 4. Perbarui Matrik Jarak antar data untuk merepresentasikan kedekatan di antara kelompok baru dan kelompok yang masih tersisa. 5. Selesai. Sebagai contoh, terdapat beberapa data yang dapat dilihat pada tabel 2.4 di bawah ini. Data akan dibentuk dengan menggunakan hierarchical clustering dengan perhitungan kemiripan obyek data menggunakan euclidean distance dan perhiutngan jarak cluster dengan single linkage.

24


Tabel 2.4 Contoh Data Perhitungan hierarchical clustering Data

X

Y

A

1

1

B

4

1

C

1

2

D

3

4

E

5

4

Dihitung dengan euclidean distance setiap obyek data tersebut dihitung jaraknya sebagai berikut: (

)

√(|

|

|

| )

(

)

√(|

|

|

| )

(

)

√(|

|

|

| )

(

)

√(|

|

|

| )

(

)

√(|

|

|

| )

(

)

√(|

|

|

| )

(

)

√(|

|

|

| )

(

)

√(|

|

|

| )

(

)

√(|

|

|

| )

(

)

√(|

|

|

| )

Berdasarkan perhitungan tersebut dapat dibentuk matriks jarak seperti seperti pada tabel 2.5.

25


Tabel 2.5 Matriks jarak



A

B

C

D

E

a

0

3

1

3.61

5

b

3

0

3.16

3.16

3.16

c

1

3.16

0

2.83

4.47

d

3.61

3.16

2.83

0

2

e

5

3.16

4.47

2

0

Single linkage Selanjutnya dari tabel 2.5 dapat dilihat jarak obyek data yang paling dekat,

yaitu a dan c, berjarak 1. Kedua obyek data ini menjadi satu cluster pertama. Kemudian untuk menemukan cluster berikutnya dicari jarak antar obyek data dari sisa yang ada (b, d, e) dan berada paling dekat dengan cluster (ac). Untuk pencarian jarak ini pertama digunakan single linkage. 

(

)

*

+

*



(

)

*

+

*



(

)

*

+

*

+ + +

Kemudian baris-baris dan kolom-kolom matriks jarak yang bersesuaian dengan cluster a dan c dihapus dan ditambahkan baris dan kolom untuk cluster (ac), sehingga matriks jarak menjadi seperti berikut ini:

26


Tabel 2.6 Matriks Jarak Pertama single linkage

Ac

Ac

B

d

E

0

3

2.83

4.47

0

3.16

3.16

0

2

B D

0

E

Berdasar pada matriks jarak kedua (Tabel 2.6), dipilih kembali jarak terdekat antar cluster. Ditemukan cluster (de) yang paling dekat, yaitu bernilai 2. Kemudian dihitung jarak dengan cluster yang tersisa, (ac), dan b. 

(

)(



(

)

*

)

*

+ +

*

*

+ +

Kemudian baris-baris dan kolom-kolom matriks jarak yang bersesuaian dengan cluster d dan e dihapus dan ditambahkan baris dan kolom untuk cluster (de), sehingga matriks jarak menjadi seperti berikut ini: Tabel 2.7 Matriks Jarak Kedua single linkage

Ac B De

Ac

b

De

0

3

2.83

0

3.16 0

27


Berdasar pada matriks jarak ketiga (Tabel 2.7), dipilih kembali jarak terdekat antar cluster. Ditemukan cluster (acde) yang paling dekat, yaitu bernilai 2.83. Kemudian dihitung jarak dengan cluster yang tersisa, yaitu b. 

(

)

*

+

*

+

Langkah selanjutnya yaitu menghapus dan menambahkan baris dan kolom untuk cluster (acde) baris-baris dan kolom-kolom matriks jarak yang bersesuaian dengan cluster (ac) dan (de), sehingga matriks jarak menjadi seperti berikut ini: Tabel 2.8 Matriks Jarak Ketiga single linkage

Acde B

acde

B

0

3 0

Proses iterasi perhitungan jarak untuk pembentukan cluster sudah slesai karena cluster sudah tersisa satu. Jadi cluster (acde) dan (b) digabung menjadi satu, yaitu cluster (acdeb) dengan jarak terdekat adalah 3. Berikut ini adalah hasil dendrogram hasil hierarchical clustering dengan single linkage:

28


Gambar 2.5 Dendrogram single linkage untuk 5 obyek data

2.3 Hierarchical K Means Menurut eksperimen yang telah dilakukan, metode K Means sudah digunakan untuk metode pengelompokan data set. Hal itu dapat dibuktikan dengan prosentase eror yang minimal, namun seiring berjalannya waktu, eksperimen tentang clustering lebih berkembang dengan adanya metode Hierarichal K Means yang dapat menentukan centroid awal yang akan digunakan untuk clustering pada metode K Means. Ternyata metode Hierarichal K Means dapat mengatasi pemilihan centroid secara random yang memikiki tingkat eror lebih besar dan dalam penggunannya dianggap kurang praktis karena harus melakukan beberapa eksperimen dalam menentukan centroid awal yang tepat. Harapannya dengan diterapkan Hierarichal K Means dapat meningkatkan akurasi dan menurunkan prosentasi erornya, disebutkan dalam penelitian, ternyata eror pada metode K Means dengan centroid random sebesar 32.5236%, sedangkan dengan metode Hierarichal K Means erornya dapat diminimalisir menjadi 29.7753% (Arai ,2007).

29


Berikut adalah langkah dalam menentukan centoid awal dengan menggunakan hierarchical K Means : 1. Set X ={xi | i =1, ..., r} i setiap data A, dimana A {ai | i= 1, ..., n} dengan n-dimensi vektor. 2. Set K sebagai jumlah _ cluster yang telah ditetapkan. 3. Tentukan p sebagai banyaknya perhitungan 4. Set i = 1 sebagai counter awal 5. Terapkan algoritma K Means. 6. Catat hasil centroid hasil Clustering sebagai Ci = {ij | j = 1, ..., K} 7. Tambahkan i = i + 1 8. Ulangi dari langkah 5 saat i
untuk

menemukan centroid awal dipilih single linkage, karena single linkage penerapannya mudah selain itu ternyata tidak ada perbedaan signifikan dibandingkan dengan average maupun complete linkage (Arai, 2007). 2.3. Evaluasi Berkaitan dengan evaluasi yang digunakan pada penelitian ini, digunakan dua jenis evaluasi. Evaluasi yang digunakan adalah evaluasi internal dan

30


eksternal. Evaluasi yang pertama adalah evaluasi internal sistem, dimana berfungsi untuk mengukur kinerja K Means clustering ini menggunakan Sum Square Erorr (SSE). Evaluasi bertujuan untuk menilai kualitas cluster yang dibuat. Kinerja sistem yang dievaluasi dengan menghitung nilai akurasi, dari perhitungan akurasi akan diketahui sejauh mana metode K Means dapat mengelompokkan dokumen apa topik artikel Berbahasa Jawa. Semakin kecil nilai SSE semakin baik hasil cluster yang dibuat. ∑

∑

||

||

(2.8)

Keterangan: 

adalah jarak data



adalah rata-rata semua jarak data

di indeks di cluster

Evaluasi yang diterapkan berikutnya adalah evaluasi yang berkaitan dengan eksternal sistem, yaitu mengukur akurasi dari pengelompokkan dokumen hasil dari internal evaluasi. Langkah yang dilakukan adalah membandingkan setiap anggota cluster dengan manual pengelompokkan yang sudah dibuat, dalam hal ini sudah ditentukan pembagian cluster dokumen berdasarkan topik (ekonomi, kesehatan, dan pendidikan), dimana masing-masing kelompok beranggotakan 25 dokumen. Metode pengukuran akurasi eksternal yang digunakan adalah confussion matrix. Tabel matriks konfusi merupakan tabel yang digunakan untuk menghitung tingkat akurasi setiap cluster, dimana setiap anggota cluster dibandingkan dengan anggota cluster yang ideal (Prasetyo E, 2012). Perhitungannya adalah jumlah data benar yang dibagi dengan jumlah data.

31


3. BAB III METODOLOGI PENELITIAN Berdasar pada landasan teori yang telah disampaikan pada bab kedua di atas, pada bab ini akan membahas metodologi yang akan digunakan pada skripsi ini. Bab ini berisi diagram blok, data, tatap muka pengguna dan evaluasi. 3.1 Data Data yang digunakan adalah artikel yang bersumber dari majalah berbahasa Jawa Mekarsari, Praba, dan Djaka Lodhang yang terlebih dahulu diubah menjadi dokumen berekstensi .txt . Data yang digunakan berjumlah 75 dokumen, dengan jumlah kata unik yang digunakan 2.358 kata. 3.1.1 Jenis Data Jenis data yang diambil adalah artikel dari majalah Djaka Lodhang, Praba, dan Mekarsari diubah ke bentuk dokumen berkestensi .txt. Data yang dipilih, berasal dari tiga kelompok, yaitu pendidikan, kesehatan, dan ekonomi. 3.2 Teknik Analisis Data Secara umum, sistem yang akan dibangun dalam penelitian ini adalah sebuah sistem dengan fungsi utama untuk melakukan pengelompokan dokumen berbahasa Jawa. Dokumen yang akan dikelompokkan adalah artikel yang diambil dari majalah berbahasa Jawa yaitu Djaka Lodhang, Praba, dan Mekarsari. Proses pengelompokan yang digunakan pada sistem ini adalah metode Hierarchical K Means. Praktiknya, dokumen-dokumen yang akan dikelompokkan dijadikan sebagai arsip digital dengan ekstensi .txt. File teks inilah yang nantinya akan

32


diproses oleh sistem melalui proses tokenizing, stemming, indexing, pembobotan, clustering, percobaan, dan evaluasi. Proses-proses tersebut dapat dilihat pada Gambar 3.1 .

Input Data

IR

Hiearchical Kmeans

Tokenizing

K Means

StopWord

Hierarchical

Output

Akurasi

Hasil Cluster

SSE

(Single Linkage) Confusion Matrix

Stemming K Means Indexing

Gambar 3.1 Diagram Block Proses Clustering. Pada Gambar 3.1 dapat diketahui terdapat input data kemudian dilakukan text operation. Pada proses tersebut didapat dari proses tokenizing untuk memisah kata atau terms kemudian dilakukan normalisasi dengan melakukan stopword, stemming, dan pembobotan data

model.

Langkah

berikutnya

adalah

dengan

melakukan

pengelompokan dengan metode K Means untuk mendapatkan himpunan centroid, dimana proses menghitung jarak dokumen dengan centroid dilakukan menggunakan euclidean distance. Setelah mendapatkan hasil

33


himpunan centroid, langkah selanjutnya adalah melakukan langkah hierarchical single linkage untuk mendapatkan centroid baru sejumlah tiga buah (di rata-rata). Hal ini dilakukan untuk mendapatkan centroid lebih tepat dibandingkan pemilihan centroid random. Langkah berikutnya yaitu memproses pengelompokan dengan metode K Means dengan centroid baru. Hasil dari K Means clustering dievaluasi dengan SSE guna mendapatkan error minimum dan menemukan pembagian cluster yang baik. SSE yang minimum akan membantu dalam dalam mengevaluasi eksternal sistem, yaitu dengan menguji pengelompokan anggota kelompok dari sistem yang kemudian dibandingkan dengan manual cluster, dimana berisi anggota cluster yang ideal.

3.2.1 Text Operation 3.2.1.1 Information Retrieval (Tokenization,Stop Word, Steming, Indexing) Pada tahap information retrieval dilakukan langkah untuk mencapai calon data yang akan dikelompokkan. Langkah-langkah yang dilakukan adalah: 1. Tokenization Proses yang dilakukan pada tahap ini adalah memenggal kata-kata yang ada pada dokumen menjadi kata-kata yang berdiri sendiri. 2. Stop Word Proses yang dilakukan pada tahap ini adalah menghilangkan kata yang tidak memiliki makna (misal: kata hubung dan kata depan), pada tahap ini

34


juga diterapkan Zipf Distrubution untuk menemukan range frekuensi kata yang optimum untuk menemukan key word dari suatu dokumen. 3. Steming Pada tahap ini setiap hasil kata yang sudah tereduksi dari proses stop word dilakukan penghapusan kata menjadi kata dasar yang kemudia dicocokkan ke kamus untuk menghasilkan kata unik. 4. Indexing Pada tahap ini setiap kata unik diberi bobot kata dengan menggunakan rumus weighting (tf.idf) seperti yang sudah dijelaskan di bab sebelumnya.

Gambar 3.2 Pembobotan tf-idf Tabel 3.1 Pembobotan PEMBOBOTAN IDF

TF

IDF

w=tf*idf

Pergok

1

1,77815125

1,77815125

Wong

1

1,77815125

1,77815125

Nandhang

1

1,77815125

1,77815125

Racun

2 1,477121255 1,477121255

Dhahar

2 1,477121255 2,954242509

*log yang digunakan basis 10 pergok: tf = 1; idf = log(60/1) = 1,77815125;

W = 1,77815125

35


wong:

tf = 1; idf = log(60/1) = 1,77815125;

W = 1,77815125

nandhang: tf = 1; idf = log(60/1) = 1,77815125; W = 1,77815125 kemudian hasil pembobotan kata pada dokumen disimpan pada matriks calonData sebagai berikut: ( ) ( ( ) ( )

c

( ) ( )) ( )

dimana w merupakan bobot dari term i sepanjang jumlah kata unik (horizontal) dan yang vertikal sepanjang/sejumlah dokumen.

3.2.1.2 K Means (pertama) Langkah setelah dilakukannya pembobotan adalah melakukan pengelompokan,

pengelompokan

yang

digunakan

adalah

menggunakan K Means untuk mendapatkan himpunan centroid. Hal ini diawali dengan memilih centroid awal = 3 centroid, dipilih tiga centroid dikarenakan sudah dibatasi dengan pengelompokan topik yang diasumsikan menjadi tiga kelompok/cluster, yaitu ekonomi, kesehatan, dan pendidikan. K Means ini dilakukan sebanyak jumlah computation/jumlah computation

1

dilakukannya

menghasilkan

metode tiga

K

centroid

Means

(c=3),

random

yang

digunakan{c1,c3,c5}, computation 2 menghasilkan tiga centroid random yang digunakan {c1,c4,c5}, dan computation 3 menghasilkan tiga centroid random yang digunakan ={c2,c4,c6}. Berdasarkan proses K Means dengan computation=3, maka diperoleh 9 centroid awal.

36


Kemudian dilanjutkan dengan menghitung euclidean distance untuk menghitung jarak masing-masing centroid ke setiap dokumen. 

Contoh menghitung euclidean distance dari dokumen 1 ke dokumen 1 dan dokumen 1 ke dokumen 2:

Tabel 3.2 Perhitungan Jarak antara Dokumen dengan Centroid Pergok(w) Sum doc1

1,778151 1,778151

doc2

0

wdc1 doc1





doc1

0

sum

3,161822 3,161822

doc2

0

0

Sum 3,161822 3,161822

doc2

  dj q   dj  q

W2

0

0

3,161822 3,161822 x 3,161822

1

  dj q   dj  q 



0 3,161822 x 0

0

Lakukan untuk semua himpunan centroid dan kemudian lanjutkan dengan proses hierarchical single linkage.

37


3.2.1.3 Hierarchical Centroid awal Himpunan centroid yang diperoleh dari langkah sebelumnya digunakan dalam proses hierarchical single linkage. Hal pertama yang dilakukan adalah menghitung jarak minimum antar centroid dengan rumus: (3.1) Langkah berikutnya yaitu menggabungkan dua kelompok terdekat berdasarkan jaraknya.

Gambar 3.3 Langkah Menghitung Jarak Minimum pada single linkage Langkah berikutnya yaitu memperbarui matrik jarak antar data untuk merepresentasikan kedekatan di antara kelompok baru dan kelompok yang masih tersisa.

38


Gambar 3.4 Langkah Menghitung Menggabungkan Kelompok yang Berdekatan Berdasarkan proses menggabungkan kelompok terdekat yang sudah dilakukan didapatkah dendrogram sebagai berikut:

Gambar 3.5 Dendrogram

39


Tahap ini bertujuan untuk mendapatkan tiga buah cluster, maka bisa dipotong pada dendogram, sehingga diperoleh pusat cluster sebagai berikut: Tabel 3.3 Hasil Himpunan Cluster Berdasarkan Pemotongan c1

c2

c3

Ab

Cde

f

1,2

3,4,5

6

Langkah di atas merupakan langkah pemilihan centroid dari himpundan centroid hasil single linkage. Centroid yang dipilih adalah: C1 adalah rata-rata dari feature dari indeks 1 dan 2 C2 adalah rata-rata dari feature dari indeks 3,4, dan 5 C3 adalah rata-rata dari feature dari indeks 6 (dapat langsung diambil indeks 6). 3.2.1.4 K Means (kedua) Langkah ini memerlukan centroid baru yang didapat dari proses sebelumnya, maka ditentukan centroid baru sebagai berikut: c1, c2, dan c3. Gunakan rumus euclidean distance untuk menghitung jarah terdekat dokumen dengan centroid awal, misa dokumen 1 dan 2 dari centroid 1(dokumen1)

  dj q   dj  q 

3,161822  1 3,161822 x 3,161822

  dj q   dj  q 



0 3,161822 x 0

0

40


Tabel 3.4 Hasil iterasi K Means yang Sudah Stabil

Lakukan langkah K Means sampai anggota setiap centroid tidak terjadi peubahan, dan ternyata iterasi berhenti di iterasi 1 (2 kali iterasi), sehingga didapatkan pengelompokan dengan anggota cluster sebagai berikut: Kelompok 1 : doc 1 dan 2 Kelompok 2 : doc 3,4, dan 5 Kelompok 3 : doc 6 3.2.1.5 Output Output yang diharapkan pada penelitian ini adalah menampilkan pembagian cluster, sehingga secara visual dapat dilihat hasil pembagian cluster-nya 3.2.1.6 Penghitungan Evaluasi Penelitian ini menggunakan beberapa prosedur uji coba, di antaranya variasi jenis range kata unik yang digunakan dan variasi computation(c) yang merupakan jumlah dilakukan K Means pertama. Berdasarkan prosedur uji coba di atas dihasilkan SSE sebagai akurasi internal sistem di setiap pembentukan cluster-

41


nya. SSE dengan nilai yang paling rendah mengindikasikan bahwa cluster yang terbentuk adalah yang paling baik. Nilai SSE terkecil dipilih sebagai pedoman pengukuran akurasi eksternal sistem, yaitu pencocokan hasil pengelompokan dokumen dengan dokumen yang sebenarnya. Pada pengujian eksternal sistem ini dapat digunakan confussion matrix sebagai metodenya. 3.3 Desain User Interface

Tabel Hasil Pengujian

akurasi Dendrogram

button

button Gambar 3.6 Tampilan Menu Utama

3.4 Spesifikasi Software dan Hardware Untuk proses membuat sistem dan data digunakan software dan hardware sebagai berikut : 1. Software a) Sistem Operasi : Windows 7 Ultimate 32-bit b) Bahasa Pemprograman : Matlab version 8.0.0.783 (R2012b) 2. Hardware a) Processor : Intel(R) Core(TM) i5-2430M CPU @ 2.40GHz b) Memory : 2 GB c) Hardisk : 500 GB

42


4. BAB IV IMPLEMENTASI DAN ANALISIS HASIL

Berdasarkan metodologi yang dijelaskan pada bab sebelumnya, maka penelitian ini dapat diimplementasikan dengan langkah-langkah sebagai berikut: 4.1 Implementasi Implementasi yang diterapkan pada bab ini merupakan penerapan metodologi yang telah dipaparkan pada bab sebelumnya. Implementasi mencakup proses information retrieval, pengelompokan data dengan hierarchical K Means, hinga pengukuran akurasi dari sistem dengan menggunakan SSE dan confussion matrix. Pada tahap selanjutnya diimplementasi dengan ujicoba dan kemudian dianalisis. Analisis implementasi meliputi user interface dan pengolahan data. 4.1.1 User Interface Pembuatan user interface sistem pengelompokan artikel berbahasa Jawa menggunakan sarana yang diberikan oleh Matlab version 8.0.0.783 (R2012b). Desain

user

interface

yang

telah

dipaparkan

pada

bab

sebelumnya

diimplementasikan dan digunakan sebagai sarana untuk melakukan text operation sampai untuk mengetahui akurasi dari pengelompokan data dengan Hierarchical K Means. Sistem dapat langsung menampilkan hasil keseluruhan proses. User interface tersimpan dengan file yang bernama GUI.m dan GUI.fig (lampiran 1 dan 2). Gambar 4.1 dan 4.2 adalah contoh tampilan keseluruhan sistem yang telah dibentuk.

43


Gambar 4.1 Implementasi User Interface Awal (sebelum proses dilakukan)

Gambar 4.2 Implementasi User Interface (setelah dilakukan proses) Berdasarkan gambar di atas dapat dilihat bahwa pengguna hanya perlu menekan button Preprocessing untuk menghasilkan calon data yang siap untuk dilakukan proses pengelompokan. Proses pengelompokan dilakukan setelah pengguna menekan button Proses, setelah button Proses ditekan, maka akan menghasilkan ouput berupa pengelompokan data beserta akurasinya baik itu

44


internal maupun eksternal. Berikut adalah penjelasan lebih lengkapnya mengenai user interface yang dibuat: 

Proses input data sengaja tidak ditampilkan pada user interface karena data yang digunakan sudah tetap dan menempel pada code program. Pengguna cukup untuk menekan button preprocessing untuk melakukan information retrieval pada dokumen dan button proses untuk melakukan proses pengelompokan. Pengguna juga dapat mengetahui proses dari sistem melalui informasi teks iterasi dan melalui message yang memberikan informasi bahwa suatu proses telah dilakukan, dapat dilihat di gambar 4.3 di bawah.

Gambar 4.3 Button Preprocessing dan Button Proses 

Hasil proses yang ditampilkan pada sistem ini adalah: 1. Hasil stemming berupa kata unik. Panel ini berfungsi untuk menampilkan hasil dari yang berupa kata unik dari seluruh dokumen berdasarkan hasil stemming yang telah dilakukan dan diurutkan sesuai abjad. Seperti yang dilihat pada gambar 4.4, kolom A menampilkan frekuensi/jumlah dari kata di indeks i, sedangkan kolom Bb menampilkan kata uniknya.

45


Gambar 4.4 Hasil Kata Unik 2. Hasil dari pengelompokan yang terbaik (nilai SSE minimum) Panel ini berfungsi untuk menampilkan hasil dari pengelompokan terbaik, terbaik di sini berarti memiliki SSE yang minimum. Karena setiap proses diuji dengan range dan computation yang berbeda (masing-masing ada dua jenis) sehingga mengasilkan empat buah indeks yang menyatakan hasil

pengelompokan

(lihat

gambar

4.5).

Hasil

yang

memiliki

pengelompokan terbaik ditandai dengan warna untuk memudahkan pengguna. Secara berurutan, labek yang terdapat pada tabel hasil percobaan dijelaskan sebagai berikut: 

Iterasi merupakan jumlah computation, yaitu berapa kali iterasi proses K Means dilakukan (digunakan 2 dan 4).



CutTF_0 adalah batas bawah dari jumlah frekuensi kata unik yang digunakan (ditentukan batas bawah 50 dan 70).

46




CutTF_1 adalah batas atas dari jumlah frekuensi kata unik yang digunakan (ditentukan batas atas 90 dan 150).



SSE

merupakan

hasil

evaluasi

internal

dari

pengelompokkan yang dilakukan. 

Cls1 merupakan jumlah dari anggota kelompok 1, begitu pula dengan Cls2 dan Cls3 yang merupakan jumlah anggota dari kelompok 2 dan 3.

Gambar 4.5 Hasil Pengelompokan Terbaik

3. Hasil dari pembagian anggota cluster yang terbaik Data dokumen dipetakan berdasarkan pengelompokannya. Pada user interface ini digunakan tabel yang menampung pembagian cluster data awal dengan tabel(lihat gambar 4.6) . Harapannya pengguna dapat dengan mudah mengetahui identitas cluster dari tiap dokumen berdasarkan visualisasinya.

47


Gambar 4.6 Anggota Cluster dari Pengelompokan Terbaik

4. Centroid terbaik yang digunakan Centroid terbaik juga ditampilkan agar pengguna bisa mengetahui centroid yang didapat dari hasil single linkage. Gambar 4.7 menampilkan centroid dengan visualisasi tabel yang berisi tiga buah titik pusat/centroid dimana memiliki feature sepanjang kata unik yang digunakan untuk proses pengelompokan.

Gambar 4.7 Hasil Centroid Terbaik yang Digunakan Pengelompokan

48


5. Hasil dendrogram dari pemilihan himpunan centroid terbaik Hasil dendrogram dapat memvisualisasikan himpunan centroid hasil dari proses K Means (lihatt gambar 4.8). Apabila digambarkan melalui grafik koornidat (x,y), maka koordinat axis (x) berisi pemetaan indeks dari centroid dan y adalah jarak dari tiap centroid. Pertemuan antara garis dendrogram membantu secara visual mengenali dendrogram itu baik atau tidak. Dendrogram yang baik adalah seimbang apabila dilihat secara visual, maka dengan melihatnya saja dapat mengetahui centroid yang dipilih baik atau tidak.

Gambar 4.8 Hasil Himpunan Centroid yang Divisualisasikan dengan Dendrogram 6. Akurasi berdasarkan pengelompokan terbaik Panel akurasi dapat dilihat pada gambar 4.9, panel ini berfungsi untuk menampilkan hasil dari evaluasi pengelompokan dokumen secara eksternal yang dinyatakan dalam skala prosentase

Gambar 4.9 Hasil Akurasi Berdasarkan Pengelompokan Terbaik 49


7. Message Informasi Message Box (lihat gambar 4.10) merupakan feedback dari suatu aksi yang dilakukan pengguna, aksi yang dilakukan adalah menekan button proses dan button preprocessing. Message box membantu pengguna dalam mengetahui suatu proses yang dilakukan sistem.

Gambar 4.10 Peringatan/Informasi dari Aksi Menekan Button Preprocessing dan Proses 4.1.2 Pengolahan Data Data yang digunakan adalah artikel yang bersumber dari majalah berbahasa Jawa Mekarsari, Praba, dan Djaka Lodhang yang terlebih dahulu diubah menjadi dokumen berekstensi .txt . Data yang digunakan berjumlah 75 dokumen. Data yang diambil dibagi menjadi tiga kelompok yang diasumsikan memiliki topik yang bervarisasi. Berikut adalah gambaran data yang digunakan (lihat gambar 4.11 dan 4.12) :

50


Gambar 4.11 Jumlah Data Dokumen yang Digunakan

Gambar 4.12 Salah Satu Contoh Data Dokumen

51


4.1.1.1 Text Operation Tahap awal sebelum data masuk ke pengelompokan dokumen adalah memproses data mentah (berupa dokumen) menjadi matriks numerik berupa hasil pembobotan. Proses ini merupakan langkah dari information retrieval. Tahap information retrieval yang harus dilalui adalah : 1. Tokenizing Proses information retrieval diawali dengan membaca seluruh dokumen kemudian menyimpannya dalam sebuah matriks. Pada saat proses membaca data, tahap tokenizing dilakukan. Hal ini bertujuan untuk memenggal dokumen menjadi kata-kata yang berdiri sendiri. Berikut adalah implementasi dari proses tokenizing dengan menggunakan matlab. Data dokumen dibacauntuk dipisahkan atau dipenggal menjadi kata-kata yang mandiri. Kemudian dinormalisasi dengan lowercase atau membuat semua huruf menjadi kecil. Setelah itu karakter (angka, tanda baca, dll) harus dihapus. Hasil tokenizing kemudian disimpan di dataAwal.txt. Gambar 4.13 merupakan hasil visualisasi dari proses tokenizing for i=1:N %baca dokumen alamatFile=strcat('doc\',int2str(i),'.txt'); fileID = fopen(alamatFile); % Membuka file data = textscan(fileID,'%s'); % Membaca file fclose(fileID); % Menutup file

data=data{1}; % Memasukkan data ke dalam matriks data=regexprep(data,'[<>.,?!"-+=\/:[];_12345678910â”—ï»¿]',' '); % Menghilangkan tanda baca

data=strtrim(data); data(strcmp('',data)) = []; % Menghilangkan cell yang kosong data=lower(data); % Mengubah huruf besar menjadi kecil fid = fopen('Data\dataAwal.txt','w');

52


for row = 1:size(data,1) fprintf(fid, repmat('%s\t',1,size(data,2)-1), data{row,1:end-1}); fprintf(fid, '%s\n', data{row,end}); end fclose(fid);

Gambar 4.13 Hasil Tokenizing

2. Stop Word Proses stop word merupakan langkah lanjutan dari proses Tokenizing. proses ini membuang kata-kata yang tidak memiliki arti seperti halnya kata hubung. Pada tahap ini juga ditambahkan metode distribusi Zipf, yaitu melakukan pemotongan kata yang memiliki frekuensi kemunculan terlalu banyak maupun terlalu sedikit. Hal ini dilakukan untuk mencari ciri atau key word dari suatu dokumen. Pada penelitian ini digunakan dua buah range frekuensi kata. Range pertama (50-150) dan range ke dua (70-90). Batasan ini dipilih karena batasan tersebut paling optimum (berdasarkan ujicoba yang telah dilakukan). Berikut

53


adalah implementasi dari stop word dan penggunaan zipf distribution dimana hasil dari proses tersebut dapat dilihat melalui gambar 4.14. %cek data dengan kamus stop word yaTdk=ismember(matrixGabungan,kamusHubung); [m,n]=size(matrixGabungan); dataTemp=[]; z=1; for j=1:m if yaTdk(j,1)==0 dataTemp{z}=matrixGabungan{j}; z=z+1; end end hasilStem=dataTemp'; %potong frekuensi kata dengan batas atas dan batas bawah %======================================================= for i=1:m if jmlPerKataUnik(i,1)>batasAwal(k,1) && jmlPerKataUnik(i,1)
Gambar 4.14 Hasil Stop Word

54


3. Stemming Berdasarkan proses stop word, didapatlah matriks yang berisi kata-kata, namun kata-kata tersebut harus melalui sebuah tahap lagi yang dinamakan tahap stemming. Pada tahap ini setap kata akan dicek menggunakan stemmer Bahasa Jawa, dimana setiap imbuhan baik itu di awal, tengah, maupun akhir akan dihilangkan sehingga dihasilkan kata dasar. Proses berikutnya adalah pengecekan kata dasar ke kamus Bahasa Jawa, kata dasar yang tidak ada dalam kamus akan dihilangkan. Data awal yang digunakan diambil dari dataHasil.txt yang merupakan hasil dari proses sebelumnya. Setiap kata yang ada pada data awal dicek untuk menemukan kata dasar dengan menggunakan algoritma stememer bahasa Jawa yang diimplementasikan pada stemcoba.pl (terlampir pada lampiran 7). Kata dasar yang terdapat di dalam kamus disimpan dalam matriks hasilStem untuk proses selanjutnya, yaitu pembobotan. Berikiut adalah implementasinya, untuk lebih jelasnya bisa dilihat gambar 4.15 perl('stemcoba.pl'); fileID = fopen('Data\dataHasil.txt'); data = textscan(fileID,'%s'); fclose(fileID); hasilStem=data{1}; hasilStem=regexprep(hasilStem,'-',''); hasilStem=strtrim(hasilStem); hasilStem(strcmp('',hasilStem)) = []; matrixFIle{i} = hasilStem;

55


Gambar 4.15 Hasil Stemming

4. Indexing Data yang dihasilkan proses stemming dilanjutkan dengan proses pembobotan. Proses ini diawali dengan menghitung frekuensi kata dari tiap kata yang pada tiap dokumen, kemudian dilanjutkan dengan mengalikannya dengan idf. Berdasarkan perhitungan tf dan idf , diterapkanlah rumus pembootan/weight (tf.idf). Data hasil dari proses stemming yang telah dibobot mengasilkan sebuah matriks, yang kemudian disebut sebagai calonData yang siap untuk digunakan di tahap clustering. Berikut adalah implementasinya, dimana hasil dari implementasi pembonbotan dapat dilihat pada gambar 4.16. countKataUnik = sum(jmlPerKataUnik); [m,n]=size(jmlPerKataUnik); matrixBobot=zeros(m,n); for i=1:m matrixBobot(i)=log10(countKataUnik/jmlPerKataUnik(i)); end calonData=zeros(size(matrixBobot,1),N);

56


for i=1:N tempMatrixFile=matrixFIle{i}; [m,n]=size(tempMatrixFile); for j=1:m [row,~] = find(ismember(kataUnik,tempMatrixFile(j,1))); calonData(row, i)=matrixBobot(row,1); end end calonDataCell{k}=calonData';

Gambar 4.16 Hasil Indexing

4.1.1.2 Hierarchical K Means Tahapan yang dilakukan setelah pembobotan adalah tahap clustering atau pengelompokan. Tahap ini menjadi dasar untuk menjawab rumusan masalah yang sudah dipaparkan di bab pendahuluan. Implementasi yang dilakukan pada taham ini adalah melakukan pengelompokan dokumen. Hal-hal yang harus dilakukan adalah:

57


1. K Means Pada tahap ini, hasil dari pembobotan, data dikelompokkan dengan menggunakan metode K Means yang implementasinya sudah terlampir pada lampiran 4, yaitu dengan menggunakan fungsi() Kmeans1 yang ada pada Kmeans1.m. Hal pertama yang dilakukan adalah menentukan jumlah cluster. Jumlah cluster yang digunakan pada penelitian ini adalah tiga buah, selanjutnya centroid harus ditentukan terlebih dahulu, pada penelitian ini centroid K Means yang pertama dilakukan secara random atau acak. Setiap term/kata pada setiap dokumen diukur jaraknya dengan masing-masing centoid awal menggunakan euclidean distance. Proses ini dilakukan sampai tidak terjadi perubahan centorid atau letak indeks dari dokumen tidak berubah lagi. Proses K Means pertama dilakukan sampai batas computation (c), dimana c bernilai dua dan empat. Pengulangan K Means pada penelitian ini bertujuan untuk menghasilkan himpunan centroid random yang nantinya menjadi data awal proses Agglomerative Hierarchical Clustering dengan tujuan untuk mengasilkan centroid terbaik. 2. Agglomerative Hierarchical Clustering (Single Linkage) Proses Agglomerative Hierarchical Clustering yang dipilih adalah single linkage. Metode ini dipilih karena penggunaannya menggunakan himpunan centroid sebagai data awal, yang nantinya akan dikelompokkan berdasarkan jarak dengan salah satu Agglomerative Hierarchical Clustering yaitu Single Linkage. Perhitungan jarak yang digunakan adalah

58


dengan rumus euclidean distance. Berdasarkan perhitungan jarak, diambil jarak minimum, karena metode single linkage yang digunakan, maka perhitungan jarak minimum lah yang digunakan . Hasil dari perhitungan jarak minimum antar centroid akan membentuk berupa pasang-pasangan data centroid. Pasangan himpunan centroid dapat dilihat melaui gambar dendrogram 4.17 . Hasil dendrogram dipotong sejumlah kebutuhan centroid. Pada penelitian ini hasil cluster single linkage dilakukan pemotongan guna memperoleh jumlah centroid yang diinginkan, yaitu tiga buah centroid. Pemotongan himpunan cluster harus terlebih dahulu melalui perhitungan rata-rata tiap cluster centroid untuk mendapatkan tiga titik pusat dari himpunan centroid. Hasil keluaran dari tahap ini adalah berupa tiga buah centroid terbaik yang siap digunakan sebagai centroid awal tahap berikutnya. Berikut adalah implementasi yang digunakan dengan memakai variabel clusterSingle yang memanggil fungsi linkage() yang disediakan oleh matlab linkage.m: % Clustering Single clusterSingle=linkage(hasilKmeans,'single','euclidean');

Gambar 4.17 Dendrogram

59


3. K Means Pada tahap ini K Means kembali dilakukan, implementasinya sudah terlampir pada lampiran 4, yaitu dengan menggunakan fungsi() Kmeans1 yang ada pada Kmeans1.m, namun terdapat perbedaan proses yang dilakukan, yaitu berkaitan dengan pemilihan centroid yang sudah ditentukan berdasarkan hasil dari single linkage. Sama halnya dengan proses K Means sebelumnya, iterasi K Means dilakukan sampai tidak terjadi perubahan centorid atau letak indeks dari dokumen tidak berubah lagi. Berikut adalah centroid hasil single linkage yang digunakan sebagai centroid awal(gambar 4.18).

Gambar 4.18 Centroid Awal 4.1.1.3 Output Berdasarkan data yang diolah melalui berbagai macam proses yang sudah dipaparkan di atas, maka didapatlah hasil output berupa hasil terbaik dari pembagian cluster beserta anggota dari pembagian cluster dari setiap dokumen (berdasarkan jumlah computation K Means dan range pemotongan kata unik). Perlu adanya dilakukan evaluasi dari output penelitian ini. Pada langkah selanjutnya akan dibahas perhitungan akurasi baik itu internal maupun eksternal

60


dapat dijelaskan diproses selanjutnya. Implementasi yang dilakukan untuk menghasilkan ouput adalah berikut: Untuk menghasilkan output jumlah pembagian anggota cluster maka variabel yang digunakan untuk menampung adalah jmlObyekCls yang menampung hasil dari proses fungsi Kmeans1(), pada pembentukanCls.m(lampiran 5) begitu juga untuk menampilkan pembagian anggota, dibutuhkan variabel pembagianCls untuk menampung hasil dari proses fungsi Kmeans1(), pada pembentukanCls.m. Hasil visualisasi dari ouput Hierarchical K Means dapat dilihat pada gambar 4.19 dan 4.20 [pembagianCls,cPusat,jmlObyekCls,dist]=Kmeans1(N,calonData,3,3,1); [~,nCd]=size(calonData1); iterasi=0; for i=1:mC for j=1:nCd iterasi=iterasi+1; set(handles.txtIterasi,'String',num2str(iterasi)); [calonData,dist,SSE,jmlObyekCls,pembagianCls,cPusat,clusterSingle] = pembentukanCls(calonData1{1,j},N,jmlCluster,c(i,1)); dataTemp=[c(i,1),batasAwal(j,1),batasAkhir(j,1),SSE,jmlObyekCls(1, 1),jmlObyekCls(2,1),jmlObyekCls(3,1)]; data=[data;dataTemp]; dataTemp=[]; nDist{iterasi,1}=dist; nPembagianCls{iterasi,1}=pembagianCls; nCPusat{iterasi,1}=cPusat; nClusterSingle{iterasi,1}=clusterSingle; nCalonData{iterasi,1}=calonData; pause(3) end end

61


Gambar 4.19 Pembagian Cluster Beserta Anggotanya

Gambar 4.20 Pembagian Anggotanya Cluster 4.1.2 Akurasi Proses menghitung akurasi yang dilakukan pada penelitian ini dibagi menjadi dua jenis, yaitu internal dan eksternal. Penghitungan akurasi yang dilakukan berdasarkan percobaan berbagai jumlah computation (2 dan 4) dan macam pemotongan range frekuensi dari kata (distribusi Zipf), sehingga dihasilkan empat macam percobaan dilakukan. Tahap pengecekan internal diukur dengan menghitung (Sum of Square Error) SSE, dimana SSE terkecil memberikan hasil pengelompokan dokumen

62


yang

paling baik. Implementasi dari SSE dapat dilihat dari lampiran 6 di

hitungSSE.m.

Gambar 4.21 Pemilihan SSE Minimum Dapat dilihat pada gambar 4.21, bahwa SSE yang minimum(diberi warna) harapannya menghasilkan pembagian anggota cluster yang palling baik. Nilai SSE dapat membantu dalam menentukan cluster yang baik. Apabila nilai SSE mendekati 0, maka dapat dikatakan pembagian cluster tersebut baik. Tahap evaluasi eksternal dilakukan pada penelitian ini adalah dengan menggunakan confusion matrix berdasarkan nilai SSE yang minimum

guna

mendapatkan akurasi eksternal terbaik dari tiap cluster, dimana data hasil pengelompokan dihitung dengan membandingkan antara hasil pengelompokan yang dihasilkan sistim dengan pengelompokan data yang ideal. Pengecekan dilakukan setiap cluster hasil sistem dengan cluster ideal. Berdasarkan dari pengecekan setiap anggota cluster antara sistem dengan ideal, terbentuklah diagonal yang menyatakan hasil yang cocok atau sesuai. Hasil dari diagonal dijumlahkan kemudian dibagi dengan sejumlah data. Inilah hasil dari evaluasi internal sistem. Pada penelitian kali ini proses running dilakukan 10 kali dengan empat macam percobaan yang berbeda, sehingga didapatkan empat akurasi yang berbeda . 63


Gambar 4.22 Hasil Akurasi

4.2 Analisis Hasil Implementasi yang telah dipaparkan di atas membantu analisis terhadap pengelompokan artikel berbahasa Jawa sebagaimana judul dari tulisan ini. Analisis ini dilakukan terhadap seluruh artikel berbahasa Jawa, dengan demikian diharapkan dapat diketahui kelompok dari artikel dan mengetahui jenis topik artikel pada dokumen berbahasa Jawa. Seluruh artikel yang telah dikumpulkan diolah melalui tahap information retrieval data awal berupa dokumen diperlakukan beberapa tahap seperti tokenizing untuk memenggal dokumen menjadi kata per kata, stop word untuk menghilangkan tanda baca dan kata-kata yang tidak memiliki arti, serta digunakan distribusi zipf untuk menghilangkan kata yang memiliki frekuensi terlalu rendah dan terlalu tinggi. Tahap berikutnya adalah stemming, yaitu untuk mengubah kata menjadi kata dasar dan kemudian mencocokkan

pada

kamus

apakah

ada

atau

tidak,

kata-kata

yang

diambil/digunakan adalah kata-kata yang ada pada kamus untuk dijadikan kata unik yang kemudian dicek ke data awal untuk menentukan jumlah kemunculan/frekuensi dari kata tersebut. Kata

harus terlebih dahulu diubah

menjadi data numerik melalui proses indexing. Proses indexing berfungsi untuk mencari mana kata yang bisa menjadikan suatu ciri khas dari sebuah dokumen,

64


karena kata yang lebih sering muncul pada suatu dokumen dianggap lebih penting. Untuk mengukur keberhasilan dari penulisan ini adalah dengan menggunakan percobaan. Langkah mengetahuinya adalah dengan melakukan percobaan. Berikut adalah langkah-langkah perobaan yang dilakukan: 1. Menentukan jumlah cluster=3, sesuai dengan topik yang telah ditentukan sebelumnya 2. Memilih computation (c) awal (jumlah dilakukan K Means pertama), ditentukan dua buah parameter percobaan, c=2 dan c=4. Computation dipilih 2 dan 4 karena di penelitian sebelumnya digunakan 10 computation dari 1000, karena pada percobaan ini jumlah data ada 75, maka dipilihlah computation 2 dan 4 agar kurang lebih serupa dengan perbandingan antara jumlah data dengan computation-nya. 3. Menerapkan distribusi zipf dengan memilih beberapa range pemotongan frekuensi kata unik yang digunakan, dengan menentukan range pertama 0-152(tanpa pemotongan frekuensi), range ke dua 20-130, range ke tiga 50-150, range ke empat 7090, dan range ke lima 75-85. 4. Tiap

c

dipasangkan

dengan

masing-masing

range

untuk

mendapatkan akurasi dan errornya. 5. Melakukan masing-masing percoabaan dengan tiap percobaan diulangi 10 kali.

65


Tabel 4.1 Percobaan 1 dengan range term frekuensi 0-152 (tanpa pemotongan term) dengan jumlah kata unik 2.358

No

Hasil Percobaan

Hasil Hasil SSE Akurasi Pembentukan (confusion cluster matrix)

1

20,6 %

>12588

2

17%

>12940

3

21,3%

>11106

4

17,3%

>14128

5

17%

>13948

66


6

23%

>14361

7

17%

>14294

8

20,6%

>12339

9

20,6%

>13233

10

17,3%

>14219

Tabel 4.2 Hasil Akurasi 1 dengan tf 0-152(tanpa pemotongan) dengan jumlah kata unik 2.358 max min rerata

SSE Akurasi 14361 23,00% 11106 17,00% 13315,6 19,17%

67


Tabel 4.3 Percobaan 2 dengan range term frekuensi 20-130, dengan jumlah kata unik 236.

No

Hasil Percobaan


1

38,6 %

>685

2

40%

>730

3

37,3%

>800

4

37,3%

>1030

5

37,3%

>977

68


6

40%

>678

7

36%

>1043

8

38,6%

>763

9

37,3%

>1040

10

38,6%

>954

Tabel 4.4 Hasil Akurasi 2 dengan tf 20-130 dengan jumlah kata unik 236. SSE max min rerata

Akurasi 1043 40,00% 678 36,00% 870 38,10%

69


Tabel 4.5 Hasil Percobaan 3 dengan c=2 dan range 70-90 dengan jumlah kata unik 11. Percobaan compt TF_0 TF_1 SSE(MIN) ke: 1 2 3 4 5 6 7 8 9 10

2 2 2 2 2 2 2 2 2 2

70 70 70 70 70 70 70 70 70 70

90 90 90 90 90 90 90 90 90 90

22,83278 23,4099 22,10818 21,93853 22,39229 22,21632 19,84822 22,91106 22,22598 22,38202

Pembagian Cluster akurasi error c1 c2 c3 29 27 19 20 80 29 20 26 24 76 24 22 29 70,6 29,4 30 24 21 63,5 36,5 13 36 26 24 76 26 19 30 32 68 34 19 22 24 76 24 23 28 20 80 15 32 28 73,3 26,7 14 30 31 77,3 22,7

Tabel 4.6 Hasil Akurasi 3 c=2 dan range 70-90 dengan jumlah kata unik 11.

max min rata-rata

SSE

Akurasi

23,4099 19,84822 22,22653

80% 63,5% 74,07%

70


Tabel 4.7 Hasil Percobaan 4 dengan c=4 dan range 70-90 dengan jumlah kata unik 11. Percobaan ke: 1 2 3 4 5 6 7 8 9 10

Compt TF_0 TF_1 SSE(MIN) 4 4 4 4 4 4 4 4 4 4

70 70 70 70 70 70 70 70 70 70

90 90 90 90 90 90 90 90 90 90

22,3336 20,7682 21,22373 22,06013 23,34443 22,9735 21,8329 18,6674 23,0809 22,9603

Pembagian Cluster akurasi c1 c2 c3 35 17 23 66,6 31 27 17 52 18 27 30 72 32 24 19 54,6 27 25 23 70,6 21 26 28 62,6 18 30 27 58,65 26 20 29 62,6 25 26 24 65,3 25 25 25 70,6

error 33,4 48 28 45,4 29,4 37,4 41,35 37,4 34,7 29,4

Tabel 4.8 Hasil Akurasi 4 c=4 dan range 70-90 dengan jumlah kata unik 11. SSE

Akurasi

max

23,34443

min rata-rata

18,6674 52% 21,92451 63,555%

72%

71


Tabel 4.9 Hasil Percobaan 5 dengan c=2 dan range 50-150 dengan jumlah kata unik 40. Percobaan compt TF_0 TF_1 SSE(MIN) ke: 1 2 3 4 5 6 7 8 9 10

2 2 2 2 2 2 2 2 2 2

50 50 50 50 50 50 50 50 50 50

150 150 150 150 150 150 150 150 150 150

98,5651 98,1921 98,6601 87,2725 106,6736 90,1228 100,9536 96,6804 100,60754 84,40719

Pembagian Cluster akurasi error c1 c2 c3 41 5 29 44 56 21 29 25 40 60 22 29 24 32 68 15 28 32 48 52 17 33 25 54,6 45,4 38 32 5 57,3 42,7 10 37 28 36 64 23 27 25 40 60 28 21 26 44 56 25 37 13 48 52

Tabel 4.10 Hasil Akurasi 5 c=2 dan range 50-150 dengan jumlah kata unik 40.

max min rata-rata

SSE

Akurasi

106,6736 84,40719 96,21349

68% 52% 57,99%

72


Tabel 4.11 Hasil Percobaan 6 dengan c=4 dan range 50-150 dengan jumlah kata unik 40. Percobaan ke: 1 2 3 4 5 6 7 8 9 10

compt TF_0 TF_1 SSE(MIN) 4 4 4 4 4 4 4 4 4 4

50 50 50 50 50 50 50 50 50 50

150 89,773 150 99,9551 150 118,9248 150 94,631719 150 84,7839 150 111,2917 150 94,6199 150 107,8188 150 91,348 150 80,1049

Pembagian Cluster akurasi c1 c2 c3 21 17 37 45,3 29 13 34 58,6 22 41 12 60 19 22 34 66,6 39 28 8 52 12 39 24 62,6 31 27 17 58,6 12 29 34 57,3 22 43 10 44 29 36 10 56

error 54,7 41,4 40 33,4 48 37,4 41,4 42,7 56 44

Tabel 4.12 Hasil Akurasi 6 c=4 dan range 50-150 dengan jumlah kata unik 40. SSE max min rata-rata

118,9248 80,1049 97,32518

Akurasi 66,6% 44% 56,1%

73


Tabel 4.13 Percobaan 7 dengan range term frekuensi 75-85 dengan jumlah kata unik 4.

No

Hasil Percobaan


1

40 %

>29,10

2

48%

>28,04

3

53,3%

>27,94

4

44%

>29,121

5

44%

>29,121

6

46,6%

>27,118

74


7

46,6%

>28,44

8

40%

>26,70

9

42,6%

>26,34

10

45,3%

>27,42

Tabel 4.14 Hasil Akurasi 7 dengan tf 75-85 dengan jumlah kata unik 4. Max Min Rerata

SSE Akurasi 29,121 53,30% 26,34 40,00% 27,934 45,04%

. Berdasarkan hasil tabel percobaan di atas (tabel 4.1-4.14) dapat ditarik kesimpulan sebagai berikut: 1. Pada percobaan 1 yang menggunakan seluruh kata unik berjumlah 2358 kata ternyata didapati akurasi yang sangat rendah (rata-rata 19,17%). Hal ini terjadi karena terlalu banyak kata yang digunakan sehingga terjadi bias dan ciri dari suatu dokumen pun juga

75


membias. Dapat juga dilihat dengan pembagian anggota cluster yang terlalu timpang sehingga dihaslikan SSE yang sangat besar, yaitu mencapai 13315 (menjauhi nol). Kata unik apa saja yang digunakan dapat dilihat di lampiran 8. 2. Pada percobaan 2 yang menggunakan kata unik berjumlah 236 kata dengan frekuensi

20-130 ternyata didapati akurasi lebih baik

daripada percobaan yang pertama (rata-rata akurasi 38,10% dan SSE 870). Hal ini dikarenakan pembiasan ciri dari dokumen sedikit menurun seiiring dengan dibuangnya kata dengan frekuensi yang terlalu rendah dan terlalu tinggi. Kata unik apa saja yang digunakan dapat dilihat di lampiran 9. 3. Pada percobaan 5 dan 6 menggunakan kata unik berjumlah 40 kata dengan frekuensi 50-150 terjadi peningkatan akurasi yang cukup signifikan, yaitu mencapai akurasi rata-rata 57,99% dengan ratarata SSE yang relatif lebih rendah yaitu 96,213. Hal ini dikarenakan frekuensi kata unik yang digunakan lebih menyempit dan mendekati ciri dari dokumen dan kata-kata yang tidak memiliki makna semakin banyak tereduksi. Kata unik apa saja yang digunakan dapat dilihat di lampiran 11. 4. Pada percobaan 3 dan 4 menggunakan kata unik berjumlah 11 kata dengan frekuensi 70-90 . Pada range pemotongan inilah diperoleh akurasi optimum, yaitu mencapai akurasi tertinggi 80% dengan rata-rata SSE yang lebih rendah yaitu 19,85. Pada percobaan ini

76


semakin banyak kata yang terbuang, namun akurasinya justru meningkat. Hal ini dikarenakan frekuensi kata unik yang digunakan semakin menyempit, sehingga dihasilkan kata unik dapat manjadi ciri dari dokumen. Kata unik apa saja yang digunakan dapat dilihat di lampiran 10. 5. Pada percobaan 7 menggunakan kata unik berjumlah 4 kata dengan frekuensi 75-85. Pada range pemotongan ini diperoleh akurasi rata-rata 45,04% dengan rata-rata SSE 27,93. Pada percobaan ini kata yang digunakan lebih sedikit daripada percobaan 3 dan 4, namun akurasi yang dihasilkan justru menurun kembali. Hal ini disebabkan karena kata unik pada range 75-85 terlalu sedikit sehingga kata unik pada range tersebut tidak bisa mewakili dalam merepresentasikan kelompok dokumen yang ada. Kata unik apa saja yang digunakan dapat dilihat di lampiran 12. Berdasarkan hasil percobaan yang telah dilakukan, terlihat jelas pada pada tabel 4.5, dimana pemotongan frekuensi kata 70-90 (11 kata unik) menghasilkan cluster dengan akurasi tertinggi 80% dan memiliki rata-rata SSE 19,85. Dapat disimpulkan bahwa semakin banyak persebaran frekuensi kata yang digunakan, maka error semakin besar (ditunjukkan dengan percobaan 1 dan 2), namun hal ini tidak berlaku pada percobaan dengan frekuensi pemotongan kata antara 75-85. Pada percobaan ini jumlah kata unik yang digunakan semakin sedikit (4 kata), namun akurasi yang dihasilkan justru menurun. Hal ini dikarenakan kata unik pada range

77


75-85 terlalu sedikit sehingga kata unik pada range tersebut tidak bisa mewakili dalam merepresentasikan kelompok dokumen yang ada.

Gambar 4.23 Perbandingan Pemotongan Frekuensi Kata Masuk ke proses pengelompokan, proses pengelompokan dilakukan melalui tiga tahap, yaitu dengan K Means, single linkage, dan K Means kembali. Berdasarkan percobaan yang dilakukan, ternyata computation dengan jumlah 2 relatif lebih baik, karena error yang dihasilkan lebih minimum. Metode hierarchical K Means mengenai optimasi initial centorid ternyata dapat diterapkan pada pengelompokan dokumen berbahasa Jawa. Dibuktikan dengan hasil K Means kedua yang cukup baik karena menggunakan centroid hasil dari hierarchical clustering walaupun hanya dengan sekali percobaan. Setelah dilakukan pengelompokan, maka langkah berikutnya adalah melakukan evaluasi, baik itu internal dan eksternal. Evaluasi internal diukur berdasarkan SSE-nya. SSE yang minimum merupakan pembagian cluster yang terbaik. Dapat dilihat di tabel percobaan 4.1-4.16, dimana SSE minimum menghasilkan pengelompokan dengan jumlah anggota cluster yang relatif seimbang. SSE juga digunakan sebagai parameter pengukuran evaluasi eksternal, dengan mengambil percobaan dengan SSE minimum untuk dihitung pada proses 78


evalusi eksternal dengan menggunakan confussion matrix. Evaluasi eksternal yang dilakukan adalah menghitung perbandingan antara anggota cluster yang tepat atau relevan dengan dokumen dengan kelompok idealnya. Ternyata benar adanya bahwa SSE minimum akan menghasilkan akurasi yang maksimum (lihat gambar 4.21).

Gambar 4.24 Gambar Tabel Percobaan

79


5. BAB V PENUTUP

Bab akhir tulisan ini berisikan tentang kesimpulan dan saran. Kesimpulan berisi tentang hal-hal yang berkaitan dengan pengelompokan artikel berbahasa Jawa. Saran akan memuat hal-hal yang berkaitan tentang pengembangan sistem dalam tulisan ini. 5.1.Kesimpulan Berdasarkan hasil analisis dari implementasi dan percobaan menggunakan data artikel Berbahasa Jawa berjumlah 75 dan k(cluster)=3, dan dengan total kata unik sebelum dilakukan pemotongan (2358 kata), diperoleh kesimpulan sebagai berikut: 1. Percobaan dengan c=2(dilakukan dua kali K Means pertama secara random) dan range term frekuensi 70-90 (11 kata unik) merupakan pengelompokan yang terbaik dimana memiliki akurasi tertinggi (uji eksternal), yaitu 80% dan dengan SSE (uji internal) 19,85. 2. Pada penelitian ini juga dilakukan percobaan lain dengan berbagai macam range pemotongan term frekuensi (tf), sehingga didapatkan hasil sebagai berikut: a. Pada percobaan yang menggunakan seluruh kata unik (2358 kata) ternyata didapati akurasi yang sangat rendah (rata-rata 19,17%). Hal ini terjadi karena terlalu banyak kata yang digunakan sehingga terjadi bias dan ciri dari suatu dokumen pun juga membias. Dapat

80


juga dilihat dengan pembagian anggota cluster yang terlalu timpang sehingga dihaslikan SSE yang sangat besar, yaitu mencapai 13315 (menjauhi nol). b. Pada percobaan yang menggunakan kata unik berjumlah 236 kata dengan frekuensi

20-130

ternyata didapati akurasi lebih baik

daripada percobaan yang tanpa melalui pemotongan term frekuensi (rata-rata akurasi 38,10% dan SSE 870). c. Pada percobaan yang menggunakan kata unik berjumlah 40 kata dengan frekuensi 50-150 terjadi peningkatan akurasi yang cukup signifikan, yaitu mencapai akurasi rata-rata 57,99% dengan ratarata SSE yang relatif lebih rendah yaitu 96,213. Hal ini dikarenakan frekuensi kata unik yang digunakan lebih menyempit dan mendekati ciri dari dokumen dan kata-kata yang tidak memiliki makna semakin banyak tereduksi. d. Pada percobaan yang menggunakan kata unik berjumlah 4 kata dengan frekuensi 75-85. Pada range pemotongan ini diperoleh akurasi rata-rata 45,04% dengan rata-rata SSE 27,93. Pada percobaan ini kata yang digunakan lebih sedikit daripada percobaan yang menggunakan range tf 70-90, namun akurasi yang dihasilkan justru menurun kembali. Hal ini disebabkan karena kata unik pada range 75-85 terlalu sedikit sehingga kata unik pada range tersebut tidak bisa mewakili dalam merepresentasi data yang ada.

81


5.2 Saran Berikut adalah saran yang bisa membantu penelitian ini agar lebih baik dan berkembang nantinya, antara lain: 1. Sebaiknya sistem dapat mengelompokkan topik selain ekonomi, kesehatan, dan pendidikan, dengan asumsi jumlah data juga ditambahkan. 2. Sebaiknya sistem yang dibuat tidak hanya sebatas pengelompokan atikel saja. Sebaiknya sampai pada pembentukan sistem pembantu pengambilan keputusan, dengan demikian sistem yang dibuat kemungkinan akan dapat lebih berdaya guna bagi penelitian yang lainnya. 3. Pengelompokan artikel berdasarkan topik sebaiknya dilakukan oleh pakar di bidang Bahasa Jawa.

82


DAFTAR PUSTAKA Alifina, Tahta., Santosa, Budi., Barakbah, Ridho A.(2012). Analisa Perbandingan Metode Hierarchical Clustering, K-means dan Gabungan Keduanya dalam Cluster Data (Studi kasus : Problem Kerja Praktek Jurusan Teknik Industri ITS). Arai, K., & Barakbah, Ridho.(2007). Hierarchical K-means: an algorithm for centroids initialization for K-means. Reports of the Faculty of Science and Engineering, Saga Univ. Saga University, Vol. 36, No.1. Baswede, Anand., Nalwade, Prakash.(2013). Selection of Initial Centroid for k-Means Algorithm. International Journal of Computer Science and Mobile Computing. Christopher, D. Manning, dkk. (2008). An Introduction to Information Retrieval. Cambridge University Press. Cambrindge. England. Gupta, Ledy.,(2009). Algoritma Stemming untuk Dokumen Teks Bahasa Jawa. Thesis UGM Yogyakarta:UGM Yogyakarta. Han, J., Kamber, M. (2006). Data Mining Concept and Technique, 2nd Ed, Elsevier. Han, Jiawei., Micheline Kamber, Jian Pei. (2012). Data Mining Concepts and Techniques,USA : Morgan Kaufmann. Jiawei Han, M. K. (2011). Data mining Concepts and Techniques. USA: Morgan Kaufmann. Prasetyo, E. (2012). Data Mining: Konsep Dan Aplikasi Menggunakan Matlab. Yogyakarta: Andi. Prasetyo, E. (2014). Data Mining: Pengolahan Data Menjadi Informasi Menggunakan Matlab. Yogyakarta: Andi. Raharjo, Suwanto., & Winarko, Edi.(2014). Klasterisasi, Klasifikasi dan Peringkasan Teks Berbahasa Indonesia. Prosiding Seminar Ilmiah Nasional Komputer dan Sistem Intelijen (KOMMIT 2014). Rani, HA., Supriyati, Endang., Khotimah, Tutik. (2014). Detekso Iris Mata untuk Menentukan Kelebihan Kolesterol Menggunakan Ekstraksi Ciri Moment Invariant dengan K-Means Clustering. Prosiding SNATIF ke-1. Turban, E., dkk. 2005. Decision Support Systems and Intelligent Systems. Yogyakarta: Andi Offset Widjono,S.H.,Darmawan,J.B.,& Adji,S.E. (2011-2012). Pengaruh Stemming untuk Perolehan Informasi dalam Bahasa Jawa. Penelitian Hibah Pekerti DIKTI.

83


LAMPIRAN

Source Code 1. GUI.fig

2. GUI.m function varargout = GUI(varargin) % GUI MATLAB code for GUI.fig % GUI, by itself, creates a new GUI or raises the existing % singleton*. % % H = GUI returns the handle to a new GUI or the handle to % the existing singleton*. % % GUI('CALLBACK',hObject,eventData,handles,...) calls the local % function named CALLBACK in GUI.M with the given input arguments. % % GUI('Property','Value',...) creates a new GUI or raises the % existing singleton*. Starting from the left, property value pairs are

84


% applied to the GUI before GUI_OpeningFcn gets called. An % unrecognized property name or invalid value makes property application % stop. All inputs are passed to GUI_OpeningFcn via varargin. % % *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one % instance to run (singleton)". % % See also: GUIDE, GUIDATA, GUIHANDLES % Edit the above text to modify the response to help GUI % Last Modified by GUIDE v2.5 22-Jun-2015 22:06:08 % Begin initialization code - DO NOT EDIT gui_Singleton = 1; gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton', gui_Singleton, ... 'gui_OpeningFcn', @GUI_OpeningFcn, ... 'gui_OutputFcn', @GUI_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []); if nargin && ischar(varargin{1}) gui_State.gui_Callback = str2func(varargin{1}); end if nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:}); else gui_mainfcn(gui_State, varargin{:}); end % End initialization code - DO NOT EDIT

% --- Executes just before GUI is made visible. function GUI_OpeningFcn(hObject, eventdata, handles, varargin) % This function has no output args, see OutputFcn. % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % varargin command line arguments to GUI (see VARARGIN)

85


% Choose default command line output for GUI handles.output = hObject; clc; axes(handles.logo) imshow('usd.jpg') % Pengaturan awal tabel set(handles.tblHasil,'ColumnWidth',{45,55,55,60,35,35,35,35} ); set(handles.tblHasil,'Data',{}); set(handles.tblPembagianCls,'ColumnWidth',{30}); set(handles.tblPembagianCls,'Data',{}); set(handles.tblCentroid,'ColumnWidth',{45}); set(handles.tblCentroid,'Data',{}); set(handles.tblInfoTeks,'ColumnWidth',{40,75}); set(handles.tblInfoTeks,'RowName',{}); set(handles.tblInfoTeks,'Data',{}); set(handles.tblConfMat,'ColumnWidth',{50}); set(handles.tblConfMat,'Data',{}); set(handles.axCluster,'Visible','off'); % Update handles structure guidata(hObject, handles); % UIWAIT makes GUI wait for user response (see UIRESUME) % uiwait(handles.figure1);

% --- Outputs from this function are returned to the command line. function varargout = GUI_OutputFcn(hObject, eventdata, handles) % varargout cell array for returning output args (see VARARGOUT); % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % Get default command line output from handles structure varargout{1} = handles.output;

86


% --- Executes on button press in btnPreprocessing. function btnPreprocessing_Callback(hObject, eventdata, handles) % hObject handle to btnPreprocessing (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) clc; N=75; fileID = fopen('kamus\hubung.txt'); % Membuka file hubung = textscan(fileID,'%s'); % Membaca file fclose(fileID); % Menutup file kamusHubung=hubung{1}; %baca kamus, insset into matrix fileID = fopen('kamus\kamus.txt'); % Membuka file kamus = textscan(fileID,'%s'); % Membaca file fclose(fileID); % Menutup file dataKamus=kamus{1}; matFile = fullfile(cd, 'hasilPreprocessing.mat'); ada=exist(matFile, 'file'); if ada==1 delete(matFile); end batasAwal=[50;70]; batasAkhir=[150;90]; % handles.batasAwal=batasAwal; % handles.batasAkhir=batasAkhir; [jmlPerKataUnik,matrixFIle,kataUnik,calonData ]=preprocessing(batasAwal,batasAkhir,N,kamusHubung,dataKamus ); save('hasilPreprocessing.mat','jmlPerKataUnik','matrixFIle', 'kataUnik','calonData','batasAwal','batasAkhir'); % handles.jmlPerKataUnik=jmlPerKataUnik; % handles.matrixFIle=matrixFIle; % handles.kataUnik=kataUnik;

87


uiwait(msgbox('Preprocessing selesai.','Peringatan','modal'));

sudah

guidata(hObject, handles);

% --- Executes on button press in btnProses. function btnProses_Callback(hObject, eventdata, handles) % hObject handle to btnProses (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) clc; set(handles.tblHasil,'Data',{}); set(handles.tblPembagianCls,'Data',{}); set(handles.tblCentroid,'Data',{}); set(handles.tblInfoTeks,'Data',{}); set(handles.tblConfMat,'Data',{}); set(handles.axCluster,'Visible','off'); set(handles.txtIterasi,'String','0'); set(handles.txtJmlKataUnik,'String','0'); set(handles.txtAkurasi,'String','0'); % jmlPerKataUnik=handles.jmlPerKataUnik; % matrixFIle=handles.matrixFIle; % kataUnik=handles.kataUnik;

load('hasilPreprocessing.mat','jmlPerKataUnik'); load('hasilPreprocessing.mat','matrixFIle'); load('hasilPreprocessing.mat','kataUnik'); load('hasilPreprocessing.mat','calonData'); load('hasilPreprocessing.mat','batasAwal'); load('hasilPreprocessing.mat','batasAkhir'); N=75; jmlCluster=3; dataTemp=[]; data=[]; % nDist=[]; calonData1=calonData; [mC,nC]=size(c); % [m,n]=size(batasAwal);

88


[~,nCd]=size(calonData1); iterasi=0; for i=1:mC for j=1:nCd iterasi=iterasi+1; set(handles.txtIterasi,'String',num2str(iterasi)); [calonData,dist,SSE,jmlObyekCls,pembagianCls,cPusat,clusterS ingle] = pembentukanCls(calonData1{1,j},N,jmlCluster,c(i,1));

dataTemp=[c(i),batasAwal(j,1),batasAkhir(j,1),SSE,jmlObyekCl s(1,1),jmlObyekCls(2,1),jmlObyekCls(3,1)]; data=[data;dataTemp]; dataTemp=[]; nDist{iterasi,1}=dist; nPembagianCls{iterasi,1}=pembagianCls; nCPusat{iterasi,1}=cPusat; nClusterSingle{iterasi,1}=clusterSingle; nCalonData{iterasi,1}=calonData; pause(3) end end [data,idxMin]=warnaMin(hObject, eventdata, handles, data); set(handles.tblHasil,'ColumnWidth',{45,55,55,60,35,35,35,35} ); set(handles.tblHasil,'Data',data); nCls=N; class=1; class_test=zeros(nCls,1); for i=1:nCls if mod(i,25) == 0 class_test(i,1)=class; class=class+1; if i < nCls class_test(i+1,1)=class; end else class_test(i,1)=class; end end

89


confMat=hitungConfusionmat(class_test,nPembagianCls{idxMin}) ; [M,~]=max(confMat); [dataConfMat]=warnaConfusion(hObject, eventdata, handles,confMat); set(handles.tblConfMat,'ColumnWidth',{50}); set(handles.tblConfMat,'Data',dataConfMat); acc=(sum(M)/sum(confMat(:)))*100; set(handles.txtAkurasi,'String',num2str(acc)); set(handles.axCluster,'Visible','on'); axes(handles.axCluster); warna = nClusterSingle{idxMin}(end-jmlCluster+2,3)-eps; dendrogram(nClusterSingle{idxMin}, 0,'colorthreshold',warna); set(handles.tblPembagianCls,'RowName',{}); set(handles.tblPembagianCls,'ColumnName',{}); set(handles.tblPembagianCls,'Data',nPembagianCls{idxMin}); assignin('base','tblPembagianCls',nPembagianCls{idxMin}); set(handles.tblCentroid,'Data',nCPusat{idxMin});

set(handles.tblInfoTeks,'Data',[num2cell(jmlPerKataUnik),kat aUnik]); set(handles.tblInfoTeks,'ColumnWidth',{40,75}); set(handles.txtJmlKataUnik,'String',num2str(numel(kataUnik)) );

uiwait(msgbox('Proses selesai.','Peringatan','modal')); guidata(hObject, handles); function ConMatrix=hitungConfusionmat(class_test,class_predict) yu=unique(class_test); confMat=zeros(length(yu)); for i=1:length(yu) for j=1:length(yu) confMat(i,j)=sum(class_test==yu(i) class_predict==yu(j)); end end

sudah

&

90


ConMatrix=confMat;

function [data,idxMin]=warnaMin(hObject, eventdata, handles, data) % Konversi matrix dari nomor ke cell array string dataCell = reshape(strtrim(cellstr(num2str(data(:)))), size(data)); % Penentuan yang akan diberi warna dengan fotmat html [m,n]=size(data); sseTemp=data(1,4); % sseTemp=data(1,4); idxMin=0; for i=1:m if ~isnan(data(i,4)) if data(i,4) < sseTemp idxMin=i; sseTemp=data(i,4); dataCell(i,1:7) = strcat(... '<span style="color:#FF0000; fontweight:bold; font-size:12; text-align:center; verticalalign:middle;background-color:#ffffcc;">', ... dataCell(i,1:7), ... ''); else dataCell(i,1:7) = strcat(... '<span style="color:#000000; fontsize:10; text-align:center; vertical-align:middle;">', ... dataCell(i,1:7), ... ''); end end end data=dataCell; function [dataConfMat]=warnaConfusion(hObject, eventdata, handles,dataConfMat) % hObject handle to BtnFigureTable (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % Hint: get(hObject,'Value') BtnFigureTable

returns

toggle

state

of

X=dataConfMat;

91


% Konversi matrix dari nomor ke cell array string XX = reshape(strtrim(cellstr(num2str(X(:)))), size(X)); % Penentuan yang akan diberi warna dengan fotmat html [~,I] = max(X); for i=1:size(I,2) XX(I(i),i) = strcat(... '<span style="color: bold;font-size:14;">', ... XX(I(i),i), ... '

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Recommend Documents