mssricc.cc

一种聚类算法,名字是cocluster

    tempColSmoothingFactor *= myCCS->getAnnealingFactor();
  } while ((oldObjValue - objValue) > (colBatchUpdateThreshold * squaredFNormA));
  colSmoothingFactor = tempColSmoothingFactor;
  checkDumpLevel4BatchUpdate("end");
}


/*
// It doesn't guarantee the monotonic decrease of objective function values.
void MssrIcc::doBatchUpdate4VariationIII(bool *isReversed)
{
  checkDumpLevel4BatchUpdate("begin");
  bool *beforeIsReversed = new bool[numRow];
  bool *afterIsReversed = new bool[numRow];
  int numIteration = 0, numRowIteration = 0, numColIteration = 0;
  int *beforeRowCL = new int[numRow];
  int *afterRowCL = new int[numRow];
  double oldObjValue;
  double tempRowSmoothingFactor = rowSmoothingFactor, tempColSmoothingFactor = colSmoothingFactor;
  
  computeRowClusterSize();
  computeColClusterSize();
  computeAcompressed(isReversed);
  isNormalizedCompressed = false;
  normalizeCompressedMatrix();
  do {
    numIteration++;
    for (int r = 0; r < numRow; r++){
      beforeIsReversed[r] = isReversed[r];
      beforeRowCL[r] = rowCL[r];
    }
    myCRS->setSmoothingFactor(smoothingType, tempRowSmoothingFactor);
    myCCS->setSmoothingFactor(smoothingType, tempColSmoothingFactor);
    do {
      numRowIteration++;
      myCRS->setSmoothingFactor(smoothingType, tempRowSmoothingFactor);
      oldObjValue = objValue;
      computeRowQuality4Compressed1WayNormalized();
//-----------
      reassignRC(isReversed);
      computeRowClusterSize();
      computeAcompressed(isReversed);
      isNormalizedCompressed = false;
      normalizeCompressedMatrix();
      computeObjectiveFunction4Normalized();
      checkDumpLevel4BatchUpdate("row", numRowIteration);
      tempRowSmoothingFactor *= myCRS->getAnnealingFactor();
    } while ((oldObjValue - objValue) > (rowBatchUpdateThreshold * squaredFNormA));
//-----------
    for (int r = 0; r < numRow; r++){
      afterIsReversed[r] = isReversed[r];
      isReversed[r] = beforeIsReversed[r];
      afterRowCL[r] = rowCL[r];
      rowCL[r] = beforeRowCL[r];
    }
    computeRowClusterSize();
    computeAcompressed(isReversed);
    isNormalizedCompressed = false;
    normalizeCompressedMatrix();
    for (int r = 0; r < numRow; r++){
      isReversed[r] = afterIsReversed[r];
      rowCL[r] = afterRowCL[r];
    }
    computeRowClusterSize();
    tempRowSmoothingFactor = rowSmoothingFactor;
    myCRS->setSmoothingFactor(smoothingType, tempRowSmoothingFactor);
//-----------
    do {
      numColIteration++;
      myCCS->setSmoothingFactor(smoothingType, tempColSmoothingFactor);
      oldObjValue = objValue;
      computeColQuality4Compressed1WayNormalized();
      reassignCC(isReversed);
      computeColClusterSize();
      computeAcompressed(isReversed);
      isNormalizedCompressed = false;
      normalizeCompressedMatrix();
      computeObjectiveFunction4Normalized(Acompressed, isReversed);
      checkDumpLevel4BatchUpdate("col", numColIteration);
      tempColSmoothingFactor *= myCCS->getAnnealingFactor();
    } while ((oldObjValue - objValue) > (colBatchUpdateThreshold * squaredFNormA));
//-----------
    oldObjValue = objValue;
    computeRowClusterSize();
    computeAcompressed(isReversed);
    isNormalizedCompressed = false;
    normalizeCompressedMatrix();
    computeObjectiveFunction4Normalized();
    checkDumpLevel4BatchUpdate("both", numIteration);
//-----------
  } while ((oldObjValue - objValue) > (rowBatchUpdateThreshold * squaredFNormA));
  colSmoothingFactor = tempColSmoothingFactor;
  delete [] beforeIsReversed;
  delete [] afterIsReversed;
  delete [] beforeRowCL;
  delete [] afterRowCL;
  checkDumpLevel4BatchUpdate("end");
}
*/


