Karar ağaçları

Açılış

Martın ikinci çarşambası Onur belediyenin toplantı odasındaki masaya iki çıktı koydu. Soldaki deste Hakan Bey'in tanıdığı bir şeydi: on yedi yıl önce yazılmış yönlendirme modülünün iki yüz on iki satırı, yer yer kurşun kalemle karalanmış. Sağdaki ise iki sayfalık bir çizimdi. En üstte bir kutu, kutudan iki ok, her okun ucunda yeni bir kutu; en altta müdürlük adları.

"Bunu kimse yazmadı," dedi Onur. "Burcu'yla şubatta elle etiketlediğimiz iki yüz başvurudan çıktı."

Hakan Bey sağdaki sayfayı önüne çekti ve parmağını en üstteki kutuya koydu. Kutuda "Metinde 'su' geçiyor mu?" yazıyordu. Evet okunu izledi; ikinci kutu "Metinde 'park' geçiyor mu?" diye soruyordu. Bir kez daha evet; okun ucunda Park ve Bahçeler. Hakan Bey bir an durdu. Çeşme başvurusu yüzünden bir zamanlar yazmayı düşünüp vazgeçtiği iki yüz on üçüncü satıra benzer bir şey, kimse istemeden sayfada duruyordu.

"Bunu okuyabiliyorum," dedi. Sesinde biraz şaşkınlık vardı. Asistanın neden bir başvuruyu bir yere gönderdiğini aylardır kimse ona gösterememişti.

Sonra parmağı ikinci sayfanın dibine indi ve orada kaldı. Dallardan biri şöyle bitiyordu: metinde "su" yok, "çöp" yok, "Sayın" var; o zaman Fen İşleri. Hakan Bey başını kaldırdı. "Bu ne demek? 'Sayın' diye başlayan dilekçe Fen İşleri'nin mi oluyor?"

Burcu dizüstü bilgisayarında o dala düşen başvuruları açtı. Üç taneydi, üçü de aynı mahalleden, aynı kırık kaldırım için yazılmıştı.

Tek fikir

Bir karar ağacı, örnekleri her adımda grupları en çok ayrıştıran evet-hayır sorusuyla böler ve okunabilir bir soru zinciri bırakır. Okunabilmesi doğru olduğunu göstermez: ağaç ne kadar derinleşirse o kadar çok rastlantıyı soruya çevirir.

Nasıl çalışır

Ders 1.2'de kural tabanlı sistemi, 2.3'te uzman sistemi gördük. İkisinde de "şu varsa şuraya" biçimindeki satırları bir insan yazar. Hakan Bey'in modülü böyleydi; her satır, bir zamanlar yanlış yere giden bir başvurunun hatırasıydı. Onur'un sayfası aynı biçimde okunuyor ama satırları başka bir yoldan geldi.

Seçim şöyle yapılır. Elde bir yığın etiketli başvuru vardır. Model her aday soruyu dener, yığını o soruya göre ikiye ayırır ve her iki parçanın ne kadar karışık kaldığına bakar. İyi bir soru, Park ve Bahçeler başvurularını bir yana, Su ve Kanalizasyon başvurularını öbür yana toplar. Kötü bir soru iki parçayı da başta olduğu kadar karışık bırakır.

Onur'un ağacında "su" geçen kırk başvuruluk düğüme bakalım. Yirmi sekizi Su ve Kanalizasyon'un, on ikisi Park ve Bahçeler'in işidir. Bu düğümün Gini safsızlığı sıfır virgül kırk ikidir: biri yüzde yetmiş, öteki yüzde otuz olan iki payın karelerini birden çıkarınca bu sayı kalır.

İlk aday soru "metinde 'park' geçiyor mu?" olsun. Evet diyen on üç başvurunun on biri Park ve Bahçeler'in, ikisi Su ve Kanalizasyon'un; safsızlık sıfır virgül yirmi altı. Hayır diyen yirmi yedi başvurunun yalnız biri Park ve Bahçeler'in; safsızlık sıfır virgül sıfır yedi. İki parçanın safsızlığını büyüklükleriyle tartıp toplayınca sıfır virgül on üç bulunur.

İkinci aday "metinde 'çeşme' geçiyor mu?" olsun. Evet diyen dokuz başvurunun yedisi Park ve Bahçeler'in, ikisi değil; hayır diyen otuz bir başvurunun beşi Park ve Bahçeler'in. Parçaların safsızlığı sıfır virgül otuz beş ile sıfır virgül yirmi yedi, tartılmış toplam sıfır virgül yirmi dokuz.

Başlangıçtaki sıfır virgül kırk iki, "park" sorusuyla sıfır virgül on üçe, "çeşme" sorusuyla sıfır virgül yirmi dokuza iniyor. Model "park"ı seçer. Sonra aynı işi her alt parçada, kalan sorularla yeniden yapar ve parçalar arılaşana ya da soracak anlamlı soru kalmayana kadar sürer. Her adım yalnız o anki en iyi soruyu arar; bütün ağaçların en iyisini aramaz.

