Saya mencoba melacak siapa yang menemukan struktur dan algoritma data pohon keputusan.
Dalam entri Wikipedia tentang pembelajaran pohon keputusan ada klaim bahwa "ID3 dan CART ditemukan secara independen pada waktu yang bersamaan (antara 1970 dan 1980)". ID3 disajikan kemudian di:
- Quinlan, JR 1986. Induksi Pohon Keputusan. Mach Belajar. 1, 1 (Mar. 1986), 81-106
jadi saya tidak yakin klaim itu benar.
Saya menemukan menggunakan buku-buku Google referensi ke seri keputusan Statistik 1959 buku dan koleksi kertas Kerja 1958 . Konteksnya tidak jelas dan mereka tampaknya tidak menyajikan algoritma. Namun, mereka tidak mendefinisikan struktur data dan memperlakukannya seperti yang diketahui.
Menggunakan Google Cendekia saya menemukan kutipan kembali ke 1853 tetapi ini adalah kesalahan parsing dan bukan kutipan nyata dari tanggal itu.
Classification and Regression Trees Leo Breiman, Jerome Friedman, Charles J. Stone, R.A. Olshen (1984)tetapi yang pasti bukan yang paling awal. Wei-Yin Loh dari University of Wisconsin telah menulis tentang sejarah pohon keputusan. Berikut ini adalah makalah dan beberapa slide tentang sejarah.Jawaban:
Pertanyaan bagus. @ G5W berada di jalur yang benar dalam merujuk makalah Wei-Yin Loh. Makalah Loh membahas anteseden statistik pohon keputusan dan, dengan benar, melacak lokus mereka kembali ke kertas Fisher (1936) tentang analisis diskriminan - pada dasarnya regresi mengklasifikasikan beberapa kelompok sebagai variabel dependen - dan dari sana, melalui AID, THAID, CHAID dan Model CART.
Jawaban singkatnya adalah bahwa artikel pertama yang saya dapat temukan yang mengembangkan pendekatan "pohon keputusan" berasal dari tahun 1959 dan seorang peneliti Inggris, William Belson, dalam makalah berjudul Pencocokan dan Prediksi tentang Prinsip Klasifikasi Biologis , ( JRSS , Seri C, Statistik Terapan, Vol. 8, No. 2, Juni, 1959, hlm. 65-75), yang abstraknya menggambarkan pendekatannya sebagai salah satu sampel populasi yang cocok dan mengembangkan kriteria untuk melakukannya:
Jawaban "panjang" adalah yang lain, bahkan aliran pemikiran sebelumnya tampaknya relevan di sini. Sebagai contoh, breakout kohort usia-jenis kelamin yang sederhana yang digunakan dalam tabel kematian aktuaria menawarkan kerangka kerja untuk memikirkan keputusan yang sudah ada sejak beberapa abad yang lalu. Dapat juga dikatakan bahwa upaya dating kembali ke Babel menggunakan persamaan kuadrat, yang nonlinier dalam variabel (tidak dalam parameter, http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations. html ) memiliki relevansi, setidaknya sejauh mereka menunjukkan model parametrik pertumbuhan logistik (saya menyadari bahwa ini adalah peregangankomentar, silakan baca terus untuk motivasi yang lebih lengkap). Selain itu, para filsuf telah lama mengakui dan berteori tentang keberadaan informasi kualitatif yang diatur secara hierarkis, misalnya, buku Aristoteles tentang Kategori . Konsep dan asumsi hierarki adalah kunci di sini. Penemuan lain yang relevan dan jauh di kemudian hari adalah mendorong melampaui batas ruang Euclidean 3-D dalam pengembangan tak terbatas David Hilbert, Hilbert.ruang, kombinatorik, penemuan dalam fisika yang terkait dengan ruang 4-D Minkowski, jarak dan waktu, mekanika statistik di belakang teori relativitas khusus Einstein serta inovasi dalam teori probabilitas yang berkaitan dengan model rantai, transisi, dan proses markov. Intinya di sini adalah bahwa mungkin ada jeda yang signifikan antara teori dan aplikasinya - dalam hal ini, jeda antara teori tentang informasi kualitatif dan perkembangan yang terkait dengan penilaian, prediksi, klasifikasi dan pemodelan empiris mereka.
Dugaan terbaik adalah bahwa perkembangan ini dapat dikaitkan dengan sejarah peningkatan kecanggihan ahli statistik, sebagian besar di c ke-20, dalam mengembangkan model yang meningkatkan jenis skala selain kontinu (misalnya, nominal atau, lebih sederhana, informasi kategorikal), menghitung model data (poisson), tabel kontingensi lintas-silang, statistik nonparametrik bebas-distribusi, penskalaan multidimensi (misalnya, JG Carroll, antara lain), model dengan variabel dependen kualitatif seperti dua regresi logistik kelompok serta analisis korespondensi (kebanyakan di Belanda dan Prancis) di tahun 70an dan 80an).
Ada literatur yang luas yang membahas dan membandingkan dua regresi logistik kelompok dengan dua analisis diskriminan kelompok dan, untuk fitur nominal penuh, menemukan mereka memberikan solusi yang setara (misalnya, Analisis Multivariat Dillon dan Goldstein , 1984).
Artikel JS Cramer tentang sejarah regresi logistik ( The History of Logistic Regression , http://papers.tinbergen.nl/02119.pdf ) menggambarkannya sebagai berasal dari pengembangan univariat, fungsi logistik atau kurva berbentuk S klasik :
Model deterministik dari kurva logistik berasal pada tahun 1825, ketika Benjamin Gompertz ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) menerbitkan sebuah makalah yang mengembangkan model logistik nonlinear yang benar-benar pertama (nonlinear dalam parameter dan bukan hanya variabel seperti pada the Babylonians) - model dan kurva Gompertz.
Saya akan menyarankan bahwa mata rantai penting lainnya dalam rantai ini yang mengarah ke penemuan pohon keputusan adalah karya sosiolog Columbia Paul Lazarsfeld tentang model struktur laten. Karyanya dimulai pada 30-an, berlanjut selama Perang Dunia II dengan analisis kontennya dari surat kabar Jerman untuk OSS yang baru lahir (kemudian CIA, seperti yang dibahas dalam buku John Naisbett, Megatrends ) dan akhirnya diterbitkan pada tahun 1950. Andersen menggambarkannya dengan cara ini ( Analisis Struktur Laten: Sebuah Survei , Erling B. Andersen, Skandinavia Jurnal Statistik , Vol. 9, No. 1, 1982, hlm. 1-12):
Ada perbedaan yang bermanfaat yang perlu dibuat di sini, karena hal ini dapat dikaitkan dengan perkembangan dari AID ke CHAID (nanti CART), antara model berbasis tabel kontingensi (semua variabel dalam model ini diskalakan secara nominal) dan model kelas laten yang lebih baru (lebih lanjut tepatnya, model campuran hingga berdasarkan "campuran" skala dan distribusi, misalnya, Kamakura dan Russell, 1989, Model Pilihan Probabilistik untuk Segmentasi Pasar dan Struktur Elastisitas) dalam cara mereka membuat residu model. Untuk model tabel kontingensi yang lebih tua, jumlah sel yang melekat pada tabel yang sepenuhnya diklasifikasi-silang membentuk dasar untuk "replikasi" dan, oleh karena itu, heterogenitas dalam residu model yang digunakan dalam partisi ke dalam kelas. Di sisi lain, model campuran yang lebih baru bergantung pada tindakan berulang di satu subjek sebagai dasar untuk mempartisi heterogenitas dalam residu. Tanggapan ini bukanmenyarankan koneksi langsung antara model kelas laten dan pohon keputusan. Relevansi dengan AID dan CHAID dapat diringkas dalam statistik yang digunakan untuk mengevaluasi model, AID menggunakan distribusi F kontinu sedangkan CHAID menggunakan distribusi chi-square, sesuai untuk informasi kategori. Alih-alih dalam analisis dan pemodelan tabel kontingensi, LCM merupakan, menurut pendapat saya, bagian penting dalam teka-teki atau narasi yang mengarah pada pengembangan pohon keputusan, bersama dengan banyak inovasi lain yang telah dicatat.
CHAID adalah pengembangan kemudian, pertama kali diusulkan dalam disertasi PhD 1980 oleh Afrika Selatan Gordon Kass sebagaimana diuraikan dalam bagian Wiki ini pada CHAID ( https://en.wikipedia.org/wiki/CHAID ). Tentu saja, CART datang beberapa tahun kemudian di tahun 80-an bersama Breiman, et al, yang sekarang terkenal dengan buku Classification and Regression Trees .
AID, CHAID, dan CART, semuanya menempatkan struktur seperti pohon yang disusun secara hierarkis sebagai representasi realitas yang optimal. Mereka hanya melakukan ini menggunakan algoritma dan metode yang berbeda. Bagi saya, langkah selanjutnya dalam rantai inovasi progresif ini adalah munculnya teori struktur yang heterarkis. Seperti yang didefinisikan dalam artikel Wiki ini, heterarki "adalah suatu sistem organisasi di mana elemen-elemen organisasi tidak dimasuki (non-hierarkis) atau di mana mereka memiliki potensi untuk diperingkat sejumlah cara yang berbeda" ( https: //en.wikipedia .org / wiki / Heterarchy atau untuk perspektif yang lebih dalam dan lebih filosofis tentang heterarki, lihat Kontopoulos, The Logics of Social Structure). Dari sudut pandang empiris, analisis dan pemodelan struktur jaringan paling mewakili perkembangan historis ini dalam pemahaman struktur (misalnya, buku Freeman The Development of Social Network Analysis ). Sementara banyak analis jaringan akan mencoba dan memaksakan pengaturan hierarkis pada jaringan yang dihasilkan, ini lebih merupakan ekspresi asumsi yang tertanam dan tidak disadari daripada pernyataan tentang realitas empiris dari struktur jaringan multipleks di dunia yang kompleks.
Tanggapan ini menunjukkan bahwa busur evolusi yang mengarah pada pengembangan pohon keputusan menciptakan pertanyaan atau ketidakpuasan baru dengan metode "state-of-the-art" yang ada pada setiap langkah atau fase dalam proses, membutuhkan solusi baru dan model baru. Dalam hal ini, ketidakpuasan dapat dilihat dalam keterbatasan pemodelan dua kelompok (regresi logistik) dan pengakuan akan perlunya memperluas kerangka kerja tersebut ke lebih dari dua kelompok. Ketidakpuasan dengan asumsi tidak representatif dari distribusi normal yang mendasari (analisis diskriminan atau AID) serta perbandingan dengan "kebebasan" relatif yang dapat ditemukan dalam menggunakan asumsi dan model nonparametrik, bebas distribusi dan model (misalnya, CHAID dan CART).
Seperti yang disarankan, asal-usul pohon keputusan hampir pasti memiliki sejarah panjang yang berabad-abad lalu dan tersebar secara geografis. Berbagai aliran dalam sejarah manusia, sains, filsafat, dan pemikiran dapat ditelusuri dalam menguraikan narasi yang mengarah pada pengembangan banyak rasa pohon keputusan yang masih ada sampai sekarang. Saya akan menjadi yang pertama mengakui keterbatasan signifikan dari sketsa singkat saya tentang sejarah ini.
/ ** Tambahan ** /
Artikel 2014 dalam New Scientist ini berjudul Mengapa kita suka mengatur pengetahuan menjadi pohon? ( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ ), Ini adalah ulasan visualisasi data buku guru Manuel Lima The Book of Pohon-pohon yang melacak milenia dari penggunaan pohon sebagai visualisasi dan bantuan mnemonik untuk pengetahuan. Tampaknya ada sedikit pertanyaan tetapi bahwa model dan grafik sekuler dan empiris yang melekat dalam metode seperti AID, CHAID dan CART merupakan evolusi lanjutan dari tradisi klasifikasi keagamaan yang semula beragama ini.
Dalam video ini (diposting secara online oleh Salford Systems, pelaksana perangkat lunak CART), A Tribute to Leo Breiman , Breiman berbicara tentang perkembangan pemikirannya yang mengarah pada metodologi CART. Semuanya dimulai dengan dinding yang dilapisi siluet berbagai kapal perang era Perang Dunia II.
https://www.salford-systems.com/videos/conferences/cart-founding-fathers/a-tribute-to-leo-breiman?utm_source=linkedin&utm_medium=social&utm_content=3599323
Dalam membaca pengantar Theory of Finite and Infinite Graphs 1936 karya Denis Konig , secara luas dipandang sebagai memberikan landasan matematika pertama yang keras ke bidang yang sebelumnya dipandang sebagai sumber hiburan dan teka-teki untuk anak-anak, Tutte mencatat (hal. 13) bab itu 4 (mulai dari hlm. 62) buku Konig dikhususkan untuk pohon dalam teori grafik. Penjelasan Tutte tentang definisi Konig tentang pohon adalah "di mana grafik 'asiklik' adalah grafik tanpa sirkuit, pohon adalah graf asiklik terhubung terbatas ... dengan kata lain, dalam pohon ada satu dan hanya satu jalur dari sebuah diberikan simpul ke yang lain ... "Bagi saya (dan saya bukan ahli teori grafik atau ahli matematika), ini menunjukkan bahwa teori grafik dan pendahulu-pendahulunya di Situs Analisis Poincare atau Veblen ' ceramah tentang topologi kombinatorial, mungkin telah memberikan anteseden intelektual dan matematika awal untuk apa yang kemudian menjadi topik bagi ahli statistik.
Pohon Pengetahuan pertama secara luas dikaitkan dengan filsuf neoplatonik Porphyry yang, sekitar 270 CE menulis Pengantar Logika yang menggunakan pohon metaforis untuk menggambarkan dan mengatur pengetahuan ... http://www.historyofinformation.com/expanded.php? id = 3857
Baru saja menemukan referensi yang lebih awal ke Pohon Pengetahuan dalam Kitab Kejadian dalam Alkitab, yang dibahas dalam artikel Wiki ini ... https://en.wikipedia.org/wiki/Tree_of_life_(biblical) . Genesis mungkin berasal dari 1.400 SM berdasarkan referensi ini ... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ Apapun, Kitab Kejadian datang berabad-abad sebelumnya Porfiri.
sumber
Referensi besar pada CART adalah:
tapi itu jelas bukan pekerjaan paling awal dalam masalah ini.
Dalam makalahnya pada tahun 1986, Induksi Pohon Keputusan , Quinlan sendiri mengidentifikasi Hunt's Concept Learning System (CLS) sebagai prekursor ID3. Dia berkencan dengan CLS pada tahun 1963, tetapi referensi
Wei-Yin Loh dari University of Wisconsin telah menulis tentang sejarah pohon keputusan. Ada sebuah makalah
Ada juga slide Slide dari ceramah yang dia berikan pada topik.
sumber