mssricc.cc

一种聚类算法,名字是cocluster

  rowCS[rowCL[fromRow]]--;
  rowCS[toCluster]++;
  isReversed[fromRow] = tempIsReversed;

  if (tempIsReversed){
    myCRS->addRow(Acompressed, rowCL[fromRow], fromRow, colCL);
    rowQuality4Compressed[rowCL[fromRow]] = computeRowQuality4Compressed2WayUnnormalized(rowCL[fromRow]);
    myCRS->subtractRow(Acompressed, toCluster, fromRow, colCL);
    rowQuality4Compressed[toCluster] = computeRowQuality4Compressed2WayUnnormalized(toCluster);
  } else {
    myCRS->subtractRow(Acompressed, rowCL[fromRow], fromRow, colCL);
    rowQuality4Compressed[rowCL[fromRow]] = computeRowQuality4Compressed2WayUnnormalized(rowCL[fromRow]);
    myCRS->addRow(Acompressed, toCluster, fromRow, colCL);
    rowQuality4Compressed[toCluster] = computeRowQuality4Compressed2WayUnnormalized(toCluster);
  }
  
  rowCL[fromRow] = toCluster;
  delete [] compressedRow;
  checkDumpLevel4Cocluster(dumpFile);
}


void MssrIcc::doColLocalSearch(oneStep trace [], int step)
{
  int fromCol = 0, tempCluster, toCluster, tempColCL;
  double delta1, delta2, minDelta = MY_DBL_MAX, minDelta2 = MY_DBL_MAX;
  double *compressedCol = new double [numRowCluster];
  trace[step].id = 0;
  trace[step].fromCluster = colCL[0];
  trace[step].toCluster = toCluster = colCL[0];
  trace[step].change = 0;
/*
computeAcompressed();
isNormalizedCompressed = false;
computeColQuality4Compressed2WayUnnormalized();
*/
  for(int c = 0; c < numCol; c++){
    tempColCL = colCL[c];
    if (colCS[tempColCL] > 1  && !isColMarked[c]){
      tempCluster = tempColCL;
      minDelta2 = MY_DBL_MAX;
      for(int rc = 0; rc < numRowCluster; rc++)
	compressedCol[rc] = Acompressed[rc][tempColCL];
      myCCS->subtractCol(compressedCol, c, rowCL);
      delta1 = colQuality4Compressed[tempColCL] - computeColQuality4Compressed2WayUnnormalized(compressedCol, colCS[tempColCL]-1);
      for (int cc = 0; cc < tempColCL; cc++){
        for(int rc = 0; rc < numRowCluster; rc++)
          compressedCol[rc] = Acompressed[rc][cc];
        myCCS->addCol(compressedCol, c, rowCL);
        delta2 = colQuality4Compressed[cc] - computeColQuality4Compressed2WayUnnormalized(compressedCol, colCS[cc]+1);
        updateVariable(minDelta2, tempCluster, delta2, cc);
      }
      for (int cc = tempColCL+1; cc < numColCluster; cc++){
        for(int rc = 0; rc < numRowCluster; rc++)
          compressedCol[rc] = Acompressed[rc][cc];
        myCCS->addCol(compressedCol, c, rowCL);
        delta2 = colQuality4Compressed[cc] - computeColQuality4Compressed2WayUnnormalized(compressedCol, colCS[cc]+1);
        updateVariable(minDelta2, tempCluster, delta2, cc);
      }
      if ((delta1 + minDelta2) < minDelta){
	fromCol = c;
	toCluster = tempCluster;
        minDelta = delta1 + minDelta2;
      }
      checkDumpLevel4DeltaTrace("col", c, tempCluster, delta1, minDelta2);
    }
  }
  isColMarked[fromCol] = true;
  trace[step].id = fromCol;
  trace[step].fromCluster = colCL[fromCol];
  trace[step].toCluster = toCluster;
  trace[step].change = minDelta;
  colCS[colCL[fromCol]]--;
  colCS[toCluster]++;

  myCCS->subtractCol(Acompressed, colCL[fromCol], fromCol, rowCL);
  colQuality4Compressed[colCL[fromCol]] = computeColQuality4Compressed2WayUnnormalized(colCL[fromCol]);
  myCCS->addCol(Acompressed, toCluster, fromCol, rowCL);
  colQuality4Compressed[toCluster] = computeColQuality4Compressed2WayUnnormalized(toCluster);

  colCL[fromCol] = toCluster;
  delete [] compressedCol;
  checkDumpLevel4Cocluster(dumpFile);
}



