![22
43
Supervised L.->Decision Tree-> ID3 Algoritmas脹
rnek 3 al脹ma 旦rnei
Values(Wind)= Weak, Strong ; Wind 旦znitelii ya Weak ya Strong deeri alabilir
S= [9+,5-]; 9 pozitif , 5 negatif 旦rnek var.
SWeak <- [6+, 2-]; Wind=Weak i巽in 6 pozitif, 2 negatif 旦rnek var.
SStrong <- [3+, 3-]; Wind=Strong i巽in 3 pozitif, 3 negatif 旦rnek var.
Gain(S,Wind)= Entropy(S) - v E Values(A)|Sv| / |S| Entropy(Sv)
= Entropy(S) (8/14)Entropy(SWeak)- (6/14)Entropy(SStrong)
= 0.940 (8/14) 0.811 (6/14) 1.00
= 0.048
44
C4.5 Algoritmas脹
Bir eikleme y旦ntemini i巽erir. Temel mant脹k; n端merik 旦zellik
vekt旦r端ndeki t端m deerler ikili olarak ele al脹n脹r, en b端y端k
bilgi kazanc脹n脹 salayacak bi巽imde bir eik deer belirlenir.
Eik deeri belirlemek i巽in t端m deerler s脹ralan脹r ve ikiye
b旦l端n端r.
Hangi eik deeriyle bilgi kazan脹m脹 en iyi ise o deer se巽ilir.
Se巽ilen eie g旦re 旦zellik vekt旦r端 kategorize edilir ve ID3
uygulan脹r.](https://image.slidesharecdn.com/ml3-230103071402-07f8e489/85/ML_3-pdf-22-320.jpg)
ML_3.pdf
- 1. 1 1 Dan脹manl脹 renme Supervised Learning Karar Aa巽lar脹 Decision Tree Dan脹manl脹 renme Supervised Learning Karar Aa巽lar脹 Decision Tree Machine Learning Sel巽uk niversitesi Fen Bilimleri Enstit端s端 Bilgisayar M端hendislii A.B.D. Dr.Erkan LKER Sunularda yararlan脹lan kaynaklar: Gazi niversitesi Bilgisayar M端hendislii B旦l端m端 M. Ali Ak巽ayol ders sunusu Dr.Umut Orhan ders sunular脹 Dan脹manl脹 renme Supervised Learning 2 Dan脹manl脹 (Denetimli, g旦zetimli, Eiticili) 旦renme, makine 旦renmesinde s脹n脹fland脹rma veya t端mevar脹ml脹 (inductive) 旦renme eklinde ifade edilir. Denetimli 旦renmede hedef deerler (targets) ile giri deerleri (inputs) birlikte eitim k端mesi (training set) olarak salan脹r. renme ileminde bir kay脹t k端mesi kullan脹l脹r ve 旦zellikler k端mesi olarak g旦sterilir. k端medeki eleman say脹s脹n脹 g旦sterir
- 2. 2 Dan脹manl脹 renme Supervised Learning 3 Dan脹manl脹 renme Supervised Learning 4 rnek: Bir kredi uygulamas脹na y旦nelik veri k端mesi
- 3. 3 Dan脹manl脹 renme Supervised Learning 5 rnek veri k端mesi Table 3.1 The Credit Card Promotion Database Income Life Insurance Credit Card Range Promotion Insurance Sex Age 4050K No No Male 45 3040K Yes No Female 40 4050K No No Male 42 3040K Yes Yes Male 43 5060K Yes No Female 38 2030K No No Female 55 3040K Yes Yes Male 35 2030K No No Male 27 3040K No No Male 43 3040K Yes No Female 41 4050K Yes No Female 43 2030K Yes No Male 29 5060K Yes No Female 39 4050K No No Male 55 2030K Yes Yes Female 19 rnekler (intances, samples) Kaynak:Dr.Song端l Albayrak Ders sunusu Dan脹manl脹 renme Supervised Learning 6 rnek veri k端mesi Table 3.1 The Credit Card Promotion Database Income Life Insurance Credit Card Range Promotion Insurance Sex Age 4050K No No Male 45 3040K Yes No Female 40 4050K No No Male 42 3040K Yes Yes Male 43 5060K Yes No Female 38 2030K No No Female 55 3040K Yes Yes Male 35 2030K No No Male 27 3040K No No Male 43 3040K Yes No Female 41 4050K Yes No Female 43 2030K Yes No Male 29 5060K Yes No Female 39 4050K No No Male 55 20 30K Yes Yes Female 19 zellikler, nitelikler (features) Kaynak:Dr.Song端l Albayrak Ders sunusu
- 4. 4 Dan脹manl脹 renme Supervised Learning 7 Bir veri k端mesi ile 旦renen bir model gelitirip gelecekteki yeni m端terilere ait verilerde kullan脹labilir. Bu ekilde s脹n脹f etiketlerinin de verildii 旦renmeye denetimli (supervised) 旦renme denilir. renme s端recinde kullan脹lan veri k端mesine eitim verisi (training data), 旦renmeden sonraki deerlendirme s端recinde kullan脹lan veri k端mesine ise test verisi denilmektedir. Eitim verisinin de test verisinin de t端m sistemi temsil etme kapasitesine sahip olmas脹 gerekir. Test verisi eitim s端recinde g旦r端lmemi veri (unseen data) olarak oluturulmal脹d脹r. Gelitirilen modelin doruluk deeri (accuracy), test verisinde doru s脹n脹fland脹rma say脹s脹yla belirlenir. Dan脹manl脹 renme Supervised Learning 8 Apply Model Learn Model Tid Attrib1 Attrib2 Attrib3 Class 1 Yes Large 125K No 2 No Medium 100K No 3 No Small 70K No 4 Yes Medium 120K No 5 No Large 95K Yes 6 No Medium 60K No 7 Yes Large 220K No 8 No Small 85K Yes 9 No Medium 75K No 10 No Small 90K Yes 10 Tid Attrib1 Attrib2 Attrib3 Class 11 No Small 55K ? 12 Yes Medium 80K ? 13 Yes Large 110K ? 14 No Small 95K ? 15 No Large 67K ? 10 S脹n脹flaman脹n temel kurallar脹: renme eiticilidir Veri setinde bulunan her 旦rnein bir dizi nitelii vard脹r ve bu niteliklerden biri de s脹n脹f bilgisidir. Hangi s脹n脹fa ait olduu bilinen nesneler (旦renme k端mesi- training set) ile bir model oluturulur Oluturulan model 旦renme k端mesinde yer almayan nesneler (deneme k端mesi- test set) ile denenerek baar脹s脹 旦l巽端l端r
- 5. 5 9 S脹n脹fland脹rma problemleri i巽in yayg脹n kullan脹lan y旦ntemdir. S脹n脹fland脹rma doruluu dier 旦renme metotlar脹na g旦re 巽ok etkindir renmi s脹n脹fland脹rma modeli aa巽 eklinde g旦sterilir ve karar aac脹 (decision tree) olarak adland脹r脹l脹r Temel fikir, giri verisinin bir k端meleme algoritmas脹 yard脹m脹yla tekrar tekrar gruplara b旦l端nmesine dayan脹r. Grubun t端m elemanlar脹 ayn脹 s脹n脹f etiketine sahip olana kadar k端meleme ilemi derinlemesine devam eder. Dan脹manl脹 renme (Supervised Learning) Karar Aa巽lar脹 Decision Tree 10 Karar Aac脹 Nedir? Hava Nem Evet R端zgar G端neli Bulutlu Yamurlu Evet Evet Hay脹r Hay脹r Normal Y端ksek Kuvvetli Hafif 聴fadeleri ay脹rmay脹 旦renme yetenei olan ve g端r端lt端l端 veriyi salamlat脹ran soyut deerli fonksiyonlar脹 tahmin eden bir metottur. Inductive Bias脹 genis aa巽lar 端zerinde k端巽端k aa巽lar脹 tercih etmesidir Attribute deerindeki s脹n脹rlamalar脹n birleiminin ayr脹lmas脹 eklinde sunulur
- 6. 6 11 Karar Aac脹 rnek Attribute deerindeki s脹n脹rlamalar脹n birleiminin ayr脹lmas脹 eklinde sunulur Tid Refund Marital Status Taxable Income Cheat 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Splitting Attributes Training Data Model: Decision Tree 12 Karar Aac脹 rnek?Attribute deerindeki s脹n脹rlamalar脹n birleiminin ayr脹lmas脹 eklinde sunulur Tid Refund Marital Status Taxable Income Cheat 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 MarSt Refund TaxInc YES NO NO NO Yes No Married Single, Divorced < 80K > 80K There could be more than one tree that fits the same data!
- 7. 7 13 Karar Aac脹 renmesi i巽in uygun problemler Decision tree learning genellikle aa脹daki karakteristiklerdeki problemler i巽in uygundur. 1. rnekler; 旦zniteliklerin sabit isimleri (旦rnek Hava) ve onlar脹n deerleri ile a巽脹klan脹r (旦rnein G端neli). (Instance are represented by attribute value pairs) 2. Hedef fonksiyon, Ayr脹k 巽脹k脹 deerleridir.(The target function has discrete output values). 3. Yukar脹da da iaret edildii gibi Karar Aac脹 doal olarak ayr脹k ifadeleri sunar (Disjunctive descriptions may be required). 4. Karar Aac脹 renme metotlar脹 hatalara kar脹 g端巽l端d端r (The training data may contain errors). 5. Karar Aac脹 metotlar脹 bilinmeyen deerli eitim 旦rneklerinde bile kullan脹labilir (The training data may contain missing attribute values). 14 Karar Aac脹 Bir Algoritma Temel Algoritma (miyobik bir algoritma) Karar aac脹 yukar脹dan aa脹ya, yinelemeli olarak b旦l ve kazan y旦ntemine g旦re ina edilirler. Balang脹巽ta b端t端n noktalar aac脹n k旦k端nde toplanmaktad脹r Kategorik veriler kullan脹l脹r, s端rekli deikenlerin 旦nceden kesikli hale getirilmesi gerekir. rnekler, se巽ilen deikenlere (karakteristik) g旦re yinelemeli olarak b旦l端mlenir Deikenlerin se巽imi sezgisel veya belli bir istatistiksel 旦l巽端ye (mesela bilgi kazan脹m脹) dayan脹r B旦l端mlemenin durmas脹 i巽in artlar Bir d端端mde bulunan b端t端n 旦rnekler ayn脹 s脹n脹fa aittir B旦l端mlenin yap脹laca脹 deiken kalmam脹t脹r. Yani o d端端me (yaprak) gelene kadar b端t端n deikenler kullan脹lm脹t脹r. Baka 旦rnek kalmam脹t脹r. Kaynak: Dr. Ayhan Demiriz ders sunumu
- 8. 8 15 Karar Aac脹 Bir Algoritma - S脹n脹fland脹rma Apply Model Learn Model Tid Attrib1 Attrib2 Attrib3 Class 1 Yes Large 125K No 2 No Medium 100K No 3 No Small 70K No 4 Yes Medium 120K No 5 No Large 95K Yes 6 No Medium 60K No 7 Yes Large 220K No 8 No Small 85K Yes 9 No Medium 75K No 10 No Small 90K Yes 10 Tid Attrib1 Attrib2 Attrib3 Class 11 No Small 55K ? 12 Yes Medium 80K ? 13 Yes Large 110K ? 14 No Small 95K ? 15 No Large 67K ? 10 Decision Tree 16 Karar Aac脹 Bir Algoritma - S脹n脹fland脹rma Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Refund Marital Status Taxable Income Cheat No Married 80K ? 1 0 Test Data Start from the root of tree.
- 9. 9 17 Karar Aac脹 Bir Algoritma - S脹n脹fland脹rma Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Refund Marital Status Taxable Income Cheat No Married 80K ? 1 0 Test Data 18 Karar Aac脹 Bir Algoritma - S脹n脹fland脹rma Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Refund Marital Status Taxable Income Cheat No Married 80K ? 1 0 Test Data
- 10. 10 19 Karar Aac脹 Bir Algoritma - S脹n脹fland脹rma Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Refund Marital Status Taxable Income Cheat No Married 80K ? 1 0 Test Data 20 Karar Aac脹 Bir Algoritma - S脹n脹fland脹rma Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Refund Marital Status Taxable Income Cheat No Married 80K ? 1 0 Test Data
- 11. 11 21 Karar Aac脹 Bir Algoritma - S脹n脹fland脹rma Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced < 80K > 80K Refund Marital Status Taxable Income Cheat No Married 80K ? 1 0 Test Data Assign Cheat to No 22 Karar Aac脹ndan Kural 巽脹kar脹m脹 Bilgiyi Eer-O Zaman kurallar脹 ile temsil et K旦kten yapraklara giden heryol i巽in bir kural 端retilir Bir yol 端zerindeki her bir deiken-deer 巽ifti bir bala巽 oluturur Yapraklar s脹n脹f tahminini i巽erir Kurallar脹n anal脹lmas脹 巽ok kolayd脹r rnek Eer ya = <=30 ve 旦renci = hay脹r O Zaman Bilgisayar Al脹r? = hay脹r Eer ya = <=30 ve 旦renci = evet O Zaman Bilgisayar Al脹r? = evet Eer ya = 3140 O Zaman Bilgisayar Al脹r? = evet Eer ya = >40 ve kredi durumu = m端kemmel O Zaman Bilgisayar Al脹r? = evet Eer ya = <=30 ve kredi durumu = vasat O Zaman Bilgisayar Al脹r? = hay脹r Kaynak: Dr. Ayhan Demiriz ders sunumu
- 12. 12 23 Karar Aac脹 Tipleri Entropiye dayal脹 s脹n脹fland脹rma aa巽lar脹 (ID3, C4.5) S脹n脹fland脹rma ve Regresyon aa巽lar脹na (CART- Classification And Regression Trees) dayal脹 olmak 端zere iki kategoride bir巽ok algoritma 旦nerilmitir (Towing ve gini). CART algoritmalar脹nda her d端端mde bir kritere g旦re ikili b旦l端nme yap脹l脹r nce entropiye dayal脹 karar aa巽lar脹n脹 inceleyeceiz. Bu algoritmalar脹 iyi anlayabilmek i巽in 旦nce entropiyi iyi bilmek gerekmektedir. 24 Entropi, Belirsizlik ve Enformasyon
- 13. 13 25 Enformasyon Asl脹nda z脹t eyleri temsil etmelerine ramen Shannona g旦re maksimum belirsizlik maksimum enformasyon salad脹脹 i巽in Enformasyon ve Belirsizlik terimleri benzerdir. Enformasyon (self-information) form端l端 aa脹daki gibidir. Shannon bilgiyi bitlerle temsil ettii i巽in logaritmay脹 iki taban脹nda kullanm脹t脹r. ) ( log ) ( 1 log ) ( x P x P x I P (x), x olay脹n脹n ger巽ekleme olas脹l脹脹n脹 g旦sterir 26 Entropi Shannona g旦re entropi, iletilen bir mesaj脹n ta脹d脹脹 enformasyonun beklenen deeridir. Shannon Entropisi (H) ad脹yla an脹lan terim, t端m ai durumlar脹na ait Pi olas脹l脹klar脹na bal脹 bir deerdir. n i i i n i i i n i i i P P x P x P x I x P X I E X H 1 2 1 2 1 log ) ( 1 log ) ( ) ( ). ( )) ( ( ) (
- 14. 14 27 Entropi Bir paran脹n havaya at脹lmas脹 olay脹, rassal X s端recini temsil etsin. Yaz脹 ve tura gelme olas脹l脹klar脹 eit olduu i巽in X s端recinin entropisi aa脹daki gibidir. Entropisi 1 olan para atma olay脹 (X) ger巽ekletiinde 1 bitlik bilgi kazan脹lacakt脹r. 1 ) 5 . 0 log 5 . 0 5 . 0 log 5 . 0 ( log ) ( 2 2 2 1 2 i i i p p X H 28 rnek
- 15. 15 29 Karar Aac脹nda Entropi Karar aa巽lar脹 巽ok boyutlu (旦zellikli) veriyi belirlenmi 旦zellik 端zerindeki bir art ile par巽alara b旦ler. Her seferinde verinin hangi 旦zellii 端zerinde hangi arta g旦re ilem yapaca脹na karar vermek 巽ok b端y端k bir kombinasyonun 巽旦z端m端yle m端mk端nd端r. 5 旦zellik ve 20 旦rnee sahip bir veride 106 dan fazla say脹da farkl脹 karar aac脹 oluturulabilir. Bu sebeple her par巽alanman脹n metodolojik olmas脹 gerekir. 30 Karar Aac脹nda Entropi rnek Yukar脹da verilen hayvanlar脹n 巽eitli 旦zelliklerine g旦re sonraki slidelardaki gibi karar aa巽lar脹 haz脹rlamak m端mk端nd端r
- 16. 16 31 herhangi bir eleman脹 aa巽ta kodlayan ka巽ar ad脹m olduunu listeleyelim: Koala -> 1 (sadece k端rkl端d端r ayr脹m脹 yeterli) Timsah -> 2 (hem k端rks端z hem de s脹cak kanl脹 olduunu bilmemiz gerekiyor) Yunus -> 3 ( hem k端rks端z hem s脹cak kanl脹 hem de y端zd端端n端 bilmemiz gerekiyor) Deve Kuu -> 3 Albatros -> 3 Kuzgun -> 3 Yukar脹daki deerleri toplarsak, 15 ad脹mda b端t端n elemanlar脹 birer kere ziyaret etmek m端mk端nd端r denilebilir. eriim say脹lar脹n脹 yazarsak: Deve Kuu -> 1 Albatros -> 1 Kuzgun -> 1 Koala -> 2 Timsah -> 3 Yunus -> 3 Aa脹daki yeni aa巽ta her elemana birer kere eriilmesi istendiinde toplam 11 ad脹m harcanmas脹 gerekmektedir Kaynak:www.bilgisayarkavramlari.com 32 Quinlane g旦re; veri, bir 旦zellie g旦re b旦l端nd端端nde elde edilen her bir veri k端mesinin belirsizlii minimum ve dolay脹s脹yla bilgi kazanc脹 maksimum ise en iyi se巽im yap脹lm脹 demektir. Buna g旦re 旦nerdii ilk algoritma ID3te tek tek 旦zellik vekt旦rleri incelenir ve en y端ksek bilgi kazanc脹na sahip 旦zellik, aa巽ta dallanma yapmak i巽in tercih edilir. Karar Aac脹nda Entropi Entropi, 旦rneklerin keyfi olarak toplanmas脹n脹n kirliliini karakterize eder
- 17. 17 33 Supervised L.->Decision Tree-> ID3 Algoritmas脹 Sadece kategorik veri ile 巽al脹an bir y旦ntemdir. Her iterasyonun ilk ad脹m脹nda veri 旦rneklerine ait s脹n脹f bilgilerini ta脹yan vekt旦r端n entropisi belirlenir. Daha sonra 旦zellik vekt旦rlerinin s脹n脹fa ba脹ml脹 entropileri hesaplanarak ilk ad脹mda hesaplanan entropiden 巽脹kart脹l脹r. Bu ekilde elde edilen deer ilgili 旦zellik vekt旦r端ne ait kazan巽 deeridir. En b端y端k kazanca sahip 旦zellik vekt旦r端 aac脹n o iterasyonda belirlenen dallanmas脹n脹 ger巽ekletirir (Dallanma D端端m端). Iterative Dichotomiser Tree 34 Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek Yukar脹daki tablo i巽in karar aac脹 oluturulsun s脹n脹f bilgilerini ta脹yan vekt旦r端n entropisi 旦zellik vekt旦rlerinin s脹n脹fa ba脹ml脹 entropilerini hesapla ilk ad脹mda hesaplanan entropiden 巽脹kart. Elde edilen deer kazan巽 deeridir. En b端y端k kazanca sahip 旦zellik vekt旦r端 Dallanma D端端m端d端r.
- 18. 18 35 Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek Yukar脹daki tablo i巽in karar aac脹 oluturulsun S脹n脹f bilgilerini ta脹yan vekt旦r端n entropisi =1 旦zellik vekt旦rlerinin s脹n脹fa ba脹ml脹 entropilerini hesapla ilk ad脹mda hesaplanan entropiden 巽脹kart. Elde edilen deer kazan巽 deeridir. 36 Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek Yukar脹daki tablo i巽in karar aac脹 oluturulsun S脹n脹f bilgilerini ta脹yan vekt旦r端n entropisi =1 旦zellik vekt旦rlerinin s脹n脹fa ba脹ml脹 entropilerini hesapla ilk ad脹mda hesaplanan entropiden 巽脹kart. Elde edilen deer kazan巽 deeridir.
- 19. 19 37 Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek Yukar脹daki tablo i巽in karar aac脹 oluturulsun S脹n脹f bilgilerini ta脹yan vekt旦r端n entropisi =1 旦zellik vekt旦rlerinin s脹n脹fa ba脹ml脹 entropilerini hesapla ilk ad脹mda hesaplanan entropiden 巽脹kart. Elde edilen deer kazan巽 deeridir. 38 Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek S脹n脹f bilgilerini ta脹yan vekt旦r端n entropisi =1 旦zellik vekt旦rlerinin s脹n脹fa ba脹ml脹 entropilerini hesapla, ilk ad脹mda hesaplanan entropiden 巽脹kart. Elde edilen deer kazan巽 deeridir. En b端y端k kazanca sahip 旦zellik vekt旦r端 Dallanma D端端m端d端r.
- 20. 20 39 Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek 40 V1 V2 S A C E B C F B D E B D F 2 旦zellik vekt旦r端 (V1 ve V2) ile S s脹n脹f vekt旦r端ne sahip 4 旦rnekli veri k端mesi verilmitir. ID3 algoritmas脹 ile ilk dallanma hangi 旦zellik 端zerinde ger巽ekleir ? H(S) - H(V1,S) H(S) - H(V2,S) Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek - 2
- 21. 21 41 V1 V2 S A C E B C F B D E B D F S脹n脹f Entropisi 1 2 1 log 2 1 2 1 log 2 1 ) ( 2 2 S H V1 Entropisi 0,6887 0,9183 4 3 0 3 2 log 3 2 3 1 log 3 1 4 3 0 4 1 ) ( 4 3 ) ( 4 1 ) 1 ( 2 2 B H A H V H V2 Entropisi 1 2 1 2 1 ) ( 2 1 ) ( 2 1 ) 2 ( D H C H V H V1 se巽ilir Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek - 2 42 Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek 3 al脹ma 旦rnei Day Outlook Temperature Humidity Wind PlayTennis D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes D10 Rain Mild Normal Weak Yes D11 Sunny Mild Normal Strong Yes D12 Overcast Mild High Strong Yes D13 Overcast Hot Normal Weak Yes D14 Rain Mild High Strong No
- 22. 22 43 Supervised L.->Decision Tree-> ID3 Algoritmas脹 rnek 3 al脹ma 旦rnei Values(Wind)= Weak, Strong ; Wind 旦znitelii ya Weak ya Strong deeri alabilir S= [9+,5-]; 9 pozitif , 5 negatif 旦rnek var. SWeak <- [6+, 2-]; Wind=Weak i巽in 6 pozitif, 2 negatif 旦rnek var. SStrong <- [3+, 3-]; Wind=Strong i巽in 3 pozitif, 3 negatif 旦rnek var. Gain(S,Wind)= Entropy(S) - v E Values(A)|Sv| / |S| Entropy(Sv) = Entropy(S) (8/14)Entropy(SWeak)- (6/14)Entropy(SStrong) = 0.940 (8/14) 0.811 (6/14) 1.00 = 0.048 44 C4.5 Algoritmas脹 Bir eikleme y旦ntemini i巽erir. Temel mant脹k; n端merik 旦zellik vekt旦r端ndeki t端m deerler ikili olarak ele al脹n脹r, en b端y端k bilgi kazanc脹n脹 salayacak bi巽imde bir eik deer belirlenir. Eik deeri belirlemek i巽in t端m deerler s脹ralan脹r ve ikiye b旦l端n端r. Hangi eik deeriyle bilgi kazan脹m脹 en iyi ise o deer se巽ilir. Se巽ilen eie g旦re 旦zellik vekt旦r端 kategorize edilir ve ID3 uygulan脹r.
- 23. 23 45 C4.5 Algoritmas脹 C4.5 aac脹n脹n ID3 aac脹ndan en b端y端k fark脹 normalletirme (normalization) kullan脹yor olmas脹d脹r. Yani ID3 aac脹 端zerinde entropi hesab脹 yap脹l脹r (veya bilgi kazan脹m脹 (information gain)) ve bu deere g旦re karar noktalar脹 belirlenir. C4.5 aac脹nda ise entropi deerleri birer oran olarak tutulur. Ayr脹ca aa巽 端zerinde eriim s脹kl脹klar脹na g旦re alt aa巽lar脹n (subtree) farkl脹 seviyelere ta脹nmas脹 da m端mk端nd端r. C4.5 aac脹n脹n dier bir fark脹 ise tam bu noktada orataya 巽脹kar ID3 aac脹n脹n yakla脹m脹ndan farkl脹 olarak C4.5 aac脹nda budama (prunning) ilemi yap脹lmaktad脹r. Kaynak: Sadi Evren eker Web sayfas脹 46 Supervised L.->Decision Tree-> C4.5 Algoritmas脹 rnek
- 24. 24 47 Supervised L.->Decision Tree-> C4.5 Algoritmas脹 rnek 48 Supervised L.->Decision Tree-> C4.5 Algoritmas脹 rnek
- 25. 25 49 Supervised L.->Decision Tree-> C4.5 Algoritmas脹 rnek 50 Supervised L.->Decision Tree-> C4.5 Algoritmas脹 rnek
- 26. 26 51 Supervised L.->Decision Tree-> C4.5 Algoritmas脹 rnek 52 Kay脹p Veri Unknown attribute values Eer veride baz脹 旦rneklerin baz脹 旦zellikleri kay脹psa izlenecek iki yol vard脹r: Kay脹p 旦zelliklere sahip 旦rnek veriden tamamen 巽脹kart脹l脹r. Kay脹p verilerle 巽al脹abilecek ekilde algoritma d端zenlenir. Eer kay脹pl脹 旦rneklerin say脹s脹 birinci se巽enek uygulanamayacak kadar 巽oksa ikinci se巽enek uygulanmal脹d脹r.
- 27. 27 53 Kay脹p bilgiye sahip 旦zellik vekt旦r端 i巽in kazan巽 hesaplan脹rken; kay脹pl脹 旦rnekler hari巽 tutularak bilgi kazanc脹 normal ekilde hesaplan脹r ve daha sonra F katsay脹s脹yla 巽arp脹l脹r. F, kay脹ps脹z verinin tamam脹na oran脹d脹r. )) , ( ) ( .( ) ( X V H X H F X IG Kay脹p Veri Unknown attribute values Kay脹p bilgiye sahip 旦zellik vekt旦r端 i巽inde en s脹k tekrarlanan deerin kay脹p bilgi yerine yaz脹lmas脹 da 旦nerilen y旦ntemlerdendir 54 Ezber, A脹r脹 renme (Overfitting) T端m makine 旦renmesi y旦ntemlerinde verinin ana hatlar脹n脹n modellenmesi esas al脹nd脹脹 i巽in 旦renme modelinde ezberden (overfitting) ka巽脹n脹lmal脹d脹r. T端m karar aa巽lar脹 旦nlem al脹nmazsa ezber yapar. 叡renme seti kullan脹larak t端mevar脹m ile bulunmu bir karar aac脹 a脹r脹 旦renmi olabilir Verideki g端r端lt端den ve sapmalardan 旦t端r端 巽ok fazla dal mevcut olabilir G旦r端lmeyen veriler i巽in 巽ok zay脹f bir tahmin yetenei olabilir A脹r脹 旦renmeden ka巽脹nmak i巽in iki yol nceden budama: Aa巽 en b端y端k ekline ulamadan 旦renmenin durdurulmas脹 (Prepruning) Aa巽 tam b端y端kl端e ulat脹ktan sonra budanmas脹 (Postpruning) Budama, s脹n脹fland脹rmaya katk脹s脹 olmayan b旦l端mlerin karar aac脹ndan 巽脹kar脹lmas脹 ilemidir. Bu sayede karar aac脹 hem sade hem de anla脹labilir hale gelir Kaynak: Dr. Ayhan Demiriz ders sunumu
- 28. 28 55 n Budama Prepruning n budama ilemi aa巽 oluturulurken yap脹l脹r. B旦l端nen nitelikler, deerleri belli bir eik de- erinin (hata tolerans脹n脹n) 端st端nde deilse o noktada aa巽 b旦l端mleme ilemi durdurulur ve o an elde bulunan k端medeki bask脹n s脹n脹f eti- keti, yaprak olarak oluturulur. Deciding not to divide a set of samples any further under some conditions. The stopping criterion is usually based on some statistical test, such as the 2- test. 56 Sonradan Budama Postpruning Sonradan budama ilemi aa巽 oluturulduktan sonra devreye girer. Alt aa巽lar脹 silerek yaprak oluturma, alt aa巽lar脹 y端kseltme, dal kesme eklinde yap脹labilir. Removing retrospectively some of the tree structure using selected accuracy criteria.
- 29. 29 57 Aa巽 Budama Hava Nem Evet 15 R端zgar G端neli Bulutlu Yamurlu Evet 20 Evet 15 Hay脹r 35 Hay脹r 25 Normal Y端ksek Kuvvetli Hafif Hata tolerans脹 %33 se巽ilirse Nem d端端m端n端n alt dallar脹ndaki Evet oran脹 %30dur. Bu y端zden Nem d端端m端 budan脹p yerine Hay脹r yapra脹 konur. 58 Aa巽 Budama Hava Evet R端zgar G端neli Bulutlu Yamurlu Evet Hay脹r Hay脹r Kuvvetli Hafif
- 30. 30 59 S脹n脹fland脹rma ve Regresyon Aa巽lar脹 (CART) CART karar aa巽lar脹n脹n temel prensibi herbir d端端mde aac脹 iki dala ay脹rmas脹d脹r. En 巽ok bilinen iki algoritmas脹: Twoing algoritmas脹 Gini algoritmas脹 60 DEVLER Aa脹daki CART algoritmalar脹n脹 program eklinde yaz脹n脹z ve bir dok端man s脹n脹fland脹rma 旦rnei olarak d端端n端n端z. Twoing Gini Twoing ve Gini algoritmalar脹n脹 birbiriyle kar脹lat脹r脹p avantajlar脹n脹 ve dezavantajlar脹n脹 i巽eren bir rapor haz脹rlay脹n脹z
- 31. 31 61 Dier Karar aac脹 旦renme algoritmalar脹 Rastgele Orman (Random Forest) : S脹n脹fland脹rma ilemi s脹ras脹nda birden fazla karar aac脹 kullan脹larak s脹n脹fland脹rma deerinin y端kseltilmesi hedeflenir. H脹zland脹r脹lm脹 Aa巽lar (Boosted Trees): Hem s脹n脹fland脹rma (classification) hem de ilkelleme (regression) problemleri i巽in kullan脹labilen bir algoritmad脹r. D旦nd端rme Aac脹 (Rotation Forest) : Rastgele aaca benzer ekilde birden fazla aa巽 kullan脹lmaktad脹r ancak her aa巽, 旦nce farkl脹 bileen analizi (Pricipal Component Analysis, PCA) kullan脹larak eitilmektedir. Bu eitim i巽in veri k端mesinin rast gele se巽ilmi bir alt k端mesi kullan脹lmaktad脹r (sarn脹巽lama y旦ntemiyle). Chi-Kare Otomatik 聴liki Taray脹c脹s脹 (Chi-Square Automatic Interaction Detector, CHAID) : Birden fazla seviyeye b旦lme ilemine izin veren bir s脹n脹fland脹rma algoritmas脹d脹r. MARS : Say脹sal verilerin daha iyi ilenebilmesi i巽in karar aa巽lar脹n脹 iyiletiren bir yakla脹md脹r DEVLER S脹n脹fland脹rma Modelini Deerlendirme S脹n脹fland脹rma Metodu taraf脹ndan oluturulan modelin baar脹s脹n脹 旦l巽mek i巽in Doruluk (Accuracy) Hata Oran脹 (Error rate) Specificity Sensitivity gibi 旦l巽端ler kullan脹l脹r. Kaynak:Dr.Song端l Albayrak Ders sunusu
- 32. 32 S脹n脹fland脹rma Modelini Deerlendirme: * Doruluk (Accuracy) * Hata Oran脹 (Error Rate) Bir M s脹n脹flay脹c脹s脹 i巽in doruluk; acc(M) doru s脹n脹flanm脹 旦rneklerin toplam 旦rnek say脹s脹na oran脹ndan bulunur. Bir M s脹n脹flay脹c脹s脹 i巽in hata oran脹; 1-acc(M) olarak hesaplan脹r. Kaynak:Dr.Song端l Albayrak Ders sunusu S脹n脹fland脹rma Modelini Deerlendirme: Kar脹脹kl脹k Matrisi (Class Confusion Matrix) ng旦r端len s脹n脹f (Predicted Class) Ger巽ek S脹n脹f (Actual Class) C1 (Positive) C2 (Negative) C1 (Positive) True positive TP False negative FN C2 (Negative) False positive FP True negative TN sensitivity = TP /pos /* true positive recognition rate */ specificity = TN /neg /* true negative recognition rate */ accuracy= (TP +TN) / (pos + neg) 裡Positive 裡Negative Kaynak:Dr.Song端l Albayrak Ders sunusu
- 33. 33 S脹n脹fland脹rma Modelini Deerlendirme: Kar脹脹kl脹k Matrisi (Class Confusion Matrix) Table 2.7 Two Confusion Matrices Each Showing a 10% Error Rate Model Computed Computed Model Computed Computed A Accept Reject B Accept Reject Accept 600 25 Accept 600 75 Reject 75 300 Reject 25 300 Kaynak:Dr.Song端l Albayrak Ders sunusu 66 Haftaya Haftaya Machine Learning Sel巽uk niversitesi Fen Bilimleri Enstit端s端 Bilgisayar M端hendislii A.B.D. Dr.Erkan LKER