Tehnik data mining

  Mining association rules atau pencarian aturan-aturan hubungan antar item dari suatu basis data transaksi atau basis data relasional, telah menjadi perhatian utama dalam masyarakat basis data. Tugas utamanya adalah untuk menemukan suatu himpunan hubungan antar item dalam bentuk A1A...AAm => B1A...ABn dimana A, ( for i E {1,...,m}) dan B; ( for j C {1,...,n} ) adalah himpunan atribut nilai, dari sekumpulan data yang relevan dalam suatu basis data. Sebagai contoh, dari suatu himpunan data transaksi, seseorang mungkin menemukan suatu hubungan berikut, yaitu jika seorang pelanggan membeli selai, ia biasanya juga membeli roti dalam satu transaksi yang sama. Oleh karena proses untuk menemukan hubungan antar item ini mungkin memerlukan pembacaan data transaksi secara berulang-ulang dalam sejumlah besar data-data transaksi untuk menemukan pola-pola hubungan yang berbeda-beda, maka waktu dan biaya komputasi tentunya juga akan sangat besar, sehingga untuk menemukan hubungan tersebut diperlukan suatu algoritma yang efisien dan metodemetode tertentu.

         Analisis asosiasi atau association rule mining adalah teknik data mining untuk menemukan aturan assosiatif antara suatu kombinasi item. Contoh dari aturan assosiatif dari analisa pembelian di suatu pasar swalayan adalah dapat diketahuinya berapa besar kemungkinan seorang pelanggan membeli roti bersamaan dengan susu. Dengan pengetahuan tersebut pemilik pasar swalayan dapat mengatur penempatan barangnya atau merancang kampanye pemasaran dengan memakai kupon diskon untuk kombinasi barang tertentu. Karena analisis asosiasi menjadi terkenal karena aplikasinya untuk menganalisa isi keranjang belanja di pasar swalayan, analisis asosiasi juga sering disebut dengan istilah market basket analysis 

          Fungsi Association Rules seringkali disebut dengan "market basket analysis", yang digunakan untuk menemukan relasi atau korelasi diantara himpunan item. Market Basket Analysis adalah Analisis dari kebiasaan membeli customer dengan mencari asosiasi dan korelasi antara item-item berbeda yang diletakkan customer dalam keranjang belanjaannya. Fungsi ini paling banyak digunakan untuk menganalisa data dalam rangka keperluan strategi pemasaran, desain katalog, dan proses pembuatan keputusan bisnis. Tipe association rule bisa dinyatakan sebagai misal : "70% dari orangorang yang membeli mie, juice dan saus akan membeli juga roti tawar". Aturan asosiasi mengcapture item atau kejadian dalam data berukuran besar yang berisi data transaksi. Dengan kemajuan teknologi, data penjualan dapat disimpan dalam jumlah besar yang disebut dengan "basket data." Aturan asosiasi yang didefinisikan pada basket data, digunakan untuk keperluan promosi, desain katalog, segmentasi customer dan target pemasaran. Secara tradisional, aturan asosiasi digunakan untuk menemukan trend bisnis dengan menganalisa transaksi customer.
          Berdasarkan definisi di [6] maka pencarian pola kaidah asosiasi mengunakan dua buah parameter nilai yaitu dukungan (support) dan keterpercayaan (confidence) yang memiliki nilai antara 0% - 100 %. Berikut sedikit penjelasan mengenai dukungan dan keterpercayaan.
          Sebagai contoh terdapat relasi I berisi sejumlah kumpulan item yang kemudian dikatakan sebagai itemset, dimana masing–masing itemset terdiri dari sekumpulan atribute bertipe boolean I1, I2, …, In. Dan basis data transaksi D yang berisi transaksi T, adalah himpunan dari I atau T Í I. Dimana transaksi T pada basis data transaksi D memiliki sebuah atribut yang unik yang dinotasikan dengan TID. Dalam konteks ini, A dan B merupakan itemset dari transaksi T, jika dan hanya jika A Í T dan B Í T. Sehingga jumlah A dinotasikan ó (A) merupakan jumlah Support (support count) itemset A pada basis data transaksi D. Kaidah asosiasi A› B, jika dan hanya jika A I, B I dan A B 0. Sehingga A› B memiliki Support s pada transaksi T, dimana S merupakan persentase itemset A È B pada basis data transaksi D. Dan A› B memiliki Confidence C pada transaksi T, dimana C merupakan persentase jumlah itemset A yang terdapat pada relasi I, yang diikuti itemset B. Dukungan kaidah asosiasi A› B dinyatakan dengan :
           Support (A› B) = P(AÈB) (xx)
           Sedangkan keterpercayaan kaidah asosiasi A› B
           dinyatakan dengan :
           Confidence (A› B) = P(A|B) (xx)
           dimana :A dan B adalah frequent itemset memiliki jumlah dukungan lebih besar
