Kapitel 13: "Methoden der Künstlichen Intelligenz"

"Knn.java"


import java.io.*;
import java.util.StringTokenizer;

public class Knn {
// wir setzen alle Daten public, damit wir in einen einfachen Zugriff erhalten
public double[][] trainingsdaten;
public int[] label;

// Konstruktor
public Knn() {
trainingsdaten = new double[1000][192];
label = new int[1000];
}

// Methoden
public boolean readData(String filename){
String filenameIn = filename, sLine;
StringTokenizer st;

try {
FileInputStream fis = new FileInputStream(filenameIn) ;
InputStreamReader isr = new InputStreamReader(fis);
BufferedReader bur = new BufferedReader(isr);

int zaehler = 0;
while((sLine = bur.readLine()) != null) {
// lese das Ziffernbild ein
int count = 0;
for(int i = 0; i < 16; i++) {
// Wir zerlegen die Zeile in Ihre Bestandteile:
st = new StringTokenizer(sLine," ");
for(int j = 0; j < 12; j++)
trainingsdaten[zaehler][count++] = Double.parseDouble(st.nextToken());
sLine = bur.readLine();
}

// dekodiere das Label
int lab = -1; // es könnte sich um einen Outlier handeln
st = new StringTokenizer(sLine," ");
for(int i = 0; i < 10; i++) {
if(Double.parseDouble(st.nextToken()) == 1.0) {
lab = i;
break;
}
}
label[zaehler] = lab;
sLine = bur.readLine();
zaehler++;
}
} catch(ArrayIndexOutOfBoundsException eAIOOB) {
System.out.println("Es gab einen Indexfehler.");
} catch(IOException eIO) {
System.out.println("Konnte Datei "+ filenameIn +" nicht öffnen!");
}
return true;
}

public void zentrierung(){
// Ermittle das Zentrum der Daten
int m[] = new int[192];
for (int j=0; j < 192; j++){
for (int i=0; i < 1000; i++)
m[j]+=trainingsdaten[i][j];
m[j]/=1000;
}

// Zentriere die Daten
for (int i=0; i < 1000; i++)
for (int j=0; j < 192; j++)
trainingsdaten[i][j]-=m[j];
}

// k-nn
public int classify(double[] y, int k){
int returnLabel;
int freq[] = new int[10];
int lab[] = new int[k];
double dist[] = new double[k];
double d;

// Abstände auf unendlich setzen
for (int i=0; i < k; i++)
dist[i] = Double.POSITIVE_INFINITY;

// Abstand von y zu allen Vektoren der Trainingsmenge berechnen
// und die k-nächsten Nachbarn speichern
for (int i=0; i < 1000; i++) {
d = 0;

// Euklidischer Abstand
for (int j=0; j < 192; j++)
d += (y[j]-trainingsdaten[i][j]) * (y[j]-trainingsdaten[i][j]);

if (d > dist[k-1])
continue;

// die Entfernungen werden mit InsertionSort sortiert
for (int j=0; j < k; j++) {
if (d < dist[j]) {
for (int h=k-1; h > j; h--) {
dist[h] = dist[h-1];
lab[h] = lab[h-1];
}
dist[j] = d;
lab[j] = label[i];
break;
}
}
}

// nun wird demokratisch entschieden
for (int i=0; i < k; i++)
if (lab[i]!=-1)
freq[lab[i]]++;
returnLabel = -1;
int f = -1;
for (int i=0; i < 10; i++) {
if (f < freq[i]) {
f = freq[i];
returnLabel = i;
}
}

return returnLabel;
}

public static void main(String[] args){
Knn classifier = new Knn();
classifier.readData("digits-training.txt");

// Teste Trainingsdaten auf sich selber und ermittle
// die Erkennungsrate
double er = 0;
for (int i=0; i < 1000; i++)
if (classifier.label[i] == classifier.classify(classifier.trainingsdaten[i], 1))
er++;
er/=1000;
System.out.println("Erkennungsrate = "+er);
}
}

Picksel Media Marco Block © 2006-2009 – ImpressumKontakt
Gestaltung und Umsetzung Tobias Losch, www.picksel-media.de