Skip to content
Kembali ke hasil pencarian

Pohon Keputusan Daring

Diperkenalkan oleh
Domingos, P. & Hulten, G.
Tahun
2000
Jenis
Incremental supervised classifier
Keluarga
Machine learning

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

Ukuran huruf

Apa fungsinya?

Pohon Keputusan Daring adalah pohon keputusan yang tumbuh secara inkremental dari aliran data kontinu tanpa meninjau kembali contoh-contoh sebelumnya.

Algoritma dominan, Pohon Hoeffding (VFDT), menggunakan batas Hoeffding untuk memutuskan kapan cukup banyak contoh telah dilihat di sebuah node untuk membaginya dengan percaya diri, memungkinkan klasifikasi berskala, waktu-nyata pada aliran data yang berpotensi tak terbatas.

Intuisi di balik metode

Pohon keputusan standar dibangun dengan memindai seluruh kumpulan data berulang kali untuk menemukan pembagian terbaik. Dalam pengaturan aliran, ini tidak mungkin karena data tiba satu per satu dan tidak dapat disimpan. Pendekatan daring hanya menyimpan statistik berjalan di setiap daun. Ketika cukup banyak contoh terkumpul, batas Hoeffding — jaminan statistik — mengonfirmasi bahwa atribut pembagian terbaik yang tampak akan tetap menjadi atribut terbaik bahkan jika kita telah melihat setiap contoh yang mungkin. Baru kemudian pohon benar-benar terbagi, tumbuh dari satu daun menjadi struktur yang semakin dalam tanpa pernah melihat kembali data masa lalu.

Sejarah

Algoritma dasar, Very Fast Decision Tree (VFDT) atau Pohon Hoeffding, diperkenalkan oleh Domingos dan Hulten di KDD 2000. Algoritma ini menerapkan ketidaksetaraan Hoeffding untuk membatasi kesalahan dalam memilih atribut pembagian dari aliran data, memungkinkan induksi pohon yang secara asimtotik benar tanpa menyimpan contoh. Hulten, Spencer, dan Domingos memperluas ini ke aliran yang mengalami hanyutan konsep pada tahun 2001. Pendekatan ini menjadi landasan kerangka kerja MOA (Massive Online Analysis) dan memengaruhi generasi metode ensemble streaming.

Kapan digunakan

Gunakan pohon keputusan daring ketika data tiba sebagai aliran kontinu, ketika menyimpan seluruh kumpulan data tidak mungkin karena kendala volume atau privasi, atau ketika model harus diperbarui secara waktu-nyata dengan setiap pengamatan baru. Sangat cocok untuk aliran sensor IoT, klasifikasi aliran klik, deteksi penipuan dengan pola yang berkembang, dan pengaturan apa pun di mana hanyutan konsep diharapkan dan model harus beradaptasi tanpa melatih ulang dari awal. Jangan gunakan ketika kumpulan data kecil dan statis — pohon keputusan standar atau hutan acak akan lebih cepat diimplementasikan dan lebih akurat. Hindari juga jika interpretasi ambang batas pembagian yang tepat sangat penting tanpa menerima bahwa ambang batas dapat bergeser seiring waktu.

Batasan dan pertimbangan

  • Akurasi pada kumpulan data kecil biasanya lebih rendah daripada pohon keputusan batch karena batas Hoeffding memerlukan banyak contoh sebelum pembagian awal dibuat.
  • Keputusan pembagian tidak dapat diubah dalam algoritma dasar; pembagian awal yang buruk dapat bertahan kecuali penggantian subtree eksplisit ditambahkan.
  • Menyesuaikan parameter kepercayaan delta dan periode tenggang antara evaluasi pembagian memerlukan pengetahuan domain.
  • Interpretasi pohon berubah seiring waktu saat pembagian baru ditambahkan, membuat pelaporan statis menjadi sulit.

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

Kelebihan

  • Memproses data dalam satu lintasan dengan memori konstan per node, diskalakan ke aliran yang secara teoritis tak terbatas.
  • Memberikan jaminan teoretis melalui batas Hoeffding bahwa pembagian secara asimtotik identik dengan pohon batch jika data cukup banyak.
  • Dapat menggabungkan detektor hanyutan untuk beradaptasi dengan distribusi non-stasioner tanpa pelatihan ulang penuh.
  • Menghasilkan model yang dapat digunakan sejak contoh pertama, tidak seperti metode batch yang memerlukan seluruh kumpulan data sebelum menghasilkan prediksi apa pun.
  • Secara alami menangani pengaturan throughput tinggi di mana penyimpanan data tidak praktis atau dibatasi secara hukum.

Penerapan

  • Deteksi penipuan waktu-nyata pada aliran transaksi keuangan.
  • Deteksi intrusi jaringan di mana statistik lalu lintas tiba terus menerus.
  • Klasifikasi data IoT dan sensor dengan perangkat tepi yang terbatas memori.
  • Aliran klik atau pemodelan perilaku pengguna di mana volume data menghalangi penyimpanan penuh.
  • Penyaringan spam adaptif karena pola linguistik dalam email berevolusi seiring waktu.
  • Pengklasifikasi streaming dasar yang menjadi tolok ukur bagi ensemble streaming yang lebih kompleks.

