Java'da Karar Agaclari - ID3 Algoritmasi

Karar Agaçları, Temel sınıflandırma tekniklerinden biri olan karar agaçları; verileri belli nitelik degerlerine göre sınıflandırmaya yarar. Bunun için algoritmaya girdi olarak verilerin belirlenen belli nitelikleri, çıktı olarak da verilerin belli bir niteligi verilir. Algoritma bu çıktı niteligindeki degerlere ulasmak için hangi girdi nitelik degerlerinin olması gerektigini agaç veri yapılarını kullanarak kesfeder. Karar agaçları, yaygın olarak kullanılan sınıflama algoritmalarından birisidir. Karar agacı yapılarında, her dügüm bir nitelik üzerinde gerçeklestirilen testi, her dal bu testin çıktısını, her yaprak dügüm ise sınıfları temsil eder. En üstteki dügüm kök dügüm olarak adlandırılır. Karar agaçları, kök dügümden yaprak dügüme dogru çalısır. En yaygın kullanılan karar agacı algoritmaları; • CHAID (Chi-Squared Automatic Interaction Detector , Kass 1980), • C&RT (Classification and Regression Trees, Breiman ve Friedman, 1984), • ID3 (Induction of Decision Trees, Quinlan, 1986), • C4.5 (Quinlan, 1993). Simdi ID3 Algoritmasi ile ilgili bir java'da gelistirilmis bir uygulamayi inceleyelim... ID3 algoritması aşağıdaki gibi özetlenebilir:

1. Kullanılmayan tüm nitelikleri ve bunların sayısı entropi ile ilgili test örnekleri

2. Entropi (ya da eşdeğeri, bilgi artışı maksimum) minimum olduğu özellik secilebilir

3. Bu özniteliği içeren düğüm bulunmus olur.

Oncelikle nano.txt belgesinde asagida ki gibi bir verilerin bulundugu bir tablo olusturuyoruz. Verilerin arasinda Tab tusuyla ilerlemeyi ihmal etmeyiniz.

Kaynak Kodlar ;

ID3.JavaID3.Java

