Terjemahan disediakan oleh mesin penerjemah. Jika konten terjemahan yang diberikan bertentangan dengan versi bahasa Inggris aslinya, utamakan versi bahasa Inggris.

Bagaimana RCF Bekerja

Amazon SageMaker AI Random Cut Forest (RCF) adalah algoritma tanpa pengawasan untuk mendeteksi titik data anomali dalam dataset. Ini adalah pengamatan yang menyimpang dari data yang terstruktur dengan baik atau berpola. Anomali dapat bermanifestasi sebagai lonjakan tak terduga dalam data deret waktu, jeda periodisitas, atau titik data yang tidak dapat diklasifikasikan. Mereka mudah dijelaskan dalam hal itu, ketika dilihat dalam plot, mereka sering mudah dibedakan dari data “biasa”. Memasukkan anomali ini dalam kumpulan data dapat secara drastis meningkatkan kompleksitas tugas pembelajaran mesin karena data “reguler” sering dapat dijelaskan dengan model sederhana.

Ide utama di balik algoritma RCF adalah untuk membuat hutan pohon di mana setiap pohon diperoleh menggunakan partisi sampel data pelatihan. Misalnya, sampel acak dari data input ditentukan terlebih dahulu. Sampel acak kemudian dipartisi sesuai dengan jumlah pohon di hutan. Setiap pohon diberi partisi seperti itu dan mengatur subset titik itu menjadi pohon k-d. Skor anomali yang ditetapkan ke titik data oleh pohon didefinisikan sebagai perubahan yang diharapkan dalam kompleksitas pohon sebagai hasil menambahkan titik itu ke pohon; yang, dalam perkiraan, berbanding terbalik dengan kedalaman titik yang dihasilkan di pohon. Hutan penebangan acak memberikan skor anomali dengan menghitung skor rata-rata dari setiap pohon konstituen dan menskalakan hasilnya sehubungan dengan ukuran sampel. Algoritma RCF didasarkan pada yang dijelaskan dalam referensi [1].

Data Sampel Secara Acak

Langkah pertama dalam algoritma RCF adalah untuk mendapatkan sampel acak dari data pelatihan. Secara khusus, misalkan kita menginginkan sampel ukuran dari total titik data. Jika data pelatihan cukup kecil, seluruh kumpulan data dapat digunakan, dan kita dapat secara acak menggambar elemen dari kumpulan ini. Namun, seringkali data pelatihan terlalu besar untuk memuat sekaligus, dan pendekatan ini tidak layak. Sebagai gantinya, kami menggunakan teknik yang disebut pengambilan sampel reservoir.

Pengambilan sampel reservoir adalah algoritma untuk secara efisien menggambar sampel acak dari kumpulan data di mana elemen-elemen dalam dataset hanya dapat diamati satu per satu atau dalam batch. Faktanya, pengambilan sampel reservoir bekerja bahkan ketika tidak diketahui secara ap riori. Jika hanya satu sampel yang diminta, seperti kapan , algoritmanya seperti ini:

Algoritma: Pengambilan Sampel Waduk

Algoritma ini memilih sampel acak sedemikian rupa untuk semua . Ketika algoritma lebih rumit. Selain itu, perbedaan harus dibuat antara pengambilan sampel acak yang dengan dan tanpa penggantian. RCF melakukan pengambilan sampel reservoir ditambah tanpa penggantian pada data pelatihan berdasarkan algoritma yang dijelaskan dalam [2].

Melatih Model RCF dan Menghasilkan Kesimpulan

Langkah selanjutnya dalam RCF adalah membangun hutan potong acak menggunakan sampel data acak. Pertama, sampel dipartisi menjadi sejumlah partisi berukuran sama dengan jumlah pohon di hutan. Kemudian, setiap partisi dikirim ke pohon individu. Pohon secara rekursif mengatur partisinya menjadi pohon biner dengan mempartisi domain data menjadi kotak pembatas.

