5.5 Karar Kuralları (Decision Rules)

Bir karar kuralı, bir şart (öncül olarak da adlandırılır) ve bir tahmin içeren basit bir IF-THEN ifadesidir. Örneğin: EĞER bugün yağmur yağarsa VE Nisan ayıysa (şart), O ZAMAN yarın yağmur yağacaktır (tahmin). Tek bir karar kuralı veya birkaç kuralın birleşimi, tahminler yapmak için kullanılabilir.

Karar kuralları genel bir yapıyı takip eder: EĞER şartlar sağlanırsa, O ZAMAN belirli bir tahmin yapılır. Karar kuralları muhtemelen en yorumlanabilir tahmin modelleridir. IF-THEN yapısı, doğal dili ve düşünme şeklimizi semantik olarak andırır; tabii ki şartın anlaşılır özelliklerden oluşturulması, şartın uzunluğunun kısa olması (az sayıda özellik=değer çiftinin AND ile birleşmesi) ve çok fazla kuralın olmaması koşuluyla. Programlamada IF-THEN kuralları yazmak çok doğaldır. Makine öğreniminde yeni olan, bu kuralların bir algoritma tarafından öğrenilmesidir.

Bir algoritma kullanarak, bir evin değerini (düşük, orta veya yüksek) tahmin etmek için karar kuralları öğrenildiğini hayal edin. Bu model tarafından öğrenilen bir karar kuralı şöyle olabilir: EĞER bir evin büyüklüğü 100 metrekareden büyükse VE bir bahçesi varsa, O ZAMAN değeri yüksektir. Daha resmi olarak: EĞER büyüklük>100 VE bahçe=1 O ZAMAN değer=yüksek.

Karar kuralını parçalayalım:

büyüklük>100 IF kısmındaki ilk şarttır.
bahçe=1 IF kısmındaki ikinci şarttır.
İki şart, bir ‘AND’ ile birleştirilerek yeni bir şart oluşturur. Kuralın uygulanabilmesi için her iki şartın da doğru olması gerekir.
THEN kısmındaki tahmin, değer=yüksektir.

Bir karar kuralı, şart kısmında en az bir özellik=değer ifadesi kullanır; ancak bir ‘AND’ ile kaç tane eklenebileceği konusunda bir üst sınır yoktur. Bir istisna, hiçbir açık IF bölümü olmayan ve diğer kuralların uygulanmadığı durumlarda geçerli olan varsayılan kuraldır.

Bir karar kuralının yararlılığı genellikle iki sayı ile özetlenir: Destek ve doğruluk.

Bir kuralın desteği veya kapsama alanı: Bir kuralın şartının sağlandığı örneklerin yüzdesine destek denir. Örneğin, ev değerlerini tahmin etmek için büyüklük=büyük VE konum=iyi O ZAMAN değer=yüksek kuralını ele alalım. Diyelim ki 1000 evden 100'ü büyük ve iyi bir konuma sahipse, bu kuralın desteği %10 olur. Tahmin (THEN kısmı), destek hesaplaması için önemli değildir.
Bir kuralın doğruluğu veya güvenilirliği: Bir kuralın, şartı sağlanan örnekler için doğru sınıfı ne kadar iyi tahmin ettiğini ölçer. Örneğin: Büyüklük=büyük VE konum=iyi O ZAMAN değer=yüksek kuralının uygulandığı 100 evin 85'inde değer=yüksek, 14'ünde değer=orta ve 1'inde değer=düşükse, bu kuralın doğruluğu %85tir.

Genellikle doğruluk ve destek arasında bir denge vardır: Şarta daha fazla özellik ekleyerek daha yüksek doğruluk elde edebiliriz, ancak destek azalır.

Bir evin değerini tahmin eden iyi bir sınıflandırıcı oluşturmak için sadece bir kural değil, belki 10 veya 20 kural öğrenmeniz gerekebilir. Bu durumda işler karmaşıklaşabilir ve şu sorunlarla karşılaşabilirsiniz:

Kurallar örtüşebilir: Ya bir evin değerini tahmin etmek istediğimde iki veya daha fazla kural geçerli olursa ve çelişkili tahminler verirse?
Hiçbir kural uygulanamaz: Ya bir evin değerini tahmin etmek istediğimde hiçbir kural geçerli değilse?

Birden fazla kuralı birleştirmek için iki ana strateji vardır: Karar listeleri (sıralı) ve karar kümeleri (sırasız). Her iki strateji de örtüşen kurallar sorununa farklı çözümler getirir.

Karar listesi kurallara bir sıra ekler. Eğer bir örnek için ilk kuralın şartı doğruysa, o kuralın tahmini kullanılır. Eğer değilse, bir sonraki kurala geçilir ve onun uygulanıp uygulanmadığı kontrol edilir. Karar listeleri, yalnızca listedeki ilk geçerli kuralın tahminini döndürerek örtüşen kurallar sorununu çözer.
Karar kümesi, kuralların bir demokrasisine benzer, ancak bazı kuralların oy gücü daha yüksek olabilir. Bir kümede kurallar ya karşılıklı olarak dışlayıcıdır ya da çakışmaları çözmek için bir strateji (örneğin çoğunluk oylaması) kullanılır. Bu strateji, bireysel kural doğrulukları veya diğer kalite ölçütleriyle ağırlıklandırılabilir. Ancak, birden fazla kuralın geçerli olması yorumlanabilirliği potansiyel olarak zorlaştırır.

Hem karar listeleri hem de kümeleri, hiçbir kuralın bir örneğe uygulanamaması sorunuyla karşılaşabilir. Bu durum, bir varsayılan kural eklenerek çözülebilir. Varsayılan kural, diğer kuralların kapsamadığı veri noktalarının en sık görülen sınıfını tahmin eder. Eğer bir kural kümesi veya listesi tüm özellik uzayını kapsıyorsa, buna tükenmiş (exhaustive) denir. Varsayılan bir kural ekleyerek, bir küme veya liste otomatik olarak tükenmiş hale gelir.

