Skip to content
Kembali ke hasil pencarian

Induksi Aturan (RIPPER)

Diperkenalkan oleh
William W. Cohen
Tahun
1995
Jenis
Supervised rule learning algorithm
Keluarga
Rule learning

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

Ukuran huruf

Apa fungsinya?

Induksi Aturan, dan khususnya algoritma RIPPER (Repeated Incremental Pruning to Produce Error Reduction), adalah metode pembelajaran mesin terawasi yang mempelajari sekumpulan aturan klasifikasi IF-THEN yang ringkas dari data pelatihan berlabel.

Diperkenalkan oleh William W. Cohen pada tahun 1995, RIPPER menerapkan strategi pisahkan-dan-taklukkan (separate-and-conquer) yang dikombinasikan dengan pemangkasan panjang deskripsi minimum (MDL) untuk menghasilkan aturan yang akurat dan dapat diinterpretasikan, menjadikannya algoritma penting dalam bidang pembelajaran aturan induktif.

Intuisi di balik metode

Bayangkan menulis daftar periksa diagnostik untuk seorang dokter: setiap aturan menangkap kombinasi gejala tertentu yang secara andal memprediksi diagnosis. RIPPER membangun daftar periksa ini secara otomatis dari data pasien. Algoritma ini menyusun satu aturan pada satu waktu, mencakup sebanyak mungkin kasus positif, kemudian memeriksa silang setiap aturan pada set data yang disisihkan untuk menghapus kondisi yang terlalu spesifik. Hasilnya adalah buku aturan yang pendek dan dapat dibaca manusia yang dapat diterapkan pada pasien baru tanpa perlu memeriksa seluruh riwayat pelatihan.

Sejarah

Induksi Aturan berakar pada sistem pembelajaran mesin awal seperti AQ (Michalski, 1969) dan CN2 (Clark dan Niblett, 1989). Makalah RIPPER Cohen tahun 1995 mengatasi inefisiensi komputasi dan kecenderungan overfitting dari pendahulunya dengan memperkenalkan pemangkasan inkremental dan optimasi berbasis MDL. Disajikan di ICML 1995, RIPPER dengan cepat menjadi algoritma tolok ukur karena akurasi dan transparansinya yang kompetitif, dan tetap menjadi referensi standar dalam literatur dan buku teks pembelajaran aturan.

Kapan digunakan

Induksi Aturan dengan RIPPER sesuai ketika interpretasi model adalah persyaratan utama, seperti dukungan keputusan klinis, deteksi penipuan, atau pengaturan kepatuhan peraturan. Algoritma ini bekerja dengan fitur nominal dan numerik campuran dan diskalakan secara wajar hingga puluhan ribu instance. RIPPER mengasumsikan label pelatihan cukup andal dan batas keputusan yang mendasarinya dapat diperkirakan oleh konjungsi yang sejajar sumbu. Algoritma ini kurang cocok untuk ruang fitur kontinu berdimensi tinggi atau tugas yang memerlukan keluaran terkalibrasi probabilitas; dalam kasus tersebut, pohon yang ditingkatkan gradien (gradient boosted trees) atau regresi logistik mungkin lebih disukai.

Batasan dan pertimbangan

  • Kualitas aturan menurun secara signifikan dalam ruang fitur berdimensi sangat tinggi atau jarang
  • Daftar aturan yang diurutkan dapat sensitif terhadap urutan kelas; kelas minoritas yang dipelajari terakhir mungkin menerima aturan yang lebih lemah
  • Tidak menghasilkan perkiraan probabilitas terkalibrasi, membatasi penggunaan dalam tugas yang sensitif terhadap biaya atau peringkat
  • Aturan konjungtif tidak dapat menangkap interaksi kompleks yang memerlukan batas non-sejajar sumbu tanpa rekayasa fitur

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

Kelebihan

  • Menghasilkan aturan IF-THEN yang dapat dibaca manusia yang dapat diaudit dan divalidasi oleh pakar domain
  • Pembelajaran pisahkan-dan-taklukkan yang efisien dengan pemangkasan yang dipandu MDL mengurangi overfitting
  • Menangani atribut nominal dan numerik tanpa memerlukan pra-pemrosesan ekstensif
  • Waktu pelatihan umumnya cepat dibandingkan dengan metode ensemble untuk ukuran dataset sedang

Penerapan

  • Dukungan keputusan klinis dan ekstraksi aturan diagnosis medis
  • Deteksi penipuan dan anomali dalam pemantauan transaksi keuangan
  • Kategorisasi teks menggunakan fitur leksikal dan struktural
  • Deteksi intrusi jaringan dengan aturan peringatan yang dapat diinterpretasikan
  • Prediksi churn pelanggan dengan aturan bisnis yang dapat ditindaklanjuti

Cara kerjanya

Cara kerjanya

1

