Skip to content
Kembali ke hasil pencarian

Aturan Asosiasi Semi-terawasi

Diperkenalkan oleh
Liu, B.; Hsu, W.; Ma, Y. (and subsequent researchers)
Tahun
2003–2010s
Jenis
Pattern mining with partial supervision
Keluarga
Machine learning

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Penambangan aturan asosiasi semi-terawasi memperluas pembelajaran aturan asosiasi klasik dengan menggabungkan sejumlah kecil data berlabel bersama dengan kumpulan data tak berlabel yang lebih besar.

Metode ini menggunakan informasi kelas yang diketahui atau batasan yang diberikan pengguna untuk memandu penemuan aturan yang sering secara statistik dan bermakna secara semantik, menjembatani penambangan pola tanpa pengawasan dengan pengawasan ringan.

Intuisi di balik metode

Penambangan aturan asosiasi standar menemukan semua pola ko-kemunculan yang sering tanpa rasa apa yang penting. Aturan asosiasi semi-terawasi mengubah ini dengan membiarkan sejumlah kecil contoh berlabel atau batasan domain mengarahkan pencarian: aturan yang selaras dengan struktur kelas yang diketahui lebih disukai daripada yang sering secara statistik tetapi tidak bermakna. Anggap saja seperti memberikan algoritma beberapa petunjuk tentang apa yang diperhatikan analis, sehingga algoritma berhenti memunculkan pola yang sepele atau sudah diketahui dan malah menyoroti hubungan yang benar-benar baru dan dapat ditindaklanjuti.

Sejarah

Penambangan aturan asosiasi diformalkan oleh Agrawal, Imielinski, dan Swami pada tahun 1993 dengan pengenalan algoritma Apriori, yang menargetkan penemuan itemset yang sering tanpa pengawasan dalam data keranjang pasar. Integrasi label kelas dan batasan ke dalam penambangan aturan asosiasi mendapatkan momentum pada awal tahun 2000-an, terutama melalui kerangka kerja CMAR dan CBA dari Liu dan rekan-rekannya, yang memperlakukan label kelas sebagai konsekuen aturan. Perluasan semi-terawasi muncul ketika para peneliti menyadari bahwa pengawasan parsial dapat mengurangi ledakan kombinatorial aturan kandidat sambil mempertahankan kontribusi statistik data tak berlabel. Pendekatan ini sekarang muncul di bioinformatika, penambangan data pendidikan, dan sistem rekomendasi.

Kapan digunakan

Gunakan penambangan aturan asosiasi semi-terawasi ketika Anda memiliki kumpulan data transaksional atau tabular yang besar, yang hanya sebagian kecil yang memiliki label kelas atau anotasi domain, dan Anda perlu menemukan pola ko-kemunculan yang benar-benar relevan dengan konsep target daripada sekadar sering. Metode ini sangat cocok untuk analisis keranjang pasar dengan beberapa hasil pembelian yang diketahui, penambangan catatan medis di mana hanya sebagian kasus yang memiliki diagnosis yang dikonfirmasi, dan kategorisasi teks di mana dokumen berlabel langka. Hindari jika bagian berlabel sangat kecil (kurang dari beberapa lusin contoh berlabel), ketika pengawasan penuh layak dilakukan, atau ketika persyaratan interpretasi menuntut model yang lebih sederhana seperti regresi logistik atau pohon keputusan.

