Bolu Beyi'nden Selam Olsun…

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 < log₂n

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;

1. Her adımda bütün özellikler kontrol edilir
2. Her özelliğin normalize edilmiş bilgi kazancı hesaplanır
3. En iyi bilgi kazancını veren özellik karar ağacına eklenir
4. 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 x² 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 x² 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) – p_L g(t_L)- p_R g(t_R)

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