ipi54097

JURNAL TEKNIK ITS Vol. 1, (Sept, 2012) ISSN: 2301-9271 A-521

Abstrak— Saat ini, konsep data mining semakin dikenalsebagai tools penting dalam manajemen informasi karenajumlah informasi yang semakin besar jumlahnya. Salahsatu teknik yang dikenal dalam data mining adalahclustering, berupa proses pengelompokan sejumlah dataatau objek ke dalam cluster (group) sehingga setiap dalamcluster tersebut akan berisi data yang semirip mungkindan berbeda dengan objek dalam cluster yang lainnya.Clustering memiliki dua metode, yaitu partisi dan hierarki.Dua metode ini memiliki kelebihan dan kekuranganmasing-masing, dan dengan menggabungkan keduanyadapat diperoleh hasil cluster yang lebih baik. Dari hasilcluster dengan menggunakan data problem Kerja PraktekJurusan Teknik Industri ITS, maka diperoleh hasil bahwagabungan metode Single Linkage Clustering dan K-meansmemberikan hasil cluster yang lebih baik denganparameter uji cluster variance dan metode silhouettecoefisien.

Kata Kunci— Kerja Praktek, Document Clustering, K-means,Hierarchical Clustering, Cluster Variance, Metode SilhouetteCoeficient.

I. PENDAHULUAN

aat ini, konsep data mining semakin dikenal sebagai toolspenting dalam manajemen informasi karena jumlah

informasi yang semakin besar jumlahnya. Data mining sendirisering disebut sebagai knowledge discovery in database(KDD) adalah kegiatan yang meliputi pengumpulan,pemakaian data historis untuk menemukan keteraturan, polahubungan dalam set data berukuran besar [1]. Output dari datamining ini dapat digunakan untuk pengambilan keputusan dimasa depan.

Salah satu teknik yang dikenal dalam data mining yaituclustering. Pengertian clustering keilmuan dalam data miningadalah pengelompokan sejumlah data atau objek ke dalamcluster (group) sehingga setiap dalam cluster tersebut akanberisi data yang semirip mungkin dan berbeda dengan objekdalam cluster yang lainnya. Sampai saat ini, para ilmuwanmasih terus melakukan berbagai usaha untuk melakukan

perbaikan model cluster dan menghitung jumlah cluster yangoptimal sehingga dapat dihasilkan cluster yang paling baik.Ada dua metode clustering yang kita kenal, yaitu hierarchicalclustering dan partitioning. Metode hierarchical clusteringsendiri terdiri dari complete linkage clustering, single linkageclustering, average linkage clustering dan centroid linkageclustering.Sedangkan metode partitioning sendiri terdiri darik-means dan fuzzy k-means.

Metode K-means merupakan metode clustering yang palingsederhana dan umum [1]. Hal ini dikarenakan K-meansmempunyai kemampuan mengelompokkan data dalam jumlahyang cukup besar dengan waktu komputasi yang relatif cepatdan efisien [2]. Namun, K-means mempunyai mempunyaikelemahan yang diakibatkan oleh penentuan pusat awalcluster. Hasil cluster yang terbentuk dari metode K-means inisangatlah tergantung pada inisiasi nilai pusat awal clusteryang diberikan [1]. Hal ini menyebabkan hasil clusternyaberupa solusi yang sifatnya local optimal. Untuk itu, maka K-means dikolaborasikan oleh metode hierarki untuk penentuanpusat awal cluster. Metode hierarki yang akan dicobaditerapkan dalam penelitian ini adalah kelima metodehirarchical clustering yang telah disebutkan sebelumnya.Kelima metode ini akan dibandingkan untuk melihat clustermana yang memberikan hasil pengelompokan yang lebih baik.Dari proses pengelompokan ini nantinya diharapkan akandiketahui kemiripan atau kedekatan antar data sehingga dapatdikelompokkan ke dalam beberapa cluster, dimana antaranggota cluster memiliki tingkat kemiripan yang tinggi.

