Kapitel 13: "Methoden der Künstlichen Intelligenz"

"KMeans.java"


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

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

private int[] myprototype;
private double prototypen[][];
private int protolabel[];
private int k;

// Konstruktor
public KMeans(int anzprototypen) {
k = anzprototypen;
trainingsdaten = new double[1000][192];
label = new int[1000];
myprototype = new int[1000];
prototypen = new double[k][192];
protolabel = new int[k];
}

// 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];
}

// Euklidischer Abstand zwischen zwei Vektoren
private double distance(double[] v1, double[] v2) {
double dist = 0, diff = 0;
for (int i = 0; i < v1.length; i++) {
diff = v1[i] - v2[i];
dist += diff*diff;
}
return Math.sqrt(dist);
}

public void train(int abbruchkrit, int anzIter, double epsilon) {
// Prototypen zufällig aus der Trainingsmenge wählen
double d = Double.MAX_VALUE;
int nearestprototype = 0;
Random random = new Random();
double sum[][] = new double[k][192];

for (int i = 0; i < k; i++) {
int rand = random.nextInt(trainingsdaten.length);
prototypen[i] = trainingsdaten[rand];
protolabel[i] = label[rand];
}

while ( (0 < anzIter & 1 == abbruchkrit) |
(d > epsilon & 2 == abbruchkrit) ) {

// ***************************************************************
// Expectationschritt:
// - Trainingsdaten zu den nächstgelegenen Protoypen zuordnen
for (int i = 0; i < 1000; i++) {
d = Double.MAX_VALUE;
for (int j = 0; j < k; j++) {
if (d > distance(trainingsdaten[i], prototypen[j])) {
nearestprototype = j;
d = distance(trainingsdaten[i], prototypen[j]);
}
}
myprototype[i] = nearestprototype;
}
// ***************************************************************

// ***************************************************************
// Maximizationschritt:
// - Prototypen werden zu den jeweiligen Daten zentriert
int xicount[] = new int[k];
double[][] prototypenref = new double[k][192];

for (int i = 0; i < k; i++)
for (int j = 0; j < 192; j++)
sum[i][j] = 0;

// Schwerpunkte der Prototypen neu berechen
for (int i = 0; i < 1000; i++) {
// Wieviele Vektoren gehören zu diesem Prototypen
xicount[myprototype[i]]++;

// Addition der Vektoren zu jedem Prototypen
for (int j = 0; j < 192; j++)
sum[myprototype[i]][j] += trainingsdaten[i][j];
}

for (int i = 0; i < k; i++) {
for (int j = 0; j < 192; j++) {
prototypenref[i][j] = prototypen[i][j];
prototypen[i][j] = (prototypen[i][j] + sum[i][j]) / (xicount[i] + 1) ;
}
}
// ***************************************************************

// Abstandsberechnung der alten gegenüber den neuen Prototypen
d = 0;
for(int i=0; i < k; i++)
d += distance(prototypen[i], prototypenref[i]);
anzIter--;
}

// ***************************************************************
// Korrektur des Labels an Hand der Zugehörigkeiten
for (int i=0; i < k; i++){
int ziffern[] = new int[10];

for (int j=0; j < 1000; j++)
if (myprototype[j]==i)
if (label[j]!=-1)
ziffern[label[j]]++;

int max=0;
for (int l=1; l < 10; l++)
if (ziffern[l] > ziffern[max])
max=l;

protolabel[i]=max;
}
// ***************************************************************

}

// k-means
public int classify(double[] y) {
int returnLabel;
double d;

returnLabel = -1;
d = Double.MAX_VALUE;
for (int i = 0; i < k; i++) {
if(d > distance(prototypen[i], y)) {
returnLabel = protolabel[i];
d = distance(prototypen[i], y);
}
}
return returnLabel;
}

public static void main(String[] args) {
// Abbruchkriterien
// (1) wird die Anzahl Iterationen (anzIterationen) gewählt
// (2) Veränderung der Positionen der Prototypen
int abbruchKriterium = 2;
double epsilon = 0.000001;
int anzPrototypen = 20;
int anzIterationen = 3;

KMeans classifier = new KMeans(anzPrototypen);
classifier.readData("digits-training.txt");
classifier.zentrierung();
classifier.train(abbruchKriterium, anzIterationen, epsilon);

// 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]))
er++;
er /= 1000;
System.out.println("Erkennungsrate = " + er);
}
}

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