void MssrIcc::doBatchUpdate4VariationIII(bool *isReversed)
{
  checkDumpLevel4BatchUpdate("begin");
  int numIteration = 0;
  double oldObjValue;
  computeAcompressed(isReversed);
  isNormalizedCompressed = false;
  normalizeCompressedMatrix();

  do {
    numIteration++;
    myCRS->setSmoothingFactor(smoothingType, rowSmoothingFactor);
    myCCS->setSmoothingFactor(smoothingType, colSmoothingFactor);
    oldObjValue = objValue;

    if (randNumGenerator.GetUniform() > SELECTION_PROBABILITY){
      computeRowQuality4Compressed1WayNormalized();
      reassignRC(isReversed);
      computeRowClusterSize();
      computeAcompressed(isReversed);
      isNormalizedCompressed = false;
      normalizeCompressedMatrix();
      computeObjectiveFunction4Normalized();
      checkDumpLevel4BatchUpdate("row", numIteration);
    } else {
      computeColQuality4Compressed1WayNormalized();
      reassignCC(isReversed);
      computeColClusterSize();
      computeAcompressed(isReversed);
      isNormalizedCompressed = false;
      normalizeCompressedMatrix();
      computeObjectiveFunction4Normalized();
      checkDumpLevel4BatchUpdate("col", numIteration);
    }    
    rowSmoothingFactor *= myCRS->getAnnealingFactor();
    colSmoothingFactor *= myCCS->getAnnealingFactor();

  } while ((oldObjValue - objValue) > (rowBatchUpdateThreshold * squaredFNormA));

  checkDumpLevel4BatchUpdate("end");
}


void MssrIcc::doBatchUpdate4VariationIV(bool *isReversed)
{
  checkDumpLevel4BatchUpdate("begin");
  int numIteration = 0;
  double oldObjValue;
  computeAcompressed(isReversed);
  isNormalizedCompressed = false;
  normalizeCompressedMatrix();

  do {
    numIteration++;
    myCRS->setSmoothingFactor(smoothingType, rowSmoothingFactor);
    myCCS->setSmoothingFactor(smoothingType, colSmoothingFactor);

    if (randNumGenerator.GetUniform() > SELECTION_PROBABILITY){
      do {
        oldObjValue = objValue;
        computeRowQuality4Compressed1WayNormalized();
        reassignRC(isReversed);
        computeRowClusterSize();
        computeAcompressed(isReversed);
        isNormalizedCompressed = false;
        normalizeCompressedMatrix();
        computeObjectiveFunction4Normalized();
        checkDumpLevel4BatchUpdate("row", numIteration);
      } while ((oldObjValue - objValue) > (MULTIPLE_FACTOR * rowBatchUpdateThreshold * squaredFNormA));
    } else {
      do {
        oldObjValue = objValue;
	computeColQuality4Compressed1WayNormalized();
        reassignCC(isReversed);
        computeColClusterSize();
        computeAcompressed(isReversed);
        isNormalizedCompressed = false;
        normalizeCompressedMatrix();
        computeObjectiveFunction4Normalized();
        checkDumpLevel4BatchUpdate("col", numIteration);
      } while ((oldObjValue - objValue) > (MULTIPLE_FACTOR * colBatchUpdateThreshold * squaredFNormA));
    }    
    rowSmoothingFactor *= myCRS->getAnnealingFactor();
    colSmoothingFactor *= myCCS->getAnnealingFactor();

  } while ((oldObjValue - objValue) > (rowBatchUpdateThreshold * squaredFNormA));

  checkDumpLevel4BatchUpdate("end");
}


void MssrIcc::recoverRowCL(int begin, int end, oneStep trace [])
{
  for(int r = begin; r < end; r++)
    if (trace[r].toCluster != trace[r].fromCluster) {
//        myCRS->subtractRow(Acompressed, trace[r].toCluster, trace[r].id, colCL);
        rowCS[trace[r].toCluster]--;
//        myCRS->addRow(Acompressed, trace[r].fromCluster, trace[r].id, colCL);
        rowCS[trace[r].fromCluster]++;
        rowCL[trace[r].id] = trace[r].fromCluster;
    }
}


