laporan_kelompok

5/17/2018 laporan_kelompok - slidepdf.com

http://slidepdf.com/reader/full/laporankelompok 1/15

BAB I

PENDAHULUAN

1.1 Latar Belakang.

Data Mining (DM) adalah salah satu bidang yang berkembang pesat karena

besarnya kebutuhan akan nilai tambah dari database skala besar yang makin banyak

terakumulasi sejalan dengan pertumbuhan teknologi informasi. Definisi umum dari

DM itu sendiri adalah serangkaian proses untuk menggali nilai tambah berupa

pengetahuan yang selama ini tidak diketahui secara manual dari suatu kumpulan.

Mining berarti usaha untuk mendapatkan sedikit barang berharga dari sejumlah besar material dasar. Karena itu DM sebenarnya memiliki akar yang panjang dari

bidang ilmu seperti kecerdasan buatan (artificial intelligent), machine learning,

statistic dan database. Beberapa teknik yang sering disebut-sebut dalam literatur

DM antara lain : clustering, classification, association rule mining, neural network,

genetic algorithm dan lain-lain. Yang membedakan persepsi terhadap DM adalah

perkembangan teknik-teknik DM untuk aplikasi pada database skala besar. Sebelum

populernya DM, teknik-teknik tersebut hanya dapat dipakai untuk data skala kecil

saja.

Data Clustering merupakan salah satu metode Data Mining yang bersifat

tanpa arahan (unsupervised ). Ada dua jenis data clustering yang sering

dipergunakan dalam proses pengelompokan data yaitu hierarchical (hirarki) data

clustering dan non-hierarchical (non hirarki) data clustering. K-Means merupakan

salah satu metode data clustering non hirarki yang berusaha mempartisi data yang

ada ke dalam bentuk satu atau lebih cluster atau kelompok. Metode ini mempartisi

data ke dalam cluster atau kelompok sehingga data yang memiliki karakteristik

yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang

mempunyai karakteristik yang berbeda dikelompokkan ke dalam kelompok yang

lain. Adapun tujuan dari data clustering ini adalah untuk meminimalisasikan

objective function yang diset dalam proses clustering, yang pada umumnya

berusaha meminimalisasikan variasi di dalam suatu cluster dan

memaksimalisasikan variasi antar cluster.



1.2 Rumusan Masalah.

Sesuai dengan latar belakang di atas, permasalahan yang timbul adalah

sebagai berikut.

1. Bagaimanakah metode K-Means Clustering itu?

1.3 Batasan Masalah.

Mengingat luasnya jangkauan masalah diatas, laporan ini dibatasi

berdasarkan hal-hal sebagai berikut.

1 Pengertian Clustering.2 Pengertian K-Means.

3 Contoh perhitungan k-means.

1.4 Tujuan.

Dari rumusan masalah di atas, tujuan yang ingin dicapai adalah sebagai

berikut..

1. Mengetahui dan memahami metode Clustering dalam data mining

khususnya K-Means Clustering .

2



BAB II

PEMBAHASAN

Definisi sederhana dari data mining adalah ekstraksi informasi atau pola

yang penting atau menarik dari data yang ada di database yang besar (Yudho,

2003:1). Dalam jurnal ilmiah, data mining juga dikenal dengan nama Knowledge

Discovery in Databases (KDD). Menurut Taufik Abidin, data mining atau juga

dikenal dengan sebutan knowledge discovery in database lahir karena data yang

terkumpul sekarang ini sudah mencapai terrabyte (1000 gigabytes). Data mining

merupakan proses mencari pola-pola menarik dalam data.

Beberapa teknik yang sering disebut-sebut dalam literatur DM antara lain :

Clustering, Classification, Association Rule Mining (ARM), Neural Network,

Genetic Algorithm dan lain-lain.

2.1 Classification.

Classification adalah proses untuk menemukan model atau fungsi yang

menjelaskan atau membedakan konsep atau kelas data, dengan tujuan untuk dapat

