contingencytables.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

    if (Utils.eq(total, 0)) {
      return 0;
    }
    return (returnValue + lnFunc(total)) / (total * log2);
  }

  /**
   * Computes gain ratio for contingency table (split on rows).
   * Returns Double.MAX_VALUE if the split entropy is 0.
   *
   * @param matrix the contingency table
   * @return the gain ratio
   */
  public static double gainRatio(double[][] matrix){
    
    double preSplit = 0, postSplit = 0, splitEnt = 0,
      sumForRow, sumForColumn, total = 0, infoGain;

    // Compute entropy before split
    for (int i = 0; i < matrix[0].length; i++) {
      sumForColumn = 0;
      for (int j = 0; j < matrix.length; j++) 
	sumForColumn += matrix[j][i];
      preSplit += lnFunc(sumForColumn);
      total += sumForColumn;
    }
    preSplit -= lnFunc(total);

    // Compute entropy after split and split entropy
    for (int i = 0; i < matrix.length; i++) {
      sumForRow = 0;
      for (int j = 0; j < matrix[0].length; j++) {
	postSplit += lnFunc(matrix[i][j]);
	sumForRow += matrix[i][j];
      }
      splitEnt += lnFunc(sumForRow);
    }
    postSplit -= splitEnt;
    splitEnt -= lnFunc(total);

    infoGain = preSplit - postSplit;
    if (Utils.eq(splitEnt, 0))
      return 0;
    return infoGain / splitEnt;
  }

  /**
   * Returns negative base 2 logarithm of multiple hypergeometric
   * probability for a contingency table.
   *
   * @param matrix the contingency table
   * @return the log of the hypergeometric probability of the contingency table 
   */
  public static double log2MultipleHypergeometric(double[][] matrix) {

    double sum = 0, sumForRow, sumForColumn, total = 0;

    for (int i = 0; i < matrix.length; i++) {
      sumForRow = 0;
      for (int j = 0; j < matrix[i].length; j++) {
	sumForRow += matrix[i][j];
      }
      sum += SpecialFunctions.lnFactorial(sumForRow);
      total += sumForRow;
    }
    for (int j = 0; j < matrix[0].length; j++) {
      sumForColumn = 0;
      for (int i = 0; i < matrix.length; i++) {
	sumForColumn += matrix [i][j];
      }
      sum += SpecialFunctions.lnFactorial(sumForColumn);
    }
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
	sum -= SpecialFunctions.lnFactorial(matrix[i][j]);
      }
    }
    sum -= SpecialFunctions.lnFactorial(total);
    return -sum / log2;
  }

  /**
   * Reduces a matrix by deleting all zero rows and columns.
   *
   * @param matrix the matrix to be reduced
   * @param the matrix with all zero rows and columns deleted
   */
  public static double[][] reduceMatrix(double[][] matrix) {

    int row, col, currCol, currRow, nrows, ncols, 
      nonZeroRows = 0, nonZeroColumns = 0;
    double[] rtotal, ctotal;
    double[][] newMatrix;

    nrows = matrix.length;
    ncols = matrix[0].length;
    rtotal = new double [nrows];
    ctotal = new double [ncols];
    for (row = 0; row < nrows; row++) {
      for (col = 0; col < ncols; col++) {
	rtotal[row] += matrix[row][col];
	ctotal[col] += matrix[row][col];
      }
    }
    for (row = 0; row < nrows; row++) {
      if (Utils.gr(rtotal[row],0)) {
	nonZeroRows++;
      }
    }
    for (col = 0; col < ncols; col++) {
      if (Utils.gr(ctotal[col],0)) {
	nonZeroColumns++;
      }
    }
    newMatrix = new double[nonZeroRows][nonZeroColumns];
    currRow = 0;
    for (row = 0; row < nrows; row++) {
      if (Utils.gr(rtotal[row],0)) {
	currCol = 0;
	for (col = 0; col < ncols; col++) {
	  if (Utils.gr(ctotal[col],0)) {
	    newMatrix[currRow][currCol] = matrix[row][col];
	    currCol++;
	  }
	}
	currRow++;
      }
    }
    return newMatrix;
  }
    
   /**
    * Calculates the symmetrical uncertainty for base 2.
    *
    * @param matrix the contingency table
    * @return the calculated symmetrical uncertainty
    *
    */
  public static double symmetricalUncertainty(double matrix[][]) {

    double sumForColumn, sumForRow, total = 0, columnEntropy = 0, 
      rowEntropy = 0, entropyConditionedOnRows = 0, infoGain = 0;

    // Compute entropy for columns
    for (int i = 0; i < matrix[0].length; i++) {
      sumForColumn = 0;
      for (int j = 0; j < matrix.length; j++) {
	sumForColumn += matrix[j][i];
      }
      columnEntropy += lnFunc(sumForColumn);
      total += sumForColumn;
    }
    columnEntropy -= lnFunc(total);

    // Compute entropy for rows and conditional entropy
    for (int i = 0; i < matrix.length; i++) {
      sumForRow = 0;
      for (int j = 0; j < matrix[0].length; j++) { 
	sumForRow += matrix[i][j];
	entropyConditionedOnRows += lnFunc(matrix[i][j]);
      }
      rowEntropy += lnFunc(sumForRow);
    }
    entropyConditionedOnRows -= rowEntropy;
    rowEntropy -= lnFunc(total);
    infoGain = columnEntropy - entropyConditionedOnRows;
    if (Utils.eq(columnEntropy, 0) || Utils.eq(rowEntropy, 0))
      return 0;
    return 2.0 * (infoGain / (columnEntropy + rowEntropy));
  }

  /**
   * Computes Goodman and Kruskal's tau-value for a contingency table.
   *
   * @param matrix the contingency table
   * @param Goodman and Kruskal's tau-value
   */
  public static double tauVal(double[][] matrix) {
    
    int nrows, ncols, row, col;
    double [] ctotal;
    double maxcol = 0, max, maxtotal = 0, n = 0;
    
    nrows = matrix.length;
    ncols = matrix[0].length;
    ctotal = new double [ncols];
    for (row = 0; row < nrows; row++) {
      max = 0;
      for (col = 0; col < ncols; col++) {
	if (Utils.gr(matrix[row][col], max)) 
	  max = matrix[row][col];
	ctotal[col] += matrix[row][col];
	n += matrix[row][col];
      }
      maxtotal += max;
    }
    if (Utils.eq(n, 0)) {
      return 0;
    }
    maxcol = ctotal[Utils.maxIndex(ctotal)];
    return (maxtotal - maxcol)/(n - maxcol);
  }

  /**
   * Help method for computing entropy.
   */
  private static double lnFunc(double num){
    
    // Constant hard coded for efficiency reasons
    if (num < 1e-6) {
      return 0;
    } else {
      return num * Math.log(num);
    }
  }

  /**
   * Computes chi-value for one cell in a contingency table.
   *
   * @param freq the observed frequency in the cell
   * @param expected the expected frequency in the cell
   * @return the chi-value for that cell; 0 if the expected value is
   * too close to zero 
   */
  private static double chiCell(double freq, double expected, 
                                boolean yates){

    // Cell in empty row and column?
    if (Utils.smOrEq(expected, 0)) {
      return 0;
    }

    // Compute difference between observed and expected value
    double diff = Math.abs(freq - expected);
    if (yates) {

      // Apply Yates' correction if wanted
      diff -= 0.5;

      // The difference should never be negative
      if (diff < 0) {
        diff = 0;
      }
    }

    // Return chi-value for the cell
    return (diff * diff / expected);
  }

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

    double[] firstRow = {10, 5, 20};
    double[] secondRow = {2, 10, 6};
    double[] thirdRow = {5, 10, 10};
    double[][] matrix = new double[3][0];

    matrix[0] = firstRow; matrix[1] = secondRow; matrix[2] = thirdRow;
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
	System.out.print(matrix[i][j] + " ");
      }
      System.out.println();
    }
    System.out.println("Chi-squared probability: " +
		       ContingencyTables.chiSquared(matrix, false));
    System.out.println("Chi-squared value: " +
		       ContingencyTables.chiVal(matrix, false));
    System.out.println("Cochran's criterion fullfilled: " +
		       ContingencyTables.cochransCriterion(matrix));
    System.out.println("Cramer's V: " +
		       ContingencyTables.CramersV(matrix));
    System.out.println("Entropy of first row: " +
		       ContingencyTables.entropy(firstRow));
    System.out.println("Entropy conditioned on columns: " +
		       ContingencyTables.entropyConditionedOnColumns(matrix));
    System.out.println("Entropy conditioned on rows: " +
		       ContingencyTables.entropyConditionedOnRows(matrix));
    System.out.println("Entropy conditioned on rows (with Laplace): " +
		       ContingencyTables.entropyConditionedOnRows(matrix, matrix, 3));
    System.out.println("Entropy of rows: " +
		       ContingencyTables.entropyOverRows(matrix));
    System.out.println("Entropy of columns: " +
		       ContingencyTables.entropyOverColumns(matrix));
    System.out.println("Gain ratio: " +
		       ContingencyTables.gainRatio(matrix));
    System.out.println("Negative log2 of multiple hypergeometric probability: " +
		       ContingencyTables.log2MultipleHypergeometric(matrix));
    System.out.println("Symmetrical uncertainty: " +
		       ContingencyTables.symmetricalUncertainty(matrix));
    System.out.println("Tau value: " +
		       ContingencyTables.tauVal(matrix));
    double[][] newMatrix = new double[3][3];
    newMatrix[0][0] = 1; newMatrix[0][1] = 0; newMatrix[0][2] = 1;
    newMatrix[1][0] = 0; newMatrix[1][1] = 0; newMatrix[1][2] = 0;
    newMatrix[2][0] = 1; newMatrix[2][1] = 0; newMatrix[2][2] = 1;
    System.out.println("Matrix with empty row and column: ");
    for (int i = 0; i < newMatrix.length; i++) {
      for (int j = 0; j < newMatrix[i].length; j++) {
	System.out.print(newMatrix[i][j] + " ");
      }
      System.out.println();
    }
    System.out.println("Reduced matrix: ");
    newMatrix = ContingencyTables.reduceMatrix(newMatrix);
    for (int i = 0; i < newMatrix.length; i++) {
      for (int j = 0; j < newMatrix[i].length; j++) {
	System.out.print(newMatrix[i][j] + " ");
      }
      System.out.println();
    }
  }
}