---

SON.java

gehe zur Dokumentation dieser Datei

/*
 * $Source: /shared/cvsroot/diplom/app/src/java/de/picana/clusterer/SON.java,v $
 * $Author: mstolpe $
 * $Date: 2003/04/22 09:51:28 $
 * $Revision: 1.5 $
 * $Release$ 
 *
 * Created on 5. M?rz 2003, 21:50
 *
 * Copyright 2002 by Marco Stolpe
 */

package de.picana.clusterer;

import de.picana.control.*;
import de.picana.logging.*;
import de.picana.math.*;

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

import weka.core.*;


public class SON extends Clusterer {
    
    protected static final int METHOD_KOHONEN = 0;
    protected static final int METHOD_WTAN = 1;
    protected static final int NEIGH_GAUSSIAN = 0;
    protected static final int NEIGH_WTAN = 1;
    protected static final int NEIGH_KOHONEN = 2;
    protected static final int TOPO_SQUARE = 0;
    protected static final int TOPO_HEXA = 1;
    protected static final int ADPT_STEP = 0;
    protected static final int ADPT_CONT = 1;
    protected static final int ADPT_SNNS = 2;
    protected static final int ADPT_PICANA = 3;

    protected int cycles;
    protected double radius;
    protected String preset;
    
    protected int method;
    protected int neigh;
    protected int topo;
    protected int adpt;
     
    protected int width;
    protected int height;
    
    protected double adpt_height;
    protected double adpt_radius;
    protected double mult_height;
    protected double mult_radius;
    protected double dist_winner;

    protected int micro_step;
    protected int step;
    protected int nr_examples;
    
    protected double b;
    protected int dim;
    
    protected List centroids;
    protected List freq_table;
    protected Map freq_htable;
    
    protected long time_total;
    
    
    
