Pemisah yang tepat untuk klasifikasi biner dengan fitur numerik

Di unit ini, Anda akan menjelajahi algoritme pemisah yang paling sederhana dan umum, yang membuat kondisi dengan bentuk $\mathrm{feature}_i \geq t$ dalam setelan berikut:

• Tugas klasifikasi biner
• Tanpa nilai yang hilang di contoh
• Tanpa indeks prakomputasi pada contoh

Asumsikan satu set contoh $n$ dengan fitur numerik dan label biner "oranye" dan "blue". Secara formal, mari kita jelaskan set data $D$ sebagai:

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

dalam hal ini:

• $x_i$ adalah nilai fitur numerik dalam $\mathbb{R}$ (kumpulan bilangan riil).
• $y_i$ adalah nilai label klasifikasi biner dalam {oranye, biru}.

Tujuan kami adalah menemukan nilai ambang batas $t$ (nilai minimum) sehingga membagi contoh $D$ menjadi grup $T(rue)$ dan $F(alse)$ berdasarkan kondisi $x_i \geq t$ akan meningkatkan pemisahan label; misalnya, lebih banyak "oranye" contoh dalam $T$ dan banyak lagi "biru"

Entropi Shannon adalah ukuran gangguan. Untuk label biner:

• Entropi Shannon maksimum jika label dalam contoh seimbang (50% biru dan 50% oranye).
• Entropi Shannon berada pada nilai minimum (nilai nol) jika label dalam contoh murni (100% biru atau 100% oranye).

Gambar 8. Tiga tingkat entropi yang berbeda.

 

Secara formal, kita ingin menemukan kondisi yang mengurangi jumlah entropi distribusi label di $T$ dan $F$. Skor yang sesuai adalah penguatan informasi, yang merupakan perbedaan antara entropi $D$'s dan entropi {$T$,$F$}. Perbedaan ini disebut perolehan informasi.

Gambar berikut menunjukkan pemisahan yang buruk, dengan entropi tetap tinggi dan informasi yang diperoleh rendah:

Gambar 9. Pemisahan yang buruk tidak akan mengurangi entropi label.

 

Sebaliknya, gambar berikut menunjukkan pemisahan yang lebih baik saat entropi menjadi rendah (dan informasinya bertambah tinggi):

Gambar 10. Pemisahan yang baik akan mengurangi entropi label.

 

Secara formal:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

dalam hal ini:

• $IG(D,T,F)$ adalah perolehan informasi yang membagi $D$ menjadi $T$ dan $F$.
• $H(X)$ adalah entropi dari kumpulan contoh $X$.
• $|X|$ adalah jumlah elemen dalam kumpulan $X$.
• $t$ adalah nilai ambang batas.
• $pos$ adalah nilai label positif, misalnya, "biru" dalam contoh di atas. Memilih label yang berbeda sebagai "label positif" tidak mengubah nilai entropi atau perolehan informasi.
• $R(X)$ adalah rasio nilai label positif dalam contoh $X$.
• $D$ adalah set data (sebagaimana dijelaskan sebelumnya dalam unit ini).

Pada contoh berikut, kami mempertimbangkan set data klasifikasi biner dengan satu fitur numerik $x$. Gambar berikut menunjukkan nilai $t$ ambang batas yang berbeda (sumbu x):

1. Histogram fitur $x$.
2. Rasio "biru" contoh dalam $D$, $T$, dan $F$ ditetapkan sesuai dengan nilai ambang batas.
3. Entropi dalam $D$, $T$, dan $F$.
4. Perolehan informasi; yaitu, delta entropi antara $D$ dan {$T$,$F$} berdasarkan bobot contoh.

Gambar 11. Empat plot nilai minimum.

 

Plot ini menunjukkan hal berikut:

• Diagram "frekuensi" menunjukkan bahwa pengamatan relatif disebarkan dengan baik dengan konsentrasi antara 18 dan 60. Penyebaran nilai yang luas berarti ada banyak kemungkinan pemisahan, yang bagus untuk melatih model.

• Rasio "biru" label dalam set data adalah ~25%. "rasio label biru" plot menunjukkan bahwa untuk nilai ambang batas antara 20 dan 50:

  • Kumpulan $T$ berisi contoh label "biru" hingga 35% untuk nilai minimum 35.
  • Set $F$ berisi defisit komplementer dari "biru" contoh label (hanya 8% untuk ambang batas 35).

  "rasio label biru" dan "entropi" plot menunjukkan bahwa label dapat dipisahkan dengan relatif baik dalam rentang ambang batas ini.

• Pengamatan ini dikonfirmasi dalam "perolehan informasi" plot. Kita mendapatkan bahwa perolehan informasi maksimum diperoleh dengan t~=28 untuk nilai perolehan informasi ~0,074. Oleh karena itu, kondisi yang ditampilkan oleh pemisah akan menjadi $x \geq 28$.

• Keuntungan informasi selalu positif atau null. Nilai ini bertemu ke nol saat nilai ambang batas bertemu ke nilai maksimum / minimumnya. Dalam kasus tersebut, $F$ atau $T$ menjadi kosong sedangkan yang lainnya berisi seluruh set data dan menunjukkan entropi yang sama dengan yang ada di $D$. Penguatan informasi juga dapat menjadi nol jika $H(T)$ = $H(F)$ = $H(D)$. Pada nilai minimum 60, rasio "biru" label untuk $T$ sama dengan $$ dan sama dengan $$

Nilai kandidat untuk $t$ dalam kumpulan bilangan riil ($\mathbb{R}$) tidak terbatas. Namun, dengan jumlah contoh terbatas, hanya ada sejumlah pembagian $D$ dalam $T$ dan $F$. Oleh karena itu, hanya sejumlah terbatas nilai $t$ yang dapat diuji.

Pendekatan klasik adalah mengurutkan nilai x_i dalam meningkatkan urutan x_s(i) sehingga:

$$ x_{s(i)} \leq x_{s(i+1)} $$

Kemudian, uji $t$ untuk setiap nilai di antara nilai yang diurutkan berturut-turut sebesar $x_i$. Misalnya, Anda memiliki 1.000 nilai floating-point dari fitur tertentu. Setelah mengurutkan, misalkan dua nilai pertama adalah 8,5 dan 8,7. Dalam hal ini, nilai minimum pertama yang akan diuji adalah 8,6.

Secara formal, kami mempertimbangkan nilai kandidat berikut untuk t:

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

Kompleksitas waktu algoritme ini adalah $\mathcal{O} ( n \log n) $ dengan $n$ jumlah contoh dalam node (karena pengurutan nilai fitur). Saat diterapkan pada pohon keputusan, algoritme pemisah akan diterapkan ke setiap node dan setiap fitur. Perhatikan bahwa setiap node menerima ~1/2 dari contoh induknya. Oleh karena itu, menurut teorema master, kompleksitas waktu pelatihan pohon keputusan dengan pemisah ini adalah:

$$ \mathcal{O} ( m n \log^2 n ) $$

dalam hal ini:

• $m$ adalah jumlah fitur.
• $n$ adalah jumlah contoh pelatihan.

Dalam algoritme ini, nilai fitur tidak berpengaruh; yang penting hanyalah urutannya. Karena alasan ini, algoritme ini bekerja secara independen dari skala atau distribusi nilai fitur. Itulah sebabnya kita tidak perlu menormalkan atau menskalakan fitur numerik saat melatih pohon keputusan.