Veriden kural öğrenmenin birçok yolu vardır ve bu kitap bunların hepsini kapsamak için yazılmadı. Bu bölüm size bunlardan üçünü gösterecek. Algoritmalar, kural öğrenme için genel fikirlerin geniş bir yelpazesini kapsamak üzere seçildi, bu nedenle her biri oldukça farklı yaklaşımları temsil eder.

OneR tek bir özelliğe dayalı kurallar öğrenir. OneR, basitliği, yorumlanabilirliği ve bir karşılaştırma ölçütü olarak kullanılmasıyla bilinir.
Sıralı kapsama (Sequential covering), iteratif olarak kurallar öğrenen ve yeni kuralla kapsanan veri noktalarını kaldıran genel bir prosedürdür. Bu prosedür, birçok kural öğrenme algoritması tarafından kullanılır.
Bayesyen Kural Listeleri, önceden çıkarılmış sık desenleri Bayes istatistiklerini kullanarak bir karar listesine dönüştürür. Önceden çıkarılmış desenlerin kullanılması, birçok kural öğrenme algoritması tarafından yaygın olarak kullanılan bir yaklaşımdır.

En basit yaklaşımla başlayalım: Kuralları tek bir özellikten öğrenmek.

5.5.1. Tek Bir Öznitelikten Kurallar Öğrenme (OneR)

Holte (1993) tarafından önerilen OneR algoritması, en basit kural çıkarma algoritmalarından biridir. Tüm özellikler arasından OneR, ilgilenilen sonuca dair en fazla bilgi taşıyan özelliği seçer ve bu özellikten karar kuralları oluşturur.

OneR adı "One Rule" anlamına gelse de, algoritma aslında birden fazla kural oluşturur: Seçilen en iyi özelliğin her bir benzersiz değeri için bir kural oluşturur. Daha doğru bir isim "Tek Özellik Kuralları" (OneFeatureRules) olabilir.

Algoritma basit ve hızlıdır: Sürekli özellikleri uygun aralıklar seçerek ayrıklaştırın. Her özellik için: Özellik değerleri ve (kategorik) sonuç arasında bir çapraz tablo oluşturun. Özelliğin her değeri için, bu değeri taşıyan örneklerin en sık görülen sınıfını tahmin eden bir kural oluşturun (bu bilgi çapraz tablodan okunabilir). Özellik için kuralların toplam hatasını hesaplayın. Toplam hatası en küçük olan özelliği seçin. OneR her zaman veri setindeki tüm örnekleri kapsar, çünkü seçilen özelliğin tüm seviyelerini kullanır. Eksik değerler, ek bir özellik değeri olarak ele alınabilir veya önceden doldurulabilir.

Bir OneR modeli, yalnızca tek bir bölünmesi olan bir karar ağacıdır. Bu bölünme, CART'ta olduğu gibi ikili olmak zorunda değildir; benzersiz özellik değerlerinin sayısına bağlıdır.

Bir örnek üzerinden OneR'ın en iyi özelliği nasıl seçtiğine bakalım. Aşağıdaki tablo, evlerle ilgili yapay bir veri setini göstermektedir. Bu veri setinde evin değeri, konumu, büyüklüğü ve evcil hayvanlara izin verilip verilmediği bilgisi yer almaktadır. Amacımız, bir evin değerini tahmin etmek için basit bir model öğrenmektir.

location

size

pets

value

good

small

yes

high

good

big

high

good

big

high

bad

medium

good

medium

only cats

medium

good

small

only cats

medium

bad

medium

yes

medium

bad

small

yes

low

bad

medium

yes

low

bad

small

low

OneR her öznitelik ve çıktı arasında çapraz tablolar oluşturur.

value=low

value=medium

value=high

size=big

size=medium

size=small

value=low

value=medium

value=high

pets=no

pets=only cats

pets=yes

Her bir özellik için tabloyu satır satır inceleriz: Her özellik değeri bir kuralın IF kısmını oluşturur; bu özellik değerine sahip örnekler için en sık görülen sınıf tahmin edilen değer olur, yani kuralın THEN kısmını oluşturur. Örneğin, size (büyüklük) özelliği küçük, orta ve büyük seviyelerine sahip olduğunda üç kural oluşturur. Her özellik için oluşturulan kuralların toplam hata oranını hesaplarız, bu hata oranı yapılan hataların toplamıdır.

Location (konum) özelliğinin olası değerleri bad (kötü) ve good (iyi) şeklindedir. Kötü konumdaki evler için en sık görülen değer low (düşük) olduğundan bu değeri tahmin ettiğimizde iki hata yaparız, çünkü iki evin değeri medium (orta)'dır. İyi konumdaki evler için tahmin edilen değer high (yüksek) olur ve yine iki hata yaparız, çünkü iki evin değeri medium (orta)'dır. Location özelliğini kullanarak yaptığımız hata oranı 4/10'dur, size özelliği için bu oran 3/10'dur ve pet özelliği için hata oranı 4/10'dur. En düşük hata oranını üreten size (büyüklük) özelliği, nihai OneR modeli için kullanılacaktır:

IF size=small THEN value=low
IF size=medium THEN value=medium
IF size=big THEN value=high

