lfsmethods.java

这是关于数据挖掘的一些算法

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    LFSMethods.java
 *    Copyright (C) 2007 Martin Gütlein
 *
 */
package weka.attributeSelection;

import weka.core.FastVector;
import weka.core.Instances;
import weka.core.Utils;

import java.io.Serializable;

import java.util.BitSet;
import java.util.Hashtable;


/**
 * @author Martin Guetlein ([e-mail])
 * @version $Revision: 1.1 $
 */
public class LFSMethods {
  /** max-size of array bestGroupOfSize, should be suffient */
  private final static int MAX_SUBSET_SIZE = 200;
  private BitSet m_bestGroup;
  private double m_bestMerit;
  private int m_evalsTotal;
  private int m_evalsCached;
  private BitSet[] m_bestGroupOfSize = new BitSet[MAX_SUBSET_SIZE];

  /**
   * empty constructor
   *
   * methods are not static because of access to inner class Link2 and
   * LinkedList2
   *
   */
  public LFSMethods() {
  }

  /**
   * @return best group found by forwardSearch/floatingForwardSearch
   */
  public BitSet getBestGroup() {
    return m_bestGroup;
  }

  /**
   * @return merit of best group found by forwardSearch/floatingForwardSearch
   */
  public double getBestMerit() {
    return m_bestMerit;
  }

  /**
   * @return best group of size found by forwardSearch
   */
  public BitSet getBestGroupOfSize(int size) {
    return m_bestGroupOfSize[size];
  }

  /**
   * @return number of cached / not performed evaluations
   */
  public int getNumEvalsCached() {
    return m_evalsCached;
  }

  /**
   * @return number totally performed evaluations
   */
  public int getNumEvalsTotal() {
    return m_evalsTotal;
  }

  /**
   * @return ranking (integer array) of attributes in data with evaluator (sorting is NOT stable!)
   */
  public int[] rankAttributes(Instances data, SubsetEvaluator evaluator,
                              boolean verbose) throws Exception {
    if (verbose) {
      System.out.println("Ranking attributes with " +
                         evaluator.getClass().getName());
    }

    double[] merit = new double[data.numAttributes()];
    BitSet group = new BitSet(data.numAttributes());

    for (int k = 0; k < data.numAttributes(); k++) {
      if (k != data.classIndex()) {
        group.set(k);
        merit[k] -= evaluator.evaluateSubset(group);
        m_evalsTotal++;
        group.clear(k);
      } else {
        merit[k] = Double.MAX_VALUE;
      }

      if (verbose) {
        System.out.println(k + ": " + merit[k]);
      }
    }

    int[] ranking = Utils.sort(merit);

    if (verbose) {
      System.out.print("Ranking [ ");

      for (int i = 0; i < ranking.length; i++) {
        System.out.print(ranking[i] + " ");
      }

      System.out.println("]\n");
    }

    return ranking;
  }