sama dengan batas ambang dukungan minimum).

Algoritma Apriori

         Persoalan association rule mining terdiri dari dua sub persoalan :
a. Menemukan semua kombinasi dari item, disebut dengan frequent itemsets, yang memiliki support     yang lebih besar daripada minimum support.
b. Gunakan frequent itemsets untuk men-generate aturan yang dikehendaki.Semisal,  ABCD dan AB adalah frequent, maka didapatkan aturan AB -> CD jika rasio dari upport(ABCD) terhadap support(AB) sedikitnya sama dengan minimum confidence. Aturan ini memiliki minimum support karena ABCD adalah frequent.
          Algoritma Apriori yang bertujuan untuk menemukan frequent itemsets dijalankan pada sekumpulan data. Pada iterasi ke -k, akan ditemukan semua itemsets yang memiliki k items, disebut dengan k -itemsets. Tiap iterasi berisi dua tahap. Misal Oracle Data Mining Fk merepresentasikan himpunan dari frequent k -itemsets, dan Ck adalah himpunan candidate k-itemsets (yang potensial untuk menjadi frequent itemsets). Tahap pertama adalah men-generate kandidat, dimana himpunan dari semua frequent (k- 1) itemsets, Fk-1, ditemukan dalam iterasi ke-(k-1), digunakan untuk men-generate candidate itemsets Ck. Prosedur generate candidate memastikan bahwa Ck adalah superset dari himpunan semua frequent k-itemsets. Struktur data hash-tree digunakan untuk menyimpan Ck. Kemudian data di-scan dalam tahap penghitungan support. Untuk setiap transaksi, candidates dalam Ck diisikan ke dalam transaksi, ditentukan dengan menggunakan struktur data hash-tree hashtree dan nilai penghitungan support dinaikkan. Pada akhir dari tahap kedua, nilai Ck diuji untuk menentukan yang mana dari candidates yang merupakan frequent. Kondisi penghitung (terminate condition) dari algoritma ini dicapai pada saat Fk atau Ck+1 kosong.

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. Disini setiap percabangan menyatakan kondisi yang harus dipenuhi dan tiap ujung pohon menyatakan kelas data. Algoritma decision tree yang paling terkenal adalah C4.5, tetapi akhirakhir ini telah dikembangkan algoritma yang mampu menangani data skala besar yang tidak dapat ditampung di main memory 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 tsb. Bila akurasinya mencukupi model ini dapat dipakai untuk prediksi kelas data yang belum diketahui.

Clustering

           Berbeda dengan association rule mining dan classification dimana kelas data telah ditentukan sebelumnya, clustering melakukan penge-lompokan data tanpa berdasarkan kelas data tertentu. Bahkan clustering dapat dipakai untuk memberikan label pada kelas data yang belum diketahui itu. Karena itu clustering sering digolongkan sebagai metode unsupervised learning. Prinsip dari clustering adalah memaksimalkan kesamaan antar anggota satu kelas dan meminimumkan kesamaan antar kelas/cluster. Clustering dapat dilakukan pada data yan memiliki beberapa atribut yang dipetakan sebagai ruang multidimensi.
          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, metode lain yang telah lama dikenal adalah metode hierarki yang terbagi dua lagi : bottom-up yang menggabungkan cluster kecil menjadi cluster lebih besar dan top-down yang memecah cluster besar menjadi cluster yang lebih kecil. 

           Kelemahan metode ini adalah bila bila salah satu penggabungan/pemecahan dilakukan pada tempat yang salah, tidak dapat didapatkan cluster yang optimal. Pendekatan yang banyak diambil adalah menggabungkan metode hierarki dengan metode clustering lainnya seperti yang dilakukan oleh Chameleon. Akhir-akhir ini dikembangkan juga metode berdasar kepadatan data, yaitu jumlah data yang ada di sekitar suatu data yang sudah teridentifikasi dalam suatu cluster. Bila jumlah data dalam jangkauan tertentu lebih besar dari nilai ambang batas, data-data tsb dimasukkan dalam cluster. Kelebihan metode ini adalah bentuk cluster yang lebih fleksibel. Algoritma yang terkenal adalah DBSCAN.