OneR, çok sayıda olası seviyeye sahip özellikleri tercih eder, çünkü bu tür özellikler hedef değişkeni daha kolay aşırı öğrenebilir (overfitting). Sadece gürültü içeren ve hiçbir sinyal taşımayan bir veri setini hayal edin; bu durumda tüm özellikler rastgele değerler alır ve hedef değişken için tahmin gücü taşımaz. Bazı özelliklerin daha fazla seviyesi varken, diğerleri daha az seviyeye sahiptir. Daha fazla seviyeye sahip olan özellikler hedefi daha kolay aşırı öğrenebilir. Eğer bir özellik, veri setindeki her bir örnek için ayrı bir seviyeye sahipse, tüm eğitim veri setini mükemmel bir şekilde tahmin eder. Bu durumu çözmek için veri setini eğitim ve doğrulama olarak ikiye ayırabiliriz, kuralları eğitim verisi üzerinde öğrenir ve özelliği seçmek için toplam hatayı doğrulama setinde değerlendiririz.

Beraberlik de başka bir sorundur, yani iki özellik aynı toplam hata oranını verdiğinde ne yapılacağıdır. OneR, beraberlik durumunu ya en düşük hataya sahip olan ilk özelliği seçerek ya da khi-kare testi p-değeri en düşük olan özelliği seçerek çözer.

Örnek

Gerçek bir veri seti ile OneR algoritmasını deneyelim. Rahim ağzı kanseri sınıflandırma görevini test etmek için OneR algoritmasını kullanacağız. Tüm sürekli giriş özellikleri 5 eşit çeyrek (quantile) aralığına ayrıklaştırılmıştır. Oluşturulan kurallar aşağıdaki gibidir:

Age

prediction

(12.9,27.2]

Healthy

(27.2,41.4]

Healthy

(41.4,55.6]

Healthy

(55.6,69.8]

Healthy

(69.8,84.1]

Healthy

Age (Yaş) özelliği, OneR tarafından en iyi tahmin edici özellik olarak seçilmiştir. Kanser nadir bir durum olduğundan, her kural için çoğunluk sınıfı ve dolayısıyla tahmin edilen etiket her zaman Healthy (Sağlıklı) olmaktadır, bu da oldukça yararsızdır. Bu dengesiz durumda etiket tahminini kullanmak mantıklı değildir. Bunun yerine, ‘Age’ (Yaş) aralıkları ile Kanser/Sağlıklı durumu arasındaki çapraz tablo ve kadınlar arasında kanser oranı yüzdesi daha bilgilendiricidir:

# Cancer

# Healthy

P(Cancer)

Age=(12.9,27.2]

477

0.05

Age=(27.2,41.4]

290

0.08

Age=(41.4,55.6]

0.11

Age=(55.6,69.8]

0.00

Age=(69.8,84.1]

0.00

Ancak bir şeyi yorumlamaya başlamadan önce: Her özellik ve her değer için tahmin Healthy (Sağlıklı) olduğu için toplam hata oranı tüm özellikler için aynıdır. Toplam hatalardaki eşitlikler, varsayılan olarak en düşük hata oranına sahip özelliklerden ilki kullanılarak çözülür (burada tüm özelliklerin hata oranı 55/858’dir), bu da Age (Yaş) özelliği olur.

OneR, regresyon görevlerini desteklemez. Ancak, sürekli bir çıktıyı aralıklara ayırarak bir regresyon görevini sınıflandırma görevine dönüştürebiliriz. Bu yöntemi, kiralanan bisiklet sayısını tahmin etmek için kullanıyoruz ve bisiklet sayılarını dört çeyrek dilime ayırıyoruz (%0-25, %25-50, %50-75 ve %75-100). Aşağıdaki tablo, OneR modelini uyguladıktan sonra seçilen özelliği göstermektedir:

mnth

prediction

JAN

[22,3152]

FEB

[22,3152]

MAR

[22,3152]

APR

(3152,4548]

MAY

(5956,8714]

JUN

(4548,5956]

JUL

(5956,8714]

AUG

(5956,8714]

SEP

(5956,8714]

OCT

(5956,8714]

NOV

(3152,4548]

DEC

[22,3152]

Boş bir kural listesi (rlist) ile başlayın.
Bir kural (r) öğrenin.
Kural listesi belirli bir kalite eşiğinin altında olduğu sürece (veya pozitif örnekler henüz kapsanmadığı sürece):
- Kuralı (r) kural listesine (rlist) ekleyin.
- Kural (r) tarafından kapsanan tüm veri noktalarını çıkarın.
- Kalan veri üzerinde başka bir kural öğrenin.
Karar listesini döndürün.

Elimizde, verilerin bir kısmını kapsayan bir kural oluşturabilen bir algoritma olduğunu varsayalım. İki sınıf (bir pozitif, bir negatif) için sequential covering algoritması şu şekilde çalışır:

Temel fikir oldukça basittir: Öncelikle, verilerin bir kısmına uyan iyi bir kural bulun. Kuralla kapsanan tüm veri noktalarını çıkarın. Bir veri noktası, koşullar sağlandığında (doğru sınıflandırılsa da yanlış sınıflandırılsa da) kapsanmış sayılır. Kalan veri noktalarıyla tekrar kural öğrenme ve kapsanan noktaları çıkarma işlemini tekrarlayın. Bu işlem, artık veri kalmayana ya da başka bir durdurma koşulu sağlanana kadar devam eder. Sonuç, bir karar listesi olur. Bu tekrarlı kural öğrenme ve kapsanan veri noktalarını çıkarma yaklaşımına "separate-and-conquer" (ayır ve fethet) denir.

Sequential covering (sıralı kapsama), veri kümesini kurallar listesiyle (veya setiyle) adım adım kapsayan genel bir prosedürdür. Birçok kural öğrenme algoritması, sequential covering algoritmasının varyasyonlarıdır. Bu bölümde temel tarifi anlatıyor ve örnekler için RIPPER algoritmasını (sequential covering’in bir varyasyonu) kullanıyoruz.