Data yang digunakan dalam penelitian ini adalah data teks.Dimana data ini merupakan data problem kerja praktekJurusan Teknik Industri ITS yang disampaikan olehmahasiswanya melalui forum diskusi jejaring sosial facebook.Sehingga dalam penelitian ini nantinya akan dijelaskanbagaimana cara mengelompokkan problem kerja praktekberdasarkan posting problem yang ada pada forum diskusionline SI-KP yang ada di jejaring sosial facebook. Metodeyang digunakan adalah metode document clustering dengan K-means dan hierarchical clustering.

Sebelumnya, penelitian mengenai problem pengelompokandokumen telah banyak dilakukan melalui berbagai metode.

Analisa Perbandingan Metode HierarchicalClustering, K-means dan Gabungan Keduanya

dalam Cluster Data(Studi kasus : Problem Kerja Praktek Jurusan

Teknik Industri ITS)

Tahta Alfina, Budi Santosa, dan Ali Ridho BarakbahJurusan Teknik Industri, Fakultas Teknologi Industri, Institut Teknologi Sepuluh Nopember (ITS)

Jl. Arief Rahman Hakim, Surabaya 60111E-mail: [email protected]

S


Misalnya penggunaan metode K-Nearest Neigbour (KNN)untuk kategorisasi teks [3], klasifikasi dokumen berbahasaindonesia dengan algoritma single pass clustering [4],clustering based on frequent word and sequence dan K-means[5], pengelompokan data teks dengan fuzzy c-means [6] danbeberapa penelitian lain dengan metode yang hampir serupa.

II. METODOLOGI PENELITIANPada bagian metodologi penelitian ini akan diuraikan

langkah-langkah sistematis dan terarah yang akan dijadikanacuan sebagai kerangka penelitian penentuan kemiripanproblem kerja praktek di Jurusan Teknik Industri denganmenggunakan kombinasi semua metode Hierarchicalclustering dan K-means sehingga dapat diketahui metodemanakah yang menghasilkan hasil cluster yang terbaik.

A. Tahap Pengolahan Data Teks ke dalam Metadata

Dari semua data yang diperoleh, dipilih keyword-keywordyang dapat mewakili problem Kerja Praktek Jurusan TeknikIndustri ITS pada tahun 2011. Keyword yang terpilih nantinyaakan digunakan digunakan untuk membentuk matriksmetadata yang menunjukkan frekuensi dari setiap keywordsdalam setiap problem yang disampaikan oleh mahasiswa.Pemilihan keywords dapat dilakukan dengan berbagai metode.Diantaranya dengan menggunakan metode documentclustering atau menggunakan algoritma text mining. Dalampenelitian ini digunakan algoritma document clusteringsederhana karena domain teks yang akan dibawa kedalamsuatu cluster bersifat spesifik, yaitu problem kerja praktekJurusan Teknik Industri ITS. Sehingga keywords yang akandigunakan dalam metadata dapat ditentukan secara manualoleh peneliti. Berbeda halnya dengan algoritma text mining.Text mining digunakan untuk mengelompokkan data dimanadomainnya bersifat bebas. Sehingga harus melewati proses-proses dalam text mining seperti tokenizing adalah prosespenghilangan tanda baca pada kalimat yang ada dalamdokumen sehingga menghasilkan kata-kata yang berdirisendiri-sendiri dan tahap filtering adalah tahap pengambilankata-kata yang penting dari hasil tokenizing denganmenggunakan algoritma stoplist atau wordlist.

Pada umumnya, penetuan keywords ditentukan olehsubyektifitas peneliti karena peneliti yang mengerti dan tahutujuan yang ingin dicapai dalam penelitiannya. Namun,problem kerja praktek ini melibatkan banyak stakeholder yangikut berperan disana. Oleh karena itulah, keywords yangdipilih pada permasalahan ini ditentukan dengan melakukaninterview yang dibantu dengan sebuah kuisioner (terlampir).Adapun pihak yang diinterview adalah admin Kerja Praktektahun 2011, Koordinator Kerja Praktek Jurusan TeknikIndustri dan beberapa mahasiswa yang mengambil KerjaPraktek pada tahun 2011. Berikut ini adalah list keywordsyang digunakan untuk membentuk matriks metadata :

Tabel 1 List Keywords untuk Metadata

