Tuesday 6 May 2008

KNOWLEDGE DISCOVERY PROCESS

A ROUGH SET-BASED KNOWLEDGE
DISCOVERY PROCESS

Oleh : SUpratman Zakir

Knowledge Discovery from Database (KDD) merupakan tahapan atau fase yang menyertai tahapan numeric, seperti Preperasi data, pencarian hipotesis untuk digeneralisasi, formasi pola, evaluasi knowledge, representasi serta manajemen. Proses yang multi fase tersebut merupakan methodology yang sangat penting untuk menemukan pengetahuan dalam data yang sesungguhnya.

Teory Rough set merupakan basic bagi KDD dan digunakan dalam KDD. Istilah knowledge discovery in databases (KDD) dan data mining sering kali digunakan secara bergantian untuk menjelaskan proses penggalian informasi tersembunyi dalam suatu basis data yang besar. Sebenarnya kedua istilah tersebut memiliki konsep yang berbeda akan tetapi berkaitan satu sama lain. Dan salah satu tahapan dalam keseluruhan proses KDD adalah data mining. Proses KDD secara garis besar dapat dijelaskan sebagai berikut

Data Selection
Pemilihan (seleksi) data daru sekumpulan data operasional perlu dilakukan sebelum tahap penggalian informasi dalam KDD dimulai. Data hasil seleksi yang akan digunakan untuk proses data mining, disimpan dalam suatu berkas, terpisah dari basis data operasional.

Pre-processing/ Cleaning
Sebelum proses data mining dapat dilaksanakan, perlu dilakukan proses cleaning pada data yang menjadi fokus KDD.
Proses cleaning mencakup antara lain membuang duplikasi data, memeriksa data yang inkonsisten, dan memperbaiki kesalahan pada data, seperti kesalahan cetak (tipografi).
Juga dilakukan proses enrichment, yaitu proses “memperkaya” data yang sudah ada dengan data atau informasi lain yang relevan dan diperlukan untuk KDD, seperti data atau informasi eksternal.

Transformation
Coding adalah proses transformasi pada data yang telah dipilih, sehingga data tersebut sesuai untuk proses data mining. Proses coding dalam KDD merupakan proses kreatif dan sangat tergantung pada jenis atau pola informasi yang akan dicari dalam basis data

Data mining
Data mining adalah proses mencari pola atau informasi menarik dalam data terpilih dengan menggunakan teknik atau metode tertentu. Teknik, metode, atau algoritma dalam data mining sangat bervariasi. Pemilihan metode atau algoritma yang tepat sangat bergantung pada tujuan dan proses KDD secara keseluruhan.

Interpretation/ Evaluation
Pola informasi yang dihasilkan dari proses data mining perlu ditampilkan dalam bentuk yang mudah dimengerti oleh pihak yang berkepentingan. Tahap ini merupakan bagian dari proses KDD yang disebut dengan interpretation. Tahap ini mencakup pemeriksaan apakah pola atau informasi yang ditemukan bertentangan dengan fakta atau hipotesa yang ada sebelumnya.


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.