partition.java

clustering data for the different techniques of data mining

    System.out.println();
  }

  /** appends contents of this Partition as an array of integers to
   * <code>output</code>*/
  protected void print(StringBuffer output)
  {
    for (int i = 0; i < size; i++)
      output.append(v[i] + " ");
    
    output.append("\n");
  }

  /** prints this Partition as an array of a collection of rowids */
  public void printAM()
  {
    int noClasses = getNoClasses();
    Hashtable[] am = new Hashtable[noClasses];
    for (int i = 0; i < noClasses; i++)
      am[i] = new Hashtable();
    
    System.out.print("printAM noClasses = " + noClasses);
    print();

    getAM(am);
  
    System.out.print("[");
    for (int i = 0; i < noClasses; i++)
      {
	 System.out.print("[ ");

	 try
	   {
	     for (Enumeration keys = am[i].keys(); keys.hasMoreElements(); )
	       System.out.print(keys.nextElement() + " ");
	   }
	 catch(NoSuchElementException e)
	   {
	     System.err.println("InternalError:Partition.printAM()!");
	     System.exit(1);
	   }

	 System.out.print("]");
      }
    System.out.println("]");
  }
  
  /** @return the entropy of this partition computed with
   * <code>entropyMeasure</code> */
  public double entropy(int entropyMeasure)
  {
    double entropy = 0.0;
    for (Enumeration classCards = classCard.elements(); 
	 classCards.hasMoreElements(); )
      entropy += ImpurityMeasure.impurityMeasure(entropyMeasure,
						 ((Integer)classCards.nextElement()).intValue() / (double)size);
    return entropy;
  }

  /** @return true if this Partition is equal to the one received as
   * argument, false otherwise */
  public boolean isEqual(Partition p)
  {
    if (size != p.size)
      {
	if (Global.DEBUG == 1)
	  System.err.println("Warning! Partition.isEqual(): compared two partitions with different size");
	return false;
      }
    
    for (int i = 0; i < size; i++)
      if (v[i] != p.v[i])
	return false;
    
    return true;
  }

  /** sets the values of this Partition equal to the one from the
   * parameter */
  public void set(Partition p)
  {
    if (Global.DEBUG == 1)
      if (size != p.size)
	{
	  System.err.println("ERROR! Partition.set(): partitions have different size");
	  System.exit(1);
	}

    for (int rowid = 0 ; rowid < size; rowid++)
      set(rowid, p.v[rowid]);
    
    fitness = p.fitness;
    classFitness = new Hashtable(p.classFitness);
    cfIsValid = p.cfIsValid;
  }

  /** @return the cardinality of class <code>c</code> */
  public int getClassCard(int c)
  {
    Integer classNo = new Integer(c);
    if (classCard.containsKey(classNo) == true)
      return ((Integer)classCard.get(classNo)).intValue();
    else
      return 0;
  }

  /** @return the fitness of class <code>c</code> */
  public double getClassFitness(int c)
  {
    if (cfIsValid == false)
      {
	System.err.println("ERROR! Partition.getClassFitness(): cfIsValid = false");
	System.exit(1);
      }

    Integer classNo = new Integer(c);
    if (classFitness.containsKey(classNo))
      return ((Double)classFitness.get(classNo)).doubleValue();
    else
      {
	System.err.println("ERROR! Partition.getClassFitness(): invalid class no " + c);
	System.exit(1);
      }
    return 0.0;
  }

  /** sets the fitness of class <code>c</code> to <code>value</code> */
  public void setClassFitness(int c, double value)
  {
    classFitness.put(new Integer(c), new Double(value));
    cfIsValid = true;
  }

  /** @return fitness of this Partition */
  public double getFitness()
  {
    return fitness;
  }

  /** sets the fitness of this Partition to value <code>f</code> */
  public void setFitness(double f)
  {
    fitness = f;
  }

  /** @return the fitness type of the classes */
  public int getClassFitnessType()
  {
    return classFitnessType;
  }

  /** computes intersections between the classes of partitions in
      collection <code>c1</code> and classes of the partitions in
      collection <code>c2</code>
      @param NPART1 represents the number of partitions in c1
      @param NPART2 represents the number of partitions in c2
      @param intersectMap stores in intersectMap[i][j]: <class of
      c1[i], <class of c2[j], intersection count >>;
      intersectMap[i][j] is a map for intersections between partitions
      c1[i] and c2[j]; intersectMap[i][j]:key corresponds to each
      distinct value in c1[i](C_s); intersectMap[i][j]:value
      corresponds to a map with intersections between c2[j][t] and
      c1[i][s] (B_t x C_s); intersectMap[i][j] = <C_s, <B_t, B_t x C_s
      >> */
  static public void computeIntersections(Partition[] c1, int NPART1, 
				   Partition[] c2, int NPART2,
				   Hashtable[][] intersectMap)
  {
    int SIZE = c1[0].size; // partition size
    
    // create maps
    for (int rowid = 0; rowid < SIZE; rowid++)
      for (int i = 0; i < NPART1; i++)
	for (int j = 0; j < NPART2; j++)
	  {
	    Integer currClassC1 = new Integer(c1[i].v[rowid]);
	    Integer currClassC2 = new Integer(c2[j].v[rowid]);
	    
	    if (intersectMap[i][j].containsKey(currClassC1) == false)
	      {
		// currClassC1 has no hashtable associated yet
		// create a new table, with mapping (currClassC2, 1)
		Hashtable h = new Hashtable();
		h.put(currClassC2, new Integer(1));
		intersectMap[i][j].put(currClassC1, h);
	      }
	    else
	      {
		// currClassC1 has already a hashtable associated
		Hashtable h = (Hashtable)intersectMap[i][j].get(currClassC1);
		// does it contain an entry for currClassC2
		if (h.containsKey(currClassC2) == false)
		  h.put(currClassC2, new Integer(1));
		else
		  {
		    int oldCount = ((Integer)h.get(currClassC2)).intValue();
		    h.put(currClassC2, new Integer(oldCount+1));
		  }
	      }
	  }
  }
  
  /** computes intersections between the classes of partition
      <code>p</code> and classes of the partitions in collection
      <code>c</code>
      @param NPART represents the number of partitions in c
      @param intersectMap[i] stores: <class of p, <class of c[i],
      intersection count >>; intersectMap[i] is a map for
      intersections between partitions c[i] and p; intersectMap[i]:
      key corresponds to each distinct value in p (C_s);
      intersectMap[i]: value corresponds to a map with intersection
      between c[i][t] and p[s] (B_t x C_s); intersectMap[i] = <C_s,
      <B_t, B_t x C_s >> */
  static public void computeIntersections(Partition p, 
					  Partition[] c, int NPART,
					  Hashtable[] intersectMap)
  {
    int SIZE = p.size; // partition size
    
    // create maps
    for (int rowid = 0; rowid < SIZE; rowid++)
      for (int i = 0; i < NPART; i++)
	{
	  Integer currClass = new Integer(p.v[rowid]);
	  Integer currClassC = new Integer(c[i].v[rowid]);
	  
	  if (intersectMap[i].containsKey(currClass) == false)
	    {
	      // currClass has no hashtable associated yet
	      // create a new table, with mapping (currClassC, 1)
	      Hashtable h = new Hashtable();
	      h.put(currClassC, new Integer(1));
	      intersectMap[i].put(currClass, h);
	    }
	  else
	    {
	      // currClass has already a hashtable associated
	      Hashtable h = (Hashtable)intersectMap[i].get(currClass);
	      // does it contain an entry for currClassC
	      if (h.containsKey(currClassC) == false)
		h.put(currClassC, new Integer(1));
	      else
		{
		  int oldCount = ((Integer)h.get(currClassC)).intValue();
		  h.put(currClassC, new Integer(oldCount+1));
		}
	    }
	}
  }
  
  /** prints the intersection between classes of one partition and
   * other <code>nPart</code> partitions */
  static public void printIntersections(Hashtable[] intersectMap, int nPart)
  {
    for (int i = 0; i < nPart; i++)
      {
	System.out.println("Intersections with partition " + i);
	try
	  {

	    for (Enumeration classesC1 = intersectMap[i].keys(); 
		 classesC1.hasMoreElements();)
	      {
		Integer currClassC1 = (Integer)classesC1.nextElement();
		Hashtable intersect = (Hashtable)intersectMap[i].get(currClassC1);
		for (Enumeration classesC2 = intersect.keys(); 
		     classesC2.hasMoreElements();)
		  {
		    Integer currClassC2 = (Integer)classesC2.nextElement();
		    System.out.println(currClassC1 + " " + currClassC2 + " " 
				       + intersect.get(currClassC2));
		  }
	      }
	  }
	catch(NoSuchElementException e)
	  {
	    System.err.println("InternalError! Partition.printIntersections");
	    System.exit(1);
	  }
      }
  }

  /** @return entropy of the partition resulting from the
   * intersection of this Partition with the one received as argument,
   * computed with <code>entropyMeasure</code> */
  public double entropyIntersect(Partition p, int entropyMeasure)
  {
    // <Cs, <Bt, |Cs x Bt|> >
    Hashtable[] intersectMap = new Hashtable[1];
    intersectMap[0] = new Hashtable();
    Partition[] c = new Partition[1];
    c[0] = p;
    // create map with intersections
    computeIntersections(this, c, 1, intersectMap);

    double entropy = 0.0;
    // key: C_s, value: <B_t, B_t x C_s >
    for (Enumeration values = intersectMap[0].elements(); 
	 values.hasMoreElements(); )
      {
	Hashtable intersections = (Hashtable)values.nextElement();
	
	// key: B_t, value: |Bt x C_s|
	for (Enumeration counts = intersections.elements(); 
	     counts.hasMoreElements(); )
	  {
	    int count = ((Integer)counts.nextElement()).intValue(); // |B_t x C_s|
	    if (Global.DEBUG == 1)
	      if (count == 0)
		{
		  System.err.println("ERROR! Partition.entropyIntersect(): |B_t x C_s| = 0");
		  System.exit(1);
		}

	    entropy += ImpurityMeasure.impurityMeasure(entropyMeasure,
						       (double)count 
						       /(double)size);
	  }
      }
    
    return entropy;
  }


  /** fills the vector <code>v</code> with a Double representing the
   * value of the entropy of the partition determined by the
   * intersection of all <code>NPART</code> partitions in the
   * collection <code>c</code> and with an Integer representing the
   * number of classes of the intersection partition */
  static public void computeInfoIntersections(Partition[] c, int NPART, 
					      int entropyMeasure,
					      Vector v)
  {
    // the value in the partitions are integers so the key will be an
    // Integer; key:intersection class id, value: cardinality of the
    // class
    Hashtable intersections = new Hashtable();
    int SIZE = c[0].getSize(); // size of the partitions in c
    int key = 0;
    for (int rowid = 0; rowid < SIZE; rowid++)
      {
	for (int i = NPART-1; i >= 0; i--)
	  {
	    // accumulates the values in the columns to create a number; if
	    // the columns contain 1 2 3 4 5 for this rowid the key will
	    // be the number 12345
	    key = key*10 + c[i].v[rowid];
	  }
	
	Integer keyInt = new Integer(key);
	
	int count = 0;
	// is key already in the map, get old count
	if (intersections.containsKey(keyInt) == true)
	  count = ((Integer)intersections.get(keyInt)).intValue();
	
	intersections.put(keyInt, new Integer(count+1));
      }
    
    // compute entropy
    double entropy = 0.0;
    for (Enumeration values = intersections.elements(); 
	 values.hasMoreElements(); )
      entropy += ImpurityMeasure.impurityMeasure(entropyMeasure,
						 ((Integer)values.nextElement()).doubleValue() / (double)SIZE);

    v.insertElementAt(new Double(entropy), 0);

    v.insertElementAt(new Integer(intersections.size()), 1);
  }

  /** @return true if for the specified <code>fitnessMeasure</code>
   * we need to compute the entropy conditioned by the partition of
   * the argument */
  private boolean needsEntropyConditionedByThem(int fitnessMeasure)
  {
    return (fitnessMeasure == Global.FM_P_PA
	    || fitnessMeasure == Global.FM_BOTH
	    || fitnessMeasure == Global.FM_BOTH_SCALED
	    || fitnessMeasure == Global.FM_Q
	    || fitnessMeasure == Global.FM_L
	    || fitnessMeasure == Global.FM_Q_QR
	    || fitnessMeasure == Global.FM_ALTERNATE_HAVG
	    || fitnessMeasure == Global.FM_ALTERNATE
	    || fitnessMeasure == Global.FM_MOD
	    || fitnessMeasure == Global.FM_COS
	    || fitnessMeasure == Global.FM_NORM_W
	    || fitnessMeasure == Global.FM_WE
	    || fitnessMeasure == Global.FM_TEST);
  }

  /** @return true if for the specified <code>fitnessMeasure</code>
   * we need to compute the entropy conditioned by this partition */
  private boolean needsEntropyConditionedByUs(int fitnessMeasure)
  {
    return (fitnessMeasure == Global.FM_PA_P
	    || fitnessMeasure == Global.FM_BOTH
	    || fitnessMeasure == Global.FM_BOTH_SCALED
	    || fitnessMeasure == Global.FM_QR
	    || fitnessMeasure == Global.FM_LR
	    || fitnessMeasure == Global.FM_Q_QR
	    || fitnessMeasure == Global.FM_ALTERNATE_HAVG
	    || fitnessMeasure == Global.FM_ALTERNATE
	    || fitnessMeasure == Global.FM_MOD
	    || fitnessMeasure == Global.FM_COS
	    || fitnessMeasure == Global.FM_NORM_W
	    || fitnessMeasure == Global.FM_WE
	    || fitnessMeasure == Global.FM_TEST);
  }

  /** @return true if for the specified <code>fitnessMeasure</code>
   * we need to compute the entropy of intersections of all
   * partition */
  private boolean needsEntropyOfIntersection(int fitnessMeasure)
  {
    return (fitnessMeasure == Global.FM_L
	    || fitnessMeasure == Global.FM_LR);
  }