Makine Öğreniminde Karar Ağaçlarının İlkeleri ve Algoritmaları | Popüler Bilim
Lei Feng net basın: Bu makalenin yazarı Li Xiangbin, Karmaşık Sistemler Devlet Anahtar Laboratuvarı, Otomasyon Enstitüsü, Çin Bilimler Akademisi'nden mezun oldu ve makine öğrenimi ve bilgisayarla görü alanlarında bir algoritma mühendisi. Lei Feng'in ilk makalesi.
Makine öğrenmesinde iki tür çok önemli problem olduğunu biliyoruz, biri sınıflandırma problemleri ve diğeri regresyon problemleri. Bugün tartışacağımız şey, sınıflandırma ve regresyon problemlerinde kullanılan, karar ağaçları adı verilen çok temel bir yöntemdir. Karar ağaçları da önemli etiket öğrenme yöntemleridir. Bu makaledeki içeriğin bir kısmı AI MOOC Akademisi "Makine Öğrenimi Teorisi ve Pratik İleri Özel Eğitim Sınıfı" ders notları.
Adından yola çıkarsak, karar vermenin anlamı, sınıflandırdığımız kategoriye ait olduğuna karar vermemiz gereken birçok kategori arasından karar vermemiz gerektiğidir. Karar verme ayrık değerlerine karar ağaçları denir ve karar alma sürekli değerlerine regresyon ağaçları denir. Akademik dilde, karar ağacının çıktısı ayrı bir rastgele değişkendir ve regresyon ağacının çıktısı sürekli bir rasgele değişkendir.Bu makalenin odak noktası, çıktısı ayrı bir rastgele değişken olan karar ağacını açıklamaktır.Karar ağacının işleyişini anladığınızda Mekanizmadan sonra, regresyon ağacı analojiyi izleyecektir.
İsmindeki ağaç, adından da anlaşılacağı gibi, modelin yapısının bir ağaç yapısı olmasıdır.Ağaç yapısının temel avantajı, sınıflandırmada daha okunabilir ve daha hızlı olmasıdır. Bir ağaç bir gövde ve yapraklardan oluşur.Karar ağacındaki yönlendirilmiş kenarlar ve düğümler bunlara karşılık gelir.Ayrıca iki tür düğüm vardır, biri iç düğümler ve diğeri yaprak düğümlerdir.
Yukarıdaki girişler, kelimenin tam anlamıyla anlaşılabilen bazı kavramlardır.Doğa açısından, bir karar ağacı, nesne öznitelikleri ve nesne değerleri arasındaki bir eşleştirme ilişkisini temsil eden öngörücü bir modeldir. Ağaçtaki her düğüm bir nesneyi temsil eder, dahili düğüm bir özelliği veya niteliği temsil eder, yaprak düğüm bir sınıfı temsil eder ve her çatallanma yolu olası bir öznitelik değerini temsil eder ve her bir yaprak düğüm, Kök düğümden yaprak düğüme giden yolla temsil edilen nesnenin değeri.
Bir karar ağacını eğer-o zaman kurallarının bir koleksiyonu olarak düşünebiliriz veya özellik uzayında ve sınıf uzayında tanımlanan koşullu bir olasılık dağılımı olarak anlaşılabilir. Bu bir eğer-ise kuralı olduğundan, karar ağacının önemli bir özelliği vardır: karşılıklı olarak dışlayıcı ve eksiksiz, yani her durum bir yol veya kural tarafından ve yalnızca bir yol veya bir kural tarafından kapsanır.
Pek çok soyut kavram, karar ağacının ne tür sorunlarla başa çıkılabileceğini söyledikten sonra karar ağacının açıklamasını genişletmek için pratik bir örnek kullanıyoruz ve herkesin başlamasına izin vermek için de çok basit bir Faliyet alani, sahne.
Xiao Ming işe giderse, iki ulaşım yöntemi seçebilir, biri işe gitmek için çevrimiçi taksi çağırma, diğeri ise çalışmak için ortak bir bisiklete binmek. Bu iki yaklaşımdan hangisinin uygulandığı üç faktöre bağlıdır. Biri hava koşullarıdır. Hava varsayımları şiddetli hava ve şiddetli olmayan hava olarak ikiye ayrılabilir. Diğer faktör Xiao Mingin iyi ruh hali ve kötü ruh hali olarak ikiye ayrılan ruh halidir. Son faktör, Xiao Ming'in geç kalmak üzere olup olmadığı. Üç faktörün Xiao Ming'in çalışma şekline karşılık geldiğini varsayarsak, aşağıdaki tablo:
Yukarıdaki tablo örnek set olarak adlandırdığımız şeydir.Dikkatli okuyucular yukarıdaki örnek setin bir durumu eksik bulabilir, yani durum kötü hava, Xiao Ming kötü bir ruh halinde, ancak çalışma saatleri nispeten bol, evet, Bu grubu kasıtlı olarak ihmal ettim çünkü bu grubu bir test seti yapmak istedim, böylece herkes bir karar ağacı oluşturarak Xiao Ming'in bu durumda hangi yolla işe gideceğini tahmin edebilsin.
Artık verilere sahip olduğumuza göre, nasıl bir karar ağacı oluşturabiliriz?
Bir karar ağacı oluştururken çözmemiz gereken üç sorun vardır:
-
Kök düğüme hangi koşul niteliğinin yerleştirildiği;
-
Aşağıdaki düğüme hangi nitelik yerleştirilir;
-
Ağacın büyümesinin ne zaman durdurulacağı.
Yukarıdaki üç problemi çözmek için bazı kavramları tanıtmamız gerekiyor.
Tanıtılan ilk kavram, İngilizce'de Entropi olarak adlandırılan bilgi entropisi olarak adlandırılır. Tom Mitchell'in kitabında bilgi entropisi şu şekilde açıklanmaktadır:
S kümesinin herhangi bir üyesini kodlamak için gereken minimum ikili basamak sayısını belirler (yani tek tip olasılıkla rastgele seçilen bir üye).
Dürüst olmak gerekirse, o zaman bu cümleyi anlamak benim için çok çaba gerektirdi. Aslında onu daha popüler bir dile çevirmek, yani bilgi entropisi "rastgele değişken Y'nin değerini tahmin etmenin" veya "rastgele değişkeni" ölçmenin zorluğudur. Belirsizlik.
İki örnekle açıklayın. Eğer yeryüzündeyseniz, elinizde demir bir blok tutarak, demir bloğa kuvvet uygulamadan bıraktığınızda, lütfen aşağıya mı düşeceğini yoksa yukarı mı uçacağını yargılayın. Sağduyumuza göre, biz yapabiliriz. Taşın düşeceğini yargılamak kolaydır, o zaman bu konunun sonucunu yargılamak çok kolaydır, o zaman şu andaki bilgi entropisi 0 olarak kabul edilebilir.
Başka bir örnek vermek gerekirse, homojen bir madeni paranın başının mı arkasının mı atıldığına karar vermeniz istenirse, bu soruyu yanıtlamak bizim için daha zordur, çünkü tura yukarı ve yedekleme olasılığı eşittir, yapamayız. Madalyonun hangi tarafının belirli bir dereceye kadar yukarı baktığına karar vermek daha zordur, bu nedenle şu anki bilgi entropisi 1 olarak kabul edilebilir.
Fakat yukarıdaki paragraf, tanım ve açıklama için nasıl matematik diline dönüştürülebilir? Birçok bilim insanı bilgi entropisi ifadeleri hakkında ne düşündüğünü ortaya koymuştur.Aşağıdaki tablodan bazı güncel bilgi entropisi tanımlarına bakabiliriz.
Çok fazla tanım olmasına rağmen, çoğu durumda Shannon bilgi entropisini kullanıyoruz, bu nedenle aşağıdaki diğer tanımları açıklamak için Shannon bilgi entropisini de kullanacağım.
Bilgi entropisinin ifadesine sahip olduğumuzda, aşağıdaki şekilde gösterildiği gibi ikili sınıflandırma probleminin bilgi entropi görüntüsünü elde edebiliriz.
Bu görselin ifade ettiği bilginin daha önce verdiğimiz örneğe tamamen karşılık geldiğini görebiliyoruz.Bir şeyi yargılamak çok kolay olduğunda yani yüksek bir olasılıkla olacağını veya olmayacağını düşünürüz, o zaman Bilgi entropisi 0'a doğru önyargılıdır. Bir şeyi yargılamak çok zor olduğunda, en zor zamanın olayın tüm olasılıklarının eşit olduğu, o zaman bilgi entropisinin 1 olduğunu düşünebiliriz.
Artık bilgi entropisi kavramına sahip olduğumuza göre, bilgi entropisine dayalı olması gereken ikinci kavramı tanıtıyoruz. Bu şartlı bilgi entropisidir. Bilgi entropisi kavramıyla, "rastgele değişken X'in önermesi altında rastgele değişken Y'yi tahmin etmenin" zorluğunun bir ölçüsü olan koşullu bilgi entropisi kavramını doğal olarak türetebiliriz.
Bilgi entropisi, yargılamanın zorluğunu temsil eder.İki kelimeli koşulla, bir koşulu bildikten sonra, değişkenin sonucunu yargılamanıza izin vermeniz anlamına gelir.Bu zamandaki zorluk, koşullu bilgi entropisidir. Yukarıdaki örnekte olduğu gibi, Xiao Ming geç kalacağını öğrendiği sürece işe taksiyle gideceğini, bu yüzden Xiao Ming'in bugün geç kalacağını öğrendiğimde taksiye binip binmeyeceğine karar vermem çok kolay oldu. Şu andaki koşullu bilgi entropisi, koşullu bilgi entropisi olan 0 olarak kabul edilebilir. Shannonın tanımlama yöntemi hala kullanılıyorsa, koşullu bilgi entropisinin matematiksel ifadesi
Verilen P (Y | X), P (X),
Bilgi entropisi ve koşullu bilgi entropisi kavramlarıyla, bilgi kazancı olan üçüncü kavramı doğal olarak türetebiliriz.Bilgi kazanımının matematiksel tanımı,
Bu matematiksel ifadeye bakarak bilgi kazanımının anlamını görmek zor değil. Eksi, hiç kimse bize bundan bahsetmediğinde sonucu yargılamanın zorluğu olan bilgi entropisidir; eksi, bir koşulu bildiğimizde sonucu yargılamanın zorluğu olan koşullu bilgi entropisidir. Bilgi kazanımı değişkeninin anlamı, x koşulunun yargı sonucuna ne kadar zorlandığını, yani X'in Y'yi tahmin etme yeteneği üzerindeki etkisini ölçmektir.
Mesela Happy Dictionary adında bir TV programı var Cevap veren kişi cevabı yargılayamadığında, yardım istemek için üç yol seçecek.Aslında yardım isteme yolu bir şarttır.Yarışmacı yardım isteme yolunu kullandığında, soruyu cevaplama zorluğu azalır. Bilgi kazancıdır. Zorluk büyük ölçüde azalırsa, bilgi kazanımının büyük olduğunu söyleyebiliriz.
Yukarıdaki üç kavramı tanıttıktan sonra, bir karar ağacı oluştururken karşılaştığımız ilk soruyu cevaplayabiliriz: hangi koşul niteliği kök düğüme yerleştirilmelidir.
Yerleştirme yöntemimiz şudur: kök düğüm olarak en büyük bilgi kazanımına sahip özniteliği seçin.
Bir veri kümesinin bilgi entropisi sabit olduğundan, bu sorun en küçük koşullu bilgi entropisine sahip özniteliğin seçilmesine dönüştürülür, bu nedenle kök düğümü tanımak için yalnızca en küçük koşullu bilgi entropisine sahip özniteliğe ihtiyacımız var.
Örneğin hesaplanmasıyla tek bir özelliğin koşullu bilgi entropisini ayrı ayrı hesaplayabiliriz Hesaplama süreci şu şekildedir:
Hesaplama yoluyla, Xiao Ming geç kaldıysa, bu özelliğin koşullu bilgi entropisinin en küçük olup olmadığını görebiliriz, sonra bu niteliği kök düğüm olarak alırız. Dolayısıyla, karar ağacının prototipi aşağıda gösterilmiştir.
Kök düğümün yerleştirme yöntemini bilerek, ikinci soru kolayca çözülür, hangi öznitelik aşağıdaki düğüme yerleştirilir. Elde edilen düğümü yalnızca yeni bir kök düğüm olarak görmemiz ve koşullu bilgi entropisini en aza indirme yöntemini kullanmamız gerekir. Xiao Ming'i yakında geç kalmaması şartı olarak kabul ediyoruz, bu yüzden tablo aşağıdaki gibi
Ardından koşullu bilgi entropisini tekrar hesaplayın, hesaplama süreci aşağıdaki gibidir:
Hava faktörlerinin koşullu bilgi entropisinin en küçük olduğunu, yani 0 olduğunu görüyoruz, dolayısıyla bir sonraki düğümümüz hava faktörleri. Şu anda karar ağacının büyümesini gerçekten sonlandırabiliriz, neden? Öyleyse, karar ağacının büyümesini ne zaman bitireceğimize nasıl karar vereceğiz?
Koşullu bilgi entropisini en aza indirdiğimiz için, tüm özelliklerin bilgi kazanımının küçük olduğunu veya aralarından seçim yapabileceğimiz bir özelliğimiz olmadığını fark ettiğimizde durabiliriz. Şimdiye kadar karar ağacımızı oluşturduk.
Ardından nihai karar ağacımız aşağıda gösterilmiştir:
Karar ağacından, hava kötü olduğunda, Xiao Ming'in kötü bir ruh hali içinde olduğunu, ancak çok fazla çalışma saatine sahip olduğunu, Xiao Ming'in seyahat modunun taksiye binmek olduğunu kolayca yargılayabiliriz.
Bu nedenle karar ağacının nasıl oluşturulacağı şu andan itibaren temelde herkese tanıtıldı.Akademik anlamda yaygın olarak kullanılan algoritmalar ID3 algoritması, C4.5 algoritması ve CART algoritmasıdır.Aslında bu algoritmalar yukarıda anlattığım yöntem ve fikirlerle aynıdır. Temelde aynı, ancak nesnel işlevi seçerken bazı farklılıklar var. Koşullu bilgi entropisini en aza indirmekten bahsediyorum. ID3 bilgi kazanımını, C4.5 algoritması bilgi kazanma oranını ve CART algoritması Gini'yi kullanıyor. İndeks, bu indeks bilgi entropisi ile ilgili yukarıdaki tabloda mevcuttur, ona başvurabilirsiniz.
Karar ağaçlarının ilkeleri ve algoritmaları temelde tanıtıldı, çünkü modelin aşırı uyumunu önlemek de makine öğreniminde önemli bir konudur, bu nedenle karar ağaçlarının budanmasını kısaca tanıtacağım.
Aşırı uydurmanın meydana gelmesinin nedeni, öğrenme sürecinde eğitim verilerinin doğru sınıflandırmasını nasıl geliştireceğimiz konusunda çok fazla düşünmemiz ve bu nedenle bazen aşırı karmaşık bir karar ağacı oluşturmamızdır. Karar ağacı karmaşık hale geldiğinde, test verilerinin sınıflandırılması daha az doğrudur ve bu da fazlasıyla uygundur. Bu nedenle Occam'ın ustura ruhuna göre karar ağacı sadeleştirilmelidir.Bu işleme budama denir.
Karar ağacı budama, karar ağacının genel kayıp işlevini en aza indirerek gerçekleştirilir. Karar ağacının kayıp işlevi şu şekilde tanımlanır:
Bunlar arasında, T ağacının yaprak düğümlerinin sayısı | T |, C (T) modelin eğitim verisine olan tahmin hatasını, yani model ile eğitim verisi arasındaki uyum derecesini, | T | model karmaşıklığını temsil eder ve parametresi, Negatif sayılar, ikisi arasındaki etkiyi kontrol eder.
C (T) şu şekilde hesaplanır:
Bunlar arasında t, T ağacının yaprak düğümüdür, yaprak düğümünde Nt örnekleri vardır, bunların arasında k kategorisinin Ntk örnek noktaları vardır, k = 1,2, ..., K.
Yukarıdaki ifade ile, minimize edilmiş kayıp fonksiyonunun hesaplanması gerçekleştirilebilir.Kayıp fonksiyonu, yaprak düğümünden özyinelemeli olarak hesaplanır.Bir yaprak düğüm grubu, ana düğümüne dönerse, bundan önceki ve sonraki tüm ağaç sırasıyla TB'dir. TA ile, karşılık gelen kayıp fonksiyonları C (TB) ve C (TA) 'dır, eğer
Budama yapılır, yani ana düğüm yeni bir yaprak düğümü olur.
Karar ağacı üretimi açık kaynak kitaplığı OpenCV'de uygulandığından, nihayet yukarıdaki örneğimi eğitmek için OpenCV kullanan bir kod parçası ekleyeceğim Amaç, herkesin kendi başına bir Hello World benzeri programı uygulamasına izin vermektir. OpenCV'nin konfigürasyon yöntemi burada tekrar edilmeyecektir, aşağıdaki kodu bir alıştırma olarak kullanabilirsiniz. OpenCV'nin dahili uygulamasıyla ilgilenen öğrenciler, OpenCV'nin resmi web sitesinden de indirilebilen kaynak kodunu öğrenebilirler.
Açıklanması gereken bir nokta, yukarıdaki senaryoları sayısallaştırmamız gerektiğidir ve yukarıdaki senaryoları, karar ağacının yapısını temsil etmek için 0 ve 1 olarak kullanıyoruz. Yani yeni tablo şuna benziyor:
Bu programı kullanarak, herkes Xiao Ming'in hava kötü ve ruh hali kötü olduğunda hangi ulaşım modunu seçeceğini tahmin etmek için bu karar ağacına bakabilir, ancak yeterli zaman vardır. Size gizlice anlatayım, yapay zekanın verdiği cevap şu şekildedir
Çıkarılan sonucumuzla aynı mı?
Lei Feng'den arkadaşlar şunu hatırlattı:
Derin öğrenme, yapay zeka alanında siyah bir teknolojidir. Hızlı bir başlangıç yapmak birçok öğrencinin her zaman hayali olmuştur. AI MOOC Academy, 17-18 Haziran tarihleri arasında 12 saatlik bir derin öğrenme kursuna sahiptir. Fastai Çin topluluğundaki en aktif dört katılımcı, derin öğrenmeye başlamanız için kapıyı açacaktır.
Kurs, Silikon Vadisi'nin "keşif + uygulama" öğretim modelini benimseyerek, proje zorluklarını birbiri ardına tamamlamak için bir derin öğrenme mühendisi rolüne hızlı bir şekilde girmenize izin verir. En popüler derin öğrenme becerilerini burada tek tek deneyimleyecek ve dersin tamamını öğreneceksiniz.CNN, RNN, VGG16, ResNet, InceptionCNN gibi en son teknolojileri sıkıştıracak ve derin öğrenme uygulamalarınızı birkaç saniye içinde hızlıca inşa edeceksiniz. Artık rüya değil.
Temel Python programlama deneyiminiz olduğu sürece, bu kursu iyi öğrenebilirsiniz! Sıfır programlama temeliyle bile, sizi uçmaya götürebiliriz!
