Veri Madenciliği, veri setlerinin sistematik bir analizini içerir ve verilere anlam verir. Veri madenciliği, verilerin toplanması, ayıklanması, işlenmesi, analiz edilmesi ve bunlardan faydalı içgörüler elde edilmesi üzerine yapılan çalışmadır.

Özellikle günümüzde karar ağacı öğrenme algoritması, bilgi yakalamada uzman sistemlerde başarıyla kullanılmaktadır. Bu makalenin amacı, karar ağacı hakkında kısa bir açıklama sunmaktır. Bu makale, karar ağacının anlamını, en iyi bölme kıstası, popüler karar ağacı algoritmalarını, karar ağacının avantajlarını ve dezavantajlarını açıklığa kavuşturmak amacıyla yazılmış olup yazının sonunda ID3/C4.5 uygulanarak bir data seti ele alınmış ve karar ağacı oluşturulmasına yönelik çalışma yapılmıştır. Büyük veri hakkındaki yazımızı okumak için tıklayınız.

Zeynep Ayça Gürel, Elektrik Mühendisi, Kalite Güvence

Giriş

Bu makale karar ağacının ne olduğunu açıklamakta ve karar ağacının veri madenciliğindeki yeri hakkında bilgi vermektedir. Ayrıca, bu makale ağaç boyutu, en iyi bölme kıstası, entropi ve bilgi kazancı hakkında bilgi içermektedir.

Bir örnek kümesinin (veya eğitim kümesinin) sınıfları, yeni örnekler için sınıfları tahmin etmek üzere örneklerin öznitelik vektörünün davranış şeklini keşfetmek için birkaç algoritma kullanabiliriz.

Başlangıçta mantık, yönetim ve istatistikten türetilen karar ağaçları, günümüzde metin madenciliği, bilgi çıkarma, makine öğrenimi ve örüntü tanıma gibi diğer alanlarda oldukça etkili bir araç haline gelmiştir.

Rokach ve Maimon’a göre, Karar ağaçları birçok fayda sağlar:

• Sınıflandırma, regresyon, kümeleme ve özellik seçimi gibi çok çeşitli veri madenciliği görevleri için çok yönlülük
• Kendinden açıklamalı ve takip etmesi açısından kolaylık (sıkıştırıldığında)
• Çeşitli girdi verilerini işleme esnekliği: nominal, sayısal ve metinsel
• Hatalara veya eksik değerlere sahip olabilecek veri kümelerinin işlenmesinde uyarlanabilirlik
• Nispeten küçük bir hesaplama çabasına göre yüksek tahmin performansı
• Çeşitli platformlar üzerinden birçok veri madenciliği paketine uygunluk
• Büyük veri kümeleri için kullanışlılık (bir topluluk çerçevesinde)

Karar ağacı, ID3, C4.5, CART, CHAID, QUEST, Cal5, Fact, LMDT, T1, Public: mars gibi bir öğrenme algoritmasına sahiptir. Bu yazıda bunlardan sadece ikisi açıklanmıştır.: ID3, C4.5.

ID3 algoritması, basitliği nedeniyle bu yazıda uygulama olarak kullanılacaktır.

Karar Ağaçları ile Veri Madenciliği

Aggarwal’a göre, Karar ağaçları, sınıflandırma sürecinin, ağaç benzeri bir yapıda düzenlenmiş, özellik değişkenleri üzerinde bir dizi hiyerarşik karar kullanılarak modellendiği bir sınıflandırma metodolojisidir.

Sharma ve Bhargava & Mathuria’ya göre, Karar ağacı, ağaç benzeri grafik kararları, şans olay sonuçları, kaynak maliyetleri ve yararları dahil olmak üzere bunların olası artçı etkilerini kullanan bir karar destek sistemidir. Bir Karar Ağacı veya bir sınıflandırma ağacı, bağımsız (girdi) niteliklerin (değişkenlerin) değerleri verildiğinde bir bağımlı niteliğin (değişken) değerini sonlandıran bir sınıflandırma işlevini öğrenmek için kullanılır.