void MssrIcc::doColLocalSearch(oneStep trace [], int step, bool *isReversed)
{
  int fromCol = 0, tempCluster, toCluster, tempColCL;
  double delta1, delta2, minDelta = MY_DBL_MAX, minDelta2 = MY_DBL_MAX;
  double *compressedCol = new double [numRowCluster];
  trace[step].id = 0;
  trace[step].fromCluster = colCL[0];
  trace[step].toCluster = toCluster = colCL[0];
  trace[step].change = 0;
/*
computeAcompressed(isReversed);
isNormalizedCompressed = false;
computeColQuality4Compressed2WayUnnormalized();
*/
  for(int c = 0; c < numCol; c++){
    tempColCL = colCL[c];
    if (colCS[tempColCL] > 1  && !isColMarked[c]){
      tempCluster = tempColCL;
      minDelta2 = MY_DBL_MAX;
      for(int rc = 0; rc < numRowCluster; rc++)
	compressedCol[rc] = Acompressed[rc][tempColCL];
      myCCS->subtractCol(compressedCol, c, rowCL, isReversed);
      delta1 = colQuality4Compressed[tempColCL] - computeColQuality4Compressed2WayUnnormalized(compressedCol, colCS[tempColCL]-1);
      for (int cc = 0; cc < tempColCL; cc++){
        for(int rc = 0; rc < numRowCluster; rc++)
          compressedCol[rc] = Acompressed[rc][cc];
        myCCS->addCol(compressedCol, c, rowCL, isReversed);
        delta2 = colQuality4Compressed[cc] - computeColQuality4Compressed2WayUnnormalized(compressedCol, colCS[cc]+1);
        updateVariable(minDelta2, tempCluster, delta2, cc);
      }
      for (int cc = tempColCL+1; cc < numColCluster; cc++){
        for(int rc = 0; rc < numRowCluster; rc++)
          compressedCol[rc] = Acompressed[rc][cc];
        myCCS->addCol(compressedCol, c, rowCL, isReversed);
        delta2 = colQuality4Compressed[cc] - computeColQuality4Compressed2WayUnnormalized(compressedCol, colCS[cc]+1);
        updateVariable(minDelta2, tempCluster, delta2, cc);
      }
      if ((delta1 + minDelta2) < minDelta){
	fromCol = c;
	toCluster = tempCluster;
        minDelta = delta1 + minDelta2;
      }
      checkDumpLevel4DeltaTrace("col", c, tempCluster, delta1, minDelta2);
    }
  }
  isColMarked[fromCol] = true;
  trace[step].id = fromCol;
  trace[step].fromCluster = colCL[fromCol];
  trace[step].toCluster = toCluster;
  trace[step].change = minDelta;
  colCS[colCL[fromCol]]--;
  colCS[toCluster]++;

  myCCS->subtractCol(Acompressed, colCL[fromCol], fromCol, rowCL, isReversed);
  colQuality4Compressed[colCL[fromCol]] = computeColQuality4Compressed2WayUnnormalized(colCL[fromCol]);
  myCCS->addCol(Acompressed, toCluster, fromCol, rowCL, isReversed);
  colQuality4Compressed[toCluster] = computeColQuality4Compressed2WayUnnormalized(toCluster);

  colCL[fromCol] = toCluster;
  delete [] compressedCol;
  checkDumpLevel4Cocluster(dumpFile);
}


