cluster.cc

模糊聚类的算法实现程序

};

void 
Clustering::Berechne_fuer_neue_Daten (DVektorArray & Diese_Daten)
{
  DVektorArray Proj_Daten, Proj_Cluster;

  if ((Diese_Daten.Lese_Dim () != Die_waren_relevant.Lese_Dim ()) &&
      (Cluster.Lese_Groesse () != 0)) {
    Fehlermeldung ("Clustering::Berechne_fuer_neue_Daten(...)", DIMFEHLER);
  } else {
    if (Cluster.Lese_Groesse () != 0) {		/* gibt es was zu tun ? */
      Zugehoerigkeit.Setze_Dim (Cluster.Lese_Groesse (), Diese_Daten.Lese_Groesse ());
      Proj_Daten = Diese_Daten.Projiziere (Die_waren_relevant);
      Proj_Cluster = Cluster.Projiziere (Die_waren_relevant);

      if (Possibilistisch && ClusterFertig && Possib_Zaehler)
	Berechne_possib_U (Proj_Daten, Proj_Cluster, Zugehoerigkeit);
      else
	Berechne_U (Proj_Daten, Proj_Cluster, Zugehoerigkeit);

      if ((Art == OPTIMAL) && (Cluster.Lese_Groesse () > 2) && (!ClusterFertig)) {	/* Das vorherige Ergebnis */
	Tausche_Buffer ();
	Zugehoerigkeit.Setze_Dim (Cluster.Lese_Groesse (), Diese_Daten.Lese_Groesse ());
	Proj_Cluster = Cluster.Projiziere (Die_waren_relevant);

	Berechne_U (Proj_Daten, Proj_Cluster, Zugehoerigkeit);
	Tausche_Buffer ();
      }
//      Cluster=Cluster.Deprojiziere(Die_waren_relevant);/* gibt es schon */
      Berechne_Zuordnung ();
      Berechne_Form (Diese_Daten, Cluster);
    }
  }
};

void 
Clustering::Speichern (char *Name)
{
  FILE *File;

  if ((File = fopen (Name, "w")) == NULL) {
    Fehlermeldung ("Clustering::_File_speichern", DATEIOEFFNENFEHLER);
  } else {
    switch (Lese_Typ ()) {
/** Typ speichern **/
    case FCM:
      fprintf (File, "FCM\n");
      break;
    case GK:
      fprintf (File, "GK\n");
      break;
    case GK_parallel:
      fprintf (File, "GK_parallel\n");
      break;
    case GG:
      fprintf (File, "GG\n");
      break;
    case GG_parallel:
      fprintf (File, "GG_parallel\n");
      break;
    }

    switch (Art) {
/** Art speichern **/
    case KEINE:
      fprintf (File, "KEINE\n");
      break;
    case OPTIMAL:
      fprintf (File, "OPTIMAL\n");
      break;
    case ANZAHL:
      fprintf (File, "ANZAHL\n");
      break;
    case KLASSEN:
      fprintf (File, "KLASSEN\n");
      break;
    }

    switch (Guete_Verfahren->Lese_Typ ()) {
/** Typ speichern **/
    case S:
      fprintf (File, "S\n");
      break;
    case PK:
      fprintf (File, "PK\n");
      break;
    case CS:
      fprintf (File, "CS\n");
      break;
    case D1:
      fprintf (File, "D1\n");
      break;
    case FHV:
      fprintf (File, "FHV\n");
      break;
    case DPA:
      fprintf (File, "DPA\n");
      break;
    case PD:
      fprintf (File, "PD\n");
      break;
    default:
      break;
    }

    fprintf (File, "%d %d %d %d %lf\n", Iterationen,
	     Max_Iterationen, M, K, Delta_U);
    if (Fertig)
      fprintf (File, "1 ");
    else
      fprintf (File, "0 ");
    if (ClusterFertig)
      fprintf (File, "1 ");
    else
      fprintf (File, "0 ");
    if (Possibilistisch) {
      fprintf (File, "1 ");
      fprintf (File, "%d ", Possib_Zaehler);
      if (ClusterFertig && Possibilistisch && Possib_Zaehler) {
	eta.Speichern (File);
      }
    } else
      fprintf (File, "0 ");

    Guete_Verfahren->Speichern (File);
    Vorgabe_Cluster.Speichern (File);
    Cluster.Speichern (File);
    ClusterBuffer.Speichern (File);
    Die_waren_relevant.Speichern (File);
    Die_sind_relevant.Speichern (File);
    Mein_Speichern (File);
    fclose (File);
  }
};

