partition.java

clustering data for the different techniques of data mining

      avgSilh += silhouettes[rowid];
    
    output.append("Average silhouette " + avgSilh/(double)size + "\n");

    for (int classNo = 0; classNo < noClasses; classNo++)
      {
	Heap silhToPrint = new Heap(noClasses);
	for (Enumeration rowids = am[classNo].keys();
	     rowids.hasMoreElements();)
	  {
	    int currRowid = ((Integer)rowids.nextElement()).intValue();
	    silhToPrint.insert(new SilhInfo(currRowid, silhouettes[currRowid],
					    neighbors[currRowid]));
	  }

	while (silhToPrint.size() != 0)
	  {
	    SilhInfo s = null;
	    try
	      {
		s = (SilhInfo)silhToPrint.remove();
	      }
	    catch(EmptyHeapException e)
	      {
		System.err.println("Internal Error: Partition.plotSilhouettes(): empty heap");
		System.exit(1);
	      }

	    double currSilh = s.silhouette;
	    output.append("c " + (classNo + 1) 
			  + " n " + (s.neighbor + 1) 
			  + " r " + s.rowid + "\t");
	    if (currSilh < 0)
	      {
		int i = 0;
		while(i++ < -30*currSilh)
		  output.append("-");
	      }
	    else
	      {
		int i = 0;
		while(i++ < 30*currSilh)
		  output.append("+");
	      }
	    output.append(" (" + currSilh + ")\n");
	  }
      }
  }



  /** prints information about this Partition */
  public void printInfo(Partition[] db, int NPART, 
			double[] wTargetCondOnDB, 
			double[] wDBCondOnTarget, 
			double[] weight,
			int entropyMeasure, int fitnessMeasure,
			String s)
  {
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(3);

    printClassCardinalities();
    System.out.println("entropy " + s + ": " 
		       + nf.format(entropy(entropyMeasure)));
    computeFitness(db, NPART, entropyMeasure, fitnessMeasure, 
		   wTargetCondOnDB, wDBCondOnTarget, weight);
    System.out.println("fitness " + s + ": " + nf.format(fitness));
    computeFitness(db, NPART, entropyMeasure, Global.FM_BOTH, 
		   wTargetCondOnDB, wDBCondOnTarget, weight);
    System.out.println("Sum H(piA|pi) + H(pi|piA) " + s + ": " 
		       + nf.format(fitness));

    if (Global.VERBOSE == 1)
      {
	System.out.println("Symmetrical difference equiv classes: "
			 + nf.format(sumDistSymDiff(db, NPART)));

	if (getNoClasses() > 1)
	  {
	    double[] silhouettes = new double[size];
	    int[] neighbors = new int[size];
	    computeSilhouettes(silhouettes, neighbors, db, NPART);
	    plotSilhouettes(silhouettes, neighbors);
	  }
      }
  }

  /** appends information about this Partition to
   * <code>output</code>*/
  public void printInfo(Partition[] db, int NPART, 
			double[] wTargetCondOnDB, 
			double[] wDBCondOnTarget, 
			double[] weight,
			int entropyMeasure, int fitnessMeasure,
			String s, StringBuffer output)
  {
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(3);

    printClassCardinalities(output);
    output.append("entropy " + s + ": " 
		  + nf.format(entropy(entropyMeasure)) + "\n");
    computeFitness(db, NPART, entropyMeasure, fitnessMeasure, 
		   wTargetCondOnDB, wDBCondOnTarget, weight);
    output.append("fitness " + s + ": " 
		  + nf.format(fitness) + "\n");
    computeFitness(db, NPART, entropyMeasure, Global.FM_BOTH, 
		   wTargetCondOnDB, wDBCondOnTarget, weight);
    output.append("Sum H(piA|pi) + H(pi|piA) " + s + ": " 
		  + nf.format(fitness) + "\n");

    if (Global.VERBOSE == 1)
      {
	output.append("Symmetrical difference equiv classes: "
		      + nf.format(sumDistSymDiff(db, NPART)) + "\n");

	if (getNoClasses() > 1)
	  {
	    double[] silhouettes = new double[size];
	    int[] neighbors = new int[size];
	    computeSilhouettes(silhouettes, neighbors, db, NPART);
	    plotSilhouettes(silhouettes, neighbors, output);
	  }
      }
  }


  /** <code>mapIntersect</code> contains <B_t, |B_txC_s|>,
   * <code>excluding</code> is a map of B_t values that should not be
   * considered; the function returns the value B_t with the maximum
   * |B_txC_s| excluding the values specified; return 0 if no class
   * can be found */
  private int findAssocClass(Hashtable mapIntersect, 
			     Hashtable excluding)
  {
    int maxCount;
    int classId;
    if (excluding.size() == 0)
      {
	Enumeration keys = mapIntersect.keys();
	Integer currClass = null;
	try
	  {
	    currClass = (Integer)keys.nextElement();
	  }
	catch(NoSuchElementException e)
	  {
	    System.err.println("Internal Error: Partition.findAssocClass()");
		System.exit(1);	    
	  }
	
	maxCount = ((Integer)mapIntersect.get(currClass)).intValue();
	classId  = currClass.intValue();
      }
    else
      {
	maxCount = 0;
	classId = 0;
	// search for the first class that is not excluded
	for (Enumeration classes = mapIntersect.keys();
	     classes.hasMoreElements();)
	  {
	    Integer currClass = (Integer)classes.nextElement();
	    
	    if (excluding.containsKey(currClass) == false)
	      {
		maxCount = ((Integer)mapIntersect.get(currClass)).intValue();
		classId  = currClass.intValue();
		break;
	      }
	  }

	// all classes are excluded
	if (classId == 0)
	  return 0;
      }

    // search for the class B_t* with the maximum value |B_txC_s|
    // excluding the classes specified
    for (Enumeration classes = mapIntersect.keys();
	 classes.hasMoreElements();)
      {
	Integer currClass = (Integer)classes.nextElement();
	
	// if B_t should be excluded skip it
	if (excluding.size() != 0 && excluding.containsKey(currClass) == true)
	  continue;
      
	if (((Integer)mapIntersect.get(currClass)).intValue() > maxCount)
	  {
	    maxCount = ((Integer)mapIntersect.get(currClass)).intValue();
	    classId  = currClass.intValue();
	  }
      }
    
    return classId;
  }

  /** @return and ArrayList of ArrayList elements containing a string
   * representing the class of target and a String representing
   * intersections with the classes of this Partition */
  public ArrayList getClassIntersections(Partition target)
  {
    // target = (C_s), this = (B_t)
    // intersectMap = <C_s, <B_t, |B_t x C_s| >>
    Hashtable[] intersectMaps = new Hashtable[1];
    intersectMaps[0] = new Hashtable();
    Partition[] c = new Partition[1];
    c[0] = this;
    computeIntersections(target, c, 1, intersectMaps);
    Hashtable intersectMap = intersectMaps[0];

    int targetNoClasses = target.getNoClasses();
    ArrayList result = new ArrayList(targetNoClasses);

    // look for each C_s, at the map <B_t, |B_t x C_s| >
    for (Enumeration classes = intersectMap.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	ArrayList innerRes = new ArrayList(2);
	
	innerRes.add(currClass + "(" + 
		     + target.getClassCard(currClass.intValue())
		     + ")");
	// <B_t, |B_t x C_s| > to sum up all misclassifications
	Hashtable map = (Hashtable)intersectMap.get(currClass);
	StringBuffer value2 = new StringBuffer();
	for (Enumeration classes2 = map.keys(); 
	     classes2.hasMoreElements(); )
	  {
	    Integer currClass2 = (Integer)classes2.nextElement();
	    value2.append(currClass2 + "("
			 + getClassCard(currClass2.intValue())
			 + ")[" + map.get(currClass2) +"]  ");
	  }
	innerRes.add(value2.toString());
	result.add(innerRes);
      }

    return result;
  }

  /** @return the percent of rowids classified in the same way as in
   * the target partition */
  public double getClassifRate(Partition target)
  {
    // target = (C_s), this = (B_t)
    // intersectMap = <C_s, <B_t, |B_t x C_s| >>
    Hashtable[] intersectMaps = new Hashtable[1];
    intersectMaps[0] = new Hashtable();

    Partition[] c = new Partition[1];
    c[0] = this;

    computeIntersections(target, c, 1, intersectMaps);
    Hashtable intersectMap = intersectMaps[0];

    int targetNoClasses = target.getNoClasses();

    // class id c in target partition corresponds to class corrClass[c]
    // in this partition
    int[] corrClass = new int[targetNoClasses + 1]; // we do not use position 0

    // stores at position c the cardinality of the intersection of class
    // c and class corrClass[c]
    int[] cardIntersect = new int[targetNoClasses+1]; // we do not use
						      // position 0

    // we do not use position 0
    Hashtable[] excluding = new Hashtable[targetNoClasses + 1]; 
    for (int i = 0; i < targetNoClasses + 1; i++)
      excluding[i] = new Hashtable();

    // look for each C_s, at the map <B_t, |B_t x C_s| >
    for (Enumeration classes = intersectMap.keys(); 
	 classes.hasMoreElements(); )
      {
	Integer currClass = (Integer)classes.nextElement();
	// find the associated class not excluding any class
	int classId = findAssocClass((Hashtable)intersectMap.get(currClass), 
				     excluding[currClass.intValue()]);
      
	// classId was not previously assigned, assign it to C_s
	corrClass[currClass.intValue()] = classId;
	if (classId != 0)
	  cardIntersect[currClass.intValue()] = 
	    ((Integer)(((Hashtable)intersectMap.get(currClass)).get(new Integer(classId)))).intValue();
	else
	  cardIntersect[currClass.intValue()] = 0;
      }
    
    if (Global.VERBOSE == 1)
      {
	System.out.println("original mapping");
	for (int i = 1; i <= targetNoClasses; i++)
	  System.out.println("Ref Part class " + i + "(" 
			     + target.getClassCard(i)+ ") mapped to "
			     + corrClass[i] + " (" 
			     + getClassCard(corrClass[i]) + ") : " 
			     + cardIntersect[i]);
      }

    if (Global.VERBOSE == 1)
      {
	System.out.println("full mapping");
	// look for each C_s, at the map <B_t, |B_t x C_s| >
	for (Enumeration classes = intersectMap.keys(); 
	     classes.hasMoreElements(); )
	  {
	    Integer currClass = (Integer)classes.nextElement();
	    // <B_t, |B_t x C_s| > to sum up all misclassifications
	    Hashtable map = (Hashtable)intersectMap.get(currClass);
	    for (Enumeration classes2 = map.keys(); 
		 classes2.hasMoreElements(); )
	      {
		Integer currClass2 = (Integer)classes2.nextElement();
		System.out.println("target class " + currClass+ "("
				   + target.getClassCard(currClass.intValue()) 
				   + ") mapped to " +  currClass2 + " (" 
				   + getClassCard(currClass2.intValue())
				   + ") : " + map.get(currClass2));
	      }
	  }
      }
	
    // check if the mapping between classes of the target partition and
    // this partition are unique
    for (int i = 1; i <= targetNoClasses; i++)
      {
	// this class has no association
	if (corrClass[i] == 0)
	  continue;
      
	int j;
	for (j = i + 1; j <= targetNoClasses; j++)
	  if (corrClass[i] == corrClass[j])
	    {
	      // decide what class will be assigned to a different one
	      int change = 0;

	      if (cardIntersect[i] < cardIntersect[j])
		change = i;
	      else 
		if (cardIntersect[i] > cardIntersect[j])
		  change = j;
		else // cardIntersect[i] == cardIntersect[j]
		  if (getClassCard(i) < getClassCard(j))
		    change = j;
		  else
		    change = i;

	      // find another candidate associated with class i
	      excluding[change].put(new Integer(corrClass[change]),
				    new Integer(corrClass[change]));

	      corrClass[change] = 
		findAssocClass((Hashtable)intersectMap.get(new Integer(change)),
			       excluding[change]);
	      if (corrClass[change] != 0)
		cardIntersect[change] = 
		  ((Integer)((Hashtable)intersectMap.get(new Integer(change))).get(new Integer(corrClass[change]))).intValue();

	      // some change occur break the j loop
	      break;
	    } // end j loop
	
	// we break from the for above, we should start from the
	// beginning again
	if (j <= targetNoClasses)
	  i = 0;
      }
    

    if (Global.VERBOSE == 1)
      {
	System.out.println("unique mapping");
	// check if the mapping between classes of the target partition and
	// this partition are unique
	for (int i = 1; i <= targetNoClasses; i++)
	  System.out.println("target class " + i + "(" 
			     + target.getClassCard(i) + ") mapped to " 
			     + corrClass[i] + " (" 
			     + getClassCard(corrClass[i]) 
			     + ") : " + cardIntersect[i]);
	
	System.out.println("Elements classified as in target");
	// check if the mapping between classes of the target partition and
	// this partition are unique
	for (int i = 1; i <= targetNoClasses; i++)
	  if (corrClass[i] != 0)
	    System.out.println(cardIntersect[i] + " out of " 
			       + target.getClassCard(i));
      }
    
    int classifCorrect = 0;
    for (int i = 1; i <= targetNoClasses; i++)
      if (corrClass[i] != 0)
	classifCorrect += cardIntersect[i];
    
    if (Global.VERBOSE == 1)
      System.out.println(classifCorrect + " rowids out of " + size 
			 + " have been classified as in target parition");

    return (double)classifCorrect/(double)size;
  }


  static public void main(String[] args)
  {
    int nRows = 5;
    int nCols = 5;
    int nMaxNoClasses = 3;