---

FastAMLJ.java

gehe zur Dokumentation dieser Datei

/*
 * $Source: /shared/cvsroot/diplom/app/src/java/de/picana/clusterer/FastAMLJ.java,v $
 * $Author: mstolpe $
 * $Date: 2003/04/22 09:51:27 $
 * $Revision: 1.11 $
 * $Release$
 *
 * Created on 21. November 2002, 14:05
 *
 * 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 FastAMLJ extends GenericML {
    
    private double rho;
    private boolean pruning = true;
    
    private IndexList index_list;
    private IndexListIterator[] outer_iter_min;
    private IndexListIterator[] outer_iter_max;
    private IndexListIterator[] inner_iter_min;
    private IndexListIterator[] inner_iter_max;
    
    private MLVector[] corners;
    private MLVector corner;
    private double[] mean;
    private int numCorners;
    private boolean outer_finished;
    private boolean inner_finished;
    private HashMap max_index;
    private double max_dist;
    private int sum_pruned = 0;
    
    private long time_sort;
    
    
    public FastAMLJ() {
    }
    
    public void init(ParameterSet params, Logger logger) {
        
        super.init(params, logger);
        
        rho = 0.0;
        try {
            rho = Double.parseDouble((String)params.getParameter("rho"));
        } catch (NumberFormatException nfe) {}
        
        String p = (String)params.getParameter("pruning");
        if (p.equals("true"))
            pruning = true;
        else
            pruning = false;
    }
    
    
    protected void buildFirst() {
        
        statwriter.println("algo_clusterer_name:FastAMLJ");
        statwriter.println("algo_clusterer_rho:" + rho);
        statwriter.println("algo_clusterer_pruning:" + pruning);
        
        int i, j;
        MLVector vec;
        int index;
        Integer freq;
        
        logger.info(LOGSRC, "Build sorted index table ...");
        
        time_sort = System.currentTimeMillis();
        
        for (i=0; i < freq_table.size(); i++) {
            
            vec = (MLVector)freq_table.get(i);
            dim = vec.dim;
            
            for (j=0; j < vec.dim; j++) {
                vec.value[j] *= Math.pow(
                rho * ((double)vec.freq / (double)training_set.numInstances()) + (1-rho), rho);
            }
            
            //System.out.println(vec);
        }
        
        index_list = new IndexList(freq_table);
        
        time_sort = System.currentTimeMillis() - time_sort;
        
        logger.info(LOGSRC, "sorted index table built.");
        
        logger.info(LOGSRC, "Sorting took " + getTimeString(time_sort));
        
        // get corners
        
        mean = new double[dim];
        
        double min;
        double max;
        
        for (i=0; i < dim; i++) {
            vec = (MLVector)freq_table.get(index_list.getFirst(i));
            min = vec.value[i];
            vec = (MLVector)freq_table.get(index_list.getLast(i));
            max = vec.value[i];
            mean[i] = (max + min) / 2.0;
        }
        
        corner = new MLVector(dim);
        
        numCorners = (int)Math.pow(2, (double)dim);
        corners = new MLVector[numCorners];
        int bit;
        
        logger.debug(LOGSRC, "Find " + numCorners + " corners ...");
        
        for (i=0; i < numCorners; i++) {
            
            corners[i] = new MLVector(dim);
            
            for (j=0; j < dim; j++) {
                
                bit = (i & (1 << j)) >> j;
                
                if (bit == 0) {
                    index = index_list.getFirst(j);
                    vec = (MLVector)freq_table.get(index);
                    corners[i].value[j] = vec.value[j];
                } else {
                    index = index_list.getLast(j);
                    vec = (MLVector)freq_table.get(index);
                    corners[i].value[j] = vec.value[j];
                }
            }
            
            logger.debug(LOGSRC, "corner[" + i + "] = " + corners[i].toString());
        }
        
        logger.debug(LOGSRC, "corners found.");
        
        // outer loop
        
        max_dist = 0.0;
        max_index = new HashMap();
        
        outer_iter_min = new IndexListIterator[dim];
        outer_iter_max = new IndexListIterator[dim];
        inner_iter_min = new IndexListIterator[dim];
        inner_iter_max = new IndexListIterator[dim];
        
        for (i=0; i < dim; i++) {
            outer_iter_min[i] = index_list.iterator(i);
            outer_iter_max[i] = index_list.iteratorReverse(i);
        }
        
        outer_finished = false;
        while (!outer_finished) {
            
            //System.out.println(sum_pruned + " " + freq_table.size() + " " + i);
            
            for (i=0; i < dim; i++) {
                if (!(sum_pruned > (freq_table.size()-2))) {
                    if (outer_iter_min[i].hasNext()) {
                        index = outer_iter_min[i].next();
                        find_new_max_dist(index);
                        //System.out.println(sum_pruned + " " + freq_table.size() + " " + i);
                    }
                }
                if (!(sum_pruned > (freq_table.size()-2))) {
                    if (outer_iter_max[i].hasPrevious()) {
                        index = outer_iter_max[i].previous();
                        find_new_max_dist(index);
                        //System.out.println(sum_pruned + " " + freq_table.size() + " " + i);
                    }
                }
            }
            
            if (sum_pruned > (freq_table.size()-2))
                outer_finished = true;
            else if (outer_iter_min[0].nextIndex() > outer_iter_max[0].previousIndex())
                outer_finished = true;
        }
        
        for (i=0; i < dim; i++) {
            index_list.freeIterator(i, outer_iter_min[i]);
            index_list.freeIterator(i, outer_iter_max[i]);
        }
        
        
        Iterator keys = max_index.keySet().iterator();
        while (keys.hasNext()) {
            IntegerPair pair = (IntegerPair)keys.next();
            MLVector vec_a = (MLVector)freq_table.get(pair.a);
            MLVector vec_b = (MLVector)freq_table.get(pair.b);
            logger.debug(LOGSRC, "(" + pair.a + ") " + vec_a.toString() + " - " +
            "(" + pair.b + ") " + vec_b.toString() + " = " + max_dist);
        }
        
        statwriter.println("stat_Pruned:" + sum_pruned);
        
        logger.info(LOGSRC, "Pruned " + sum_pruned + " of " + freq_table.size() + " (" +
        (freq_table.size()-sum_pruned) + " left) instances in whole.");
        
        IntegerPair pair = (IntegerPair)getRandomElement(max_index.keySet());
        MLVector vec_a = (MLVector)freq_table.get(pair.a);
        MLVector vec_b = (MLVector)freq_table.get(pair.b);
        centroids.add(vec_a);
        logger.info(LOGSRC, "centroid[0] = " + vec_a.toString());
        centroids.add(vec_b);
        logger.info(LOGSRC, "centroid[1] = " + vec_b.toString());
        
        statwriter.println("time_clusterer_sort:" + time_sort);
    }
    
    
    private void find_new_max_dist(int index1) {
        
        MLVector vec1 = (MLVector)freq_table.get(index1);
        int index2;
        
        if (vec1.visited == false) {
            //System.out.println("Find max_dist for index " + index1);
            
            int i, j;
            
            for (i=0; i < dim; i++) {
                inner_iter_min[i] = index_list.iterator(i);
                inner_iter_max[i] = index_list.iteratorReverse(i);
            }
            
            inner_finished = false;
            while (!inner_finished) {
                
                boolean prune = false;
                
                for (i=0; i < dim; i++) {
                    
                    if (inner_iter_min[i].hasNext()) {
                        index2 = inner_iter_min[i].next();
                        if (find_new_max_dist(index1, index2))
                            prune = true;
                    }
                    if (inner_iter_max[i].hasPrevious()) {
                        index2 = inner_iter_max[i].previous();
                        if (find_new_max_dist(index1, index2))
                            prune = true;
                    }
                }
                
                if (prune && pruning)
                    prune();
                
                if (sum_pruned > freq_table.size()-2)
                    inner_finished = true;
                else if (inner_iter_min[0].nextIndex() > inner_iter_max[0].previousIndex())
                    inner_finished = true;
                
                //if (!inner_iter_min[0].hasNext() && !inner_iter_max[0].hasPrevious())
                //    inner_finished = true;
            }
            
            for (i=0; i < dim; i++) {
                index_list.freeIterator(i, inner_iter_min[i]);
                index_list.freeIterator(i, inner_iter_max[i]);
            }
            
            vec1.visited = true;
        }
    }
    
    
    private boolean find_new_max_dist(int index1, int index2) {
        
        MLVector vec1 = (MLVector)freq_table.get(index1);
        MLVector vec2 = (MLVector)freq_table.get(index2);
        
        double dist = Distance.euklidian(vec1.value, vec2.value);
        
        if (dist > max_dist) {
            max_index.clear();
            max_dist = dist;
            
            max_index.put(new IntegerPair(index1, index2), new Integer(1));
            logger.info(LOGSRC, "Found new maximum distance " + max_dist);
            return true;
            
        } else if (dist == max_dist) {
            max_index.put(new IntegerPair(index1, index2), new Integer(1));
        }
        return false;
    }
    
    
    private void prune() {
        int pruned = 0;
        int i, j;
        IndexListIterator iter;
        int pindex;
        MLVector pvec;
        boolean prune;
        
        for (i=0; i < dim; i++) {
            
            iter = index_list.iterator(i);
            while(iter.hasNext()) {
                pindex = iter.next();
                pvec = (MLVector)freq_table.get(pindex);
                
                if (pvec.pruned)
                    prune = true;
                else {
                    prune = true;
                    /*
                    for (j=0; j < numCorners; j++) {
                        if (Distance.euklidian(pvec.value, corners[j].value) > max_dist)
                            prune = false;
                    }
                     */
                    
                    if (Distance.euklidian(pvec.value, calculateCorner(pvec).value)
                        > max_dist)     prune = false;
                    
                    if (prune)
                        pruned++;
                }
                
                if (prune) {
                    pvec.pruned = true;
                    
                    iter.remove();
                }
            }
        }
        
        logger.info(LOGSRC, "Pruned " + pruned + " instances.");
        
        sum_pruned += pruned;
    }
    
    
    protected void buildRest() {
        
        int i, j, k;
        MLVector vec;
        MLVector vec_a;
        MLVector vec_b;
        List max_index = new ArrayList();
        
        double max_dist;
        double min_dist;
        double act_dist;
        
        for (i=0; i < num_clusters-2; i++) {
            
            max_dist = 0.0;
            max_index.clear();
            
            for (j=0; j < freq_table.size(); j++) {
                
                vec_a = (MLVector)freq_table.get(j);
                
                min_dist = Double.MAX_VALUE;
                
                for (k=0; k < centroids.size(); k++) {
                    
                    vec_b = (MLVector)centroids.get(k);
                    
                    act_dist = Distance.euklidian(vec_a.value, vec_b.value);
                    
                    if (act_dist < min_dist)
                        min_dist = act_dist;
                }
                
                if (min_dist > max_dist) {
                    
                    max_index.clear();
                    max_index.add(new Integer(j));
                    max_dist = min_dist;
                    
                } else if (min_dist == max_dist) {
                    
                    max_index.add(new Integer(j));
                }
            }
            
            Integer index = (Integer)getRandomElement(max_index);
            vec = (MLVector)freq_table.get(index.intValue());
            centroids.add(vec);
            logger.info(LOGSRC, "centroid[" + (i+2) + "] = " + vec.toString());
        }
        
        for (i=0; i < centroids.size(); i++) {
            
            vec = (MLVector)centroids.get(i);
            
            for (j=0; j < vec.dim; j++) {
                vec.value[j] /= Math.pow(
                rho * ((double)vec.freq / (double)training_set.numInstances()) + (1-rho), rho);
            }
        }
    }
    
    
    protected MLVector calculateCorner(MLVector vec) {
        
        for (int i=0; i < dim; i++) {
            
            if (vec.value[i] <= mean[i])
                
                corner.value[i] = ((MLVector)freq_table.get(index_list.getLast(i))).value[i];
            else
                corner.value[i] = ((MLVector)freq_table.get(index_list.getFirst(i))).value[i];
        }
        return corner;
    }
}

---