Batasan dan pertimbangan

  • Kualitas aturan sangat bergantung pada kualitas dan keterwakilan kumpulan benih berlabel; subset berlabel yang bias menyebarkan bias ke dalam aturan yang ditemukan.
  • Kombinasi ambang batas dukungan, kepercayaan, dan batasan menciptakan ruang hyperparameter yang besar yang sulit disetel tanpa data validasi berlabel.
  • Biaya komputasi berskala dengan jumlah itemset kandidat; kumpulan data dengan ruang item berdimensi sangat tinggi memerlukan strategi pemangkasan yang agresif.
  • Lingkaran pelatihan mandiri dapat memperkuat kesalahan awal jika label semu awal berderau, yang menyebabkan pergeseran aturan antar iterasi.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Memanfaatkan data tak berlabel yang melimpah untuk menemukan pola yang secara statistik tidak terlihat hanya dengan data berlabel.
  • Batasan yang berasal dari label memangkas aturan yang tidak relevan, menghasilkan kumpulan aturan yang lebih kecil dan lebih dapat ditindaklanjuti daripada penambangan tanpa pengawasan murni.
  • Aturan tetap berupa pernyataan IF-THEN yang dapat dibaca manusia, mempertahankan keuntungan interpretasi dari pembelajaran aturan asosiasi klasik.
  • Penyempurnaan pelatihan mandiri dapat secara iteratif meningkatkan kualitas aturan dan cakupan label semu tanpa biaya pelabelan tambahan.
  • Fleksibel: batasan dapat mengodekan pengetahuan domain di luar label kelas sederhana (misalnya, urutan temporal, hierarki item).

Penerapan

  • Penambangan catatan medis di mana hanya sebagian catatan pasien yang memiliki diagnosis yang dikonfirmasi.
  • Analisis keranjang pasar yang dipandu oleh sebagian hasil pembelian bernilai tinggi yang diketahui.
  • Penambangan data pendidikan untuk menemukan pola perilaku belajar yang terkait dengan sejumlah kecil hasil kinerja siswa yang berlabel.
  • Penambangan teks dan kategorisasi dokumen dengan korpus berlabel yang langka.
  • Deteksi intrusi di mana hanya sebagian peristiwa jaringan yang merupakan serangan yang dikonfirmasi.
  • Sistem rekomendasi yang menggunakan peringkat pengguna yang jarang untuk membatasi aturan ko-kemunculan item.

Cara kerjanya

Cara kerjanya

1

Kumpulan data dibagi menjadi bagian berlabel kecil (dengan label kelas yang diketahui atau batasan yang ditentukan pengguna) dan bagian tak berlabel yang lebih besar. Contoh berlabel berfungsi sebagai benih atau jangkar yang mendefinisikan ruang konsep target, sementara transaksi tak berlabel menyediakan massa statistik yang diperlukan untuk menghitung jumlah dukungan yang andal.

2

Enumerasi itemset yang sering berjalan di seluruh data berlabel dan tak berlabel menggunakan algoritma klasik seperti Apriori atau FP-Growth, menghitung dukungan sebagai fraksi transaksi yang berisi itemset tertentu. Hanya itemset yang melebihi ambang batas dukungan minimum yang dipertahankan sebagai kandidat untuk pembuatan aturan.

Rumus
\text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \text{min\_sup}
3

Batasan yang diturunkan dari label atau ditentukan pengguna diterapkan untuk memangkas ruang kandidat. Batasan dapat berupa bentuk harus-terhubung (dua item harus muncul bersama dalam konsekuen dengan kelas target), tidak-boleh-terhubung (kombinasi tertentu dikecualikan), atau filter label kelas yang membatasi aturan mana yang melibatkan hasil target. Ini secara drastis mengurangi jumlah aturan palsu atau redundan.

4

Aturan valid X menyiratkan Y dihasilkan dari itemset yang sering bertahan, difilter oleh ambang batas kepercayaan minimum. Kepercayaan mengukur probabilitas kondisional bahwa Y muncul dengan syarat X. Dalam pengaturan semi-terawasi, aturan yang konsekuennya selaras dengan kelas berlabel atau batasan diprioritaskan atau diberi bobot lebih tinggi.

Rumus
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}
5

Aturan yang ditemukan dapat digunakan secara iteratif untuk menetapkan label semu ke transaksi yang sebelumnya tidak berlabel, yang kemudian dimasukkan kembali ke dalam putaran penambangan berikutnya. Lingkaran pelatihan mandiri ini secara bertahap memperkaya kumpulan berlabel dan mempertajam kumpulan aturan, konvergen ketika tidak ada aturan kepercayaan tinggi baru yang ditemukan atau batas iterasi yang telah ditentukan tercapai.