Dari hasil interview dan survey yang dilakukan, terdapat 40keywords yang akan digunakan untuk membentuk kolommatriks metadata. Sedangkan banyaknya data yang digunakansebagai input sebanyak 327 data yang membentuk barismatriks metadata.

B. Tahap Clustering

Pada tahap ini dilakukan pengelompokan datamenggunakan kombinasi dua algoritma clustering, yaituhierarchical clustering dan metode K-means. Dari algoritmahierarchical clustering ini digunakan untuk menentukan pusatcluster. Selanjutnya, pusat cluster yang diperoleh hierarchicalclustering tersebut digunakan untuk proses pengelompokandata dengan menggunakan metode K-means. Gambar 1 adalahflowchart yang menjelaskan urutan pengerjaan penelitiandengan menggunakan metode hierarchical clustering dan K-means.

Gambar 1 Algoritma Hierarchical clustering dan K-means

No. Keywords No. Keywords No. Keywords No. Keywords

1 SI-KP 11 Jurusan 21 eksternal 31 Username2 KP 12 email 22 logbook 32 Approve3 registrasi 13 Prosedur 23 PDF 33 Delete

4 Mahasiswa 14 aktivasi 24 Manual 34 Hapus

5 Tanggal 15 Arahan 25 Dashboard 35 Edit

6 User 16 Notifikasi 26 Login 36 Input

7 Akun 17 Dosen 27 online 37 Laporan

8 Admin 18 Pembimbing 28 password 38 Periode

9 Koordinator 19 nilai 29 group 39 Sosialisasi

10 perusahaan 20 Internal 30 Kelompok 40 Cetak


Dari gambar flowchart tersebut dapat diketahui tentangurutan metode clustering dengan hierarchical clustering yangditandai dengan warna kuning dan metode K-means ditandaidengan warna hijau. Pada metode hierarchical clustering,sebelum dilakukan pengelompokan, setiap data yang adadiasumsikan sebagai cluster. Hal ini jika terdapat jumlah datasebanyak n, dan k dianggap sebagai jumlah cluster, makabesarnya n = k. Kemudian, dihitung jarak antar clusternyadengan menggunakan Euclidian distance berdasarkan jarakrata-rata antar objek. Selanjutnya, dari hasil perhitungan tadidipilih jarak yang paling minimal dan digabungkan sehinggabesarnya n = n -1. Hal ini akan terus dilakukan dan akanberhenti jika memenuhi kondisi jumlah k = 1. Pada akhir tahaphierarchical clustering ini akan diperoleh sebuah gambardendrogram yang menunjukkan urutan pengelompokanmasing-masing anggota dalam cluster.

Setelah sampai pada kondisi k = 1, maka dilanjutkandengan metode K-means. Pada metode ini, seharusnya diawalioleh penentuan jumlah k cluster yang akan dibentuk,kemudian dilanjutkan dengan penentuan pusat awal clustersecara random. Namun, karena metode ini merupakankombinasi antara hierarchical clustering dan K-means, makapenentuan pusat cluster untuk metode K-means ditentukandengan mencari rata-rata dari data yang berada pada sebuahcluster hasil dari hierarchical k-means. Sehingga pada tahapanini, pusat cluster metode K-means langsung dapat ditentukan.Selanjutnya, dihitung jarak anggota cluster ke setiapcentroidnya. Setelah didapatkan hasilnya, anggota clusterdimasukkan kedalam cluster yang memiliki jarak yang paingdekat dengan centroidnya. Iterasi pada K-Means akan berhentiketika semua data yang berada pada sebuah cluster tertentutidak berpindah ke cluster yang lainnya.

C. Pengujian Performansi Algoritma

Pada Subbab ini akan dilakukan pengujian tehadap hasilalgoritma metode clustering. Pengujian ini dilakukan untukmelihat apakah kombinasi algoritma hierarchical clusteringdengan K-means menghasilkan pengelompokan data yanglebih baik jika dibandingkan dengan metode hierarki itusendiri maupun K-means. Adapun pengujian yang dilakukanadalah sebagai berikut :

