chromosome.java

clustering data for the different techniques of data mining

   * their sizes (smaller have greater probability of being picked
   * up); the selection is placed in the array
   * <code>sampleClasses</code> */
  private void selectSmallClassesProb(Hashtable[] am, int n,
				      int[] sampleClasses, Random rand)
  {
    double overallProb = 0.0;
    double[] prob = new double[getMaxNoClasses()];

    // initial prob are the classes sizes
    for (int i = 0; i < getMaxNoClasses(); i++)
      {
	if (am[i].size() == 0)
	  {
	    System.err.println("ERROR! Chromosome.selectSmallClassesProb():"
			       + " empty class found");
	    System.exit(1);
	  }

	// am[i] with smallest size will have the greatest probability
	prob[i] = ((double)size) / ((double)am[i].size());
	overallProb += prob[i];
      }

    // normalize the probabilities
    for (int i = 0; i < getMaxNoClasses(); i++)
      prob[i] /= overallProb;
    
    // cumulate probabilities
    for (int i = 1; i < getMaxNoClasses() - 1; i++)
      prob[i] += prob[i - 1];
    prob[getMaxNoClasses() - 1] = 1.0;
    
    if (Global.ULTRA_VERBOSE == 1)
      {
	for (int i = 0; i < getMaxNoClasses(); i++)
	  System.out.print(prob[i] + " ");
	System.out.println();
      }

    SelectionMethods.selectProb(getMaxNoClasses(), prob,
				 sampleClasses, n, rand);
  
    if (Global.ULTRA_VERBOSE == 1)
      for (int j = 0; j < n; j++)
	{
	  System.out.println("class " + sampleClasses[j] + " having size "
			     + am[sampleClasses[j]].size());
	}
  }

  /** distributes the elements of the map <code>temp</code> to other
   * classes in <code>am</code>; classes with smaller sizes having a
   * greater chance to receive the new elements */
  private void distributeToEven(Hashtable temp, Hashtable[] am,
				Random rand)
  {
    if (Global.VERBOSE == 1)
      System.out.print("distributeToEven ");

    int nElemDistribute = temp.size();
    if (nElemDistribute == 0)
      return; // no elements to distribute
  
    if (Global.ULTRA_VERBOSE == 1)
      {
	System.out.print("temp ");
	printMap(temp);
      }
  
    int[] sampleClasses = new int[nElemDistribute];
    // select probabilistic nElemDistribute classes
    selectSmallClassesProb(am, nElemDistribute, sampleClasses, rand);

    // distribute the elements in temp to these classes
    int t = 0;
    for (Enumeration classes = temp.keys(); classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	// insert the element from temp
	am[sampleClasses[t]].put(currClass, currClass); 
	      
	if (Global.ULTRA_VERBOSE == 1)
	  {	
	    System.out.print("distribute " + currClass
			     + " to am[" + sampleClasses[t] + "] ");
	    printMap(am[sampleClasses[t]]);
	  }
      }
  }

  /** distributes the elements of <code>temp</code> into the
   * <code>emptyClasses</code> of <code>am</code>; puts
   * <code>quota</code> elements from <code>temp</code> into each
   * empty class; remaining elements are distributed according to
   * distributionType */
  private void distributeToEmptyClasses(Hashtable temp,
					Hashtable[] am, 
					Hashtable emptyClasses, 
					int quota,
					Random rand)
  {
    if (Global.VERBOSE == 1)
      System.out.print("distributeToEmptyClasses ");

    Enumeration classesTemp = temp.keys();
    Enumeration classesEmpty = emptyClasses.keys();

    Integer currClassEmpty = null;
    Integer currClassTemp = null;

    int t = -1; // number of elements inserted in the current empty
		// class

    while (classesTemp.hasMoreElements())
      {
	if (classesEmpty.hasMoreElements() == false)
	  break;
	
	currClassTemp = (Integer)classesTemp.nextElement();

	// if we already inserted the quota
	// of elements into this class
	if (t == -1 || ++t == quota)
	  {
	    t = 0;
	    // advance to next class
	    currClassEmpty = (Integer)classesEmpty.nextElement();
	  }
	
	// insert the element from temp
	// into an empty class
	am[currClassEmpty.intValue()].put(currClassTemp, currClassTemp); 
	
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("distributing " + currClassTemp + " to am["
			     + currClassEmpty + "] ");
	    printMap(am[currClassEmpty.intValue()]);
	  }
      }

    // if we still have empty classes
    while (classesEmpty.hasMoreElements())
      {
	currClassEmpty = (Integer)classesEmpty.nextElement();

	// pick at random a position from where
	// to start the search for the first class
	// having size at least 2
	// to take one element from it
	// pos is between 0 and getMaxNoClasses()-1
	int pos = rand.nextInt(getMaxNoClasses());
	
	for (; am[pos].size() < 2; )
	  pos = (pos + 1 >= getMaxNoClasses() ? 0 : pos + 1);
	
	// we take a random element
	// between 0 and am[pos].size() - 1 
	int e = rand.nextInt(am[pos].size());
	Enumeration keys = am[pos].keys();
	// position class3 on the right element on class
	// am[pos]
	Integer class3 = null;
	while(e-- >= 0)
	  class3 = (Integer)keys.nextElement();
	
	// add element to am[itr2->first]
	am[currClassEmpty.intValue()].put(class3, class3);
	// erase element from am[pos]
	am[pos].remove(class3);
	
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("transfering " + class3 + " from class " + pos
			     + " to am[" + currClassEmpty + "] ");
	    printMap(am[currClassEmpty.intValue()]);
	  }
      }
    
    // if we still have elements to distribute
    Hashtable rest = new Hashtable();
    while (classesTemp.hasMoreElements())
      {
	currClassTemp = (Integer)classesTemp.nextElement();
	rest.put(currClassTemp, currClassTemp);
      }

    if (rest.size() > 0)
      distribute(rest, am, rand);
  }

  /** prints the content of the map received as argument */
  static private void printMap(Hashtable m)
  {
    for (Enumeration classes = m.keys(); classes.hasMoreElements(); )
      System.out.print(classes.nextElement() + " ");
    System.out.println();
  }

  //////////////// MUTATION METHODS ////////////////////

  /** performes the mutation according to mutation type */
  public void mutate( Random rand)
  {
    if (Global.VERBOSE == 1)
      System.out.print("M ");

    switch(mutationType)
      {
      case MUT_RAND:
	// do the mutation
	// by randomly changing some cells in the array of values
	mutateR(rand);
	break;

      case MUT_SWAP_ELEM:
	// do the mutation
	// by swapping elements between classes
	mutateAM_SW(rand);
	break;

      case MUT_MOVE_ELEM:
	// do the mutation
	// by moving elements from one class to the other
	mutateAM_ME(rand);
	break;
	
      default:
	System.err.println("ERROR! Chromosome.mutate(): wrong choice"
			   + " of mutation type");
	System.exit(1);
      }
  }

  
  /** randomly mutates 10% elements */
  private void mutateR(Random rand)
  {
    int nMutations = (int)(0.1*size);
    // make at least one mutation
    if (nMutations == 0)
      nMutations = 1;
    
    int temp;
    for (int j = 0; j < nMutations; j++)
      {
	// randomly select the element to mutate
	// k should be a number between 0 and size-1
	int k = rand.nextInt(size);

	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("element " + k + " in class " + v[k]);

	// randomly select a new class (between 1 and getMaxNoClasses())
	// for element k, different than the old class 
	temp = 1 + rand.nextInt(getMaxNoClasses());
	while (temp == v[k])
	  temp = 1 + rand.nextInt(getMaxNoClasses());
      
	// set the new class
	set(k, temp);
	
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println(" mutated to " + temp);
      }
  }

  /** moves 10% elements between randomly selected classes */
  private void mutateAM_ME(Random rand)
  {
    int nMoves = (int)(0.1*size);
    // move at least one element
    if (nMoves == 0)
      nMoves = 1;

    int noClasses = getNoClasses(); // actual number of classes  
    Hashtable[] am = new Hashtable[getMaxNoClasses()];
    for (int i = 0; i < getMaxNoClasses(); i++)
      am[i] = new Hashtable();
    getAM(am);
  
    for (int k = 0; k < nMoves; k++)
      {
	// randomly select two distinct classes among which we will transfer
	// one element, k1, k2 are between 0 and noClasses-1
	int k1 = rand.nextInt(noClasses);

	// we do nothing if the first selected class
	// has only one element
	if (am[k1].size() == 1)
	  continue;

	// select destination class
	int k2 = rand.nextInt(getMaxNoClasses());
	while (k2 == k1)
	  k2 = rand.nextInt(noClasses);
	
	// if we picked an empty class, make it be the first empty class
	// if it's not already
	if (k2 > noClasses)
	  k2 = noClasses;

	// increment noClasses if we're going to add to an empty class
	if (k2 == noClasses)
	  noClasses++;
	
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("initial class am[" + k1 + "] ");
	    printMap(am[k1]);
	    System.out.println("initial class am[" + k2 + "] ");
	    printMap(am[k2]);
	  }
	  
	// select randomly the element that will be moved
	// e is between 0 and card_k1 - 1
	int e = rand.nextInt(am[k1].size());
	
	Enumeration keys = am[k1].keys();
	// position the iterator on the right element
	// in class k1
	Integer currClass = null;
	while (e-- >= 0)
	  currClass = (Integer)keys.nextElement();
	
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("moving element " + currClass + " from class "
			     + k1 + " to class " + k2);
	am[k1].remove(currClass);
	am[k2].put(currClass, currClass);

	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("final class am[" + k1 + "] ");
	    printMap(am[k1]);
	    System.out.print("final class am[" + k2 + "] ");
	    printMap(am[k2]);
	  }
      }

    //    setAM(am, noClasses);
    setAM(am);
  }


  /** swaps 10% elements between randomly selected classes */
  private void mutateAM_SW(Random rand)
  {
    if (getNoClasses() == 1)
      return;
    
    int nSwaps = (int)(0.1*size);
    // swap at least one element
    if (nSwaps == 0)
      nSwaps = 1;
    
    int noClasses = getNoClasses();
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();
    getAM(am);
 
    int k1, k2, e1, e2;
    for (int k = 0; k < nSwaps; k++)
      {
	// randomly select two distinct classes among which we will swap
	// one element, k1, k2 are between 0 and noClasses-1
	k1 = rand.nextInt(noClasses);
	k2 = rand.nextInt(noClasses);
	while (k2 == k1)
	  k2 = rand.nextInt(noClasses);
      
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("initial class am[" + k1 + "] ");
	    printMap(am[k1]);
	    System.out.print("initial class am[" + k2 + "] ");
	    printMap(am[k2]);
	  }
	  
	// randomly select the elements that will be swap 
	// e1 is between 0 and card_k1 - 1
	// e2 is between 0 and card_k2 - 1
	e1 = rand.nextInt(am[k1].size());
	e2 = rand.nextInt(am[k2].size());
	
	Enumeration classes1 = am[k1].keys();
	Enumeration classes2 = am[k2].keys();
	Integer currClass1 = null;
	Integer currClass2 = null;

	// position the iterator on the right element
	// in class k1
	while (e1-- >= 0)
	  currClass1 = (Integer)classes1.nextElement();

	// position the iterator on the right element
	// in class k2
	while (e2-- >= 0)
	  currClass2 = (Integer)classes2.nextElement();
	
	if (Global.ULTRA_VERBOSE == 1)
	  System.out.println("Swapping elements " + currClass1 + " from class "
			     + k1 + " with element " + currClass2 
			     + " from class "  + k2);
	// swap the elements
	Integer temp = currClass2;
	am[k2].remove(currClass2);
	am[k2].put(currClass1, currClass1);

	am[k1].remove(currClass1);
	am[k1].put(temp, temp);
	  
	if (Global.ULTRA_VERBOSE == 1)
	  {
	    System.out.print("final class am[" + k1 + "] ");
	    printMap(am[k1]);
	    System.out.print("final class am[" + k2 + "] ");
	    printMap(am[k2]);
	  }
      }
    //    setAM(am, noClasses);
    setAM(am);
  }

  static public void main(String[] args)
  {
    int nRows = 10;
    int nCols = 10;
    int nMaxNoClasses = 3;
    Chromosome[] db = new Chromosome[nCols];
    for (int i = 0; i < nCols; i+=2)
      {
	db[i] = new Chromosome(nRows, nMaxNoClasses, Partition.CF_SYM_DIFF,
			       CROSS_RAND + i, MUT_RAND, DISTRIB_RAND);
	db[i+1] = new Chromosome(nRows, nMaxNoClasses, Partition.CF_SYM_DIFF,
			       CROSS_RAND + i, MUT_RAND, DISTRIB_RAND);
      }

    Random rand = new Random(1000);
    
    for (int i = 0; i < nCols; i++)
      db[i].init(rand);

    computeFitnessValues(db, nCols, db, nCols, ImpurityMeasure.GINI,
			 Global.FM_BOTH, null, null, null);

    for (int i = 0; i < nCols/2; i++)
      {
	System.out.println("CROSSOVER " + (CROSS_RAND+i));
	System.out.print(i + ": ");
	db[i].print();
	System.out.print((i+1) + ": ");
	db[i+1].print();
	System.out.println("Crossing over ...");
	db[i].crossover(db[i+1], rand);
	System.out.print(i + ": ");
	db[i].print();
	System.out.print((i+1) + ": ");
	db[i+1].print();
      }

    for (int i = 0; i < 3; i++)
      db[i] = new Chromosome(nRows, nMaxNoClasses, Partition.CF_SYM_DIFF,
			     CROSS_RAND + i, MUT_RAND+i, DISTRIB_RAND);
    for (int i = 0; i < 3; i++)
      db[i].init(rand);

    computeFitnessValues(db, 3, db, 3, ImpurityMeasure.GINI,
			 Global.FM_BOTH, null, null, null);

    for (int i = 0; i < 3; i++)
      {
	System.out.println("MUTATION " + (MUT_RAND+i));
	System.out.print(i + ": ");
	db[i].print();
	db[i].mutate(rand);
	System.out.print(i + ": ");
	db[i].print();
      }
  }
}