Data Mining

Knowledge Discovery in Databases (KDD)

Knowledge Discovery in Database (KDD) adalah analisis otomatis eksplorasi dan pemodelan dari repositori data yang besar (Maimon & Rokach, 2010:1). Knowledge Discovery in Database (KDD) didefenisikan sebagai ekstraksi informasi potensial, implisit dan tidak dikenal dari sekumpulan data. Proses Knowlegde Discovery in Database melibatkan hasil proses data mining (proses pengekstrak kecenderungan suatu pola data), kemudian mengubah hasilnya secara akurat menjadi informasi yang mudah dipahami (Tampubolon, Saragih, Reza, 2013). Fayyad (1996) dan Dunham (2003) menggunakan istilah Knowledge Discovery in Databases (KDD) untuk menunjuk pada keseluruhan proses pencarian pengetahuan dalam kumpulan data jumlah besar. Mereka menggolongkan data mining sebagai salah satu langkah dalam proses KDD dikarenakan oleh penerapannya terhadap suatu algoritma spesifik dalam mencari pola-pola (model) dalam data (Azhari dan Anshori, 2009).

Menurut Santoso (2007) KDD adalah kegiatan yang meliputi pengumpulan, pemakaian data, historis untuk menemukan keteraturan, pola atau hubungan dalam set data berukuran besar (Benni R Siburian, 2014).

Menurut Gunadi dan Indra S (2012) Data mining juga sering disebut sebagai Knowledge Discovery in Database (KDD). KDD terdiri dari tiga proses utama yaitu (Anis Kurniawati, 2014):

a. Preprocessing

Preprocessing dilakukan terhadap data sebelum algoritma data mining diaplikasikan. Proses ini meliputi data cleaning, integrasi, seleksi dan transformasi.

b. Data mining

Proses utama dalam KDD adalah proses data mining, dalam proses ini algoritma-algoritma data mining diaplikasikan untuk mendapatkan pengetahuan dari sumber data.

c. Post processing

Hasil yang diperoleh dari proses data miningselanjutnya akan dievaluasi pada

post processing.

Pada dasarnya ada enam elemen yang paling esensial dalam teknik pencarian informasi/pengetahuan dalam KDD yaitu (Tampubolon, aragih, Reza, 2013):

a. Mengerjakan sejumlah besar data.

b. Diperlukan efesiensi berkaitan dengan volume data.

c. Mengutamakan ketetapan/keakuratan.

d. Membutuhkan pemakaian bahasa tingkat tinggi.

e. Menggunakan beberapa bentuk dari pembelajaran otomatis.

f. Menghasilkan hasil yang menarik.

Ada beberapa macam pendekatan yang berbeda yang diklasifikasikan sebagai teknik pencarian informasi/pengetahuan dalam KDD. Ada pendekatan kuantitatif, seperti pendekatan probabilistik seperti logika induktif, pencarian pola, dan analisis pohon keputusan. Pendekatan yang lain meliputi deviasi, analisis kecenderungan, algoritma genetik, jaringan saraf tiruan, dan pendekatan campuran dua atau lebih dari beberapa pendekatan yang ada.

Menurut Han dan Kamber (2006) Knowledge discovery sebagai sebuah proses digambarkan pada gambar 2.1, dan terdiri atas runtunan iterative dari langkah-langkah berikut (Benni R Siburian, 2013):

a. Data cleaning (untuk membuang noise dan data yang tidak konsisten).

b. Data integration (beragam sumber data digabungkan).

c. Data selection (data yang relevan untuk dianalisa di-retrieve dari database).

d. Data transformation (dimana data diubah atau dikonsolidasikan ke dalam bentuk yang sesuai untuk pertambangan misalnya dengan melakukan ringkasan atau operasi agregasi).

e. Data mining (sebuah proses esensi dimana metode cerdas diterapkan untuk mengekstraksi pola-pola data).

f. Pattern evaluation (mengidentifikasi pola yang benar menarik merepresentasikan dasar pengetahuan pada beberapa ukuran menarik).

Knowledge presentation (teknik representasi visualisasi dan penngetahuan digunakan untuk memperlihatkan pengetahuan yang telah ditambang kepada pengguna).

Gambar 2.1. Data Mining Sebagai Sebuah Langkah Dalam Proses Knowledge Discovery

2.2 Data Mining

Beberapa pengertian data mining yang berhasil penulis himpun dari beberapa pendapat adalah sebagai berikut :

a. Data Mining adalah serangkaian proses untuk menggali nilai tambah dari suatu kumpulan data berupa pengetahuan yang selama ini tidak diketahui secara manual (Benni R Siburian, 2013).