1. Cluster VarianceAnalisa ini digunakan untuk nilai penyebaran dari data-data hasil clustering dengan metode K-means. Clustervariance ini hanya digunakan untuk data yang bersifatunsupervised. Sedangkan pada data supervised digunakanerror ratio analysis [7]. Besarnya nilai varian sebuahcluster dapat dihitung dengan rumus berikut := ∑ ( − ) (1)

Dimana := variance pada cluster ke c

c =1…k,dimana k =jumlah cluster= jumlah data pada cluster c

= data ke-i pada suatu cluster= rata-rata dari data pada suatu cluster

Ada dua macam cluster variance, yaitu varian withincluster ( ) dan varian between cluster ( ).

digunakan untuk melihat hasil variansi penyebaran

data yang ada pada sebuah cluster (internal homogenity).Semakin kecil nilai , maka semakin baik clusternya.Besarnya nilai dapat dihitung dengan rumus := ∑ ( − ). … (2)Dimana :N : jumlah semua datak : jumlah cluster

: jumlah anggota dalam cluster ke-i

Sedangkan nilai ( ) merupakan nilai yang digunakanuntuk melihat hasil variansi penyebaran data antar cluster(external homogenity). Semakin besar nilai ( ), makasemakin baik hasil clusternya.besarnya nilai ( ) dapatdihitung dengan rumus := ∑ − ……. (3)Dimana

k : jumlah cluster̅ : rata-rata dariSedangkan untuk melihat varian dari semua cluster makadiukur dengan membandingkan nilai ( ) dan ( ) yaitu= (4)

Nilai akan menunjukkan hasil yang semakin baikketika nilainya semakin kecil. Sedangkan nilai akanmenunjukkan hasil yang baik ketika nilainya semakinbesar. Maka dari sini, nilai V dari semua cluster akansemakin baik jika nilainya semakin kecil.Dengan menggunakan rumus-rumus diatas, makadiperoleh hasil cluster variance untuk 3,5 dan 7 clustersebagai berikut :

Gambar 2 Grafik perbandingan nilai

Gambar 2 menunjukkan perbandingan nilai ( ) darimasing-masing metode dengan 3 skenario cluster yang telahdibuat. Jika ditinjau dari segi jumlah clusternya, prosesclustering yang menghasilkan ( ) terbaik adalah dihasilkanoleh data yang diclusterkan kedalam 5 cluster. Hal inimenunjukkan bahwa jumlah cluster sebanyak 5 inimemberikan hasil penyebaran data yang baik dibandingkandengan 3 cluster atau 7 cluster. Sedangkan jika ditinjau darisegi metode, nilai terbesar dihasilkan oleh metode singlelinkage clustering. Pada umumnya, metode average linkageclustering memberikan hasil yang lebih baik jika dibandingkadengan metode yang lainnya. Namun hal tersebut berlaku jika


data yang digunakan dalam menguji cluster berupa data set,misalnya data iris, data russpini dan lain sebagainya.Sedangkan data yang digunakan dalam penelitian ini adalahdata yang bersifat non-globular atau menyebar.

Sedangkan nilai akan menunjukkan hasil yang semakinbaik ketika nilainya semakin kecil. Untuk lebih mudah dalammelakukan analisa, nilai untuk semua metode dan semuacluster yang telah diperoleh dari perhitungan pada bab 4diplotkan ke dalam sebuah grafik seperti yang ditampilkanpada gambar 3 dibawah.

Jika dilihat dari segi metode yang digunakan, besarnya nilaiyang dihasilkan tidak menunjukkan perbedaan yang terlalu

signifikan. Sedangkan jika ditinjau dari jumlah cluster, nilaiterkecil dihasilkan oleh data yang terbentuk kedalam 7

cluster. Hal ini dikarenakan semakin banyak cluster yangdibentuk, semakin banyak data yang dapat masuk ke dalamdata cluster yang berbeda-beda sehingga menghasilkanvariansi cluster yang semakin kecil.Selanjutnya, nilai kedua varian tersebut dapat dibandingkansehingga nantinya dapat digunakan untuk melihat variansi darisemua cluster maka diukur dengan membandingkan nilai ( )dan ( ). Maka dari sini, nilai dari semua cluster akansemakin baik jika nilainya semakin kecil.