bool MssrIcc::doRowLocalSearchChain()
{
  checkDumpLevel4LocalSearch("beginRow");
  bool isHelpful = false;
  int minIndex;
  double *totalChange = new double [rowLocalSearchLength], minChange;
  oneStep *trace = new oneStep[rowLocalSearchLength];

  for (int i = 0; i < rowLocalSearchLength; i++){
    if (isTakingReverse)
      doRowLocalSearch(trace, i, isReversed);
    else
      doRowLocalSearch(trace, i);
    checkDumpLevel4LocalSearch("row", trace[i].id, trace[i].fromCluster, trace[i].toCluster, trace[i].change);
  }
  totalChange[0] = trace[0].change;
  minChange = trace[0].change;
  minIndex = 0;
  for(int i = 1; i < rowLocalSearchLength; i++)
    totalChange[i] = totalChange[i-1] + trace[i].change;
  for(int i = 0; i < rowLocalSearchLength; i++)
//    if (totalChange[i] <= minChange){
    if (totalChange[i] < minChange){
      minChange = totalChange[i];
      minIndex = i;
    }
  if (totalChange[minIndex] > (rowLocalSearchThreshold * squaredFNormA)){
    checkDumpLevel4NumOfChain("row", 0, NULL);
    if (isTakingReverse)
      recoverRowCL(0, rowLocalSearchLength, trace, isReversed);
    else
      recoverRowCL(0, rowLocalSearchLength, trace);
    isHelpful = false;
  } else {		//   i.e. if(totalChange[minIndex] <= (rowLocalSearchThreshold * squaredFNormA))
    checkDumpLevel4NumOfChain("row", minIndex, totalChange);
    if (isTakingReverse)
      recoverRowCL(minIndex+1, rowLocalSearchLength, trace, isReversed);
    else
      recoverRowCL(minIndex+1, rowLocalSearchLength, trace);
    isHelpful = true;
  }
  delete [] totalChange;
  delete [] trace;
  checkDumpLevel4Cocluster(dumpFile);
  checkDumpLevel4LocalSearch("endRow");
  return isHelpful;
}

     
bool MssrIcc::doColLocalSearchChain()
{
  checkDumpLevel4LocalSearch("beginCol");
  bool isHelpful = false;
  int minIndex;
  double *totalChange = new double [colLocalSearchLength], minChange;
  oneStep *trace = new oneStep [colLocalSearchLength];

  for (int i = 0; i < colLocalSearchLength; i++){
    if (isTakingReverse)
      doColLocalSearch(trace, i, isReversed);
    else
      doColLocalSearch(trace, i);
    checkDumpLevel4LocalSearch("col", trace[i].id, trace[i].fromCluster, trace[i].toCluster, trace[i].change);
  }
  totalChange[0] = trace[0].change;
  minChange = trace[0].change;
  minIndex = 0;
  for(int i = 1; i < colLocalSearchLength; i++)
    totalChange[i] = totalChange[i-1] + trace[i].change;
  for(int i = 0; i < colLocalSearchLength; i++)
//    if (totalChange[i] <= minChange){
    if (totalChange[i] < minChange){
      minChange = totalChange[i];
      minIndex = i;
    }
  if (totalChange[minIndex] > (colLocalSearchThreshold * squaredFNormA)){
    checkDumpLevel4NumOfChain("col", 0, NULL);
    if (isTakingReverse)
      recoverColCL(0, colLocalSearchLength, trace, isReversed);
    else
      recoverColCL(0, colLocalSearchLength, trace);
    isHelpful = false;
  } else { 		//  i.e., if( totalChange[minIndex] <= (colLocalSearchThreshold * sqrt(squaredFNormA)))
    checkDumpLevel4NumOfChain("col", minIndex, totalChange);
    if (isTakingReverse)
      recoverColCL(minIndex+1, colLocalSearchLength, trace, isReversed);
    else
      recoverColCL(minIndex+1, colLocalSearchLength, trace);
    isHelpful = true;
  }
  delete [] totalChange;
  delete [] trace;
  checkDumpLevel4Cocluster(dumpFile);
  checkDumpLevel4LocalSearch("endCol");
  return isHelpful;
}