memperkirakan kelas dari suatu objek yang labelnya tidak diketahui. Model itu

sendiri bisa berupa aturan “jika-maka”, berupa decision tree, formula matematis

atau neural network .

Decision tree adalah salah satu metode classification yang paling populer

karena mudah untuk diinterpretasi oleh manusia. Algoritma decision tree yang

paling terkenal adalah C4.5, tetapi akhir-akhir ini telah dikembangkan algoritma

yang mampu menangani data skala besar yang tidak dapat ditampung di main

memori seperti RainForest . Metode-metode classification yang lain adalah

Bayesian, neural network, genetic algorithm, fuzzy, case-based reasoning, dan

k-nearest neighbor .

Proses classification biasanya dibagi menjadi dua fase : learning dan test .

Pada fase learning , sebagian data yang telah diketahui kelas datanya diumpankan

untuk membentuk model perkiraan. Kemudian pada fase test model yang sudah

terbentuk diuji dengan sebagian data lainnya untuk mengetahui akurasi dari model

3



tsb. Bila akurasinya mencukupi model ini dapat dipakai untuk prediksi kelas data

yang belum diketahui.

2.2 Clustering.

Berbeda dengan association rule mining dan classification dimana kelas data

telah ditentukan sebelumnya, clustering melakukan pengelompokan data tanpa

berdasarkan kelas data tertentu. Pengklasteran (clustering) merupakan salah satu

bentuk dari proses pembelajaran data yang tidak terbimbing, dimana obyek yang

akan dikelompokkan tidak memiliki label atau tanda. Klasterisasi berupaya untuk

melakukan pengaturan agar obyek yang dikelompokkan berada dalam kelompok

yang anggotanya serupa atau homogen. Clustering dapat didefinisikan sebagai

proses mengelompokkan sekumpulan objek sedemikian hingga objek dalam satu

grup lebih serupa karakteristiknya dibandingkan dengan objek-objek di grup-grup

yang lain. Bahkan clustering dapat dipakai untuk memberikan label pada kelas data

yang belum diketahui. Karena itu clustering sering digolongkan sebagai metode

unsupervised learning . Analisa grup sangat bermanfaat untuk mengetahui dan

memahami distribusi data dan sering sekali digunakan sebagai proses awal sebelum

teknik-teknik data mining lain digunakan.

Prinsip dari clustering adalah memaksimalkan kesamaan antar anggota satu

kelas dan meminimumkan kesamaan antar kelas atau cluster . Clustering dapat

dilakukan pada data yang memiliki beberapa atribut yang dipetakan sebagai

multidimensi. Secara garis besar teknik-teknik clustering dapat dikategorikan dalam

2 kelompok. Teknik clustering berdasarkan hirarki (hierarchy-based) dan

berdasarkan partisi ( Distance-based ).

Hierarchy-based clustering terbagi menjadi 2 jenis yaitu agglomerative dan

divisive. Pendekatan secara agglomerative (bottom-up) memulai clustering dengan

mengambil setiap objek sebagai objek yang terpisah satu sama lainnya dan

menggabungkannya satu persatu berdasarkan suatu metric (measurement ) atau lebih

singkatnya menggabungkan cluster kecil menjadi cluster lebih besar. Sebaliknya,

divisive (top-down) memulai clustering dengan menganggap bahwa semua objek

berada dalam satu cluster kemudian memecahkannya satu persatu sehingga pada

4



akhirnya setiap objek merupakan suatu cluster tersendiri atau dengan kata lain

memecah cluster besar menjadi cluster yang lebih kecil.

Nonhierarchical atau partitional clustering membuat clusters dalam satu

langkah sebagai lawan dari beberapa langkah. Hanya satu set clusters yang dibuat,

walaupun beberapa set berbeda dari cluster mungkin dibuat secara internal dengan

berbagai algoritma. Masalah dengan algoritma partitional adalah mereka berbeda