5.5.2 Sequential Covering

Şimdi, basit OneR algoritmasından, daha karmaşık koşullardan (birden fazla özelliği içeren) oluşan kurallarla çalışan bir prosedüre geçiyoruz: Sequential Covering (Sıralı Kapsama).

Seçilen özellik month (ay) oldu. Ay özelliği (sürpriz!) 12 seviyeye sahiptir, bu da çoğu diğer özellikten daha fazladır. Bu durum aşırı öğrenme (overfitting) riskini artırabilir. Daha iyimser bir açıdan bakacak olursak, ay özelliği mevsimsel trendleri ele alabilir (örneğin, kış aylarında daha az kiralanan bisiklet) ve tahminler mantıklı görünüyor.

Örneğin: Evlerin değerlerini boyut, konum ve evcil hayvanların izinli olup olmamasına göre tahmin etmek için bir görevimiz ve veri kümesimiz var. İlk öğrenilen kural şu olabilir: Eğer boyut=büyük ve konum=iyi ise, değer=yüksek. Daha sonra iyi bir konumdaki büyük evleri veri kümesinden çıkarırız. Kalan veri ile bir sonraki kuralı öğreniriz. Belki de: Eğer konum=iyi ise, değer=orta. Dikkat edin, bu kural yalnızca iyi konumda olan büyük evler çıkarıldıktan sonra öğrenildiği için, yalnızca iyi konumdaki orta ve küçük evleri kapsar.

Çok sınıflı görevlerde, yaklaşımın biraz değiştirilmesi gerekir. İlk olarak, sınıflar azalan sıklık sırasına göre sıralanır. Sequential covering algoritması en az yaygın sınıfla başlar, bu sınıf için bir kural öğrenir, kapsanan tüm örnekleri çıkarır ve ardından ikinci en az yaygın sınıfa geçer. Mevcut sınıf her zaman pozitif sınıf olarak ele alınır ve daha yaygın olan tüm sınıflar negatif sınıf olarak birleştirilir. Son sınıf default rule (varsayılan kural) olarak kabul edilir. Bu yöntem, sınıflandırmada birine karşı tümü (one-versus-all) stratejisi olarak da bilinir.

Tek bir kural nasıl öğrenilir?

OneR algoritması burada işe yaramaz, çünkü her zaman tüm özellik uzayını kapsar. Ancak, başka birçok seçenek vardır. Bir olasılık, bir karar ağacından beam search (ışın arama) ile tek bir kural öğrenmektir:

Bir karar ağacı öğrenin (CART veya başka bir ağaç öğrenme algoritması ile).
Kök düğümden başlayarak en saf düğümü (örneğin, en düşük yanlış sınıflandırma oranına sahip olan düğüm) seçerek ilerleyin.
Terminal düğümün çoğunluk sınıfı, kuralın tahmini olarak kullanılır; bu düğüme giden yol ise kuralın koşulu olarak kullanılır.

Aşağıdaki şekil, bir ağacın içinde beam search (ışın arama) yöntemini göstermektedir:

Servikal kanser sınıflandırma görevi: RIPPER bu görevde herhangi bir kural bulamamıştır.
Bisiklet sayısını tahmin etme (regresyon görevi): Bisiklet sayıları tahmin edilirken RIPPER bazı kurallar bulmuştur. Ancak, RIPPER yalnızca sınıflandırma görevlerinde çalıştığı için bisiklet sayılarının kategorik bir çıktıya dönüştürülmesi gerekmiştir. Bu dönüşümü, bisiklet sayılarını çeyreklik aralıklarına bölerken gerçekleştirdim. Örneğin, (4548, 5956) aralığı, 4548 ile 5956 arasında tahmin edilen bisiklet sayılarını kapsar. Aşağıdaki tablo, öğrenilen kuralların oluşturduğu karar listesini göstermektedir.

Aşağıdaki örneklerde RIPPER algoritması kullanılacaktır.

Örnekler

Cohen (1995) tarafından önerilen RIPPER (Repeated Incremental Pruning to Produce Error Reduction), Sequential Covering algoritmasının bir varyantıdır. RIPPER biraz daha sofistike olup karar listesini (veya setini) optimize etmek için bir son işlem aşaması (rule pruning) kullanır. RIPPER, sıralı (ordered) veya sırasız (unordered) modda çalışabilir ve bir karar listesi veya karar seti oluşturabilir.

Bir kural öğrenmek, tüm olası kuralların oluşturduğu arama uzayında bir arama problemidir. Aramanın amacı, belirli kriterlere göre en iyi kuralı bulmaktır. Bunun için farklı arama stratejileri bulunmaktadır: tepe tırmanma (hill-climbing), ışın arama (beam search), tükeniş araması (exhaustive search), en-öncelikli arama (best-first search), sıralı arama (ordered search), stokastik arama (stochastic search), yukarıdan-aşağıya (top-down search), aşağıdan-yukarıya (bottom-up search) ve daha fazlası.

rules

(temp >= 16) and (days_since_2011 <= 437) and (weathersit = GOOD) and (temp <= 24) and (days_since_2011 >= 131) => cnt=(4548,5956]

(temp <= 13) and (days_since_2011 <= 111) => cnt=[22,3152]

(temp <= 4) and (workingday = NO WORKING DAY) => cnt=[22,3152]

(season = WINTER) and (days_since_2011 <= 368) => cnt=[22,3152]

(hum >= 72) and (windspeed >= 16) and (days_since_2011 <= 381) and (temp <= 17) => cnt=[22,3152]

(temp <= 6) and (weathersit = MISTY) => cnt=[22,3152]

(hum >= 91) => cnt=[22,3152]

(mnth = NOV) and (days_since_2011 >= 327) => cnt=[22,3152]

