Supervised Segmentation with Tree-Structured Models

Supervised Segmentation with Tree-Structured Models

Kami sekarang telah memperkenalkan salah satu ide dasar penambangan data: menemukan atribut informatif dari data. Mari lanjutkan topik membuat segmentasi supervised, karena sama pentingnya, pemilihan atribut saja sepertinya tidak cukup. Jika kita memilih variabel tunggal yang memberikan perolehan informasi paling banyak, kita membuat segmentasi yang sangat sederhana. Jika kami memilih beberapa atribut yang masing-masing memberikan beberapa perolehan informasi, tidak jelas cara menyatukannya. Ingat dari awal bahwa kami ingin membuat segmen yang menggunakan beberapa atribut, seperti “Middle-aged professionals who reside in New York City on average have a churn rate of 5%.” Sekarang kita akan memperkenalkan elegant application dari ide-ide yang telah kami kembangkan untuk memilih atribut penting, to produce a multivariate (multiple attribute) supervised segmentation.

Pertimbangkan segmentasi data untuk mengambil bentuk "pohon," seperti yang ditunjukkan pada Gambar 3-10. Pada gambar, pohon itu terbalik dengan akar di bagian atas. Pohon ini terdiri dari node, node interior dan node terminal, dan cabang yang berasal dari node interior. Setiap simpul interior dalam pohon berisi pengujian atribut, dengan setiap cabang dari simpul yang mewakili nilai yang berbeda dari atribut. 

Mengikuti cabang dari simpul akar ke bawah (ke arah panah), setiap jalur akhirnya berakhir pada simpul terminal, atau daun. Pohon menciptakan segmentasi data: setiap titik data akan sesuai dengan satu dan hanya satu jalur di pohon, dan dengan demikian hanya satu dan hanya satu daun. Dengan kata lain, setiap daun sesuai dengan segmen, dan atribut dan nilai di sepanjang jalur memberikan karakteristik segmen. Jadi jalur paling kanan di pohon pada Gambar 3-10 berhubungan dengan segmen “Orang yang lebih tua, pengangguran dengan saldo tinggi.

The tree is a supervised segmentation karena setiap daun mengandung nilai untuk variabel target. Karena kita berbicara tentang klasifikasi, di sini setiap daun mengandung klasifikasi untuk segmennya. Pohon seperti ini disebut pohon klasifikasi atau pohon keputusan yang lebih longgar.

Pohon klasifikasi sering digunakan sebagai model prediktif - "Tree Structured Models." Digunakan, ketika disajikan dengan contoh yang tidak kita ketahui klasifikasinya, kita dapat memprediksi pengelompokannya dengan mencari segmen yang sesuai dan menggunakan nilai kelas di daun . Secara mekanis, seseorang akan mulai pada simpul akar dan turun melalui simpul-simpul interior, memilih cabang berdasarkan nilai-nilai atribut tertentu dalam contoh.

The nonleaf nodes are often referred to as “decision nodes,” karena ketika menurun melalui pohon, pada setiap node, seseorang menggunakan nilai atribut untuk membuat keputusan tentang cabang mana yang akan diikuti. Mengikuti cabang-cabang ini akhirnya mengarah pada keputusan akhir tentang what class to predict: akhirnya node terminal tercapai, yang memberikan prediksi kelas. Di pohon, tidak ada dua orang tua yang berbagi keturunan dan tidak ada siklus; cabang-cabang selalu "menunjuk ke bawah" sehingga setiap contoh selalu berakhir di simpul daun dengan beberapa penentuan kelas tertentu.

Pertimbangkan bagaimana kita akan menggunakan pohon klasifikasi pada Gambar 3-10 untuk mengklasifikasikan contoh orang bernama Claudio dari Gambar 3-1. Nilai atribut Claudio adalah Balance = 115K, Employed = No, dan Age = 40. Kami mulai di node root yang menguji Employed. Karena nilainya adalah Tidak, kami mengambil cabang yang tepat. Tes selanjutnya adalah Balance. Nilai Balance adalah 115K, yang lebih besar dari 50K jadi kami mengambil cabang kanan lagi ke node yang menguji Age. Nilainya adalah 40 jadi kami mengambil cabang kiri.

Ini membawa kita ke simpul daun yang menentukan class = Not Write-off, mewakili prediksi bahwa Claudio tidak akan default. Cara lain untuk mengatakan ini adalah bahwa kita telah mengklasifikasikan Claudio ke dalam segmen yang didefinisikan oleh (Employed = No, Balance = 115K, Age <45) whose classification is Not Write -off.

Pohon klasifikasi adalah salah satu jenis model struktur pohon. Seperti yang akan kita lihat nanti, dalam aplikasi bisnis sering kita ingin memprediksi kemungkinan keanggotaan di kelas (misalnya, probabilitas churn atau kemungkinan write-off), daripada kelas itu sendiri. Dalam hal ini, daun dari pohon estimasi probabilitas akan mengandung probabilitas ini daripada nilai sederhana. Jika variabel target adalah numerik, daun pohon regresi mengandung nilai numerik. Namun, ide dasarnya sama untuk semua.

