Makine Öğrenmesi Algoritmaları - ID3 Algoritması
Ağaçlar Karar Verebilir Mi ?
Elbette! Fakat yalnızca bir türü, karar ağaçları.
Karar ağaçları, basit if-then kuralları olarak ifade ettiğimiz örneğin; “Sayı 0'dan küçük ise negatiftir” şeklindeki kurallardan oluşur. Bir sayının Pozitif, Negatif ya da Nötr olduğunu kontrol eden karar ağacı aşağıda görülmektedir.
Karar ağaçları için kullanılan terminolojiye göz atmak gerekirse; ağaç üzerindeki koşul ifadeleri ‘düğüm’ olarak adlandırılırken ilk düğüm ‘kök düğüm’ olarak ifade edilir. Düğümler arası bağlantı ‘kenar’ olarak adlandırılır. ‘Yaprak’ olarak isimlendirilen koşul belirtmeyen ifadeler ise sınıf etiketlerini gösterir.
Ağaç üzerindeki ilerleme; düğümdeki karar durumuna bağlı olarak ilgili kenar aracılığı ile ulaşılacak düğüm ya da yaprağa ilerleyerek gerçekleştirilir.
Örneğin; örnek karar ağacında, sayının 0'a eşit olmadığı durumda, 0'dan küçük olma durumu kontrol edilir.
Şimdi bir karar ağacı algoritması olan ID3 algoritmasının teknik kısmına geçelim ve veri kümesindeki bilgilerden ilgili formülleri kullanarak nasıl karar ağacı oluşturulduğunu, öğrenme işleminin nasıl gerçekleştiğini görmeye çalışalım!
Veri Kümesi
Öncelikle bu yazıda kullanacağımız örnek veri kümesine bir göz atalım.
Karar ağacı algoritmaları için sıklıkla kullanılan bu veri kümesi; hava, para ve aile durumuna bağlı olarak hafta sonunda yapılacak aktivitenin ne olacağına karar vermeye yönelik bilgileri içerir.
Şimdi bu veri kümesini kullanarak algoritmamızı uygulamaya başlayalım!
ID3
ID3, makine öğrenmesi alanında çalışmaya yeni başlayan kişilerin rahatlıkla kavrayabilecekleri ve karar ağaçlarının temel çalışma şeklini öğrenebilecekleri ideal algoritmalardan biridir.
ID3 algoritması, entropi’den faydalanarak sınıflandırma problemlerinin çözülmesine imkan tanır. Bu sebeple algoritmanın nasıl çalıştığına geçmeden önce “entropi” kavramından bahsetmeliyiz.
Entropiyi tek bir kelime ile ifade edecek olursak, tanım için kullanılacak en uygun sözcük ‘düzensizlik’ olacaktır.
Daha açıklayıcı olmak gerekirse;
Yukarıda görselden görüldüğü üzere entropinin düşük olduğu kümede tüm sınıf etiketleri aynı iken, entropinin yüksek olduğu küme 2 farklı sınıf etiketinden oluşmakta dolayısıyla düzensizlik daha fazla olmaktadır.
Shannon’un entropi formülünü incelersek;
m : Entropisi hesaplanacak durum sayısı
Pi : i durumunun olasılığı
olmak üzere formül aşağıda görülmektedir.
Örnek veri kümemize entropi formülünü uygulayalım ve karar ağacımızı oluşturmaya başlayalım!
Veri kümemizde bulunan 10 örneğimiz için öncelikle her sınıf etiketine (hafta sonu yapılacak farklı aktivite durumları) ait kaç örneğe sahip olduğumuzu tablolayalım.
Şimdi artık Shannon’un formülü ile entropi hesabı yapabiliriz!
Haftasonu yapılacak aktivitelerimiz diğer bir deyişle sınıf etiketlerimiz ‘Sinema, Tenis, Alışveriş, Ev’ olmak üzere 4 adettir. Bu durumda m değerimizin 4 olduğunu söyleyebiliriz.
Bir sınıf etiketinin gerçekleşme olasılığı (Pi) “ilgili etikete sahip örnek sayısı / veri kümesindeki toplam örnek sayısı” ile hesaplanır. Buna göre Pi olasılıklarının aşağıdaki gibi olduğunu söyleyebiliriz:
Olasılık hesabının tamamlanmasının ardından entropi formülü yardımı ile veri kümesinin entropi değerini hesaplayalım :
Böylelikle veri kümesinin entropi değerinin 1,571 olduğunu elde ettik.
ID3 algoritmasında sistemin genel entropisinin hesaplanmasının ardından her bir özniteliğin entropisi de ayrı ayrı hesaplanır. Hesaplanan entropi değerleri, genel entropiden çıkartılarak; hangi özniteliğin entropi değerini en çok azalttığı tespit edilir.
Entropideki azalış ‘kazanç’ olarak ifade edilir. Başka bir deyişle; entropiyi en çok düşüren öznitelik, en çok kazanç sağlayan öznitelik olarak karşımıza çıkar!
Kazanç formülünü matematiksel olarak ifade etmek gerekirse :
Şeklinde ifade edilebilir. Karışık gözüken kazanç formülünü kolayca yorumlayabilmek mümkündür.
Gain(S,A); A niteliğinin S sistemine göre kazancı anlamına gelir. Bu değer sistemin entropisinden, özniteliğin entropi değerinin çıkarılmasıyla elde edilir.
Formülle ifade ettiğimiz kazanç hesabını bir kez de veri kümemiz üzerinde uygulayarak sonuçları değerlendirelim!
Öncelikle “Hava Durumu” özniteliğini ele alırsak; farklı hava durumu koşullarına bağlı olarak (Güneşli, Rüzgarlı, Yağmurlu) farklı sınıf etiketlerine sahip örnek sayısını belirlememiz gerekecektir.
Hava koşullarına bağlı olarak, farklı sınıf etiketlerine ait toplam örnek sayılarını içeren tabloyu aşağıdaki gibi özetleyebilmek mümkündür.
Bir niteliğin entropisi hesaplanırken kenarlarının entropisinin ağırlıklı ortalaması alınır.
Tablodaki değerleri kullanarak “Hava Durumu” özniteliğinin ağırlıklı entropisini hesaplayalım.
Öncelikle kenarların entropisinin hesaplanmasıyla başlayalım.
Kolayca hesaplanan kenar entropileri değerlerinden sonra, ikinci olarak yapılması gereken kazanç değerlerinin hesaplanması işlemidir.
Böylelikle “Hava Durumu” özniteliğine ait kazanç değeri hesaplanmış oldu. Bu işlem diğer tüm öznitelikler için tekrarlanır ve kazanç değeri en büyük olan öznitelik kök düğüm olarak seçilir.
Diğer özniteliklerin kazanç değerleri özetle aşağıdaki gibi listelenebilir.
Elde edilen kazanç değerlerinden görüleceği üzere, “Hava Durumu” düğümü, en çok kazanç sağlayan düğüm olarak “kök düğüm” olmaya hak kazanmıştır!
3 ayrı “Hava Durumu” koşuluna göre ilk adımda karar ağacımızın görüntüsü aşağıdaki gibidir:
Bu durumda kök düğümün her bir kenarı için hangi örneklerin geçerli olduğu belirlenir. Her kenar için sistemi ifade edecek veri kümesi bu belirlenen örneklerden oluşur. Bundan sonraki aşamalarda bu veri kümelerinin her biri ayrı bir sistem olarak ele alınır.
Algoritmaya geri dönecek olursak bir sonraki aşamada tüm kenarlar için bir sonraki düğüm hesaplanır. Biz burada bir kenar için gerekli hesabı yapalım ve diğer kenarları size bırakalım.
Örnek olarak veri kümesindeki “Hava Durumu” özniteliğinin “Güneşli” kenarını hesaplayacak olursak;
Veri kümesindeki ilgili örnekler alınır ve entropi hesabı bu veri kümesi üzerinden yapılır. Aşağıda bu örnekler gösterilmektedir.
Tabloda ifade edilen ve yalnızca hava durumunun güneşli olduğu durumlara ait olan küçük veri kümesi üzerinde tekrar daha önce yaptığımız hesaplamaları gerçekleştirerek, bir sonraki karar düğümünü belirlemeye çalışacağız.
Bu amaçla, öncelikle “Güneşli” durumu için yeni bir sistem entropisi hesaplanmalıdır. Bu işlem için, bildiğiniz üzere farklı sınıf etiketlerine ait örneklerin sayılması gerekmektedir.
Tabloda sınıf etiketleri ve ilgili sınıf etiketine ait örnek sayıları görülmektedir. Tabloya bağlı olarak havanın güneşli olması durumunda haftasonu sinema aktivitesi gerçekleştiren 1, tenis aktivitesi gerçekleştiren 2 örnek bulunduğunu ifade edebiliriz.
O halde tabloya göre sistem entropisini hesaplarsak :
Entropinin 0,918 olduğu görülür. Şimdi de hangi özniteliğin entropiyi en çok düşüreceğini bulmak adına her bir özniteliğin kazançlarını hesaplayalım. “Para” özniteliğinin kazancını hesaplayarak başlayabiliriz.
Bu aşamada “Para” özniteliğine ait farklı etiketlerin entropisini ve ardından bu özniteliğin kazancını hesaplayalım.
Bu durumda ‘Zengin’ ve ‘Fakir’ kenarlarına ait entropi değerleri aşağıdaki gibidir.
Hesaplanan entropi değerlerinden yola çıkarak kazanç hesabı yapılırsa;
Kazancın ‘0’ olduğu görülür. Bu sonuç bize; “Para” özniteliğinin herhangi bir kazanç sağlamadığını, başka bir deyişle “Para” özniteliğinin şu aşamada düğüm olarak yer alamayacağını, diğer özniteliklerin kontrol edilmesi gerektiğini ifade etmektedir.
Diğer bir öznitelik olan “Aile” yi ele alacak olursak; “Aile” özniteliğinde “Evet” etiketine sahip tek bir örnek bulunduğunu ve bu örneğinde haftasonu aktivitesi olarak “Sinema” tercihinde bulunduğunu görebiliriz. Benzer şekilde “Hayır” etiketine sahip 2 örneğinde haftasonunda “Tenis Oynamak” eylemini gerçekleştirdiğini görebiliriz.
Bu durum bize entropinin “0” olacağını ifade etmektedir. Dolayısıyla kazanç hesabı yapılırsa:
“Aile” özniteliğinin “Para özniteliğinden daha kazançlı olduğu görülür. Bu durumda Aile özniteliği düğüm olarak belirlenir.
Bu bilgileri göz önünde bulundurarak karar ağacımızı tekrar oluşturursak aşağıdaki gibi gözükecektir.
Tüm kenarların yukarıda yapılan işlemlerin yapılması ve yaprağa ulaştırılması ile karar ağacı tamamlanacaktır. “Yaprağa ulaşmak” tüm kayıtların aynı etikete sahip olması ile, yani entropinin “0” olması ile gerçekleşecektir.
Tahmin
Tüm bu adımların sonucunda oluşan nihai karar ağacı, model olarak adlandırılır. Elde edilen model kullanılarak, gelen yeni kayıtların tahmini yapılabilir.
Şimdi birlikte bir örneğin tahminini yapalım ve yazıyı sonlandıralım.
Örnek kayıt:
Oluşan modelimizin kök düğümü “Hava Durumu” olarak belirlenmişti.
İlk olarak kök düğüm olan “hava durumu” özniteliğini kontrol ediyoruz. Test verisinde “Hava durumu” özniteliği “Güneşli” değerine sahip olduğundan model bize “Aile” özniteliğini kontrol etmemiz gerektiğini söylüyor. Test verisinde “Aile” özniteliğinin değeri “Evet” olduğundan model bizi bir sonraki aşamada yaprak düğüm olan Sinema düğümüne ulaştırıyor.
Yaprak düğüme ulaşınca ilerleme sonlanır. Ulaşılan değer tahmin sonucudur.
Bu kayıt için tahminimiz “Sinema” olmalıdır.
Siz de karar ağacının geri kalanını hesaplayarak modeli tamamlayabilir, kendi test verilerinizi belirleyerek tahminler yapabilirsiniz.
Soru ve görüşleriniz için benimle twitter ve linkedin üzerinden iletişime geçebilirsiniz.
Herkese iyi çalışmalar…
Kaynaklar
1-https://en.wikipedia.org/wiki/Entropy_(information_theory)
2-http://dataaspirant.com/2017/01/30/how-decision-tree-algorithm-works/
4-http://www.doc.ic.ac.uk/~sgc/teaching/pre2012/v231/lecture11.html