(days_since_2011 >= 438) and (weathersit = GOOD) and (hum >= 51) => cnt=(5956,8714]

(days_since_2011 >= 441) and (hum <= 73) and (temp >= 15) => cnt=(5956,8714]

(days_since_2011 >= 441) and (windspeed <= 10) => cnt=(5956,8714]

(days_since_2011 >= 455) and (hum <= 40) => cnt=(5956,8714]

=> cnt=(3152,4548]

Yorumlama oldukça basittir: Eğer koşullar sağlanıyorsa, sağ tarafta belirtilen aralık bisiklet sayısı için tahmin edilir. Son kural, diğer hiçbir kuralın uygulanmadığı durumlarda geçerli olan varsayılan kuraldır. Yeni bir örneği tahmin etmek için listenin en üstünden başlar ve bir kuralın geçerli olup olmadığını kontrol edersiniz. Eğer bir koşul eşleşirse, o kuralın sağ tarafındaki değer bu örnek için tahmin olur. Varsayılan kural sayesinde her zaman bir tahmin yapılabilir.

5.5.3 Bayesian Rule Lists

Bu bölümde, karar listesi oluşturmak için kullanılan farklı bir yaklaşımı göstereceğim. Bu yaklaşım şu genel tariften oluşur:

Verilerden koşul olarak kullanılabilecek sık desenleri önceden çıkarın.
Önceden çıkarılmış kuralların bir seçkisinden bir karar listesi öğrenin.

Bu tarife dayalı özel bir yaklaşım, Bayesian Rule Lists (Letham ve diğerleri, 2015) veya kısaca BRL olarak adlandırılır. BRL, FP-tree algoritması (Borgelt 2005) kullanılarak önceden çıkarılmış sık desenlerden Bayesian istatistikleri kullanarak karar listeleri öğrenir.

Ama önce BRL’nin ilk adımı olan ön madencilik ile yavaşça başlayalım.

Sık Desenlerin Ön Madenciliği

Bir sık desen, özellik değerlerinin sıkça (birlikte) tekrar eden durumlarıdır. BRL algoritması için ön işleme adımı olarak, özellikleri (bu adımda hedef değişkeni kullanmaya gerek yoktur) kullanır ve bunlardan sıkça meydana gelen desenleri çıkarır. Bir desen, tek bir özellik değeri (örneğin, size=medium) veya birden fazla özellik değerinin birleşimi (size=medium AND location=bad) olabilir.

Bir desenin sıklığı, veri setindeki destek oranı (support) ile ölçülür: $\operatorname{Support}\left(x_j=A\right)=\frac{1}{n} \sum_{i=1}^n I\left(x_j^{(i)}=A\right)$

Sık desenleri bulmak için Apriori veya FP-Growth gibi birçok algoritma vardır. Hangi algoritmayı kullandığınız önemli değildir, sadece desenlerin bulunma hızında fark yaratır; elde edilen desenler ise her zaman aynıdır.

Apriori algoritmasının sık desenleri nasıl bulduğuna dair genel bir fikir vereyim. Aslında Apriori algoritması iki bölümden oluşur: İlk bölüm sık desenleri bulur, ikinci bölüm ise bu desenlerden ilişki kuralları oluşturur. BRL algoritması için, Apriori’nin yalnızca ilk bölümünde oluşturulan sık desenlerle ilgileniyoruz.

Sık Desenlerin Apriori ile Bulunması

İlk Adım: Apriori algoritması, kullanıcı tarafından belirlenen minimum destek değerinden daha yüksek bir desteğe sahip olan tüm özellik değerleriyle başlar. Örneğin, minimum destek %10 olarak belirlenmişse ve sadece %5 oranında ev size=big değerine sahipse, bu değer kaldırılır ve yalnızca size=medium ve size=small desen olarak kalır. Bu, evlerin veri setinden çıkarıldığı anlamına gelmez; yalnızca size=big sık desen olarak geri döndürülmez.
İkinci Adım: Tek bir özellik değerine sahip sık desenlere dayanarak, Apriori algoritması iteratif olarak daha yüksek sırada kombinasyonlar oluşturmaya çalışır. Desenler, özellik=değer ifadelerini bir AND ile birleştirerek oluşturulur (örneğin, size=medium AND location=bad). Minimum destek değerinin altındaki desenler elenir. Sonuçta elimizde tüm sık desenler olur. Bir sık desenin tüm alt kümeleri de sık desen olarak kabul edilir; bu durum Apriori özelliği olarak adlandırılır.

Apriori Özelliği şu şekilde anlaşılabilir: Bir desenden bir koşul kaldırıldığında, geri kalan desen daha fazla ya da aynı sayıda veri noktasını kapsayabilir, ancak daha azını kapsayamaz. Örneğin, evlerin %20’si size=medium AND location=good ise, yalnızca size=medium olan evlerin desteği %20 veya daha fazladır. Apriori özelliği, incelenmesi gereken desen sayısını azaltmak için kullanılır. Yalnızca sık desenler durumunda daha yüksek sıradaki desenleri kontrol etmemiz gerekir.

Bayesian Rule Lists ile Kuralların Öğrenilmesi

Hedef: BRL algoritması, önceden çıkarılan koşullardan bir seçim kullanarak doğru bir karar listesi öğrenmek, aynı zamanda az sayıda kurala ve kısa koşullara öncelik vermektir. BRL, bu hedefi şu şekilde gerçekleştirir:

Kuralların uzunluğu ve sayısı için önsel dağılımlar tanımlar (tercihen kısa kurallar ve kısa liste).

Sonuç: Bu öncüller ve veriye ne kadar iyi uyduğu dikkate alındığında, karar listesinin olasılığını hesaplayan bir art dağılımı (posterior distribution) oluşturulur. Amacımız, bu art dağılıma göre en yüksek olasılığı olan listeyi bulmaktır.

