Teknolojinin gelişmesi, saklanacak veri sayısı ve veri boyutunun artmasıyla birlikte gün geçtikçe veri madenciliğine olan ihtiyaç artmaktadır. Bununla birlikte saklanacak verilerin saklanması için bilgisayar ortamına ihtiyaç duyulmakta ve istenilen performanslar, tespitler, sınıflandırmalar vs. için veri madenciliğine yönelim gerçekleşmektedir. Bu makalede ise veri madenciliği uygulamalarından olan, karar ağaçları incelenecek olup, az sayıda veri setinden oluşan küçük bir örnek uygulama gerçekleştirilecektir. Örnek uygulama sırasında yaklaşık 10-15 veriye sahip bir eğitim kümesi oluşturulacak, karar ağacı algoritmalarından bir tanesi seçilerek örnek yapılacaktır.
Karar ağaçları, veri madenciliğinde en çok kullanılan yöntemlerden biridir. Bir veri, karar ağacına göre sınıflandırılmak istendiğinde, sınıf etiketleri bilinen bir veri setine ihtiyaç duyulur. Veri seti üzerinde karar verme basamakları uygulanarak, çok sayıdaki kayıtlı veriler, az sayıda gruplarına bölünür. Her bölme işlemi yapıldığında, özellikleri bakımından birbirine benzer veriler grup haline gelir. Karar ağaçları için farklı dallanma kriterleri mevcuttur.
ID3(Iterative Dichotomiser 3) Algoritması
ID3 algoritması entropiye dayalı bir algoritmadır. Nitelikler birbirinden bağımsızdır. Bu algoritmada amaç, ağaç oluşturulurken öğrenme kümesindeki veriler mümkün olduğunca birbirine benzer hale getirilir ve böylece ağaç derinliği minimum seviyede tutulur. Karmaşıklık minimuma indirilir, kazanç maksimum seviyede olur.
Karmaşıklık belirlemek amacıyla entropi kuralları içeren bilgi teorisi kullanılmaktadır. Entropi değer aralığı, sınıf etiket sayısına göre değişiklik göstermektedir.
“n” sınıf etiketine sahip bir veri setindeki entropi değer aralıkları:
0 < entropi < log2n
Bu duruma göre, 2 sınıf etiketine sahip bir veri setinin entropi değer aralıkları 0 ile 1 arasında olacaktır. Entropi değeri 1’e yaklaştıkça belirsizlik(karmaşıklık) artar, 0’a yaklaştıkça belirsizlik azalır. Yani birbirine benzer verilerin bulunduğu bir veri seti 0’a yakın olacaktır.
ID3 algoritmasını adım adım uygulayacak olursak;
- Ağaca dahil edilmemiş olan bütün niteliklerin entropi değerleri hesaplanır
- En düşük entropi değerine sahip olan nitelik seçilerek ağaca dahil edilir
Her yol için bu adımlar tekrarlanır.
C4.5 ve C5.0 Algoritması
C4.5 ve C5.0 algoritmaları ID3 algoritmasının bazı eksik yönlerini gidermek için geliştirilmiştir. C5.0 algoritması da C4.5’e göre doğruluğu artırmak amacıyla geliştirilmiş bir algoritmadır ve özellikle büyük sayıda verilerden oluşan veri setlerinde kullanılmaktadır. Doğruluğun artırılmasını sağlamak amacıyla boosting algoritmasını da kullanır. C4.5 ve C5.0 algoritmaları da temelde ID3 algoritmasının özellikleri kullanılır. Bu algoritmaların en büyük farkı normalizasyon yapılmasıdır. ID3 ağacı üzerinde entropi hesabı yapılır ve bu değere göre karar noktaları belirlenir. C4.5 ağacında hesaplanan entropi değerleri oran olarak tutulur. Ayrıca ağaç üzerinde erişim sıklıklarına göre alt ağaçlar farklı seviyelere taşınabilir. C4.5 ağacının bir diğer farkı da budama işleminin yapılabilmesidir.
C4.5 ve C5.0 algoritmasını adım adım takip edecek olursak;
- Her adımda bütün özellikler kontrol edilir
- Her özelliğin normalize edilmiş bilgi kazancı hesaplanır
- En iyi bilgi kazancını veren özellik karar ağacına eklenir
- Bütün yollar için bu adımlar tekrar edilir
Chi-Kare Otomatik İlişki Tarayıcısı (Chi-Square Automatic Interaction Detector, CHAID)
Chaid algoritması, sürekli olmayan, kategorik bağımlı veriler için oluşturulmuştur. Chaid algoritmasıyla, veriler birbirine benzer alt gruplara ayrılır. Her bir veri için kategoriler oluşturulur ve bölünme sonucu gruplaşan veriler, bir önceki grubun özeti şeklindedir. Kategoriler, anlamlı bir şekilde birleştirildikten sonra tablolar oluşturulur ve x2 istatistikleri hesaplanır. Veriler birbirleriyle karşılaştırılıp, kategorilere göre alt gruplara ayrılır.
Alt gruplar, bağımsız bir şekilde tekrar analiz edilir
, her bir veri kategorisinde bölünmeler oluşturularak x2 testindeki önemine göre tablolar(kontenjans) oluşturulur. Böylelikle araştırmacılar, ağaç yapısıyla önemli verileri ve bağımlı verilerle olan ilişkileri elde ederler.
C&RT Algoritması
C&RT algoritması 1984 yılında Breiman ve Friedman tarafından, bütün aşamalarda her bir grubu kendinden daha homojen grup oluşturacak şekilde alt gruplara ayırmayı hedefleyen bir yapı ile oluşturulmuştur.
Her seviyede öznitelik seçme işlemi yapılırken bağımlı değişkenler için gini ve twoing indeks, sürekli değişkenler için ise en küçük kare sapması(Least-Squared Deviation) indeks hesaplamaları yapılır. Bu algoritma kar, maliyet değerleri ve önceliklerin tanımlanması gibi esneklikleri gibi avantajları nedeniyle günümüzde yaygın olarak kullanılmaktadır.
Gini indeksi hesaplanırken ,
Φ(s,t) = g(t) – pL g(tL)- pR g(tR)
formülasyonu kullanılmaktadır. Bu eşitlikte Φ(s,t) değerinin maksimum olmasını sağlayacak s değerinin seçilmesi amaçlanmaktadır. t düğümündeki bütün verilerle hesaplanan bu değer, C&RT ağacında improvement kavramı ile ifade edilmektedir.
CAL5 Algoritması
CAL5 algoritması istatistiki veri aralıklarını kullanarak gerçek veri değerlerinin sınıflandırılmasını ve öngörüye dayalı tahminler üretilmesini sağlar. En uygun sınıf ayrımı oluşturulacak şekilde aralıklar otomatik olarak belirlenir. Ağaçta sınıflar arasındaki ayrımı artırmak için top-down yaklaşımı kullanılır. Her seviyede yeni bir özellik eklenerek en alt seviyeye inilir. Her seviyede seçilecek olan öznitelik entropi hesabı ile belirlenir.
Rastgele Orman(Random Forest) Algoritması
Breiman’ın geliştirdiği bu algoritmada amaç tek bir karar ağacı üretmek yerine her biri farklı eğitim kümelerinde eğitilmiş olan çok sayıda çok değişkenli ağacın kararlarını birleştirmektir. Farklı eğitim kümeleri oluştururken ön yükleme ve rastgele özellik seçimi kullanılır. Çok değişkenli karar ağaçları oluşturulurken CART algoritması kullanılır. Her seviyedeki özniteliği belirlerken önce bütün ağaçlarda hesaplamalar yapılarak nitelik belirlenir, ardından bütün ağaçlardaki nitelikler birleştirilerek en fazla kullanılan öznitelik seçilir. Seçilen nitelik ağaca dahil edilerek diğer seviyelerde aynı işlemler tekrarlanır.
Döndürme Ağacı (Rotation Forest) Algoritması
Breiman’ın geliştirdiği rastgele orman algoritmasına benzer bir algoritmadır. Rastgele Orman’dan farklı olarak, öncelikle farklı bileşen analiziyle eğitilmesi sağlanmaktadır. Eğitilmesi için, very seti rastgele seçilen bir alt küme kullanılır.
MARS(Multivariate Adaptive Regression Splines; Friedman)
Daha çok sayısal verilerin sık bulunduğu veri setlerinde kullanılmaktadır. MARS algoritması, karar ağaçlarından daha iyi sonuç elde etmek için kullanılan bir dallanma kriteridir.
Hızlandırılmış Ağaçlar (Boosted Trees)
Regresyon analiziyle birlikte sınıflandırma problemleriyle kullanılan karar ağacı algoritmasıdır Statik değildir fakat güçlü bir karar ağacı algoritmasıdır. Ufak bir değişiklik tüm ağacı etkileyebilir.
SPRINT (Scalable PaRallelizable Induction of Decision Trees )
SPRINT algoritmasında bağlı listeler kullanılır ve veriler bu şekilde ağaca yerleştirilir. Bağlı listelerle yalnızca bir kez sıralama yapılır ve bu yüzden hızlı bir algoritmadır. SPRINT algoritması da çok sayıda veri içeren veri setlerinde avantaj sağlamaktadır.
SLIQ Algoritması
Bu algoritma Shih ve Loh tarafından 1977 yılında geliştirilmiştir ve budama ve doğrudan durma teknikleri kullanılabildiğinden, ikili karar ağacı yapısını kullanarak sınıflandırma yapmaktadır. QUEST algoritması, hesaplama maliyetini düşürmek maksadıyla geliştirilmiştir.
SLIQ algoritması, ID3, C4.5 ve C5.0 algoritmalarına benzer olarak derinlik(depth first) mantığıyla çalışmaktadır. Farklı olarak, veriyi ağaca yerleştirmek yerine enine olarak “breth first” mantığını kullanmaktadır. Veri setinin çok büyük olduğu durumlarda hızlı sonuçlar aldığından çok tercih edilen algoritmalardan biridir.
ID3 ile Örnek bir Uygulama
Karar ağacı örneği için ID3(Iterative Dichotomiser 3) algoritması kullanılmıştır. Veri seti olarak “http://archive.ics.uci.edu/ml/datasets/Car+Evaluation” adresindeki “car evaluation” veri seti sadeleştirilmiştir. Veri seti tablosu aşağıdaki şekildedir:
ID | BAKIM | FİYAT | GÜVENLİK | KİŞİ | ETİKET |
1 | Kolay | Uygun | Orta | 4 | Alınır |
2 | Zor | Pahalı | Orta | 4 | Alınmaz |
3 | Kolay | Uygun | İyi | 2 | Alınır |
4 | Zor | Uygun | İyi | 4 | Alınır |
5 | Kolay | Pahalı | Orta | 4 | Alınmaz |
6 | Kolay | Uygun | İyi | 2 | Alınır |
7 | Kolay | Uygun | Kötü | 4 | Alınmaz |
8 | Zor | Pahalı | Kötü | 2 | Alınmaz |
9 | Kolay | Uygun | Orta | 4 | Alınır |
10 | Zor | Pahalı | Kötü | 4 | Alınmaz |
11 | Kolay | Pahalı | Orta | 2 | Alınmaz |
12 | Zor | Uygun | İyi | 2 | Alınmaz |
13 | Kolay | Pahalı | Orta | 2 | Alınmaz |
14 | Zor | Uygun | Kötü | 2 | Alınmaz |
Tablo: Car Evaluation Veri seti
Gain sonucunda maksimum olan nitelik, ağaca ilk yerleşecektir. Bu örnekte, nitelik entropileri hesaplandıktan sonra, entropisi minimum değere sahip olan nitelik seçilecektir.
Sınıf E: Araba = ”Alınır”
Sınıf H: Araba = ”Alınmaz”
Info(D)=I(5,9) = -5/14 * log2(5/14) – 9/14 * log2(9/14) = 0,92
Info-bakım(D) = 8/14 * I(4,4) + 6/14 * I(1,5)
= 8/14 * (-4/8 * log2(4/8) – 4/8 * log2(4/8)) + 6/14 * (-1/6 * log2(1/6) – 5/6 * log2(5/6))
= 0,56
Info-fiyat(D) = 8/14 * I(5,3) + 6/14 * I(0,6)
= 8/14 * (-5/8 * log2(5/8) – 3/8 * log2(3/8)) + 0 = 0,51
Info-güvenlik(D) = 4/14 * I(0,4) + 6/14 * I(2,4) + 4/14 * I(3,1)
= 0 + 6/14 * (-2/6 * log2(2/6) – 4/6 * log2(4/6)) + 4/14 * (-3/4 * log2(3/4) – 1/4 * log2(1/4)) = 0,59
Info-kişi(D) = 7/14 * I(3,4) + 7/14 * I(2,5)
= 7/14 * (-3/7 * log2(3/7) – 4/7 * log2(4/7)) + 7/14 * (-2/7 * log2(2/7) – 5/7 * log2(5/7))
= 0,88
–> minimum = Fiyat
Info-bakım(D) = 5/8 * I(4,1) + 3/8 * I(1,2)
= 5/8 * (-4/5 * log2(4/5) – 1/5 * log2(4/5)) + 3/8 * (-1/3 * log2(1/3) – 2/3 * log2(2/3))
= 0,32
Info-güvenlik(D) = 2/8 * I(0,2) + 2/8 * I(2,0) + 4/8 * I(3,1)
= 0 + 0 + 4/8 * (-3/4 * log2(3/4) – 1/4 * log2(1/4)) = 0,4
Info-kişi(D) = 4/8 * I(2,2) + 4/8 * I(3,1)
= 4/8 * (-2/4 * log2(2/4) – 2/4 * log2(2/4)) + 4/8 * (-3/4 * log2(3/4) – 1/4 * log2(1/4))
= 0,9
–> minimum = Bakım
KOLAY:
Info-güvenlik(D) = 1/5 * I(0,1) + 2/5 * I(2,0) + 2/5 * I(2,0) = 0 + 0 + 0 = 0
Info-kişi(D) = 2/5 * I(2,0) + 3/5 * I(2,1) = 0 + 3/5 * (-2/3 * log2(2/3) – 1/3 * log2(1/3))
= 0,25
–> minimum = Güvenlik
ZOR:
Info-güvenlik(D) = 1/3 * I(0,1) + 0/3 * I(0,0) + 2/3 * I(1,1)
= 0 + 0 + 2/3 * (-1/2 * log2(1/2) – 1/3 * log2(1/3)) = 0,67
Info-kişi(D) = 2/3 * I(0,2) + 1/3 * I(1,0) = 0 + 0 = 0
–> minimum = Kişi
Keşke Chi-Square ile ilgili de bir örnek olaydı…
Burada bir örnek mevcut: http://ceng.gazi.edu.tr/~ozdemir/teaching/dm/slides/02.DM.DataPreProcessing.pdf
Örnek için teşekkürler.Ama ben bunu kastetmemiştim aslında.Benim örnekten kastettiğim,ki-kare kullanılarak bir karar ağacı üzerinde nasıl işlem yaparız,yani ki-kare testinin karar ağacına uygulanması aşamasında örnek arıyorum ben.
Hocam tam aradığım şeyi yazmışınız. Ödev 5 saniyede bitti 😀 Teşekkürler
Hocam sprint ve sliq algoritmalarına dair örnek yayınlamanız mümkün mü
CAL5 algoritması hakkında bilgi örnek veya kaynak verebilirmisiniz
Şuradaki makaleyi inceleyebilirsiniz: https://www.hindawi.com/journals/aai/2009/134807/
Merhabalar, benim cal 5 algoritması üzerine araştırma yapmam gerekiyor. Araştırmalarım sonucunda sizin sitenize ulaşabildim fakat biraz daha derine bir araştırma yapmam gerekiyor. Bunun için bana önerebileceğiniz kaynak veya yol gösterebileceğiniz bir durum varsa çok sevinirim. Şimdiden teşekkür ederim.
Şuradaki makaleyi inceleyebilirsiniz: https://www.hindawi.com/journals/aai/2009/134807/
Çok çok teşekkür ederim 🙂
Teşekkür ederim Hocam,
İyi çalışmalar 🙂