partition.java

clustering data for the different techniques of data mining

/*
  Partition.java
  
  Definition of the class Partition
  
  (P)2002  Dana Cristofor

*/

/*

GAClust - Clustering categorical databases using genetic algorithms
Copyright (C) 2002  Dana Cristofor


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., 59 Temple Place, Suite 330, Boston, MA 02111-1307
USA

GAClust was written by Dana Cristofor ([e-mail]).

*/

import java.util.*;
import java.text.*;

/**
 * Partition
 *
 * @version 	1.0
 * @author	Dana Cristofor
 */
public class Partition
{
  protected int classFitnessType;
  protected int[] v;  // array of integers
  protected int size; // no. of elements

  protected int maxNoClasses; // maximum no. of classes (distinct elements)
  protected Hashtable classCard; // classes cardinalities, key (integer):
			         // class id, value (integer) class
			         // cardinality
  protected Hashtable classCode; // classes encodings, key is a
				 // String representing the
				 // original value, mapped to an
				 // Integer representing the
				 // encoding
  protected Hashtable classFitness; // we remember the fitness for each
				    // class of the partition; key
				    // (Integer): class number, value
				    // (Double): fitness of the class
  protected boolean cfIsValid;

  protected double fitness; // fitness of the partition

  // class fitness types
  static public final int CF_SYM_DIFF  = 1; // symmetrical difference
  static public final int CF_PROD      = 2; // |Cj|imp(Cj)
  static public final int CF_DIV       = 3; // imp(Cj) / |Cj|
  static public final int CF_POW       = 4; // 2^imp(Cj) / |Cj| 

  Partition(int size)
  {
    this(size, 0, CF_SYM_DIFF);
  }

  Partition(int size, int maxNoClasses)
  {
    this(size, maxNoClasses, CF_SYM_DIFF);
  }

  Partition(int size, int maxNoClasses, int classFitnessType)
  {
    this.size = size;
    v = new int[size];
    for (int i = 0; i < size; i++)
      v[i] = 0;  // initial values 0, no class is set yet
    this.maxNoClasses = maxNoClasses;
    classCard = new Hashtable();
    classCode = new Hashtable();
    classFitness = new Hashtable();
    fitness = 0.0;
    this.classFitnessType = classFitnessType;
    cfIsValid = false;
  }

  /** sets <code>rowid</code> to belong to class <code>c</code>,
   * updates the class cardinality of the new and old class to whom
   * rowid belongs */
  public void set(int rowid, int c)
  {
    // if new class equal the old class return
    if (v[rowid] == c)
      return;
    
    // otherwise update classCard info!

    // if v[rowid] already had a class number
    Integer oldClassNo = new Integer(v[rowid]);
    if (v[rowid] != 0)
      if (classCard.containsKey(oldClassNo))
	{
	  // if v[rowid] is unique
	  int card = ((Integer)classCard.get(oldClassNo)).intValue();
	  if (card == 1)
	    // remove this class from the map
	    classCard.remove(oldClassNo);
	  else
	    // decrement cardinality of previous class v[rowid]
	    classCard.put(oldClassNo, new Integer(card - 1)); 
	}
    
    // set new value
    v[rowid] = c;
    
    // increment the cardinality of new class val
    Integer newClassNo = new Integer(c);

    int newClassCard = 1;
    if (classCard.containsKey(newClassNo))
      newClassCard = ((Integer)classCard.get(newClassNo)).intValue() + 1;
   
    classCard.put(newClassNo , new Integer(newClassCard));
    
    cfIsValid = false;
  }

  /** @return the class of <code>rowid</code> */
  public int get(int rowid)
  {
    if (Global.DEBUG == 1)
      if (rowid >= size)
	{
	  System.err.println("ERROR! Partition.get(): rowid too large");
	  System.exit(1);
	}

    return v[rowid];
  }

  /** @return true if the class <code>classOrig</code> has already a
   *  numeric code */
  public boolean hasClassCode(String classOrig)
  {
    return classCode.containsKey(classOrig);
  }

  /** @return an Integer encoding associated with the class
   * <code>classOrig</code>*/
  public Integer getClassCode(String classOrig)
  {
    return (Integer)(classCode.get(classOrig));
  }

  /** sets an Integer encoding <code>code</code> for the class
   * <code>classOrig</code>*/
  public void setClassCode(String classOrig, Integer code)
  {
    classCode.put(classOrig, code);
  }

  /** @return the maximum number of classes */
  public int getMaxNoClasses()
  {
    return maxNoClasses;
  }

  /** @return the actual number of classes */
  public int getNoClasses()
  {
    return classCard.size();
  }

  /** prints information about the classes of this Partition */
  public void printClassInfo()
  {
    for (Enumeration e = classCode.keys() ; e.hasMoreElements() ; ) 
      {
	String classOrig = (String)(e.nextElement());
	Integer encoding  = (Integer)classCode.get(classOrig);
	System.out.println(classOrig + " enc: " +  encoding 
			   + " card: " + classCard.get(encoding));
      }
  }

  /** returns a String containing a list of classes of this Partition
   * and their cardinalities */
  public String getClassesAndCardinalities()
  {
    StringBuffer output = new StringBuffer();
    for (Enumeration classes = classCard.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	output.append(currClass + " (" 
		      + classCard.get(currClass) + ") ");
      }
    return output.toString();
  }

  /** prints cardinalities of the classes of this Partition */
  public void printClassCardinalities()
  {
    for (Enumeration classes = classCard.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	System.out.print(currClass + " (" 
			 + classCard.get(currClass) + ") ");
      }
    System.out.println();
  }

