utils.java

Java 编写的多种数据挖掘算法 包括聚类、分类、预处理等

      if (Double.isNaN(array[i])) {
        array[i] = Double.MAX_VALUE;
      }
    }
    quickSort(array, index, 0, array.length - 1);
    return index;
  }

  /**
   * Sorts a given array of doubles in ascending order and returns an 
   * array of integers with the positions of the elements of the original 
   * array in the sorted array. The sort is stable (Equal elements remain
   * in their original order.) Occurrences of Double.NaN are treated as 
   * Double.MAX_VALUE
   *
   * @param array this array is not changed by the method!
   * @return an array of integers with the positions in the sorted
   * array.
   */
  public static /*@pure@*/ int[] stableSort(double [] array){

    int [] index = new int[array.length];
    int [] newIndex = new int[array.length];
    int [] helpIndex;
    int numEqual;
    
    array = (double [])array.clone();
    for (int i = 0; i < index.length; i++) {
      index[i] = i;
      if (Double.isNaN(array[i])) {
        array[i] = Double.MAX_VALUE;
      }
    }
    quickSort(array,index,0,array.length-1);

    // Make sort stable

    int i = 0;
    while (i < index.length) {
      numEqual = 1;
      for (int j = i+1; ((j < index.length) && Utils.eq(array[index[i]],
							array[index[j]])); j++)
	numEqual++;
      if (numEqual > 1) {
	helpIndex = new int[numEqual];
	for (int j = 0; j < numEqual; j++)
	  helpIndex[j] = i+j;
	quickSort(index, helpIndex, 0, numEqual-1);
	for (int j = 0; j < numEqual; j++) 
	  newIndex[i+j] = index[helpIndex[j]];
	i += numEqual;
      } else {
	newIndex[i] = index[i];
	i++;
      }
    }

    return newIndex;
  }

  /**
   * Computes the variance for an array of doubles.
   *
   * @param vector the array
   * @return the variance
   */
  public static /*@pure@*/ double variance(double[] vector) {
  
    double sum = 0, sumSquared = 0;

    if (vector.length <= 1) {
      return 0;
    }
    for (int i = 0; i < vector.length; i++) {
      sum += vector[i];
      sumSquared += (vector[i] * vector[i]);
    }
    double result = (sumSquared - (sum * sum / (double) vector.length)) / 
      (double) (vector.length - 1);

    // We don't like negative variance
    if (result < 0) {
      return 0;
    } else {
      return result;
    }
  }

  /**
   * Computes the sum of the elements of an array of doubles.
   *
   * @param doubles the array of double
   * @return the sum of the elements
   */
  public static /*@pure@*/ double sum(double[] doubles) {

    double sum = 0;

    for (int i = 0; i < doubles.length; i++) {
      sum += doubles[i];
    }
    return sum;
  }

  /**
   * Computes the sum of the elements of an array of integers.
   *
   * @param ints the array of integers
   * @return the sum of the elements
   */
  public static /*@pure@*/ int sum(int[] ints) {

    int sum = 0;

    for (int i = 0; i < ints.length; i++) {
      sum += ints[i];
    }
    return sum;
  }

  /**
   * Returns c*log2(c) for a given integer value c.
   *
   * @param c an integer value
   * @return c*log2(c) (but is careful to return 0 if c is 0)
   */
  public static /*@pure@*/ double xlogx(int c) {
    
    if (c == 0) {
      return 0.0;
    }
    return c * Utils.log2((double) c);
  }

  /**
   * Partitions the instances around a pivot. Used by quicksort and
   * kthSmallestValue.
   *
   * @param array the array of doubles to be sorted
   * @param index the index into the array of doubles
   * @param l the first index of the subset 
   * @param r the last index of the subset 
   *
   * @return the index of the middle element
   */
  private static int partition(double[] array, int[] index, int l, int r) {
    
    double pivot = array[index[(l + r) / 2]];
    int help;

    while (l < r) {
      while ((array[index[l]] < pivot) && (l < r)) {
        l++;
      }
      while ((array[index[r]] > pivot) && (l < r)) {
        r--;
      }
      if (l < r) {
        help = index[l];
        index[l] = index[r];
        index[r] = help;
        l++;
        r--;
      }
    }
    if ((l == r) && (array[index[r]] > pivot)) {
      r--;
    } 

    return r;
  }

  /**
   * Partitions the instances around a pivot. Used by quicksort and
   * kthSmallestValue.
   *
   * @param array the array of integers to be sorted
   * @param index the index into the array of integers
   * @param l the first index of the subset 
   * @param r the last index of the subset 
   *
   * @return the index of the middle element
   */
  private static int partition(int[] array, int[] index, int l, int r) {
    
    double pivot = array[index[(l + r) / 2]];
    int help;

    while (l < r) {
      while ((array[index[l]] < pivot) && (l < r)) {
        l++;
      }
      while ((array[index[r]] > pivot) && (l < r)) {
        r--;
      }
      if (l < r) {
        help = index[l];
        index[l] = index[r];
        index[r] = help;
        l++;
        r--;
      }
    }
    if ((l == r) && (array[index[r]] > pivot)) {
      r--;
    } 

    return r;
  }
  
  /**
   * Implements quicksort according to Manber's "Introduction to
   * Algorithms".
   *
   * @param array the array of doubles to be sorted
   * @param index the index into the array of doubles
   * @param left the first index of the subset to be sorted
   * @param right the last index of the subset to be sorted
   */
  //@ requires 0 <= first && first <= right && right < array.length;
  //@ requires (\forall int i; 0 <= i && i < index.length; 0 <= index[i] && index[i] < array.length);
  //@ requires array != index;
  //  assignable index;
  private static void quickSort(/*@non_null@*/ double[] array, /*@non_null@*/ int[] index, 
                                int left, int right) {

    if (left < right) {
      int middle = partition(array, index, left, right);
      quickSort(array, index, left, middle);
      quickSort(array, index, middle + 1, right);
    }
  }
  
  /**
   * Implements quicksort according to Manber's "Introduction to
   * Algorithms".
   *
   * @param array the array of integers to be sorted
   * @param index the index into the array of integers
   * @param left the first index of the subset to be sorted
   * @param right the last index of the subset to be sorted
   */
  //@ requires 0 <= first && first <= right && right < array.length;
  //@ requires (\forall int i; 0 <= i && i < index.length; 0 <= index[i] && index[i] < array.length);
  //@ requires array != index;
  //  assignable index;
  private static void quickSort(/*@non_null@*/ int[] array, /*@non_null@*/  int[] index, 
                                int left, int right) {

    if (left < right) {
      int middle = partition(array, index, left, right);
      quickSort(array, index, left, middle);
      quickSort(array, index, middle + 1, right);
    }
  }
  
  /**
   * Implements computation of the kth-smallest element according
   * to Manber's "Introduction to Algorithms".
   *
   * @param array the array of double
   * @param index the index into the array of doubles
   * @param left the first index of the subset 
   * @param right the last index of the subset 
   * @param k the value of k
   *
   * @return the index of the kth-smallest element
   */
  //@ requires 0 <= first && first <= right && right < array.length;
  private static int select(/*@non_null@*/ double[] array, /*@non_null@*/ int[] index, 
                            int left, int right, int k) {
    
    if (left == right) {
      return left;
    } else {
      int middle = partition(array, index, left, right);
      if ((middle - left + 1) >= k) {
        return select(array, index, left, middle, k);
      } else {
        return select(array, index, middle + 1, right, k - (middle - left + 1));
      }
    }
  }
  
  /**
   * Implements computation of the kth-smallest element according
   * to Manber's "Introduction to Algorithms".
   *
   * @param array the array of integers
   * @param index the index into the array of integers
   * @param left the first index of the subset 
   * @param right the last index of the subset 
   * @param k the value of k
   *
   * @return the index of the kth-smallest element
   */
  //@ requires 0 <= first && first <= right && right < array.length;
  private static int select(/*@non_null@*/ int[] array, /*@non_null@*/ int[] index, 
                            int left, int right, int k) {
    
    if (left == right) {
      return left;
    } else {
      int middle = partition(array, index, left, right);
      if ((middle - left + 1) >= k) {
        return select(array, index, left, middle, k);
      } else {
        return select(array, index, middle + 1, right, k - (middle - left + 1));
      }
    }
  }

  /**
   * Main method for testing this class.
   *
   * @param ops some dummy options
   */
  public static void main(String[] ops) {

    double[] doublesWithNaN = {4.5, 6.7, Double.NaN, 3.4, 4.8, 1.2, 3.4};
    double[] doubles = {4.5, 6.7, 6.7, 3.4, 4.8, 1.2, 3.4, 6.7, 6.7, 3.4};
    int[] ints = {12, 6, 2, 18, 16, 6, 7, 5, 18, 18, 17};

    try {

      // Option handling
      System.out.println("First option split up:");
      if (ops.length > 0) {
	String[] firstOptionSplitUp = Utils.splitOptions(ops[0]);
	for (int i = 0; i < firstOptionSplitUp.length; i ++) {
	  System.out.println(firstOptionSplitUp[i]);
	}
      }					       
      System.out.println("Partitioned options: ");
      String[] partitionedOptions = Utils.partitionOptions(ops);
      for (int i  = 0; i < partitionedOptions.length; i++) {
	System.out.println(partitionedOptions[i]);
      }
      System.out.println("Get position of flag -f: " + Utils.getOptionPos('f', ops));
      System.out.println("Get flag -f: " + Utils.getFlag('f', ops));
      System.out.println("Get position of option -o: " + Utils.getOptionPos('o', ops));
      System.out.println("Get option -o: " + Utils.getOption('o', ops));
      System.out.println("Checking for remaining options... ");
      Utils.checkForRemainingOptions(ops);
      
      // Statistics
      System.out.println("Original array with NaN (doubles): ");
      for (int i = 0; i < doublesWithNaN.length; i++) {
	System.out.print(doublesWithNaN[i] + " ");
      }
      System.out.println();
      System.out.println("Original array (doubles): ");
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(doubles[i] + " ");
      }
      System.out.println();
      System.out.println("Original array (ints): ");
      for (int i = 0; i < ints.length; i++) {
	System.out.print(ints[i] + " ");
      }
      System.out.println();
      System.out.println("Correlation: " + Utils.correlation(doubles, doubles, 
							     doubles.length));
      System.out.println("Mean: " + Utils.mean(doubles));
      System.out.println("Variance: " + Utils.variance(doubles));
      System.out.println("Sum (doubles): " + Utils.sum(doubles));
      System.out.println("Sum (ints): " + Utils.sum(ints));
      System.out.println("Max index (doubles): " + Utils.maxIndex(doubles));
      System.out.println("Max index (ints): " + Utils.maxIndex(ints));
      System.out.println("Min index (doubles): " + Utils.minIndex(doubles));
      System.out.println("Min index (ints): " + Utils.minIndex(ints));
      System.out.println("Median (doubles): " + 
                         Utils.kthSmallestValue(doubles, doubles.length / 2));
      System.out.println("Median (ints): " + 
                         Utils.kthSmallestValue(ints, ints.length / 2));

      // Sorting and normalizing
      System.out.println("Sorted array with NaN (doubles): ");
      int[] sorted = Utils.sort(doublesWithNaN);
      for (int i = 0; i < doublesWithNaN.length; i++) {
	System.out.print(doublesWithNaN[sorted[i]] + " ");
      }
      System.out.println();
      System.out.println("Sorted array (doubles): ");
      sorted = Utils.sort(doubles);
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(doubles[sorted[i]] + " ");
      }
      System.out.println();
      System.out.println("Sorted array (ints): ");
      sorted = Utils.sort(ints);
      for (int i = 0; i < ints.length; i++) {
	System.out.print(ints[sorted[i]] + " ");
      }
      System.out.println();
      System.out.println("Indices from stable sort (doubles): ");
      sorted = Utils.stableSort(doubles);
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(sorted[i] + " ");
      }
      System.out.println();
      System.out.println("Indices from sort (ints): ");
      sorted = Utils.sort(ints);
      for (int i = 0; i < ints.length; i++) {
	System.out.print(sorted[i] + " ");
      }
      System.out.println();
      System.out.println("Normalized array (doubles): ");
      Utils.normalize(doubles);
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(doubles[i] + " ");
      }
      System.out.println();
      System.out.println("Normalized again (doubles): ");
      Utils.normalize(doubles, Utils.sum(doubles));
      for (int i = 0; i < doubles.length; i++) {
	System.out.print(doubles[i] + " ");
      }
      System.out.println();
      
      // Pretty-printing
      System.out.println("-4.58: " + Utils.doubleToString(-4.57826535, 2));
      System.out.println("-6.78: " + Utils.doubleToString(-6.78214234, 6,2));
      
      // Comparisons
      System.out.println("5.70001 == 5.7 ? " + Utils.eq(5.70001, 5.7));
      System.out.println("5.70001 > 5.7 ? " + Utils.gr(5.70001, 5.7));
      System.out.println("5.70001 >= 5.7 ? " + Utils.grOrEq(5.70001, 5.7));
      System.out.println("5.7 < 5.70001 ? " + Utils.sm(5.7, 5.70001));
      System.out.println("5.7 <= 5.70001 ? " + Utils.smOrEq(5.7, 5.70001));
      
      // Math
      System.out.println("Info (ints): " + Utils.info(ints));
      System.out.println("log2(4.6): " + Utils.log2(4.6));
      System.out.println("5 * log(5): " + Utils.xlogx(5));
      System.out.println("5.5 rounded: " + Utils.round(5.5));
      System.out.println("5.55555 rounded to 2 decimal places: " + 
			 Utils.roundDouble(5.55555, 2));
      
      // Arrays
      System.out.println("Array-Dimensions of 'new int[][]': " + Utils.getArrayDimensions(new int[][]{}));
      System.out.println("Array-Dimensions of 'new int[][]{{1,2,3},{4,5,6}}': " + Utils.getArrayDimensions(new int[][]{{1,2,3},{4,5,6}}));
      String[][][] s = new String[3][4][];
      System.out.println("Array-Dimensions of 'new String[3][4][]': " + Utils.getArrayDimensions(s));
    } catch (Exception e) {
      e.printStackTrace();
    }
  }
}