Karar Ağacı Öğrenmesi (decision tree learning)

Yazan : Şadi Evren ŞEKER

Karar ağacı öğrenmesi (decision tree learning) yöntemi, makine öğrenmesi (machine learning) konularından birisidir. Literatürde karar ağacı öğrenmesinin alt yöntemleri olarak kabul edilebilecek sınıflandırma ağacı (classification tree) veya ilkelleştirme ağacı (regression tree ,tahmin ağacı) gibi uygulamaları vardır.

Karar ağacı öğrenmesinde, bir ağaç yapısı oluşturularak ağacın yaprakları seviyesinde sınıf etiketleri ve bu yapraklara giden ve başlangıçtan çıkan kollar ile de özellikler üzerindeki işlemeler ifade edilmektedir.

Bu yazı karar ağacı olarak geçen (decision tree) konusunu değil, veri madenciliği (data mining) ve makine öğrenmesi (machine learning) konularında geçen, karar ağacı öğrenmesi ile ilgilidir.

Karar ağacı öğrenmesi sırasında, öğrenilen bilgi bir ağaç üzerinde modellenir. Bu ağacın bütün iç düğümleri (interior nodes) birer girdiyi ifade eder. Örneğin aşağıda örnek bir öğrenilmiş ağaç gösterilmiştir:

Yukarıdaki şekil, kalp krizi geçiren kişilerin çeşitli özellikleri ele alınarak veriler üzerinden öğrenilmesi durumunda hayali olarak elde edilecek sonuçlardır. Diğer bir deyişle, iç düğümlerde (dikdörtgenler) çeşitli girdilere göre ağacın dallanması söz konusudur. Yapraklarda ise sonuç olarak elde edilen değerler gösterilmiştir.

Karar ağacı öğrenmesinde, ağacın öğrenilmesi sırasında, üzerinde eğitim yapılan küme, çeşitli özelliklere göre alt kümelere bölünür, bu işlem, özyineli olarak (recursive) tekrarlanır ve tekrarlama işleminin tahmin üzerinde bir etkisi kalmayana kadar sürer. Bu işleme özyineli parçalama (recursive partitioning) ismi verilir.

Genelde veri madenciliği sırasında verinin gelme şekli aşağıdaki gibidir:

(x,Y) = (x1,x2,x3,x4,…, Y)

Bu gösterime göre x1’den xn’e kadar olan değerler, sistemin girdileri iken, Y değeri sistemin çıktısı olarak elde edilmesi istenen değerdir. Örneğin yukarıdaki şekilde, kalp krizi geçirme oranı Y değeri olarak, “ailesinde kalp krizi geçirenlerin olup olmaması”, “kişinin yaşı”, “alkol kullanıp kullanmaması”, “sigara içip içmemesi” gibi bilgiler ise sistemin girdileri olan x değerleri olarak düşünülebilir.

Veri madenciliğinde karar ağacı öğrenmesi (decision tree learning) iki temel amaç için kullanılır. Bu amaçlar ve karar ağacı öğrenmesinin bu amaca yönelik özel isimleri aşağıdaki şekildedir:

• Sınıflandırma problemleri : Sınıflandırma ağaçları (Classification Tree) : Bir kişinin harcamalarından eğitim düzeyinin tahmini gibi, hedef kümeyi çeşitli sınıflardan birisine yerleştirmeyi amaçlayan ve sınıf tanımı yapan problemler.

• İlkelleme problemleri : İlkelleme ağaçları (Regression Trees): Sonuçta bir sınıf yerine sayısal bir değer döndüren veri madenciliği problemleri : Örneğin yukarıda verilen kalp krizi geçirme ihtimalleri gibi.

Ayrıca yukarıdaki iki terimi de içine alan bir çatı terim olarak CART (Classification and Regression Tree) terimi de kullanılmaktadır.

Karar ağacı öğrenme algoritmaları

Bu ağaçların çalıştırılması sırasında aşğıdaki bazı algoritmalardan yararlanılabilir (İnşaAllah vakit bulursam bunları da ayrı birer yazı halinde site üzerinden yayınlayacağım):

• Rastgele Orman (Random Forest) : Sınıflandırma işlemi sırasında birden fazla karar ağacı kullanılarak sınıflandırma değerinin yükseltilmesi hedeflenir.

• Hızlandırılmış Ağaçlar (Boosted Trees): Hem sınıflandırma (classification) hem de ilkelleme (regression) problemleri için kullanılabilen bir algoritmadır.