b. Data mining adalah proses mencari pola atau informasi menarik dalam data terpilih dengan menggunakan teknik atau metode tertentu (Gunadi, Sensuse, 2012).

c. Data mining, sering juga disebut knowledge discovery in database (KDD), adalah kegiatan yang meliputi pengumpulan, pemakaian data historis untuk menemukan keteraturan, pola atau hubungan dalam set data berukuran besar (Efori Buulolo, 2013).

d. Data mining merupakan analisis data menggunakan tool untuk menemukan pola dan aturan dalam himpunan data (Eka Novita Sari, 2013).

e. Menurut Kusrini, EmhaTaufiq Luthfi (2010) Data mining adalah suatu istilah yang digunakan untuk menguraikan penemuan pengetahuan didalam database (Dewi Kartika Pane, 2013).

f. Menurut Han dkk (2001) Data mining merupakan suatu proses yang menggunakan teknik statistik, visualisasi, kecerdasan buatan, dan machine-learning untuk mengekstraksi dan mengidentifikasi informasi yang bermanfaat dan pengetahuan yang terkait dari berbagai database (Azhari, Anshori, 2009).

g. Data Mining adalah menganalisis pendekatan dari berbagai data perspektif untuk merangkum hasil informasi yang berguna (Kularbphettong,Tongsiri, 2012).

h. Data mining diartikan sebagai proses menemukan pola-pola dalam data. Proses tersebut harus secara otomatis, atau (biasanya) semi otomatis. Pola-pola yang ditemukan haruslah memiliki makna yang dapat mengarahkan pada beberapa keuntungan seperti biasanya keuntungan ekonomis. Data tersebut biasanya dalam ukuran yang besar (Witten & Frank, 2005).

i. Data mining merujuk pada ekstraksi atau "penambangan" pengetahuan dari dalam sejumlah besar data (Han & Kamber, 2006).

Berdasarkan beberapa pengertian diatas dapat ditarik kesimpulan bahwa Data mining adalah sebuah analisa dari observasi data dalam jumlah besar untuk menemukan hubungan yang tidak diketahui sebelumnya dan metode baru untuk meringkas data agar mudah dipahami serta kegunaannya untuk pemilik data.

2.2.1 Teknik-teknik Data Mining

Terdapat beberapa teknik yang digunakan dalam data mining, yaitu antara lain (Azhari, Anshori, 2009):

a. Klasifikasi (Classification)

Klasifikasi adalah proses untuk menemukan model atau fungsi yang menjelaskan atau membedakan kelas data, dengan tujuan untuk memperkirakan kelas dari suatu objek yang labelnya tidak diketahui.

b. Regresi (Regression)

Model dengan tipe regresi ini menggunakan serangkaian nilai-nilai atribut yang ada untuk memprediksi suatu nilai kontinu.

c. Aturan Asosiasi (Association Rule)

Aturan asosiasi adalah teknik data mining untuk menemukan aturan asosiatif antara kombinasi item. Penting atau tidaknya suatu aturan asosiasi dapat diketahui dengan dua parameter, support yaitu persentase kombinasi item tersebut dalam database dan confidence yaitu kuatnya hubungan antara item dalam association rule. Algoritma untuk aturan asosiasi yang paling popular dikenal dengan nama algoritma apriori dengan paradigma generate and test, yaitu pembuatan kandidat kombinasi item yang mungkin berdasarkan aturan tertentu, kemudian diuji apakah kombinasi item tersebut memenuhi syarat support minimum. Kombinasi item yang memenuhi syarat tersebut disebut frequent item set atau large item set, yang kemudian dipakai untuk membuat aturan-aturan yang memenuhi syarat confidence minimum. Algoritma dari aturan asosiasi yang lain adalah algoritma predictive apriori dan tertius.

d. Clustering

Berbeda dengan klasisfikasi, regresi, dan aturan asosiasi dimana kelas data telah ditentukan sebelumnya. Clustering melakukan pengelompokan data tanpa berdasarkan kelas data tertentu. Bahkan clustering dapat digunakan untuk memberikan label pada kelas data yang belum diketahui tersebut.

2.3 Metodologi Data mining

Untuk dapat memanfaatkan Data mining semaksimal mungkin, sangat dibutuhkan langkah-langkah metodologi dalam sebuah implementasi data mining. Dari implementasi diharapakan adanya keguanaan yang positif dari eksplorasi untuk semua pengguna. Ini bermaksud menghilangkan pandangan sebagian orang bahwa Data mining hanyalah dapat digunakan oleh praktisi Data mining.