dari combinatorial explosion dalam kaitan dengan banyaknya kemungkinan

pemecahan masalah.

Banyak algoritma clustering memerlukan fungsi jarak untuk mengukur

kemiripan antar data, diperlukan juga metode untuk normalisasi bermacam atribut

yang dimiliki data. Beberapa kategori algoritma clustering yang banyak dikenal

adalah metode partisi dimana pemakai harus menentukan jumlah k partisi yang

diinginkan lalu setiap data dites untuk dimasukkan pada salah satu partisi.

2.3 K-Means Clustering.

K-means adalah suatu iterasi algoritma clustering dimana items

dipindahkan antar set clustering sampai set yang diinginkan tercapai. Seperti yang

dijelaskan bagian sebelumnya, K-Means merupakan salah satu metode data

clustering non hirarki yang berusaha mempartisi data yang ada ke dalam bentuk

satu atau lebih cluster . Metode ini mempartisi data ke dalam cluster sehingga data

yang memiliki karakteristik yang sama dikelompokkan ke dalam satu cluster yang

sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke

dalam kelompok yang lain. Adapun tujuan dari data clustering ini adalah untuk

meminimalisasikan objective function yang diset dalam proses clustering, yang

pada umumnya berusaha meminimalisasikan variasi di dalam suatu cluster danmemaksimalisasikan variasi antar cluster . Data clustering menggunakan metode K-

Means ini secara umum dilakukan dengan algoritma dasar sebagai berikut:

5



K-means Algorithm

Input: D = (t 1 , t 2 ,…...,t n ) // Set of elements

K // Number of desired clusters

Output:

K // Set of clusters

K-means algoritma:

assign initial values for means m1 ,m2 ,…..mk ;

repeat

assign each item t 1 to the cluster which has the closest mean;

calculate new mean for each cluster;

until convergence criteria is met;

Penjelasan Algoritma K-Means

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

4. Alokasikan masing-masing data ke centroid /rata-rata terdekat

5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai centroid .

Distance space diimplementasikan dalam menghitung jarak (distance)

antara data dan centroid termasuk di antaranya L1 ( Manhattan/City Block ) distance

space[9], L2 ( Euclidean) distance space[3], dan Lp (Minkowski) distance space[9].

Jarak antara dua titik x1 dan x2 pada Manhattan/City Block distance space dihitung

dengan menggunakan rumus sebagai berikut:

(1)

dimana:

p : Dimensi data

| . | : Nilai absolut

Sedangkan untuk L2 ( Euclidean) distance space, jarak antara dua titik dihitung

menggunakan rumus sebagai berikut[3]:

6



(2)

dimana:

p : Dimensi data

Lp ( Minkowski) distance space yang merupakan generalisasi dari beberapa

distance space yang ada seperti L1 ( Manhattan/City Block ) dan L2 ( Euclidean),

juga telah diimplementasikan. Tetapi secara umum distance space yang sering

digunakan adalah Manhattan dan Euclidean. Euclidean sering digunakan karena

penghitungan jarak dalam distance space ini merupakan jarak terpendek yang bisa

didapatkan antara dua titik yang diperhitungkan, sedangkan Manhattan sering

digunakan karena kemampuannya dalam mendeteksi keadaan khusus seperti

keberadaaan outliers dengan lebih baik.

Ada dua cara 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 dinyatakan sebagai anggota

cluster yang satu dan tidak menjadi anggota cluster lainnya, dan dengan cara fuzzy,

dimana masing-masing data item diberikan nilai kemungkinan untuk bisa

bergabung ke setiap cluster yang ada. Kedua cara pengalokasian tersebut

diakomodasikan pada dua metode Hard K-Means dan Fuzzy K-Means. Perbedaan

di antara kedua metode ini terletak pada asumsi yang dipakai sebagai dasar

pengalokasian.

Hard K-Means

Pengalokasian kembali data ke dalam masing-masing cluster dalam metode Hard