package id3_algoritmalari; import java.io.*; import java.util.*; public class ID3 { int OznitelikNumarasi; String []OznitelikIsimleri; Vector []EtkiAlanlari; class DataPoint { public int []OzNitelikleri; public DataPoint(int numattributes) { OzNitelikleri = new int

; } }; class TreeNode { public double DugunNoktalari; public Vector veri; public int AyrismaOzniteligi; public int AyrismaDegeri; public TreeNode []AltDugum; public TreeNode UstDugum; public TreeNode() { veri = new Vector(); } }; TreeNode kok = new TreeNode(); public int SembolDegeriniGetir(int nitelik, String sembol) { int index = EtkiAlanlari

.indexOf(sembol); if (index < 0) { EtkiAlanlari

.addElement(sembol); return EtkiAlanlari

.size() -1; } return index; } public int []ButunDegerleriGetir(Vector veri, int nitelik) { Vector degerler = new Vector(); int say = veri.size(); for (int i=0; i< say; i++) { DataPoint point = (DataPoint)veri.elementAt(i); String sembol = (String)EtkiAlanlari

.elementAt(point.OzNitelikleri

); int index = degerler.indexOf(sembol); if (index < 0) { degerler.addElement(sembol); } } int []dizi = new int

; for (int i=0; i< dizi.length; i++) { String symbol = (String)degerler.elementAt(i); dizi

= EtkiAlanlari

.indexOf(symbol); } degerler = null; return dizi; } public Vector AltKumeleriGetir(Vector veri, int nitelik, int deger) { Vector AltKume = new Vector(); int say = veri.size(); for (int i=0; i< say; i++) { DataPoint point = (DataPoint)veri.elementAt(i); if (point.OzNitelikleri

== deger) AltKume.addElement(point); } return AltKume; } public double DugumNoktalariniHesapla(Vector veri) { int VeriNumarasi = veri.size(); if (VeriNumarasi == 0) return 0; int nitelik = OznitelikNumarasi-1; int nitelikDegeri = EtkiAlanlari

.size(); double topla = 0; for (int i=0; i< nitelikDegeri; i++) { int sayac=0; for (int j=0; j< VeriNumarasi; j++) { DataPoint point = (DataPoint)veri.elementAt(j); if (point.OzNitelikleri

== i) sayac++; } double Olasilik = 1.*sayac/VeriNumarasi; if (sayac > 0) topla += -Olasilik*Math.log(Olasilik); } return topla; } public boolean AyristirmaIcinKullanilacak(TreeNode dugum, int nitelik) { if (dugum.AltDugum != null) { if (dugum.AyrismaOzniteligi == nitelik ) return true; } if (dugum.UstDugum == null) return false; return AyristirmaIcinKullanilacak(dugum.UstDugum, nitelik); } public void AyristirmaDugumu(TreeNode dugum) { double EnIyiDugumNoktasi=0; boolean secilen=false; int SecilenNitelik=0; int VeriNumarasi = dugum.veri.size(); int GirilenNiteliklerinNumarasi = OznitelikNumarasi-1; dugum.DugunNoktalari = DugumNoktalariniHesapla(dugum.veri); if (dugum.DugunNoktalari == 0) return; for (int i=0; i< GirilenNiteliklerinNumarasi; i++) { int DegerNumarasi = EtkiAlanlari

.size(); if ( AyristirmaIcinKullanilacak(dugum, i) ) continue; double OrtalamaDugumNoktasi = 0; for (int j=0; j< DegerNumarasi; j++) { Vector AltKume = AltKumeleriGetir(dugum.veri, i, j); if (AltKume.size() == 0) continue; double AltDugumNoktasi = DugumNoktalariniHesapla(AltKume); OrtalamaDugumNoktasi += AltDugumNoktasi * AltKume.size(); } OrtalamaDugumNoktasi = OrtalamaDugumNoktasi / VeriNumarasi; if (secilen == false) { secilen = true; EnIyiDugumNoktasi = OrtalamaDugumNoktasi; SecilenNitelik = i; } else { if (OrtalamaDugumNoktasi < EnIyiDugumNoktasi) { secilen = true; EnIyiDugumNoktasi = OrtalamaDugumNoktasi; SecilenNitelik = i; } } } if (secilen == false) return; int DegerNumarasi = EtkiAlanlari

.size(); dugum.AyrismaOzniteligi = SecilenNitelik; dugum.AltDugum = new TreeNode

; for (int j=0; j< DegerNumarasi; j++) { dugum.AltDugum

= new TreeNode(); dugum.AltDugum

.UstDugum = dugum; dugum.AltDugum

.veri = AltKumeleriGetir(dugum.veri, SecilenNitelik, j); dugum.AltDugum

.AyrismaDegeri = j; } for (int j=0; j< DegerNumarasi; j++) { AyristirmaDugumu(dugum.AltDugum

); } dugum.veri = null; } public int VerileriOkuma(String DosyaIsmi)  throws Exception { FileInputStream in = null; try { File DosyaIcerigi = new File(DosyaIsmi); in = new FileInputStream(DosyaIcerigi); } catch ( Exception e) { System.err.println( "Veri dosyası açılamıyor : " + DosyaIsmi + "\n" + e); return 0; } BufferedReader bin = new BufferedReader(new InputStreamReader(in) ); String input; while(true) { input = bin.readLine(); if (input == null) { System.err.println( "Veri dosyasında veriler bulunamadı : " + DosyaIsmi + "\n"); return 0; } if (input.startsWith("//")) continue; if (input.equals("")) continue; break; } StringTokenizer tokenizer = new StringTokenizer(input); OznitelikNumarasi = tokenizer.countTokens(); if (OznitelikNumarasi <= 1) { System.err.println( "Okunan Satir : " + input); System.err.println( "Nitelikleri doğrultusunda isimleri elde edilemedi..."); System.err.println( "En azından bir giriş öznitelik ve bir çıkış öznitelik bekleniyor..."); return 0; } EtkiAlanlari = new Vector

; for (int i=0; i < OznitelikNumarasi; i++) EtkiAlanlari

= new Vector(); OznitelikIsimleri = new String

; for (int i=0; i < OznitelikNumarasi; i++) { OznitelikIsimleri

  = tokenizer.nextToken(); } while(true) { input = bin.readLine(); if (input == null) break; if (input.startsWith("//")) continue; if (input.equals("")) continue; tokenizer = new StringTokenizer(input); int numtokens = tokenizer.countTokens(); if (numtokens != OznitelikNumarasi) { System.err.println( "Okunan : " + kok.veri.size() + " data"); System.err.println( "Okunan Son Satir : " + input); System.err.println( "Beklenen  " + OznitelikNumarasi  + " Degerler"); return 0; } DataPoint point = new DataPoint(OznitelikNumarasi); for (int i=0; i < OznitelikNumarasi; i++) { point.OzNitelikleri

  = SembolDegeriniGetir(i, tokenizer.nextToken() ); } kok.veri.addElement(point); } bin.close(); return 1; } public void AgaciYazdirma(TreeNode dugum, String sekme) { int DegeriDisariAlmakIcin = OznitelikNumarasi-1; if (dugum.AltDugum == null) { int []degerler = ButunDegerleriGetir(dugum.veri, DegeriDisariAlmakIcin ); if (degerler.length == 1) { System.out.println(sekme + "\t" + OznitelikIsimleri

+ " = \"" + EtkiAlanlari

.elementAt(degerler<0>

) + "\";"); return; } System.out.print(sekme + "\t" + OznitelikIsimleri

+ " = {"); for (int i=0; i < degerler.length; i++) { System.out.print("\"" + EtkiAlanlari

.elementAt(degerler

) + "\" "); if ( i != degerler.length-1 ) System.out.print( " , " ); } System.out.println( " };"); return; } int DegerNumarasi = dugum.AltDugum.length; for (int i=0; i < DegerNumarasi; i++) { System.out.println(sekme + "if( " + OznitelikIsimleri

+ " == \"" + EtkiAlanlari

.elementAt(i) + "\") {" ); AgaciYazdirma(dugum.AltDugum

, sekme + "\t"); if (i != DegerNumarasi-1) System.out.print(sekme +  "} else "); else System.out.println(sekme +  "}"); } } public void KararAgaciOlusturma() { AyristirmaDugumu(kok); AgaciYazdirma(kok, ""); } public static void main(String[] args) throws Exception { int num = args.length; if (num != 1) { System.out.println("Komut satirindan veri dosyasinin adini belirtmeniz gerekiyor... " ); return; } ID3 Id3Sinifimiz = new ID3(); long BaslamaZamani = System.currentTimeMillis(); int durum = Id3Sinifimiz.VerileriOkuma(args<0>

); if (durum <= 0) return; Id3Sinifimiz.KararAgaciOlusturma(); long BitisZamani = System.currentTimeMillis(); long ToplamSure = (BitisZamani-BaslamaZamani)/1000; System.out.println( ToplamSure + " Seconds"); } }

ID3Test.JavaID3Test.Java

package id3_algoritmalari; public class ID3Test { public static void main(String[] args) throws Exception { ID3.main(new String[]{"c:/nano.txt"}); } } nuc olarak ekran ciktisi asagida ki gibidir ;