Karar ağaçları, istatistiksel sınıflandırma ve tahmin etme yöntemi olarak çok sık kullanılan bir metodolojidir. Yapay sinir ağları, kümeleme gibi pek çok sınıflandırma yaklaşımı olmasına rağmen karar ağaçlarının tercih edilme nedeni, kolay yorumlanabilmesi ve daha anlaşılabilir olmasıdır. Özellikle büyük veri kümelerinin uygulama alanını ifade eden veri madenciliği alanında gitgide daha fazla karşımıza çıkar. Karar ağacını anlatmadan önce istatistiksel sınıflandırmanın ne olduğunu anlatmam gerekmektedir.
İstatistiksel Sınıflandırma Nedir?
Sınıflandırma, önemli veri sınıflarını tanımlayan modelleri açığa çıkaran bir veri analizi biçimidir. Sınıflandırıcılar olarak adlandırılan bu tür modeller, kategorik (ayrık, sırasız) sınıf etiketlerini tahmin eder. Veri sınıflandırması, bir öğrenme adımından (bir sınıflandırma modelinin oluşturulduğu) ve bir sınıflandırma adımından (modelin, verilerin sınıf etiketlerini tahmin etmek için kullanıldığı) oluşan iki aşamalı bir süreçtir.
Örneğin; bir banka kredi yetkilisi kredi başvurusunda bulunan insanların, başvuru öncesinde “riskli” grupta olup olmadığını öğrenmek isteyebilir. Ya da herhangi bir kanser türü üzerine çalışan bir tıp araştırmacısı, bir hastanın alması gereken üç özellikli tedaviden hangisinin daha başarılı olduğunu tahmin etmek için verilerini analiz etmek isteyebilir. Görüldüğü gibi sınıflandırma metotları, bankacılıktan tıp bilimine kadar verinin bilgiye dönüştürülmesinin istendiği pek çok yerde kullanım alanına sahiptir.
Bir sınıflandırma algoritmasının kullanımı, veritabanıyla ilişkili sınıf etiketlerinden oluşan bir eğitim setini analiz etmesi veya “öğrenmesidir”. Bu, sınıflandırıcıyı oluşturan öğrenme adımı veya eğitim aşamasıdır. Sınıflandırıcının öğrenmesi ya da eğitilmesi aşamasında her eğitim grubunun hangi sınıfa ait olduğu söylenerek “denetlenmesinden dolayı” sınıflandırma aynı zamanda denetimli öğrenme olarak da bilinir. Burada önemli bir nokta daha vardır. İstatistiksel sınıflandırmanın kümeleme analizinden farkı, sınıf etiketlerinin ve gruplandırılacak küme sayısının önceden bilinmesidir.
Sınıflandırma Mantığı Nasıl Çalışır?
Az önce de söylemiş olduğum banka kredi yetkilisi ve tıp araştırmacısı örneklerine geri dönelim. Banka örneğindeki veri analizinin amacı, kredi başvurusu verilerinden “güvenli” veya “riskli” gibi sınıf (kategorik) etiketlerini tahmin etmektir. Tıbbi veriler içinse amaç, “tedavi A”, “tedavi B” ve “tedavi C”’den hangisinin daha başarılı bir yöntem olduğunu keşfetmektir. Bu kategoriler, nitelikler arasındaki sıralamanın hiçbir anlam ifade etmediği sayısal değerlerle temsil edilebilir. Örneğin, “1” değeri güvenli kişiyi, “2” değeri riskli kişiyi ifade etmek için kullanılabilir. “1, 2 ve 3” değerleri, bu tedavi rejimleri grubu arasında ima edilen herhangi bir sıralamanın olmadığı durumlarda, A, B ve C tedavilerini temsil etmek için kullanılabilir.
Modelin inşa edildiği tahmin, bir sınıf etiketinin aksine sürekli değerli bir işlevi veya sıralı bir değeri öngörebilir. Bu model, sınıflandırmayı içeren bir tahmin modelidir. Regresyon analizi, çoğunlukla sayısal tahmin için kullanılan istatistiksel bir metodolojidir; bu nedenle iki terim eşanlamlı olarak kullanılma eğilimindedir; ancak sayısal tahmin için başka yöntemler de mevcuttur. Sınıflandırma ve sayısal tahmin, iki ana tahmin problemi türüdür. Bu yazı bir sınıflandırma türü olan karar ağacına odaklanmaktadır.
İki Aşamalı Sınıflandırma Prosedürü
Sınıflandırmanın ilk aşamasında, önceden belirlenmiş veri sınıfları veya kavramlar kümesini açıklayan bir sınıflandırıcı oluşturulur. Bu, bir sınıflandırma algoritmasının veritabanı demetlerinden ve bunlarla ilişkili sınıf etiketlerinden oluşan bir eğitim setini analiz ederek veya “öğrenerek” sınıflandırıcıyı oluşturduğu öğrenme adımıdır (veya eğitim aşamasıdır). Eğitim setini oluşturan bireysel gruplar, eğitim grupları olarak adlandırılır ve analiz edilen veritabanından rastgele örneklenir. Sınıflandırma bağlamında veri grupları; örnekler, veri noktaları veya nesneler olarak adlandırılabilir. Sınıflandırma sürecinin bu ilk adımı, belirli bir X dizisinin ilişkili sınıf etiketi y’yi tahmin edebilen işlevin öğrenilmesi olarak da görülebilir. Bu görünümde, y = f(x) işlevini ayıran veri sınıflarını öğrenmek istiyoruz. Tipik olarak bu eşleme; sınıflandırma kuralları, karar ağaçları veya matematiksel formüller şeklinde temsil edilir.
Sınıflandırma doğruluğunu anlatan ikinci adımda, model sınıflandırma için kullanılmaktadır. Öncelikle, sınıflandırıcının tahmin doğruluğu elde edilir. Sınıflandırıcının doğruluğunu ölçmek için kendi eğitim setinin dışında, test grupları ve bunlarla ilişkili sınıf etiketlerinden oluşan bir test seti kullanılır. Bu test seti, eğitim dizilerinden bağımsızdır. Yani sınıflandırıcıyı oluşturmak için kullanılmadıkları anlamına gelir. Belirli bir test setindeki bir sınıflandırıcının doğruluğu, sınıflandırıcı tarafından doğru şekilde sınıflandırılan test seti demetlerinin yüzdesidir. Her bir test demetinin ilişkili sınıf etiketi, öğrenilen sınıflandırıcının o demet için sınıf tahminiyle karşılaştırılır.
Karar Ağaçları Yapısı
Karar ağacı sınıflandırıcıları neden bu kadar popülerdir?
- Herhangi bir alan bilgisi veya parametre ayarı gerektirmez ve bu nedenle keşifsel bilgi için uygundur.
- Çok boyutlu verileri işleyebilir. Edinilen bilginin ağaç formundaki temsilleri sezgiseldir ve genellikle insanlar tarafından özümsenmesi kolaydır.
- Öğrenme ve sınıflandırma adımları basit ve hızlıdır. Genel olarak, karar ağacı sınıflandırıcılarının doğruluğu iyidir. Bununla birlikte başarılı kullanım, eldeki verilere bağlı olabilir –ki istatistik bilimi verinin doğru edinilmesinden geçer.
- Karar ağacı indüksiyon algoritmaları tıp, imalat ve üretim, finansal analiz, astronomi ve moleküler biyoloji gibi birçok uygulama alanında sınıflandırma için kullanılmıştır. Bunun yanında birçok ticari kural indüksiyon sisteminin temelini de oluşturur.
Bir Karar Ağacı Algoritması Nasıl Çalışır?
Algoritma, 3 parametre ile çağrılır: Veri bölümü, Öznitelik listesi ve Öznitelik seçim yöntemidir. Veri bölümü, eğitim demetleriyle bunlarla ilişkili sınıf etiketlerinin tam setidir. Öznitelik listesi, demetleri tanımlamaya yarayan özniteliklerin bütünüdür. Öznitelik seçim yöntemi ise verilen diziyi sınıfa göre “en iyi” ayırt eden özniteliği seçmek için sezgisel bir prosedür belirtir. Ağacın tam anlamıyla ikili olup olmadığı genellikle öznitelik seçim ölçüsü tarafından belirlenir.
- Ağaç, veri bölümündeki eğitim demetlerini temsil eden tek bir düğüm olarak başlar. Dallar oluşurken eğer seçilen demetlerin tümü aynı sınıftaysa düğüm bir yaprak olur ve bu sınıfla etiketlenir. Aksi takdirde, algoritma bölme kriterini belirlemek için öznitelik seçim yöntemini çağırır. Bölme kriteri, veri bölümündeki demetleri ayrı sınıflara ayırmanın veya bölümlemenin “en iyi” yolunu belirleyerek kök düğümünde hangi özniteliğin test edileceğini bize söyler. Bölme kriteri ayrıca, seçilen testin sonuçlarına göre kök düğümünden hangi dalların büyüyeceğini de gösterir.
- Kök düğüm, düğümde bir test görevi gören bölme kriteri ile etiketlenir. Bölme kriterinin sonuçlarının her biri için kök düğümünden bir dal büyütülür. Veri bölümündeki demetler buna göre bölümlenir. Diyelim ki A, bölme niteliği olsun. A’nın, eğitim verilerine dayalı olarak olası 3 farklı sonucu vardır:
- A, ayrık değerli olabilir. A’nın bilinen her değeri için bir dal oluşturulur ve bu değerle etiketlenir. Belirli bir bölümdeki tüm demetler A için aynı değere sahip olduğundan, A demetlerinin gelecekteki bölümlemelerde dikkate alınması gerekmez. Bu nedenle, öznitelik listesinden kaldırılır.
- A, sürekli değerli olabilir. Bu durumda kök düğümündeki testin, sırasıyla A <= bölme noktası ve A > bölme noktası koşullarına karşılık gelen iki olası sonucu vardır ve burada bölme noktası, bölme kriteridir. Uygulamada, bölünme noktası a, genellikle A’nın bilinen iki bitişik değerinin orta noktası olarak alınır. Bu nedenle aslında eğitim verilerinde yer alan ve A’nın önceden bilinen bir değeri olmayabilir. Sonuç olarak kök düğümden iki dal büyütülür ve buna göre etiketlenir.
- A, ayrık değerlidir ve bir ikili ağaç üretilmelidir. Kök düğümündeki test, bölme kriterinin bir parçası olarak öznitelik seçim yöntemi tarafından döndürülür. Bu, A’nın bilinen değerlerinin bir alt kümesidir ve kök düğümden iki dal büyütülür.
- Algoritma veri bölümünün her sonuçtaki bölümünde, demetler için bir karar ağacı oluşturmak üzere özyinelemeli olarak aynı işlemi kullanır. Yinelemeli bölümleme, yalnızca aşağıdaki sonlandırma koşullarından herhangi biri doğru olduğunda durur:
- Veri bölümündeki (kök düğümünde temsil edilen) tüm kayıtlar aynı sınıfa aittir.
- Üzerinde demetlerin daha fazla bölümlenebileceği ve kalan hiçbir öznitelik yoktur. Bu durumda, çoğunluk oyu kullanılır. Bu, düğümünün bir yaprağa dönüştürülmesi için veri bölümündeki en yaygın sınıfla etiketlenmesini içerir.
- Belirli bir dal için demet yoktur, yani veri bölümünün bir kısmı boştur. Bu durumda, veri bölümündeki çoğunluk sınıfıyla bir yaprak oluşturulur. Aşağıda yer alan örnek, konuyu daha anlaşılır hale getirecektir.
Bir Karar Ağacı Örneği
Örneğimizde, bir topluluk için bilgisayar satın alma olasılığının olup olmadığını gösteren bir karar ağacı görülmektedir. Eğitim seti parametreleri; bilgisayar satın alıp almama durumu, yaş grubu, öğrenci olup olmama ve kredi derecesi grupları olarak ele alınmıştır. Her yaprak olmayan düğüm bir öznitelik üzerindeki testi temsil ederken, her yaprak olan düğüm de bir sınıfı temsil etmekte.
Yaş grubu ayrık değerli olarak ele alındığından her bir değeri için bir dal büyütülmüştür. Yani yaş grubu, 30’dan küçük, 31 – 40 yaş arası ve 40’dan büyük olmak üzere ayrılmıştır. Aynı şekilde öğrenci olup olmama ve kredi oranının da her bir değeri için ayrı bir dal büyütülmüştür. Tabloya göre; 30 yaşında küçük ve öğrenci olanların 2 tanesi bilgisayar satın almışken, 3 tanesi satın almamıştır. 31 – 40 yaş arasındaki 4 kişi bilgisayar satın almıştır. 40 yaşından büyük olanlarsa kredi oranına göre büyütülen dalda etiketlenmiştir. Excellent grubunda olanlar bilgisayar satın almamışken, Fair grubunda 3 kişi bilgisayar satın almıştır. Dolayısıyla 31 – 40 yaş grubunda olanlar için ağaç yapısında evet cevabında dallanma durmuş ve diğer yaş gruplarında evet/hayır ya da başarılı/başarısız gruplarındaki değere göre dallanma devam etmiştir. Böylece gruplar bazında bilgisayar satın alıp almama durumuna göre karar ağacı oluşturulmuştur.
Karar Ağacı Öznitelik Seçim Ölçüleri
Peki, yukarıdaki gibi örneği görülen karar ağaçları hangi seçim yöntemine göre çalışır? Bu prosedür en yaygın olarak; bilgi kazancı, kazanç oranı veya Gini indeksi gibi bir öznitelik seçim ölçüsü kullanır. Gini indeksi gibi bazı öznitelik seçim ölçüleri, elde edilen ağacı ikili olmaya zorlar. Bilgi kazancı gibi diğerleri ise çok yollu bölünmelere (yani, bir düğümden iki veya daha fazla dalın büyütülmesine) izin vermezler. Kısaca bu ölçüleri tanıyalım:
Bilgi Kazancı
Bilgi kazancı entropinin tersi olan bir kavramdır. Entropi, bilgi kuramında bir örneğin sınıfını göstermek için kullanılan en az bit sayısı olarak tanımlanır. Yani rasgele değişkenle ilgili belirsizlik ölçüsüdür. Tüm olası bölünmeler için bölünmeden sonraki saflık durumunun ne olacağını ölçer. En yüksek entropiye sahip olan nitelik en yüksek kararsızlığa sahip olacaktır, aksi de geçerlidir.
Dolayısıyla bilgi kazancı, 0 ile 1 arası değerler alan ve entropinin tersinin işlediği bir ölçüm türüdür. Şöyle ki, istenen bir özellik için verilen sınıflandırma sonuçlarının ne kadar değer kazanacağının ölçüsünü verir. Örneğin 5 farklı sınıf için istenen özellik 5 farklı değer alıyorsa, entropisi 0 bilgi kazancı 1 olacaktır. Fakat aynı özellik sınıflardan ne kadar bağımsızsa o kadar düşük bilgi kazancına sahip olur. Görüldüğü gibi sahip olunan bilgi ile sınıf arasında birebir ilişki kurulabilmektedir. Bir ağaç yapısında en yüksek bilgi kazancına sahip öznitelik, düğüm için bölme özniteliği olarak seçilir.
Kazanç Oranı
Entropiye dayalı olan bu ölçüt, bilgi kazanımından faydalanılarak hesaplanır. Fakat bilgi kazanımından daha iyi sonuçlar verir. Bilgi kazancı ölçüsü, birçok sonucu olan testlere yöneliktir. Yani, çok sayıda değere sahip öznitelikleri seçmeyi tercih eder. Kazanç oranı ise bu önyargıyı ortadan kaldırmayı amaçlar.
Gini İndeksi
Bu ölçüt, karar ağacının her bir karar düğümünden itibaren ağacın iki dala ayrılması ilkesine dayanır. İlk hangi nitelikten bölüneceği ve bölünme değeri Gini indeks değerine bakılarak hesaplanır. Her bir öznitelik için, olası ikili bölünmelerin her biri dikkate alınır. Strateji, her bir (sıralı) bitişik değer çifti arasındaki orta noktanın olası bir bölünme noktası olarak alındığı, bilgi kazanımı için daha önce açıklanan stratejiye benzer. Ayrık değerli bir öznitelikte, bu öznitelik için minimum Gini indeksini veren alt küme, bölme alt kümesi olarak seçilir. Sürekli değerli öznitelikler için, her olası bölme noktası dikkate alınmalıdır. İki niteliğin Gini değeri aynı çıkarsa sonuç dağılımları aynı demektir. Eğer veri kümesindeki bir nitelikte 3 veya daha fazla seçenek bulunuyorsa kural gereği ikiden fazla bölünmeye izin verilmediğinden birbirine yakın seçenekler gruplandırılır.
Özetleyecek olursam, istatistiksel sınıflandırmanın önemli bir yöntemi olan karar ağaçları, anlaşılması ve uygulanması kolay bir metodolojidir. Karar ağaçları, aslında veri madenciliğinin bir alanı olup çok geniş kapsamlıdır. Üzerine çok fazla araştırma yapılmakta ve incelenmektedir. Her istatistiksel yöntemin uygulanmasında olduğu gibi karar ağaçlarının uygulama alanında da bazı dezavantajlar bulunmakta ve bu dezavantajlar iyi bir alan bilgisiyle çözümlenebilmektedir. İstatistik olmazsa olmaz, güzel bir bilim dalımızdır; yeter ki yanlış zihinlerin eline düşmesin! Bir sonraki yazımda karar ağaçları algoritmalarının en sık kullanılanları hakkında bilgi vereceğim.
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.