K-Means didasarkan pada perbandingan jarak antara data dengan centroid setiap

cluster yang ada. Data dialokasikan ulang secara tegas ke cluster yang mempunyai

centroid terdekat dengan data tersebut. Pengalokasian ini dapat dirumuskan sebagai

berikut:

7



(3)

dimana:

ik a : Keanggotaan data ke-k ke cluster ke-i

i v : Nilai centroid cluster ke-i

Fuzzy K-Means

Metode Fuzzy K-Means (atau lebih sering disebut sebagai Fuzzy C-Means)

mengalokasikan kembali data ke dalam masing-masing cluster dengan

memanfaatkan teori Fuzzy. Teori ini mengeneralisasikan metode pengalokasian

yang bersifat tegas (hard ) seperti yang digunakan pada metode Hard K-Means.

Dalam metode Fuzzy K-Means dipergunakan variable membership function, ik u ,

yang merujuk pada seberapa besar kemungkinan suatu data bisa menjadi anggota ke

dalam suatu cluster. Pada Fuzzy K-Means yang diusulkan oleh Bezdek,

diperkenalkan juga suatu variabel m yang merupakan weighting exponent dari

membership function. Variabel ini dapat mengubah besaran pengaruh dari

membership function, ik u, dalam proses clustering menggunakan metode Fuzzy K-

Means. m mempunyai wilayah nilai m>1. Sampai sekarang ini tidak ada ketentuan

yang jelas berapa besar nilai m yang optimal dalam melakukan proses optimasi

suatu permasalahan clustering. Nilai m yang umumnya digunakan adalah 2.

Membership function untuk suatu data ke suatu cluster tertentu dihitung

menggunakan rumus sebagai berikut:

(4)

dimana:

ik u : Membership function data ke-k ke cluster ke-i

i v : Nilai centroid cluster ke-i

m : Weighting Exponent

Membership function, ik u , mempunyai wilayah nilai 0≤ ik u ≤1. Data item yang

mempunyai tingkat kemungkinan yang lebih tinggi ke suatu kelompok akan

8



mempunyai nilai membership function ke kelompok tersebut yang mendekati angka

1 dan ke kelompok yang lain mendekati angka 0.

Diagram Aktivitas K-Means Clustering.

2.4 K-Means Numerical Example.

Misalkan kita memiliki beberapa objek (4 jenis obat-obatan) dan obyek

masing-masing memiliki dua atribut atau fitur seperti yang ditunjukkan dalam tabel

di bawah ini. Tujuan pengelompokan adalah kelompok benda-benda ke dalam K =

2 kelompok obat yang didasarkan pada dua fitur (pH dan indeks berat).

Object attribute 1 (X): weight index attribute 2 (Y): pHMedicine A 1 1

Medicine B 2 1

Medicine C 4 3

Medicine D 5 4

Setiap obat merupakan salah satu titik dengan dua atribut (X, Y) yang kita dapat

merepresentasikan sebagai koordinat dalam ruang atribut seperti yang ditunjukkan

pada gambar di bawah ini.

9



Gambar 1.

1. nilai awal dari centroid: Misalkan kita menggunakan obat A dan obat B sebagai

centroid pertama. Biarkan c1 dan c2 menunjukkan koordinat dari centroid, lalu

c1 (1,1) dan c2 (2,1).

Gambar 2.

2. Objek-centroid jarak: kami menghitung jarak antara cluster centroid untuk tiap

objek. Mari kita gunakan jarak Euclidean, maka kita memiliki matriks jarak

pada iterasi 0 adalah

10



Setiap kolom dalam matriks jarak melambangkan objek. Baris pertama dari

matriks jarak sesuai dengan jarak tiap objek ke centroid pertama dan baris

kedua adalah jarak tiap objek ke centroid kedua. Sebagai contoh, jarak dari

obat C = (4, 3) untuk centroid yang pertama c1 (1,1) adalah