Kesalahan umum

  • Menetapkan dukungan minimum terlalu rendah tanpa batasan, membanjiri hasil dengan aturan yang sangat sering tetapi tidak informatif.
  • Mengabaikan ketidakseimbangan kelas dalam kumpulan benih berlabel, yang menyebabkan filter batasan mewakili kelas mayoritas secara berlebihan dalam aturan yang ditemukan.
  • Memperlakukan kepercayaan sebagai satu-satunya ukuran menariknya dan melewatkan aturan dengan lift atau keyakinan tinggi yang lebih berguna secara praktis.
  • Melewatkan evaluasi kualitas prediksi aturan yang ditahan dan menerima aturan yang ditambang apa adanya tanpa validasi pada data yang belum dilihat.
  • Mencampuradukkan asosiasi (ko-kemunculan) dengan kausalitas saat melaporkan temuan.

Pertanyaan yang sering diajukan

Bagaimana ini berbeda dari penambangan aturan asosiasi standar?

Penambangan aturan asosiasi standar sepenuhnya tanpa pengawasan: ia menemukan semua pola ko-kemunculan di atas ambang batas dukungan dan kepercayaan tanpa konsep kelas target. Aturan asosiasi semi-terawasi menggabungkan informasi label parsial atau batasan domain untuk memfilter dan memprioritaskan aturan yang relevan dengan hasil tertentu, menghasilkan kumpulan hasil yang lebih kecil dan lebih dapat ditindaklanjuti.

Berapa banyak data berlabel yang dibutuhkan?

Bahkan kumpulan data berlabel kecil dapat memberikan batasan yang berguna, tetapi kualitas benih lebih penting daripada kuantitas. Dalam praktiknya, memiliki setidaknya beberapa lusin contoh berlabel per kelas disarankan untuk menghindari batasan yang sangat bias. Jika label sangat jarang, hasil harus divalidasi dengan hati-hati pada subset berlabel yang ditahan.

Ambang batas apa yang harus saya tetapkan untuk dukungan dan kepercayaan?

Tidak ada jawaban universal: ambang batas bergantung pada ukuran kumpulan data, domain, dan berapa banyak aturan yang dapat Anda evaluasi secara realistis. Mulailah dengan ambang batas sedang (misalnya, dukungan 0,05–0,10, kepercayaan 0,60–0,80), periksa jumlah aturan yang dihasilkan, dan sesuaikan. Ketika batasan aktif, Anda sering kali dapat menggunakan ambang batas dukungan yang sedikit lebih rendah karena aturan yang tidak relevan difilter oleh kondisi label.

Bisakah metode ini menangani fitur kontinu atau numerik?

Penambangan aturan asosiasi secara native beroperasi pada item diskrit. Fitur kontinu harus didiskretisasi menjadi bin sebelum penambangan. Pilihan strategi binning memengaruhi itemset mana yang menjadi sering, jadi ada baiknya bereksperimen dengan binning lebar sama, frekuensi sama, dan yang digerakkan oleh domain dan memeriksa seberapa sensitif hasilnya terhadap pilihan tersebut.

Bagaimana cara mengevaluasi kualitas aturan yang ditemukan?

Selain dukungan dan kepercayaan, evaluasi aturan menggunakan lift (nilai di atas 1 menunjukkan ko-kemunculan nyata di luar kebetulan), keyakinan, dan leverage. Jika aturan digunakan untuk prediksi, ukur akurasi klasifikasi, F1, atau AUC pada set berlabel yang ditahan. Ukuran menarik saja tidak cukup untuk menilai kegunaan praktis.

Metode terkait

Sumber

  1. Liu, B., Hsu, W., & Ma, Y. (2003). Integrating Classification and Association Rule Mining. In Proceedings of the 4th IEEE International Conference on Data Mining (ICDM), pp. 339–346.

    Buka referensi publikasi
    Disalin.
  2. Association rule learning. Wikipedia.

    Buka referensi publikasi
    Disalin.