mssriicc.cc

一种聚类算法,名字是cocluster

  computeAcompressed(isReversed);
  isNormalizedCompressed = false;
  normalizeCompressedMatrix();
  computeRowCentroid(isReversed);
  normalizeRowCentroid();
  computeColCentroid(isReversed);
  normalizeColCentroid();
 
  myCRS->setSmoothingFactor(smoothingType, tempRowSmoothingFactor);
  myCCS->setSmoothingFactor(smoothingType, tempColSmoothingFactor);
  do{
    numIteration++;
    for (int r = 0; r < numRow; r++){
      beforeIsReversed[r] = isReversed[r];
      beforeRowCL[r] = rowCL[r];
    }
    do {
      numRowIteration++;
      myCRS->setSmoothingFactor(smoothingType, tempRowSmoothingFactor);
      oldObjValue = objValue;
      reassignRC(isReversed);
      computeRowClusterSize();
      computeAcompressed(isReversed);
      isNormalizedCompressed = false;
      normalizeCompressedMatrix();
      computeRowCentroid(isReversed);
      normalizeRowCentroid();
      computeColCentroid(isReversed);
      normalizeColCentroid();
      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();
//    computeRowCentroid(isReversed);
//    normalizeRowCentroid();
//    computeColCentroid(isReversed);
//    normalizeColCentroid();
//    for (int r = 0; r < numRow; r++){
//      isReversed[r] = afterIsReversed[r];
//      rowCL[r] = afterRowCL[r];
//    }
//    computeRowClusterSize();

    numColIteration = 0;
    tempRowSmoothingFactor = rowSmoothingFactor;
    myCRS->setSmoothingFactor(smoothingType, tempRowSmoothingFactor);
//-----------
    do {
      numColIteration++;
      myCCS->setSmoothingFactor(smoothingType, tempColSmoothingFactor);
      oldObjValue = objValue;
      reassignCC(isReversed);
      computeColClusterSize();
      computeAcompressed(isReversed);
      isNormalizedCompressed = false;
      normalizeCompressedMatrix();
      computeColCentroid(isReversed);
      normalizeColCentroid();
      computeObjectiveFunction4Normalized();
      checkDumpLevel4BatchUpdate("col", numColIteration);
      tempColSmoothingFactor *= myCCS->getAnnealingFactor();
    } while ((oldObjValue - objValue) > (colBatchUpdateThreshold * squaredFNormA));
//-----------
    oldObjValue = objValue;
    computeRowClusterSize();
    computeAcompressed(isReversed);
    isNormalizedCompressed = false;
    normalizeCompressedMatrix();
//    computeRowCentroid(isReversed);
//    normalizeRowCentroid();
    computeObjectiveFunction4Normalized();
    checkDumpLevel4BatchUpdate("both", numIteration);
//-----------
  } while ((oldObjValue - objValue) > (rowBatchUpdateThreshold * squaredFNormA));
  colSmoothingFactor = tempColSmoothingFactor;
  delete [] beforeIsReversed;
  delete [] afterIsReversed;
  delete [] beforeRowCL;
  delete [] afterRowCL;
  checkDumpLevel4BatchUpdate("end");
}
*/


