Term


Structural pattern mining merupakan data mining yang mencari informasi struktural dari structural database. Jelas, databasenya sangat berhubungan dengan graph. Pentingnya structural pattern mining dapat dilihat karena banyak sekali real world entity dapat dinyatakan dalam bentuk graph mulai dari relational database, molekul, networks, web, sampai proteomics. Berbagai representasi pengetahuan seperti sequence dan tree juga termasuk jenis graph. Karena itulah, area ini menjadi semakin penting saat ini. Beberapa disiplin ilmu seperti bioinformatika dan chem-informatics mulai memanfaatkan structural pattern mining untuk memperoleh deskripsi pola-pola data yang akan dianalisa.
Beberapa task structural pattern mining dapat dibaca pada posting Survey Link Mining.
Resource dan publikasi tentang structural pattern mining dapat dilihat pada [1].
Sedangkan [2], memberikan review tentang algoritma structural pattern mining yang dibagi menjadi kernels methods, molecular query methods, dan maximum common substructure methods bedasarkan sudut pandang molecular mining. Posting ini sangat menarik karena memberikan link ke source code, referensi, dan komentar tentang kelebihan algoritma-algoritma tersebut.

Referensi:
1. Homepage for Mining Structured Data. http://hms.liacs.nl/index.html
2. Mining Drug Space: Molecular Mining Review 2006. http://miningdrugs.blogspot.com/2007/01/molecule-mining-review-2006.html

Iklan

Saat saya browsing internet hari ini, secara tidak sengaja saya menemukan sebuah project PP-SVM. Setelah membaca overview PP-SVM, salah satu project IDIS (Iowa Data and Information System Group), saya baru benar-benar menyadari tentang perlunya privacy preserving. Jika sebelumnya saya hanya memahaminya secara sempit bahwa keperluan ini hanya untuk menjaga privacy data yang akan dimining, misalnya mining data finansial untuk keperluan fraud detection atau penentuan credit risk. Proses mining dilakukan dengan menjaga kerahasiaan (privacy) sehingga dapat diperoleh pengetahuan tanpa ada privacy yang bocor.
Namun, pada overview project ini saya memperoleh gambaran yang lebih luas tentang perlunya privacy preserving yaitu mining data terdistribusi. Menggabungkan data dari berbagai sumber (repository) dapat meningkatkan kualitas pengetahuan yang diperoleh, misalnya pada klasifikasi data tingkat akurasinya akan lebih baik.
Hal ini akan sangat berguna dalam berbagai aplikasi misalnya untuk mining data medis, dan fraud detection. Data Mining untuk menentukan treatment yang paling efektif pada suatu penyakit dengan berbagai gejala dan kondisi pasien akan lebih baik jika data yang dimining diperoleh dari sumber (apalagi jika diperoleh dari semua rumah sakit di dunia). Bisa dibayangkan juga mungkin, jika seluruh instansi perbankan mengabungkan datanya untuk mengatasi fraud detection.
Hanya saja masalahnya adalah privacy dan security yang menghambat sharing data karena privacy data merupakan asset yang sangat berharga bagi masing-masing pemiliknya. Mereka tidak mungkin membocorkan asset mereka masing-masing. Nah, Privacy preserving data mining akan sangat berperan di sini. Dengan privacy preserving data mining, orang-orang dapat saling share data mereka untuk dimining tanpa perlu kehilangan asset mereka. Pengetahuan yang diperoleh juga dapat dipakai bersama, saling menguntungkan.
Semakin banyak tahu, data mining ini kelihatan semakin luas. Rasanya yang saya tahu hanya secuil dari ilmu ini.

Reference:
1. PP-SVM. http://idis.hwanjoyu.org/ppsvm/ppsvm.html

Ketiga istilah ini sangat berkaitan dengan klasifikasi data. Sebuah model classifier pada klasifikasi data dibentuk berdasarkan data yang sudah ada, dan kemudian model tersebut digunakan untuk klasifikasi dan prediksi data baru yang belum pernah ada.
Pada umumnya, proses dapat digambarkan seperti ini:

Data umumnya dibagi menjadi training set dan testing set. Training set digunakan oleh algoritma klassifikasi (misalnya: decision tree, bayesian, neural network, SVM) untuk membentuk sebuah model classifier. Model ini merupakan representasi pengetahuan yang akan digunakan untuk prediksi kelas data baru yang belum pernah ada. Testing set digunakan untuk mengukur sejauh mana classifier berhasil melakukan klasifikasi dengan benar. Karena itu, data yang ada pada testing set seharusnya tidak boleh ada pada training set sehingga dapat diketahui apakah model classifier sudah “pintar” dalam melakukan klasifikasi.
Lain lagi halnya dengan validation set. Umumnya beberapa algoritma klasifikasi memerlukan beberapa parameter. Misalnya: jumlah hidden layer dan learning rate pada neural network; parameter kernel pada SVM. Biasanya sebagian dari training set diambil untuk validation set. Validation set ini digunakan untuk mencari parameter yang paling baik untuk sebuah algoritma klasifikasi.
Memisahkan data menjadi training dan testing set dimaksudkan agar model yang diperoleh nantinya memiliki kemampuan generalisasi yang baik dalam melakukan klasifikasi data. Tidak jarang sebuah model klasifikasi dapat melakukan klasifikasi data dengan sangat baik pada training set, tetapi sangat buruk dalam melakukan klasifikasi data yang baru dan belum pernah ada. Hal ini dinamakan overfitting. Model tersebut masih belum baik.