RIPPER memproses satu kelas pada satu waktu, memperlakukan semua instance yang tersisa sebagai set negatif. Algoritma ini secara serakah menumbuhkan aturan konjungtif dengan berulang kali menambahkan kondisi yang memaksimalkan rasio positif terhadap total instance yang tercakup. Setelah tumbuh, aturan tersebut dikomitmenkan dan semua instance yang dicakupnya dihapus sebelum aturan berikutnya dipelajari, mengikuti paradigma pisahkan-dan-taklukkan klasik yang dijelaskan oleh Cohen (1995).

Rumus
\text{For each class } c \in \mathcal{C} \text{, grow a rule } R: \text{cond} \Rightarrow c \text{ maximizing } \frac{p}{p+n}
2

Setiap aturan kandidat dipangkas pada partisi validasi yang disisihkan menggunakan metrik (p - n) / (p + n), di mana p dan n menghitung instance yang dicakup dengan benar dan salah. Kondisi dihapus dari ekor aturan ke dalam selama pemangkasan meningkatkan nilai ini, melindungi dari overfitting yang disebabkan oleh konjungsi yang sangat spesifik yang kebetulan cocok dengan set pelatihan.

Rumus
\text{Prune rule } R \text{ by removing conditions to maximize } v(R, \text{prune set}) = \frac{p - n}{p + n}
3

Setelah semua aturan per-kelas dipelajari, RIPPER menjalankan fase optimasi opsional yang dipandu oleh prinsip Minimum Description Length. Untuk setiap aturan dalam set akhir, algoritma mempertimbangkan untuk mengganti atau merevisinya dan menerima perubahan hanya jika mengurangi panjang deskripsi gabungan dari kumpulan aturan dan data yang salah diklasifikasikan residual, menyeimbangkan akurasi terhadap kompleksitas model.

Rumus
\text{Minimize description length: } DL(\text{ruleset}) + DL(\text{data} \mid \text{ruleset})
4

Saat prediksi, aturan diterapkan sesuai urutan pembelajarannya. Instance yang tidak terlihat diberi label kelas dari aturan pertama yang semua kondisinya dipenuhi oleh nilai fitur instance tersebut. Jika tidak ada aturan yang aktif, instance tersebut masuk ke kelas default, biasanya kelas mayoritas dari data pelatihan, memastikan cakupan ruang input yang lengkap.

Rumus
\hat{y} = c_k \text{ where } R_k \text{ is the first rule in the ordered list that fires on instance } \mathbf{x}

Kesalahan umum

  • Menerapkan RIPPER ke dataset kecil tanpa data pemangkasan yang cukup menyebabkan aturan yang terlalu dipangkas dan cakupan rendah
  • Mengabaikan ketidakseimbangan kelas menyebabkan kelas default menyerap kelas minoritas, menutupi ingatan kelas minoritas yang buruk
  • Memperlakukan urutan aturan yang dipelajari sebagai kausal daripada prediktif menyebabkan kesalahan interpretasi dalam analisis eksplorasi
  • Melewatkan fase optimasi MDL (tersedia dalam beberapa implementasi) dapat meninggalkan aturan yang redundan atau bertentangan dalam set akhir

Pertanyaan yang sering diajukan

Bagaimana RIPPER berbeda dari pohon keputusan?

Keduanya mempelajari batas sejajar sumbu, tetapi pohon keputusan mempartisi seluruh ruang fitur secara rekursif, menghasilkan struktur hierarkis. RIPPER sebaliknya mempelajari daftar aturan yang diurutkan menggunakan pisahkan-dan-taklukkan, yang dapat menghasilkan representasi yang lebih ringkas ketika hanya sedikit pola spesifik kelas yang penting. Aturan juga lebih mudah dibaca oleh pakar domain secara terisolasi daripada jalur pohon.

Bisakah RIPPER menangani masalah multi-kelas?

Ya. RIPPER diperluas ke pengaturan multi-kelas dengan mempelajari aturan untuk setiap kelas secara bergantian, diurutkan dari kelas yang paling jarang hingga yang paling sering. Instance yang dicakup oleh aturan untuk kelas sebelumnya dihapus sebelum aturan untuk kelas berikutnya dipelajari. Aturan default menetapkan kelas mayoritas ke instance apa pun yang tidak dicakup oleh aturan eksplisit.

Apa peran prinsip Minimum Description Length dalam RIPPER?

MDL menyediakan kriteria formal untuk menyeimbangkan kompleksitas aturan terhadap kesesuaian data. Dalam fase optimasi, RIPPER lebih memilih kumpulan aturan yang panjang deskripsi totalnya—mengkodekan aturan dan instance yang salah diklasifikasikan—lebih pendek. Ini mencegah algoritma mempertahankan aturan yang terlalu spesifik yang menghafal noise daripada menangkap pola asli dalam data.

Metode terkait

Sumber

  1. Cohen, W. W. (1995). Fast effective rule induction. Proceedings of the 12th International Conference on Machine Learning, 115–123.

    Buka referensi DOI
    Disalin.