Clustering *
Clustering_Laden (char *Name)
{
  Clustering *Result = 0;
  FILE *File;
  char Typ_String[20];

  if ((File = fopen (Name, "r")) == NULL) {
    Fehlermeldung ("Clustering_Laden(char* Name)", DATEIOEFFNENFEHLER);
    return (NULL);
  }
  do {
    if (!(fscanf (File, "%20s", Typ_String)))
      break;

    if (!strcmp (Typ_String, "FCM"))
      Result = new FCM_Clustering ();
    else if (!strcmp (Typ_String, "GK"))
      Result = new GK_Clustering ();
    else if (!strcmp (Typ_String, "GK_parallel"))
      Result = new GK_parallel_Clustering ();
    else if (!strcmp (Typ_String, "GG"))
      Result = new GG_Clustering ();
    else if (!strcmp (Typ_String, "GG_parallel"))
      Result = new GG_parallel_Clustering ();
    else {
      Fehlermeldung ("Clustering_Laden(char* Name)", DATEIFORMATFEHLER);
      return (NULL);		/* Fehler */
    }

    if (!(fscanf (File, "%20s", Typ_String)))
      break;
    if (!strcmp (Typ_String, "KEINE"))
      Result->Art = KEINE;
    else if (!strcmp (Typ_String, "OPTIMAL"))
      Result->Art = OPTIMAL;
    else if (!strcmp (Typ_String, "ANZAHL"))
      Result->Art = ANZAHL;
    else if (!strcmp (Typ_String, "KLASSEN"))
      Result->Art = KLASSEN;
    else
      break;			/* Fehler */

    if (!(fscanf (File, "%20s", Typ_String)))
      break;			/* Fehler */
    delete Result->Guete_Verfahren;
    if (!strcmp (Typ_String, "S"))
      Result->Guete_Verfahren = new S_Guete;
    else if (!strcmp (Typ_String, "PK"))
      Result->Guete_Verfahren = new PK_Guete;
    else if (!strcmp (Typ_String, "CS"))
      Result->Guete_Verfahren = new CS_Guete;
    else if (!strcmp (Typ_String, "D1"))
      Result->Guete_Verfahren = new D1_Guete;
    else if (!strcmp (Typ_String, "FHV"))
      Result->Guete_Verfahren = new FHV_Guete;
    else if (!strcmp (Typ_String, "DPA"))
      Result->Guete_Verfahren = new DPA_Guete;
    else if (!strcmp (Typ_String, "PD"))
      Result->Guete_Verfahren = new PD_Guete;
    else
      break;			/* Fehler */

    if (!(fscanf (File, "%d %d %d %d %lf\n", &(Result->Iterationen),
		  &(Result->Max_Iterationen), &(Result->M),
		  &(Result->K), &(Result->Delta_U))))
      break;
    if (!(fscanf (File, "%c %c %c", &(Typ_String[0]), &(Typ_String[1]),
		  &(Typ_String[2]))))
      break;

    if (Typ_String[0] == '1')
      Result->Fertig = TRUE;
    else
      Result->Fertig = FALSE;
    if (Typ_String[1] == '1')
      Result->ClusterFertig = TRUE;
    else
      Result->ClusterFertig = FALSE;
    if (Typ_String[2] == '1') {
      Result->Possibilistisch = TRUE;
      if (!(fscanf (File, "%d ", &(Result->Possib_Zaehler))))
	break;
      if (Result->ClusterFertig && Result->Possibilistisch && Result->Possib_Zaehler) {
	Result->eta.Laden (File);
      }
    } else
      Result->Possibilistisch = FALSE;

    if ((!Result->Guete_Verfahren->Laden (File)) ||
	(!Result->Vorgabe_Cluster.Laden (File)) ||
	(!Result->Cluster.Laden (File)) ||
	(!Result->ClusterBuffer.Laden (File)))
      break;
    if (Result->Art == OPTIMAL) {
      if (Result->Cluster.Lese_Groesse () == Result->ClusterBuffer.Lese_Groesse ())
	Result->zu_berechnen = Result->Cluster.Lese_Groesse () + 1;
      else
	Result->zu_berechnen = Result->Cluster.Lese_Groesse ();
    }
    if ((!Result->Die_waren_relevant.Laden (File)) ||
	(!Result->Die_sind_relevant.Laden (File)) ||
	(!Result->Mein_Laden (File)))
      break;
    fclose (File);
    return (Result);
  } while (TRUE);

  Fehlermeldung ("Clustering_Laden(char* Name)", DATEIFORMATFEHLER);
  delete Result;
  fclose (File);
  return (NULL);
};

