Bir önceki yazımda istatistiksel sınıflandırmanın ne olduğunu ve bir sınıflandırma yöntemi olan karar ağacı metodolojisi hakkında bilgi vermeyi amaçladım. Bu yazının konusunu ise karar ağacı algoritmaları oluşturmaktadır. Karar ağaçları, farklı yaklaşımlara sahip olan algoritmalarla şekillenir. Bilinen ilk algoritma olan ID3, John Ross Quinlan tarafından geliştirilmiştir.
ID3 Algoritması
Bilgi kazanımı ölçüsünü kullanır. Yani ilk adımda sınıfın entropisi hesaplanır. Daha sonra her bir nitelik için ayrı ayrı entropi hesaplanır ve sınıf entropisinden çıkarılır. Böylece en büyük bilgi kazanımına sahip nitelik seçilir ve dallanma başlar. Yalnızca kategorik değişkenler için hesaplanması yapılmaktadır.
C4.5 ve C5.0 Algoritmaları
ID3’ün nümerik değişkenler üzerine uygulanamaması sebebiyle yine Quinlan tarafından geliştirilen C4.5 algoritması, temelinde kazanç oranını kullanır. Her düğümden çıkan çoklu dallar ile ağaç oluşturur. Dalların sayısı tahmin edicinin kategori sayısına eşittir. Tek bir sınıflayıcıda birden çok karar ağacını birleştirir. Yinelemeli olarak ID3 uygulanır. C5.0 ise C4.5’ındaha geliştirilmiş halidir ve daha hızlıdır. Her iki algoritmanın sonuçları benzerdir. Fakat C5.0’da oluşan ağaç yapısı daha düzgündür.
CART Algoritması
Öznitelik seçim ölçüsü olarak Gini indeksini kullanır. İstatistikçi Leo Breiman (1928 – 2005) tarafından önerilen bu algoritma hem sayısal hem de kategorik veri kümelerinin analizinde kullanılmaktadır. Verinin hazırlanmasına ihtiyaç duyan bu algoritmanın son düğümünde iki adet dal oluşur. Sınıflandırma ile birlikte regresyon analizini de destekler.
CHAID Algoritması
Açılımı Chi-squared Automatic Interaction Detector olan CHAID, özellikle pazarlama alanında çok sık kullanılır ve günümüzde uygulama alanı gitgide genişlemektedir. Bu algoritma, bağımsızlık için Ki Kare Testini bir öznitelik seçim ölçüsü olarak kullanır. Aslında kullanılacak olan istatistiksel test, veri kümesinin ölçüm değerine bağlıdır. Dalların sayısı ikiyle başlar ve tahmin edicinin kategori sayısına göre değişir.
Minimum Açıklama Uzunluğu (MDL)
Minimum Açıklama Uzunluğu (MDL) ilkesine dayalı öznitelik seçim ölçüleri, birden çok değerli özniteliklere yönelik en az önyargıya sahiptir. MDL tabanlı ölçümler, “en iyi” karar ağacında en az sayıda uzunluğa sahip ağacı kodlar. Aynı zamanda aykırı değerler için yani ağaç tarafından doğru şekilde sınıflandırılmayan durumlarda ağaç yapısını düzenler. Ana fikri, en basit çözümlerin tercih edilmesidir.
QUEST Algoritması
Diğer algoritmalara göre daha çeşitli istatistiksel testlere dayanan ve oldukça hızlı sonuç veren bu algoritmayı 1997 yılında İstatistikçiler Yu-Shan Shih ve Wei-Yin Loh geliştirmişlerdir. İkili bölünmeli bir karar ağacı algoritmasıdır. Uygulanması CART algoritmasına benzerdir. Varsayılan olarak tarafsız değişken seçim tekniği kullanır. Verilerde eksik değer yoksa isteğe bağlı olarak CART algoritmasını kullanabilir. Tahminciyi seçmek için F ve Ki kare testleri gibi çeşitli önem testleri kullanır. Bir bölme noktası bulmak için o nitelik üzerinde ihmal edilebilir değişken seçim önyargısına sahiptir.
RandomTree Algoritması
RandomTree algoritması sonucu oluşturulan ağaç, olası ağaç kümesi içerisinden rastgele olarak seçilir. Bu algoritmaya göre oluşturulan ağaçlar, bir ağaç kümesi içerisinde yer alır ve her biri eşit olarak denenme şansına sahiptir. Ağaçların dağılımı düzgün (uniform) dağılım gösterir. Yani RandomTree algoritmasına göre her düğümde, belli bir sayıda rastgele seçilmiş özellikleri alarak ağaç oluşturulur.
RainForest Algoritması
Mevcut ana bellek miktarını herhangi bir karar ağacı indüksiyon algoritmasına göre daha verimli ve daha hızlı kullanmaktadır. Bu nedenle yöntem, çok büyük veri kümelerinde karar ağacı indüksiyonu için yüksek ölçeklenebilirliğe sahiptir. Kısaca RandomForest, birden fazla karar ağacını oluşturur ve daha doğru ve istikrarlı bir tahmin elde etmek için onları birleştirir. Dolayısıyla makine öğrenmesi sistemlerinin çoğunu oluşturan problemler için kullanılabilmektedir.
BOAT (Bootstrapped Optimistic Algorithm for Tree Construction)
Ölçeklenebilirliğe tamamen farklı bir yaklaşım getiren bir karar ağacı algoritmasıdır – herhangi bir özel veri yapısının kullanımına dayalı değildir. Bunun yerine eğitim verilerinin her birinde, belleğe sığan daha küçük birkaç örneğini (veya alt kümelerini) oluşturmak için “önyükleme” olarak bilinen istatistiksel bir teknik kullanır. Her alt küme, birkaç ağaçla sonuçlanan bir ağaç oluşturmak için çalışır. Ağaçlar incelenir ve yeni bir ağaç inşa etmek için kullanılır. Böylece eğitim verilerinin hafızaya sığdığı yeni bir ağaç ortaya çıkar. Yapılan son çalışmalara göre Rainforest’in diğer algoritmalara göre; BOAT’ın ise RainForest algoritmasına göre daha başarılı sonuçlar verdiği veri kümeleri bulunmaktadır.
Naive Bayes Karar Ağacı
Naive Bayes (Naive Bayes Tree – NBTree) karar ağaçları, Bayes kuralı ile karar ağacını birleştiren öğreticili bir sınıflandırıcıdır. Bu algoritma, etiketi bilinen veriyi koşullu bağımsız varsayar ve verilen her sınıfın olasılığını hesaplamak için Bayes kuralını kullanır. Naive Bayes’in araştırmacılar tarafından tercih edilmesinin nedeni, hızlı hesaplama performansı ve uygulama kolaylığıdır.
Sınıflandıracak algoritmaları birbirinden bağımsız olarak ele alır. Uygulama çerçevesinde niteliklerin birbirinden bağımsız olduğu kabulü vardır. Çünkü nitelikler birbirini etkilerse bu durumda olasılık hesabı zorlaşacaktır. Dolayısıyla her bir nitelik bağımsız ve eşit derecede önemli kabul edilir. Naive Bayes, sürekli veri ile çalışmaz. Bu nedenle sürekli değerleri içeren bağımlı ya da bağımsız değişkenler, kategorik veriye dönüştürülür. Modelin öğrenilmesi esnasında her çıktının öğrenme kümesinde kaç kere meydana geldiği hesaplanır. Bulunan bu değer, öncelikli olasılık olarak adlandırılır. Aynı zamanda bu yöntem, her bağımsız değişken/bağımlı değişken kombinasyonunun meydana gelme sıklığını bulmaktadır. Bu sıklıklar öncelikli olasılıklarla birleştirilmek suretiyle tahminde kullanılır.
Algı Temelli Sınıflandırma Yöntemi (PBC)
Bu algoritma, çok boyutlu görselleştirme tekniklerine dayalı etkileşimli bir yaklaşımdır. Kullanıcının bir karar ağacı oluştururken verilerle ilgili arka plan bilgisini birleştirmesine olanak tanır. Verilerle görsel olarak etkileşime girer. Böylece kullanıcının verileri daha derinlemesine anlamasını sağlar. Ortaya çıkan ağaçlar, geleneksel karar ağacı indüksiyon yöntemleri kullanılarak oluşturulanlardan daha küçük olma eğilimindedir ve bu nedenle, aynı doğruluğu elde ederken yorumlanması daha kolaydır.
PBC, sınıf etiketi bilgileriyle çok boyutlu verileri görüntülemek için piksel odaklı bir yaklaşım kullanır. Geleneksel karar ağacı algoritmaları, sayısal öznitelikler için yalnızca ikili bölmelere izin verir. Bununla birlikte PBC, kullanıcının birden çok bölme noktası belirlemesine izin vererek, tek bir ağaç düğümünden birden çok dalın büyütülmesini sağlar. Bazı durumlarda oluşan karar ağaçlarında eksik ya da uç değerlere sahip veri kümeleri yüzünden ağaç yapısında anormallikler görülebilir. Aşağıda anlatılacak olan ağaç budaması, bu soruna çözüm olarak istatistiksel temelli yaklaşım sunar.
Ağaç Budaması (Tree Pruning)
Ağaç budaması, sınıflandırma içinde gereksiz ya da tekrarlı yerlerin çıkarılması işlemidir. Böylece karar ağacı hem daha sade hem de daha anlaşılır olmaktadır. Bir karar ağacı oluşturulduğunda, dalların çoğu, gürültü veya aykırı değerler nedeniyle eğitim verilerindeki anormallikleri yansıtacaktır. Ağaç budama yöntemleri, verilerin aşırı uyum sorununu ele alır. Bu tür yöntemler, tipik olarak en az güvenilir dalları kaldırmak için istatistiksel yöntemler kullanır.
2 türlü budama yöntemi vardır: Ön budama ve Sonradan budama. Ön budama işlemi, ağaç oluşum aşamasında gerçekleştirilir. Bu yaklaşım, bir ağaç yapımını erkenden yani oluşum aşamasında durdurur. Örneğin, belirli bir düğümdeki eğitim demetlerinin alt kümesini daha fazla bölmemeye veya bölümlememeye karar vererek “budar”. Durduktan sonra düğüm bir yaprak olur. Yaprak, alt kümeler arasında en sık sınıfa veya bu dizilerin olasılık dağılımına sahip olabilir.
Bir düğümdeki demetlerin bölünmesi, önceden belirlenmiş bir eşiğin altına düşen bir bölünmeye neden olursa, verilen alt kümenin daha fazla bölünmesi durdurulur. Bununla birlikte, uygun bir eşik seçiminde zorluklar vardır. Yüksek eşikler aşırı basitleştirilmiş ağaçlara neden olabilirken, düşük seçilen eşikler çok az basitleştirme ile sonuçlanabilir. İkinci ve daha yaygın olan yaklaşım, alt ağaçları “tamamen büyümüş” bir ağaçtan kaldıran son budama yöntemidir. Belirli bir düğümdeki bir alt ağaç, dalları çıkarılarak ve bir yaprakla değiştirilerek budanır. Yaprak, değiştirilen alt ağaç arasında en sık kullanılan sınıfla etiketlenir ve böylece budama gerçekleşir.
Bitirirken;
Bir sınıflandırma problemi üzerine çalışırken yukarıda bahsedilen algoritmaları, elinizdeki veri kümesine bağlı olarak kullanmayı tercih edebilirsiniz. Hangi algoritmanın diğerinden daha iyi tahmin doğruluğuna sahip olduğunu söylemek teorik olarak güçtür. Fakat pratik olarak, bu algoritmaların veri kümenize uygun olanları seçebilir, farklı algoritmaları uygulayabilirsiniz. Ardından tahmin hatalarına bağlı olarak en iyi performans gösteren algoritmaya karar vermek için performans ölçütlerini karşılaştırabilirsiniz.
Kaynakça:
Bu yazı; Jiawei Han, Micheline Kamber ve Jian Pei tarafından yazılan “Data Mining: Concepts and Techniques Third Edition” adlı kitaptan uyarlanmıştır.
- QUEST Classification Tree (version 1.10.1). (Erişim Tarihi : 10.05.2021) QUEST (ccu.edu.tw)
- Veri Madenciliğinde Karar Ağacı Algoritmaları İle Bilgisayar Ve İnternet Güvenliği Üzerine Bir Uygulama. (Erişim Tarihi : 10.05.2021) ab225c69b017f13_ek.pdf (mmo.org.tr)