Prosedur ini paling baik diilustrasikan dengan contoh. Misalkan sebuah pohon diberikan dataset dua dimensi berikut. Pohon yang sesuai diinisialisasi ke simpul akar:

Gambar: Dataset dua dimensi di mana sebagian besar data terletak dalam cluster (biru) kecuali untuk satu titik data anomali (oranye). Pohon diinisialisasi dengan simpul akar.

Algoritma RCF mengatur data ini dalam pohon dengan terlebih dahulu menghitung kotak pembatas data, memilih dimensi acak (memberikan bobot lebih pada dimensi dengan “varians” yang lebih tinggi), dan kemudian secara acak menentukan posisi hyperplane “potong” melalui dimensi itu. Dua subruang yang dihasilkan menentukan sub pohon mereka sendiri. Dalam contoh ini, pemotongan kebetulan memisahkan titik tunggal dari sisa sampel. Tingkat pertama dari pohon biner yang dihasilkan terdiri dari dua node, satu yang akan terdiri dari subpohon titik di sebelah kiri potongan awal dan yang lainnya mewakili titik tunggal di sebelah kanan.

Gambar: Potongan acak yang mempartisi kumpulan data dua dimensi. Titik data anomali lebih mungkin terletak terisolasi dalam kotak pembatas pada kedalaman pohon yang lebih kecil daripada titik lainnya.

Kotak pembatas kemudian dihitung untuk bagian kiri dan kanan data dan proses diulang sampai setiap daun pohon mewakili satu titik data dari sampel. Perhatikan bahwa jika titik tunggal cukup jauh maka kemungkinan besar pemotongan acak akan menghasilkan isolasi titik. Pengamatan ini memberikan intuisi bahwa kedalaman pohon, secara longgar, berbanding terbalik dengan skor anomali.

Saat melakukan inferensi menggunakan model RCF terlatih, skor anomali akhir dilaporkan sebagai rata-rata di seluruh skor yang dilaporkan oleh setiap pohon. Perhatikan bahwa sering kali titik data baru belum berada di pohon. Untuk menentukan skor yang terkait dengan titik baru, titik data dimasukkan ke dalam pohon yang diberikan dan pohon secara efisien (dan sementara) dipasang kembali dengan cara yang setara dengan proses pelatihan yang dijelaskan di atas. Artinya, pohon yang dihasilkan seolah-olah titik data input adalah anggota sampel yang digunakan untuk membangun pohon di tempat pertama. Skor yang dilaporkan berbanding terbalik dengan kedalaman titik input di dalam pohon.

Pilih Hyperparameter

Hiperparameter utama yang digunakan untuk menyetel model RCF adalah num_trees dan. num_samples_per_tree Peningkatan num_trees memiliki efek mengurangi kebisingan yang diamati dalam skor anomali karena skor akhir adalah rata-rata skor yang dilaporkan oleh setiap pohon. Meskipun nilai optimal bergantung pada aplikasi, kami sarankan menggunakan 100 pohon untuk memulai sebagai keseimbangan antara kebisingan skor dan kompleksitas model. Perhatikan bahwa waktu inferensi sebanding dengan jumlah pohon. Meskipun waktu pelatihan juga terpengaruh, itu didominasi oleh algoritma pengambilan sampel reservoir yang dijelaskan di atas.

Parameter num_samples_per_tree ini terkait dengan kepadatan anomali yang diharapkan dalam kumpulan data. Secara khusus, num_samples_per_tree harus dipilih sedemikian rupa sehingga 1/num_samples_per_tree mendekati rasio data anomali dengan data normal. Misalnya, jika 256 sampel digunakan di setiap pohon maka kami mengharapkan data kami mengandung anomali 1/256 atau sekitar 0,4% dari waktu. Sekali lagi, nilai optimal untuk hyperparameter ini tergantung pada aplikasi.

Referensi