Data Mining
Penggalian data (bahasa Inggris: data mining) adalah ekstraksi pola
yang menarik dari data dalam jumlah besar [1]. Suatu pola dikatakan menarik
apabila pola tersebut tidak sepele, implisit, tidak diketahui sebelumnya, dan
berguna. Pola yang disajikan haruslah mudah dipahami, berlaku untuk data yang
akan diprediksi dengan derajat kepastian tertentu, berguna, dan baru.
Penggalian data memiliki beberapa nama alternatif, meskipun definisi eksaknya
berbeda, seperti KDD (knowledge discovery in database), analisis pola,
arkeologi data, pemanenan informasi, dan intelegensia bisnis. Penggalian data
diperlukan saat data yang tersedia terlalu banyak (misalnya data yang diperoleh
dari sistem basis data perusahaan, e-commerce, data saham, dan data bioinformatika),
tapi tidak tahu pola apa yang bisa didapatkan.
Apriori
Algoritma Apriori adalah algoritma paling terkenal untuk menemukan
pola frekuensi tinggi. Pola frekuensi tinggi adalah pola-pola item di dalam
suatu database yang memiliki frekuensi atau support di atas ambang batas
tertentu yang disebut dengan istilah minimum support.
Pola frekuensi tinggi ini digunakan untuk menyusun aturan
assosiatif dan juga beberapa teknik data mining lainnya.
Algoritma Apriori dibagi menjadi beberapa tahap yang disebut
iterasi atau pass. Tiap iterasi menghasilkan pola frekuensi tinggi dengan
panjang yang sama dimulai dari pass pertama yang menghasilkan pola frekuensi
tinggi dengan panjang satu. Di iterasi pertama ini, support
dari setiap item dihitung dengan men-scan database. Setelah support
dari setiap item didapat, item yang memiliki support diatas minimum support
dipilih sebagai pola frekuensi tinggi dengan panjang 1 atau sering disingkat
1-itemset. Singkatan k-itemset berarti satu set yang terdiri dari k item.
Iterasi kedua menghasilkan 2-itemset yang tiap set-nya memiliki dua
item. Pertama dibuat kandidat 2-itemset dari kombinasi semua 1-itemset. Lalu
untuk tiap kandidat 2-itemset ini dihitung support-nya dengan men-scan
database. Support disini artinya jumlah transaksi
dalam database yang mengandung kedua item dalam kandidat 2-itemset.
Setelah support dari semua kandidat 2-itemset didapatkan, kandidat 2-itemset
yang memenuhi syarat minimum support dapat ditetapkan sebagai 2-itemset yang
juga merupakan pola frekuensi tinggi dengan panjang 2.
Untuk selanjutnya pada iterasi ke-k dapat dibagi lagi menjadi
beberapa bagian :
1.
Pembentukan
kandidat itemset, Kandidat k-itemset dibentuk dari kombinasi (k-1)-itemset yang
didapat dari iterasi sebelumnya. Satu ciri dari algoritma Apriori adalah adanya
pemangkasan kandidat k-itemset yang subset-nya yang berisi k-1 item tidak
termasuk dalam pola frekuensi tinggi dengan panjang k-1.
2.
Penghitungan
support dari tiap kandidat k-itemset. Support dari tiap kandidat k-itemset
didapat dengan men-scan database untuk menghitung jumlah transaksi yang memuat
semua item di dalam kandidat k-itemset tsb. Ini adalah juga ciri dari algoritme
Apriori dimana diperlukan penghitungan dengan scan seluruh database sebanyak
k-itemset terpanjang.
3.
Tetapkan pola
frekuensi tinggi. Pola frekuensi tinggi yang memuat k item atau k-itemset
ditetapkan dari kandidat k-itemset yang support-nya lebih besar dari minimum
support.
4.
Bila tidak
didapat pola frekuensi tinggi baru maka seluruh proses dihentikan. Bila tidak,
maka k ditambah satu dan kembali ke bagian 1.
Sedangkan pseudocode dari pembentukan kandidat itemset bersama
pemangkasannya diberikan di Gambar berikut :
Satu contoh dari penerapan algoritma Apriori diilustrasikan di
Gambar berikut :
Di sini minimum support adalah 50% atau minimal support-nya adalah
2. Pada iterasi pertama, item yang support-nya atau count-nya dibawah 2
dieliminasi dari 1-itemset L1. Kemudian kandidat 2-itemset C2 dari iterasi
kedua dibentuk dari cross product item-item yang ada di L1. Setelah kandidat
2-itemset itu dihitung dari database, ditetapkan 2-itemset L2. Proses serupa
berulang di iterasi ketiga, tetapi perhatikan bahwa selain {2,3,5} yang menjadi
kandidat 3-itemset C3 sebenarnya ada juga itemset {1,2,3} dan {1,3,5} yang
dapat diperoleh dari kombinasi item-item di L2, tetapi kedua itemset itu
dipangkas karena {2,3} dan {1,5} tidak ada di L2. Proses ini berulang sampai
tidak ada lagi kandidat baru yang dapat dihasilkan di iterasi ke 4.
Dalam contoh ini bisa dilihat bahwa Apriori dapat mengurangi jumlah
kandidat yang harus dihitung support-nya dengan pemangkasan. Misalnya kandidat
3-itemset dapat dikurangi dari 3 menjadi 1 saja. Pengurangan jumlah kandidat
ini merupakan sebab utama peningkatan performa Apriori.
Tetapi di lain pihak Apriori memiliki kelemahan karena harus
melakukan scan database setiap kali iterasi, sehingga waktu yang diperlukan
bertambah dengan makin banyak iterasi. Masalah ini yang dipecahkan oleh
algoritma-algoritma baru seperti FP-growth.
K-Means
K-Means adalah suatu metode penganalisaan data atau metode Data
Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan
merupakan salah satu metode yang melakukan pengelompokan data dengan sistem
partisi. Metode k-means berusaha mengelompokkan data yang ada ke dalam beberapa
kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama
satu sama lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada
di dalam kelompok yang lain. Dengan kata lain, metode ini berusaha untuk
meminimalkan variasi antar data yang ada di dalam suatu cluster dan
memaksimalkan variasi dengan data yang ada di cluster lainnya.
Objective function yang berusaha
diminimalkan oleh k-means adalah:
J (U, V) = SUM (k=1 to N) SUM (i=1 to c)
(a_ik * (x_k, v_i)^2)
dimana:
U : Matriks keanggotaan data ke
masing-masing cluster yang berisikan nilai 0 dan 1
V : Matriks centroid/rata-rata masing-masing
cluster
N : Jumlah data
c : Jumlah cluster
a_ik : Keanggotaan data ke-k ke cluster
ke-i
x_k : data ke-k
v_i : Nilai centroid cluster ke-i
Prosedur yang digunakan dalam melakukan
optimasi menggunakan k-means adalah sebagai berikut:
Step 1. Tentukan jumlah cluster
Step 2. Alokasikan data ke dalam cluster
secara random
Step 3. Hitung centroid/rata-rata dari data
yang ada di masing-masing cluster.
Step 4. Alokasikan masing-masing data ke
centroid/rata-rata terdekat
Step 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 yang ditentukan
Centroid/rata-rata dari data yang ada di
masing-masing cluster yang dihitung pada Step 3. didapatkan menggunakan rumus
sebagai berikut:
v_ij = SUM (k=0 to N_i) (x_kj) / N_i
dimana:
i,k : indeks dari cluster
j : indeks dari variabel
v_ij : centroid/rata-rata cluster ke-i
untuk variabel ke-j
x_kj : nilai data ke-k yang ada di dalam
cluster tersebut untuk variabel ke-j
N_i : Jumlah data yang menjadi anggota
cluster ke-i
Sedangkan pengalokasian data ke
masing-masing cluster yang dilakukan pada Step 4. dilakukan secara penuh,
dimana nilai yang memungkinkan untuk a_ik adalah 0 atau 1. Nilai 1 untuk data
yang dialokasikan ke cluster dan nilai 0 untuk data yang dialokasikan ke
cluster yang lain. Dalam menentukan apakah suatu data teralokasikan ke suatu
cluster atau tidak, dapat dilakukan dengan menghitung jarak data tersebut ke
masing-masing centroid/rata-rata masing-masing cluster. Dalam hal ini, a_ik
akan bernilai 1 untuk cluster yang centroidnya terdekat dengan data tersebut,
dan bernilai 0 untuk yang lainnya.
No comments:
Post a Comment