BRL Tarifi:

Başlangıç: Rastgele olarak önsel dağılımdan bir başlangıç kararı listesi oluşturulur.
İteratif Değişiklik: Liste iteratif olarak değiştirilir (kurallar eklenir, değiştirilir veya kaldırılır) ve sonuçta oluşan listelerin art dağılıma uygun olduğundan emin olunur.
Seçim: Art dağılıma göre en yüksek olasılığa sahip liste seçilir.

Algoritmaya yakından bakalım. Algoritma, FP-Growth algoritmasını kullanarak özellik değeri desenlerini önceden çıkararak başlar. BRL, hedefin dağılımı ve bu dağılımı tanımlayan parametrelerin dağılımı hakkında bir dizi varsayımda bulunur. (Bu noktada Bayesian istatistikleri devreye girer.) Eğer Bayesian istatistiklerine aşina değilseniz, ayrıntılara çok takılmayın. Bilmeniz gereken: Bayesian yaklaşımı, mevcut bilgileri veya gereklilikleri (önsel dağılımlar) veriye uydurmanın bir yoludur. Karar listeleri durumunda, önsel varsayımlar karar listelerinin kısa olmasını teşvik eder.

Hedef, posterior dağılımdan karar listeleri d örneklemektir.

\underbrace{p(d \mid x, y, A, \alpha, \lambda, \eta)}_{\text {posteriori }} \propto \underbrace{p(y \mid x, d, \alpha)}_{\text {likelihood }} \cdot \underbrace{p(d \mid A, \lambda, \eta)}_{\text {priori }}

Bu eşitlikte d karar listesi, x öznitelikler, y hedef, A önceden çıkarılan koşullar kümesi, λ karar listelerinin önceden beklenen uzunluğunu, η bir kuraldaki koşulların önceden beklenen sayısını, α pozitif ve negatif sınıflar için önsel pseudo-sayıyı ifade eder. (genellikle en iyi değer olarak ( 1 , 1 ) (1,1) alınır)

$p(d|x,y,A,\alpha,\lambda,\eta)$

Bir karar listesinin gözlemlenen verilere ve öncül varsayımlara dayanarak ne kadar olası olduğunu ölçer. Bu, karar listesi ve veri göz önüne alındığında sonucun 𝑦 olasılığı ile öncül varsayımlar ve önceden belirlenmiş koşullara göre listenin olasılığının çarpımına orantılıdır.

$p(d|A,\lambda,\eta)$

Bu eşitlik, listedeki kural sayısı için kısıtlanmış bir Poisson dağılımını (parametre λ ) ve kuralların koşullarındaki özellik değerlerinin sayısı için kısıtlanmış bir Poisson dağılımını (parametre η) çarpımsal olarak birleştirir.

Bir karar listesi, sonucu (y) iyi bir şekilde açıklıyorsa ve öncül varsayımlara göre de olasıysa yüksek bir posterior olasılığa sahiptir.

Bayesçi istatistiklerde tahmin yapmak her zaman biraz zordur, çünkü genellikle doğru cevabı doğrudan hesaplayamayız. Bunun yerine, adaylar seçmek, bunları değerlendirmek ve posterior tahminlerimizi Markov zinciri Monte Carlo (MCMC) yöntemiyle güncellemek zorundayız. Karar listeleri için bu daha da zor hale gelir, çünkü karar listelerinin dağılımından seçim yapmak gerekir. BRL (Bayesian Rule Lists) yazarları, önce başlangıçta bir karar listesi oluşturmayı ve ardından bu listeyi yinelemeli olarak değiştirmeyi önerir. Bu, karar listelerinin posterior dağılımından örnekler elde etmek (karar listelerinin bir Markov zincirini oluşturmak) amacıyla yapılır. Ancak sonuçlar başlangıç karar listesine bağlı olabileceğinden, bu prosedürün farklı başlangıçlarla tekrarlanması önerilir. Yazılım uygulamasında varsayılan tekrar sayısı 10’dur. Aşağıdaki yöntem, bir başlangıç karar listesinin nasıl oluşturulacağını açıklamaktadır:

FP-Growth algoritmasıyla örüntüler önceden belirlenir.
Liste uzunluğu parametresi mmm, kısıtlanmış bir Poisson dağılımından örneklenir.
Varsayılan kural için: Hedef değerinin (yani başka hiçbir kuralın geçerli olmadığı durumda uygulanacak olan kuralın) Dirichlet-Multinomial dağılım parametresi θ0θ_0θ0 örneklenir.
Karar listesi kuralı j=1,...,mj = 1, ..., mj=1,...,m için şunlar yapılır:
- Kural jjj'nin uzunluk parametresi lll (koşul sayısı) örneklenir.
- Önceden belirlenen koşullardan ljl_jlj uzunluğunda bir koşul örneklenir.
- THEN kısmı (yani kurala göre hedef sonucun dağılımı) için Dirichlet-Multinomial dağılım parametresi örneklenir.
Veri kümesindeki her bir gözlem için:
- İlk olarak (yukarıdan aşağıya doğru) uygulanan kural bulunur.
- Geçerli kuralın önerdiği olasılık dağılımından (Binomial) tahmin edilen sonuç örneklenir.

Bir başlangıç örneği oluşturulduktan sonraki adım, posterior karar listesi dağılımından çok sayıda örnek elde etmek için bu ilk örnekten başlayarak yeni listeler üretmektir.

