itcc.cc

一种聚类算法,名字是cocluster

  return ccq / log(2.0);
}


void Itcc::rowClusterQuality(double *result)
{
  for(int rc = 0; rc < numRowCluster; rc++)
    result[rc] = 0;
  for(int rc = 0; rc < numRowCluster; rc++)
    for(int cc = 0; cc < numColCluster; cc++)
      if (Acompressed[rc][cc] > 0)
	result[rc] += Acompressed[rc][cc] * log(Acompressed[rc][cc] / (pxhat[rc] * pyhat[cc])) / log(2.0);
}


void Itcc::colClusterQuality(double *result)
{
  for(int cc = 0; cc < numColCluster; cc++)
    result[cc] = 0;
  for(int cc = 0; cc < numColCluster; cc++)
    for(int rc = 0; rc < numRowCluster; rc++)
      if (Acompressed[rc][cc] > 0)
	result[cc] += Acompressed[rc][cc] * log(Acompressed[rc][cc] / (pxhat[rc] * pyhat[cc])) / log(2.0);
}


void Itcc::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);
      pxhat[trace[r].toCluster] -= pX[trace[r].id];
      myCRS->addRow(Acompressed, trace[r].fromCluster, trace[r].id, colCL);
      pxhat[trace[r].fromCluster] += pX[trace[r].id];
      rowCL[trace[r].id] = trace[r].fromCluster;
    }
}


void Itcc::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);
      pyhat[trace[c].toCluster] -= pY[trace[c].id];
      myCCS->addCol(Acompressed, trace[c].fromCluster, trace[c].id, rowCL);
      pyhat[trace[c].fromCluster] += pY[trace[c].id];
      colCL[trace[c].id] = trace[c].fromCluster;
    }
}