  /** appends cardinalities of the classes of this Partition to the
   * <code>output</code> */
  public void printClassCardinalities(StringBuffer output)
  {
    for (Enumeration classes = classCard.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	output.append(currClass + " (" 
		      + classCard.get(currClass) + ") ");
      }
    output.append("\n");
  }

  /** prints the class fitness values */
  public void printClassFitness()
  {
    if (cfIsValid == false)
      {
	System.err.println("ERROR! Partition.getClassFitness(): cfIsValid = false");
	System.exit(1);
      }

    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(3);

    for (Enumeration classes = classFitness.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	System.out.print(currClass + " (" 
			 + nf.format(classFitness.get(currClass)) + ") ");
      }
    System.out.println();
  }


  /** @return the size of this Partition */
  public int getSize()
  {
    return size;
  }

  /** resets the size of this partition to a smaller value
   * <code>size</code>*/
  public void setSize(int size)
  {
    if (size <= this.size)
      this.size = size;
  }

  /** randomly initializes this Partition 
   *  @param rand random number generator
  */
  public void init(Random rand)
  {
    for (int j = 0; j < size; j++)
      // fill with a random number between 1 and getMaxNoClasses()
      set(j, rand.nextInt(getMaxNoClasses()) + 1); 
    
    // if we do not have exactly getMaxNoClasses() adjust the chromosome
    if (getNoClasses() != getMaxNoClasses())
      adjust(rand);
  }


  /** adjusts this Partition to have exactly
   * <code>getMaxNoClasses()</code> classes 
   * @param rand a random number generator object
  */
  public void adjust(Random rand)
  {
    //System.out.println("adjusting...");
    int noClasses = getNoClasses();
    int maxNoClasses = getMaxNoClasses();
    Hashtable[] am = new Hashtable[maxNoClasses];
    for (int i = 0; i < maxNoClasses; i++)
      am[i] = new Hashtable();

    getAM(am);
  
    // the empty classes will be between indices noClasses and
    // getMaxNoClasses()-1
    // populate the empty classes
    for (int k = noClasses; k < getMaxNoClasses(); k++)
      {
	// pick a random class between 0 and noClasses - 1
	int pos = rand.nextInt(noClasses);
      
	// if the selected class has less than 2 elements
	// choose again
	while (am[pos].size() < 2)
	  pos = rand.nextInt(noClasses);
      
	// pick one element in the selected class
	// between 0 and size-1
	int selClass = rand.nextInt(am[pos].size());
	
	// retrieve the class to move
	Integer classToMove = null;
	try
	  {
	    for (Enumeration keys = am[pos].keys(); selClass >= 0; selClass--)
	      classToMove = (Integer)keys.nextElement();
	  }
	catch(NoSuchElementException e)
	  {
	    System.err.println("InternalError: Partition.adjust()");
	    System.exit(1);
	  }

	// move the element
	am[k].put(classToMove, classToMove);
	am[pos].remove(classToMove);
      }
    
    // setAM(am, getMaxNoClasses());
    setAM(am);
  }

  /** fills an array of Hashtable objects, <code>am</code>, with the
   * array representation of the partition; in this array each class
   * corresponds to an index in the array; the contents of the array
   * at that index is a Hashtable with the rowids where the class
   * appears in the partition */
  public void getAM(Hashtable[] am)
  {
    // maps classes to the order in the array of maps
    Hashtable classToIndexMap = new Hashtable();

    int index = 0;
    for (int i = 0; i < size; i++)
      {
	// v[i] is the class, key in the map
	// classToIndexMap.get(v[i]) is the index in am where
	Integer currClassNo = new Integer(v[i]);
	
	// this class will be stored at classToIndexMap index in am
	// class v[i] was not mapped yet
	if (classToIndexMap.containsKey(currClassNo) == false)
	  classToIndexMap.put(currClassNo, 
			      new Integer(index++));

	// key and value are the same
	Integer currRowid = new Integer(i);
	am[((Integer)classToIndexMap.get(currClassNo)).intValue()].put(currRowid, currRowid);
      }
  }

  /** sets this Partition according to the groupings in the array of
   * Hashtables <code>am</code> that contains <code>am.length</code>
   * Hashtables */
  public void setAM(Hashtable[] am)
  {
    //    System.out.println("B setAM " + getNoClasses() + " " + am.length);
    int noClasses = am.length;

    // empty the classCard map
    classCard.clear();

    // reset partition to 0
    for (int i = 0; i < size; i++)
      v[i] = 0;

    // we can have at most noClasses classes
    for (int i = 0; i < noClasses; i++)
      for (Enumeration e = am[i].keys(); e.hasMoreElements(); )
	{
	  int currRowid = ((Integer)e.nextElement()).intValue();
	  set(currRowid, i+1);

	  /*
	  v[currRowid] = i+1; // classes will be encoded starting from 1
	  Integer currClass = new Integer(i+1);
	  int currCard = 0;
	  if (classCard.containsKey(currClass) == true)
	    currCard = ((Integer)classCard.get(currClass)).intValue();
	  
	  // increment class cardinality
	  classCard.put(currClass, new Integer(currCard + 1)); 
	  */
	}
    
    cfIsValid = false;

    //    System.out.println("A setAM " + getNoClasses() + " " + am.length);
  }

  /** prints this Partition as an array of integers */
  protected void print()
  {
    for (int i = 0; i < size; i++)
      System.out.print(v[i] + " ");