/************vv********************************************//*   filename: cluster.cc                               *//*                                                      *//********************************************************//* programmed by: Oliver Wagner                         *//* last change: 26-04-95                                *//********************************************************/#include "cluster.h"#include <limits.h>/****************************************************************//*              Alles zur Klasse Clustering                     *//****************************************************************/Clustering::Clustering (Guete_Typ Guete, int Soll_Iterationen,	    char Possib){  Possibilistisch = Possib;  Guete_Verfahren = NULL;  Setze_Guete (Guete);  Max_Iterationen = Soll_Iterationen;  Iterationen = 0;  Possib_Zaehler = 0;  M = DEFAULT_M;  K = DEFAULT_K;  Delta_U = DEFAULT_DELTA_U;  ClusterFertig = FALSE;  Fertig = FALSE;  Art = KEINE;  zu_berechnen = 0;};Clustering::~Clustering (){  delete Guete_Verfahren;  Guete_Verfahren = NULL;};void Clustering::Setze_Guete (Guete_Typ Damit){  if (Guete_Verfahren != NULL)    delete Guete_Verfahren;  switch (Damit) {  case S:    Guete_Verfahren = new S_Guete;    break;  case CS:    Guete_Verfahren = new CS_Guete;    break;  case PK:    Guete_Verfahren = new PK_Guete;    break;  case D1:    Guete_Verfahren = new D1_Guete;    break;  case FHV:    Guete_Verfahren = new FHV_Guete;    break;  case DPA:    Guete_Verfahren = new DPA_Guete;    break;  case PD:    Guete_Verfahren = new PD_Guete;    break;#if 0  default:    break;#else  default:    Guete_Verfahren = 0;    break;#endif  }};void Clustering::Reset (){  Fertig = FALSE;  ClusterFertig = FALSE;  Cluster. ~ DVektorArray ();  Zugehoerigkeit. ~ DMatrix ();  Iterationen = 0;  Possib_Zaehler = 0;  Art = KEINE;  eta. ~ DVektor ();  Zuordnung. ~ IVektor ();  Klassen. ~ IVektor ();  neuer_Proto. ~ DVektor ();  Loesche_Buffer ();  Reset_Fehlerstatus ();};void Clustering::Clustere (DVektorArray & Das, int Clusteranzahl){  int i;  DVektorArray Uebergabe;  if (((Art != ANZAHL) || (Cluster.Lese_Groesse () != Clusteranzahl)) &&      (ClusterFertig != TRUE)) {    Die_waren_relevant = Die_sind_relevant;    Reset ();    Art = ANZAHL;    Cluster. ~ DVektorArray ();    for (i = 0; (i < Vorgabe_Cluster.Lese_Groesse ()) &&	 (i < Clusteranzahl); i++) {      Vorgabe_Cluster[i].Setze_Nummer (i);      Cluster += Vorgabe_Cluster[i];    }    for (i = Cluster.Lese_Groesse (); i < Clusteranzahl; i++) {      Cluster += Das.Zufallsvektor ();      Cluster[i].Setze_Nummer (i);    }  }/* Zunaechst das normale Clustern */  if (ClusterFertig != TRUE) {	/* Zunaechst einmal fertig Clustern */    Uebergabe = Das.Projiziere (Die_sind_relevant);    ClusterBuffer = Cluster.Projiziere (Die_sind_relevant);/*********************************/    /* Die Cluster runterprojizieren *//*********************************/    ClusterBuffer = Mein_Clustern (Uebergabe, ClusterBuffer);    if (ClusterBuffer.Lese_Groesse () != 0) {      Cluster = ClusterBuffer.Deprojiziere (Die_sind_relevant);		/* fuer Ausgabe */      if (ClusterFertig) {	if (Cluster.Lese_Groesse () != 0) {	  Guete_Verfahren->Berechne (Uebergabe, Zugehoerigkeit,				     ClusterBuffer, M);	  if (Possibilistisch)	    Possib_Zaehler = 1;	  else	    Fertig = TRUE;	} else	  Fertig = TRUE;	ClusterBuffer. ~ DVektorArray ();      }      Cluster.Aktualisiere_Min_etc ();    } else {      Reset ();      ClusterFertig = Fertig = TRUE;    }  }/* Jetzt vielleicht noch possibilistisches Clustern */  if ((ClusterFertig) && (Possibilistisch) && (Fertig == FALSE) &&      (Cluster.Lese_Groesse () != 0) && (Iterationen < Max_Iterationen)) {    Uebergabe = Das.Projiziere (Die_sind_relevant);    ClusterBuffer = Cluster.Projiziere (Die_sind_relevant);    Mache_Possibilistisch (Uebergabe, ClusterBuffer);    Guete_Verfahren->Berechne (Uebergabe, Zugehoerigkeit, ClusterBuffer, M);    Cluster = ClusterBuffer.Deprojiziere (Die_sind_relevant);    if (Fertig) {      Guete_Verfahren->Berechne (Uebergabe, Zugehoerigkeit,				 ClusterBuffer, M);      ClusterBuffer. ~ DVektorArray ();    }    Cluster.Aktualisiere_Min_etc ();  }  Berechne_Zuordnung ();	/* Auf jeden Fall vor Formberechnung !!!!! */  if (Cluster.Lese_Groesse () != 0) {    Berechne_Form (Das, Cluster);  }  Iterationen = 0;		/* bei erneutem Aufruf wieder alle */};void Clustering::Clustere (DVektorArray & Das){  int i;  DVektorArray Uebergabe;  if ((Art != OPTIMAL) && (ClusterFertig != TRUE)) {	/* Reseten und Anfangscluster auffuellen */    Die_waren_relevant = Die_sind_relevant;    Reset ();    Guete_Verfahren->Reset ();    Art = OPTIMAL;    for (i = 0; (i < Vorgabe_Cluster.Lese_Groesse ()) /* && (i < 2) */ ; i++) {      Vorgabe_Cluster[i].Setze_Nummer (0);      Cluster += Vorgabe_Cluster[i];    }    for (i = Cluster.Lese_Groesse (); i < 2; i++) {	/* mindestens zwei */      Cluster += Das.Zufallsvektor ();      Cluster[i].Setze_Nummer (i);    }    zu_berechnen = 2;  }  if (ClusterFertig != TRUE) {    DVektorArray NiederCluster;    Uebergabe = Das.Projiziere (Die_sind_relevant);/********************/    while ((Cluster.Lese_Groesse () < Das.Lese_Groesse ()) &&	   (Iterationen < Max_Iterationen)) {	/* Hoechsten n-1 Cluster :-) */      if (zu_berechnen > Cluster.Lese_Groesse ()) {	/* neues Cluster notwendig */	Cluster += Das.Zufallsvektor ();	Cluster[Cluster.Lese_Groesse () - 1].Setze_Nummer (Cluster.Lese_Groesse () - 1);      }      Cluster = Cluster.Projiziere (Die_sind_relevant);      NiederCluster = Mein_Clustern (Uebergabe, Cluster);      if (ClusterFertig) {	/* jetzt fertig ? */	if (NiederCluster.Lese_Groesse () != 0) {	  Guete_Verfahren->Berechne (Uebergabe, Zugehoerigkeit,				     NiederCluster, M);	  if (Cluster.Lese_Groesse () == Guete_Verfahren->Lese_Bestes ()) {	/* besser geworden ? */	    Cluster = NiederCluster.Deprojiziere (Die_sind_relevant);	    Speichere_Buffer ();	    zu_berechnen++;	    ClusterFertig = FALSE;	  } else {		/* wieder schlechter */	    Uebernehme_Buffer ();	    Loesche_Buffer ();	    if (Possibilistisch)	      Possib_Zaehler = 1;	    else	      Fertig = TRUE;	    break;	  }	} else {	  if (zu_berechnen > 2) {	/* Dann gibt es schon was */	    Uebernehme_Buffer ();	    Loesche_Buffer ();	    if (Possibilistisch)	      Possib_Zaehler = 1;	    else	      Fertig = TRUE;	  } else {	    Reset ();	    Fertig = TRUE;	  }	  break;	}      } else	/* Cluster zumindest fuer die Ausgabe erzeugen */      {	Cluster = NiederCluster.Deprojiziere (Die_sind_relevant);	break;      }    }    Cluster.Aktualisiere_Min_etc ();  }  /* Jetzt vielleicht noch possibilistisches Clustern */  if ((ClusterFertig) && (Possibilistisch) && (Fertig == FALSE) &&      (Cluster.Lese_Groesse () != 0) && (Iterationen < Max_Iterationen)) {    Uebergabe = Das.Projiziere (Die_sind_relevant);    ClusterBuffer = Cluster.Projiziere (Die_sind_relevant);    Mache_Possibilistisch (Uebergabe, ClusterBuffer);    Guete_Verfahren->Berechne (Uebergabe, Zugehoerigkeit,			       ClusterBuffer, M);    Cluster = ClusterBuffer.Deprojiziere (Die_sind_relevant);    if (Fertig) {      ClusterBuffer. ~ DVektorArray ();    }    Cluster.Aktualisiere_Min_etc ();  }  Berechne_Zuordnung ();	/* Auf jeden Fall vor Formberechnung !!!!! */  if (Cluster.Lese_Groesse () != 0) {    Berechne_Form (Das, Cluster);  }  Iterationen = 0;		/* bei erneutem Aufruf wieder alle */};void Clustering::Clustere_Klassen (DVektorArray & Das, int Fehlerprozent){  int i, j, k, Klasse, Zaehler;  double Abstand, DBuffer;  DVektorArray Uebergabe;  // Zur Sicherheit:   Klasse=0;  if ((Art != KLASSEN) && (ClusterFertig != TRUE)) {    Die_waren_relevant = Die_sind_relevant;/*****************************************/    /* Reseten und Anfangscluster auffuellen *//*****************************************/    Reset ();    Art = KLASSEN;    /* Zunaechst Anzahl der Klassen feststellen */    for (i = 0; i < Das.Lese_Groesse (); i++) {      if (!Klassen.Ist_drinnen (Das[i].Lese_Nummer ())) {	/* neu aufnehmen */	Klassen += (Das[i].Lese_Nummer ());      }    }    BVektor benutzt (Klassen.Lese_Dim ());    /* Zunaechst die Vorgabe-Cluster uebernehmen */    for (i = 0; i < Vorgabe_Cluster.Lese_Groesse (); i++) {      Abstand = MAXDOUBLE;      for (j = 0; j < Das.Lese_Groesse (); j++) {	DBuffer = Vorgabe_Cluster[i].Abstand (Das[j], Die_sind_relevant);	if (DBuffer < Abstand) {	  Abstand = DBuffer;	  Klasse = Das[j].Lese_Nummer ();	}      }      benutzt.Setze_i (Klassen.Lese_Index (Klasse), TRUE);      Cluster += Vorgabe_Cluster[i];    }    /* jetzt noch fuer die Klassen, die nicht bedient sind */    /* einen Prototyp in die Mitte setzen */    i = 0;    neuer_Proto.Setze_Dim (Die_sind_relevant.Lese_Dim ());    while (benutzt.Anzahl_gesetzt () != benutzt.Lese_Dim ()) {      if (!(benutzt[i])) {	neuer_Proto.NullVektor ();	Zaehler = 0;	Klasse = Klassen[i];	for (j = 0; j < Das.Lese_Groesse (); j++) {	  if (Das[j].Lese_Nummer () == Klasse) {	    neuer_Proto += Das[j];	    Zaehler++;	  }	}	neuer_Proto *= 1.0 / ((double) Zaehler);	Cluster += neuer_Proto;	benutzt.Setze_i (i, TRUE);      }      i++;    }    neuer_Proto. ~ DVektor ();    zu_berechnen = Cluster.Lese_Groesse ();  }/********************* Jetzt geht es los ************************/  if (ClusterFertig != TRUE) {    DVektorArray NiederCluster;    /* Zunaechst einmal Clustern */    Uebergabe = Das.Projiziere (Die_sind_relevant);    while ((Cluster.Lese_Groesse () < Das.Lese_Groesse ()) &&	   (Iterationen < Max_Iterationen)) {	/* Hoechsten n-1 Cluster :-) */      Cluster = Cluster.Projiziere (Die_sind_relevant);      if (zu_berechnen > Cluster.Lese_Groesse ()) {	/* neues Cluster notwendig */	Cluster += neuer_Proto;	neuer_Proto. ~ DVektor ();	/* wird nicht mehr gebraucht */      }      NiederCluster = Mein_Clustern (Uebergabe, Cluster);      /* Jetzt testen, ob das funktioniert hat */      if (ClusterFertig) {	/* jetzt fertig ? */	if (NiederCluster.Lese_Dim () == 0) {	/* So gings nicht *//* aber vielleicht gab es schon vorher was */	  Zugehoerigkeit = UBuffer;	  UBuffer. ~ DMatrix ();	  Cluster = ClusterBuffer;	  ClusterBuffer. ~ DVektorArray ();	  Berechne_Zuordnung ();	  break;	  if (Possibilistisch == FALSE) {	    Fertig = TRUE;	  }	} else {	  /* Testen, ob noch weitere Prototypen notwendig sind: */	  int Falsche = 0;	  /* zunaechst jedem Cluster die Klasse zuordnen */	  for (i = 0; i < NiederCluster.Lese_Groesse (); i++) {	    DBuffer = 0;	    for (j = 0; j < Das.Lese_Groesse (); j++) {	      if (Zugehoerigkeit[i][j] > DBuffer) {		DBuffer = Zugehoerigkeit[i][j];		NiederCluster[i].Setze_Nummer (Das[j].Lese_Nummer ());	      }	    }	  }	  Berechne_Zuordnung ();	/* Jedes Datum einem Cluster zuordnen */	  /* testen, wieviele falsch sind */	  for (i = 0; i < Das.Lese_Groesse (); i++) {	    if (Das[i].Lese_Nummer () != NiederCluster[Zuordnung[i]].Lese_Nummer ())	      Falsche++;	  }	  if ((100.0 * Falsche) / ((double) Das.Lese_Groesse ()) >= Fehlerprozent) {	/* neuer Proto notwendig ? */	    int diese_Klasse, dieses_Cluster, Falsche_akt, Falsche = 0;	    // Zur Sicherheit:	    diese_Klasse=0;	    dieses_Cluster=0;	    /* jetzt testen, welches Cluster die meiszten falschen enthaelt */	    for (i = 0; i < NiederCluster.Lese_Groesse (); i++) {	      for (j = 0; j < Klassen.Lese_Dim (); j++) {		Falsche_akt = 0;		for (k = 0; k < Das.Lese_Groesse (); k++) {		  if ((Das[k].Lese_Nummer () == Klassen[j]) &&		      (Das[k].Lese_Nummer () != NiederCluster[i].Lese_Nummer ()) &&		      (Zuordnung[k] == i))		    Falsche_akt++;		}		if (Falsche_akt > Falsche) {		  diese_Klasse = Klassen[j];		  dieses_Cluster = i;		  Falsche = Falsche_akt;		}	      }	    }	    neuer_Proto.Setze_Dim (Die_sind_relevant.Anzahl_gesetzt ());	    neuer_Proto.NullVektor ();	    j = 0;	    for (i = 0; i < Das.Lese_Groesse (); i++) {	      if ((Das[i].Lese_Nummer () == diese_Klasse) &&		  (Zuordnung[i] == dieses_Cluster)) {		j++;		neuer_Proto += Uebergabe[i];	      }	    }	    neuer_Proto *= 1.0 / (double) j;	    zu_berechnen++;	    ClusterFertig = FALSE;	  }	  Cluster = NiederCluster.Deprojiziere (Die_sind_relevant);	  if (ClusterFertig) {	/* wirklich immer noch fertig */	    ClusterBuffer. ~ DVektorArray ();#if 0	    UBuffer. ~ Zugehoerigkeit ();#endif	    if (Possibilistisch == FALSE)	      Fertig = TRUE;	    else if (Iterationen < Max_Iterationen)	      Possib_Zaehler = 1;	    break;	  } else {		/* weiter suchen */	    ClusterBuffer = Cluster;	    UBuffer = Zugehoerigkeit;	  }	}      } else	/* Clustern nocht nicht fertig,aber zumindest fuer die Ausgabe erzeugen */      {	Cluster = NiederCluster.Deprojiziere (Die_sind_relevant);	Berechne_Zuordnung ();	break;      }    }    Cluster.Aktualisiere_Min_etc ();  }  /* Jetzt vielleicht noch possibilistisches Clustern */  if ((ClusterFertig) && (Possibilistisch) && (Fertig == FALSE) &&      (Cluster.Lese_Groesse () != 0) && (Iterationen < Max_Iterationen)) {    Uebergabe = Das.Projiziere (Die_sind_relevant);    ClusterBuffer = Cluster.Projiziere (Die_sind_relevant);    Mache_Possibilistisch (Uebergabe, ClusterBuffer);    Guete_Verfahren->Berechne (Uebergabe, Zugehoerigkeit,			       ClusterBuffer, M);    Cluster = ClusterBuffer.Deprojiziere (Die_sind_relevant);    if (Fertig) {      ClusterBuffer. ~ DVektorArray ();    }    Berechne_Zuordnung ();    Cluster.Aktualisiere_Min_etc ();  }  if (Cluster.Lese_Groesse () != 0) {    Berechne_Form (Das, Cluster);  }  Iterationen = 0;		/* bei erneutem Aufruf wieder alle */};DVektor Clustering::Berechne_Zugehoerigkeit (DVektor & Datum)return Result (Cluster.Lese_Groesse (), 0, NULL);{  double Summe, Max = 0;  int i, j, Dim;  DVektor Dist (Cluster.Lese_Groesse (), 0, NULL);  if ((Possibilistisch) && (ClusterFertig) && (eta.Lese_Dim () != 0)) {    Berechne_Dist (Dist, Datum, Cluster);    for (i = 0; i < Cluster.Lese_Groesse (); i++)      Result[i] = 1.0 / (1.0 + pow (Dist[i] / eta[i],				1.0 / (M - 1.0)));  } else {    Dim = Berechne_Dist (Dist, Datum, Cluster);    if (Dim > 0) {      /* Falls I_k != \emptyset */      for (i = 0; i < Cluster.Lese_Groesse (); i++)	if (Dist[i] == 0)	  Result[i] = 1.0 / (double) Dim;	else	  Result[i] = 0.0;    }    /* if(Nulltest) */     else {      /* Falls I_k == \emptyset */      for (i = 0; i < Cluster.Lese_Groesse (); i++) {	if (Dist[i] == MAXDOUBLE)	  Result[i] = 0,0;	else {	  Summe = 0.0;	  for (j = 0; j < Cluster.Lese_Groesse (); j++)	    Summe += pow (Dist[i] / Dist[j], 1.0 / (M - 1.0));	  Result[i] = 1.0 / Summe;	  if (Result[i] > Max) {	    Max = Result[i];	    Result.Setze_Nummer (Cluster[i].Lese_Nummer ());	  }	}      }    }				/* else */  }