Karar Agaclari Algoritmasi
Karar Agaclari Algoritmasi (Decision Tree)
Karar ağaçları (Decision Tree) algoritması, supervised learningde (denetimli öğrenmede), tree based (ağaç bazlı) öğrenme algoritmalarından birisidir. Hem sınıflandırma (classification) hem de regresyon için kullanılabilir. Karar ağaçları için hazırlanmış olan notebooka buradan erişebilirsiniz
Random Forest (Rassal Orman) algoritmasının da temelini oluşturan karar ağaçları, oldukça önemli bir algoritmadır.
Öğrenilen ağaç, insan tarafından okunabilirliği artırmak için iç içe if-else kuralı olarak da temsil edilebilir. Ağaç yapısında ilk bölünmenin başladığı yere, kök, dalların uzaması ile gelişen kısımlara düğümler, ve en son kararın verildiği alt uçlarına ise yapraklar deniliyor.
Karar ağacı algoritması, belirli bir karar vermeden önce kendimize her soru sorduğumuzda insan beyni gibi çalışır. Örneğin, online alışverişte indirim kampanyaları mı oluyor? Eğer evet ise, o zaman almayacağım ürünleri alacağım.
Bu makale boyunca, makine öğrenmesi dünyasında hava durumu veri kümesi olarak adlandırılan ünlü bir veri kümesini kullanacağız. Veri kümesinin 4 özelliği (features) vardır, Gün, Hava, Nem, Rüzgar ve kategorik olan bir çıkış değişkeni y (evet veya hayır).
Yukarıdaki 14 örneklemden X ve Y arasındaki eşleştirmeyi öğrenmemiz gerekiyor. Tenis oynayıp oynanmayacağını yeni özellik vektörüne (X) dayanarak tahmin etmek istiyor muyuz?
Karar ağacı, eğitim kümesini alır ve özelliklere göre daha küçük alt kümelere böler. Bu prosedürü, tenis oynayıp oynanmayacağına dair bir belirsizlik kalmayana kadar, farklı alt kümeler ve niteliklere sahip bir ağacın her düğümünde tekrarlıyoruz.
Yeni veri noktası ortaya çıktığında, noktaların hangi alt kümelere düştüğüne bakarız ve bir noktayı o sınıfa sınıflandırırız.
Veri kümesini bölmek için Hava özniteliğini aldığımızı varsayalım. Hava’nın 3 olası değeri vardır, yani Güneşli, Bulutlu ve Yağmur. Bu yüzden veri kümemizi aşağıda gösterildiği gibi 3 küçük alt kümeye ayırdık:
Hava özniteliğini böldükten sonra, her zaman tenis oynanan bir saf düğümümüz var. Yukarıdaki, bulutlu (Overcast) sütununu incelediğimizde, sezgisel olarak, hava bulutlu olduğunda her zaman tenis oynandığını söyleyebiliriz.
Öte yandan, 2 saf olmayan setimiz var, yani bu alt kümelerde tenis oynanıp oynanmayacağı hakkında hiçbir fikrimiz yok? Bu alt kümeler için daha fazla bölme gereklidir. Bir Outlook alt kümesi olarak Sunny için Nemi (Humidity) aldığımızı ve daha sonra ayrıldığımızı varsayalım, ardından ağaç aşağıdaki gibi görünür:
Şimdi 2 saf ve 1 saf olmayan alt kümemiz var. Güneşli bir görünüm ve yüksek nemli olduğunda tenis oynanmaz ve normal nem için tenis oynanır.
Yağmurlu altküme için, saf bir altküme olmadığı için Wind’e dayalı olarak daha fazla bölme yaparız.
Bu noktada, tüm eğitim kümemizi, küçük kurallar kümesine dayalı olarak daha küçük alt kümelere ayırdık. Her alt küme saf durumdadır, yani tenis oynanıp oynanmadığı tüm alt kümelerde açıkça görülmektedir.
Örnekleri etiketlerle değiştirdikten sonraki son karar ağacı aşağıdaki gibi görünecektir:
Buraya kadar tartıştığımız veri kümesi, karar ağacının bir veri yapısı olarak tam olarak ne ürettiğinin bir gösterimidir.
Peki buraya kadar, ağacın nasıl ve nereden bölüneceği konusunda konuşmadık. Ağacın ilk bölümünde (root, kök kısmında), Hava’ya göre değil, nem durumunda göre ağacı bölsek ne olurdu? Veya rüzgar durumuna göre ağacı bölmeye başlasak ne olurdu? Aslında şu soruyu sormak istiyorum, Ağacı bölmeye nereden başlamalıyız? Bunun için information gain maksimum olan feature seçilmelidir. information gain’i maksimum yapan feature için de Entropy hesaplanmalıdır.
Entropy:
Entropi, verilerde mevcut olan belirsizlik miktarıdır. Bölünmeden önce, hangi noktaların olumlu, hangi noktaların olumsuz olduğu konusunda oldukça kararsızdık. Ama ayrılıktan sonra daha eminiz. Saf alt kümemiz varsa, o zaman tamamen eminizdir, diğer yandan %50–50 varsa, o zaman bu bölünmedeki noktalar hakkında tamamen belirsizizdir.
Sezgisel olarak, entropinin mümkün olduğunca küçük olması gerektiğini söyleyebiliriz. Yukarıdaki grafikte görüldüğü üzere, olasılık 0.5 olduğunda, entropi maksimum değerini almaktadır. Dolayısıyla Entropi hesabı yapılırken, değeri en düşük olan feature ile ağacı bölmeye başlamak gerekmektedir. Yani elimizde ya hep 0 ya da hep 1 kalmasını hedefliyoruz ki olasılık 0 veya 1 olsun, dolayısıyla da entropi 0 olsun.
4 adet örneğimiz olduğunda, olasılık durumlarına göre entropi hesabı aşağıda verilmiştir.
14 adet örneğimiz olduğunda, olasılık durumlarına göre entropi hesabı aşağıda verilmiştir. (Entropi fonksiyonunda, ilk değer pozitif sayısını, ikinci değer negatif sayısını simgelemektedir. )
Information Gain
Entropi sadece bir alt küme için hesaplanır ve her düğüm için birden fazla alt kümemiz vardır. Bu yüzden alt kümelerin her biri için ortalama entropi alacağız.
H(S) = Entropi değeri
S = toplam örneklem sayısı
Sv = v değeri için örneklem sayısı
Formül biraz karışık geldi ise açıklamaya çalışalım. Mesela wind sütunu için konuşuyorum. Entropi hesabı yapmak istedim. Wind sütunu için toplam toplam 9 pozitif ve 5 negatif değer mevcuttur. Entropi değeri formüle göre
H(S) = (— 9 / 14) * log(9/14) — (5/ 14) * log(5/14)
H(S) = 0.94 olarak hesapladım. Şimdi formülün ikinci kısmına geçelim. Her bir wind değeri için (weak ve strong), Sv / S = Sweak/Stoplam = 8/14, aynı şekilde Sstrong/Stoplam = 6/14 değerleri bulundu. Şimdi sadece weak ve strong değerlerine göre Entropi hesaplayıp yerine koymak kaldı. (weak için 6 pozitif, 2 negatif değer mevcut. strong için 3pozitif, 3 negatif değer mevcut.)
H(Sweak) = -(6/8) * log(6/8) -(2/8) * log(2/8) = 0.811
H(Sstrong) = -(3/6) * log(3/6) -(3/6) * log(3/6) = 1
Şimdi formülü yerine koyalım.
Gain = H(S) — 8/14 * H(Sweak) — 6/14 * H(Sstrong)
Gain = 0.94–8/14 * 0.811 — 6/14 * 1
Gain = 0.048
Gini impurity nedir?
Gini katsayısı tarafından geliştirilen eşitsizlik bir ölçüsüdür . Normalde bir ülkedeki gelir eşitsizliğini ölçmek için kullanılır, ancak herhangi bir eşitsiz dağılımı ölçmek için kullanılabilir.
Gini indeksi ve entropi, bilgi kazancını (information gain) hesaplamak için kriterdir. Karar ağacı algoritmaları, bir düğümü bölmek için bilgi kazancını kullanır.
Hem gini hem de entropi, bir düğümün safsızlığının ölçüleridir. Birden fazla sınıfı olan bir düğüm saf değildir, sadece bir sınıfı olan bir düğüm ise saftır. İstatistikteki entropi, düzensizliği ifade ettiği termodinamikteki entropiye benzer. Bir düğümde birden fazla sınıf varsa, o düğümde düzensizlik vardır.
Biz burada Gini değerini kendi algoritmamıza uyarlayacağız. Yani kendi datasetimizde Giniyi nasıl kullanacağımızı konuşacağız.
Wind sutunu için entropi hesabı yapmıştık ve 0.94 olarak hesaplamıştık. Şimdi wind sütunu için gini değerini hesaplayalım.
Wind sütunu için toplam toplam 9 pozitif ve 5 negatif değer mevcuttur. Gini formüle göre:
GI = 1 — [(9/14)**2 + (5/14)**2] = 0.46 değerini alır.
Şimdi burada kafamız karıştı. Çünkü entropi değeri 0.94 iken gini değeri 0.46 değerini aldı. Peki biz neye güveneceğiz? Hangisine göre işlem yapacağız?
Evet çok güzel sorularınızın cevabını hemen veriyorum. Entropi, 0 ile 1 arasında değer alırken, Gini 0 ile 0.5 arasında değerler alır. Yani aslında ikisine de güvenebiliriz. Peki hangisini tercih etmeliyim diye soruyorsanız, computation power (hesaplama güçlüğü olarak ifade edeyim) yönünde Gini daha iyidir. Çünkü herhangi bir logaritma hesabı yoktur.
Karar Ağacına ait Hiperparametreler:
Overfitting ve underfitting sorunlarından kurtulmak için hiperparametre değerlerine müdahale etmeliyiz. Unutmamız gereken önemli bir konu, Decision Tree modeli, overfit olmaya son derece meyilli bir modeldir.
max_depth= Karar Ağacının maksimum derinliğini ifade eder. Değer girilmezse limitsiz olur. Overfite karşı küçük değer girilmelidir.
min_samples_split=Bir düğümün bölünmeden önce sahip olması gereken minimum örnek sayısıdır. Örneğin 7 girildiğini varsayalım. Düğümdeki örneklem sayısı 7'den fazla ise, düğüm alt yapraklara doğru inecektir. Örneklem sayısı 7'den az ise, düğüm orada son bulacaktır.
min_samples_leaf=Bir yaprağın sahip olması gereken minimum örnek sayısıdır. Yani en sondaki yaprak belirtilen sayıdan daha az örnekleme sahip ise, bu yaprağa kadar düğümler inmeyecek ve bir önceki yaprakta son bulacak.
min_weight_fraction= min_samples_leaf’e benzer.Ağırlıklı örneklerin, toplam örnekler içerisindeki oranı. Ağacın dengeli gitmesi için kullanılır.
max_leaf_nodes= Maksimum yaprak sayısı. Aslında max_depth parametresi gibi, oluşacak maksimum yaprak sayısı ile, overfiti engellemeyi amaçlar. Max_depth daha keskin bir şekilde ağacı bitirirken, max_leaf_nodes daha yumuşak bir şekilde dallanmayı azaltmayı hedefler.
max_features= En iyi bölünmeyi ararken göz önünde bulundurulması gereken featureların sayısı.
Şimdi buraya kadar karar ağaçlarının çalışma prensiplerinden ve kullandığı matematikten bahsettik. Şimdi ise, aklımıza gelen sorulara cevap vererek devam edelim isterseniz.
Karar Ağacı algoritmasını kısaca açıklayınız?
Karar ağacı, esas olarak Regresyon ve Sınıflandırma için kullanılan denetimli bir makine öğrenme algoritmasıdır. Bir veri kümesini daha küçük ve alt kümelere ayırırken aynı zamanda ilgili bir karar ağaç kademeli olarak geliştirilir. Nihai sonuç, karar düğümleri ve yaprak düğümleri olan bir ağaçtır. Bir karar ağaç hem kategorik hem de sayısal verileri işleyebilir. Sınıflandırma ve Regresyon Ağacı (CART-Classification and Regression Tree) terimi analiz, yukarıdaki prosedürlerin her ikisine atıfta bulunmak için kullanılan bir şemsiye terimdir. Genellikle topluluk (ensemble) yöntemleri olarak adlandırılan bazı teknikler, birden fazla karar ağacı oluşturur.
Karar Ağaçlarının Avantajları nelerdir?
- Anlaması ve yorumlaması kolaydır. Kullanılan ağaç yapılar görselleştirilebilir.
- Bir karar ağacı, verilerin normalleştirilmesini gerektirmez.
- Bir karar ağacı, verilerin ölçeklendirilmesini de gerektirmez.
- Az oranda bir veri hazırlığına ihtiyaç duyar. Fakat unutulmamalıdır ki bu model kayıp değerleri desteklememektedir.
- Kullanılan ağacın maliyeti, ağacı eğitmek için kullanılan veri noktalarının sayısıyla logaritmiktir.
- Hem sayısal hem de kategorik verileri işleyebilir.
- Çok çıktılı problemleri ele alabilmektedirler.
- İstatistiksel testler kullanılarak bir modelin doğrulanması mümkündür.
- Karar ağaçları, parametrik olmayan bir yöntem olarak düşünülebilir. Yani uzay dağılımı ve sınıflandırma yapısı hakkında bir yaklaşıma sahip değilledir.
Karar Ağaçlarının Dezavantajları nelerdir?
- Verilerdeki küçük bir değişiklik, karar ağacının yapısında büyük bir değişikliğe neden olarak kararsızlığa neden olabilir.
- Veriyi iyi bir şekilde açıklamayan aşırı karmaşık ağaçlar üretilebilir. Bu durumda ağaç dallanması takip edilemeyebilir.
- Bir Karar ağacı için bazen hesaplama, diğer algoritmalara kıyasla çok daha karmaşık olabilir. Karar ağacı genellikle modeli eğitmek için daha fazla zaman gerektirir. Karar ağacı eğitimi, karmaşıklığı ve aldığı zaman daha fazla olduğu için nispeten pahalıdır.
- Ezbere öğrenme yaşanabilir (“over-fitting”). Bu problemin çözümü için model parametrelere kısıtlamalar ve budama gibi yöntemler kullanılabilir. Budama işlemi, az sayıda nesneyi barındıran yaprak düğümlerin karar ağacı grafiğinden atılmasını ifade etmektedir.
- Karar Ağacı algoritması, regresyon uygulamak ve sürekli değerleri tahmin etmek için yetersizdir.
Karar Ağacı algoritması hangi verilerde daha başarılı sonuçlar vermektedir?
- Sonlu sayıda öznitelik olduğunda, feature’lar, az sayıda kategorik değişkenler (örneğin: sarı, mavi,mor) içerdiğinde.
- Hedef değişkeni binary (1 ve 0) olduğunda. Ancak yinede ikiden fazla hedef değişkeni olduğunda da başarılı tahminlerde bulunabilir.
- Karar ağaçları doğal olarak ayrık ifadeleri temsil eder.
- Eğitim verileri hatalar içerebilir. Örneklerin sınıflandırılmasındaki veya bu örnekleri tanımlayan öznitelik değerlerindeki hatalar, karar ağaçları tarafından iyi bir şekilde işlenir ve onları sağlam bir öğrenme yöntemi haline getirir.
- Eğitim verileri Nan değerleri içerebilir. Karar ağacı yöntemleri, bazı eğitim örneklerinin bilinmeyen değerleri olduğunda bile kullanılabilir (örneğin, örneklerin yalnızca bir kısmı için nem bilinmektedir).
Information Gain dezavantajı nedir?
Information Gain (Bilgi kazanımı), bir özelliğin uygunluğuna karar vermek için genellikle iyi bir ölçü olmasına rağmen, mükemmel değildir. Çok sayıda farklı kategorik değer alabilen feature’lara Information Gain uygulandığında kayda değer bir sorun oluşur. Örneğin, bir işletmenin müşterilerini tanımlayan bazı veriler için bir karar ağacı oluşturduğunu varsayalım. Information Gain genellikle hangi featureların en alakalı olduğuna karar vermek için kullanılır, böylece bunlar ağacın köküne yakın bir yerde test edilebilir. Giriş featurelarından biri, işletmenin üyelik programının bir üyesiyse müşterinin üyelik numarası olabilir. Bu feature, yüksek bir karşılıklı bilgiye sahiptir, çünkü her müşteriyi benzersiz olarak tanımlar, ancak bunu karar ağacına dahil etmek istemiyoruz. Bir müşteriye üyelik numarasına göre nasıl davranılacağına karar vermek, daha önce görmediğimiz müşterilere genelleme yapmak (overfit) olası değildir.
Bu soruna karşı koymak için Ross Quinlan, bunun yerine bilgi kazancı ortalama veya daha yüksek olan nitelikler arasından en yüksek bilgi kazanım oranına sahip özniteliği seçmeyi önerdi. Bu, karar ağacını çok sayıda farklı değere sahip nitelikleri dikkate almaya karşı önyargılı kılarken, bilgi değeri bilgi kazancına eşit veya daha yüksek olduğu için çok düşük bilgi değerine sahip niteliklere haksız bir avantaj sağlamaz.
Karar Ağacının Öğrenmede Endüktif Önyargısı nedir?
Daha uzun ağaçlar yerine daha kısa ağaçlar tercih edilir. Köke yakın yüksek bilgi kazanımı nitelikleri yerleştiren ağaçlar, yapmayanlara tercih edilir.
Karar ağacında budama -pruning nedir?
Budama, karar ağaçlarının boyutunu küçülten, makine öğrenmesi ve arama algoritmalarında kullanılan bir tekniktir. Ağaçların örnekleri sınıflandırmak için az bilgi veren bölümlerini kaldırma işlemidir. Bu nedenle, bir karar düğümünün alt düğümlerini kaldırdığımızda, bu işleme budama (pruning) veya ters bölme (split işleminin tersi ) işlemi denir.
Karar ağaçları, Sınıflandırma ve Regresyon amacıyla öğrenme algoritmaları kullanılarak oluşturulan ağaç veri yapılarıdır. Bir karar ağacını öğrenirken en yaygın sorunlardan biri, modelin daha iyi bir doğruluğuna yol açan sonuçtaki ağacın optimal boyutunu öğrenmektir. Çok fazla dalı ve katmanı olan bir ağaç, eğitim verilerinin fazla takılmasına neden olabilir. Bir karar ağacının budanması, modelimizin görünmeyen verilere (test seti) iyi bir şekilde genellenmesi için eğitim verilerinin fazla takılmasını önlemeye yardımcı olur. Bir karar ağacını budamak, gereksiz ve yararlı bir bölünme olmayan bir alt ağacı kaldırmak ve bir yaprak düğümü ile değiştirmek anlamına gelir. Karar ağacı budaması iki türe ayrılabilir: pre-pruning ve post-pruning.
Agacı Neden budamalıyız?
Aslında şunu belirtmek isterim ki, budama konusu ile ilgili başka bir yazı yazılsa yeridir, çünkü budama, Karar ağaçlarında önemli bir yer tutar.
Makine öğrenmesi ve veri madenciliğinde budama, karar ağaçlarıyla ilişkili bir tekniktir. Budama, ağacın örnekleri sınıflandırma gücü sağlamayan kısımlarını kaldırarak karar ağaçlarının boyutunu küçültür. Karar ağaçları, tüm makine öğrenmesi algoritmaları arasında overfite karşı en hassas olanıdır ve etkili budama overfit olma olasılığı azaltabilir.
Karar ağacında, sayısal ve kategorik veriler nasıl ele alınır?
Karar ağacı, feature’larda aynı anda hem sayısal hem de kategorik değişkenleri işleyebilir. Bunu yapmakta herhangi bir problem yoktur. Bir karar ağacındaki her bölme (dalları ayırma) bir özelliğe dayanır.
- Özellik kategorik ise, bölme belirli bir sınıfa ait elemanlarla yapılır.
- Özellik sürekli ise, ayırma eşik değerinden daha yüksek (örneğin
X> 25) olan elemanlarla yapılır.
Her bölmede, karar ağacı o andaki en iyi değişkeni alacaktır. Bu, bölünmüş dallarla bir kirlilik ölçüsüne göre yapılacaktır. Ve split yapmak için kullanılan değişkenin kategorik veya sürekli olması konumuz ile pek ilgisi yoktur.
Karar Ağacı, Nan değerlerini nasıl ele alır?
- Nan değerini, o featuredaki en yaygın değer ile doldurabilirsiniz.
- Diğer örneklere dayalı olarak (mesela korelasyonu en yüksek olan başka bir feature) olası değerlerinin her birine bir olasılık atayarak eksik değeri doldurun.
50 tane küçük karar ağacı, 1 tane dallı budaklı karar ağacından daha iyi midir?
Evet. Çünkü, dallanıp budaklanan ağaçlar, overfit olmaya daha meyillidir. Ayrıca küçük, sığ karar ağaçları daha açıklanabilirdir.
Aslında bu soru şu anlama geliyor, random forest, decison treeden daha mı iyi? Evet, çünkü rastgele bir ormanı, güçlü bir öğrenici yapmak için birçok zayıf karar ağacını alan bir topluluk yöntemidir. Random forest, decision tree algoritmasına göre daha doğru, daha sağlam ve overfite daha az eğilimlidir.
Referanslar :
https://en.wikipedia.org/wiki/Information_gain_in_decision_trees