void MssrIIcc::doBatchUpdate4VariationIII(bool *isReversed)
{
  checkDumpLevel4BatchUpdate("begin");
  int numIteration = 0;
  double oldObjValue;

  computeRowClusterSize();
  computeColClusterSize();
  computeAcompressed(isReversed);
  isNormalizedCompressed = false;
  normalizeCompressedMatrix();
  computeRowCentroid(isReversed);
  normalizeRowCentroid();
  computeColCentroid(isReversed);
  normalizeColCentroid();

  do {
    numIteration++;

    myCRS->setSmoothingFactor(smoothingType, rowSmoothingFactor);
    myCCS->setSmoothingFactor(smoothingType, colSmoothingFactor);
    oldObjValue = objValue;
    
    if (randNumGenerator.GetUniform() > SELECTION_PROBABILITY){
      reassignRC(isReversed);
      computeRowClusterSize();
      computeAcompressed(isReversed);
      isNormalizedCompressed = false;
      normalizeCompressedMatrix();
      computeRowCentroid(isReversed);
      normalizeRowCentroid();
      computeObjectiveFunction4Normalized();
      checkDumpLevel4BatchUpdate("row", numIteration);
    } else {
      reassignCC(isReversed);
      computeColClusterSize();
      computeAcompressed(isReversed);
      isNormalizedCompressed = false;
      normalizeCompressedMatrix();
      computeColCentroid(isReversed);
      normalizeColCentroid();
      computeObjectiveFunction4Normalized();
      checkDumpLevel4BatchUpdate("col", numIteration);
    }
    rowSmoothingFactor *= myCRS->getAnnealingFactor();
    colSmoothingFactor *= myCCS->getAnnealingFactor();

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

  checkDumpLevel4BatchUpdate("end");
}


void MssrIIcc::doBatchUpdate4VariationIV(bool *isReversed)
{
  checkDumpLevel4BatchUpdate("begin");
  int numIteration = 0;
  double oldObjValue;

  computeRowClusterSize();
  computeColClusterSize();
  computeAcompressed(isReversed);
  isNormalizedCompressed = false;
  normalizeCompressedMatrix();
  computeRowCentroid(isReversed);
  normalizeRowCentroid();
  computeColCentroid(isReversed);
  normalizeColCentroid();

  do {
    numIteration++;

    myCRS->setSmoothingFactor(smoothingType, rowSmoothingFactor);
    myCCS->setSmoothingFactor(smoothingType, colSmoothingFactor);
    
    if (randNumGenerator.GetUniform() > SELECTION_PROBABILITY){
      do {
        oldObjValue = objValue;
        reassignRC(isReversed);
        computeRowClusterSize();
        computeAcompressed(isReversed);
        isNormalizedCompressed = false;
        normalizeCompressedMatrix();
        computeRowCentroid(isReversed);
        normalizeRowCentroid();
        computeObjectiveFunction4Normalized();
        checkDumpLevel4BatchUpdate("row", numIteration);
      } while ((oldObjValue - objValue) > (MULTIPLE_FACTOR * rowBatchUpdateThreshold * squaredFNormA));
    } else {
      do {
        oldObjValue = objValue;
        reassignCC(isReversed);
        computeColClusterSize();
        computeAcompressed(isReversed);
        isNormalizedCompressed = false;
        normalizeCompressedMatrix();
        computeColCentroid(isReversed);
        normalizeColCentroid();
        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 MssrIIcc::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 MssrIIcc::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 MssrIIcc::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 MssrIIcc::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 MssrIIcc::doRowLocalSearch(oneStep trace [], int step)
{
  int fromRow = 0, tempCluster, toCluster, tempRowCL;
  double delta1, delta2, minDelta = MY_DBL_MAX, minDelta2;
  double *centroidRow = new double [numCol], *compressedRow = new double [numColCluster];
  trace[step].id = 0;
  trace[step].fromCluster = rowCL[0];
  trace[step].toCluster = toCluster = rowCL[0];
  trace[step].change = 0;

  for (int r = 0; r < numRow; r++){
    tempRowCL = rowCL[r];
    if (rowCS[tempRowCL] > 1 && !isRowMarked[r]){
     tempCluster = tempRowCL;
     minDelta2 = MY_DBL_MAX;
     for (int c = 0; c < numCol; c++)
        centroidRow[c] = rowCentroid[tempRowCL][c];
      myCRS->subtractRow(centroidRow, r);
      for (int cc = 0; cc < numColCluster; cc++)
        compressedRow[cc] = Acompressed[tempRowCL][cc];
      myCRS->subtractRow(compressedRow, r, colCL);
      delta1 = rowQuality4Centroid[tempRowCL] - computeRowQuality4CentroidUnnormalized(centroidRow, rowCS[tempRowCL]-1);
      delta1 += computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[tempRowCL]-1) - rowQuality4Compressed[tempRowCL]; 
      for (int rc = 0; rc < tempRowCL; rc++){
        for (int c = 0; c < numCol; c++)
          centroidRow[c] = rowCentroid[rc][c];
        myCRS->addRow(centroidRow, r);
        for(int cc = 0; cc < numColCluster; cc++)
          compressedRow[cc] = Acompressed[rc][cc];
        myCRS->addRow(compressedRow, r, colCL);
        delta2 = rowQuality4Centroid[rc] - computeRowQuality4CentroidUnnormalized(centroidRow, rowCS[rc]+1);
        delta2 += computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1) - rowQuality4Compressed[rc];
        updateVariable(minDelta2, tempCluster, delta2, rc);
      }
      for (int rc = tempRowCL+1; rc < numRowCluster; rc++){
        for (int c = 0; c < numCol; c++)
          centroidRow[c] = rowCentroid[rc][c];
        myCRS->addRow(centroidRow, r);
        for(int cc = 0; cc < numColCluster; cc++)
          compressedRow[cc] = Acompressed[rc][cc];
        myCRS->addRow(compressedRow, r, colCL);
        delta2 = rowQuality4Centroid[rc] - computeRowQuality4CentroidUnnormalized(centroidRow, rowCS[rc]+1);
        delta2 += computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1) - rowQuality4Compressed[rc];
        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);
  myCRS->subtractRow(rowCentroid[rowCL[fromRow]], fromRow); 
  rowQuality4Centroid[rowCL[fromRow]] = computeRowQuality4CentroidUnnormalized(rowCL[fromRow]);
  myCRS->addRow(rowCentroid[toCluster], fromRow); 
  rowQuality4Centroid[toCluster] = computeRowQuality4CentroidUnnormalized(toCluster);

  rowCL[fromRow] = toCluster;
  delete [] centroidRow;
  delete [] compressedRow;
  checkDumpLevel4Cocluster(dumpFile);
}


void MssrIIcc::doRowLocalSearch(oneStep trace [], int step, bool *isReversed)
{
  bool tempIsReversed = false;
  int fromRow = 0, tempCluster, toCluster, tempRowCL;
  double delta1, delta2, minDelta = MY_DBL_MAX, minDelta2;
  double *centroidRow = new double [numCol], *compressedRow = new double [numColCluster];
  trace[step].id = 0;
  trace[step].fromCluster = rowCL[0];
  trace[step].toCluster = toCluster = rowCL[0];
  trace[step].change = 0;

  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 c = 0; c < numCol; c++)
          centroidRow[c] = rowCentroid[tempRowCL][c];
        myCRS->addRow(centroidRow, r);
        for (int cc = 0; cc < numColCluster; cc++)
          compressedRow[cc] = Acompressed[tempRowCL][cc];
        myCRS->addRow(compressedRow, r, colCL);
        delta1 = rowQuality4Centroid[tempRowCL] - computeRowQuality4CentroidUnnormalized(centroidRow, rowCS[tempRowCL]-1);
        delta1 += computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[tempRowCL]-1) - rowQuality4Compressed[tempRowCL]; 
        for (int rc = 0; rc < tempRowCL; rc++){
          for (int c = 0; c < numCol; c++)
            centroidRow[c] = rowCentroid[rc][c];
          myCRS->subtractRow(centroidRow, r);
          for(int cc = 0; cc < numColCluster; cc++)
            compressedRow[cc] = Acompressed[rc][cc];
          myCRS->subtractRow(compressedRow, r, colCL);
          delta2 = rowQuality4Centroid[rc] - computeRowQuality4CentroidUnnormalized(centroidRow, rowCS[rc]+1);
          delta2 += computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1) - rowQuality4Compressed[rc];
          updateVariable(minDelta2, tempCluster, delta2, rc);
        }
        for (int rc = tempRowCL+1; rc < numRowCluster; rc++){
          for (int c = 0; c < numCol; c++)
            centroidRow[c] = rowCentroid[rc][c];
          myCRS->subtractRow(centroidRow, r);
          for(int cc = 0; cc < numColCluster; cc++)
            compressedRow[cc] = Acompressed[rc][cc];
          myCRS->subtractRow(compressedRow, r, colCL);
          delta2 = rowQuality4Centroid[rc] - computeRowQuality4CentroidUnnormalized(centroidRow, rowCS[rc]+1);
          delta2 += computeRowQuality4Compressed2WayUnnormalized(compressedRow, rowCS[rc]+1) - rowQuality4Compressed[rc];
          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 c = 0; c < numCol; c++)
          centroidRow[c] = rowCentroid[tempRowCL][c];
        myCRS->subtractRow(centroidRow, r);
        for (int cc = 0; cc < numColCluster; cc++)
          compressedRow[cc] = Acompressed[tempRowCL][cc];
        myCRS->subtractRow(compressedRow, r, colCL);
        delta1 = rowQuality4Centroid[tempRowCL] - computeRowQuality4CentroidUnnormalized(c