Data Mining - (Frequent Patterns, Association, and Correlations)

A. Pendahuluan: Apa Itu Frequent Pattern Analysis?

Dokumen ini membahas tentang frequent pattern analysis, sebuah teknik penting dalam data mining. Frequent pattern didefinisikan sebagai pola yang bisa berupa sekumpulan item, subsekuensi, atau substruktur yang muncul secara berulang dalam sebuah dataset. Konsep ini pertama kali diperkenalkan oleh Agrawal, Imielinski, dan Swami pada tahun 1993, khususnya dalam konteks penambangan frequent itemsets dan association rule mining.

Motivasi utama di balik frequent pattern analysis adalah untuk mengungkap regularitas yang tersembunyi dalam data. Beberapa pertanyaan kunci yang ingin dijawab melalui analisis ini meliputi:

• Produk apa saja yang sering dibeli bersamaan? Contoh klasik yang sering disebutkan adalah hubungan antara pembelian bir dan popok.
• Pembelian apa yang biasanya mengikuti pembelian komputer pribadi (PC)?
• Jenis DNA mana yang menunjukkan sensitivitas terhadap obat baru tertentu?
• Mungkinkah kita mengklasifikasikan dokumen web secara otomatis berdasarkan pola kata yang sering muncul?

Frequent pattern analysis memiliki beragam aplikasi, termasuk:

• Analisis data keranjang belanja: Memahami perilaku konsumen dalam pembelian.
• Cross-marketing: Mengidentifikasi produk yang dapat dipromosikan bersamaan.
• Desain katalog: Menyusun tata letak produk yang menarik berdasarkan pola pembelian.
• Analisis kampanye penjualan: Mengevaluasi efektivitas promosi produk.
• Analisis log web (click stream): Memahami navigasi pengguna di situs web.
• Analisis urutan DNA: Mengidentifikasi pola genetik yang relevan.

B. Mengapa Frequent Pattern Mining Begitu Penting?

Frequent pattern bukan sekadar artefak data; mereka mencerminkan properti intrinsik dan penting dari dataset itu sendiri. Oleh karena itu, frequent pattern mining menjadi fondasi bagi banyak tugas esensial dalam data mining. Beberapa di antaranya adalah:

• Analisis asosiasi, korelasi, dan kausalitas: Memahami hubungan antar variabel.
• Analisis pola sekuensial dan struktural: Mengenali urutan kejadian atau struktur yang berulang (misalnya, dalam analisis jaringan sosial atau pola molekuler).
• Analisis pola dalam data spatiotemporal, multimedia, time-series, dan stream: Mengidentifikasi tren atau anomali dalam berbagai jenis data yang kompleks.
• Klasifikasi: Menggunakan pola frekuensi untuk membedakan antar kelas objek.
• Analisis cluster: Mengelompokkan objek berdasarkan kesamaan pola frekuensi.
• Data warehousing: Mengoptimalkan penyimpanan dan pengambilan data dengan menggunakan konsep seperti iceberg cube dan cube-gradient.
• Kompresi data semantik: Memanfaatkan pola untuk mengompres data secara efisien sambil mempertahankan makna pentingnya.

Dengan demikian, frequent pattern mining memiliki aplikasi yang sangat luas dan mendasar dalam berbagai bidang.

C. Konsep-Konsep Dasar dalam Frequent Pattern Analysis

Untuk memahami frequent pattern analysis secara mendalam, kita perlu memahami beberapa konsep dasar:

• Itemset: Ini adalah sekumpulan satu atau lebih item. Jika kita memiliki k item, maka kita menyebutnya sebagai k-itemset. Contohnya, jika kita sedang menganalisis data keranjang belanja, itemset bisa berupa {'Roti', 'Susu', 'Telur'} .
• Support: Support mengukur seberapa sering sebuah itemset muncul dalam dataset. Ada dua jenis support:
  1) Absolute support (atau support count): Ini adalah jumlah transaksi yang mengandung itemset tertentu.
  2) Relative support: Ini adalah fraksi dari total transaksi yang mengandung itemset tersebut. Relative support sering diinterpretasikan sebagai probabilitas bahwa sebuah transaksi secara acak akan mengandung itemset tersebut.