• Döndürme Ağacı (Rotation Forest) : Rastgele ağaca benzer şekilde birden fazla ağaç kullanılmaktadır ancak her ağaç, önce farklı bileşen analizi (Pricipal Component Analysis, PCA) kullanılarak eğitilmektedir. Bu eğitim için veri kümesinin rast gele seçilmiş bir alt kümesi kullanılmaktadır (sarnıçlama yöntemiyle).

• Ayırca aşağıdaki algoritmalar da karar ağacı öğrenmesinde kullanılmaktadır:

• ID3 algoritması

• C4.5 algoritması

• Chi-Kare Otomatik İlişki Tarayıcısı (Chi-Square Automatic Interaction Detector, CHAID) : Birden fazla seviyeye bölme işlemine izin veren bir sınıflandırma algoritmasıdır.

• MARS : Sayısal verilerin daha iyi işlenebilmesi için karar ağaçlarını iyileştiren bir yaklaşımdır.

Karar ağacı öğrenme algoritmalarının avantajları

• Anlaşılması ve yorumlanması basittir. Basit bir açıklama ile karar ağacı öğrenmesinin neticelerini insanlar anlayabilirler.

• Hızlı ver ön işlemesi gerektirir: Çoğu alternatif tekniklere göre çok az bir işleme ile veri kullanılabilir hale gelir. Ön işleme aşaması diğer alternatiflerine göre daha kısa ve basittir.

• Hem sayısal hem de sınıfsal verilerin işlenmesi için kullanılabilir: Çoğu makine öğrenmesi algoritması, ya sayısal uygulamalarda kullanışlı ya da sınıflandırma problemleri için kullanışlıdır. Karar ağacı öğrenmeleri ise, iki alanda da kullanılabilir.

• Beyaz kutu modelini kullanır: Yazılım mühendisliğinin (software engineering) bir yaklaşımı olan beyaz kutu modelinde, her adım görüntülenebilir ve yorumlanabilirdir. Yine bir yazılım mühendisliği uygulaması olan kara kutu yaklaşımı (black box approach) ise makine öğrenmelerinde daha çok yapay sinir ağları (artificial neural network) tarafından karşılanır. Bu yöntemde girdi ve çıktı yorumlanabilirken sistemin iç dinamiklerinin her adımda gözlemlenmesi ve yorumlanması mümkün değildir.

• Düşük hesaplama karmaşıklığına (computational complexity) sahiptir: Basit ve hızlı olmasından dolayı yüksek miktardaki veriyi kısa sürede işleyebilir ve alternatifi yöntemlere göre veri miktarı arttığında daha da tercih edilebilir olur.

Yöntemin Kısıtları

İyileştirilmiş (optimum) bir karar ağacı öğrenme algoritması çoğu zaman NP-Tam (NP-Complete) karmaşıklığa sahiptir. Bu karmaşıklığından sakınıldığı için çoğu karar ağacı öğrenme algoritması, sezgisel algoritmalar (heuristic algorithms) veya aç gözlü yaklaşımı (greedy approach) kullanmaktadır. Genelde bu uygulamalar, hedefe yönelik olarak, yerel olarak iyileştirilmiş (local optimum) bulmada başarılı olurken, genel iyileştirmeyi (global optimum) kaçırmaktadır.

Karar ağacı öğrenmesi ile çalışılırken kolaylıkla yapılacak bir hata, ağacı özel amaçlara yönelik olarak değiştirirken, bütün verinin özelliklerini modelleyemeyen bir ağaç ile karşılaşılabilir. Bu durum makine öğrenmesi konusunda aşırı uyum (overfitting) olarak geçmektedir. Bu durumu engellemek için budama (prunning) işlemleri yapılmaktadır.

Makine öğrenmesi konularında meşhur olan ve çoğu algoritma için problem olan karmaşık konular (örneğin özel veya problemi (XOR problem) , teklik problemi (parity problem) veya çoklayıcı problemi (multiplexer) problem gibi) karar ağacı öğrenmesi tarafından da modellenmesi ve çözümlenmesi zor konulardır. Bu problemlerin çözümü ya problemin tanım alanının yeniden tanımlanması (ki bu işleme haberselleştirme (propositionalisation) ismi verilir) veya algoritmanın daha açılayıcı bir gösterime dönüştürülmesi sayesinde yapılmaktadır.

Birden fazla seviyeden oluşan sınıfsal verilerin genelde diğer verilerden yüksek sonuç vermesi söz konusudur.