Bu yöntemin kurucu metinlerinden biri, uzman sistemlerin tıkandığı yerden yola çıkar.

Şimdi açılıştaki "Sayın" dalına dönelim. Ağaç durdurulmazsa her yaprakta tek sınıf kalana kadar soru sormaya devam eder. Üç başvuruluk bir köşede bile ayırt edici bir kelime bulur ve onu kural gibi yazar. Eğitim örneklerinin hepsini doğru sınıflayan böyle bir ağaç, yeni başvurularda rastlantıyı tekrar eder. Bu ezberin adını Modül 6'da koyacağız. Onur ölçtü: başvuruların yüz onuyla kurduğu iki sayfalık ağaç, sınama için hiç dokunmadan ayırdığı elli başvurunun otuz yedisini doğru yönlendirdi.

Quinlan'ın makalesi ilk yolu anlatır: bir sorunun sınıfla ilgisizliği yüksek bir güvenle reddedilemiyorsa o soru hiç sorulmaz. Onur ikinci yolu denedi: ağacı büyüttü, sonra kalan kırk başvuruda doğruluğu düşürmeyen her dalı kesti. Geriye bir sayfa kaldı, "Sayın" dalı gitti; sınama için ayrılan elli başvurunun kırk biri doğru yere gitti.

Ağaç sayı da tahmin edebilir. O zaman yaprakta bir sınıf yerine, o yaprağa düşen eğitim örneklerinin ortalaması durur ve safsızlık yerine yapraktaki sayıların ne kadar dağınık olduğuna bakılır.

Sahada

Nerede yanılır

Karar ağacının en çok şaşırtan zayıflığı oynaklığıdır. Onur ile Burcu'nun şubatta on bir başvuruda farklı müdürlük yazdığını hatırlayalım. Onur, o on bir başvuruya kendi etiketi yerine Burcu'nunkini koyup ağacı yeniden kurdu. İkinci kattaki soru değişti; altındaki dalların neredeyse hepsi başka biçim aldı. Yönlendirme doğruluğu pek oynamadı, ama Hakan Bey'in okuduğu "neden" bambaşka bir sayfaya dönüştü. Sebebi seçimin yapısındadır: iki soru birbirine yakınsa birkaç örnek kazananı değiştirir ve o tek seçim altındaki bütün ağacı sürükler.

İkinci yanılgı yeri, ağacın her sütunu soru adayı saymasıdır. Ferhat Bey'in parsel numarası gibi, Burcu'nun aynı mahalleden gelen üç dilekçesi gibi, başka bir şeyin izini taşıyan her sütun ya da kelime ağaca girebilir. Ağaç bunun bir rastlantı olduğunu bilemez; yalnız grupları ayırdığını görür. Bu yüzden derin bir ağacın en alttaki dalları, sayıca az örneğe dayandıkları için en az güvenilecek yerlerdir.

Üçüncüsü açgözlü seçimin sınırıdır. Her düğüm o anda en iyi görünen soruyu alır. Quinlan da yöntemin genellikle basit ağaçlar bulduğunu ama daha iyi bir ağacın gözden kaçmadığını garanti edemediğini yazar. İki sorunun ancak birlikte anlam taşıdığı bir durumda, ilk adımda ikisi de zayıf göründüğü için ağaç ikisini de yanlış sırayla sorabilir.

Son olarak okunabilirliğin bir sınırı vardır. Bir sayfalık ağaç okunur; dört yüz yapraklı bir ağaç ilke olarak okunabilir ama pratikte kimse okumaz. "Karar ağacı kullandık, açıklanabilir" cümlesi, ağacın gerçekten kaç yapraklı olduğu söylenmeden kurulmamalıdır.

Uygulama

Bu çalışmada on başvuruluk küçük bir tabloda kökteki soruyu elle seçecek, sonra tek bir etiketi değiştirip seçimin nasıl devrildiğini göreceksin. Tablodaki başvurular kurgusaldır; kâğıt kalem ya da bir hesap tablosu yeter.

1. Bütün tablonun Gini safsızlığını hesapla: Park ve Bahçeler payının karesini ve Su ve Kanalizasyon payının karesini birden çıkar.
2. "Park" sorusuyla tabloyu ikiye ayır. Her parçanın safsızlığını aynı yoldan bul.
3. İki parçanın safsızlığını, parçadaki başvuru sayısının ona bölümüyle çarpıp topla.
4. Aynı işi "çeşme" sorusu için yap. Hangisi daha düşük çıktı? Kökte o soru durur.
5. Altıncı başvuruya dön. Mahalle çeşmesinin suyu kesikse bu iş Su ve Kanalizasyon'un mu, çeşmenin bakımını yapan Park ve Bahçeler'in mi? Etiketini Park ve Bahçeler yap ve dördüncü adıma kadar her şeyi yeniden hesapla.
6. Yeni kökün altına ağacın ikinci katını kabaca çiz ve ilk ağaçla karşılaştır: hangi başvurular artık başka bir yoldan yaprağa iniyor?