Cara kerjanya

Cara kerjanya

1

Setiap contoh berlabel tiba satu per satu dari aliran data. Pohon merutekannya dari akar ke bawah melalui pembagian yang ada ke daun yang sesuai, membuat prediksi untuk instans sebelum diberi label.

2

Statistik yang cukup untuk semua atribut pembagian kandidat — seperti hitungan bersyarat kelas atau rata-rata dan varians Gaussian — diperbarui di daun yang menerima instans. Tidak ada data mentah yang disimpan; hanya ringkasan ringkas ini yang tumbuh.

3

Batas Hoeffding (atau Chernoff) epsilon = sqrt(R^2 * ln(1/delta) / (2n)) mengkuantifikasi kesalahan maksimum antara atribut pembagian terbaik yang diamati dan pembagian terbaik yang sebenarnya dengan probabilitas setidaknya 1 - delta. Seiring bertambahnya n, epsilon menyusut menuju nol.

Rumus
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}
4

Jika perbedaan perolehan informasi antara kandidat pembagian terbaik dan kedua terbaik melebihi batas Hoeffding saat ini, daun diganti dengan node pembagian internal pada atribut pemenang, dan dua penghitung daun baru diinisialisasi. Jika tidak, node menunggu lebih banyak data.

5

Setiap instans yang tiba menerima prediksi kelas dari pohon saat ini sebelum labelnya digunakan untuk pembaruan. Secara opsional, detektor hanyutan (misalnya, ADWIN) memantau tingkat kesalahan daun; ketika hanyutan konsep terdeteksi, subtree dapat diganti untuk menjaga model tetap mutakhir.

Kesalahan umum

  • Menyetel delta kepercayaan Hoeffding terlalu longgar, menyebabkan pembagian prematur pada data awal yang tidak representatif.
  • Mengabaikan hanyutan konsep — menjalankan pohon daring stasioner pada data dengan distribusi yang bergeser menyebabkan penurunan akurasi yang senyap.
  • Membandingkan akurasi terhadap model batch yang dilatih pada seluruh data dari aliran yang sama, yang memberikan keuntungan tidak adil bagi model batch.
  • Lupa bahwa daun sebelum pembagian pertama mereka selalu memprediksi kelas mayoritas yang terlihat sejauh ini, yang bisa menyesatkan pada fase awal dengan aliran yang tidak seimbang.

Pertanyaan yang sering diajukan

Bagaimana Pohon Hoeffding berbeda dari pohon keputusan CART standar?

Pohon CART memindai seluruh kumpulan data di setiap node untuk menemukan pembagian terbaik secara global. Pohon Hoeffding sebaliknya mengamati contoh tiba satu per satu, dan hanya berkomitmen pada pembagian ketika teori statistik menjamin pemenang yang tampak akan tetap menang bahkan dengan lebih banyak data — tanpa menggunakan contoh mentah yang disimpan.

Apakah pohon keputusan daring menangani hanyutan konsep?

Pohon Hoeffding dasar tidak mendeteksi hanyutan secara otomatis. Perluasan seperti Pohon Keputusan Sangat Cepat yang Beradaptasi Konsep (CVFDT) dan versi yang digabungkan dengan detektor hanyutan ADWIN atau Page-Hinkley dapat mengganti subtree yang ketinggalan zaman ketika hanyutan terdeteksi.

Apa itu periode tenggang dan bagaimana cara mengaturnya?

Periode tenggang adalah jumlah contoh yang tiba di sebuah daun di antara evaluasi pembagian berturut-turut. Nilai yang lebih besar mengurangi komputasi tetapi menunda pembagian; nilai yang lebih kecil mengevaluasi pembagian lebih sering dengan biaya CPU yang lebih tinggi. Nilai default tipikal berkisar dari 200 hingga 1000 contoh.

Apakah pohon keputusan daring cocok untuk kumpulan data kecil dan statis?

Tidak. Untuk kumpulan data kecil yang sepenuhnya tersedia, pohon keputusan batch standar atau hutan acak hampir selalu akan mencapai akurasi yang lebih baik dengan kompleksitas yang jauh lebih sedikit. Pohon daring dirancang khusus untuk rezim streaming, skala besar, atau terbatas sumber daya.

Bagaimana akurasi dibandingkan dengan metode batch pada kumpulan data tetap?

Dengan data yang cukup, Pohon Hoeffding konvergen ke pohon yang sama yang akan dihasilkan oleh pembelajar batch, sehingga akurasi akhirnya cocok. Di awal aliran, sebelum daun melihat banyak contoh, akurasi lebih rendah daripada pohon batch yang dilatih pada data yang sama yang terlihat sejauh ini.

Metode terkait

Sumber

  1. Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.

    Buka referensi publikasi
    Disalin.
  2. Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.

    Buka referensi DOI
    Disalin.