void MssrIcc::recoverRowCL(int begin, int end, oneStep trace [], bool *isReversed)
{
  for(int r = begin; r < end; r++)
    if (isReversed[r])
      if (trace[r].toCluster != trace[r].fromCluster) {
//        myCRS->addRow(Acompressed, trace[r].toCluster, trace[r].id, colCL);
        rowCS[trace[r].toCluster]--;
//        myCRS->subtractRow(Acompressed, trace[r].fromCluster, trace[r].id, colCL);
        rowCS[trace[r].fromCluster]++;
        rowCL[trace[r].id] = trace[r].fromCluster;
      }
    else
      if (trace[r].toCluster != trace[r].fromCluster) {
//        myCRS->subtractRow(Acompressed, trace[r].toCluster, trace[r].id, colCL);
        rowCS[trace[r].toCluster]--;
//        myCRS->addRow(Acompressed, trace[r].fromCluster, trace[r].id, colCL);
        rowCS[trace[r].fromCluster]++;
        rowCL[trace[r].id] = trace[r].fromCluster;
      }
}


void MssrIcc::recoverColCL(int begin, int end, oneStep trace [])
{
  for(int c = begin; c < end; c++)
    if (trace[c].toCluster != trace[c].fromCluster) {
//      myCCS->subtractCol(Acompressed, trace[c].toCluster, trace[c].id, rowCL);
      colCS[trace[c].toCluster]--;
//      myCCS->addCol(Acompressed, trace[c].fromCluster, trace[c].id, rowCL);
      colCS[trace[c].fromCluster]++;
      colCL[trace[c].id] = trace[c].fromCluster;
    }
}


void MssrIcc::recoverColCL(int begin, int end, oneStep trace [], bool *isReversed)
{
  for(int c = begin; c < end; c++)
    if (trace[c].toCluster != trace[c].fromCluster) {
//      myCCS->subtractCol(Acompressed, trace[c].toCluster, trace[c].id, rowCL, isReversed);
      colCS[trace[c].toCluster]--;
//      myCCS->addCol(Acompressed, trace[c].fromCluster, trace[c].id, rowCL, isReversed);
      colCS[trace[c].fromCluster]++;
      colCL[trace[c].id] = trace[c].fromCluster;
    }
}