Menurut Feen Lee & Juan Santana (2010:37-40) Langkah-langkah yang dibutuhkan untuk mengerjakan implementasi Data mining sebagai berikut (Tampubolon, Saragih, Reza, 2013) :

a. Tahap pertama: Precise statement of the problem (mendefinisikan permasalahan yang ingin diketahui). Misalnya ingin mengetahui apakah seorang customer berpotensi memiliki kredit macet, atau mengidentifikasi seorang customer apakah akan pindah ke kompetitor bisnis kita, dan lain sebagainya. Setelah menemukan pertanyaan bisnis yang perlu dijawab oleh data mining, selanjutnya tentukan tipe tugas untuk menjawab pertanyaan bisnis tersebut. Tugas dasar yang menjadi dasar algoritma data mining adalah klasifikasi, regresi, segmentasi, asosiasi dan sequence analisis.

b. Tahap kedua: Initial Exploration (Mempersiapkan data yang menjadi sumber untuk data mining termaksud data “cleaning” untuk mempelajari polanya). Setelah menemukan defenisi masalah, langkah berikutnya adalah mencari data yang mendukung defenisi masalah. Menentukan porsi data yang digunakan men-training data mining berdasarkan algoritma data mining yang telah dibuat. Setelah persiapan data selesai dilakukan, langkah berikutnya adalah memberikan sebagian data kedalam algoritma data mining.

c. Tahap ketiga: Model building and validation. Validasi apakah data mining memberikan prediksi yang akurat. Setelah training data selesai dilakukan, data mining tersebut perlu di-“uji” atau di-validasi keakuratannya terhadap data testing.

d. Tahap ke-empat: Deployment. Tahap ini memilih aplikasi yang tepat terhadap data mining untuk membuat prediksi.

Gambar 2.2. Tahapan dalam Data Mining dan Membangun Model

2.4 Rule Association

Beberapa pengertian Rule Association yang berhasil penulis himpun dari beberapa literatur adalah sebagai berikut :

a. Menurut Witten and Frank (2005) Association rules merupakan salah satu teknik didalam data mining untuk menentukan hubungan antar item dalam suatu dataset (sekumpulan data) yang telah ditentukan. Konsep ini sendiri diturunkan dari terminologi market basket analysis, yaitu pencarian hubungan dari beberapa produk di dalam transaksi pembelian (Bayu Adhi Tama, 2010).

b. Association rules adalah salah satu teknik data mining yang mana diharapkan untuk menjadi aplikasi yang sangat bermanfaat (D. Magdalene Delighta Angeline, 2013).

c. Menurut Amirudin et al (2007) Analisis asosiasi atau association rule mining adalah teknik data mining untuk menemukan aturan asosiasi antara kombinasi item (Tampubolon, Saragih, Reza, 2013).

Association rule mempunyai bentuk LHS (Left Hand Side) à RHS (Right Hand Side) dengan interpretasi jika setiap item dalam LHS dibeli maka sepertinya item dalam RHS juga dibeli. Dua pengukuran penting untuk sebuah rule adalah Support dan Confidence.

Support (s) didefinisikan sebagai persentase record terhadap total record keseluruhan dalam database. Support dapat dituliskan dalam rumus berikut:

Support (X)= ....................................... (1)

Sementara nilai Support dari 2 item dituliskan dalam rumus berikut:

Support (X,Y) = P(X ∩Y)............................................................................... (2)

Support (X,Y)= .................................................... (3)

Jadi jika misalnya Support sebuah item adalah 0,1 % maknanya hanya 0,1 persen dari transaksi berisikan item ini.

Sementara Confidence (c) didefinisikan sebagai persentase dari sejumlah transaksi yang berisikan X Y terhadap jumlah record keseluruhan yang mengandung X. Confidence dapat dituliskan dalam rumus berikut:

Confidence (X|Y) = ...................................................................... (4)

Confidence merupakan ukuran kekuatan sebuah rule asosiasi. Jika kita anggap Confidence XàY adalah 80%, berarti sebanyak 80 persen transaksi yang mengandung X maka akan mengandung juga akan mengandung Y (Zhao & Bhowmick, 2003:6-7).

Pada umumnya, menurut Han dan Kamber (2006:231) association rule mining dapat dilihat sebagai proses dua langkah, yaitu:

a. Temukan semua frequent itemsets, dengan pengertian setiap itemset ini akan muncul sesering sekurangnya minimum Support (min-sup) yang telah telah ditentukan.

b. Hasilkan association rules yang kuat dari frequent itemsets: dengan pengertian rule-rule ini haruslah memenuhi minimum Support dan minimum Confidence.

2.5 Langkah-Langkah Proses Aturan Asosiasi

Menurut Eko Wahyu Tyas d (2008) Proses Aturan Asosiasi terdiri dari beberapa tahap sebagai berikut (Tampubolon, Saragih, Reza, 2013):

a. Sistem men-scan database untuk mendapat kandidat 1-itemset (himpunan item yang terdiri dari 1 item) dan menghitung nilai supportnya. Kemudian nilai supportnya tersebut dibandingkan dengan minimum support yang telah ditentukan, jika nilainya lebih besar atau sama dengan minimum support maka itemset tersebut termasuk dalam large itemset.

b. Itemset yang tidak termasuk dalam large itemset tidak diikutkan dalam iterasi selanjutnya (diprune).

c. Pada iterasi kedua sistem akan menggunakan hasil large itemset pada iterasi pertama (L1) untuk membentuk kandidat itemset kedua (L2). Pada iterasi selanjutnya sistem akan menggunakan hasil large itemset pada iterasi selanjutnya akan menggunakan hasil large itemset pada iterasi sebelumnya (Lk-1) untuk membentuk kandidat itemset berikut (Lk). Sistem akan menggabungkan (join) Lk-1 dengan Lk-1 untuk mendapatkan Lk, seperti pada iterasi sebelumnya sistem akan menghapus (prune) kombinasi itemset yang tidak termasuk dalam large itemset.

d. Setelah dilakukan operasi join, maka pasangan itemset baru hasil proses join tersebut dihitung supportnya.

e. Proses pembentuk kandidat yang terdiri dari proses join dan prune akan terus dilakukan hingga himpunan kandidat itemsetnya null, atau sudah tidak ada lagi kandidat yang akan dibentuk.

f. Setelah itu, dari hasil frequent itemset tersebut dibentuk association rule yang memenuhi nilai support dan confidence yang telah ditentukan.

g. Pada pembentukan association rule, nilai yang sama dianggap sebagai satu nilai.

h. Assosiotion rule yang terbentuk harus memenuhi nilai minimum yang telah ditentukan.

i. Untuk setiap large itemset L, kita cari himpunan bagian L yang tidak kosong. Untuk setiap himpunan bagian tersebut, dihasilkan rule dengan bentuk aB(L-a) jika supportnya (L) dan supportnya (a) lebih besar dari minimum support.

2.6 Algoritma Apriori

Algoritma Apriori adalah suatu algoritma dasar yang diusulkan oleh Agrawal & Srikant pada tahun 1994 untuk penentuan frequent itemsets untuk aturan Asosiasi Boolean. Algoritma Apriori termasuk jenis aturan asosiasi pada data mining. Aturan yang menyatakan asosiasi antara beberapa atribut sering disebut Affinity Analysis atau market basket analysis. Analisis asosiasi atau association rule mining adalah teknik data mining untuk menemukan aturan suatu kombinasi item. Salah satu tahap analisis asosiasi yang menarik perhatian banyak peneliti untuk menghasilkan algoritma yang efisien adalah analisis pola frequensi tinggi (frequent pattern mining).

Penting tidaknya suatu asosiasi dapat diketahui dengan dua tolak ukur , yaitu : support dan confidence. Support (nilai penunjang) adalah persentase kombinasi item

tersebut dalam database, sedangkan confidence (nilai kepastian) adalah kuatnya hubungan antaritem dalam aturan asosiasi (Eka Novita Sari, 2013).

Algoritma apriori adalah adalah algoritma yang paling terkenal untuk menemukan pola frekuensi tinggi (Efori Buulolo, 2013). Selanjutnya menurut Sarjon (2013) Apriori adalah suatu algoritma yang sudah sangat dikenal dalam melakukan pencarian frequent itemset dengan menggunakan teknik association rule. Pada algoritma apriori untuk menentukan kandidat-kandidat yang mungkin muncul dengan cara memperhatikan minimum support (Anis Kurniawati, 2014).

Menurut Devi dindasetiawan (2009) Algoritma apriori dibagi menjadi beberapa tahap yang disebut narasi atau pass (Tampubolon, Saragih, Reza, 2013):

a. Pembentukan kandidat itemset.

Kandidat k-itemset dibentuk dari kombinasi (k-1)-itemset yang didapat dari iterasi sebelumnya. Satu cara dari algoritma apriori adalah pemangkasan kandidat k-itemset yang subsetnya berisi k-1 item tidak termasuk

b. Penghitungan support dari tiap kandidat k-itemset.

Support dari tiap kandidat k-itemset didapat dengan menscan database untuk menghitung jumlah transaksi yang memuat semua item didalam kandidat k-itemset tersebut. Ini adalah juga ciri dari algoritma apriori dimana diperlukan penghitungan dengan cara seluruh database sebanyak k-itemset terpanjang.

c. Tetapkan pola frekuensi tinggi.

Pola frekuensi tinggi yang memuat k item atau kitemset ditetapkan dari kandidat k-itemset yang supportnya lebih besar dari minimum support.

d. Bila tidak didapat pola frekuensi tinggi baru maka seluruh proses dihentikan.

Untuk mengetahui cara kerja algoritma apriori dapat kita lihat pada contoh pada tabel berikut. Diketahui telah terjadi transaksi sebanyak 5 kali, dan jenis item yang dibeli adalah Mouse, keyboard, Cdrom, Hardisk, Memory, VGA, Prosesor.

Tabel 2. 1. Transaksi Penjualan Peralatan Komputer

Ditentukan minimum support (min-sup) 20 % dan minimum confidence (min-conf) 70%, Jika ada item yang memiliki support di bawah min-sup 20% akan dihapus (pruned/pangkas). Kemudian selanjutnya item-item yang tersisa, dilakukan penggabungan (join) item sebanyak 2 buah (k=2) untuk membentuk candidate C₂. Hitung kembali support masing-masing itemset.

Tabel 2.4. Menghitung Frequent Itemset C₂

Dilihat dari hasil diatas, ternyata itemset yang tersisa, adalah (Keyboard, Cdrom, Hardisk) yang selanjutnya dapat dinyatakan sebagai frequent itemset.

Langkah selanjutnya adalah dengan membentuk association rule yang kuat berdasarkan frequent itemset yang dihasilkan tersebut berdasarkan nilai confidence.

Rule 1: {Keyboard, Cdrom} → {Hardisk}

c = s ({Keyboard, Cdrom, Hardisk}) / s ({Keyboard, Cdrom}) = 2/2 = 100%

Rule 2: { Keyboard, Hardisk } → {Cdrom}

c = s ({Keyboard, Cdrom, Hardisk}) / s ({Keyboard, Hardisk }) = 2/3 = 67%

Rule 3: { Cdrom, Hardisk } → {Keyboard}

c = s ({Keyboard, Cdrom, Hardisk }) / s ({Cdrom, Hardisk }) = 2/2 = 100%

Rule 4: {Keyboard} → { Cdrom, Hardisk }

c = s ({Keyboard, Cdrom, Hardisk }) / s ({Keyboard}) = 2/3 = 67%

Rule 5: {Cdrom} → {Keyboard, Hardisk}

c = s ({Keyboard, Cdrom, Hardisk }) / s ({Cdrom}) = 2/3 = 67%

Rule 6: {hardisk} → { Keyboard, Cdrom}

c = s ({Keyboard, Cdrom, Hardisk }) / s ({Hardisk}) = 2/3 = 67%

Dikarenakan minimum confidence yang diinginkan adalah 70% maka rule yang dapat diterima adalah rule 1 dan rule 3.

Aher dan Lobo (2012:49) menuliskan secara sederhana cara kerja algoritma apriori dalam pseudo code sebagai berikut:

2.6.1.1 C₁ = Itemsets of size one in I;

2.6.1.2 Determine all large itemsets of size 1, L₁;

3 i = 1;

4 Repeat

5 i = i + 1;

6 C_i = Apriori-Gen(L_i-1);

7 Apriori-Gen(L_i-1)

a. Generate candidates of size i+1 from large itemsets of size i.

b. Join large itemsets of size i if they agree on i-1.

c. Prune candidates who have subsets that are not large.

8 Count C_i to determine L_i;

9 until no more large itemsets found;

Gambar 2. 3. Diagram Cara Kerja Algoritma Apriori Untuk Pembentukan Frequent Itemset.

Gambar 2.2 menunjukkan bahwa algoritma akan menghasilkan kandidat baru dari 1-itemset (L1) dari frequent itemset dan menghitung nilai support 1-itemset (L1) tersebut. Selanjutnya masuk ke 2-itemset (L2) dan dihitung lagi support 2-itemset (L2). Kemudian Itemset yang memiliki nilai support di bawah dari minsup akan dihapus. Algortima berhenti jika tidak ada lagi frequent itemset baru yang dihasilkan dan menetapkan minimum support-nya = 2.