Gambar 3 Grafik perbandingan nilai

Selanjutnya, nilai kedua varian tersebut dapat dibandingkansehingga nantinya dapat digunakan untuk melihat variansi darisemua cluster maka diukur dengan membandingkan nilai ( )dan ( ). Maka dari sini, nilai dari semua cluster akansemakin baik jika nilainya semakin kecil.

Gambar 4 Grafik perbandingan nilai V

Nilai yang dihasilkan disini menunjukkan variansi totaldari setiap cluster yang dihasilkan. Dari Gambar 19, terlihatbahwa hasil cluster terbaik dihasilkan oleh data yang dibagi kedalam 5 cluster untuk semua metode karena mempunyai nilai

yang paling kecil jika dibandingkan dengan jumlah clusteryang lain. Sedangkan jika ditinjau dari segi metode, algoritmaK-Means menghasilkan varian cluster yang terbesar jikadibandingkan metode K-means yang pusat clusternyadiinisiasi dari algoritma hierarchical clustering. Ini berartimetode k-means tidak dapat menghasilkan cluster yang lebihbaik jika dibandingkan dengan kombinasi metode hierarchicalclustering dan K-means. Sedangkan untuk metode kombinasihierarchical clustering dan K-means, pada kasus ini hasilterbaiknya dihasilkan oleh K-means yang pusat awalnyadiinisiasi oleh single linkage clustering.

2. Koefisien Korelasi CopheneticSelain menggunakan analisa cluster variance, analisacluster juga dapat dilakukan dengan menggunakankoefisien korelasi cophenetic. Namun analisa ini hanyaterbatas pada cluster yang dibentuk dengan menggunakanalgoritma hierarchical clustering. Nilai koefisien korelasicophenentic terbesar adalah Average Linkage Clusteringyaitu sebesar 0.9171, sedangkan nilai koefisien korelasicophenetic yang paling kecil adalah pada CompleteLinkage Clustering yaitu sebesar 0.7798. Sedangkan nilaidua metode linkage yang lain yaitu Single LinkageClustering dan Centroid Linkage Clustering masing-masing sebesar 0.9118 dan 0.9117. untuk lebihmudahnya, perbandingan nilai koefisien korelasiCophenetic ini dapat dilihat pada gambar Grafik berikutini :

Gambar 5 Grafik Koefisien Korelasi Cophenetic

Besarnya nilai ini harus sangat dekat dengan 1 untuksolusi yang lebih baik. Ukuran ini dapat digunakan untukmembandingkan solusi cluster alternatif diperoleh denganmenggunakan algoritma yang berbeda. Sehingga, daripenjelasan tersebut dapat disimpulkan semakin besar(semakin mendekati 1) nilai koefisien korelasicophneneticnya, maka semakin baik pula hasil clusternya.Dari sini, dapat kita simpulkan bahwa metode hierarkiyang paling baik dalam membentuk suatu cluster adalahaverage linkage clustering. Hal ini dikarenakan metodeini merupakan satu-satunya metode clustering yangmemperhitungan setiap jarak antar titiknya dalammenentukan urutan membentuk cluster.

3. Metode Silhouette Coefficient

0.0000

1.0000

2.0000

3.0000

4.0000

5.0000

6.0000

7.0000

8.0000

Kmeans Single linkage danK-means

Average linkagedan K-means

Complete linkagedan K-means

Centriod linkagedan K-means

va

ria

n

Variance Within Cluster

3

5

7

0.7

0.75

0.8

0.85

0.9

0.95

Single linkageclustering

Average linkageclustering

Complete linkageclustering

Centroid linkageclustering

Koefisien Korelasi Cophenetic

KoefisienCophenetic