void MssrIcc::doRowLocalSearch(oneStep trace [], int step)
{
  int fromRow = 0, tempCluster, toCluster, tempRowCL;
  double delta1, delta2, minDelta = MY_DBL_MAX, minDelta2 = MY_DBL_MAX;
  double *compressedRow = new double [numColCluster];
  trace[step].id = 0;
  trace[step].fromCluster = rowCL[0];
  trace[step].toCluster = toCluster = rowCL[0];
  trace[step].change = 0;
/*
computeAcompressed();
isNormalizedCompressed = false;
computeRowQuality4Compressed2WayUnnormalized();
*/
  for (int r = 0; r < numRow; r++){
    tempRowCL = rowCL[r];
    if (rowCS[tempRowCL] > 1 && !isRowMarked[r]){
      tempCluster = tempRowCL;
      minDelta2 = MY_DBL_MAX;
      for (int cc = 0; cc < numColCluster; cc++)
        compressedRow[cc] = Acompressed[tempRowCL][cc];
      myCRS->subtractRow(compressedRow, r, colCL);
      delta1 = rowQuality4Compressed[tempRowCL] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[tempRowCL]-1);
      for (int rc = 0; rc < tempRowCL; rc++){
	for(int cc = 0; cc < numColCluster; cc++)
	  compressedRow[cc] = Acompressed[rc][cc];
	myCRS->addRow(compressedRow, r, colCL);
	delta2 = rowQuality4Compressed[rc] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1);
	updateVariable(minDelta2, tempCluster, delta2, rc);
      }
      for (int rc = tempRowCL+1; rc < numRowCluster; rc++){
	for(int cc = 0; cc < numColCluster; cc++)
	  compressedRow[cc] = Acompressed[rc][cc];
	myCRS->addRow(compressedRow, r, colCL);
	delta2 = rowQuality4Compressed[rc] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1);
        updateVariable(minDelta2, tempCluster, delta2, rc);
      }
      if ((delta1 + minDelta2) < minDelta){
	fromRow = r;
	toCluster = tempCluster;
        minDelta = delta1 + minDelta2;
      }
      checkDumpLevel4DeltaTrace("row", r, tempCluster, delta1, minDelta2);
    }
  }
  isRowMarked[fromRow] = true;
  trace[step].id = fromRow;
  trace[step].fromCluster = rowCL[fromRow];
  trace[step].toCluster = toCluster;
  trace[step].change = minDelta;
  rowCS[rowCL[fromRow]]--;
  rowCS[toCluster]++;

  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::doRowLocalSearch(oneStep trace [], int step, bool *isReversed)
{
  bool tempIsReversed = false;
  int fromRow = 0, tempCluster, toCluster, tempRowCL;
  double delta1, delta2, minDelta = MY_DBL_MAX, minDelta2 = MY_DBL_MAX;
  double *compressedRow = new double [numColCluster];
  trace[step].id = 0;
  trace[step].fromCluster = rowCL[0];
  trace[step].toCluster = toCluster = rowCL[0];
  trace[step].change = 0;
/*
computeAcompressed(isReversed);
isNormalizedCompressed = false;
computeRowQuality4Compressed2WayUnnormalized();
*/
  for (int r = 0; r < numRow; r++){
    tempRowCL = rowCL[r];
    if (rowCS[tempRowCL] > 1 && !isRowMarked[r]){
      tempCluster = tempRowCL;
      minDelta2 = MY_DBL_MAX;

      if (isReversed[r]){

        for (int cc = 0; cc < numColCluster; cc++)
          compressedRow[cc] = Acompressed[tempRowCL][cc];
        myCRS->addRow(compressedRow, r, colCL);
        delta1 = rowQuality4Compressed[tempRowCL] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[tempRowCL]-1);
        for (int rc = 0; rc < tempRowCL; rc++){
	  for(int cc = 0; cc < numColCluster; cc++)
	    compressedRow[cc] = Acompressed[rc][cc];
	  myCRS->subtractRow(compressedRow, r, colCL);
	  delta2 = rowQuality4Compressed[rc] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1);
          updateVariable(minDelta2, tempCluster, delta2, rc);
        }
        for (int rc = tempRowCL+1; rc < numRowCluster; rc++){
	  for(int cc = 0; cc < numColCluster; cc++)
	    compressedRow[cc] = Acompressed[rc][cc];
	  myCRS->subtractRow(compressedRow, r, colCL);
	  delta2 = rowQuality4Compressed[rc] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1);
          updateVariable(minDelta2, tempCluster, delta2, rc);
        }
        if ((delta1 + minDelta2) < minDelta){
	  fromRow = r;
	  toCluster = tempCluster;
          minDelta = delta1 + minDelta2;
          tempIsReversed = true;
        }
 
      } else {				// (i.e., isReversed[r] == false)

        for (int cc = 0; cc < numColCluster; cc++)
          compressedRow[cc] = Acompressed[tempRowCL][cc];
        myCRS->subtractRow(compressedRow, r, colCL);
        delta1 = rowQuality4Compressed[tempRowCL] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[tempRowCL]-1);
        for (int rc = 0; rc < tempRowCL; rc++){
	  for(int cc = 0; cc < numColCluster; cc++)
	    compressedRow[cc] = Acompressed[rc][cc];
	  myCRS->addRow(compressedRow, r, colCL);
	  delta2 = rowQuality4Compressed[rc] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1);
          updateVariable(minDelta2, tempCluster, delta2, rc);
        }
        for (int rc = tempRowCL+1; rc < numRowCluster; rc++){
	  for(int cc = 0; cc < numColCluster; cc++)
	    compressedRow[cc] = Acompressed[rc][cc];
	  myCRS->addRow(compressedRow, r, colCL);
	  delta2 = rowQuality4Compressed[rc] - computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1);
          updateVariable(minDelta2, tempCluster, delta2, rc);
        }
        if ((delta1 + minDelta2) < minDelta){
	  fromRow = r;
	  toCluster = tempCluster;
          minDelta = delta1 + minDelta2;
          tempIsReversed = false;
        }
      }
      checkDumpLevel4DeltaTrace("row", r, tempCluster, delta1, minDelta2);
    }
  }
  isRowMarked[fromRow] = true;
  trace[step].id = fromRow;
  trace[step].fromCluster = rowCL[fromRow];
  trace[step].toCluster = toCluster;
  trace[step].change = minDelta;