Veri Madenciliğinde Karar Ağacı Nedir ve Algoritmaları Nelerdir ?

0
93

Veri Madenciliğinde Karar Ağacı Nedir ve Algoritmaları Nelerdir ?

Temel fikir, giriş verisinin bir kümeleme algoritması yardımıyla tekrar tekrar gruplara bölünmesine dayanır. Grubun tüm elemanları aynı sınıf etiketine sahip olana kadar kümeleme işlemi derinlemesine devam eder.Entropiye dayalı sınıflandırma ağaçları (ID3, C4.5) ve Regresyon ağaçları (CART) olmak üzere iki kategoride birçok algoritma önerilmiştir.Karar ağaçları çok boyutlu (özellikli) veriyi belirlenmiş özellik üzerindeki bir şart ile parçalara böler. Her seferinde verinin hangi özelliği üzerinde hangi şarta göre işlem yapacağına karar vermek çok büyük bir kombinasyonun çözümüyle mümkündür. 5 özellik ve 20 örneğe sahip bir veride 106 dan fazla sayıda farklı karar ağacı oluşturulabilir. Bu sebeple her parçalanmanın metodolojik olması gerekir.Quinlan’e göre veri, bir özelliğe göre bölündüğünde elde edilen her bir veri kümesinin belirsizliği minimum ve dolayısıyla bilgi kazancı maksimum ise en iyi seçim yapılmış demektir. Buna göre önerdiği ilk algoritma ID3’te tek tek özellik vektörleri incelenir ve en yüksek bilgi kazancına sahip özellik, ağaçta dallanma yapmak için tercih edilir.

Ön budama işlemi ağaç oluşturulurken yapılır. Bölünen nitelikler, değerleri belli bir eşik de- ğerinin (hata toleransının) üstünde değilse o noktada ağaç bölümleme işlemi durdurulur ve o an elde bulunan kümedeki baskın sınıf etiketi, yaprak olarak oluşturulur.

Sonradan budama işlemi ağaç oluşturulduktan sonra devreye girer. Alt ağaçları silerek yaprak oluşturma, alt ağaçları yükseltme, dal kesme şeklinde yapılabir

Veri Madenciliğinde Karar Ağacı Nedir ve Algoritmaları Nelerdir ?
Veri Madenciliğinde Karar Ağacı Nedir ve Algoritmaları Nelerdir ?

Hata toleransı %33 seçilirse “Nem” düğümünün alt dallarındaki “Evet” oranı %30’dur. Bu yüzden “Nem” düğümü budanıp yerine “Hayır” yaprağı konur.

Veri Madenciliğinde Karar Ağacı Nedir ve Algoritmaları Nelerdir ?
Veri Madenciliğinde Karar Ağacı Nedir ve Algoritmaları Nelerdir ?

C4.5 algoritması

C4.5 algoritması, karar ağacı oluşturmak için yaygın kullanılan bir algoritmadır. Bu algoritmanın işleyişi temel olarak ID3 algoritması gibidir. ID3 algoritmasından farklı olarak kesikli değişkenlerin yanında sürekli değişkenleri de kullanır. Yani C4.5 algoritması yardımıyla sayısal değişenlerde algoritmada kullanılabilir. Sayısal değişkenler gruplandırılarak işleme sokulur.

C4.5 algoritması, diğer verilerden öngörerek kayıp değerleri de kullanır.Böylelikle daha anlamlı ve daha duyarlı kurallar elde edilebilen bir ağaç üretilir.Bu değerleri kullanabilmek için düzeltilmiş bir kazanç ölçütüne ihtiyaç vardır. Düzeltilmiş kazanç ölçütü;

kazanç(A) = F(H(p,n) – E(A))

formülüyle hesaplanır. Burada “F”, düzeltme faktörüdür.

Bir veya birden çok alt ağacı ortadan kaldırarak onların yerine uygun yapraklar koyma işlemiyle karar ağaçlarının basitleştirilmesine karar ağacını budama denir. C4.5 algoritması budama işlemine olanak sağlamaktadır. Bir alt ağacın yerine yaprak koyma işleminde algoritma, tahmini hata oranını azaltmak ve sınıflandırma modelinin kalitesini arttırmayı hedefler. Ancak hata oranını hesaplamak kolay  değildir. Yalnızca eğitim verilerine dayanan hata oranı uygun bir tahmin sağlamaz. Tahmini hata oranını öngörmek için, ilave test örneklerinden yeni bir küme oluşturulur. Bu teknik, ilk olarak önceden var olan örnekleri eşit aralıklı bloklara ayırır. Her blok için bu bloklardan beklenen bütün örneklemlerle karar ağacı oluşturulur ve verilen örneklem blokları ile test edilir. Uygun test ve eğitim örneklemleri ile karar ağacı budama işleminin temel fikri ortaya çıkar. Bu temel fikir,  gizli test örneklemlerinin sınıflandırma doğruluğunda katkısı olmayanları ağacın parçalarından (alt ağaçlardan) çıkarmaktır. Böylelikle daha az karmaşık ve daha anlaşılır bir ağaç elde edilmiş olur . Basit bir veri yığınından oluşturulan karar ağacının çok büyük çıkmasına  şişme (overfitting) denir. Ağaç oluşturma algoritmaları her zaman şişme oluştururlar. Oluşan ağacın çok büyük olması bu etkiyi artırır. Ağacın dengeli olabilmesi için belli bir büyüklüğün üstünde olmalıdır. Bu büyüklü arttıkça test verisinin hata oranı yükselmekte ve ağacın doğruluğu azalmaktadır. Bu durumda ağaç budama işlemi kullanılır.  Eğitim kümesi ile test kümesinin ağaç boyuna göre doğruluk performansı şekil 8’ de gösterilmiştir

