- 31 Ara 2018
- 79
- 3
Giriş
Merhaba, bugün Karar ağaçlarının ne olduğunu ve neden kullanıldığını inceleyerek, Karar ağaçlarını kullanan ve Sınıflandırma (classification) algoritmalarından olan ID3 Algoritmasının çalışma yapısını anlatarak, örnekler üzerinden ilerleyeceğiz.
Hangi Aşamadayız?
Konumuza geçmeden önce, şimdiye kadar ki ilerlemelerimizi gözden geçirerek durum değerlendirmesi yapalım. Şimdiye kadar; Temel Kavramlar, Makine Öğrenmesi, Veri Hazırlama gibi temel konularda, YAPAY ZEKA konusunun temellerine giriş yaparak, bu kavramın içerdiği bazı alt konulara değinip, bu alanda çalışmak isteyenlere ışık tutabilecek bazı temellere değinmiştik. Daha sonrasında YAPAY ZEKA konusu ile ilgili temellerimizi sağlamlaştırdıktan sonra, (ki burada belli başlı konulara değinilerek, temel yapı taşlarının sunulduğunu ve temelinizi sağlamlaştırmanın öncelikle Sizin çalışmanıza bağlı olduğunu unutmayın) KNN Algoritması ve Python ile KNN Algoritmasının kodlanması aşamasıyla da artık pratiğe geçmiştik.
(Bu konulara gitmek için konu isimlerine tıklayabilirsiniz.)
Bundan sonraki aşamalarda da çeşitli Makine Öğrenmesi Algoritmalarını görerek, bu algoritmaların pratikte nasıl kodlandığını ve güncel hayatta ne tür problemlerin çözümünde rol alabileceğini inceleyerek ilerleyeceğiz.
Gerekli açıklamaları yaptıktan sonra, artık konumuza geçebiliriz.
Karar Ağaçları
Karar ağaçları, isminden de anlaşılabileceği gibi, karar aşamasında bize yardımcı olan yapılardır. Bu yapıda, ağacımız belirli düğümlerden çeşitli dallara ayrılarak, düğümlerin üzerindeki şartlara göre dallanmalar gerçekleştirmektedir. Şu şekil karar ağaçlarını anlamamıza yardımcı olacaktır;
Şekilde gördüğünüz gibi, düğümlerimiz çeşitli nitelikleri temsil etmektedir. Bu niteliklerin değerlerine konulan şartlarda dallanmalarımızı oluşturmaktadır. Örneğin, Weather niteliğinin temsil ettiği düğüme bakacak olursak, bu niteliğin "Sun", "cloud" ve "Rain" değerlerine göre 3 farklı dallanma meydana gelmektedir.
Karar ağaçlarına bakarak, nasıl bir karar mekanizması geliştireceğimize bir örnek üzerinden bakalım;
Bugün Havanın (Weather) bulutlu (cloud) olduğunu ve çok aç (Hungry) olduğumuzu düşünelim, karar ağacımıza göre o gün ile ilgili bir karar verecek olursak, şu şekilde ilerleriz; Weather (Hava) niteliğimiz, cloud (bulutlu) değerine sahip olduğu için Hungry düğümüne gideriz, bu düğümdeki Hungry niteliğinin de Yes değerine sahip olduğunu düşündüğümüzde (Çok aç olduğumuzu varsaymıştık), Walk (Yürüyebilirsin) sonucuna ulaştığımız görebiliriz.
Aslında karar ağaçları temel de bir if - else yapısından başka bir şey değildir.
Entropi Nedir
Algoritmamıza giriş yapmadan önce değinmemiz gereken kavramlardan biri de Entropi kavramıdır. Entropi, en basit tanımıyla düzensizliktir. Şu şekle bakarak, entropi kavramını netleştirelim:
Şekilden de farkettiğiniz durumda olduğu gibi, bir yapının içerisindeki çeşitlilik ne kadar fazlaysa entropisi o kadar fazladır diyebiliriz. Eğer bir yapının içerisinde çeşitlilik çok az ise, bu yapının entropisi de çeşitliliği fazla olan yapıya göre daha düşük olacaktır.
Bu kapsamda hesaplamalar yapılırken, bir veri seti içerisindeki sınıfların düzensizliğini bulabilmek için, Shannon tarafından belirlenmiş olan entropi formülünden faydalanacağız.
Bu formül şu şekildedir;
Burada p(x) değeri, entropisi hesaplanacak durumun, o yapı içerisindeki gerçekleşme olasılığıdır. Çeşitliliği sağlayan her bir durum için bu formül hesaplanarak, sonuçlar toplanıp entropi değerine ulaşılmış olur.
Temel kavramları anladıktan sonra artık algoritmamıza geçebiliriz.
ID3 Algoritması
ID3 Algoritması, veri setleri içerisindeki düzensizlikten (entropi) faydalanarak, bu veri setlerinden en uygun karar ağacını elde etmeyi amaçlar.
Algoritmamızın çalışma yapısını bir örnek üzerinden inceleyelim:
Her zamanki gibi, eğer Makine Öğrenmesi Algoritmalarıyla çalışmak istiyorsak, öncelikle bize bir veri seti lazım. Bu veri seti aracılığıyla Eğitme işlemini yaparak, karar ağacımızı oluşturacağız. Kullanacağımız veri seti şu şekildedir:
Veri setimiz; Hava, Isı, Nem, Rüzgâr niteliklerinin değerlerine göre, oyun oynanıp oynanmayacağını belirlediğimiz bir veri setidir.
İlk etapta, karar ağacımızı oluşturmak için, ağacımızın kökünü hangi niteliğin oluşturması gerektiğini bulmalıyız. Bu niteliği bulabilmek için öncelikle veri setimizin entropisini hesaplamalıyız. Daha sonra her bir niteliğin entropisini hesaplayarak, uygun entropi değerine sahip niteliği kök düğüm olarak seçerek, dallanmaları başlatacağız.
Öncelikle genel entropi değerimizi hesaplayalım. Bu değeri hesaplamak için shannon'un entropi formülünden faydalanacağız (Entropi değeri "OYUN" niteliği üzerinden hesaplanmalıdır. Çünkü veri setimizde, elimizdeki verilerden ulaşmak istediğimiz nitelik "OYUN" niteliğidir)
Sistemimizin genel entropisini hesapladığımıza göre, artık niteliklerimiz için entropi hesaplarımıza geçebiliriz:
Hava niteliği
Hava niteliğinin entropi değeri hesaplanırken, her bir dal için entropi değerleri hesaplandıktan sonra ağırlıklı ortalama değeri alınır. Şu şekilde;
Şimdi genel olarak hava niteliğinin entropisini bulalım. Bunun için daha öncede bahsettiğimiz gibi, niteliğin her bir dalı için hesaplanan entropi değerlerinin ağırlıklı ortalamasını almalıyız.
Şu şekilde hesaplıyoruz:
Niteliğimizin entropi değerini hesapladıktan sonra, kazanç hesabı dediğimiz bir hesap yapmalıyız. Bu hesabı yapmadan önce, bu değerin neyi ifade ettiğini ve nasıl hesaplandığını açıklayalım.
Kazanç Nedir?
Kazanç, niteliklerimiz arasından hangi niteliğimizin düğüm olarak seçilmesi gerektiğini belirlememizi sağlayan bir değerdir. Bu değer Genel Sistem entropi değerinden, o niteliğin entropi değerinin çıkarılmasıyla ifade edilir.
Bu değer, her bir niteliğin Sistemin düzensizliğini nasıl etkilediğini, sayısal olarak elde etmemizi sağlar. Asıl amaç düzensizliği en az olan değeri seçerek düğüm yapmaktır. Çünkü ilk etapta ayrıştırma işleminin fazla olması, sınıflandırma işlemini kolaylaştıran bir etken olacaktır. Şöyle düşünebilirsiniz;
Elimiz de 10 tane eşya olduğunu düşünelim. Bu eşyaların bazılarının bir özelliklerinin ortak olduğunu varsayalım. Bazılarının da bir özelliklerinin birbirinden çok farklı olduğunu varsayalım. Eğer kısa sürede bu eşyaları ayırt etmek istiyorsak, yapmamız gereken şey aynı özelliğe sahip olan eşyaları ilk etapta ayırmaktır. Her seviyede bu işlemi yaparak, karar ağacımızı kısa süre içerisinde bitirmeyi amaçlarız.
Örneklerde, kazanç hesabının sağladığı avantajları daha iyi görebilirsiniz.
Şimdi kazanç hesabımızı yapalım:
Bir niteliğimiz için anlaşılır olması açısından detaylı bir anlatım yaptık. Şimdi diğer nitelikleri de hızlıca hesaplayalım.
Isı Niteliği
Nem Niteliği
Rüzgâr Niteliği
Her bir niteliğimiz için kazanç hesabımızı yaptık. Bu aşamadan sonra, kazanç hesabına göre kök düğümümüzü belirleyeceğiz.
Gördüğünüz gibi, Hava niteliğimizin kazanç değeri, diğer niteliklerden daha fazla olduğu için bu niteliğimizi kök düğüm olarak seçiyoruz.
Ağacımız oluşmaya başladı :
Bu aşamadan sonra, Hava niteliğimizin her bir dalını kök düğümü belirlenmesi gereken ayrı birer sistem olarak düşünerek, bu dallar için yaprağa (Oyun niteliğinin değerine) ulaşana kadar, en uygun dallanmaları elde edebilmek için düğümlerimizi bulmaya devam edeceğiz.
Hava niteliğimizin Güneşli değeri için dallanma
Öncelikle, Hava Niteliğimizin Güneşli değeri için, yukarıda yaptığımız işlemleri tekrar edeceğiz.
Bu dallanmanın kök düğümünü bulabilmek için, genel entropi hesabımızı yapalım.
Isı Niteliği
Isı niteliğinin her bir dalı için entropi hesabı yapılarak ağırlıklı ortalaması alınıp, kazanç değeri hesaplanıyor.
Nem Niteliği
Rüzgâr Niteliği
Hava niteliğimizin Güneş dallanması için bütün niteliklerin kazanç hesabını yaptık. Bu kazanç hesabını yaptıktan sonra, en yüksek değere sahip niteliği düğüm olarak belirleyelim.
Gördüğünüz gibi, Nem niteliğimizin kazanç değeri, diğer niteliklerden fazla olduğu için bu niteliği Hava niteliğimizin Güneşli dallanması için düğüm olarak belirliyoruz.
Ağacımız şu şekilde olacaktır:
Oyun niteliği için Nem niteliğimizin, yüksek değerlerine sadece evet, düşük değerlerine de sadece hayır değeri geldiği için bu dal için ayrıştırma işlemini tamamladık demektir. Bu noktada dallanma işlemini sonlandırırız.
Hava niteliğimizin Bulutlu değeri için dallanma
Hava niteliğimizin bulutlu değerini içeren verileri alarak, bu dallanmayı ayrı bir sistem olarak düşünüp, bu dallanma için uygun düğümlerimizi, yukarıdaki işlemlerimizi tekrarlayarak buluyoruz.
Dikkat ederseniz, Hava niteliğimizin bulutlu dallanması için Oyun niteliğimizin bütün değerleri Evet'tir. Bu noktada ayrıştırma işlemine gerek kalmaz. Dallanma işlemi yapılmadan, Hava niteliğinin bulutlu özelliğine Evet değeri atanır.
Ağacımız şu şekilde olacaktır:
Hava niteliğimizin Yağmurlu değeri için dallanma
Hava niteliğimizin yağmurlu değerine sahip verileri alarak, bu verileri ayrı bir sistem olarak düşünüp, bu dal için düğümlerimizi aynı şekilde belirlemeye devam ediyoruz.
Hava niteliğimizin yağmurlu değerine sahip verileri bir sistem olarak düşünmüştük. Şimdi bu sistemin entropisini bulalım:
Isı Niteliği
Isı niteliğinin her bir dalı için entropi hesabı yapılarak ağırlıklı ortalaması alınıp, kazanç değeri hesaplanıyor.
Rüzgâr Niteliği
Dikkat ettiyseniz, Rüzgâr niteliğinin her bir değeri (Hafif, Kuvverli) için Oyun niteliğinin değeri ya sadece hayır veya sadece evet oluyor. Bu noktada ayrıştırma işlemi tam olarak yapıldığından dolayı dallanma işlemini sonlandırıyoruz.
Bu noktadan sonra dallanma işlemimiz sonlandı ama önemli bir noktaya değinmek için Rüzgâr niteliğinin her bir dalı için entropi hesabını yaparak, ağırlıklı ortalamalarını alıp, kazanç değerini hesaplayalım.
Şimdi kritik bir noktaya dikkatinizi çekmek istiyorum. Entropi hesabı yapılırken shannon'un entropi formülünü kullandığımızı söylemiştik. Ve bu formülünde temelde entropisi düşük olan niteliklere göre ayrıştırma işlemini yaptığını söylemiştik.
Dikkatlice incelediğimizde kazanç değerinin en fazla olduğu durumun, niteliğin entropisinin en düşük olduğu durum olan 0 değerinde oluştuğunu görebiliriz. Bunu şöyle açıklayabiliriz:
Entropi değerimiz 0 olduğu zaman, kazanç değerimiz maksimum olur. Yukarıdaki örnek için konuşacak olursak, Hava niteliğinin Yağmurlu dallanması için, Rüzgâr niteliğinin kazancı maksimum olmaktadır. Yani düzensizlik 0 olduğu için, diğer nitelikleri kontrol etmeye ihtiyaç duymadan, bu düğümü belirleyici bir düğüm olarak seçmiş oluyoruz. Bunun sebebi Rüzgâr niteliğinde düzensizliğin olmamasından kaynaklı olarak ayrıştırma işleminin tamamlanmış olmasıdır.
Son olarak, ağacımızın son durumu şu şekilde olacaktır:
ÖZET
ID3 Algoritması, Makine Öğrenmesi alanında kullanılan çok önemli bir sınıflandırma (classification) algoritmasıdır. Bu konuda ID3 Algoritmasını kullanarak, basit bir veri seti üzerinde ID3 Algoritmasının çalışma yapısını inceledik. Temel olarak ID3 Algoritması şu şekilde çalışmaktadır;
Sistemdeki entropi (düzensizlik) bulunur.
Bulunan bu düzensizliğe, her bir niteliliğin etkisi araştırılarak, nitelikler için entropi hesabı yapılır. (Nitelikler için entropi hesabı yapılırken, niteliklerin her bir dallanması için entropi hesabı yapılarak, ağırlıklı ortalamaları alınır.)
Nitelikler için genel entropiye göre kazanç hesabı yapılır.
Sistemde kazanç değeri en fazla olan nitelik düğüm olarak seçilir.
Düğüm olarak seçilen niteliğin her bir dalı, ayrı bir sistem olarak düşünülerek yaprağa (ulaşılmak istenen niteliğin değerine) ulaşılıncaya kadar işlemlere devam edilir.
Karar ağacı elde edilir.
ID3 Algoritmasında, öncelikle sistem eğitilerek karar ağacı oluşturulur. Oluşturulan bu karar ağacına göre, gelen yeni veriler hakkında çıkarımlar yapılabilir.
Merhaba, bugün Karar ağaçlarının ne olduğunu ve neden kullanıldığını inceleyerek, Karar ağaçlarını kullanan ve Sınıflandırma (classification) algoritmalarından olan ID3 Algoritmasının çalışma yapısını anlatarak, örnekler üzerinden ilerleyeceğiz.
Hangi Aşamadayız?
Konumuza geçmeden önce, şimdiye kadar ki ilerlemelerimizi gözden geçirerek durum değerlendirmesi yapalım. Şimdiye kadar; Temel Kavramlar, Makine Öğrenmesi, Veri Hazırlama gibi temel konularda, YAPAY ZEKA konusunun temellerine giriş yaparak, bu kavramın içerdiği bazı alt konulara değinip, bu alanda çalışmak isteyenlere ışık tutabilecek bazı temellere değinmiştik. Daha sonrasında YAPAY ZEKA konusu ile ilgili temellerimizi sağlamlaştırdıktan sonra, (ki burada belli başlı konulara değinilerek, temel yapı taşlarının sunulduğunu ve temelinizi sağlamlaştırmanın öncelikle Sizin çalışmanıza bağlı olduğunu unutmayın) KNN Algoritması ve Python ile KNN Algoritmasının kodlanması aşamasıyla da artık pratiğe geçmiştik.
(Bu konulara gitmek için konu isimlerine tıklayabilirsiniz.)
Bundan sonraki aşamalarda da çeşitli Makine Öğrenmesi Algoritmalarını görerek, bu algoritmaların pratikte nasıl kodlandığını ve güncel hayatta ne tür problemlerin çözümünde rol alabileceğini inceleyerek ilerleyeceğiz.
Gerekli açıklamaları yaptıktan sonra, artık konumuza geçebiliriz.
Karar Ağaçları
Karar ağaçları, isminden de anlaşılabileceği gibi, karar aşamasında bize yardımcı olan yapılardır. Bu yapıda, ağacımız belirli düğümlerden çeşitli dallara ayrılarak, düğümlerin üzerindeki şartlara göre dallanmalar gerçekleştirmektedir. Şu şekil karar ağaçlarını anlamamıza yardımcı olacaktır;
Şekilde gördüğünüz gibi, düğümlerimiz çeşitli nitelikleri temsil etmektedir. Bu niteliklerin değerlerine konulan şartlarda dallanmalarımızı oluşturmaktadır. Örneğin, Weather niteliğinin temsil ettiği düğüme bakacak olursak, bu niteliğin "Sun", "cloud" ve "Rain" değerlerine göre 3 farklı dallanma meydana gelmektedir.
Karar ağaçlarına bakarak, nasıl bir karar mekanizması geliştireceğimize bir örnek üzerinden bakalım;
Bugün Havanın (Weather) bulutlu (cloud) olduğunu ve çok aç (Hungry) olduğumuzu düşünelim, karar ağacımıza göre o gün ile ilgili bir karar verecek olursak, şu şekilde ilerleriz; Weather (Hava) niteliğimiz, cloud (bulutlu) değerine sahip olduğu için Hungry düğümüne gideriz, bu düğümdeki Hungry niteliğinin de Yes değerine sahip olduğunu düşündüğümüzde (Çok aç olduğumuzu varsaymıştık), Walk (Yürüyebilirsin) sonucuna ulaştığımız görebiliriz.
Aslında karar ağaçları temel de bir if - else yapısından başka bir şey değildir.
Entropi Nedir
Algoritmamıza giriş yapmadan önce değinmemiz gereken kavramlardan biri de Entropi kavramıdır. Entropi, en basit tanımıyla düzensizliktir. Şu şekle bakarak, entropi kavramını netleştirelim:
Şekilden de farkettiğiniz durumda olduğu gibi, bir yapının içerisindeki çeşitlilik ne kadar fazlaysa entropisi o kadar fazladır diyebiliriz. Eğer bir yapının içerisinde çeşitlilik çok az ise, bu yapının entropisi de çeşitliliği fazla olan yapıya göre daha düşük olacaktır.
Bu kapsamda hesaplamalar yapılırken, bir veri seti içerisindeki sınıfların düzensizliğini bulabilmek için, Shannon tarafından belirlenmiş olan entropi formülünden faydalanacağız.
Bu formül şu şekildedir;
Burada p(x) değeri, entropisi hesaplanacak durumun, o yapı içerisindeki gerçekleşme olasılığıdır. Çeşitliliği sağlayan her bir durum için bu formül hesaplanarak, sonuçlar toplanıp entropi değerine ulaşılmış olur.
Temel kavramları anladıktan sonra artık algoritmamıza geçebiliriz.
ID3 Algoritması
ID3 Algoritması, veri setleri içerisindeki düzensizlikten (entropi) faydalanarak, bu veri setlerinden en uygun karar ağacını elde etmeyi amaçlar.
Algoritmamızın çalışma yapısını bir örnek üzerinden inceleyelim:
Her zamanki gibi, eğer Makine Öğrenmesi Algoritmalarıyla çalışmak istiyorsak, öncelikle bize bir veri seti lazım. Bu veri seti aracılığıyla Eğitme işlemini yaparak, karar ağacımızı oluşturacağız. Kullanacağımız veri seti şu şekildedir:
Veri setimiz; Hava, Isı, Nem, Rüzgâr niteliklerinin değerlerine göre, oyun oynanıp oynanmayacağını belirlediğimiz bir veri setidir.
İlk etapta, karar ağacımızı oluşturmak için, ağacımızın kökünü hangi niteliğin oluşturması gerektiğini bulmalıyız. Bu niteliği bulabilmek için öncelikle veri setimizin entropisini hesaplamalıyız. Daha sonra her bir niteliğin entropisini hesaplayarak, uygun entropi değerine sahip niteliği kök düğüm olarak seçerek, dallanmaları başlatacağız.
Öncelikle genel entropi değerimizi hesaplayalım. Bu değeri hesaplamak için shannon'un entropi formülünden faydalanacağız (Entropi değeri "OYUN" niteliği üzerinden hesaplanmalıdır. Çünkü veri setimizde, elimizdeki verilerden ulaşmak istediğimiz nitelik "OYUN" niteliğidir)
Kod:
Sistemdeki Hayır Sayısı: [COLOR="Red"]5[/COLOR]
Sistemdeki Evet Sayısı: [COLOR="Red"] 9[/COLOR]
Sistem Entropisi = [COLOR="Red"]-((5/14) * log(5/14) + (9/14) * log(9/14))[/COLOR] = [COLOR="Red"]0.940[/COLOR]
(logaritma hesabında, 2 tabanına göre işlem yapılmaktadır.)Sistemimizin genel entropisini hesapladığımıza göre, artık niteliklerimiz için entropi hesaplarımıza geçebiliriz:
Hava niteliği
Hava niteliğinin entropi değeri hesaplanırken, her bir dal için entropi değerleri hesaplandıktan sonra ağırlıklı ortalama değeri alınır. Şu şekilde;
Kod:
[COLOR="Red"]Hava(Güneşli)[/COLOR] => Güneşli durumundaki Evet Sayısı : 2
Güneşli durumundaki Hayır Sayısı : 3
Entropi: [COLOR="Red"]-((2/5) * log(2/5) + (3/5) * log(3/5))[/COLOR] = [COLOR="Red"]0.971[/COLOR]
[COLOR="Red"]Hava(yağmurlu)[/COLOR] => Yağmurlu durumundaki Evet Sayısı : 3
Yağmurlu durumundaki Hayır Sayısı : 2
Entropi: [COLOR="Red"]-((3/5) * log(3/5) + (2/5) * log(2/5))[/COLOR] = [COLOR="Red"]0.971[/COLOR]
[COLOR="Red"]Hava(Bulutlu)[/COLOR] => Bulutlu durumundaki Evet Sayısı : 4
Bulutlu durumundaki Hayır Sayısı : 0
Entropi: [COLOR="Red"]-((4/4) * log(4/4))[/COLOR] = [COLOR="Red"]0[/COLOR]Şimdi genel olarak hava niteliğinin entropisini bulalım. Bunun için daha öncede bahsettiğimiz gibi, niteliğin her bir dalı için hesaplanan entropi değerlerinin ağırlıklı ortalamasını almalıyız.
Şu şekilde hesaplıyoruz:
Kod:
|Hava(güneşli)| = 5
|Hava(yağmurlu)| = 5
|Hava(bulutlu)| = 4
Hava niteliğinin entropisi =>
H(Hava,Oyun) = [COLOR="Red"](5/14)*H(Güneşli) + (4/14)*H(bulutlu) + (5/14)*H(yağmurlu) [/COLOR]
= [COLOR="Red"](5/14)*0.971 + (4/14)*0 + (4/14)*0.971 = 0.694[/COLOR]
Burada havanın 14 durumundan 5 tanesi Güneşli olduğu için [COLOR="Red"](5/14)[/COLOR] olduğuna dikkat edin. Diğer durumlar için de aynı şekildedir.Kazanç Nedir?
Kazanç, niteliklerimiz arasından hangi niteliğimizin düğüm olarak seçilmesi gerektiğini belirlememizi sağlayan bir değerdir. Bu değer Genel Sistem entropi değerinden, o niteliğin entropi değerinin çıkarılmasıyla ifade edilir.
Bu değer, her bir niteliğin Sistemin düzensizliğini nasıl etkilediğini, sayısal olarak elde etmemizi sağlar. Asıl amaç düzensizliği en az olan değeri seçerek düğüm yapmaktır. Çünkü ilk etapta ayrıştırma işleminin fazla olması, sınıflandırma işlemini kolaylaştıran bir etken olacaktır. Şöyle düşünebilirsiniz;
Elimiz de 10 tane eşya olduğunu düşünelim. Bu eşyaların bazılarının bir özelliklerinin ortak olduğunu varsayalım. Bazılarının da bir özelliklerinin birbirinden çok farklı olduğunu varsayalım. Eğer kısa sürede bu eşyaları ayırt etmek istiyorsak, yapmamız gereken şey aynı özelliğe sahip olan eşyaları ilk etapta ayırmaktır. Her seviyede bu işlemi yaparak, karar ağacımızı kısa süre içerisinde bitirmeyi amaçlarız.
Örneklerde, kazanç hesabının sağladığı avantajları daha iyi görebilirsiniz.
Şimdi kazanç hesabımızı yapalım:
Kod:
Kazanç(Nitelik) = [COLOR="Red"]Sistem Entropisi - Niteliğin Entropisi[/COLOR]
Kazanç(Hava) = [COLOR="Red"]0.940 - 0.694 = 0.246[/COLOR]Bir niteliğimiz için anlaşılır olması açısından detaylı bir anlatım yaptık. Şimdi diğer nitelikleri de hızlıca hesaplayalım.
Isı Niteliği
Kod:
|Isı(soğuk)| = 4
|Isı(ılık)| = 6
|Isı(sıcak)| = 4
Isı niteliğinin entropisi =>
H(Isı,Oyun) = [COLOR="Red"](4/14)*H(soğuk) + (6/14)*H(ılık) + (4/14)*H(sıcak) [/COLOR]
= [COLOR="Red"](4/14)*0.971 + (6/14)*0 + (4/14)*0.971 = 0.911[/COLOR]
Kazanç(Isı) = [COLOR="Red"]0.940 - 0.911[/COLOR]
= [COLOR="Red"]0.029[/COLOR]Nem Niteliği
Kod:
|Nem(normal)| = 7
|Nem(yüksek)| = 7
Nem niteliğinin entropisi =>
H(Nem,Oyun) = [COLOR="Red"](7/14)*H(yüksek) + (7/14)*H(normal)[/COLOR]
= [COLOR="Red"](7/14)*0.985 + (7/14)*0.592 = 0.789[/COLOR]
Kazanç(Nem) = [COLOR="Red"]0.940 - 0.789[/COLOR]
= [COLOR="Red"]0.151[/COLOR]Rüzgâr Niteliği
Kod:
|Rüzgâr(hafif)| = 8
|Rüzgâr(kuvvetli)| = 6
Rüzgâr niteliğinin entropisi =>
H(Rüzgâr,Oyun) = [COLOR="Red"](8/14)*H(hafif) + (6/14)*H(kuvvetli)[/COLOR]
= [COLOR="Red"](8/14)*0.811 + (6/14)*1= 0.892[/COLOR]
Kazanç(Rüzgâr) = [COLOR="Red"]0.940 - 0.892[/COLOR]
= [COLOR="Red"]0.048[/COLOR]Her bir niteliğimiz için kazanç hesabımızı yaptık. Bu aşamadan sonra, kazanç hesabına göre kök düğümümüzü belirleyeceğiz.
Kod:
Kazançlar:
[COLOR="Red"]Hava => 0.246[/COLOR]
Isı => 0.029
Nem => 0.151
Rüzgâr => 0.048Gördüğünüz gibi, Hava niteliğimizin kazanç değeri, diğer niteliklerden daha fazla olduğu için bu niteliğimizi kök düğüm olarak seçiyoruz.
Ağacımız oluşmaya başladı :
Bu aşamadan sonra, Hava niteliğimizin her bir dalını kök düğümü belirlenmesi gereken ayrı birer sistem olarak düşünerek, bu dallar için yaprağa (Oyun niteliğinin değerine) ulaşana kadar, en uygun dallanmaları elde edebilmek için düğümlerimizi bulmaya devam edeceğiz.
Hava niteliğimizin Güneşli değeri için dallanma
Öncelikle, Hava Niteliğimizin Güneşli değeri için, yukarıda yaptığımız işlemleri tekrar edeceğiz.
Bu dallanmanın kök düğümünü bulabilmek için, genel entropi hesabımızı yapalım.
Kod:
H(Oyun) = [COLOR="Red"]-((3/5) * log(3/5) + (2/5) * log(2/5))[/COLOR] = [COLOR="Red"]0.970[/COLOR]Isı Niteliği
Isı niteliğinin her bir dalı için entropi hesabı yapılarak ağırlıklı ortalaması alınıp, kazanç değeri hesaplanıyor.
Kod:
|Isı(soğuk)| = 1
|Isı(ılık)| = 2
|Isı(sıcak)| = 2
Isı niteliğinin entropisi =>
H(Isı,Oyun) = [COLOR="Red"](1/5)*H(soğuk) + (2/5)*H(ılık) + (2/5)*H(sıcak) [/COLOR]
= [COLOR="Red"](1/5)*0 + (2/5)*0 + (2/5)*1 = 0.4[/COLOR]
Kazanç(Isı) = [COLOR="Red"]0.970 - 0.4[/COLOR]
= [COLOR="Red"]0.570[/COLOR]Nem Niteliği
Kod:
|Nem(normal)| = 2
|Nem(yüksek)| = 3
Nem niteliğinin entropisi =>
H(Nem,Oyun) = [COLOR="Red"](3/5)*H(yüksek) + (2/5)*H(normal)[/COLOR]
= [COLOR="Red"](3/5)*0 + (2/5)*0 = 0[/COLOR]
Kazanç(Nem) = [COLOR="Red"]0.970 - 0[/COLOR]
= [COLOR="Red"]0.970[/COLOR]Rüzgâr Niteliği
Kod:
|Rüzgâr(hafif)| = 3
|Rüzgâr(kuvvetli)| = 2
Rüzgâr niteliğinin entropisi =>
H(Rüzgâr,Oyun) = [COLOR="Red"](3/5)*H(hafif) + (2/5)*H(kuvvetli)[/COLOR]
= [COLOR="Red"](3/5)*0.918 + (2/5)*1= 0.951[/COLOR]
Kazanç(Rüzgâr) = [COLOR="Red"]0.970 - 0.951[/COLOR]
= [COLOR="Red"]0.048[/COLOR]Hava niteliğimizin Güneş dallanması için bütün niteliklerin kazanç hesabını yaptık. Bu kazanç hesabını yaptıktan sonra, en yüksek değere sahip niteliği düğüm olarak belirleyelim.
Kod:
Kazançlar:
Isı => 0.570
[COLOR="Red"]Nem => 0.970[/COLOR]
Rüzgâr => 0.019Gördüğünüz gibi, Nem niteliğimizin kazanç değeri, diğer niteliklerden fazla olduğu için bu niteliği Hava niteliğimizin Güneşli dallanması için düğüm olarak belirliyoruz.
Ağacımız şu şekilde olacaktır:
Oyun niteliği için Nem niteliğimizin, yüksek değerlerine sadece evet, düşük değerlerine de sadece hayır değeri geldiği için bu dal için ayrıştırma işlemini tamamladık demektir. Bu noktada dallanma işlemini sonlandırırız.
Hava niteliğimizin Bulutlu değeri için dallanma
Hava niteliğimizin bulutlu değerini içeren verileri alarak, bu dallanmayı ayrı bir sistem olarak düşünüp, bu dallanma için uygun düğümlerimizi, yukarıdaki işlemlerimizi tekrarlayarak buluyoruz.
Dikkat ederseniz, Hava niteliğimizin bulutlu dallanması için Oyun niteliğimizin bütün değerleri Evet'tir. Bu noktada ayrıştırma işlemine gerek kalmaz. Dallanma işlemi yapılmadan, Hava niteliğinin bulutlu özelliğine Evet değeri atanır.
Ağacımız şu şekilde olacaktır:
Hava niteliğimizin Yağmurlu değeri için dallanma
Hava niteliğimizin yağmurlu değerine sahip verileri alarak, bu verileri ayrı bir sistem olarak düşünüp, bu dal için düğümlerimizi aynı şekilde belirlemeye devam ediyoruz.
Hava niteliğimizin yağmurlu değerine sahip verileri bir sistem olarak düşünmüştük. Şimdi bu sistemin entropisini bulalım:
Kod:
Sistem Entropisi = [COLOR="Red"]-((3/5) * log(3/5) + (2/5) * log(2/5))[/COLOR] = [COLOR="Red"]0.970[/COLOR]Isı Niteliği
Isı niteliğinin her bir dalı için entropi hesabı yapılarak ağırlıklı ortalaması alınıp, kazanç değeri hesaplanıyor.
Kod:
|Isı(soğuk)| = 2
|Isı(ılık)| = 3
Isı niteliğinin entropisi =>
H(Isı,Oyun) = [COLOR="Red"](2/5)*H(soğuk) + (3/5)*H(ılık) [/COLOR]
= [COLOR="Red"](2/5)*1 + (3/5)*0.918= 0.951[/COLOR]
Kazanç(Isı) = [COLOR="Red"]0.970 - 0.951[/COLOR]
= [COLOR="Red"]0.019[/COLOR]Rüzgâr Niteliği
Dikkat ettiyseniz, Rüzgâr niteliğinin her bir değeri (Hafif, Kuvverli) için Oyun niteliğinin değeri ya sadece hayır veya sadece evet oluyor. Bu noktada ayrıştırma işlemi tam olarak yapıldığından dolayı dallanma işlemini sonlandırıyoruz.
Bu noktadan sonra dallanma işlemimiz sonlandı ama önemli bir noktaya değinmek için Rüzgâr niteliğinin her bir dalı için entropi hesabını yaparak, ağırlıklı ortalamalarını alıp, kazanç değerini hesaplayalım.
Kod:
|Rüzgâr(hafif)| = 3
|Rüzgâr(kuvvetli)| = 2
Rüzgâr niteliğinin entropisi =>
H(Rüzgâr,Oyun) = [COLOR="Red"](3/5)*H(hafif) + (2/5)*H(kuvvetli)[/COLOR]
= [COLOR="Red"](3/5)*0 + (2/5)*0= 0[/COLOR]
Kazanç(Rüzgâr) = [COLOR="Red"]0.970 - 0[/COLOR]
= [COLOR="Red"]0.970[/COLOR]Şimdi kritik bir noktaya dikkatinizi çekmek istiyorum. Entropi hesabı yapılırken shannon'un entropi formülünü kullandığımızı söylemiştik. Ve bu formülünde temelde entropisi düşük olan niteliklere göre ayrıştırma işlemini yaptığını söylemiştik.
Dikkatlice incelediğimizde kazanç değerinin en fazla olduğu durumun, niteliğin entropisinin en düşük olduğu durum olan 0 değerinde oluştuğunu görebiliriz. Bunu şöyle açıklayabiliriz:
Entropi değerimiz 0 olduğu zaman, kazanç değerimiz maksimum olur. Yukarıdaki örnek için konuşacak olursak, Hava niteliğinin Yağmurlu dallanması için, Rüzgâr niteliğinin kazancı maksimum olmaktadır. Yani düzensizlik 0 olduğu için, diğer nitelikleri kontrol etmeye ihtiyaç duymadan, bu düğümü belirleyici bir düğüm olarak seçmiş oluyoruz. Bunun sebebi Rüzgâr niteliğinde düzensizliğin olmamasından kaynaklı olarak ayrıştırma işleminin tamamlanmış olmasıdır.
Son olarak, ağacımızın son durumu şu şekilde olacaktır:
ÖZET
ID3 Algoritması, Makine Öğrenmesi alanında kullanılan çok önemli bir sınıflandırma (classification) algoritmasıdır. Bu konuda ID3 Algoritmasını kullanarak, basit bir veri seti üzerinde ID3 Algoritmasının çalışma yapısını inceledik. Temel olarak ID3 Algoritması şu şekilde çalışmaktadır;
Sistemdeki entropi (düzensizlik) bulunur.
Bulunan bu düzensizliğe, her bir niteliliğin etkisi araştırılarak, nitelikler için entropi hesabı yapılır. (Nitelikler için entropi hesabı yapılırken, niteliklerin her bir dallanması için entropi hesabı yapılarak, ağırlıklı ortalamaları alınır.)
Nitelikler için genel entropiye göre kazanç hesabı yapılır.
Sistemde kazanç değeri en fazla olan nitelik düğüm olarak seçilir.
Düğüm olarak seçilen niteliğin her bir dalı, ayrı bir sistem olarak düşünülerek yaprağa (ulaşılmak istenen niteliğin değerine) ulaşılıncaya kadar işlemlere devam edilir.
Karar ağacı elde edilir.
ID3 Algoritmasında, öncelikle sistem eğitilerek karar ağacı oluşturulur. Oluşturulan bu karar ağacına göre, gelen yeni veriler hakkında çıkarımlar yapılabilir.
Son düzenleme:
