cfentry.c

数据挖掘经典的hierarchial clustering algorithm

#endif RECTANGLE
        }

void Entry::operator-=(const Entry &ent) {
        n -= ent.n;
        sx -= ent.sx;
        sxx -= ent.sxx;

#ifdef RECTANGLE
        rect = rect; // Be careful that rect can not be restored
#endif RECTANGLE
        }

// centroid euclidian distance D0
double Entry::operator||(const Entry& v2) const {
// return((sx/n) || (v2.sx/v2.n));
// for space allocation, performance and overflow reason
double tmp, d = 0;
for (short i=0; i<sx.dim; i++) {
        tmp = sx.value[i]/n - v2.sx.value[i]/v2.n;
        d += tmp*tmp;
        }
if (d>=0) return d; else return 0.0;
}

// centroid manhatan distance  D1
double Entry::operator^(const Entry &v2) const {
// return((sx/n) ^ (v2.sx/v2.n));
// for space allocation, performance and overflow reason
double tmp, d = 0;
for (short i=0; i<sx.dim; i++) {
        tmp = fabs(sx.value[i]/n - v2.sx.value[i]/v2.n);
        d += tmp;
        }
if (d>=0) return d; else return 0.0;
}

// inter-cluster distance D2
double Entry::operator|(const Entry& v2) const {
double d=(v2.n*sxx+n*v2.sxx-2*(sx&&v2.sx))/(n*v2.n);
if (d>=0) return d; else return 0.0;
}

// intra-cluster distance D3 (bad)
double Entry::operator&(const Entry& v2) const {
// return(2*((n+v2.n)*(sxx+v2.sxx)-
//           ((sx+v2.sx)&&(sx+v2.sx)))/((n+v2.n)*(n+v2.n-1)));
// for space allocation, performance and overflow reason
int tmpn = n+v2.n;
double tmp1, tmp2=0;
for (short i=0; i<sx.dim; i++) {
        tmp1 = sx.value[i]+v2.sx.value[i];
        tmp2 += tmp1/tmpn*tmp1/(tmpn-1);
        }
double d=2*((sxx+v2.sxx)/(tmpn-1)-tmp2);
if (d>=0) return d; else return 0.0;
}

// variance increase distance D4
double Entry::operator&&(const Entry& v2) const {
// return(n*((sx/n)&&(sx/n))+
//        v2.n*((v2.sx/v2.n)&&(v2.sx/v2.n))-
//        (n+v2.n)*(((sx+v2.sx)/(n+v2.n))&&((sx+v2.sx)/(n+v2.n))));
// for space allocation, performance and overflow reason
double tmp1, tmp2, tmp3;
double dot1, dot2, dot3;
dot1 = dot2 = dot3 =0;
for (short i=0; i<sx.dim; i++) {
        tmp1 = sx.value[i]/n;
        dot1 += tmp1*tmp1;
        tmp2 = v2.sx.value[i]/v2.n;
        dot2 += tmp2*tmp2;
        tmp3 = (sx.value[i]+v2.sx.value[i])/(n+v2.n);
        dot3 += tmp3*tmp3;
        }
double d=(n*dot1+v2.n*dot2-(n+v2.n)*dot3);
if (d>=0) return d; else return 0.0;
}

void Entry::Add(const Entry& e1, const Entry& e2) {
        n = e1.n+e2.n;
        sx.Add(e1.sx, e2.sx);
        sxx = e1.sxx+e2.sxx;

#ifdef RECTANGLE
        rect.Add(e1.rect, e2.rect); // rect changed
#endif RECTANGLE
        }

void Entry::Sub(const Entry& e1, const Entry& e2) {
        n = e1.n-e2.n;
        sx.Sub(e1.sx, e2.sx);
        sxx = e1.sxx-e2.sxx;
#ifdef RECTANGLE
        rect = e1.rect; // Be careful that rect can not be restored.
#endif RECTANGLE
        }

void Entry::Transform(const Vector &W, const Vector &M) {
if (n<=1) {
        sx.Transform(W,M);

#ifdef RECTANGLE
        rect.Transform(W,M);
#endif RECTANGLE

        sxx = sx && sx;
        }
}

// correct for dimension=1,2,3, needs to verify for dimension>3
// with d-dimensional hyper-sphere volume formula

// connect nonleaf entries
short connected(const Entry& ent1, const Entry& ent2)
{
double sqrR1, sqrR2, d;
sqrR1=ent1.Radius()*(ent1.sx.dim+2.0)/ent1.sx.dim;
sqrR2=ent2.Radius()*(ent2.sx.dim+2.0)/ent2.sx.dim;
d=ent1||ent2;
if (sqrt(d)<=sqrt(sqrR1)+sqrt(sqrR2)) return TRUE;
else return FALSE;
}

