Proses KDD secara garis besar memang terdiri dari 5 tahap seperti yang telah dijelaskan sebelumnya. Akan tetapi, dalam proses KDD yang sesungguhnya, dapat saja terjadi iterasi atau pengulangan pada tahap tahap tertentu. Pada setiap tahap dalam proses KDD, seorang analis dapat saja kembali ke tahap sebelumnya. Sebagai contoh, pada saat coding atau data mining, analis menyadari proses cleaning belum dilakukan dengan sempurna, atau mungkin saja analis menemukan data atau informasi baru untuk “memperkaya” data yang sudah ada.
KDD mencakup keseluruhan proses pencarian pola atau informasi dalam basis data, dimulai dari pemilihan dan persiapan data sampai representasi pola yang ditemukan dalam bentuk yang mudah dimengerti oleh pihak yang berkepentingan. Data mining merupakan salah satu komponen dalam KDD yang difokuskan pada penggalian pola tersembunyi dalam basis data.
Generalized Distribution Table and Rough Set System
GDT merupakan sebuah sistem induksi yang mudah untuk menemukan aturan-aturan pengklasifikasian dari database dengan data yang tidak lengkap dan tidak pasti (Zhong, dkk., 1998, Dong dkk., 1999a). Sistem tersebut didasarkan atas hibridisasi dari Tabel Distribusi Generalisasi (GDT, Generalization Distribution Table) dan metodologi Rough Set. Dari data pelatihan yang tidak lengkap, system GDT-RS dapat menghasilkan sekumpulan aturan dengan panjang deskripsi yang minimal (semi minimal), yang mempunyai kekuatan yang besar dan mencakup semua contoh-contoh.
Terdapat dua jenis atribut dalam sebuah database yaitu atribut kondisi dan atribut keputusan yang kadang disebut atribut kelas. Atribut kondisi digunakan untuk menggambarkan contoh-contoh yang memungkinkan dalam GDT, sedangkan atribut keputusan berhubungan dengan konsep-konsep (kelas-kelas) yang tergambar dalam sebuah aturan. Biasanya, sebuah atribut keputusan yang tunggal sudah merupakan semua yang dibutuhkan.
Sebuah GDT terdiri dari tiga komponen, yaitu contoh-contoh yang memungkinkan, generalisasi yang memungkinkan dari contoh-contoh, dan hubungan probabilitas antara contoh-contoh yang memungkinkan dan generalisasi-generalisasi yang memungkinkan.
Contoh-contoh yang memungkinkan, yang digambarkan di puncak baris GDT, ditetapkan oleh semua kombinasi yang memungkinkan dari nilai-nilai atribut dari suatu database. Generalisasi-generalisasi yang memungkinkan dari contoh-contoh, yang digambarkan oleh kolom kiri dari sebuah GDT, semuanya merupakan kasus-kasus yang memungkinkan dari generalisasi untuk semua contoh-contoh yang memungkinkan.
Hubungan-hubungan probabilitas antara contoh-contoh yang memungkinkan dan generalisasi-generalisasi yang memungkinkan , yang digambarkan dengan entri-entri Gij dari sebuah GDT yang diberikan, ditentukan dengan menggunakan distribusi probabilitas yang menggambarkan kekuatan hubungan antara contoh-contoh manapun dan generalisasi yang memungkinkan manapun. Distribusi utama diasumsikan menjadi seragam jika latar belakang pengetahuan tidak tersedia. Karena itu, hal ini dibatasi dengan
dimana Pij adalah j-th contoh yang memungkinkan, PG adalah i-th generalisasi yang memungkinkan, dan Npg adalah jumlah dari contoh-contoh yang memungkinkan yang memenuhi i-th generalisasi yang memungkinkan tersebut, contoh:
dimana Pgi{l} adalah nilai dari atribut l-th dalam generalisasi yang memungkinkan Pgi, dan nk adalah angka dari nilai-nilai dari atribut k-th. Pastinya, kita mempunyai EjGij =d1 untuk i apasaja.
Lebih jauh lagi, penemuan aturan tersebut dapat didesak oleh tiga tipe bias yang berhubungan dengan tiga komponen GDT, sehingga pengguna dapat memilih deskripsi-deskripsi konsep yang lebih umum dari sebuah level yang lebih tinggi atau konsep yang lebih khusus dari sebuah level yang lebih rendah, menyesuaikan kekuatan dari hubungan antara contoh-contoh dan generalisasinya, dan menentukan/memilih contoh-contoh yang memungkinkan (Zhong dkk., 1998).
Penyederhanaan Tabel Keputusan dengan GDT-RS
Proses penemuan aturan terdiri dari pemrosesan tabel keputusan termasuk seleksi dan pengurangan dari atribut-pelengkapan (fitur-fitur) yang relevan, dan penghasilan aturan keputusan yang tepat. Aturan-aturan keputusan yang relevan dapat disebabkan oleh aturan-aturan minimal (yaitu dengan panjang minimal dari sisi-sisi kirinya mengenai discernibility antara keputusan-keputusan) dengan menyetelnya (contohnya, menurunkan beberapa kondisi untuk mendapatkan aturan-aturan yang lebih general yang lebih baik dipredisposed untuk mengklasifikasian objek-objek yang baru walaupun objek-objek tesebut tidak mengklasifikasian dengan baik beberapa objek dari kumpulan pelatihan). Aturan –aturan yang relevan dapat disebabkan oleh kumpulan semua aturan-aturan yang minimal tersebut, atau dari sub-kumpulannya yang mencakup kumpulan objek-objek dari sebuah tabel keputusan yang diberikan. (Komorowski dkk., 1999; Pawlak dan Skowron, 1993). Sebuah pendekatan yang representatif untuk masalah dari generasi tersebut yang biasa disebut reducts relatif lokal dari atribut kondisi merupakan satu-satunya yang akan mewakili pengetahuan yang akan memelihara kedapatan dilihat antara objek-objek dengan menggunakan fungsi-fungsi kedapatan dilihat (Pawlak, 1991; Skowron dan Rauszer, 1992).
Jelas bahwa dengan menggunakan GDT satu contoh dapat dipasangkan dengan beberapa generalisasi-generalisasi yang memungkinkan, dan beberapa contoh-contoh dapat di generalkan ke dalam satu generalisasi yang memungkinkan. Penyederhanaan sebuah tabel keputusan dengan menggunakan sistem GDT-RS tersebut membawa pada satu kumpulan generalisasi minimal (atau sub-minimal) yang mencakup semua contoh-contoh. Tujuan utamanya adalah untuk menemukan sesuatu yang relevan (yaitu: minimal atau semi-minimal yang berkenaan dengan ukuran gambaran) yang mencakup tentang contoh-contoh yang masih membolehkan kita untuk memecahkan konflik-konflik antara aturan-aturan keputusan yang berbeda yang mengenali objek-objek baru. Langkah pertama dalam sistem GDT-RS untuk generasi aturan keputusan didasarkan pada penghitungan reduct-reduct relatif lokal dari atribut-atribut kondisi dengan menggunakan metode matrik kedapatan dilihat (Bazan dan Szczuka, 2000; pawlak, 1991; skowron dan Rauszer, 1992).
Lagipula, dari pada mencari atribut-atribut yang dapat dikeluarkan, lebih baik mencari atribut-atribut yang relevan yang menggunakan sebuah metode bottom-up. Contoh-contoh yang cocok dengan generalisasi apapun dengan keputusan yang berbeda-beda sebaiknya dicek dengan (6). Jika level suara lebih kecil daripada satu nilai treshold, seperti sebuah generalisasi dianggap sebagai sesuatu yang masuk akal. Jika tidak, generalisasi tersebut akan bertentangan.
Lebih jauh lagi, sebuah aturan dalam GDT-RS dipilih menurut prioritasnya. Prioritas tersebut dapat dibatasi dengan jumlah contoh-contoh yang dicakup oleh sebuah aturan (yaitu semakin banyak contoh-contoh yang dicakup, semakin tinggi prioritas tersebut), atau dengan kekuatan aturan (Zhong dkk., 1998).
Mencari Algoritma Untuk Satu Kumpulan Yang Optimal Dari atribut
Sekarang kita membuat outline ide mencari algoritma untuk satu kumpulan aturan yang dikembangkan (Dong dkk., 1999a) dan didasarkan atas metodologi GDT-RS. Kita menggunakan sebuah tabel keputusan sampel yang terlihat dalam Tabel 1 untuk menggambarkan ide tersebut. Biarkan suara menjadi sebuah nilai treshold.
Langkah 1. Buat GDT tersebut
Jika latar belakang pengetahuan sebelumnya tidak tersedia, distribusi suatu generalisasi terdahulu dikalkulasikan dengan menggunakan persamaan (1) dan (2).
Langkah 2. Pertimbangkan kelas-kelas ketidakdapatan dilihat menurut atribut kondisi kumpulan C (seperti U1, U3 dan U5 dalam database sampel dari Tabel 1) sebagai satu contoh, yang disebut contoh gabungan (seperti U1=[U1] IND (a,b,c) dalam tabel berikut). Kemudian generalisasi-generalisasi kemungkinan dapat dikalkulasikan dengan benar.
Langkah 3. Untuk contoh U’ gabungan apapun (seperti contoh U’ dalam contoh di atas), biarkan d(U’) menjadi kumpulan kelas-kelas keputusan terhadap contoh-contoh dalam yang mana U’ berada.
Langkah 4. Pilih satu contoh dari U’. Dengan menggunakan ide matriks kedapatan dilihat, buat sebuah vector kedapatan dilihat (yaitu, baris atau kolom mengenai U dalam matriks kedapatan dilihat) untuk u. Sebagai contoh, vector kedapatan dilihat untuk contoh u2:aobici adalah sebagai berikut:
Langkah 5. Hitung semua yang disebut reducts relatif lokal untuk contoh u dengan menggunakan fungsi kedapatan dilihat.
Langkah 6. Bangun aturan-aturan dari reducts lokal untuk contoh u, dan revisi kekuatan dari masing-masing aturan
Langkah 7. Pilih aturan-aturan terbaik dari aturan-aturan (untuk u) yang didapat dalam Langkah 6 berdasarkan prioritasnya (Zhong dkk., 1998).
Langkah 8. kemudian kembali ke Langkah 4. Kalau tidak, terus ke Langkah 9.
Langkah 9. Jika aturan manapun dipilih dalam Langkah 7 mencakup satu contoh dengan tepat , lalu BERHENTI, kalau tidak, dengan menggunakan metode dari Bagian 2.3, pilih satu kumpulan aturan-aturan minimal yang mencakup semua contoh dalam tabel keputusan.
Rough Set with Heuristics (RSH)
RSH adalah sebuah sistem untuk seleksi sub-kumpulan sebuah atribut. Ini didasarkan atas kumpulan-kumpulan yang sulit dengan Heuristik (Dong dkk., 1999b). Perkembangan RSH tersebut didasarkan atas observasi berikut: (i) sebuah database selalu mengandung banyak atribut yang tumpang tindih dan tidak penting untuk penemuan aturan; (ii) jika atribut-pelengkapan yang tumpang tindih ini tidak dibuang, tidak hanya kompleksitas waktu dari penemuan aturan akan meningkat tapi juga kualitas dari aturan-aturan yang ditemukan dapat turun secara signifikan.
Tujuan dari seleksi atribut adalah untuk menemukan sebuah sub-kumpulan optimal dari atribut-atribut menurut beberapa kriteria sehingga satu penggolong dengan kemungkinan keakuratan tertinggi dapat disebabkan oleh sebuah algoritma belajar induktif yang menggunakan informasi tentang data yang tersedia hanya dari atribut-atribut sub-kumpulan.
Beberapa konsep dari rough set yang berhubungan dengan seleksi atribut dalam pra-pemrosesan (Pawlak, 1991). Biarkan C dan D menunjukkan kondisi dan kumpulan-kumpulan atribut dari tabel keputusan T, secara berurutan. Daerah C-positif dari D merupakan kumpulan dari semua objek-objek dari semesta U yang dapat diklasifikasikan dengan kepastian untuk kelas-kelas U/D yang mempekerjakan atribut-atribut dari C, yaitu
Dimana CX menunjukkan perkiraan yang rendah dari kumpulan X tentang C, yaitu kumpulan dari semua objek dari U yang dapat diklasifikasikan dengan pasti sebagai elemen-elemen dari X berdasarkan pada atribut-atribut dari C.
Sebuah atribut dapat dikeluarkan dalam sebuah tabel keputusan T, jika = jika tidak, atribut c dapat dikeluarkan dalam T. Satu kumpulan atribut … disebut sebuah reduct dari C jika ini merupakan sebuah sub-kumpulan atribut minimal yang memelihara kondisi Lebih jauh, kumpulan dari semua atribut yang tidak dapat dikeluarkan dalam C ditunjukkan oleh CORE( C ). Kita mempunyai
Dimana RED (C) adalah kumpulan dari semua reducts C.
Kualitas dari suatu sub-kumpulan atribut R dalam GDT-RS bergantung pada kekuatan dari aturan-aturan yang ditemukan dengan menggunakan sub-kumpulan ini. Semakin tinggi kekuatannya semakin baik sub-kumpulannya. Mencari atribut-atribut yang bermanfaat untuk mendapatkan aturan-aturan dengan rata-rata sampul yang besar dan kekuatan didasarkan atas strategi seleksi yang digambarkan.