Salah satu task data mining adalah Classification (klasifikasi). Banyak sekali aplikasi dari klasifikasi data ini, contohnya: customer profiling untuk targeted marketing dan CRM, spam filtering, fraud detection, diagnosa medis.
Pada data classification, data dipasangkan pada sebuah class label tertentu. Classification membentuk sebuah model yang nantinya digunakan untuk melakukan prediksi class label data baru yang belum pernah ada. Misalnya pada aplikasi email spam filtering, data email dipasangkan pada class label “spam” dan “bukan spam”. Kemudian dibentuk sebuah model yang dapat menentukan sebuah email baru (yang belum pernah ada) termasuk “spam” atau “bukan spam”.
Jadi, data classification memiliki dua tahap yaitu: pembentukan model, dan penggunaan model tersebut untuk prediksi class label data baru. Model yang dihasilkan biasa disebut classifier.
Terdapat banyak sekali teknik dan pendekatan yang digunakan dalam data classification, sebut saja decision tree, bayesian classifier, rule-based classifier, neural network, support vector machine (SVM), associative classification, nearest neighbor, genetic algorithm, fuzzy logic, dan lain-lain. Dari beberapa istilah ini, kita tahu bahwa banyak algoritma data classification berasal dari bidang machine learning, pattern recognition, dan statistik.

Secara umum, terdapat dua tahap dalam melakukan Association Rule Mining yaitu Frequent Itemset Candidate Generation dan Rule Generation. Pada tahap Frequent Itemset Candidate Generation terdapat beberapa kendala yang harus dihadapi untuk memperoleh Frequent Itemset seperti banyaknya jumlah kandidat yang memenuhi minimum support, dan proses perhitungan minimum support dari Frequent Itemset yang harus melakukan scan database berulang-ulang. Pendekatan Apriori sangat membantu dalam mengurangi jumlah kandidat Frequent Itemset.
Apakah mungkin candidate generation ini tidak dilakukan?
Dengan menggunakan FP-growth, kita dapat melakukan Frequent Itemset Mining tanpa melakukan candidate generation. FP-growth menggunakan struktur data FP-tree. Dengan menggunakan cara ini scan database hanya dilakukan dua kali saja, tidak perlu berulang-ulang. Data akan direpresentasikan dalam bentuk FP-tree. Setelah FP-tree terbentuk, digunakan pendekatan divide and conquer untuk memperoleh Frequent Itemset. FP-tree merupakan struktur data yang baik sekali untuk Frequent Pattern mining. Struktur ini memberikan informasi yang lengkap untuk membentuk Frequent Pattern. Item-item yang tidak frequent (infrequent) sudah tidak ada dalam FP-tree.

Referensi :
1. J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. SIGMOD’00.
2. R. Agarwal, C. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent itemsets. J. Parallel and Distributed Computing:02.

Masalah utama pencarian Frequent Itemset adalah banyaknya jumlah kombinasi itemset yang harus diperiksa apakah memenuhi minimum support atau tidak. Salah satu cara untuk mengatasinya adalah dengan mengurangi jumlah kandidat itemset yang harus diperiksa.
Apriori adalah salah satu pendekatan yang sering digunakan pada Frequent Itemset Mining. Prinsip Apriori adalah jika sebuah itemset infrequent, maka itemset yang infrequent tidak perlu lagi diexplore supersetnya sehingga jumlah kandidat yang harus diperiksa menjadi berkurang.
Kira-kira ilustrasinya seperti ini:

Pada gambar di atas, pencarian Frequent Itemset dilakukan tanpa menggunakan prinsip Apriori. Dengan menggunakan prinsip Apriori, pencarian Frequent Itemset akan menjadi seperti di bawah ini:

Dapat dilihat bahwa dengan menggunakan Apriori, jumlah kandidat yang harus diperiksa cukup banyak berkurang. Apriori sendiri terus dikembangkan untuk meningkatkan efisiensi dan efektivitasnya. Salah satunya adalah dengan memanfaatkan Hash Tree untuk perhitungan support yang efisien (mengurangi Database scan yang berulang-ulang).

Referensi :
1. Agrawal and R. Srikant. Fast algorithms for mining association rules. VLDB’94.
2. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for discovering association rules. KDD’94.
3. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. VLDB’95.

Secara umum, Association Rule Mining dapat dibagi menjadi dua tahap:

  1. Pencarian Frequent Itemset
    Pada proses ini dilakukan pencarian Frequent Itemset. Frequent Itemset yang diperoleh harus memenuhi minimum support (lihat post Itemset, Support, dan Confidence).
  2. Rule Generation
    Frequent Itemset yang telah dihasilkan dari proses sebelumnya digunakan untuk membentuk Association Rule. Association Rule yang dihasilkan akan memenuhi minimum support dan minimum confidence.

Masalah utama yang muncul pada pencarian Frequent Itemset adalah banyaknya hasil Frequent Itemset yang memenuhi threshold minimum support. Semakin rendah threshold minimum support, Frequent Itemset yang dihasilkan akan semakin banyak. Jika terdapat d item, maka akan diperoleh 2d-1 kombinasi itemset yang bisa diperoleh. Contoh: 100 item akan menghasilkan kombinasi itemset 2100-1. Jumlah itemset ini sangat banyak untuk dapat disimpan atau diproses pada komputer manapun. Untuk mengatasi hal ini, muncul istilah Closed Frequent Itemset dan Maximal Frequent Itemset.

Laman Berikutnya »