Yeni karar listeleri, başlangıç listesinden başlayarak rastgele şekilde bir kuralı listenin başka bir konumuna taşımak, önceden belirlenmiş koşullardan bir kural eklemek veya mevcut bir kuralı silmek yoluyla oluşturulur. Hangi kuralın değiştirileceği, ekleneceği veya silineceği rastgele seçilir. Her adımda algoritma, karar listesinin posterior olasılığını (doğruluk ve kısalık karışımı) değerlendirir. Metropolis-Hastings algoritması, yüksek posterior olasılığına sahip karar listelerinin örneklenmesini sağlar. Bu prosedür, karar listesi dağılımından birçok örnek elde edilmesini sağlar. BRL algoritması, en yüksek posterior olasılığa sahip örneklerden birini seçerek nihai karar listesini belirler.

Örnek:

Teori kısmı burada sona eriyor, şimdi BRL yönteminin uygulamadaki halini görelim. Bu örneklerde, Yang ve arkadaşlarının (2017) önerdiği Scalable Bayesian Rule Lists (SBRL) adlı BRL’nin daha hızlı bir varyantı kullanılmıştır. SBRL algoritmasını kullanarak rahim ağzı kanseri riskini tahmin etmeyi amaçlıyoruz. Öncelikle, SBRL algoritmasının çalışabilmesi için tüm giriş özelliklerini ayrıklaştırmam gerekti. Bunun için, sürekli özellikleri değerlerin frekanslarına göre çeyrek dilimler (quantiles) temelinde sınıflandırdım.

Sonuç olarak aşağıdaki kuralları elde ettik:

rules

If {STDs=1} (rule[259]) then positive probability = 0.16049383

else if {Hormonal.Contraceptives..years.=[0,10)} (rule[82]) then positive probability = 0.04685408

else (default rule) then positive probability = 0.27777778

Unutmayın ki oldukça mantıklı kurallar elde ettik; çünkü THEN kısmındaki tahmin, sınıf sonucunu değil, kanser için öngörülen olasılığı ifade ediyor.

Koşullar, FP-Growth algoritmasıyla önceden belirlenmiş örüntülerden seçilmiştir. Aşağıdaki tablo, SBRL algoritmasının bir karar listesi oluştururken seçebileceği koşullar havuzunu göstermektedir. Kullanıcı olarak bir koşuldaki maksimum özellik değeri sayısını iki ile sınırladım. İşte on örüntüden oluşan bir örnek:

pre-mined conditions

Num.of.pregnancies=[3.67, 7.33)

IUD=0, STDs=1

Number.of.sexual.partners=[1, 10), STDs..Time.since.last.diagnosis=[1, 8)

First.sexual.intercourse=[10, 17.3), STDs=0

Smokes=1, IUD..years.=[0, 6.33)

Hormonal.Contraceptives..years.=[10, 20), STDs..Number.of.diagnosis=[0, 1)

Age=[13, 36.7)

Hormonal.Contraceptives=1, STDs..Number.of.diagnosis=[0, 1)

Number.of.sexual.partners=[1, 10), STDs..number.=[0, 1.33)

STDs..number.=[1.33, 2.67), STDs..Time.since.first.diagnosis=[1, 8)

Sonraki adımda, SBRL algoritmasını bisiklet kiralama tahmini görevine uyguluyoruz. Bu yalnızca, bisiklet sayısını tahmin etmeye yönelik regresyon probleminin ikili bir sınıflandırma görevine dönüştürülmesi durumunda çalışır. Bu sınıflandırma görevini, gün içinde kiralanan bisiklet sayısı 4000’i aşıyorsa etiketi 1, aksi takdirde 0 olacak şekilde keyfi olarak oluşturdum.

SBRL tarafından öğrenilen karar listesi şu şekildedir:

rules

If {yr=2011,temp=[-5.22,7.35)} (rule[718]) then positive probability = 0.01041667

else if {yr=2012,temp=[7.35,19.9)} (rule[823]) then positive probability = 0.88125000

else if {yr=2012,temp=[19.9,32.5]} (rule[816]) then positive probability = 0.99253731

else if {season=SPRING} (rule[351]) then positive probability = 0.06410256

else if {temp=[7.35,19.9)} (rule[489]) then positive probability = 0.44444444

else (default rule) then positive probability = 0.79746835

2012 yılında sıcaklığın 17 santigrat derece olduğu bir gün için, günlük bisiklet kiralama sayısının 4000’i aşma olasılığını tahmin etmek için SBRL algoritmasını kullandık. İlk kural uygulanamaz, çünkü yalnızca 2011 yılına ait günler için geçerlidir. İkinci kural ise geçerlidir, çünkü gün 2012 yılına aittir ve 17 derece, [7.35, 19.9) aralığına düşer. Bu durumda, 4000’den fazla bisiklet kiralanma olasılığı %88 olarak tahmin edilmiştir.

5.5.4 Avantajlar

Bu bölüm, genel olarak EĞER-SONRA (IF-THEN) kurallarının avantajlarını tartışır:

IF-THEN kuralları kolay anlaşılır ve yorumlanabilir. Muhtemelen en anlaşılır modellerdir. Ancak bu yalnızca kural sayısının az, koşulların kısa (örneğin, maksimum 3 koşul) ve kuralların bir karar listesi veya çakışmayan bir kural kümesi şeklinde düzenlenmesi durumunda geçerlidir.

Karar kuralları, karar ağaçları kadar ifade gücüne sahip olabilir, ancak daha kompakt bir yapı sunar. Karar ağaçları genellikle yinelenen alt ağaçlar içerir; bu, sol ve sağ alt düğümlerde aynı yapıya sahip bölünmelerin olması durumunda görülür.

IF-THEN kuralları ile tahmin yapmak hızlıdır; hangi kuralların uygulanacağını belirlemek için yalnızca birkaç ikili ifade kontrol edilir.