// connect leaf entries
short connected(const Entry& ent1, const Entry& ent2,
                short ftype, double Ft,double density)
{
double d=ent1||ent2;
switch (ftype) {
  case AVG_DIAMETER: if (sqrt(d)<2*sqrt(Ft/2.0*(ent1.sx.dim+2.0)/ent1.sx.dim) &&
                         ent1.n>density && ent2.n>density)
                     return TRUE;
                     else return FALSE;
  case AVG_RADIUS:   if (sqrt(d)<2*sqrt(Ft*(ent1.sx.dim+2.0)/ent1.sx.dim) &&
                         ent1.n>density && ent2.n>density)
                     return TRUE;
                     else return FALSE;
  default: print_error("connected", "Invalid fitness type");
  }
}

/* Intended for generating data files for Devise */

void Entry::Visualize_Circle(ostream &fo) const {
Vector tmpv;
tmpv.Init(sx.dim);
if (sx.dim>2)
        print_error("Entry::Visualize",
                    "can't visualize higher than 2 dimensions");
tmpv.Div(sx,n);
if (n>1) {
fo << 3 << " "          // shape: filled polygon
   << n%10+3 << " "     // color: variable
   << n << " "                                  // count
   << tmpv << " "                               // center
   << 2*sqrt(Radius()) << " "           //width
   << 2*sqrt(Radius()) << endl;       //height
   }
else {
fo << 3 << " "
   << n%10+3 << " "
   << n << " "
   << tmpv << " "
   << 0 << " "
   << 0 << endl;
   }
}

void Entry::Visualize_Rectangle(ostream &fo) const {
Vector tmpv;
tmpv.Init(sx.dim);
if (sx.dim>2)
        print_error("Entry::Visualize",
                            "can't visualize higher than 2 dimensions");
tmpv.Div(sx,n);
fo << 0 << " "   // shape: filled rectangle
   << 2 << " "   // color: red
   << n << " "
#ifdef RECTANGLE
   << rect << " "
#endif RECTANGLE
   << endl;     // center, width, height
}

void Entry::Visualize_Circle(ofstream &fo) const {
Vector tmpv;
tmpv.Init(sx.dim);
if (sx.dim>2)
        print_error("Entry::Visualize",
                    "can't visualize higher than 2 dimensions");
tmpv.Div(sx,n);
if (n>1) {
fo << 3 << " "
   << n%10+3 << " "
   << n << " "
   << tmpv << " "
   << 2*sqrt(Radius()) << " "
   << 2*sqrt(Radius()) << endl;
   }
else {
fo << 3 << " "
   << n%10+3 << " "
   << n << " "
   << tmpv << " "
   << 0 << " "
   << 0 << endl;
   }
}

void Entry::Visualize_Rectangle(ofstream &fo) const {
Vector tmpv;
tmpv.Init(sx.dim);
if (sx.dim>2)
        print_error("Entry::Visualize",
                            "can't visualize higher than 2 dimensions");
tmpv.Div(sx,n);
fo << 0 << " "
   << 2 << " "
   << n << " "
#ifdef RECTANGLE
   << rect << " "
#endif RECTANGLE
   << endl;
}

istream &operator>=(istream &fi, Entry &ent) {
        ent.n=1;
        fi >> ent.sx;
        ent.sxx = ent.sx && ent.sx;

#ifdef RECTANGLE
        ent.rect=ent.sx;
#endif RECTANGLE
        return fi;
        }

ifstream &operator>=(ifstream &fi, Entry &ent) {
        ent.n=1;
        fi >> ent.sx;
        ent.sxx = ent.sx && ent.sx;

#ifdef RECTANGLE
        ent.rect=ent.sx;
#endif RECTANGLE
        return fi;
        }

istream &operator>>(istream &fi, Entry &ent) {
        fi >> ent.n;
        fi >> ent.sx;
        fi >> ent.sxx;

#ifdef RECTANGLE
        fi >> ent.rect;
#endif RECTANGLE
        return fi;
        }

ifstream &operator>>(ifstream &fi, Entry &ent) {
        fi >> ent.n;
        fi >> ent.sx;
        fi >> ent.sxx;

#ifdef RECTANGLE
        fi >> ent.rect;
#endif RECTANGLE
        return fi;
        }

ostream &operator<<(ostream &fo, const Entry &r) {
        fo << r.n <<'\t';
        fo << r.sx <<'\t';
        fo << r.sxx <<'\t';

        fo << sqrt(r.Radius()) << '\t';
        fo << sqrt(r.Diameter()) << '\t';

#ifdef RECTANGLE
        fo << r.rect << '\t';
#endif RECTANGLE
        return fo;
}

ofstream &operator<<(ofstream &fo, const Entry &r) {
        fo << r.n <<'\t';
        fo << r.sx <<'\t';
        fo << r.sxx <<'\t';

        fo << sqrt(r.Radius()) << '\t';
        fo << sqrt(r.Diameter()) << '\t';

#ifdef RECTANGLE
        fo << r.rect << '\t';
#endif RECTANGLE
        return fo;
}