• Frequent Itemset: Sebuah itemset dianggap frequent jika support-nya (baik absolute maupun relative) tidak kurang dari ambang batas minimum yang telah ditentukan sebelumnya, yang disebut minsup. Minsup adalah parameter penting yang mengontrol seberapa sering sebuah itemset harus muncul agar dianggap signifikan.

Contoh:

Misalkan kita memiliki tabel transaksi berikut:

Gambar 1. Tabel data transaksi

Jika kita menetapkan minsup sebesar 3 (artinya, sebuah itemset harus muncul dalam minimal 3 transaksi), maka itemset {'Beer', 'Diaper'} adalah frequent karena muncul dalam 3 transaksi (10, 20, dan 30).

D. Association Rules

Association rule mining adalah teknik untuk menemukan hubungan menarik antar variabel dalam dataset besar. Aturan asosiasi memiliki bentuk "Jika A, maka B" (A B), di mana A dan B adalah itemset.

Dua ukuran penting untuk aturan asosiasi adalah:

• Support: Ini mengukur seberapa sering itemset A dan B muncul bersamaan dalam dataset. Secara formal, support dari aturan A B adalah probabilitas bahwa sebuah transaksi mengandung AB.
• Confidence: Ini mengukur seberapa sering B muncul dalam transaksi yang mengandung A. Secara formal, confidence dari aturan A B adalah probabilitas kondisional bahwa sebuah transaksi mengandung B, dengan syarat mengandung A.

Aturan asosiasi dianggap "kuat" jika support dan confidence-nya melebihi ambang batas minimum yang ditentukan pengguna (minsup dan minconf).

Contoh (melanjutkan contoh sebelumnya):

Jika minsup = 50% (artinya, minimal 2.5 transaksi, yang kita bulatkan menjadi 3) dan minconf = 50%, maka kita dapat menemukan aturan asosiasi berikut:

• Beer Diaper (support = 60%, confidence = 100%): Ini berarti 60% dari transaksi mengandung baik Beer dan Diaper, dan 100% dari transaksi yang mengandung Beer juga mengandung Diaper.
• Diaper Beer (support = 60%, confidence = 75%): Ini berarti 60% dari transaksi mengandung baik Beer dan Diaper, dan 75% dari transaksi yang mengandung Diaper juga mengandung Beer.

E. Closed Patterns dan Max-Patterns 

Dalam banyak aplikasi, frequent pattern mining dapat menghasilkan sejumlah besar pola. Ini bisa menjadi masalah karena:

• Sulit untuk menyimpan dan memproses semua pola.
• Banyak pola mungkin berlebihan, karena pola yang lebih panjang sering kali mengandung sub-pola yang lebih pendek.

Untuk mengatasi masalah ini, konsep closed patterns dan max-patterns diperkenalkan.

• Closed Pattern: Sebuah itemset X adalah closed jika X adalah frequent dan tidak ada super-pattern (itemset yang lebih besar yang mengandung X) yang memiliki support yang sama dengan X. Dengan kata lain, X adalah closed jika kita tidak dapat menambahkan item apa pun ke dalamnya tanpa mengurangi support-nya. Closed patterns memberikan representasi ringkas dari pola frekuensi tanpa kehilangan informasi.
• Max-Pattern: Sebuah itemset X adalah max-pattern jika X adalah frequent dan tidak ada super-pattern Y yang mengandung X yang juga frequent. Dengan kata lain, X adalah max-pattern jika itu adalah pola frequent terpanjang yang mungkin. Max-patterns berguna untuk menemukan pola yang paling spesifik dan informatif.