dan dengan jarak ke pusat kedua c2 (2,1) adalah

dan seterusnya.

3. Objek clustering: Kami menetapkan setiap obyek berdasarkan jarak minimal.

Jadi, obat A diberikan untuk kelompok 1, B obat untuk kelompok 2, C obat ke

grup 2 dan obat D untuk kelompok 2. Unsur Grup matriks di bawah ini adalah

1 jika dan hanya jika objek diberikan ke grup tersebut.

4. Iterasi-1, menentukan centroid: Mengetahui anggota masing-masing kelompok,

sekarang kita menghitung centroid baru setiap kelompok berdasarkan

keanggotaan baru ini. Kelompok 1 hanya memiliki satu anggota centroid

sehingga tetap. Grup 2 kini memiliki tiga anggota, sehingga centroid adalah

rata-rata koordinasi antara tiga anggota yaitu:

11



Gambar 3.

5. Iterasi-1, Obyek-centroid jarak: Langkah selanjutnya adalah menghitung jarak

dari semua obyek ke centroid baru. Serupa dengan langkah 2, kita telah matriks

jarak pada iterasi 1 adalah

6. Iterasi-1, clustering Objects: Serupa dengan langkah 3, kita memberikan setiap

obyek berdasarkan jarak minimal. Berdasarkan matriks jarak yang baru, kita bergerak B obat ke grup 1 sementara semua benda lainnya tetap. Grup matriks

ditunjukkan di bawah ini

7. Iterasi 2, menentukan centroid: Sekarang kita ulangi langkah 4 untuk

menghitung koordinat centroid baru berdasarkan pengelompokan iterasi

12



sebelumnya. Group1 dan kelompok 2 keduanya memiliki dua anggota,

sehingga centroid baru dan

Gambar 4.

8. Iterasi-2, Benda-centroid jarak: Ulangi langkah 2 lagi, kita telah jarak baru

matriks pada iterasi 2 sebagai

9. Iterasi-2, Objek clustering: Sekali lagi, kita memberikan setiap obyek

berdasarkan jarak minimal.

13



10. Kami mendapatkan hasil itu G1=G2. Membandingkan pengelompokan iterasi

terakhir dan iterasi ini menunjukkan bahwa benda-benda tidak bergerak lagi

kelompok. Dengan demikian, perhitungan pengelompokan k-berarti telah

mencapai stabilitas dan tidak iterasi lebih dibutuhkan. Kami mendapatkan hasil

pengelompokan akhir sebagai berikut.

Object attribute 1 (X):

weight index

attribute 2 (Y):

pH

Group

(Result)

Medicine A 1 1 1

Medicine B 2 1 1

Medicine C 4 3 2

Medicine D 5 4 2

14



BAB III

PENUTUP

3.1 Simpulan.

Clustering dapat didefinisikan sebagai proses mengelompokkan sekumpulan

objek sedemikian hingga objek dalam satu grup lebih serupa karakteristiknya

dibandingkan dengan objek-objek di grup-grup yang lain. Prinsip dari clustering

adalah memaksimalkan kesamaan antar anggota satu kelas dan meminimumkan

kesamaan antar kelas atau cluster . K-means adalah suatu iterasi algoritma clustering

dimana items dipindahkan antar set clustering sampai set yang diinginkan tercapai.

K-Means merupakan salah satu metode data clustering non hirarki yang berusaha

mempartisi data yang ada ke dalam bentuk satu atau lebih cluster . Metode ini

mempartisi data ke dalam cluster sehingga data yang memiliki karakteristik yang

sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai

karakteristik yang berbeda dikelompokkan ke dalam kelompok yang lain. Adapun

tujuan dari data clustering ini adalah untuk meminimalisasikan objective function

yang diset dalam proses clustering, yang pada umumnya berusaha

meminimalisasikan variasi di dalam suatu cluster dan memaksimalisasikan variasi

antar cluster.

15

laporan_kelompok

Documents