karar ağacı boyuna göre doğruluk performansı
karar ağacı boyuna göre doğruluk performansı

iki çeşit budama yöntemi vardır bunlar;

– Ön budama

– Sonradan budama

Bazı durumlarda örneklem kümesini daha fazla bölmemek kararı alınır.

Bölme işlemine son verme ölçütü olarak ki-kare gibi istatistiksel testler uygulanır.

Bölünme öncesine ve sonrasında önemli bir fark yoksa o zaman söz konusu düğüm

bir yaprak olarak gösterilir. Bu ön budama çeşididir.

Seçilen bir doğruluk ölçütü kullanarak bazı ağaçlar budanabilir. Bu yöntem ağaç oluşturulduktan sonra uygulanır. Bundan dolayı bu yönteme sonradan budama denir. C4.5 algoritmasında bu budama yöntemi kullanılır .Bu yöntem, kötümser budama olarak da adlandırılır. Örneğin, “T” , “S” eğitim kümesinden üretilmiş yapraksız bir karar ağacı olsun. * – T ise karar ağacının budanmışlığını simgelesin. Ek olarak ,TF* “B” düğümünün en sık gözlenen alt ağacını ve “L” ise “S” kümesinin en sık gözlenenleri ile sınıflanmış bir yaprağını ifade etsin. Sırasıyla ET,ETF  VE EL ise “S” sınıfı içinde, T,TF* ve L tarafından sınıflandırılmamış durumların sayılarını göstersin. Bunlara göre üç çeşit hata oranı

tahminlenebilir (Kohavi ve Quinlan, 1999:8). Bunlar;

Burada “ CF U ” ile istatistiksel tablolar kullanılarak hesaplanan binomial dağılımı göstermektedir. ”CF” ise güven düzeyini gösterir. C4.5 algoritması genelde % 25‘ lik güven düzeyini kullanır (Kantardzic, 2011:184 ). Bu hata oranlarına göre alt ağaç, kök düğüm haline getirilerek budama işlemi tamamlanmış olur.

CART Algoritması

CART, sınıflama ve regresyon ağaçları 1984 yılında Breiman tarafından ortaya atılmıştır .Bu algoritma C4.5 algoritması ile aynı temelde karar ağacı kurarak karar üretir. CART algoritması da C4.5 gibi en uygun değeri seçme prosedürünü kullanır. C4.5 ‘in tersine CART algoritması, sadece ikili ağaç yapımına olanak sağlar (Berry ve Browne, 2006:85). ikili ağaç, her düğümün iki dala ayrıldığı ağaç çeşididir. Bölünme işlemi, twoing ve gini algoritmalarıyla yapılır. CART algoritmasının en önemli özelliği, regresyon ağacı oluşturmasıdır. Regresyon ağacında, ağacın yaprakları bir sınıfı tahminlemez, gerçek sayıları tahminler. CART algoritmasında her düğüm, mümkün bütün bölünmelerle karşılaştırılır ve homojenlik derecesi en yüksek olan özellik seçilir. Budama işleminde, C4.5 algoritması binomial güven sınırlarını kullanırken CART, en az maliyetli karmaşıklık budama yöntemini kullanır. Bu yaklaşım, tekrar yerine koyma hatası (re-substitution error) yanlılığının, karar ağacı yaprak sayısını doğrusal olarak arttırdığını varsayar. Bir alt ağaca yüklenen maliyet iki terimden oluşur; yerine koyma hatası (re-substitution error) ve karmaşıklığın ölçüsünü gösteren parametresinin yapraklardaki sayısı.CART algoritmasında iki tip bölünme algoritması vardır; Twoing ve gini. Bölünme için twoing algoritması seçilirse algoritma şu şekilde çalışır.

CEVAP VER

Time limit is exhausted. Please reload CAPTCHA.