cluster.cc

模糊聚类的算法实现程序

/************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 */
  }