Karar ağacı, köklü bir ağaç oluşturan düğümlerden oluşur, yani bu, gelen kenarları olmayan “kök” adı verilen bir düğüme sahip yönlendirilmiş bir ağaçtır. Diğer tüm düğümlerin tam olarak bir gelen kenarı vardır. Dışarı çıkan kenarlara sahip bir düğüme dahili veya test düğümü denir. Diğer tüm düğümlere yapraklar denir (aynı zamanda terminal veya karar düğümleri olarak da bilinir) [3].

Bir karar ağacında, her bir dahili düğüm, giriş öznitelik değerlerinin belirli bir ayrık işlevine göre örnek alanını iki veya daha fazla alt alana böler. En basit ve en sık karşılaşılan durumda, her test tek bir özniteliği dikkate alır, öyle ki örnek alanı özniteliğin değerine göre bölünür. Sayısal öznitelikler söz konusu olduğunda, koşul [3] aralığına atıfta bulunur.

Her yaprak, en uygun hedef değeri temsil eden bir sınıfa atanır. Alternatif olarak, yaprak, hedef özelliğin belirli bir değere sahip olma olasılığını gösteren bir olasılık vektörü tutabilir. Örnekler, yol boyunca yapılan testlerin sonucuna göre, onları ağacın kökünden bir yaprağa götürerek sınıflandırılır. Şekil 1, potansiyel bir müşterinin doğrudan postalamaya yanıt verip vermeyeceğini açıklayan bir karar ağacını açıklamaktadır. İç düğümler daire ile temsil edilirken, yapraklar üçgenler ile gösterilir. [3]

Bu karar ağacının hem nominal hem de sayısal özellikleri içerdiğine dikkat edin. Bu sınıflandırıcı göz önüne alındığında, analist potansiyel bir müşterinin tepkisini tahmin edebilir (ağacı sıralayarak) ve doğrudan postayla ilgili tüm potansiyel müşteri populasyonunun davranış özelliklerini anlayabilir [3].

Her düğüm test ettiği öz nitelikle etiketlenir ve dalları karşılık gelen değerleriyle etiketlenir [3].

Şekil 1 deki yollar kurala dönüşebilir.  Müşterinin yaşı 30da büyük ise postaya yanıt vermeyecektir.

Bir diğer kuralı da şu şekilde belirtebiliriz: Müşterinin yaşı 30 a eşit veya küçük ise ve müşterinin cinsiyeti erkek ise müşteri postaya yanıt verecektir.

Ortaya çıkan kural kümesi daha sonra bir insan kullanıcı için anlaşılabilirliğini ve muhtemelen doğruluğunu geliştirmek için basitleştirilebilir [4].

2.1 Bölme Kıstası

Bölme kriterinin amacı, farklı sınıfların alt düğümler arasındaki ayrımını en üst düzeye çıkarmaktır. Aşağıda, sadece tek değişkenli kriterler tanımlanmıştır. Bir bölünmeyi değerlendirmek için bir kalite kriterinin mevcut olduğunu varsayalım. Bölünmüş kriterin tasarımı, temeldeki niteliğinin doğasına bağlıdır[1]:

• İkili öznitelik: Yalnızca bir tür bölme mümkündür ve ağaç her zaman ikilidir. Her dal, ikili değerlerden birine karşılık gelir.
• Kategorik öznitelik: Kategorik bir özniteliğin r farklı değeri varsa, onu bölmenin birçok yolu vardır. Bir olasılık, bölünmenin her bir dalının belirli bir öznitelik değerine karşılık geldiği bir r-yollu bölme kullanmaktır. Diğer olasılık, kategorik özelliklerin 2r – 1 kombinasyonlarının (veya gruplamalarının) her birini test ederek ve en iyisini seçerek bir ikili bölme kullanmaktır. Açıkçası, r’nin değeri büyük olduğunda bu uygulanabilir bir seçenek değildir. Bazen kullanılan basit bir yaklaşım, ikilileştirme yaklaşımını kullanarak kategorik verileri ikili verilere dönüştürmektir. Bu durumda, ikili öznitelikler için yaklaşım kullanılabilir.
• Sayısal öznitelik: Sayısal öznitelik az sayıda sıralı değer içeriyorsa (örneğin, küçük bir aralıktaki [1, r] tam sayılar), her bir farklı değer için bir r-yolu bölmesi oluşturmak mümkündür. Bununla birlikte, sürekli sayısal öznitelikler için, bölme tipik olarak öznitelik değeri x ve sabit a için x ≤ a gibi bir ikili koşul kullanılarak gerçekleştirilir.

