---

FastAML.java

gehe zur Dokumentation dieser Datei

/*
 * $Source: /shared/cvsroot/diplom/app/src/java/de/picana/clusterer/FastAML.java,v $
 * $Author: mstolpe $
 * $Date: 2003/04/22 09:51:27 $
 * $Revision: 1.6 $
 * $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 FastAML extends GenericML {
    
    private double rho;
    private String strategy;
    
    private List index_list;
    private List set_u;
    
    private MLVector corner;
    private double[] mean;
    private double[] max;
    private double[] min;
    private MLVector vec_a;
    private MLVector vec_b;
    private double max_dist;
    private int sum_pruned = 0;
    
    private long time_sort;
    
    //-----------------------------
    
    
    class IndexComparator implements Comparator {
     
        private int component;
        
        public IndexComparator(int component) {
            this.component = component;
        }
        
        public int compare(Object o1, Object o2) {
            MLVector vec1 = (MLVector)o1;
            MLVector vec2 = (MLVector)o2;
            if (vec1.value[component] > vec2.value[component])
                return 1;
            if (vec1.value[component] < vec2.value[component])
                return -1;
            return 0; 
        }
    }
    
    class MidComparator implements Comparator {
        
        public MidComparator() {
        }
        
        public int compare(Object o1, Object o2) {
            MLVector vec1 = (MLVector)o1;
            MLVector vec2 = (MLVector)o2;
            if (Distance.euklidian(vec1.value,mean) > Distance.euklidian(vec2.value,mean))
                return -1;
            if (Distance.euklidian(vec1.value,mean) < Distance.euklidian(vec2.value,mean))
                return 1;
            return 0; 
        }
    }
    

    
    public FastAML() {
    }
    
    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) {}
                
        strategy = (String)params.getParameter("pruning");
    }
    
    
    protected void buildFirst() {
        
        statwriter.println("algo_clusterer_name:FastAML");
        statwriter.println("algo_clusterer_rho:" + rho);
        statwriter.println("algo_clusterer_pruning:" + strategy);
        
        int i, j;
        MLVector vec;
        int index;
        Integer freq;
        
        logger.info(LOGSRC, "Build sorted index table ...");
        
        time_sort = System.currentTimeMillis();
        
        set_u = new LinkedList();
        min = new double[dim];
        for (i=0; i < dim; i++)
            min[i] = Double.MAX_VALUE;
        max = new double[dim];
        for (i=0; i < dim; i++)
            max[i] = 0.0;
            
        for (i=0; i < freq_table.size(); i++) {
            
            vec = (MLVector)freq_table.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);
            
                if (vec.value[j] > max[j])
                    max[j] = vec.value[j];
                if (vec.value[j] < min[j])
                    min[j] = vec.value[j];
            }
            
            set_u.add(vec);
        }
        
        // get mid(HC(U))
        
        corner = new MLVector(dim);
        
        mean = new double[dim];
        
        for (i=0; i < dim; i++) {
            mean[i] = (max[i] + min[i]) / 2.0;
        }
        
        // get sorted index table
        
        if (strategy.equals("rand")) {
            index_list = getRandIndexList();
        } else if (strategy.equals("lexi")) {
            index_list = getLexiIndexList();
        } else if (strategy.equals("comp")) {
            index_list = getCompIndexList();
        } else if (strategy.equals("mid")) {
            index_list = getMidIndexList();
        }
        
        time_sort = System.currentTimeMillis() - time_sort;
        
        logger.info(LOGSRC, "sorted index table built.");
        
        logger.info(LOGSRC, "Sorting took " + getTimeString(time_sort)); 
        
        // start algorithm
        
        max_dist = 0.0;
        
        for (i=0; i < index_list.size(); i++) {
            vec = (MLVector)index_list.get(i);
            if (!vec.pruned)
                TryToPrune(vec);
        }
    
        logger.debug(LOGSRC, vec_a.toString() + " - " + 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.");
        
       
        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);
    }
    
     
    protected void TryToPrune(MLVector p) {
        
        MLVector q = null;
        MLVector temp;
        double dist = 0.0;
        double max_qdist = 0.0;
        boolean prune = false;
        int pruned = 0;
        
        // get point q furthest from p
        
        Iterator set_u_iter = set_u.iterator();
        while (set_u_iter.hasNext()) {
            temp = (MLVector)set_u_iter.next();
            if (p.equals(temp)) {
                temp.pruned = true;
                set_u_iter.remove();  // remove p in each case
            } else {
                dist = Distance.euklidian(p.value,temp.value);
                if (dist > max_qdist) {
                    max_qdist = dist;
                    q = temp;
                    if (max_qdist == max_dist)
                        logger.info(LOGSRC, "found new max_qdist = " + max_qdist);
                }
            }
        }
        
        if (max_qdist > max_dist) {  // if possible, prune points in set_u
            
            logger.info(LOGSRC, "found new maximum distance = " + max_qdist);
            
            max_dist = max_qdist;
            vec_a = p;
            vec_b = q;
        
            set_u_iter = set_u.iterator();
            while (set_u_iter.hasNext()) {
                temp = (MLVector)set_u_iter.next();

                if (Distance.euklidian(temp.value, calculateCorner(temp).value) > max_dist) {
                    prune = false;
                } else {
                    temp.pruned = true;
                    set_u_iter.remove();
                    pruned++;
                }
            }
            
            logger.info(LOGSRC, "Pruned " + pruned + " instances.");
            sum_pruned += pruned;
        }
    }
    
    
    protected void buildRest() {
        
        int i, j, k;
        MLVector vec = null;
        MLVector vec_a;
        MLVector vec_b;
        
        double max_dist;
        double min_dist;
        double act_dist;
        
        for (i=0; i < num_clusters-2; i++) {
            
            max_dist = 0.0;
            
            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) {
                    vec = vec_a;
                    max_dist = min_dist;
                }
            }

            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] = max[i];
            else
                corner.value[i] = min[i];
        }
        return corner;
    }
    
    
    protected List getRandIndexList() {
        return freq_table;
    }
    
    protected List getLexiIndexList() {
        Collections.sort(freq_table);
        return freq_table;
    }
    
    protected List getCompIndexList() {
        
        MLVector vec = null;
        List[] sorted_indexl = new ArrayList[dim];
        List sorted = new ArrayList();
        int i;
        
        for (i=0; i < dim; i++) {
            sorted_indexl[i] = new ArrayList();
            for (int j=0; j < freq_table.size(); j++) {
                vec = (MLVector)freq_table.get(j);
                sorted_indexl[i].add(vec);
            }
            Collections.sort(sorted_indexl[i], new IndexComparator(i));
        }
        
        i=0;
        int min = 0;
        int max = freq_table.size()-1;
        while (i < (dim*freq_table.size())) {
            for (int c=0; c < dim; c++) {
                sorted.add(sorted_indexl[c].get(min));
                i++;
            }
            min++;
            if (i < (dim*freq_table.size())) {
                for (int c=0; c < dim; c++) {
                    sorted.add(sorted_indexl[c].get(max));
                    i++;
                }
                max--;
            }
        }
        System.out.println(dim*freq_table.size() + " = " + sorted.size());
        return sorted;
    }
    
    protected List getMidIndexList() {
        Collections.sort(freq_table, new MidComparator());
        return freq_table;
    }
}

---