PENERAPAN ALGORITMA K-MEANS UNTUK CLUSTERING DOKUMEN E-JURNAL STMIK GI MDP Ernie Kurniawan (
[email protected]), Maria Fransiska (
[email protected]) Tinaliah (
[email protected]), Rachmansyah (
[email protected]) Program Studi Teknik Informatika STMIK GI MDP Abstrak : Banyaknya dokumen jurnal yang terus bertambah membuat pengelompokkan dokumen jurnal semakin sulit karena memperlambat pencarian dokumen. Oleh karena itu, pengelompokkan dokumen jurnal diperlukan untuk mempercepat pencarian yang diperoleh dari query yang diinput pengguna dan menghasilkan hasil yang relevan dengan query tersebut. Penelitian ini bertujuan untuk menerapkan algoritma K-Means dalam mengelompokkan dokumen jurnal yang sesuai dengan query yang diinput sehingga menghasilkan kelompok-kelompok yang sesuai dengan query. Dalam prosesnya dilakukan tahap preprocessing yaitu tokenization, penghilangan stopwords dan stemming. Selanjutnya, pengelompokkan dokumen dilakukan dengan algoritma K-Means menggunakan bahasa pemrograman PHP dengan menggunakan proses stemming dan non-stemming untuk mengetahui kerelevanan hasil yang diperoleh dari masing-masing proses. Hasil dari pengelompokkan dokumen dengan menggunakan proses stemming menghabiskan waktu lebih banyak dibandingkan dengan proses non-stemming karena proses stemming harus menemukan terlebih dahulu kata dasar dari query yang diinput sedangkan dalam proses non-stemming tidak diperlukan proses pencarian kata dasar, hasil pengelompokan menggunakan proses stemming lebih relevan dibandingkan dengan pengelompokan dengan menggunakan proses non-stemming, pengujian dengan menggunakan dataset yang sedikit membuat pengembang kesulitan dalam membedakan hasil kelompok antara proses stemming dan proses non-stemming, penentuan titik pusat awal sangat berpengaruh terhadap jumlah cluster yang terbentuk serta pengelompokan dokumen ini juga dapat membantu pengguna menemukan dokumen yang relevan sesuai dengan query yang diinput. Kata Kunci : Clustering, K-Means, stemming, PHP Abstract : The amount of journal documents which increase continously make the classified of journal document more difficult is slow down the document research. Therfore the classification of journal document is needed to speed the research which get from query that input by the user and produce a relevant result from the query. The purpose of the research is to imply K-Means algorithm in classify the journal document based on the query which already input so produce the groups as query. In that process, there is preprocessing step which is call tokenization, the omit of stopwords and stemming. Next, the classification of documents are done with K-Means algorithm use PHP programming language with use stemming and nonstemming process to know the relevance result with get from each process. The result from document classification with use stemming process spend more times compare with non-stemming process because the stemming process should be found the basic words of query which already input. While in non-stemming process isn't needed of the basic words research process. The result of this classification with use stemming process is more relevant compare with the classification by non-stemming process. The testing with use a little dataset make the developer find the difficulty in comparing the result of groups between stemming and non-stemming process, the determination of the beginning of center is very influence to the amount of cluster which is formed beside that the classification of this document can help the user find the relevant document as suit as query which is input. Keywords : Clustering, K-Means, stemming, PHP
Hal - 1
1
PE ENDAHULU UAN
Peerkembangan n teknologi informasi dan d kompuuter saat inii sangat ceppat, kebutuhhan pengguuna akan tek knologi kompputer sangatllah dibutuhhkan. Saat ini banyakk pengembaang membuuat teknologi baru yang beermanfaat bukkan hanya sebagai hibu uran melainkaan juga sebaggai media komunikasi yang berbasiis visual sepeerti websitee. Media website berrisi bermacaam inform masi seperti berita, iklan, permainan p seerta inform masi lain sangat membantuu para pengguuna kompuuter. Selain iklan secara online, dalam websitee juga biisa dimasukkkan berbaggai inform masi yang berkaitan dengan dunnia pendiddikan. Baanyak perguruan tinnggi memiilih mengggunakan med dia web untuuk memberikkan inform masi secara langsung kepada para mahasiiswanya den ngan cukup mengakses m link websitee perguruan tinggi terseebut. Teknoloogi websitee dapat disisipkan dengann menggunakkan perpustakaan digitaal yang di dallamnya terdappat pengelompokan do okumen berbbasis web bagi mahasiiswa yang in ngin mencarii buku atauppun jurnal. Hal ini dissebabkan karrena mahasiswa cenderrung lebih suk ka memilih buku yang diccari dengann menggunak kan komputeer dibandingkkan harus ke perpustak kaan untuk mengecek data d buku teersebut. Peengelompokaan dokumen berbasis web w merupaakan sebuah situs web diimana di dalam web teersebut terdaapat sistem yang dibenttuk berdasaarkan pengeelompokan dokumen d sesuuai dengann kategori yan ng dibuat oleeh pengembanng. Pengellompokan dok kumen memiliki teknik yaang lebih spesifik s untuk k dokumen seperti s ekstraaksi judul otomatis dan n pencarian informasi yaang cepat atau filtering g. Misalnya, mesin penccari web seering memberrikan ribuan halaman dalam menanggapi permiintaan penggguna, sehinggga sulit bagi pengguna untuk mencari attau mengiddentifikasi infformasi yang relevan. Dengan adany ya pengelomppokan dokum men ini, maahasiswa han nya perlu menngetikkan juddul tugas akhirnya, a lalu u secara otom matis web akkan membeerikan dokumen-dokumeen yang miirip dengann judul yang dimasukan aggar tidak terjadi penelittian dengan judul yang sama. Hal ini dikarennakan di dalam website terdapat t sebuuah algoritm ma yang dapaat mengelomppokan dokum men
berddasarkan kesaamaan antar dokumen terrsebut atauu berdasarkan kelompoknyya. Dengan addanya sebuaah sistem yang berffungsi untukk mengelom mpokan dokkumen jurnnal ini, dapat memperm mudah mahaasiswa dalaam pencariaan jurnal dengan tiingkat kem miripan yang paling sesuuai dengan query yangg diberikan oleh penggunaa. 2
LANDASA AN TEORI
2.1 Clustering Clusteringg adalah suaatu metode untuk pengggelompokann dokumen dimana dokkumen dikeelompokan deengan konten untuk menguurangi ruanng pencariaan yang diperlukan d d dalam merrespon suatuu query. Misalnya M kooleksi dokuumen yang berisi b dokumeen-dokumen medis m dan hukum dappat dikelompookkan sedem mikian rupaa sehingga semua dokumen medis m ditem mpatkan dallam satu clluster dan semua s dokuumen hukum m ditempattkan dalam satu clusster hukum (G Grossman, David A. dan Ophir Frieeder, 2004, h.105). 2.2 Algoritma K-Means K Algoritm ma K-Meaans meruppakan m an parameter input algooritma yang membutuhka sebaanyak k dan membagi sekkumpulan n objek ke dalam d k clustter sehingga tingkat kemiiripan antaar anggota dalam satuu cluster tinggi t sedaangkan tingkkat kemiripann dengan annggota padaa cluster laain sangat reendah. Kemiripan angggota terhaddap cluster diukur deengan kedeekatan objekk terhadap nilai mean pada clusster atau daapat disebut sebagai cenntroid clusster atau pusaat massa. (Naango, Dwi Nooviati, 20122). Berikut ini adalahh rumus untuk mennentukan jumllah cluster : (1) r pengukkuran jarak : Berikut rumus d(x,y) =|||x-y||2 = ∑
(2)
H - 2 Hal
Adapun rumus perhitungan jarak lainnya didefinisikan sebagai berikut :
Ilustrasi Algoritma dilihat dibawah ini:
K-Means
dapat
(3)
,
Keterangan : d = titik dokumen x = data record y = data centroid Jarak yang terpendek antara centroid dengan dokumen menentukan posisi cluster suatu dokumen. Misalnya dokumen A mempunyai jarak yang paling pendek ke centroid 1 dibanding ke yang lain, maka dokumen A masuk ke group 1. Hitung kembali posisi centroid baru untuk tiap-tiap centroid (Ci..j) dengan mengambil rata- rata dokumen yang masuk pada cluster awal (Gi..j). Iterasi dilakukan terus hingga posisi group tidak berubah. Berikut rumus dari penentuan centroid. |
|
∑
̅
Sumber : http://www.mathworks.com
Gambar 1.1 Algoritma K-Means
(4) 2.3 PHP Script Language
Adapun rumus iterasi didefinisikan sebagai berikut : ..
…
∑
lainnya
(5)
Keterangan : x1 = nilai data record ke-1 x2 = nilai data record ke-2 Σx = jumlah data record Menurut Adiningsih (2007), tahap penyelesaian algoritma K-Means adalah sebagai berikut: a. Menentukan K buah titik yang merepresentasikan obyek pada setiap cluster (centroid awal). b. Menetapkan setiap objek pada cluster dengan posisi centroid terdekat. c. Jika semua objek sudah dikelompokkan maka dilakukan perhitungan ulang dalam menentukan centroid yang baru. d. Ulangi langkah ke-2 dan ke-3 sampai centroid tidak berubah.
PHP: HyperText Preprocessor merupakan secara umum dikenal sebagai bahasa pemrograman script-script yang membuat dokumen HTML secara on the file yang dieksekusi di server web, dokumen HTML yang dihasilkan dari suatu aplikasi bukan dokumen HTML yang dibuat dengan menggunakan editor teks atau editor HTML (Sidik, Bertha, 2012, h.7). 2.4 MySQL MySQL merupakan software database yang termasuk paling populer di lingkungan Linux. Kepopuleran ini karena ditunjang performansi query dari database-nya yang saat itu paling cepat dan jarang bermasalah. Berangkat dari software database yang shareware MySQL populer, kini mulai versi 3.23 MySQL menjadi software open source yang berarti free. MySQL dapat digunakan untuk kepentingan komersial ataupun personal (Sidik, Bertha, 2012, h.333).
Hal - 3
3
RANCANGAN PROGRAM
ALGORITMA
DAN
3.1 Metodologi RUP Dalam mengembangkan aplikasi ini, metodologi yang digunakan adalah metodologi RUP. RUP (Rational Unified Process) merupakan sebuah proses pengembangan perangkat lunak yang berfungsi untuk memastikan hasil yang diperoleh dari pengembangan perangkat lunak dan sesuai dengan jadwal serta anggaran yang telah dirancang. Proses ini lebih menekankan pada pengembangan dan pemeliharaan yang terus diperbaharui agar menghasilkan perangkat lunak yang lebih baik lagi (Simarmata, Janner, 2009, h.81). Di dalam metodologi ini terdapat tahapan - tahapan dalam menjalankan prosesnya yang terdiri dari: 1. Inception (permulaan) Pada tahapan ini merupakan tahap dalam proses menentukan dan mencari kebutuhan yang diperlukan dalam proses pembuatan sebuah sistem dan dampak/manfaat dari pengembangan sistem tersebut. Aktivitas yang dilakukan pada tahap ini antara lain mencakup analisis sistem, perumusan sistem target, penentuan arsitektur global target, identifikasi kebutuhan, perumusan persyaratan, perumusan kebutuhan pengujian (level unit, integrasi, sistem, performansi, fungsionalitas, keamanan), pemodelan diagram UML, dan pembuatan dokumentasi. Di dalam tahapan ini terdapat perincian sebagai berikut : a. Studi Literatur (Inception) Mengumpulkan informasi dan data mengenai algoritma K-Means dan proses clustering dokumen dari buku ataupun jurnal, mengumpulkan data-data jurnal serta mempersiapkan semua data-data yang dibutuhkan yaitu dokumen jurnal skripsi STMIK GI MDP.
2. Elaboration (perluasan) Pada tahapan ini merupakan proses dimana hasil dari tahapan inception dievaluasi lagi mengenai desain dan kebutuhan yang diperlukan, apakah masih terdapat kebutuhan ataupun desain yang diperlukan untuk melengkapi sistem agar lebih baik lagi. Pada tahap desain ini menggunakan pemodelan kasus use case dimana terdapat interaksi antara aktor-aktor dan sistem yang berinteraksi di dalamnya yang mencakup pembuatan desain arsitektur subsistem (architecture pattern), desain komponen sistem, desain format data (protokol komunikasi), desain database, desain user interface, pemodelan diagram UML, dan pembuatan dokumentasi. 3. Construction (pembuatan) Pada tahapan ini merupakan proses dimana pengembang melakukan pengimplementasian mengenai sistem yang akan dibuat dengan menggunakan bahasa pemrograman PHP. Aktivitas yang dilakukan pada tahap ini antara lain mencakup pengujian hasil analisis dan desain, pendataan kebutuhan implementasi lengkap, penentuan coding pattern yang digunakan, pembuatan program, pengujian, optimasi program, pendataan berbagai kemungkinan pengembangan / perbaikan lebih lanjut, dan pembuatan dokumentasi. 4. Transition (peralihan) Tahapan ini merupakan tahapan akhir dari metodologi sistem RUP yang mana pada tahapan ini dilakukan transisi agar pengguna dapat mengerti dalam menggunakan sistem yang telah dibangun/dikembangkan. Pada tahap peralihan ini, sistem yang telah dibangun diuji coba dengan cara mendemokan cara penggunaannya sehingga user bisa menguji hasil dari sistem, apakah sistem berjalan sesuai dengan yang diharapkan atau tidak.
Hal - 4
3.3 Flowchart Flowchart adalah sebuah diagram dengan simbol-simbol grafis yang menyatakan aliran algoritma atau proses yang menampilkan langkah-langkah yang disimbolkan dalam bentuk kotak, beserta urutannya dengan menghubungkan masing-masing langkah tersebut menggunakan tanda panah. 3.3.1 Flowchart Tahap Preprocessing Flowchart tahap preprocessing merupakan flowchart yang berisi proses penghilangan tanda baca (tokenization), proses penghilangan kata yang tidak penting (stopwords), serta proses pengambilan kata dasar (stemming). 3.3.3 Flowchart Mencari Jarak Flowchart mencari jarak merupakan flowchart yang berisi proses pencarian jarak antara dokumen dengan titik centroid dimana proses dilakukan dengan menghitung nilai frekuensi kata yang ada pada tiap dokumen, kemudian dilakukan perhitungan jarak dengan Euclidean.
3.3.2 Flowchart Mencari Jumlah Cluster Flowchart mencari jumlah cluster merupakan flowchart yang berisi proses pencarian jumlah cluster dengan cara membagi dua jumlah dari seluruh dokumen kemudian diakarkan.
Hal - 5
3.3.4 Flowchart Mencari Centroid Baru Flowchart mencari centroid baru merupakan flowchart yang berisi proses pencarian centroid (titik pusat) baru dengan cara membagi jumlah seluruh dokumen dengan jumlah cluster yang terbentuk.
3.3.5 Flowchart Algoritma K-Means
Flowchart Algoritma K-Means merupakan flowchart yang berisi urutan proses dari mencari frekuensi kemunculan kata (Tf), mencari jumlah cluster, menentukan centroid (titik pusat) awal, mencari jarak, mengelompokkan dokumen berdasarkan jarak terdekat dengan centroid, serta proses mencari centroid baru.
4
IMPLEMENTASI PROGRAM
DAN
ANALISIS
4.1 Prosedur Uji Coba Program 4.1.1 Tampilan Antarmuka Menu Utama Ketika user menjalankan aplikasi maka halaman pertama yang akan tampil adalah halaman menu utama. Berikut adalah tampilan antarmuka menu utama yang dapat dilihat pada Gambar 4.1. Hal - 6
4.1.3 Tampilan Antarmuka Halaman Isi Dokumen Pada saat user memilih salah satu jurnal maka akan menampilkan halaman isi dokumen.
Gambar 4.1 Antarmuka Halaman Menu Utama 4.1.2 Tampilan Pencarian
Antarmuka
Halaman
Pada saat user memasukan query yang ingin dicari dan menekan tombol cari maka akan tampil halaman pencarian.
Gambar 4.4 Tampilan Antarmuka Halaman Isi Dokumen 4.1.4 Tampilan Antarmuka Halaman Admin
Gambar 4.2 Tampilan Antarmuka Halaman Pencarian dengan Stemming
Gambar 4.5 Tampilan Antarmuka Halaman Admin 4.1.5 Tampilan Antarmuka Menu Ubah Dokumen Menu ubah dokumen pada Gambar 4.6 adalah menu yang disediakan bagi admin untuk melakukan perbaikan apabila ada kesalahan dalam penginputan data. Gambar 4.3 Tampilan Antarmuka Halaman Pencarian Non-Stemming Hal - 7
dengan cara memasukkan 5 query yang sama ke dalam masing-masing aplikasi. Nilai akurasi = jumlah dokumen yang sama antara dan klasi ikasi jumlah dokumen keseluruhan
Query = “ perancangan sistem informasi ” Tabel 4.1 Hasil Hasil Kesamaan Clustering dan Klasifikasi Clustering J0001 J0007 J0016 J0017 J0028 J0040 J0060 J0074 J0076 J0077
Gambar 4.6 Tampilan Antarmuka Menu Ubah Dokumen 4.1.6 Tampilan Antarmuka Tambah Dokumen
Menu
Tab
Menu tab tambah dokumen pada Gambar 4.7 menampilkan sebuah daftar yang harus dimasukkan oleh admin yaitu berupa sebuah file .pdf jurnal, sebuah file .txt jurnal, judul jurnal, nama pengarang, tahun dan abstrak.
Pada Tabel 4.1 buah dokumen clustering dan diperoleh nilai berikut : Nilai akurasi =
Klasifikasi J0004 J0007 J0008 J0016 J0017 J0018 J0026 J0027 J0028 J0077
diperoleh bahwa terdapat 5 yang sama pada aplikasi klasifikasi sehingga dapat akurasinya adalah sebagai x 100% = 50%
4.2.2 Uji Coba Kedua
Gambar 4.7 Tampilan Antarmuka Menu Tab Tambah Dokumen
Hasil uji coba waktu antara proses stemming dengan proses non-stemming dengan query : “aplikasi pembelian barang” terhadap 300 dokumen jurnal.
4.2 Analisis Hasil Pengujian Program
3
4.2.1 Uji Coba Pertama
2
Uji coba pertama dilakukan untuk menguji keakuratan sistem dengan membandingkan hasil yang diperoleh dari aplikasi menggunakan algoritma K-Means dengan klasifikasi judul yang ada pada database aplikasi dimana dilakukan proses pencarian
1
2.85 1.48
0 Stemming
Non‐Stemming
Gambar 4.8 Uji Coba Pengujian Waktu Hal - 8
5
PENUTUP
5.1 Kesimpulan Setelah banyak tahapan dalam pengembangan perangkat lunak dimulai dari analisis kebutuhan sampai dengan implementasi dan pengujian maka ada beberapa kesimpulan yang didapat setelah skripsi ini yaitu sebagai berikut : 1. Algoritma K-Means dapat melakukan pengelompokan dokumen dalam jumlah yang banyak akan tetapi belum efisien dalam mengelompokan dokumen secara tepat. 2. Penentuan centroid (titik pusat) pada tahap awal Algoritma K-Means sangat berpengaruh pada hasil cluster seperti pada hasil pengujian yang dilakukan dengan menggunakan 300 dataset dengan centroid yang berbeda menghasilkan hasil cluster yang berbeda juga. 3. Proses clustering menggunakan stemming akan menghabiskan waktu lebih lama dibandingkan dengan non-stemming, hal ini dapat dilihat pada hasil uji coba 2. 4. Semakin sedikit dokumen yang dipakai, maka semakin sulit untuk membedakan cluster antara stemming dan non-stemming. 5.2 Saran Berikut ini beberapa saran yang bertujuan mengembangkan Aplikasi Penerapan Algoritma K-Means untuk Clustering Dokumen E-jurnal STMIK MDP yang penulis buat adalah sebagai berikut: 1. Untuk meningkatkan hasil pengelompokan dokumen yang lebih relevan sebaiknya algoritma K-Means digabung dengan algoritma lain seperti Algoritma Hierarchical Clustering. 2. Aplikasi ini dapat dikembangkan dengan cara menambah fitur convert file dan standarisasi sehingga dapat mempermudah kerja admin. 3. Agar aplikasi dapat digunakan untuk umum, sebaiknya aplikasi dibuat secara online.
DAFTAR PUSTAKA [1]
[2]
Grossman, David A. dan Ophir Frieder 2004.Information Retrieval Algorithms and Heuristics Second Edition. Springer, The Netherlands. Determining the number of clusters in a data set. http://en.wikipedia.org/wiki/ Determining_the_number_of_clusters_in _a_data_set. Diakses pada tanggal 10 Januari 2014.
[3]
Nango, Dwi Noviati 2012. Penerapan Algoritma K-means untuk Clustering Data Anggaran Pendapatan Belanja Daerah di Kabupaten XYZ. http://sro.web.id. Diakses pada tanggal 16 Agustus 2013.
[4]
Ken 2009. Clustering Analysis, Part II: K-Means Clustering. http://www.centerspace.net. Diakses pada tanggal 10 September 2013.
[5]
Sidik, Bertha 2012. Pemrograman Web PHP (Edisi Revisi). Informatika, Bandung.
[6]
Rational Unifed Process 2006. http://www.skillresource.com. Diakses pada tanggal 12 Desember 2013.
[7]
Simarmata, Janner 2009. Rekayasa Perangkat Lunak. Andi, Yogyakarta.
[8]
Suryana,Taryana 2007. Metode RUP. sms.unikom.ac.id. Diakses pada tanggal 10 November 2013.
Hal - 9
