PENDAHULUAN Latar Belakang Sponge atau poriferans berasal dari bahasa Latin yaitu porus yang artinya pori dan ferre yang artinya memiliki. Sponge adalah hewan berpori, pada umumnya terdapat di lautan, yang memompa air melalui tubuhnya untuk menyaring partikel–partikel sebagai makanannya. Berdasarkan tipe spicules dari kerangka tubuhnya bunga karang dikelompokan menjadi tiga kelas yaitu Calcarea, Hexactenellida, dan Demospongiae. Beberapa ahli taksonomi berpendapat adanya kelas lain yaitu Sclerospongiae. Ditemukannya kelas dan species baru mendorong ilmuwan–ilmuwan ahli taksonomi untuk melakukan penelitian lebih lanjut terhadap bunga karang berdasarkan anatomy, phisiology, geological history, dan lineage untuk memperoleh kemungkinan mendapatkan kelas dan species baru. Iosune Uriz dan Marta Domingo melakukan riset dan pengumpulan data terhadap bunga karang (sponge) di Lautan Atlantik. Jenis bunga karang pada data tersebut adalah O.Hadromerida (Demospongiae. Porifera) dan berdasarkan taksonominya termasuk kelas Demospongiae. Salah satu tujuan riset dan pengumpulan data tersebut adalah untuk mengetahui model cluster berdasarkan anatomy dan phisiology sponge. Model cluster tersebut diharapkan dapat direpresentasikan pada klasifikasi taksonomi sehingga dapat memprediksikan ada atau tidaknya kemungkinan species atau bahkan kelas baru dari data sponge tersebut. Data mining merupakan proses ekstraksi informasi atau pola yang penting dalam basis data yang berukuran besar (Han & Kamber, 2006). Data mining yang diterapkan pada data bunga karang tersebut diharapkan mampu menggali informasi pola cluster data tersebut. Clustering adalah proses data mining untuk melihat pola pendistribusian data yang akan digunakan untuk melihat karakteristik dari data (Han & Kamber 2006). Pola yang dihasilkan adalah pengelompokan himpunan objek ke dalam kelas-kelas berdasarkan nilai maksimal kemiripan data antar cluster. Sebagian besar data bunga karang adalah data kategorik. Algoritme ROCK dan QROCK merupakan algoritme clustering hirarki aglomeratif untuk data kategorik, oleh karena itu algoritme yang digunakan adalah
algoritme ROCK dan QROCK. ROCK (RObust Clustering using linKs) adalah algoritme yang membangun link untuk menggabungkan cluster-cluster-nya dan tidak menggunakan jarak (distance) seperti pada algoritme clustering pada umumnya. Algoritme ROCK tidak hanya menghasilkan kualitas yang lebih baik daripada algoritme clustering distance tetapi juga memiliki penanganan data kategorik yang lebih baik (Guha et al 2000). QROCK adalah perbaikan dari algoritme ROCK karena dari segi waktu iterasi lebih efisien dan dapat mendeteksi outlier dari hasil proses algoritme ROCK (M.Dutta et al. 2005). Tujuan Tujuan dari penelitian ini adalah : 1 2
Menerapkan teknik clustering ROCK dan QROCK pada data kategorik dari bunga karang. Membandingkan kualitas cluster yang dihasilkan oleh algoritme ROCK dan QROCK pada data kategorik dari bunga karang.
Ruang Lingkup Penelitian ini dibatasi pada penggunaan teknik clustering untuk data kategorik dengan menggunakan algoritme ROCK dan QROCK. Data yang digunakan adalah data bunga karang jenis O.Hadromerida (Demospongiae. Porifera) yang terdapat di Lautan Atlantik hasil penelitian Iosune Uriz dan Marta Domingo pada tahun 1993. Data dapat diunduh pada situs http://archive.ics.uci.edu/ml/dataset/Sponge. Manfaat Penelitian Penelitian ini diharapkan dapat bermanfaat bagi pihak-pihak yang membutuhkan informasi tentang penjelasan cara kerja ROCK dan QROCK, serta perbandingan diantara keduanya.
TINJAUAN PUSTAKA Knowledge Discovery in Database (KDD) Knowledge Discovery in Database (KDD) adalah proses menentukan informasi yang berguna serta pola-pola yang ada dalam data (Goharian & Grossman, 2003). Informasi ini terkandung dalam basis data yang berukuran besar yang sebelumnya tidak diketahui dan potensial bermanfaat (Han & Kamber, 2006). KDD merupakan sebuah proses yang terdiri dari serangkaian proses iterative yang terurut. 1
Data mining merupakan salah satu langkah dalam prosess KDD. Tahapan proses KDD dapat dilihat pada Gambar 1.
7
Presentasi pengetahuan Penggunaan visualisasi dan teknik representasi untuk menunjukan pengetahuan hasil penggalian dari tumpukan data kepada pengguna.
Data Mining Data mining merupakan suatu proses untuk menemukan pola-pola yang menarik dari data berukuran besar yang disimpan di basis data, data warehouse, atau sarana penyimpanan yang lain (Han & Kamber, 2006).
Gambar 1 Tahapan dalam KDD (Han & Kamber, 2006).
Proses data mining dapat dibedakan menjadi dua tujuan utama yaitu (Kantardzic 2003) : 1
Descriptive data mining Deskripsi konsep atau task-relevan data dalam bentuk yang ringkas, informatif, dan diskriminatif.
2
Predictive data mining Dari hasil analisis data dibuat model untuk dijadikan alat prediksi tren dan data yang tidak diketahui nilainya.
Tahapan proses KDD menurut Han & Kamber (2006) terdiri dari : 1
2
Pembersihan data Pembersihan data dilakukan untuk menghilangkan data yang tidak konsisten dan mengandung noise. Integrasi data Proses integrasi data dilakukan untuk menggabungkan data dari berbagai sumber menjadi bentuk sebuah penyimpanan data yang saling berhubungan, seperti dalam data warehousing.
3
Seleksi data Proses seleksi data mengambil data yang relevan digunakan untuk proses analisis.
4
Tranformasi data Proses ini mentransformasikan atau menggabungkan data ke dalam bentuk yang tepat untuk dilakukan proses mine dengan cara melakukan peringkasan atau operasi agregasi. Dalam beberapa kasus proses tranformasi dilakukan sebelum proses seleksi, misalnya dalam kasus data warehouse.
5
6
Data mining Data mining merupakan proses yang penting, di mana metode-metode cerdas diaplikasikan untuk mengekstrak polapola dalam data. Evaluasi pola Evaluasi pola diperlukan untuk mengidentifikasi beberapa pola yang menarik dalam merepresentasikan pengetahuan.
Clustering Clustering merupakan proses dari data mining untuk mengelompokkan kumpulan objek ke dalam kelas-kelas atau cluster sehingga objek-objek dalam satu cluster memiliki kemiripan yang tinggi tetapi tidak mirip terhadap objek dari cluster lain (Han & Kamber, 2006). Ukuran kemiripan dan ketidakmiripan dinilai berdasarkan nilai atribut yang mendeskripsikan objek. Metode yang umum digunakan dalam clustering dapat diklasifikasikan sebagai berikut (Han & Kamber, 2006) : 1
Metode partisi Metode yang membangun berbagai partisi (bagian) kemudian mengevaluasinya dengan beberapa kriteria. Metode ini akan memindahkan objek dari satu kelompok ke kelompok lain.
2
Metode hirarki Metode yang membangun dekomposisi hirarki dari himpunan data (objek) menggunakan beberapa kriteria.
3
Metode berdasarkan kepekatan Metode yang berdasarkan kepada keterhubungan diantara objek dan fungsi kepadatan.
2
4
5
Metode berdasarkan grid Metode yang berdasarkan kepada struktur multiple level granularity. Metode berdasarkan model Metode yang menjadikan sebuah model merupakan patokan bagi setiap cluster mendapatkan model yang tepat terhadap suatu data dengan model yang diberikan.
Agglomerative Hirarchical Clustering Agglomerative hirarchical clustering adalah metode clustering hirarki yang pada langkah awal menganggap masing-masing objek adalah cluster, cluster digabungkan pada coarser partition atau partisi yang lebih kasar dan proses penggabungan tersebut berlangsung sampai trivial partition terbentuk yaitu ketika semua objek berada pada satu cluster (Kantardzic 2003). Sebagian besar algoritme agglomerative hirarchical clustering terdiri dari algoritme single link atau algoritme complete link. Pada single link method jarak antara dua cluster adalah minimum jarak antardua objek dari dua cluster (minimum jarak antardua cluster). Sedangkan complete link method jarak antardua cluster adalah maksimum jarak antara dua objek dari dua cluster (maksimum jarak antardua cluster) (Kantardzic 2003).
ROCK (RObust Clustering using linKs) ROCK adalah algoritme clustering hirarki aglomeratif untuk mengelompokkan data kategorik (Guha et al. 2000). ROCK merupakan algoritme yang membangun link untuk menggabungkan cluster-cluster-nya dan tidak menggunakan distance seperti algoritme clustering pada umumnya (Guha et al. 2000). Link antar dua tuple pada ROCK adalah nilai common neighbor yang mereka miliki dari data set. Common neighbor yaitu jumlah tetangga yang sama diantara dua objek data. Algoritme ROCK akan berhenti ketika (M.Dutta et al. 2005) : 1
Jumlah dari cluster yang diharapkan sudah terpenuhi,
2
Tidak ada lagi link antar cluster-clusternya.
Langkah-langkah dalam algoritme ROCK yaitu (M.Dutta et al. 2005) : 1
Menentukan inisialisasi untuk masingmasing data poin sebagai cluster pada awalnya.
2
Menghitung similaritas antarcluster dengan cluster lainnya dengan menggunakan persamaan :
Data Kategorik
...(1)
Data kategorik yaitu data non-numeric (symbolic) yang variabelnya memiliki dua relasi. Contoh dari data kategorik seperti warna mata, jenis kelamin, dan kewarganegaraan (Kantardzic 2003). Biasanya data kategorik adalah data hasil pengamatan. Data numerik adalah data metric atau data yang merupakan hasil pengukuran.
dan
akan dihitung similaritasnya, k merupakan nomor atribut dan | | adalah jumlah kandidat atribut ke k. Penjumlahan satu perjumlah kandidat atribut dilakukuan untuk atribut yang bukan anggota atribut irisan dan .
Data kategorik diklasifikasikan menjadi dua yaitu : 1. Data nominal yaitu data kategorik yang tak dapat dinyatakan bahwa kategori yang satu lebih baik dari kategori lainnya. Contoh dari data nominal yaitu pria–wanita, ungu– biru. 2. Kategorik ordinal, yaitu data kategorik yang mempunyai urutan tertentu namun jarak antar kategori sulit untuk dinyatakan sama. Contoh dari data ordinal yaitu keadaan baik, sedang, dan buruk.
adalah pasangan cluster yang
3
Mencari nilai nbrlist antarcluster dengan cluster lainnya. Nbrlist yaitu matrik nilai tetangga yang didapat dari threshold yang diberikan (nilai threshold antara 0 dan 1). Suatu objek dan bertetangga jika ...(2)
4
Menghitung link cluster lainnya.
antarcluster dengan antar objek
diperoleh neighbor
jumlah Jika
dari dan .
common
3
bernilai besar maka kemungkinan besar dan berada pada cluster yang sama. 5
Menentukan local heap. Local heap yaitu nilai goodness measure untuk setiap cluster dengan cluster lainnya jika link 0. Goodness measure yaitu persamaan yang menghitung jumlah link dibagi dengan kemungkinan link yang akan terbentuk dilihat dari ukuran cluster-nya. Persamaan untuk mencari goodness measure :
cluster akhir algoritme ROCK ketika ROCK sudah tidak memiliki link antar cluster-nya (M.Dutta, et al. 2005). QROCK tidak lagi menggunakan link untuk menggabungkan cluster-cluster-nya tetapi menggunakan primitif tipe data abstrak MFSET. MFSET (Merge Find Set) atau disjoint set adalah suatu struktur data yang menggunakan dua operasi yaitu : 1
Find: menentukan himpunan yang berisi elemen khusus. Digunakan untuk menentukan dua elemen yang berada pada himpunan yang sama.
2
Merge: menggabungkan dua himpunan menjadi satu himpunan.
...(3) adalah
jumlah
common adalah
MFSET yang digunakan pada QROCK yaitu (M.Dutta et al. 2005 ):
jumlah anggota cluster i dan
adalah
1
jumlah anggota persamaan :
dengan
Merge (A,B) : menggabungkan komponen A dan B.
2
Find (x) : mencari komponen yang salah satu anggota dari komponen tersebut adalah x.
3
Initial (x) : membuat komponen yang hanya berisi elemen x.
neighbor
dari
dan cluster
, j,
...(4) 6
Menentukan global heap. Global heap yaitu nilai maksimum goodness measure antar kolom di baris ke i.
7
Ulangi langkah 5 dan 6 hingga mendapat kan nilai maksimum di global heap dan local heap.
Langkah-langkah dalam algoritme QROCK yaitu (M.Dutta et al. 2005 ) : 1
Menentukan inisialisasi untuk masingmasing data poin sebagai cluster pada awalnya.
2
Menghitung similaritas antar dengan cluster lainnya menggunakan persamaan (1).
3
Mencari nilai nbrlist antar cluster dengan cluster lainnya.
4
Inisialisasi MFSET yang terdiri dari count, first element, set name, next element.
5
Inisialisasi elemen x adalah anggota himpunan data.
Time complexity pada saat worst case yaitu dengan
6
Inisialisasi elemen y adalah semua nilai nbrlist x = 1.
n adalah jumlah data,
7
Find nilai A sebagai first element nilai x.
8
Find nilai B sebagai first element nilai y.
neighbor.
9
Jika nilai A B maka merge A dan B, selainnya passed.
QROCK (Quick RObust Clustering using linKs)
10 Ulangi langkah 5 dan 6 selama y berada dalam nbrlist.
8
9
Selama ukuran data > k, dengan k adalah jumlah kelas yang ditentukan lakukan penggabungan cluster yang memiliki nilai local heap terbesar dengan global heap terbesar menjadi satu cluster, tambahkan link antar cluster yang digabungkan, hapus cluster yang digabungkan dari local heap dan update global heap dengan nilai hasil penggabungan. Lakukan langkah 8 hingga menemukan jumlah cluster yang diharapkan (k) atau cluster akan dibangkitkan secara otomatis ketika tidak ada lagi link antar clusternya.
neighbor, dan
maksimum jumlah
nilai rata-rata jumlah
cluster dengan
QROCK adalah algoritme yang memiliki metode yang lebih efisien untuk menghasilkan 4
Time complexity dari algoritme QROCK yaitu
.
Evaluasi Cluster Cluster validation adalah kemampuan untuk mendeteksi ada atau tidaknya suatu stuktur tidak acak dalam data. Beberapa aspek penting dalam cluster validation yaitu (Tan et al. 2006) : 1
..(5)
Menentukan clustering tendency dari data. Clustering tendency yaitu kecenderungan sifat dari suatu cluster.
Demikian juga dengan separation antar dua cluster dapat dihitung dari jumlah bobot link suatu objek data dalam suatu cluster ke objek data di cluster lain dengan persamaan : ...(6)
2
Menentukan jumlah cluster yang tepat.
3
Mengevaluasi seberapa baik hasil analisis cluster tanpa diberikan informasi eksternal.
4
Membandingkan hasil analisis cluster terhadap hasil eksternal yang diketahui, misalnya label kelas eksternal.
Fungsi proximity dapat berupa similarity, dissimilarity atau fungsi kuantitas lainnya. Dikarenakan fungsi kuantitas dari algoritme ROCK dan QROCK adalah fungsi goodness pada persamaan (3) maka persamaan yang digunakan untuk menghitung nilai evaluasi cluster-nya adalah persamaan goodness measure dibagi m yaitu cluster yang terbentuk. Persamaan cohesion dan separation tersebut yaitu :
5
Membandingkan dua himpunan cluster untuk menentukan yang lebih baik.
...(7)
Pada aspek satu, dua dan tiga tidak diperlukan informasi eksternal yang merupakan teknik unsupervised, sedangkan aspek empat membutuhkan informasi eksternal. Aspek empat termasuk teknik supervised. Aspek lima dapat dilakukan pada teknik supervised atau unsupervised. Perhitungan evaluasi dapat digolongkan menjadi tiga jenis yaitu (Tan et al. 2006) : 1
2
3
Unsupervised. Mengukur goodness dari struktur clustering tanpa informasi eksternal. Besaran unsupervised dibagi dua yaitu : cluster cohesion (seberapa dekat suatu objek dalam suatu cluster) dan cluster separation atau isolation (perbedaan atau seberapa jauh suatu cluster dengan cluster lainnya). Supervised. Mengukur kecocokan struktur clustering dengan struktur eksternal. Relative. Membandingkan clustering yang beda. Besaran evaluasi cluster relative merupakan teknik unsupervised atau supervised yang digunakan untuk perbandingan.
Algoritme ROCK dan QROCK merupakan teknik unsupervised dan graphbase sehingga cohesion didapatkan dengan menjumlahkan bobot link dari proximity graf yang terhubungkan pada cluster dengan persamaan (Tan et al. 2006) :
...(8) Dengan
sama dengan persamaan (4).
Semakin tinggi nilai total cohesion dan semakin minimum nilai separation maka semakin baik suatu cluster terhadap yang lainnya. Karena fungsi yang digunakan adalah fungsi goodness measure yang semakin besar nilai goodness-nya maka semakin dekat suatu objek cluster dengan objek lainnya. Outlier Outlier menurut ilmu statistik adalah data yang terdapat di atas batas atas atau di bawah batas bawah rentangan data (Huntsbergen 1987). Outlier adalah data yang tidak mengikuti tingkahlaku umum sebagian besar data, perbedaan yang penting atau sesuatu yang tidak konsisten dalam himpunan data (Kantardzic 2003).
METODE PENELITIAN Proses Knowledge Discovery in Database Penelitian ini akan dianalisis dengan menggunakan langkah-langkah Knowledge Discovery in Database (KDD) (Han & Kamber, 2006) dengan tahapan seperti pada Gambar 2. 5