Pepohonan memberikan model yang dapat mewakili secara tepat jenis segmentasi yang diawasi yang sering kita inginkan, dan kita tahu bagaimana menggunakan model tersebut untuk memprediksi nilai untuk kasus baru (dalam “penggunaan”). Namun, kami masih belum membahas cara membuat model seperti itu dari data. Kami beralih ke itu sekarang.

Ada banyak teknik untuk menginduksi segmentasi yang diawasi dari kumpulan data. Salah satu yang paling populer adalah membuat model struktur pohon (induksi pohon). Teknik-teknik ini sangat populer karena model pohon mudah dimengerti, dan karena prosedur induksinya elegan (mudah dideskripsikan) dan mudah digunakan. Mereka kuat untuk banyak masalah data umum dan relatif efisien. Sebagian besar paket data mining termasuk beberapa jenis teknik induksi pohon.

Bagaimana cara kita membuat pohon klasifikasi dari data? Menggabungkan ide-ide yang diperkenalkan di atas, tujuan dari pohon adalah untuk menyediakan segmentasi yang diawasi lebih spesifik, untuk membagi contoh, berdasarkan atribut mereka, ke dalam subkelompok yang memiliki nilai yang sama untuk variabel target mereka. Kami ingin untuk setiap segmen "daun" mengandung contoh yang cenderung milik kelas yang sama.

Untuk mengilustrasikan proses induksi pohon klasifikasi, pertimbangkan contoh yang sangat sederhana yang ditunjukkan sebelumnya pada Gambar 3-2. 

Induksi pohon mengambil pendekatan divide-and-conquer, dimulai dengan seluruh dataset dan menerapkan pemilihan variabel untuk mencoba menciptakan subkelompok “paling murni” yang mungkin menggunakan atribut. Dalam contoh, salah satu caranya adalah memisahkan orang berdasarkan jenis tubuh mereka: persegi panjang versus oval. Ini menciptakan dua kelompok yang ditunjukkan pada Gambar 3-11. Seberapa baik partisi ini? Orang-orang tubuh persegi panjang di sebelah kiri kebanyakan Ya, dengan satu Tidak ada orang, jadi kebanyakan murni. Kelompok tubuh lonjong di sebelah kanan kebanyakan bukan orang, tetapi dua orang Ya. Langkah ini hanyalah aplikasi langsung dari ide pemilihan atribut yang disajikan di atas. Mari kita anggap “perpecahan” ini menjadi salah satu yang menghasilkan perolehan informasi terbesar.

Melihat Gambar 3-11, kita sekarang dapat melihat keanggunan induksi pohon, dan mengapa hal itu beresonansi dengan begitu banyak orang. Subkelompok kiri dan kanan adalah versi yang lebih kecil dari masalah yang awalnya kita hadapi! Kita bisa mengambil setiap subset data dan secara rekursif menerapkan pemilihan atribut untuk menemukan atribut terbaik untuk mempartisi itu. Jadi dalam contoh kita, kita secara rekursif mempertimbangkan kelompok oval-tubuh (Gambar 3 12). Untuk membagi kelompok ini lagi sekarang kita mempertimbangkan atribut lain: bentuk kepala. Ini membagi kelompok menjadi dua di sisi kanan gambar. Seberapa baik partisi ini? Setiap grup baru memiliki label target tunggal: empat (kepala persegi) No, dan dua (kepala bulat) dari Ya. Kelompok-kelompok ini "murni murni" sehubungan dengan label kelas dan tidak perlu membaginya lebih lanjut.

Kami masih belum melakukan apa pun dengan kelompok tubuh segi empat di sisi kiri Gambar 3-11, jadi mari kita pertimbangkan cara memisahkannya. Ada lima orang Ya dan satu Tidak ada orang. Ada dua atribut yang bisa kita bagi: bentuk kepala (persegi atau bulat), dan warna badan (putih atau abu-abu). Salah satu dari ini akan berhasil, jadi kami memilih warna tubuh secara sewenang-wenang. Ini menghasilkan pengelompokan pada Gambar 3-13. Ini adalah kelompok murni (semua dari satu jenis) jadi kami selesai. Pohon klasifikasi yang sesuai dengan pengelompokan ini ditunjukkan pada Gambar 3-14.

Singkatnya, prosedur induksi pohon klasifikasi adalah proses rekursif dari membagi dan menaklukkan, di mana tujuan pada setiap langkah adalah untuk memilih atribut untuk mempartisi kelompok saat ini menjadi subkelompok yang semurni mungkin sehubungan dengan variabel target. Kami melakukan pembagian ini secara rekursif, membelah lebih jauh sampai kami selesai. Kami memilih atribut untuk dibagi dengan menguji semua dari mereka dan memilih mana yang menghasilkan subkelompok paling murni. Kapan kita selesai? (Dengan kata lain, kapan kita berhenti mengulang?) Harus jelas bahwa kita akan berhenti ketika node murni, atau ketika kita kehabisan variabel untuk berpisah. Tetapi kita mungkin ingin berhenti lebih awal; kami akan kembali ke pertanyaan ini di Bab 5.