Analisa metode silhouette ini dilakukan dengan melihatbesar nilai s dari hasil perhitungan dengan menggunakanbantuan software MatLab. Hasil perhitungan nilaisilhouette coeffisien dapat bervariasi antara -1 hingga 1.Jika si = 1 berarti objek i sudah berada dalam cluster yangtepat. Jika nilai si = 0 maka objek i berada di antara duacluster sehingga objek tersebut tidak jelas harusdimasukan ke dalam cluster A atau cluster B. Akan tetapi,jika si = -1 artinya struktur cluster yang dihasilkanoverlapping, sehingga objek i lebih tepat dimasukan kedalam cluster yang lain. Untuk mempermudah dalammelakukan analisa, nilai s dikonversikan ke dalam duanilai, yaitu 1 jika nilai silhouettenya lebih besar dari 0 danbernilai 0 jika nilai silhouettenya lebih kecil dari nol.Sehingga ketika hasil dari penjumlahan nilai s yangdikonversikan tadi jumlahnya paling besar diantaracluster yang lainnya, maka artinya hasil cluster yangdihasilkan merupakan cluster yang terbaik karenasemakin sedikit nilai s yang nilainya dibawah 0. Berikutini adalah gambar berikut ini :

Gambar 6 Evaluasi Nilai Silhouette dengan Jumlah Cluster sebanyak 3

Untuk skenario jumlah cluster sebanyak 3, semua metodehierarki yang digabungkan dengan K-means memberikan hasilcluster yang sama dan lebih baik jika dibandingkan denganmetode K-means itu sendiri. Untuk skenario jumlah clusteryang digunakan sebanyak 5, dapat dilihat bahwa penjumlahannilai s terbesar diperoleh ketika pengclusteran dilakukandengan menggunakan metode single lingkage clustering yangdikombinasikan dengan K-means, diikuti oleh 3 metodeHierarchical Clustering yang lainnya yang digabungkandengan K-means dan penjumlahan nilai s yang paling kecildihasilkan oleh metode K-means.

Berbeda dengan evaluasi nilai s yang dihasilkan oleh 5cluster, pada evaluasi nilai s dengan 7 cluster, metode yangmemberikan hasil yang terbaik adalah metode gabunganCentroid Linkage Clustering dan K-means sebesar 294 datadiclusterkan pada cluster yang tepat. Kemudian baru diikutioleh 3 metode Hierarchical Clustering yang lainnya yangdigabungkan dengan K-means dan penjumlahan nilai s yangpaling kecil dihasilkan oleh metode K-means.

III. KESIMPULAN

Adapun kesimpulan dari penelitian ini adalah sebagaiberikut :

1. Kombinasi algoritma hierarchical clustering dan k-means menghasilkan pengelompokan data yang lebihbaik jika dibandingkan dengan k-means dalam semuapengujian.

2. Dengan evalusi koefisien cophenetic, metodeclustering terbaik dihasilkan oleh average linkageclustering

3. Dalam studi kasus Problem Kerja Praktek JurusanTeknik Industri ITS, dari kombinasi hierarchicalclustering dan K-means yang ada, kombinasi singlelinkage clustering dan K-means menghasilkanpengelompokan data yang terbaik dibandingkandengan metode hierarki yang lainnya.

DAFTAR PUSTAKA

[1] B. Santosa, Data Mining. Teknik Pemanfaatan Datauntuk Keperluan Bisnis, First Edition ed. Yogyakarta:Graha Ilmu, (2007).

[2] K. Arai and A. R. Barakbah, "Hierarchical K-means:an algorithm for centroids initialization for K-means," (2007).

[3] S. Jiang, et al., "An improved K-nearest-neighboralgorithm for text categorization," Expert Systemswith Applications, vol. 39, pp. 1503-1509, (2011).

[4] A. Z. Arifin and A. N. Setiono, "Klasifikasi DokumenBerita Kejadian Berbahasa Indonesia denganAlgoritma Single Pass Clustering," (2002).

[5] N. R. Widyawati, et al., Perbandingan ClusteringBased on Frequent Word Sequnce dan K-Meansuntuk Pengelompokan Dokumen BerbahasaIndonesia, ( 2011).

[6] C.-x. Li and N. Lin, "A Novel Text ClusteringAlgorithm," Energy Procedia, vol. 13, pp. 3583-3588, (2011).

[7] A. R. Barakbah and Y. Kiyoki, "A pillar algorithmfor k-means optimization by distance maximizationfor initial centroid designation," (2009), pp. 61-68.

ipi54097

Documents