Yukarıda bahsedilen yöntemlerin çoğu, bir dizi seçenekten “en iyi” ayrımın belirlenmesini gerektirir. Spesifik olarak, her bir özniteliği bölmek için mevcut çeşitli alternatifler ve birden çok öznitelik arasından seçim yapılması gerekir. Bu nedenle, bölünmüş kalite miktarlarının belirlenmesi gereklidir. Bu miktarlar, özellik seçim kriterleri ile aynı ilkelere dayanmaktadır: [1]

2.1.1.  Gini Endeksi

Bir dizi S veri noktası için Gini indeksi G (S), S ‘deki eğitim veri noktalarının p1….pk’si sınıf dağılımı üzerinde hesaplanabilir. [1]

S kümesinin S1 kümelerine r-yollu bölünmesi için genel Gini indeksi. . . Sr, Si’nin ağırlığının | Si | olduğu her Si’nin Gini indeksi değerlerinin G (Si) ağırlıklı ortalaması olarak ölçülebilir. [1]

2.1.1.  Entropi

Entropi ölçümü, ID3 olarak adlandırılan en eski sınıflandırma algoritmalarından birinde kullanılır. [1]

Gini indeksinde olduğu gibi, S kümesinin S1 kümelerine r-yollu bölünmesi için genel entropi. . . Sr, Si’nin ağırlığının | Si | olduğu her Si’nin Gini indeksi değerlerinin G (Si) ağırlıklı ortalaması olarak hesaplanabilir.

Entropinin daha düşük değerleri daha çok arzu edilir. Entropi ölçümü, ID3 ve C4.5 algoritmaları tarafından kullanılır. [1].

Bilgi kazancı entropi ile yakından ilişkilidir ve bölünmenin bir sonucu olarak entropi E (S) – Entropi-Bölünmüş (S ⇒ S1.. Sr) azalmasına eşittir. Büyük indirgeme değerleri arzu edilir. Kavramsal düzeyde, ikisinin ikisinin de bir bölünme için kullanılması arasında bir fark yoktur, ancak bilgi kazanımı durumunda bölünme derecesi için bir normalizasyon mümkündür. Entropi ve bilgi kazancı ölçümlerinin yalnızca aynı derecedeki iki bölünmeyi karşılaştırmak için kullanılması gerektiğine dikkat edin, çünkü her iki ölçüm de doğal olarak daha büyük dereceli bölünmeler lehine önyargılıdır. Örneğin, kategorik bir özniteliğin birçok değeri varsa, çok değerli öznitelikler tercih edilecektir.

Örneğin, kategorik bir özniteliğin birçok değeri varsa, çok değerli öznitelikler tercih edilecektir. C4.5 algoritması, genel bilgi kazancını   nin normalleştirme faktörüne bölmenin değişen sayıdaki kategorik değerlerin ayarlanmasına yardımcı olduğu gösterilmiştir [1].

Örneğin, sayısal bir veritabanı durumunda, her sayısal öznitelik için farklı bölme noktaları test edilir ve en iyi bölme seçilir [1].

2.2 Popüler Karar Ağacı Algoritmaları

2.2.1.  ID3 Algortiması