Giriş özelliklerine yapılan monoton dönüşümlere karşı dayanıklıdır; yalnızca koşullardaki eşik değişir. Aykırı değerlere karşı da dayanıklıdır, çünkü yalnızca bir koşulun geçerli olup olmaması önemlidir.

IF-THEN kuralları genellikle az sayıda özelliği içeren seyrek modeller üretir. Yalnızca model için önemli olan özellikleri seçer. Örneğin, doğrusal bir model varsayılan olarak her giriş özelliğine bir ağırlık atar, ancak IF-THEN kuralları alakasız özellikleri basitçe göz ardı edebilir.

OneR gibi basit kurallar, daha karmaşık algoritmalar için temel olarak kullanılabilir.

5.5.5 Dezavantajlar

Bu bölüm, genel olarak EĞER-SONRA (IF-THEN) kurallarının dezavantajlarına odaklanır:

IF-THEN kurallarıyla ilgili araştırmalar ve literatür genellikle sınıflandırmaya odaklanır; regresyon problemleri neredeyse tamamen göz ardı edilir. Sürekli bir hedef değişkeni aralıklara bölüp sınıflandırma problemine dönüştürebilirsiniz, ancak bu bilgi kaybına yol açar. Genel olarak, hem regresyon hem de sınıflandırma için kullanılabilecek yaklaşımlar daha caziptir.

Genellikle özelliklerin kategorik olması gerekir. Bu, sayısal özelliklerin kategorilere ayrılması gerektiği anlamına gelir. Sürekli bir özelliği aralıklara bölmenin birçok yolu vardır, ancak bu kolay bir işlem değildir ve net cevaplar olmayan birçok soruyu beraberinde getirir. Özellik kaç aralığa bölünmelidir? Bölme kriteri nedir: Sabit aralık uzunlukları, çeyrek dilimler veya başka bir şey mi? Bu, genellikle göz ardı edilen, ancak karmaşık bir sorundur.

Eski kural öğrenme algoritmalarının çoğu aşırı öğrenmeye yatkındır. Örneğin; OneR yalnızca bir özelliği kullanabildiği için sınırlıdır (özellik çok fazla seviyeye sahipse veya birçok özellik varsa problem oluşabilir). RIPPER budama işlemi yapar. Bayesian Rule Lists, karar listelerine ön dağılım uygular.

Karar kuralları, özellikler ile çıktı arasındaki doğrusal ilişkileri ifade etmede başarısızdır. Bu, karar ağaçlarıyla ortak bir sorundur. Karar ağaçları ve kurallar, yalnızca adım benzeri tahmin fonksiyonları üretebilir; tahminlerdeki değişiklikler her zaman ayrık adımlar halinde olur, hiçbir zaman düzgün eğriler şeklinde olmaz. Bu sorun, girdilerin kategorik olması gerektiği durumla ilişkilidir. Karar ağaçlarında bu kategorileştirme, bölünme işlemleriyle dolaylı olarak yapılır.

5.5.6 Yazılım ve Alternatifler

OneR, R’daki OneR paketinde uygulanmıştır ve bu kitapta verilen örneklerde kullanılmıştır. Ayrıca, Weka makine öğrenimi kütüphanesinde uygulanmıştır ve Java, R ve Python için mevcuttur. RIPPER, Weka’da da uygulanmıştır. Örnekler için, RWeka paketindeki JRIP’in R uygulamasını kullandım. SBRL, bir R paketi olarak (örneklerde kullandım), Python veya C uygulaması olarak mevcuttur. Ayrıca, imodels paketini öneririm. Bu Python paketi, scikit-learn arayüzüyle birlikte Bayesian kural listeleri, CORELS, OneR, greedy kural listeleri ve daha fazlasını uygular. Diğer karar kural setlerini ve listelerini öğrenme alternatiflerini burada listelemeye çalışmayacağım, ancak bazı özetleyici çalışmalara işaret edeceğim:

Fuernkranz ve diğerlerinin (2012) yazdığı "Foundations of Rule Learning" kitabı; kuralların öğrenilmesiyle ilgili kapsamlı bir çalışma olup, bu konuya derinlemesine dalmak isteyenler için önerilir. Kuralların öğrenilmesiyle ilgili bütünsel bir çerçeve sunar ve birçok kural öğrenme algoritmasını tanıtır. Ayrıca, Weka kural öğrenicilerini incelemenizi öneririm. Bunlar arasında RIPPER, M5Rules, OneR, PART ve daha fazlası bulunur. RuleFit algoritması hakkında bu kitapta yer alan bölümde anlatıldığı gibi IF-THEN kurallarını doğrusal modellerde de kullanabilirsiniz.

Holte, Robert C. “Very simple classification rules perform well on most commonly used datasets.” Machine learning 11.1 (1993): 63-90.↩︎

Cohen, William W. “Fast effective rule induction.” Machine Learning Proceedings (1995). 115-123.↩︎

Letham, Benjamin, Cynthia Rudin, Tyler H. McCormick, and David Madigan. “Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model.” The Annals of Applied Statistics 9, no. 3 (2015): 1350-1371.↩︎

Borgelt, C. “An implementation of the FP-growth algorithm.” Proceedings of the 1st International Workshop on Open Source Data Mining Frequent Pattern Mining Implementations - OSDM ’05, 1–5. http://doi.org/10.1145/1133905.1133907 (2005).↩︎

Yang, Hongyu, Cynthia Rudin, and Margo Seltzer. “Scalable Bayesian rule lists.” Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.↩︎

Fürnkranz, Johannes, Dragan Gamberger, and Nada Lavrač. “Foundations of rule learning.” Springer Science & Business Media, (2012).↩︎

Previous5.4 Karar Ağaçları (Decision Tre)Next5.6 RuleFit

Last updated 15 days ago