void 
Clustering::Berechne_Zuordnung ()
{
  int DatenNr, ClusterNr;

  Zuordnung.Setze_Dim (Zugehoerigkeit.Lese_Dim_n ());
  if (Zugehoerigkeit.Lese_Dim_n () != 0) {
    for (DatenNr = 0; DatenNr < Zugehoerigkeit.Lese_Dim_n (); DatenNr++) {	/* alle Daten zuordnen */
      Zuordnung[DatenNr] = 0;	/* default */
      for (ClusterNr = 1; ClusterNr < Zugehoerigkeit.Lese_Dim_m (); ClusterNr++) {
	if (Zugehoerigkeit[ClusterNr][DatenNr] >
	    Zugehoerigkeit[Zuordnung[DatenNr]][DatenNr])
	  Zuordnung[DatenNr] = ClusterNr;
      }
    }
  }
};

DVektorArray 
Clustering::Berechne_v (DMatrix & MatrixU,
			DVektorArray & DieDaten)
return Result (DieDaten.Lese_Dim (), MatrixU.Lese_Dim_m (), NULL);
{
  int i, j, k;
  double SummeA, SummeB;

  for (i = 0; i < MatrixU.Lese_Dim_m (); i++) {		/* alle Cluster */
    SummeB = 0;
    for (k = 0; k < DieDaten.Lese_Groesse (); k++) {
      /*    E U_ik berechnen   */
      SummeB += pow (MatrixU.Lese_i_j (i, k), M);
    }
    for (j = 0; j < DieDaten.Lese_Dim (); j++) {	/* alle Dimensionen */
      SummeA = 0;
      for (k = 0; k < DieDaten.Lese_Groesse (); k++)
	SummeA += pow (MatrixU.Lese_i_j (i, k), M) 
	          * (DieDaten.Lese_Vektor (k, j));
      Result.Setze_Vektor (i, j, SummeA / SummeB);
    }	/* for ( j = ... */
  }   /* for (i = ... */
}

void 
Clustering::Berechne_U (DVektorArray & Daten,
			DVektorArray & Cluster, DMatrix & U)
{
  double Summe;
  int i, j, k, Dim;
  DVektor Dist (Cluster.Lese_Groesse (), 0, NULL);

/**********************************************/
  /* U fuer vorgegebene Prototypen berechnen    */
/**********************************************/
  for (k = 0; (Lese_Fehlerstatus () == KEINFEHLER) &&
       (k < Daten.Lese_Groesse ()); k++) {
    /* d_ik's  fuer ein k bestimmen */
    Dim = Berechne_Dist (Dist, Daten[k], Cluster);
    if (Dim > 0) {
      /* Falls I_k != \emptyset */
      for (i = 0; i < Cluster.Lese_Groesse (); i++)
	if (Dist[i] == 0)
	  U.Setze_i_j (i, k, 1.0 / ((double) Dim));
	else
	  U.Setze_i_j (i, k, 0);
    }
    /* if(Nulltest) */ 
    else {
      /* Falls I_k == \emptyset */
      for (i = 0; i < Cluster.Lese_Groesse (); i++) {
	if (Dist[i] == MAXDOUBLE)
	  U.Setze_i_j (i, k, 0);
	else {
	  Summe = 0;
	  for (j = 0; j < Cluster.Lese_Groesse (); j++)
	    Summe += pow (Dist[i] / Dist[j], 1.0 / (M - 1.0));
	  U.Setze_i_j (i, k, 1.0 / Summe);
	}
      }
    }				/* else */
  }				/* for(k=0 ; k < Daten.Lese_Groesse() ; k++) */
};

DVektor 
Clustering::Berechne_eta (DVektorArray & Daten,
			  DVektorArray & Cluster, DMatrix & U)
return Result (Cluster.Lese_Groesse (), 0, NULL);
{
  int i, k;
  double Potenz, Ni, Buffer;

  for (i = 0; i < Cluster.Lese_Groesse (); i++) {
    Buffer = 0;
    Ni = 0;
    for (k = 0; k < Daten.Lese_Groesse (); k++) {
      Potenz = pow (U[i][k], M);
      Buffer += Potenz * Die_Norm.d_quadr (Daten[k], Cluster[i]);
      Ni += Potenz;
    }
    Result[i] = (K / Ni) * Buffer;
  }
}

void 
Clustering::Speichere_Buffer ()
{
  ClusterBuffer = Cluster;
  UBuffer = Zugehoerigkeit;
};

void 
Clustering::Uebernehme_Buffer ()
{
  Zugehoerigkeit = UBuffer;
  Cluster = ClusterBuffer;
};

void 
Clustering::Tausche_Buffer ()
{
  Zugehoerigkeit.Tausche (UBuffer);
  Cluster.Tausche (ClusterBuffer);
};

void 
Clustering::Loesche_Buffer ()
{
  ClusterBuffer. ~ DVektorArray ();
  UBuffer. ~ DMatrix ();
};

