Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
STUDI KOMPARATIF PENERAPAN METODE HIERARCHICAL, K-MEANS DAN SELF ORGANIZING MAPS (SOM) CLUSTERING PADA BASIS DATA
Undang Syaripudin1, Ijang Badruzaman2, Erwan Yani3, Dede K4, M. Ramdhani5 1, 2 Teknik Informatika UIN Sunan Gunung Djati Bandung 3, 4, 5 AMIK Garut
Abstract This study identifies the results of some test results clustering methods. The data set used in this test method Clustering. The third method of clustering based on these factors than the size of the data set and the extent of the cluster. The test results showed that the SOM algorithm produces better accuracy in classifying objects into matching groups. K-means algorithm is very good when using large data sets and compared with Hierarchical SOM algorithm. Hierarchical grouping and SOM showed good results when using small data sets compared to using k-means algorithm. Keyword: Testing, Clustering. K-means, hierarchical, hierarchical, SOM
1.
relatif cepat dan efisien. Metode hierarki
Pendahuluan Clustering
teknik
dapat dibedakan menjadi dua bagian, yaitu
pengelompokan sejumlah data atau objek
metode penggabungan (agglomerative) dan
ke dalam cluster (group) sehingga setiap
metode
dalam cluster tersebut akan berisi data yang
Pembentukan kelompok dalam metode
semirip mungkin dan berbeda dengan objek
hierarki,
dalam cluster yang lainnya (Santosa B.,
antara lain pautan tunggal (single linkage),
2007). Terdapat beberapa metode clustering
pautan lengkap (complete linkage), dan
diantaranya hierarchical, K-means, self
pautan rata-rata (average linkage). Self
organizing maps (SOM) clustering (Alfina,
Organizing Maps (SOM) merupakan suatu
2012).
tipe Artificial Neural Networks yang di-
K-means
merupakan
merupakan
metode
pemecahan
menggunakan
secara
(devisive).
beberapa
unsupervised.
cara,
clustering yang paling sederhana dan
training
SOM
umum. K-means mempunyai kemampuan
menghasilkan map yang terdiri dari output
mengelompokkan data dalam jumlah yang
dalam dimensi yang rendah (2 atau 3
cukup besar dengan waktu komputasi yang
132
Edisi Juli 2013 Volume VII No. 1
dimensi).
Map
ini
berusaha
ISSN 1979-8911
mencari
property dari input data.
memperkirakan nilai data yang lain. Metode-metode
yang
termasuk
Predictive Data Mining adalah: 2.
1. Klasifikasi: pembagian data ke
Data Mining Data mining merupakan gabungan
dari berbagai bidang ilmu, antara lain basis data,
information
retrieval,
statistika,
algoritma dan machine learning. Bidang ini telah berkembang sejak lama namun makin
dalam beberapa kelompok yang telah ditentukan sebelumnya. 2. Regresi: memetakan data ke suatu prediction variable. 3. Time
series
Analysis:
terasa pentingnya sekarang ini di mana
pengamatan
muncul
atribut dari waktu ke waktu.
keperluan
untuk
mendapatkan
perubahan
nilai
informasi yang lebih dari data transaksi
b. Descriptive: mengidentifikasi pola
maupun fakta yang terkumpul selama
atau hubungan dalam data untuk
bertahun-tahun. Data mining adalah cara
menghasilkan
informasi
baru.
menemukan informasi tersembunyi dalam
Metode
termasuk
dalam
sebuah basis data dan merupakan bagian
Descriptive Data Mining adalah:
dari
1. Clustering: identifikasi kategori
proses
Databases
Knowledge (KDD)
Discovery
untuk
in
menemukan
yang
untuk mendeskripsikan data.
informasi dan pola yang berguna dalam
2. Association Rules: identifikasi
data (Budiarti, 2006). Kegiatan data mining
hubungan antara data yang satu
biasanya dilakukan pada sebuah data
dengan lainnya.
warehouse yang menampung data dalam
3. Summarization: pemetaan data
jumlah besar dari suatu organisasi. Proses
ke
data
deskripsi sederhana.
mining
mencari
informasi
baru,
berharga dan berguna di dalam sekumpulan data bervolume besar dengan melibatkan
dalam
subset
dengan
4. Sequence Discovery: identifikasi pola sekuensial dalam data.
komputer dan manusia serta bersifat iteratif baik melalui proses otomatis ataupun manual. Secara umum, data mining terbagi dalam 2 sifat: a. Predictive:
2.1 Tahapan Data Mining Dalam aplikasinya, data mining
menghasilkan
model
sebenarnya merupakan bagian dari proses
berdasarkan sekumpulan data yang
Knowledge Discovery in Database (KDD),
dapat
bukan sebagai teknologi yang utuh dan
digunakan
untuk
133
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
berdiri sendiri. Data mining merupakan
bertujuan untuk menganalisa hasil
suatu bagian langkah yang penting dalam
penjualan, maka data-data dalam
proses KDD terutama berkaitan dengan
kumpulan seperti ”nama pegawai”,
ekstraksi dan penghitungan pola-pola dari
”umur”, dan sebagainya dapat di-
data yang ditelaah, seperti ditunjukan oleh
ignore) dan tidak konsisten.
gambar 1 di bawah ini :
b. Data integration Untuk
menggabungkan multiple
data source. c. Data selection Untuk mengambil data yang sesuai untuk keperluan analisa. d. Data transformation Untuk mentransformasikan data ke dalam bentuk yang lebih sesuai untuk data mining. e. Data Mining Proses terpenting dimana metode tertentu
diterapkan
untuk
menghasilkan data pattern. f. Pattern evaluation Untuk
mengidentifikasi
interenting
patterns
apakah yang
Gambar 1 Tahapan pada proses
didapatkan sudah cukup mewakili
knowledge discovery
knowledge berdasarkan perhitungan tertentu.
a. Data cleaning
g. Knowledge presentation
Untuk menghilangkan data noise
Untuk
(data
knowledge yang sudah didapatkan
yang
tidak
relevan/berhubungan
langsung
mempresentasikan
dari user.
dengan tujuan akhir proses data mining, misal: data mining yang
134
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
2.2 Studi Komparatif
3.
Clustering
Studi komparatif terdiri dari dua
Clustering
merupakan
proses
suku kata yaitu “studi” dan “komparatif”.
membuat pengelompokan sehingga semua
Dalam kamus bahasa Indonesia “studi”
anggota dari setiap partisi mempunyai
berarti
telaah
persamaan berdasarkan matrik tertentu
Sedangkan
(Santosa, 2007). Clustering juga dikenal
penelitian,
(Depdiknas, “komparatif” berdasarkan
kajian
2007). yaitu
atau
berkenaan
perbandingan
atau
sebagai
unsupervised
learning
yang
(Depdiknas,
membagi data menjadi kelompok-kelompok
2007). Jadi jika pengertian di atas disatukan
atau clusters berdasarkan suatu kemiripan
maka pengertian studi komparatif adalah
atribut-atribut di antara data tersebut.
penelitian ilmiah atau kajian berdasarkan
Karakteristik tiap cluster tidak ditentukan
dengan perbandingan. Pendapat Aswarni
sebelumnya,
yang dikutip Suharsimi Arikunto (1997 :
kemiripan
236)
dalamnya.
menyebutkan
bahwa
“Penelitian
melainkan data
yang
tercermin
dari
terkelompok
di
komparatif akan menemukan persamaanpersamaan
dan
perbedaan-perbedaan
3.1 Analisis Clustering
tentang benda, orang, prosedur kerja, ide,
Analisis Clustering adalah proses
kritik terhadap orang, kelompok, terhadap
pengelompokan obyek ke dalam subsets
suatu idea atau suatu prosedur kerja”.
yang
mempunyai
arti
dalam
konteks
Pendapat lain, Mohammad Nasir
masalah tertentu (Tias, 2009). Obyek
(1988 : 68) mengatakan bahwa “Studi atau
dengan demikian diorganisir ke dalam suatu
penelitian
sejenis
penyajian efisien dan bermanfaat. Tidak
penelitian deskriptif yang ingin mencari
sama dengan klasifikasi, clustering tidak
jawaban secara mendasar tentang sebab
bersandar pada kelas sudah ada. Clustering
akibat, dengan menganalisa faktor-faktor
dikenal sebagai suatu metode pelajaran
penyebab terjadinya atau munculnya suatu
pembelajaran unsupervised karena tidak ada
fenomena tertentu”.
informasi disajikan tentang “jawaban yang
Jadi penelitian
komparatif
adalah
studi
komparatif
adalah
yang
bertujuan
untuk
benar” untuk obyek yang manapun. Ini dapat
menemukan
hubungan
yang
membandingkan dua variabel atau lebih,
sebelumnya tidak diketahui didalam suatu
untuk mendapatkan jawaban atau fakta
dataset yang kompleks.
apakah ada perbandingan atau tidak dari objek yang sedang diteliti.
Analisis cluster merupakan
suatu
teknik analisa multivariate untuk mencari
135
Edisi Juli 2013 Volume VII No. 1
dan
mengorganisir
ISSN 1979-8911
tentang
skala adalah matrik Minkowski, yang mana
variabel sehingga secara relatif dapat
adalah suatu generalisasi jarak antara titik
dikelompokkan
yang
di dalam Euclidean Space. Jarak Euclidean
homogen atau “cluster” dapat dibentuk.
dapat dianggap sebagai jarak yang paling
Cluster dibentuk dengan metode kedekatan
pendek antar dua poin-poin, dan pada
yang
homogen
dasarnya sama halnya dengan persamaan
(anggota adalah serupa untuk satu sama
Pythagoras ketika digunakan di dalam 2
lain) dan sangat secara eksternal tak sejenis
dimensi. Secara matematis dapat dituliskan
(anggotanya tidak seperti anggota dari
di dalam persamaan berikut :
secara
informasi
dalam
kelompok
internal
harus
cluster yang lain). Analisis cluster dapat menerima suatu data masukan yang beragam. Ini biasanya disebut pengukuran “kesamaan”, dapat juga disebut“kedeka tannya”, dan “kemiripannya”.
Beberapa
merekomendasikan
ahli
Gambar 2. Persamaan Pythagoras
penggunaan
standardisasi data, cluster dapat dihitung dalam skala yang berbeda dan standardisasi akan
memberi
pengukuran
dengan
menggunakan unit yang berbeda.
Ketika menggunakan fungsi jarak Euclidean untuk membandingkan jarak, tidak diperlukan untuk mengkalkulasi akar dua sebab jarak selalu merupakan angka-
Seperti teknik yang lain, analisis cluster menghadapi permasalahan dalam
angka positif. Untuk dua jarak, d1 dan d2 , jika :
beberapa banyak faktor, atau dimensi, atau berapa banyak cluster yang akan dihasilkan. Untuk itu akan dipilih suatu tempat dimana struktur cluster yang stabil untuk jarak yang jauh. Beberapa kemungkinan lain akan mencari
pengelompokan
grup
dengan
struktur cocok atau yang diharapkan.
Gambar 3. Fungsi Jarak Euclidean
Jika sebagian dari suatu atribut
3.2 Fungsi Jarak Pengukuran proximity yang paling umum digunakan, sedikitnya untuk rasio
obyek diukur dengan skala berbeda, maka ketika
menggunakan
fungsi
jarak
136
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
Euclidean, atribut dengan skala yang lebih
pengukuran diambil di dalam unit yang
besar boleh meliputi atribut yang terukur
sama,
pada
berkaitan dengan skala. Skala yang berbeda
skala
yang
lebih
kecil.
Untuk
mencegah masalah ini, nilai-nilai atribut
suatu
keputusan
harus
dibuat
dapat menyebabkan perbedaan clustering.
dinormalisasi untuk terletak diantara 0 dan 1. Fungsi jarak lain mungkin lebih sesuai
4. K-Means
untuk beberapa data. Lebih jelasnya dapat
Tujuan dari data clustering ini
dilihat pada gambar 4 representasi dari
adalah untuk meminimalisasikan objective
jarak terdekat dari 2 titik.
function yang diset dalam proses clustering, yang
pada
umumnya
berusaha
meminimalisasikan variasi di dalam suatu cluster dan memaksimalisasikan variasi antar cluster. Data clustering menggunakan metode
K-Means
ini
secara
umum
dilakukan dengan algoritma dasar sebagai berikut: 1.
Tentukan jumlah cluster
2.
Alokasikan data ke dalam cluster secara random
3.
Hitung centroid/rata-rata dari data yang ada di masing-masing cluster
Gambar 4. Fungsi Euclidean
4.
Alokasikan masing-masing data ke centroid/rata-rata terdekat
Suatu
komponen
penting
pada
algoritma cluster adalah mengukur jarak antara poin-poin data. Jika komponen dari data adalah semua termasuk dalam unit yang sama, mungkin jarak Euclidean yang sederhana cukup sukses mengelompokkan data serupa.
5.
Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai centroid, ada yang di atas nilai threshold yang ditentukan atau apabila perubahan nilai pada objective function yang digunakan di atas nilai threshold
Bagaimanapun, bahkan dalam hal
yang ditentukan.
ini jarak Euclidean kadang-kadang dapat salah.
Di
samping
kedua-duanya
137
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
4.1 Perkembangan Penerapan K-Means Beberapa alternatif penerapan K-
dihitung
menggunakan
rumus
sebagai
berikut:
Means dengan beberapa pengembangan teori-teori
penghitungan
terkait
telah
diusulkan. Hal ini termasuk pemilihan: 1. Distance
space
untuk
menghitung jarak di antara suatu
dimana:
data dan centroid 2. Metode
p : Dimensi data
pengalokasian
data Lp (Minkowski) distance space yang
kembali ke dalam setiap cluster 3. Objective
function
yang
merupakan distance
digunakan
generalisasi
space
yang
dari ada
beberapa seperti
L1
(Manhattan/City Block) dan L2 (Euclidean), juga telah diimplementasikan. Tetapi secara 4.1.1 Distance Space Untuk Menghitung Jarak Antara Data dan Centroid
umum
distance
digunakan
space
adalah
yang
sering
Manhattan
dan
telah
Euclidean. Euclidean sering digunakan
diimplementasikan dalam menghitung jarak
karena penghitungan jarak dalam distance
(distance)
centroid
space ini merupakan jarak terpendek yang
termasuk di antaranya L1 (Manhattan/City
bisa didapatkan antara dua titik yang
Block) distance space, L2 (Euclidean)
diperhitungkan,
distance
(Minkowski)
sering digunakan karena kemampuannya
distance space. Jarak antara dua titik x1 dan
dalam mendeteksi keadaan khusus seperti
x2 pada Manhattan/City Block distance
keberadaaan outliers dengan lebih baik.
Beberapa
antara
space,
distance
data
dan
space
dan
Lp
sedangkan
Manhattan
space dihitung dengan menggunakan rumus sebagai berikut:
4.1.2 Metode Pengalokasian Ulang Data ke Dalam Masing-Masing Cluster Secara mendasar, ada dua cara
dimana: p : Dimensi data | . | : Nilai absolute Sedangkan untuk L2 (Euclidean) distance space, jarak antara dua titik
pengalokasian data kembali ke dalam masing-masing cluster pada saat proses iterasi clustering. Kedua cara tersebut adalah pengalokasian dengan cara tegas (hard), dimana data item secara tegas
138
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
dinyatakan sebagai anggota cluster yang
pendekatan yang digunakan dalam poin
satu dan tidak menjadi anggota cluster
sebelumnya. Untuk metode Hard K-Means,
lainnya, dan dengan cara fuzzy, dimana
objective function yang digunakan adalah
masing-masing data item diberikan nilai
sebagai berikut:
kemungkinan untuk bisa bergabung ke setiap cluster yang ada. Kedua cara pengalokasian
tersebut
diakomodasikan
pada dua metode Hard K-Means dan Fuzzy
dimana:
K-Means. Perbedaan diantara kedua metode
N : Jumlah data
ini terletak pada asumsi yang dipakai
c : Jumlah cluster
sebagai dasar pengalokasian.
aik : Keanggotaan data ke-k ke
Pengalokasian
kembali
data
cluster ke-i
ke
vi : Nilai centroid cluster ke-i
dalam masing-masing cluster dalam metode Hard
K-Means
didasarkan
pada
perbandingan jarak antara data dengan centroid setiap cluster yang ada. Data
5.
Hierarchical Clustering
dengan
pendekatan
dialokasikan ulang secara tegas ke cluster
hierarki mengelompokkan data yang mirip
yang mempunyai centroid terdekat dengan
dalam hierarki yang sama dan yang tidak
data tersebut. Pengalokasian ini dapat
mirip dihierarki yang agak jauh. Ada dua
dirumuskan sebagai berikut:
metode
yang
sering
diterapkan
yaitu
agglomerative hieararchical clustering dan divisive hierarchical clustering (Hartini, 2005). Agglomerative melakukan proses dimana:
clustering dari N cluster menjadi satu
aik : Keanggotaan data ke-k ke
kesatuan cluster, dimana N adalah jumlah
cluster ke-i
data, sedangkan divisive melakukan proses
vi : Nilai centroid cluster ke-i
clustering yang sebaliknya yaitu dari satu cluster menjadi N cluster.
4.1.3 Objective
Function
Yang
Beberapa
metode
hierarchical
clustering yang sering digunakan dibedakan
Digunakan Objective function yang digunakan
menurut cara mereka untuk menghitung
khususnya untuk Hard K-Means dan Fuzzy
tingkat kemiripan. Ada yang menggunakan
K-Means
Single Linkage, Complete Linkage, Average
ditentukan
berdasarkan
pada
139
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
Linkage, Average Group Linkage dan lainlainnya.
Seperti
juga
halnya
4. Ulangi dari langkah kedua dan
dengan
ketiga hingga tersisa sebuah
partition-based clustering, kita juga bisa
cluster.
memilih jenis jarak yang digunakan untuk menghitung tingkat kemiripan antar data. Salah
satu
cara
untuk
mempermudah pengembangan dendogram
Untuk mengukur kemiripan dari objek-objek ini dapat dengan menggunakan cosinus, kovarian, dan korelasi (Santosa, 2006).
untuk hierarchical clustering ini adalah dengan membuat similarity matrix yang
a.
Single Linkage
memuat tingkat kemiripan antar data yang
Input untuk algoritma single linkage
dikelompokkan. Tingkat kemiripan bisa
bisa berujud jarak atau similarities antara
dihitung dengan berbagai macam cara
pasangan-pasangan
seperti dengan Euclidean Distance Space.
Kelompok-kelompok dibentuk dari entities
Berangkat dari similarity matrix ini, kita
individu dengan menggabungkan jarak
bisa memilih lingkage jenis mana yang
paling pendek atau similarities (kemiripan)
akan digunakan untuk mengelompokkan
yang paling besar.
data yang dianalisa. Tugas
Pada
hierarchical
dari
awalnya,
objek-objek.
kita
harus
clustering
menemukan jarak terpendek dalam D =
adalah mengatur sekumpulan objek menjadi
{dik} dan menggabungkan objek-objek yang
sebuah hierarki hingga terbentuk kelompok
bersesuaian misalnya, U dan V , untuk
yang
Berikut
mendapatkan cluster (UV). Untuk langkah
merupakan langkah-langkah yang untuk
(3) dari algoritma di atas jarak-jarak antara
melakakukan hierarchical clustering:
(UV) dan cluster W yang lain dihitung
memiliki
kesamaan.
1. Kelompokkan
setiap
objek
dengan cara
dalam sebuah cluster.
d(UV)W=min {dUW,dVW}
2. Temukan pasangan yang paling
Di sini besaran-besaran dUW dan dVW
mirip untuk dimasukkan ke
berturut-turut adalah jarak terpendek antara
dalam cluster yang sama dengan
cluster-cluster U dan W dan juga cluster-
melihat
cluster V dan W .
data
dalam
matriks
kemiripan. 3. Kedua
objek
kemudian
digabungkan dalam satu cluster.
b.
Complete Linkage Complete
linkage
memberikan
kepastian bahwa semua item-item dalam
140
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
satu cluster berada dalam jarak paling jauh (similaritas
terkecil)
satu
sama
lain.
Algoritma aglomerative pada umumnya dimulai dengan menentukan entri (elemen matriks)
dalam
menggabungkan
D
=
{dik}
objek-objek
Gambar 5. Average Lingkage
dan yang
di mana dik adalah jarak antara objek
bersesuaian misalnya U dan V untuk mendapatkan cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara cluster (UV) dan cluster W yang lain
i dalam cluster (UV) dan objek k dalam cluster W , Nuv dan Nw berturut-turut adalah banyaknya item-item dalam cluster (UV) dan W.
dihitung dengan
d(UV)W=maks{dUW,dVW} Di sini besaran-besaran dUW dan dVW berturut-turut adalah jarak antara tetangga terdekat cluster-cluster U dan W dan juga cluster-cluster V dan W.
6.
Self Organizing Map (SOM) Walaupun proses learning yang
dilakukan SOM mirip dengan Artificial Neural Networks, tetapi proses untuk meng-
c.
Average Linkage Average linkage
assign input data ke map, lebih mirip memperlakukan
jarak antara dua cluster sebagai jarak ratarata antara semua pasangan item-item di mana satu anggota dari pasangan tersebut kepunyaan tiap cluster. Mulai dengan mencari matriks jarak D = {dik} untuk memperoleh
objek-objek
paling
dekat
(paling mirip) misalnya U dan V . Objek objek ini digabungkan untuk membentuk cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara (UV) dan cluster W yang lain ditentukan oleh
dengan K-Means dan kNN Algorithm. Adapun prosedur yang ditempuh dalam melakukan clustering dengan SOM adalah sebagai berikut: 1. Tentukan weight dari input data secara random 2. Pilih salah satu input data 3. Hitung tingkat kesamaan (dengan Eucledian) antara input data dan weight dari input data tersebut dan pilih input data yang memiliki kesamaan dengan weight yang ada (data
ini
disebut
dengan
Best
Matching Unit (BMU))
141
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
4. Perbaharui weight dari input data dengan
mendekatkan
weight
tersebut ke BMU dengan rumus:
BMU,
dan
0
untuk
yang
sebaliknya. Penggunaan fungsi
Wv(t+1) = Wv(t) + Theta(v, t) x Alpha(t) x (D(t) – Wv(t))
Gaussian juga memungkinkan. c. Alpha (t): Learning Coefficient
Dimana :
yang berkurang secara monotonic
a. Wv(t): Weight pada saat ke-t b. Theta
(v,
t):
d. D(t): Input data
Fungsi
e. Tambah
nilai t, sampai t <
neighbourhood yang tergantung
Lambda, dimana Lambda adalah
pada
jumlah iterasi
Lattice
BMU
distance
dengan
Umumnya 7.
neuron yang cukup dekat dengan
antara
neuron
bernilai
1
v. untuk
Perbandingan Algoritma Clustering Perbandingan algoritma clustering dijelaskan pada tabel 1.
Tabel 1 Perbandingan Algoritma Clustering Metode 1.
2.
Hierarchical Clustering
3.
4.
K-Means
Algoritma Kelompokkan setiap objek dalam sebuah cluster. Temukan pasangan yang paling mirip untuk dimasukkan ke dalam cluster yang sama dengan melihat data dalam matriks kemiripan. Kedua objek kemudian digabungkan dalam satu cluster. Ulangi dari langkah kedua dan ketiga hingga tersisa sebuah cluster.
Karakteristik 1. Memberikan hasil variasi kelompok yang banyak, mulai dari masing-masing data sebagai satu kelompok hingga saat semua data bergabung sebagai kelompok tunggal. 2. Metode ini biasanya digunakan untuk alasan pendasar aplikasi, seperti pembuatan taksonomi yang membutuhkan hierarki pengelompokan data. 3. Karena menggunakan teknik yang rakus dalam perosesnya, komputasi metode ini mahal dan kompleks. 4. Penggabungan dua kelompok merupakan keputusan final karena dua kelompok yang sudah digabung tidak bisa dikembalikan seperti semula. 5. Bisa terjadi masalah untuk set data yang mengandung noise, dan data berdimensi tinggi. Biasanya, untuk masalah ini dibantu dengan metode lain secara parsial, seperti k-means.
1. Tentukan jumlah cluster 1. K-means merupakan metode pengelompokan 2. Alokasikan data ke yang sederhana dan dapat digunakan dengan dalam cluster secara mudah.
142
Edisi Juli 2013 Volume VII No. 1
Metode 3.
4.
5.
1. 2. 3.
SOM
8.
4.
Algoritma random Hitung centroid/rata-rata dari data yang ada di masing-masing cluster Alokasikan masingmasing data ke centroid/rata-rata terdekat Kembali ke Step 3, apabila masih ada data yang berpindah cluster Tentukan weight dari input data secara random Pilih salah satu input data Hitung tingkat kesamaan (dengan Eucledian) antara input data dan weight dari input data tersebut dan pilih input data yang memiliki kesamaan dengan weight yang ada (data ini disebut dengan Best Matching Unit (BMU) Perbaharui weight dari input data dengan mendekatkan weight tersebut
Implementasi data uji menjelaskan struktur
tabel
Karakteristik 2. Pada jenis set data tertentu, k-means tidak dapat melakukan segmentasi data dengan baik dimana hasil segmentasinya tidak dapat memberikan pola kelompok yang mewakili karakteristik bentuk alami data. 3. K-means bisa mengalami masalah ketika mengelompokan data yang mengandung outlier.
1. SOM dapat memvisualkan hasil pengelompokan dalam bentuk topografi dua dimensi layaknya peta sehingga memudahkan pengamatan distribusi kelompok hasil pengelompokan. 2. Memerlukan penentuan fungsi keterangan, laju pembelajaran, fungsi pembelajaran, jumlah kelompok, dan jumlah iterasi yang diinginkan. Untuk penentuan parameter ini bisa digunakan cara coba-coba dengan sejumlah nilai, kemudian pilih yang terbaik. 3. Hanya cocok untuk data yang sudah diketahui jumlah kelompoknya dengan mengamati bentuk alami distribusi data. 4. Dalam memberikan hasil pengelompokan, SOM tidak menggunakan fungsi objektif tertentu seperti k-means dan fuzzy c-means sehingga untuk suatu kondisi yang sudah optimal pada suatu iterasi, SOM tidak akan menghentikan iterasinya selama jumlah iterasi yang ditentukan belum tercapai. Hal ini juga berlaku ketika hasil kelompok yang didapatkan belum optimal, tetapi jumlah iterasi yang ditentukan sudah tercapai sehingga hasilnya menjadi kurang sesuai dengan yang diharapkan (belum optimal). Oleh karena itu, SOM tidak menjamin konvergensi hasil pengelompokan.
menggunakan spreadsheet program, data uji
Implementasi Data Uji
mengenai
ISSN 1979-8911
ini
merupakan
tabel
yang
diolah
penyusunnya
menggunakan software Microsoft Offices
adapun pembuatan data dilakukan dengan
Excel. Contoh data di bawah ini yang dibuat
143
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
oleh software tersebut. Adapun contoh
bawah ini :
implementasi dapat dilihat pada gambar 3 di
Gambar 4. Data Uji (menggunakan software spreadsheet )
9.
adalah time series. Data set ini disimpan
Hasil Pengujian
dalam file ASCII, 600 baris, 60 kolom,
8.1 Pengujian Metode Clustering Data set yang digunakan untuk
untuk membedakan data set besar dan kecil
menguji algoritma klasterisasi diperoleh dari
data set dibagi dua kelompok menjadi
situs: (Http://kdd.ics.uci.edu/) atau dari situs
kumpulan data (200 baris dan 20 kolom).
lain,
yaitu,
Ketiga metode clustering dibandingkan
(http://www.kdnuggets.com/datasets). Data
berdasarkan faktor-faktor yang terdapat
set untuk menguji algoritma klasterisasi
pada tabel 1 sebagai berikut:
Tabel 2. Pengujian data Clustering Metode Hierarchical K-means
Dataset
Klaster
Basar dan
Banyak dan
Kecil
Sedikit
Basar dan
Banyak dan
144
Edisi Juli 2013 Volume VII No. 1
SOM
ISSN 1979-8911
Kecil
Sedikit
Basar dan
Banyak dan
Kecil
Sedikit
Menurut jumlah cluster k kecuali
clustering dengan algoritma lain, pohon
untuk metode hierarki, semua algoritma
hierarki dipotong pada dua tingkat yang
klasterisasi
membutuhkan
berbeda untuk mendapatkan nomor yang
pengaturan k. Disini, kinerja algoritma yang
sesuai cluster (8, 16, 32 dan 64). hasilnya,
berbeda untuk berbagai k dibandingkan
sebagai nilai k menjadi lebih besar kinerja
untuk menguji kinerja yang terkait dengan k.
algoritma SOM menjadi lebih rendah.
Untuk
untuk
Namun, kinerja k-means algoritma menjadi
membuat perbandingan lebih mudah, k yang
lebih baik dari algoritma hierarki. Dapat
dipilih sama dengan 8, 16, 32, dan 64.
dilihat
Untuk
dibandingkan
menyederhanakan
membandingkan
dan
pada
tabel
2
di
bawah
ini
hierarchical
Tabel 3. Hubungan antara jumlah cluster dan kinerja algoritma. Performance
Number Of Cluster
Hirarki
K-means
SOM
8
65
63
59
16
74
71
67
32
87
84
78
64
92
89
85
Menurut ukuran data set, data set besar digunakan terdiri dari 600 baris dan 60
kolom dan data set kecil menggunakan 200 baris dan 20 kolom. Data set
kecil 145
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
diekstraksi sebagai bagian dari dataset besar.
menunjukkan
hasil
yang
baik
bila
Kualitas k-means menjadi sangat baik ketika
menggunakan data set kecil, hasil pengujian
menggunakan data set besar. Dua algoritma
dapat dilihat pada tabel 3 di bawah ini.
hierarchical clustering dan algoritma SOM
Tabel 3. Pengaruh ukuran data pada algoritma. K=32 Data Size
Hirarki
K-means
SOM
36000
850
910
830
4000
91
95
89
besar dibanding dengan algoritma
10. Kesimpulan Setelah pengujian
menganalisis
algoritma
clustering
menjalankan algoritma tersebut
hasil dan
SOM dan Hierarchical. 3. Pengelompokan
hierarchical
dan
dengan
SOM menunjukkan hasil yang baik
faktor dan situasi yang berbeda, maka
saat menggunakan data set kecil
kesimpulan yang diperoleh sebagai berikut:
dibanding menggunakan algoritma k-
1. Algoritma akurasi
SOM
yang
lebih
menghasilkan baik dalam
means. 4. Sebagai
kesimpulan
umum,
mengelompokan objek ke dalam
algoritma partisi (seperti k-means)
kelompok yang cocok dari pada
yang direkomendasikan untuk data
algoritma k-means dan Hierarchical.
set
2. Algoritma K-means menjadi sangat
besar
sementara
algoritma
hierarchical clustering dan SOM
baik ketika menggunakan data set
146
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
yang direkomendasikan untuk data set kecil. 5. Aplikasi
K. Arai and A. R. Barakbah. 2007. "Hierarchical
bermanfaat
untuk
K-means:
an
algorithm for centroids initialization
mengetahui pengelompokan data set
for Kmeans,". Saga University.
yang dihasilkan oleh algoritma k-
Alfina, Tahta. 2012. Analisa Perbandingan
means, hierarchical dan SOM.
Metode Hierarchical Clustering, Kmeans dan Gabungan Keduanya dalam
Daftar Pustaka
Cluster
Data.
Institut
Teknologi Sepuluh Nopember. Santosa, Budi. 2007. Data Mining. Teknik Pemanfaatan Data untuk Keperluan
Latiffaturrahman. 2010. perbandingan hasil
Bisnis, First Edition ed. Yogyakarta:
penggerombolan metode k-means,
Graha Ilmu.
fuzzy k-means dan two step cluster. Institut Pertanaian Bogor.
Prasetyo, Eko. 2012. Data Mining Konsep dan Aplikasi Menggunakan Matlab.
Wahanani, Nursinta Adi. 2012. Optimasi Clustering
Yogyakarta : penerbit andi.
K-Means
Dengan
Algoritma Genetika Multiobyektif. Eisen, M. 1998. Cluster and Tree View Institut Pertanaian Bogor. Manual. Stanford University. Japan. Shandy, Liesca Levy. 2008. Perbandingan Abu Abbas, Osama. 2007. Comparisons Metode Diskretisasi Data Partisi Between
Data
Algorithms.
Computer
Clustering Intuitif dan K-Means Clustering Science Terhadap
Pembuatan
Pohon
Department, Yarmouk University, Keputusan.
Institut
Pertanaian
Jordan Bogor.
147
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
Edward. 2006. Clustering Menggunakan Self
Organizing
Maps.
Institut
Pertanaian Bogor. Fatansyah. 1999. Basis Data. Bandung: Informatika.
148
Edisi Juli 2013 Volume VII No. 1
ISSN 1979-8911
149