void Itcc::doRowLocalSearch(oneStep trace [], int step)
{
  int fromRow = 0, tempCluster, toCluster, tempRowCL;
  double rowP, delta1, delta2, minDelta = MY_DBL_MAX, minDelta2 = MY_DBL_MAX;
  double *rowClusterQ = new double[numRowCluster], *temppxhat = new double[numColCluster];
  trace[step].id = 0;
  trace[step].fromCluster = rowCL[0];
  trace[step].toCluster = toCluster = rowCL[0];
  trace[step].change = 0;
  rowClusterQuality(rowClusterQ);
  for(int r = 0; r < numRow; r++){
    tempRowCL = rowCL[r];
    tempCluster = tempRowCL;
    minDelta2 = MY_DBL_MAX;
    if (rowCS[tempRowCL] > 1 && !isRowMarked[r]){
      for(int cc = 0; cc < numColCluster; cc++)
        temppxhat[cc] = Acompressed[tempRowCL][cc];
      myCRS->subtractRow(temppxhat, r, colCL);
      rowP = pxhat[tempRowCL] - pX[r];
      delta1 = rowClusterQ[tempRowCL] - rowClusterQuality(temppxhat, rowP, pyhat);
      for (int rc = 0; rc < tempRowCL; rc++){
	for(int cc = 0; cc < numColCluster; cc++)
	  temppxhat[cc] = Acompressed[rc][cc];
	myCRS->addRow(temppxhat, r, colCL);
        rowP = pxhat[rc] + pX[r];
        delta2 = rowClusterQ[rc] - rowClusterQuality(temppxhat, rowP, pyhat);
        updateVariable(minDelta2, tempCluster, delta2, rc);
      }
      for (int rc = tempRowCL+1; rc < numRowCluster; rc++){
	for(int cc = 0; cc < numColCluster; cc++)
	  temppxhat[cc] = Acompressed[rc][cc];
	myCRS->addRow(temppxhat, r, colCL);
        rowP = pxhat[rc] + pX[r];
        delta2 = rowClusterQ[rc] - rowClusterQuality(temppxhat, rowP, pyhat);
        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);
  pxhat[rowCL[fromRow]] -= pX[fromRow];
  myCRS->addRow(Acompressed, toCluster, fromRow, colCL);
  pxhat[toCluster] += pX[fromRow];

  rowCL[fromRow] = toCluster;
  delete [] rowClusterQ;
  delete [] temppxhat;
  checkDumpLevel4Cocluster(dumpFile);
}


void Itcc::doColLocalSearch(oneStep trace [], int step)
{
  int fromCol = 0, tempCluster, toCluster, tempColCL;
  double colP, delta1, delta2, minDelta = MY_DBL_MAX, minDelta2 = MY_DBL_MAX;
  double *colClusterQ = new double[numColCluster], *temppyhat = new double[numRowCluster];
  trace[step].id = 0;
  trace[step].fromCluster = colCL[0];
  trace[step].toCluster = toCluster = colCL[0];
  trace[step].change = 0;
  colClusterQuality(colClusterQ);
  for (int c = 0; c < numCol; c++){
    tempColCL = colCL[c];
    tempCluster = tempColCL;
    minDelta2 = MY_DBL_MAX;
    if (colCS[tempColCL] > 1  && !isColMarked[c]){
      for (int rc = 0; rc < numRowCluster; rc++)
        temppyhat[rc] = Acompressed[rc][tempColCL];
      myCCS->subtractCol(temppyhat, c, rowCL);
      colP = pyhat[tempColCL] - pY[c];
      delta1 = colClusterQ[tempColCL] - colClusterQuality(temppyhat, colP, pxhat);
      for (int cc = 0; cc < tempColCL; cc++){
        for (int rc = 0; rc < numRowCluster; rc++)
	  temppyhat[rc] = Acompressed[rc][cc];
	myCCS->addCol(temppyhat, c, rowCL);
	colP = pyhat[cc] + pY[c];
        delta2 = colClusterQ[cc] - colClusterQuality(temppyhat, colP, pxhat);
        updateVariable(minDelta2, tempCluster, delta2, cc);
      }
      for (int cc = tempColCL+1; cc < numColCluster; cc++){
        for (int rc = 0; rc < numRowCluster; rc++)
	  temppyhat[rc] = Acompressed[rc][cc];
	myCCS->addCol(temppyhat, c, rowCL);
	colP = pyhat[cc] + pY[c];
        delta2 = colClusterQ[cc] - colClusterQuality(temppyhat, colP, pxhat);
        updateVariable(minDelta2, tempCluster, delta2, cc);
      }
      if ((delta1 + minDelta2) < minDelta){
        minDelta = delta1 + minDelta2;
	toCluster = tempCluster;
	fromCol = c;
      }  
      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);
  pyhat[colCL[fromCol]] -= pY[fromCol];
  myCCS->addCol(Acompressed, toCluster, fromCol, rowCL);
  pyhat[toCluster] += pY[fromCol];

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


bool Itcc::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++){
    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 * mutualInfo){
    checkDumpLevel4NumOfChain("row", 0, NULL);
    recoverRowCL(0, rowLocalSearchLength, trace);
    isHelpful = false;
  } else {
    checkDumpLevel4NumOfChain("row", minIndex, totalChange);
    recoverRowCL(minIndex+1, rowLocalSearchLength, trace);
    isHelpful = true;
  }
  delete [] totalChange;
  delete [] trace;
  checkDumpLevel4Cocluster(dumpFile);
  checkDumpLevel4LocalSearch("endRow");
  return isHelpful;
}
     

bool Itcc::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++){
    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 * mutualInfo){
    checkDumpLevel4NumOfChain("col", 0, NULL);
    recoverColCL(0, colLocalSearchLength, trace);
    isHelpful = false;
  } else {
    checkDumpLevel4NumOfChain("col", minIndex, totalChange);
    recoverColCL(minIndex+1, colLocalSearchLength, trace);
    isHelpful = true;
  }
  delete [] totalChange;
  delete [] trace;
  checkDumpLevel4Cocluster(dumpFile);
  checkDumpLevel4LocalSearch("endCol");
  return isHelpful;
}


void Itcc::doPingPong()
{
  bool isRowLocalSearchHelpful = false, isColLocalSearchHelpful = false;
  numIteration = 0;
  do {
    isRowLocalSearchHelpful = false;
    isColLocalSearchHelpful = false;
    numIteration++;
    
    checkDumpLevel4PingPong("begin", numIteration);
    
    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;
    }

    computeRowClusterSize();
    computeColClusterSize();
    
    //-----------------------------------------
    // 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();
      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();
      isColLocalSearchHelpful = doColLocalSearchChain();
    }
    checkDumpLevel4PingPong("end", numIteration);

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

  if (isComputingOneWayObjective){
    computeRowCentroid4RowCluster();
//    normalizeRowCentroid();
    computeObjectiveFunction4RowCluster();
    computeColCentroid4ColCluster();
//    normalizeColCentroid();  
    computeObjectiveFunction4ColCluster();
  }
  checkDumpLevel4FinalObjectValue();
  switch (dumpLevel){
    case MINIMUM_DUMP_LEVEL:
      break;
    case BATCH_UPDATE_DUMP_LEVEL:
    case LOCAL_SEARCH_DUMP_LEVEL:
      checkDumpLevel4Coclustering(cout, numIteration, mutualInfo);
    case MAXIMUM_DUMP_LEVEL:
      checkDumpLevel4Coclustering(dumpFile, numIteration, mutualInfo);
  }
  if (statisticsAccessMode != NO_OPEN_MODE)
    checkDumpLevel4Coclustering(statisticsFile, numIteration, mutualInfo);
//  cout << endl << "Itcc::~Itcc()" << endl;
}