void 
Errechne_Covarianz (DVektorArray & Daten, DMatrix & U,
		    DMatrixArray & CMatrix,
		    DVektorArray & Cluster, double M)
{
  DVektor DVektorBuffer;
  int i, k;
  double Summe, Buffer;

  for (i = 0; i < U.Lese_Dim_m (); i++) {	/* fuer alle Cluster */
    CMatrix[i].NullMatrix ();
    Summe = 0.0;
    for (k = 0; k < U.Lese_Dim_n (); k++) {
      DVektorBuffer = Daten[k] - Cluster[i];
      Buffer = pow (U.Lese_i_j (i, k), M);
      DVektorBuffer *= sqrt (Buffer);
      CMatrix[i] += DVektorBuffer.Produkt ();
      Summe += Buffer;
    }
    // verhindere entartete Cluster
    double minwert=MINFLOAT;
    while (fabs(CMatrix[i].Determinante())<=0.001) {
       int lauf;
       double spur,wert;
       spur=0.0;
       for(lauf=0; lauf<CMatrix[i].Lese_Dim_n (); lauf++)
	  spur+=CMatrix[i].Lese_i_j(lauf,lauf);
       spur=spur/CMatrix[i].Lese_Dim_n ()*0.01;
       if (fabs(spur)<(100.0*minwert))
	  spur=100.0*minwert;
       for(lauf=0; lauf<CMatrix[i].Lese_Dim_n (); lauf++) {
	  wert=CMatrix[i].Lese_i_j(lauf,lauf)+spur;
	  CMatrix[i].Setze_i_j(lauf,lauf,wert);
       }
    }
    CMatrix[i] /= Summe;
  }				/* for(i=0 ; i < U.Lese_Dim_m() ; i++) */
};

/**********************************************************/
/**********************************************************/
FCM_Clustering::FCM_Clustering (Guete_Typ Guete, int Soll_Iterationen,
		char Possib)
{
  Possibilistisch = Possib;
  sprintf (Name, "%s", "FCM");
};

Cluster_Typ 
FCM_Clustering::Lese_Typ ()
{
  return (FCM);
};

DMatrixArray 
FCM_Clustering::Lese_Form (IVektor & Dimensionen, DVektorArray & Daten)
return Result (Cluster.Lese_Groesse (), Dimensionen.Lese_Dim (),
	       Dimensionen.Lese_Dim (), NULL);
{
  int i, j;
  char Was_tun = TRUE;

  if (Dimensionen.Lese_Dim () == 2) {
    if (Dimensionen[0] == Dimensionen[1])
      Was_tun = FALSE;
  } else {
    if ((Dimensionen[0] == Dimensionen[1]) ||
	(Dimensionen[1] == Dimensionen[2]) ||
	(Dimensionen[0] == Dimensionen[2]))
      Was_tun = FALSE;
  }

  if (Was_tun) {
    for (i = 0; i < Cluster.Lese_Groesse (); i++) {
      for (j = 0; j < Dimensionen.Lese_Dim (); j++) {
	if (Die_sind_relevant[Dimensionen[j]])
	  Result[i][j][j] = Radien[i];
	else
	  Result[i][j][j] = 0;
      }
    }
  }
};

DVektorArray 
FCM_Clustering::Mein_Clustern (DVektorArray & Daten,
			       DVektorArray & Vorgabe_Protos)
return Result (Daten.Lese_Dim (), Vorgabe_Protos.Lese_Groesse (), NULL);
{
  int l;
  DMatrix U[2];

  if (Zugehoerigkeit.Lese_Dim_m () != Vorgabe_Protos.Lese_Groesse ()) {
    U[0] = DMatrix (Vorgabe_Protos.Lese_Groesse (), Daten.Lese_Groesse (), NULL);
    Berechne_U (Daten, Vorgabe_Protos, U[0]);
  } else
    U[0] = Zugehoerigkeit;

  U[1] = DMatrix (Vorgabe_Protos.Lese_Groesse (), Daten.Lese_Groesse (), NULL);

  /* Schleifen-Anfang */
  l = 0;
  while ((ClusterFertig != TRUE) && (Iterationen < Max_Iterationen)) {
    Iterationen++;
/*************************/
    /* II. v_i's berechnen   */
/*************************/
    Result = Berechne_v (U[l], Daten);
/*************************/
    /* III. U_neu bestimmen  */
/*************************/
    l = (l + 1) % 2;

    Berechne_U (Daten, Result, U[l]);
/*************************/
    /* IV. ||U[l-1]-U[l]||   */
/*************************/
    if (Die_Norm.d (U[0], U[1]) <= Delta_U) {
      ClusterFertig = TRUE;
    }
  };
  Zugehoerigkeit = U[l];
};