Juni 2006


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.

Iklan

Rakesh Agrawal merupakan peneliti yang sangat terkenal di bidang database dan data mining. Beliau juga disebut-sebut sebagai pioneer data mining. Asociation Rule Mining merupakan topik yang pertama kali diperkenalkan oleh Rakesh Agrawal bersama Tomasz Imielinski, dan Arun Swami. Paper “Mining association rules between sets of items in large databases” termasuk salah satu dari empat paper yang paling berpengaruh dalam bidang database menurut Wikipedia. Selain itu, pendekatan Apriori yang terkenal itu juga merupakan karya Rakesh Agrawal. Bahkan karena karya ini, Beliau memperoleh VLDB 10-Yr Most Influential Paper Award. Banyak paper dari Rakesh Agrawal merupakan paper yang berpengaruh dan banyak memberi inspirasi, paper-paper Beliau telah dikutip lebih dari 6000 kali. Beliau termasuk penulis yang paling banyak dikutip dalam bidang sistem database. Tidak hanya dalam bidang data mining, Beliau juga merupakan pioneer dari data privacy, termasuk privacy-preserving data mining.
Saat ini, Rakesh Agrawal adalah Microsoft Technical Fellow. Sebelum bergabung dengan Microsoft, Beliau merupakan IBM Fellow yang memimpin QUEST group di IBM Almaden Research Center, dan juga pernah bekerja di Bell Laboratory. Beliau sudah memiliki lebih dari 55 hak paten, penerima ACM SIGKDD First Innovation Award (2000), ACM SIGMOD Edgar F. Codd Innovation Award (2000), ACM SIGMOD Test of Time Award (2003), VLDB 10-Yr Most Influential Paper Award (2004), dan ComputerWorld First Horizon Award. Beberapa produk IBM seperti Intelligent Miner, DB2 Mining Extender, DB2 OLAP Server, dan WebSphere Commerce Server merupakan hasil penelitian Beliau. Keterlibatan Beliau dalam jurnal, workshop, dan konferensi internasional sangat banyak, bisa dilihat di homepagenya.

Referensi :
1. Dr. Rakesh Agrawal. http://rakesh.agrawal-family.com/.
2. Data-mining pioneer joins Microsoft. http://news.com.com/2100-1022_3-6072321.html.
3. List of Publications in Computer Science – Wikipedia. http://en.wikipedia.org/wiki/List_of_important_publications_in_computer_science#Databases.

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.

SIGKDD Exploration June 2006, Volume 8, Issue 1.
Special issue SIGKDD kali ini adalah Successful Real-World Data Mining Application dengan Guest Editor Gabor Melli, Osmar Zaiane, dan Brendan Kitts.
Sangat menarik karena pada edisi kali ini dapat ditemukan contoh-contoh aplikasi data mining pada dunia bisnis, medis, financial, telekomunikasi, dan ritel.
Silahkan kunjungi:
http://www.acm.org/sigs/sigkdd/explorations/issue.php?volume=8&issue=1&year=2006&month=06

Ross Quinlan termasuk salah seorang yang terkenal dalam data mining, terutama pada klasifikasi data. Setiap orang yang belajar klasifikasi data pasti tahu orang ini. Beliau memiliki kontribusi yang besar pada pengembangan awal algoritma Decision Tree. Decision Tree merupakan metode data mining yang paling populer dalam hingga saat ini. Berdasarkan polling KDnuggets (http://kdnuggets.com/polls/2006/data_mining_methods.htm) selama dua tahun, Decision Tree adalah metode yang paling banyak digunakan dalam data mining. Bahkan hasilnya mencapai 51.1% pada polling tahun ini.
Algoritma ID3, yang merupakan algoritma awal Decision Tree adalah hasil karya Ross Quilan, dan sampai sekarang algoritma ini terus dikembangkan. Berapa versi pengembangan ID3 adalah C4.5, C5.0, dan CART. Saat ini, Beliau terus mengembangkan tool data mining di RuleQuest, perusahaan data mining yang didirikannya.

Update 2006: Algoritma C4.5 berada pada urutan teratas top 10 algorithm in data mining yang dipresentasikan pada IEEE ICDM 2006.

Update 1 Oktober 2007: Dr. Ross Quinlan menerima penghargaan IEEE ICDM Research Contribution Award 2007. Selamat buat Dr. Ross Quinlan.

Referensi:
1. Ross Quilan. http://www.rulequest.com/Personal/
2. RuleQuest Research Data Mining Tools. http://www.rulequest.com/
3. KDnuggets Poll: Data Mining Methods. http://kdnuggets.com/polls/2006/data_mining_methods.htm

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.

Beberapa hari belakangan, saya lagi keluar kota. Ada beberapa hal yang harus dikerjakan sehingga beberapa posting terhenti. Mulai hari ini posting akan dimulai lagi.