  /**
   * Performs linear forward selection
   *
   * @param cacheSize         chacheSize (times number of instances) to store already evaluated sets
   * @param startGroup        start group for search (can be null)
   * @param ranking                ranking of attributes (as produced by rankAttributes), no ranking would be [0,1,2,3,4..]
   * @param k                                number of top k attributes that are taken into account
   * @param incrementK        true -> fixed-set, false -> fixed-width
   * @param maxStale                number of times the search proceeds even though no improvement was found (1 = hill-climbing)
   * @param forceResultSize        stopping criteria changed from no-improvement (forceResultSize=-1) to subset-size
   * @param data
   * @param evaluator
   * @param verbose
   * @return                                BitSet, that cotains the best-group found
   * @throws Exception
   */
  public BitSet forwardSearch(int cacheSize, BitSet startGroup, int[] ranking,
                              int k, boolean incrementK, int maxStale, int forceResultSize,
                              Instances data, SubsetEvaluator evaluator, boolean verbose)
    throws Exception {
    if ((forceResultSize > 0) && (maxStale > 1)) {
      throw new Exception("Forcing result size only works for maxStale=1");
    }

    if (verbose) {
      System.out.println("Starting forward selection");
    }

    BitSet bestGroup;
    BitSet tempGroup;
    int bestSize = 0;
    int tempSize = 0;
    double bestMerit;
    double tempMerit = 0;
    Link2 link;
    LinkedList2 list = new LinkedList2(maxStale);
    Hashtable alreadyExpanded = new Hashtable(cacheSize * data.numAttributes());
    int insertCount = 0;
    int stale = 0;
    boolean improvement;
    int thisK = k;
    int evalsTotal = 0;
    int evalsCached = 0;

    bestGroup = (BitSet) startGroup.clone();

    String hashKey = bestGroup.toString();
    bestMerit = evaluator.evaluateSubset(bestGroup);

    if (verbose) {
      System.out.print("Group: ");
      printGroup(bestGroup, data.numAttributes());
      System.out.println("Merit: " + tempMerit);
      System.out.println("----------");
    }

    alreadyExpanded.put(hashKey, new Double(bestMerit));
    insertCount++;
    bestSize = bestGroup.cardinality();

    //the list is only used if best-first search is applied
    if (maxStale > 1) {
      Object[] best = new Object[1];
      best[0] = bestGroup.clone();
      list.addToList(best, bestMerit);
    }

    while (stale < maxStale) {
      improvement = false;

      //best-first: take first elem from list
      if (maxStale > 1) {
        if (list.size() == 0) {
          stale = maxStale;

          break;
        }

        link = list.getLinkAt(0);
        tempGroup = (BitSet) (link.getData()[0]);
        tempGroup = (BitSet) tempGroup.clone();
        list.removeLinkAt(0);

        tempSize = 0;

        for (int i = 0; i < data.numAttributes(); i++) {
          if (tempGroup.get(i)) {
            tempSize++;
          }
        }
      } else //hill-climbing 
        {
          tempGroup = (BitSet) bestGroup.clone();
          tempSize = bestSize;
        }

      //set number of top k attributes that are taken into account
      if (incrementK) {
        thisK = Math.min(Math.max(thisK, k + tempSize), data.numAttributes());
      } else {
        thisK = k;
      }

      //temporarilly add attributes to current set
      for (int i = 0; i < thisK; i++) {
        if ((ranking[i] == data.classIndex()) || tempGroup.get(ranking[i])) {
          continue;
        }

        tempGroup.set(ranking[i]);
        tempSize++;
        hashKey = tempGroup.toString();

        if (!alreadyExpanded.containsKey(hashKey)) {
          evalsTotal++;
          tempMerit = evaluator.evaluateSubset(tempGroup);

          if (insertCount > (cacheSize * data.numAttributes())) {
            alreadyExpanded = new Hashtable(cacheSize * data.numAttributes());
            insertCount = 0;
          }

          alreadyExpanded.put(hashKey, new Double(tempMerit));
          insertCount++;
        } else {
          evalsCached++;
          tempMerit = ((Double) alreadyExpanded.get(hashKey)).doubleValue();
        }

        if (verbose) {
          System.out.print("Group: ");
          printGroup(tempGroup, data.numAttributes());
          System.out.println("Merit: " + tempMerit);
        }

        if (((tempMerit - bestMerit) > 0.00001) ||
            ((forceResultSize >= tempSize) && (tempSize > bestSize))) {
          improvement = true;
          stale = 0;
          bestMerit = tempMerit;
          bestSize = tempSize;
          bestGroup = (BitSet) (tempGroup.clone());
          m_bestGroupOfSize[bestSize] = (BitSet) (tempGroup.clone());
        }

        if (maxStale > 1) {
          Object[] add = new Object[1];
          add[0] = tempGroup.clone();
          list.addToList(add, tempMerit);
        }

        tempGroup.clear(ranking[i]);
        tempSize--;
      }

      if (verbose) {
        System.out.println("----------");
      }

      //handle stopping criteria
      if (!improvement || (forceResultSize == bestSize)) {
        stale++;
      }

      if ((forceResultSize > 0) && (bestSize == forceResultSize)) {
        break;
      }
    }

    if (verbose) {
      System.out.println("Best Group: ");
      printGroup(bestGroup, data.numAttributes());
      System.out.println();
    }

    m_bestGroup = bestGroup;
    m_bestMerit = bestMerit;
    m_evalsTotal += evalsTotal;
    m_evalsCached += evalsCached;

    return bestGroup;
  }

  /**
   * Performs linear floating forward selection
   * ( the stopping criteria cannot be changed to a specific size value )
   *
   *
   * @param cacheSize         chacheSize (times number of instances) to store already evaluated sets
   * @param startGroup        start group for search (can be null)
   * @param ranking                ranking of attributes (as produced by rankAttributes), no ranking would be [0,1,2,3,4..]
   * @param k                                number of top k attributes that are taken into account
   * @param incrementK        true -> fixed-set, false -> fixed-width
   * @param maxStale                number of times the search proceeds even though no improvement was found (1 = hill-climbing)
   * @param data
   * @param evaluator
   * @param verbose
   * @return                                BitSet, that cotains the best-group found
   * @throws Exception
   */
  public BitSet floatingForwardSearch(int cacheSize, BitSet startGroup,
                                      int[] ranking, int k, boolean incrementK, int maxStale, Instances data,
                                      SubsetEvaluator evaluator, boolean verbose) throws Exception {
    if (verbose) {
      System.out.println("Starting floating forward selection");
    }

    BitSet bestGroup;
    BitSet tempGroup;
    int bestSize = 0;
    int tempSize = 0;
    double bestMerit;