Bulman gereken sayılar şunlar. Bütün tablo sıfır virgül kırk sekiz. "Park" sorusunda parçalar sıfır virgül otuz yedi buçuk ile yaklaşık sıfır virgül yirmi sekiz, tartılmış toplam yaklaşık sıfır virgül otuz iki. "Çeşme" sorusunda yaklaşık sıfır virgül kırk dört ile sıfır virgül kırk bir, toplam yaklaşık sıfır virgül kırk iki; kök "park" olur. Etiket değişince bütün tablo sıfır virgül elli olur, "park" sorusu yaklaşık sıfır virgül kırk ikiye çıkar, "çeşme" sorusu yaklaşık sıfır virgül yirmi dokuza iner ve kök "çeşme" olur. On başvurudan birinin etiketi, ağacın ilk sorusunu değiştirdi. Beşinci adımdaki etiketin tek doğru cevabı yoktur; belediyenin iş bölümüne bakar.

Defter: "İlk soruyu kim seçti" başlıklı sayfaya iki kökü, iki hesabı ve altıncı başvurunun hangi müdürlüğe ait olduğuna dair kendi kararını gerekçesiyle yaz; altına, bir ağacın kökünü değiştirecek kadar tartışmalı bir etiketi bir yerde görüp görmediğini not et.

Hata köşesi

Sorumluluk

Ağacı belediyede kullanmaya karar veren Onur ve belediye bilgi işlemidir; Hakan Bey'in dalları okuyabilmesi bu kararı kolaylaştırır ama onun yerine geçmez. Hangi derinlikte durulacağına, hangi dalların kesileceğine ve "Sayın" gibi bir dalın neden atıldığına dair kararlar ağaçla birlikte bir sayfaya yazılmalıdır. Zarar en kolay, resmî dilekçe diliyle yazan vatandaşa dokunur: masaya gelip dilekçe yazdıran yaşlı bir başvuran, onun yazışma biçimini rastlantıyla öğrenmiş bir dal yüzünden yanlış müdürlükte bekleyebilir. Etiket her değiştiğinde ağaç yeniden kurulur; bu yüzden her yeni sürüm, ayrılmış başvurularla ve bir önceki sürümün dallarıyla karşılaştırılarak doğrulanır ve bu doğrulamanın sorumlusu adıyla kayda geçer.

Kapanış

1. Karar ağacı örnekleri her düğümde safsızlığı en çok düşüren evet-hayır sorusuyla böler; sorular insan tarafından yazılmaz, etiketli örneklerden seçilir.
2. Derinleşen ağaç az örneğe dayanan rastlantıları soruya çevirir; budama, yeni örneklerde doğruluğa katkı yapmayan dalları keserek ağacı hem daha basit hem daha güvenilir kılar.
3. Ağaç okunur ama oynaktır: birkaç etiketin değişmesi kökü değiştirebilir, ve okunan bir dal bir nedeni değil, örneklerdeki bir ayrımı anlatır.

Üç soru

1. Onur'un ağacı "su" düğümünde neden "çeşme" yerine "park" sorusunu seçti?
2. Onur'un iki sayfalık ağacı eğitim başvurularında çok iyiyken ayrılmış elli başvuruda neden budanmış ağaçtan geride kaldı?
3. Hakan Bey öğrenilmiş ağacı okuyabildiği için ona güvenmeye hazır. Ona hangi soruyu sormasını önerirsin?

Yanıtlar

1. Model her aday sorunun bıraktığı iki parçanın safsızlığını büyüklükleriyle tartıp topladı. "Park" sorusu kırk başvuruluk düğümün sıfır virgül kırk ikilik safsızlığını sıfır virgül on üçe, "çeşme" sorusu yalnız sıfır virgül yirmi dokuza indiriyordu; daha arı parçalar bırakan soru seçildi.
2. Ağaç durdurulmadığı için üç başvuruluk köşelerde bile ayırt edici bir kelime buldu ve "Sayın" dalı gibi rastlantıları kural hâline getirdi. Bu dallar eğitim başvurularında doğruydu ama yeni başvurularda karşılığı yoktu. Budama onları kesip yerlerine çoğunluk sınıfını koyunca ağaç sadeleşti ve yeni başvurularda daha iyi çalıştı.
3. Bir dalın hangi ve kaç başvurudan çıktığını, ve etiketler biraz değişince aynı dalın yerinde durup durmadığını sorması gerekir. Okunabilen bir dal, örneklerde bir ayrım olduğunu gösterir; o ayrımın gerçek ve kalıcı olduğunu göstermek için az örneğe dayanan dallara ve farklı etiketlerle kurulan sürümlere bakmak gerekir.

Sonraki derse köprü

Onur'un ağacı on bir etiketin değişmesiyle başka bir sayfaya dönüştü; tek bir ağaç, verideki küçük oynamalara karşı kırılgandır. Ders 5.4, Topluluk yöntemleri, tek bir modele güvenmek yerine çok sayıda zayıf modeli birleştirmeyi konu ediyor: rastgele orman ve gradyan artırma, bu birleştirmenin iki ayrı yolu.