    public SON() {
    }
    
    
    public void init(ParameterSet params, Logger logger) {
        
        super.init(params, logger);
        
        cycles = 100;
        try {
            cycles = Integer.parseInt((String)params.getParameter("cycles"));
        } catch (NumberFormatException nfe) {}
        
        radius = 0.0;
        try {
            radius = Double.parseDouble((String)params.getParameter("radius"));
        } catch (NumberFormatException nfe) {}
        
        preset = "WTAN";
        
        if ((String)params.getParameter("preset") != null) {
            
            preset = ((String)params.getParameter("preset")).toUpperCase();
            
            if (preset.equals("WTAN")) {
                method = METHOD_WTAN;
                topo = TOPO_SQUARE;
                neigh = NEIGH_WTAN;
                adpt = ADPT_PICANA;
            }
            if (preset.equals("SOM_SQUARE")) {
                method = METHOD_KOHONEN;
                topo = TOPO_SQUARE;
                neigh = NEIGH_GAUSSIAN;
                adpt = ADPT_STEP;
            }
            if (preset.equals("SOM_HEXA")) {
                method = METHOD_KOHONEN;
                topo = TOPO_HEXA;
                neigh = NEIGH_GAUSSIAN;
                adpt = ADPT_STEP;
            }
            if (preset.equals("QSOM_SQUARE")) {
                method = METHOD_KOHONEN;
                topo = TOPO_SQUARE;
                neigh = NEIGH_KOHONEN;
                adpt = ADPT_PICANA;
            }
            if (preset.equals("QSOM_HEXA")) {
                method = METHOD_KOHONEN;
                topo = TOPO_HEXA;
                neigh = NEIGH_KOHONEN;
                adpt = ADPT_PICANA;
            }
        }
    }
    
    
    public void buildClusterer(Instances set) throws TaskException {
        
        statwriter.println("algo_clusterer_name:SON");
        statwriter.println("algo_clusterer_cycles:" + cycles);
        statwriter.println("algo_clusterer_radius:" + radius);
        statwriter.println("algo_clusterer_preset:" + preset);
        statwriter.println("algo_clusterer_model:" + modelfile);
        statwriter.println("algo_clusterer_training_set:" + infile);
        
        time_total = System.currentTimeMillis();
        
        // Initialisierung
        
        dim = set.numAttributes();
        
        width  = (int)Math.ceil(Math.sqrt((double)num_clusters));
        height = num_clusters / width;
        if ((num_clusters % width) != 0)
            height++;

        micro_step = 1;
              
        freq_htable = new HashMap();
        
        int i, j;

        MLVector vec;
        Instance inst;
        Integer freq;
            
        // build frequency hash table
        
        logger.info(LOGSRC, "Build frequency table from " + training_set.numInstances() + " instances ...");
        for (i=0; i < training_set.numInstances(); i++) {
            vec = new MLVector(training_set.instance(i));
            freq = (Integer)freq_htable.get(vec);
            
            freq_htable.put(vec, (freq==null) ? ONE :
                new Integer(freq.intValue() + 1));
        }
        logger.info(LOGSRC, "frequency table containing " + freq_htable.size() + " instances built.");
            
            
        // schreibe die Instanzen in neue Liste
        // Instanzen in neue Liste
            
        freq_table = new ArrayList();
            
        Iterator iter = freq_htable.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry)iter.next();
            vec = (MLVector)entry.getKey();
            freq = (Integer)entry.getValue();
            freq_table.add(vec);
        }
        
        
        // Generiere Startwerte f?r die Vektoren des Netzes durch zuf?llige
        // Auswahl von Instanzen aus der Trainingsmenge und zuf?lliger Ver?nderung
        // der Instanzen
        
        centroids = new ArrayList();
        
        MLVector rand_vec;
        int rand_index;
        
        for (int c=0; c < num_clusters; c++) {
            
            rand_index = rand.nextInt(freq_table.size());
            rand_vec = MLVector.getRandom(
                (MLVector)freq_table.get(rand_index), radius);
            
            centroids.add(rand_vec);
        }
        
        for (i=0; i < centroids.size(); i++) {
            logger.debug(LOGSRC, "weight[" + i + "] = " + (MLVector)centroids.get(i));
        }
        
        // Parameter b
        
        b = Math.pow (0.005, (double)(1.0 /
            ((double)set.numInstances() * (double)cycles)));
        
        // Wiederhole das Training f?r cycles Lernschritte
        
        for (int c=0; c < cycles; c++) {
        
            logger.verbose(LOGSRC, "Cycle: " + (c+1));
            
            // Trainiere das Netz durch Auswahl einer Instanz aus der
            // Indextabelle und aktualisiere die Tabelle
        
            freq_table = new ArrayList();
            
            iter = freq_htable.entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry entry = (Map.Entry)iter.next();
                vec = (MLVector)entry.getKey();
                freq = (Integer)entry.getValue();
                vec.freq = freq.intValue();
                freq_table.add(vec);
            }
            
            while (freq_table.size() > 0) {
                
                rand_index = rand.nextInt(freq_table.size());
                vec = (MLVector)freq_table.get(rand_index);
                vec.freq--;
                
                if (vec.freq == 0)
                    freq_table.remove(rand_index);
                               
                adpt_height = b;
                adpt_radius = b;
                mult_height = 0.9999;
                mult_radius = 0.9999;
                nr_examples = set.numInstances();
                step = c;
                
                if (preset.startsWith("SOM")) {
                    adpt_height = 1.0;
                    adpt_radius = width;
                    nr_examples = cycles;
                }
                
                if ((adpt == ADPT_STEP) || (adpt == ADPT_PICANA))
                    update ();
                
                // trainiere das Netz mit diesem Vektor
                train(vec);
            }
            
            //for (i=0; i < centroids.size(); i++) {
            //    logger.debug(LOGSRC, "weight[" + i + "] = " + (MLVector)centroids.get(i));
            //}
        }
        
        time_total = System.currentTimeMillis() - time_total;
        
        logger.info(LOGSRC, "Algorithm took " + getTimeString(time_total));
        
        for (i=0; i < centroids.size(); i++) {
            logger.verbose(LOGSRC, "centroid[" + i + "] = " + (MLVector)centroids.get(i));
        }
        
        statwriter.println("time_clusterer_total:" + time_total);
    }

    
    public void saveModel(String filename) throws TaskException {
        
        try {
            File outfile = new File(filename);
            FileOutputStream out = new FileOutputStream(outfile);
            PrintWriter pw = new PrintWriter(out);
        
            for (int att=0; att < training_set.numAttributes(); att++) {
                pw.print(training_set.attribute(att).name());
                if (att != training_set.numAttributes()-1)
                    pw.print(",");
            }
            pw.println();
            
            for (int i=0; i < centroids.size(); i++) {
                MLVector vec = (MLVector)centroids.get(i);    
            
                for (int j=0; j < vec.value.length; j++) {
             
                    pw.print(vec.value[j]);
                    if (j != vec.value.length-1) {
                        pw.print(",");    
                    }
                }
                pw.println();
            }
            
            pw.close();
            
        } catch (Exception e) {
            throw new TaskException(e.toString());
        }
    }
    
    protected double dist_euklidian(int x1, int y1, int x2, int y2) {
        double x = x1 - x2;
        double y = y1 - y2;
        return Math.sqrt ( x*x + y*y );
    }
    
    protected double dist_hexa(int x1, int y1, int x2, int y2) {
        double dist;
        double val = x1 - x2;
        if (((y1 - y2) % 2) != 0)
            val = Math.abs(val) - 0.5;
         dist = val * val;
        val = ((y1-y2)*(y1-y2))*0.866025404;
        dist += val;
        dist = Math.sqrt(dist);
        return dist;
    }
    
    protected double neigh_gaussian() {
        
        //logger.debug(LOGSRC, "dist_winner = " + dist_winner +
        //                   ", mult_height = " + mult_height +
        //                   ", mult_radius = " + mult_radius);
        
        return mult_height * Math.pow (Math.E,
            -( (dist_winner / mult_radius) * (dist_winner / mult_radius) ));
    }
    
    protected double neigh_wtan() {
        // Achtung! mult_height ist unser Eta

        if (dist_winner >= 1e-10 )
        {
            //if (dist_winner < Math.sqrt(dim * (15.0/255.0*255.0*3.0)))
            //    return mult_height * -0.1;
            //else
                //return pow(mult_height,2.0) * (1.0 / (pow(dist_winner, 2.99) + 1.0)); ***
                return Math.pow(mult_height,2.0) * (1.0 / (Math.pow(dist_winner * 441.6729, 1.5) + 1.0));
        }
        //return pow((0.2 * mult_height),3.0) * 1.0;
        //return 0.5 * mult_height; ***
        return 0.5 * mult_height;
        
        // *** Bei 10 und 20 Neuronen, gute Ergebnisse schon bei 1 Zyklus
        //     sehr gute Ergebnisse ab 5 Zyklen
        //     ab 5 Zyklen insbesondere auch konstant gleichm??ige Ergebnisse
        //     bei noch mehr Zyklen kaum noch Ergebnisverbesserung
    }
    
    
    protected double neigh_kohonen() {
        // return 0.5 * mult_height * pow (2.718281828, -( (dist_winner / mult_radius) *
        //                                          (dist_winner / mult_radius) ));

        // Wichtige Variablen:
        // micro_step

        // Varianten, die funktioniert!
        // return 0.1 * pow(mult_height,2) * (1.0 /(1000 * pow(dist_winner, 3) + 1.0));
        // return 0.01 * pow(mult_height,2) * (1.0 /(1000 * pow(dist_winner, 2) + 1.0));
        // return 0.01 * pow(mult_height,2) * (1.0 /((100+micro_step) * pow(dist_winner, 5) + 1.0));
        // return 0.5 * mult_height * (1.0 /((100+micro_step) * pow(dist_winner, 3) + 1.0));
        // return 0.3 * mult_height * (1.0 /(pow(micro_step, 9) * dist_winner + 1.0)); ***

        return 0.3 * mult_height * (1.0 /(Math.pow(micro_step, 9) * dist_winner + 1.0));
        
        // *** ansatzweise brauchbarer Ansatz bei 20 bis 40 Zyklen
    }
    
    
    protected int train(MLVector input) {
        int i;
        int winner = -1;
        double n = 0.0;
        MLVector weight;
        MLVector sub;
        
        if (method == METHOD_WTAN)
        {
            winner = classify (input);

            for (i=0; i < num_clusters; i++)
            {
                weight = (MLVector)centroids.get(i);
                
                dist_winner = Distance.euklidian(
                    ((MLVector)centroids.get(winner)).value, weight.value);

                if (neigh == NEIGH_GAUSSIAN)
                    n = neigh_gaussian();
                if (neigh == NEIGH_WTAN)
                    n = neigh_wtan();
                if (neigh == NEIGH_KOHONEN)
                    n = neigh_kohonen();
                
                // Gewicht anpassen gem?? weight = weight + n * (input - weight)
                
                
                sub = MLVector.sub(input, weight);
                sub.mult(n);
                //logger.debug(LOGSRC, "input = " + input + ", weight = " + weight + ", sub*n = " + sub + ", n = " + n);
                weight.add(sub);
                
                //logger.debug(LOGSRC, "newweight = " + weight);
            }
        }

        if (method == METHOD_KOHONEN)
        {
            winner = classify (input);

            int x, y, xw, yw;

            xw = winner % width;
            yw = winner / width;

            for (i=0; i < num_clusters; i++)
            {
                weight = (MLVector)centroids.get(i);
                
                x = i % width;
                y = i / width;

                if (topo == TOPO_SQUARE)
                    dist_winner = dist_euklidian (x, y, xw, yw);

                if (topo == TOPO_HEXA)
                    dist_winner = dist_hexa (x, y, xw, yw);
                
                if (neigh == NEIGH_GAUSSIAN)
                    n = neigh_gaussian();
                if (neigh == NEIGH_WTAN)
                    n = neigh_wtan();
                if (neigh == NEIGH_KOHONEN)
                    n = neigh_kohonen();

                //if ((micro_step % training_set.numInstances()) == 0) {
                //    logger.debug(LOGSRC, "e^x = " + Math.pow(Math.E, -((dist_winner/mult_radius) * (dist_winner/mult_radius))));
                //    logger.debug(LOGSRC, "n = " + n + ", mh = " + mult_height);
                //}
                
                // Gewicht anpassen gem?? weight = weight + n * (input - weight)
                
                //logger.debug(LOGSRC, "n = " + n);
                sub = MLVector.sub(input, weight);
                
                //logger.debug(LOGSRC, "sub = " + sub);
                
                sub.mult(n);
                
                //logger.debug(LOGSRC, "input = " + input + ", weight = " + weight + ", sub*n = " + sub);
                weight.add(sub);
                
                //logger.debug(LOGSRC, "newweight = " + weight);
            }
            
            //logger.debug(LOGSRC, "");
        }
        
        micro_step++;
        update ();

        return winner;
    }
    
    
    protected int classify(MLVector input) {
    
        int winner = -1;
        double akt_dist;
        double min_dist;
        
        // Search Winner

        min_dist = Double.MAX_VALUE;
    
        for (int i=0; i < num_clusters; i++)
        {
            akt_dist = Distance.euklidian(
                input.value, ((MLVector)centroids.get(i)).value);
            
            if (akt_dist < min_dist)
            {
                min_dist = akt_dist;
                winner = i;
            }
        }

        return winner;    
    }
    
    
    protected void update() {
        
        switch (adpt)
        {
            case ADPT_STEP:
                mult_radius = (adpt_radius / (double)nr_examples) *
                               (double)(nr_examples - step);
                mult_height = (adpt_height / (double)nr_examples) *
                               (double)(nr_examples - step);
                break;

            case ADPT_CONT:
                mult_radius = (adpt_radius / (double)nr_examples) *
                               (double)(nr_examples - step);
                mult_height = (adpt_height / (double)nr_examples) *
                               (double)(nr_examples - step);
                break;

            case ADPT_SNNS:
                adpt_height *= mult_height;
                adpt_radius *= mult_radius;
                break;

            case ADPT_PICANA:
                mult_radius = Math.pow (adpt_radius, micro_step);
                mult_height = Math.pow (adpt_height, micro_step);
                break;
        }
    }
}

---