ID3 algoritması çok basit bir karar ağacı algoritması olarak kabul edilir [7]. Bilgi kazancını bir bölme kriteri olarak kullanan ID3 algoritması, tüm örnekler bir hedef özelliğin tek bir değerine ait olduğunda veya en iyi bilgi kazancı sıfırdan büyük olmadığında büyümeyi durdurur. ID3 herhangi bir budama prosedürü uygulamaz ve sayısal nitelikleri veya eksik değerleri işlemez. ID3’ün temel avantajı basitliğidir. Bu nedenle ID3 algoritması öğretim amacıyla sıklıkla kullanılmaktadır [8].

2.2.2.  C4.5 Algortiması

Aynı yazar tarafından sunulan ID3’ün bir evrimi olan C4.5, bölme kriteri olarak kazanç oranını kullanır. [9]. Bölünecek örnek sayısı belirli bir eşiğin altına düştüğünde bölme durur. Büyüme aşamasından sonra hataya dayalı budama yapılır. C4.5 sayısal öznitelikleri işleyebilir [8].

C4.5 algoritması, ID3’e çeşitli iyileştirmeler sağlar. En önemli iyileştirmeler [8]:

• 5, doğruluğa katkıda bulunmayan dalları kaldıran ve bunları yaprak düğümlerle değiştiren bir budama prosedürü kullanır.
• 5, nitelik değerlerinin eksik olmasına izin verir (? Olarak işaretlenir).
• 5, özniteliğin değer aralığını iki alt kümeye (ikili bölme) bölerek sürekli öznitelikleri yönetir. Spesifik olarak, kazanç oranı kriterini maksimize eden en iyi eşiği arar. Eşiğin üzerindeki tüm değerler ilk alt kümeyi ve diğer tüm değerler ikinci alt kümeyi oluşturur.

2.2.Karar Ağaçlarının Avantaj ve Dezavantajları

Karar ağacının bir sınıflandırma aracı olarak çeşitli avantajları literatürde belirtilmiştir [8]:

1. Karar ağaçları kendiliğinden açıklayıcıdır ve sıkıştırıldıklarında izlemeleri de kolaydır. Diğer bir deyişle, karar ağacının makul sayıda izni varsa, profesyonel olmayan kullanıcılar tarafından kavranabilir. Ayrıca karar ağaçları bir dizi kurala dönüştürülebilir. Dolayısıyla bu temsilin anlaşılabilir olduğu düşünülmektedir.
2. Karar ağaçları hem nominal hem de sayısal girdi özniteliklerini işleyebilir.
3. Karar ağacı temsili, herhangi bir ayrık değer sınıflandırıcısını temsil edecek kadar zengindir.
4. Karar ağaçları, hatalı olabilecek veri kümelerini işleyebilir.
5. Karar ağaçları, eksik değerlere sahip olabilecek veri kümelerini işleme yeteneğine sahiptir.
6. Karar ağaçları parametrik olmayan bir yöntem olarak kabul edilir. Bu, karar ağaçlarının alan dağılımı ve sınıflandırıcı yapısı hakkında hiçbir varsayımının olmadığı anlamına gelir.
7. Sınıflandırma maliyeti yüksek olduğunda, karar ağaçları sadece kökten yaprağa tek bir yoldaki özelliklerin değerlerini talep etmeleri açısından çekici olabilir.

Öte yandan, karar ağaçlarının şu gibi dezavantajları vardır [8]:

1. Algoritmaların çoğu (ID3 ve C4.5 gibi), hedef özelliğin yalnızca ayrı değerlere sahip olmasını gerektirir.
2. Karar ağaçları “böl ve yönet” yöntemini kullandıklarından, oldukça alakalı birkaç özellik varsa iyi performans gösterme eğilimindedirler, ancak birçok karmaşık etkileşim varsa daha az performans gösterirler. Bunun nedenlerinden biri, diğer sınıflandırıcıların, bir karar ağacı kullanarak temsil etmesi çok zor olacak bir sınıflandırıcıyı kompakt bir şekilde tanımlayabilmesidir.

Çoğu karar ağacı, bir kavramı temsil etmek için örnek alanını birbirini dışlayan bölgelere böldüğünden, bazı durumlarda ağaç, sınıflandırıcıyı temsil etmek için aynı alt ağacın birkaç kopyasını içerir. Örneğin, kavram aşağıdaki ikili işlevi izlerse: y = (A1 \ A2) [(A3 \ A4) bu işlevi temsil eden minimum tek değişkenli karar ağacı Şekil 2’de gösterilmektedir Ağacın aynı alt satırın iki kopyasını içerdiğine dikkat edilmelidir.

3.Karar ağaçlarının açgözlü özelliği, belirtilmesi gereken başka bir dezavantaja yol açar. Bu, eğitim setine, ilgisiz niteliklere karşı aşırı duyarlılığı karar ağaçlarını özellikle istikrarsız hale getirir: köke yakın bir bölünmede küçük bir değişiklik aşağıdaki tüm alt ağacı değiştirecektir [9].

4. Parçalanma sorunu, verilerin daha küçük parçalara bölünmesine neden olur. Bu genellikle yol boyunca birçok özellik test edilirse gerçekleşir. Veriler her bölünmede yaklaşık olarak eşit olarak bölünüyorsa, tek değişkenli bir karar ağacı O (logn) özelliklerinden fazlasını test edemez. Bu, birçok ilgili özelliğe sahip görevler için karar ağaçlarını dezavantajlı konuma getirir. Çoğaltmanın her zaman parçalanma anlamına geldiğini, ancak parçalanmanın herhangi bir çoğaltma olmadan gerçekleşebileceği unutulmamalıdır.
5. Diğer bir problem, eksik değerlerle başa çıkmak için gereken eforla ilgilidir [15]. Eksik değerleri ele alma becerisi bir avantaj olarak kabul edilirken, bunu başarmak için gereken aşırı çaba bir dezavantaj olarak kabul edilir. Test edilen bir özellik eksikse alınacak doğru dal bilinmemektedir ve algoritmanın eksik değerleri işlemek için özel mekanizmalar kullanması gerekir. C4.5, eksik değerler üzerindeki test oluşumlarını azaltmak için, bilgi kazanımını bilinmeyen vakaların oranıyla cezalandırır ve ardından bu örnekleri alt ağaçlara böler. CART, yerine geçen özelliklerin çok daha karmaşık bir şemasını kullanır.

3-Uygulama

Bu uygulamada ID3 / C4.5 uygulanacaktır.  Bir şirketin A,B,C ürünleri ile ilgili satış detayları verilmiştir. Bu ürünler ile beraber aşağıda belirlenen özelliklerde ürünler ile beraber aksesuar alma kararı da sette tanımlanmıştır.

Örneğin; A ürün tipi 5 ten az sayıdaki alımlar için düşük cirolu bir müşteri tarafından yurtiçinde kullanılmak üzere aksesuarsız olarak alınmıştır.

P = Aksesuarlı ürün alma “evet” = 26

N= Aksesuarlı ürün alma “hayır” = 37

İlk ayrılmayı bulabilmek için bilgi kazancı formülü kullanılarak tüm seçenekler için hesaplama yapılır.

Bu hesaplamalara göre en yüksek kazanca sahip satr özelliği ilk bölünme ayrımı olarak seçilir. Bu da karar ağacımızda yurtiçi evet ve yurtiçi hayır olmak üzere 2 ayrı kol oluşturur.

Tabloda yurtiçi evet ve yurt içi hayır seçenekleri seçilerek iki ayrı tablo oluşturulur ve bu kollar için kazanç tekrar hesaplanır.

Bu aşamada karar ağacı aşağıdaki şekildedir:

Tüm kollar için hesaplamalar tekrarlanarak en son bölünme noktası bulunana kadar hesaplama yapılmaya devam edilir.

Yurtiçi bölünmesi için “evet” kolu :

P = Aksesuarlı ürün alma “evet” = 24

N= Aksesuarlı ürün alma “hayır” = 14

Burada en yüksek kazanç seçilir. En yüksek kazanç tip seçeneğinde bulunmaktadır. Artık kollarımızında bu tip seçeneğine göre ayrılmış olduğunu bulduk. (A, B, C)

Şu ana kadar hesapladıklarımız ile karar ağacının şekli aşağıdaki gibi oluşmuştur:

B ve C Ürün tipi listelendiğinde, Aksesuar alma kararının direkt Evet olduğu görülecektir. A ürün tipi için ise bilgi kazancı hesaplanmaya devam edilir.

P = Aksesuarlı ürün alma “evet” = 5

N= Aksesuarlı ürün alma “hayır” = 14

En yüksek kazanç seçilerek bu hesaplamaya ve kol ayırmaya devam edilir.

Sonuç olarak karar ağacı aşağıdaki şekilde oluşur:

Yukarıdaki karar ağacına göre aşağıdaki kararlar oluşturulabilir: Ürün tipi A ve B için tüm yurt içi siparişleri aksesuar almaktadır. Ürün tipi A ve B için yurtdışı siparişlerinde aksesuar satışı yapılmamaktadır. 5-10 ürün sayısına sahip yurtiçi siparişlerinde C ürün tipinde aksesuar satılmamaktadır.

4-Sonuç

Bu makale karar ağaçlarının tanımlarını, avantajlarını ve dezavantajlarını sunmaktadır.

Ayrıca, bu makalede  avantajları ve dezavantajları ile ID3, C4.5 algoritmalı karar ağacı yaklaşımları vermektedir;. ID3’ün temel avantajı basitliğidir. Bu nedenle ID3 algoritması öğretim amaçlı sıklıkla kullanılmaktadır. C4.5 algoritması, ID3’ün bir evrimidir ve bu, bölme kriteri olarak kazanç oranını kullanır. Yazının 3. Bölümünde ise ID3 kullanılarak veri seti üzerinde karar ağacı oluşturulması yöntemi tanımlanmıştır.

5-Referanslar

3. [1] Aggarwal, C. C. (2015). Data mining: the textbook
4. [2] Bhargava, N., Sharma, G., Bhargava, R., & Mathuria, M. (2013). Decision tree analysis on j48 algorithm for data mining. Proceedings of International Journal of Advanced Research in Computer Science and Software Engineering, 3(6).
5. [3] Rokach, L., & Maimon, O. (2005). Decision trees. In Data mining and knowledge discovery handbook (pp. 165-192). Springer, Boston, MA.
6. [4] Quinlan, J.R., Simplifying decision trees, International Journal of Man-Machine Studies, 27, 221-234, 1987.
7. [5] Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and regression trees. Wadsworth Int. Group, 37(15), 237-251.
8. [6] Rokach, L., & Maimon, O. Z. (2008). Data mining with decision trees: theory and applications (Vol. 69). World scientific.
9. [7] Quinlan J. R., Induction of decision trees, Machine Learning 1:81–106, 1986.
10. [8] Rokach, L., & Maimon, O. (2015). Data mining with decision trees–Theory and Applications 2nd Edition. Series in Machine Perception and Artificial Intelligence, 81, 328.
11. [9] Quinlan, J. R., C4.5: Programs for Machine Learning, Morgan Kaufmann, Los Altos, 1993.
12. [10] Moore S. A., Daddario D. M., Kurinskas J. and Weiss G. M., Are decision trees always greener on the open (source) side of the fence?, Proceedings of DMIN, pp. 185–188, 2009.
13. [11] Kass G. V., An exploratory technique for investigating large quantities of categorical data, Applied Statistics 29(2):119–127, 1980.
14. [12] IBM SPSS Decision Trees 19 by SPSS Inc. 1989, 2010.
15. [13] Loh W. Y., and Shih X., Split selection methods for classification trees, Statistica Sinica 7:815–840, 1997.
16. [14] Pagallo, G. and Huassler, D., Boolean feature discovery in empirical learning, Machine Learning, 5(1): 71-99, 1990.

• [15] Friedman, J., Kohavi, R., Yun, Y. 1996. Lazy decision trees. Proceedings of the Thirteenth National Conference on Artificial Intelligence. (pp. 717-724).