void MssrIcc::doPingPong()
{
  bool isRowLocalSearchHelpful = false, isColLocalSearchHelpful = false;
  numIteration = 0;
  do {
    isRowLocalSearchHelpful = false;
    isColLocalSearchHelpful = false;
    numIteration++;
    
    checkDumpLevel4PingPong("begin", numIteration);

    if (isTakingReverse){

      switch (batchUpdateType){
        case SINGLE_RESPECTIVELY:
          doBatchUpdate(isReversed);
          break;
        case SINGLE_IN_BATCH:
          doBatchUpdate4VariationI(isReversed);
          break;
        case MULTIPLE_RESPECTIVELY:
          doBatchUpdate4VariationII(isReversed);
          break;
        case SINGLE_BY_FLIP:
          doBatchUpdate4VariationIII(isReversed);
          break;
        case MULTIPLE_BY_FLIP:
          doBatchUpdate4VariationIV(isReversed);
          break;
	default:
	  break;
      }

      //-----------------------------------------
      // To avoid empty row cluster(s)...
      if (isAvoidingEmptyRowCluster){
        computeRowClusterSize();
//        rowLocalSearchLength = getEmptyRC();
        if (getEmptyRC() > 0)
          rowLocalSearchLength = DEFAULT_ROW_LOCAL_SEARCH_LENGTH;
        else
          rowLocalSearchLength = 0;
      }
      //-----------------------------------------       
      if (rowLocalSearchLength > 0){
        clearMark4Row();
        computeAcompressed(isReversed);
        isNormalizedCompressed = false;
        computeRowQuality4Compressed2WayUnnormalized();
        isRowLocalSearchHelpful = doRowLocalSearchChain();
      }
      //-----------------------------------------
      // To avoid empty col cluster(s)...
      if (isAvoidingEmptyColCluster){
        computeColClusterSize();
//        colLocalSearchLength = getEmptyCC();
        if (getEmptyCC() > 0)
          colLocalSearchLength = DEFAULT_COL_LOCAL_SEARCH_LENGTH;
        else
          colLocalSearchLength = 0;
      }
      //-----------------------------------------
      if (colLocalSearchLength > 0){
        clearMark4Col();
        computeAcompressed(isReversed);
        isNormalizedCompressed = false;
        computeColQuality4Compressed2WayUnnormalized();
        isColLocalSearchHelpful = doColLocalSearchChain();
      }

    } else {

      switch (batchUpdateType){
        case SINGLE_RESPECTIVELY:
          doBatchUpdate();
          break;
        case SINGLE_IN_BATCH:
          doBatchUpdate4VariationI();
          break;
        case MULTIPLE_RESPECTIVELY:
          doBatchUpdate4VariationII();
          break;
        case SINGLE_BY_FLIP:
          doBatchUpdate4VariationIII();
          break;
        case MULTIPLE_BY_FLIP:
          doBatchUpdate4VariationIV();
          break;
	default:
	  break;
      }

      //-----------------------------------------
      // To avoid empty row cluster(s)...
      if (isAvoidingEmptyRowCluster){
        computeRowClusterSize();
//        rowLocalSearchLength = getEmptyRC();
        if (getEmptyRC() > 0)
          rowLocalSearchLength = DEFAULT_ROW_LOCAL_SEARCH_LENGTH;
        else
          rowLocalSearchLength = 0;
      }
      //-----------------------------------------       
      if (rowLocalSearchLength > 0){
        clearMark4Row();
	computeAcompressed();
        isNormalizedCompressed = false;
        computeRowQuality4Compressed2WayUnnormalized();
        isRowLocalSearchHelpful = doRowLocalSearchChain();
      }
      //-----------------------------------------
      // To avoid empty col cluster(s)...
      if (isAvoidingEmptyColCluster){
        computeColClusterSize();
//        colLocalSearchLength = getEmptyCC();
        if (getEmptyCC() > 0)
          colLocalSearchLength = DEFAULT_COL_LOCAL_SEARCH_LENGTH;
        else
          colLocalSearchLength = 0;
      }
      //-----------------------------------------
      if (colLocalSearchLength > 0){
        clearMark4Col();
        computeAcompressed();
        isNormalizedCompressed = false;
        computeColQuality4Compressed2WayUnnormalized();
        isColLocalSearchHelpful = doColLocalSearchChain();
      }
    }
    checkDumpLevel4PingPong("end", numIteration);

  } while ((isRowLocalSearchHelpful || isColLocalSearchHelpful) && (numIteration <= DEFAULT_MAX_PINGPONG_ITERATION));

  if (isComputingOneWayObjective){
    computeRowCentroid();
    normalizeRowCentroid();
    computeObjectiveFunction4RowCluster();
    computeColCentroid();
    normalizeColCentroid();  
    computeObjectiveFunction4ColCluster();
  }
  checkDumpLevel4FinalObjectValue();
  switch (dumpLevel){
    case MINIMUM_DUMP_LEVEL:
      break;
    case BATCH_UPDATE_DUMP_LEVEL:
    case LOCAL_SEARCH_DUMP_LEVEL: