node.cc

经网络提出了一种基于蚁群聚类算法的径向基神经网络. 利用蚁群算法的并行寻优特征和挥发系数方法的自适应更改信息量的能力,并以球面聚类的方式确定了径向基神经网络中基函数的位置, 同时通过比较隐层神经元的相

/* $Id: node.cc,v 1.5 2006-08-21 15:02:00 jonathan Exp $
* Jonathan Ledlie, Harvard University.
* Copyright 2005.  All rights reserved.
*/

#include "sim.h"
#include "node.h"

int nodeCount = 0;
Node *node = NULL;

float **rtts = NULL;

int **neighbors = NULL;
int neighborCount = 0;

int withinMeasurementError = 0;
int maxNeighborCount = 0;
double measurement_error = 0.;

bool FULL_LATENCY_MATRIX = false;
int SAMPLE_EXPIRATION = 0;
double ERROR_FRACTION = 0.25;
double DAMPENING_FRACTION = 0.25;
bool USE_CONFIDENCE = false;
double INITIAL_WEIGHTED_ERROR = 1.;
int APP_VECTOR_HISTORY_TIME = 0;


char Node::appCoordUpdateMethod = ' ';
uint Node::windowSize = 0;
double Node::appCoordUpdateThreshold = 0;
int ctorCount = 0;

bool Node::updateAppVector (double systemDistanceDelta, int stamp,
							double &appComparison) 
{
	// we enter here having updated our system-level coordinate
	// with the most recent observation

	bool updatedAppVector = false;
	Point *newStartCoord, *newCurrentCoord, *startCentroid, *currentCentroid;

	switch (appCoordUpdateMethod) 
	{
	case ' ':
	case 's':
		if (systemDistanceDelta > appCoordUpdateThreshold)
		{
			appVector->assign (vec);    
			updatedAppVector = true;
		}
		break;
	case 'a':
		if (appVector->getEuclideanDistance (vec) > appCoordUpdateThreshold)
		{
			appVector->assign (vec);
			updatedAppVector = true;
		}
		break;
	case 'l':
	case 'e':
	case 'c':

		// add to windows
		// build both windows at once
		// this way they initially overlap and
		// we always have some state to do a comparison

		if (startCoords.size() < windowSize) 
		{
			newStartCoord = new Point (vec);
			startCoords.push_back (newStartCoord);
		}

		if (currentCoords.size() >= windowSize) 
		{
			Point *p = currentCoords[0];
			currentCoords.pop_front ();
			delete p;
		}
		newCurrentCoord = new Point (vec);
		currentCoords.push_back (newCurrentCoord);

		// compute centroids
		startCentroid = new Point();

		for (uint i = 0; i < startCoords.size(); i++)
		{
			startCentroid->add (startCoords[i]);
		}
		startCentroid->scale (1./startCoords.size());

		currentCentroid = new Point();

		for (uint i = 0; i < currentCoords.size(); i++)
		{
			currentCentroid->add (currentCoords[i]);
		}
		currentCentroid->scale (1./currentCoords.size());

		// if sufficient history, do comparison
		if (currentCoords.size() >= windowSize)
		{
			if (appCoordUpdateMethod == 'l') 
			{
				appComparison = findLocalRelativeDistance(startCentroid, 
					currentCentroid);
			} 
			else if (appCoordUpdateMethod == 'e') 
			{
				appComparison = findEnergyDistance ();
			} 
			else if (appCoordUpdateMethod == 'c')
			{
				appComparison = appVector->getEuclideanDistance (vec);
			}

			if (appComparison > appCoordUpdateThreshold)
			{
				appVector->assign (currentCentroid);
				clearCoords ();
				updatedAppVector = true;
			}
		}
		delete startCentroid;
		delete currentCentroid;
		break;

	default:
		printf ("Invalid appCoordUpdateMethod\n");
		exit (-1);
	}


	if (debug) 
	{
		if (updatedAppVector)
		{
			cout << "Updated app vector = " << appVector << endl;
		}
		else
		{
			cout << "Did not update app vector" << appVector << endl;
		}
	}

	/*
	if (updatedAppVector) {
	cout << stamp << " Updated app vector = " << *appVector << endl;
	exit (0);
	}
	*/
	return updatedAppVector;
}

void Node::addToNearestNeighbor (Point *neighbor, int timestamp) 
{
	// hmm, note that we are getting this guys updates for free
	// i.e. we are using a point, not our knowledge of the distance
	// TODO
	if (nearestNeighbor->stamp == 0 ||
		vec->getEuclideanDistance (neighbor) <
		vec->getEuclideanDistance (nearestNeighbor)) 
	{
		if (debug) 
		{
			cout << "Updating nearest neighbor " << neighbor << endl;
		}
		nearestNeighbor->assign (neighbor);
		nearestNeighbor->stamp = timestamp;
	}
}

double Node::findLocalRelativeDistance (Point *startCentroid,
										Point *currentCentroid) 
{  
	double nnStart = nearestNeighbor->getEuclideanDistance (startCentroid);
	double nnCurrent = nearestNeighbor->getEuclideanDistance (currentCentroid);
	double diff = fabs (nnStart - nnCurrent) / nnStart;
	if (debug)
	{
		cout << "in findLocalRelativeDistance" << endl;
		cout << "startCentroid = " << startCentroid << endl;
		cout << "currentCentroid = " << currentCentroid << endl;
		cout << "local relative distance = " << diff << endl;
	}
	return diff;
}

double Node::findEnergyDistance () 
{
	double sum = 0., abSum = 0., aSum = 0., bSum = 0.;

	if (debug)
	{
		cout << "startCoords size " << startCoords.size() 
			<< " currentCoords size " << currentCoords.size() << endl;

		cout << "startCoords: " << endl;
		for (uint i = 0; i < startCoords.size(); i++) 
		{
			cout << i << ": " << startCoords[i] << endl;
		}

		cout << "currentCoords: " << endl;
		for (uint i = 0; i < currentCoords.size(); i++) 
		{
			cout << i << ": " << currentCoords[i] << endl;
		}
	}

	for (uint i = 0; i < startCoords.size(); i++)
	{
		for (uint j = 0; j < currentCoords.size(); j++)
		{
			abSum += startCoords[i]->getEuclideanDistance (currentCoords[j]);
		}
	}
	abSum *= 2./(startCoords.size()*currentCoords.size());
	if (debug)
		cout << "abSum = " << abSum << endl;


	for (uint i = 0; i < startCoords.size(); i++) 
	{
		for (uint j = 0; j < startCoords.size(); j++) 
		{
			aSum += startCoords[i]->getEuclideanDistance (startCoords[j]);
		}
	}
	aSum *= 1./(startCoords.size()*startCoords.size());
	if (debug)
		cout << "aSum = " << aSum << endl;

	for (uint i = 0; i < currentCoords.size(); i++) 
	{
		for (uint j = 0; j < currentCoords.size(); j++) 
		{
			bSum += currentCoords[i]->getEuclideanDistance (currentCoords[j]);
		}
	}
	bSum *= 1./(currentCoords.size()*currentCoords.size());
	if (debug)
		cout << "bSum = " << bSum << endl;

	sum = abSum - aSum - bSum;

	sum *= (startCoords.size()*currentCoords.size()) /
		(startCoords.size()+currentCoords.size());

	if (debug)
		cout << "psum = " << sum << endl;

	return sum;
}

void Node::addSample (int yourId, double sample, 
					  Point *yourCoord, double yourWeightedError,
					  Point *yourAppCoord,
					  int stamp)
{
	sampleCount++;
	map<int,Samples*>::iterator samplesIter = node2samples.find(yourId);
	Samples *samples = NULL;
	if (samplesIter == node2samples.end()) 
	{
		Samples *samples = new Samples();
		node2samples.insert(pair<int,Samples*>(yourId,samples));
		samplesIter = node2samples.find(yourId);
	}
	samples = samplesIter->second;
	samples->addSample(sample, id, yourId, yourCoord, yourWeightedError,
		yourAppCoord, stamp);
}

double Node::getSample (int yourId)
{
	map<int,Samples*>::iterator samplesIter = node2samples.find(yourId);
	Samples *samples = NULL;
	if (samplesIter == node2samples.end()) 
	{
		return -1;
	}
	samples = samplesIter->second;
	return samples->getSample();
}



bool Node::isInInitialState ()
{
	if (weightedError == INITIAL_WEIGHTED_ERROR &&
		vec->isInInitialState ())
		return true;
	return false;
}

bool Node::hasConfidence () 
{
	if (weightedError < .99)
		return true;
	return false;
}


Node::Node ()
{
	vec = new Point();
	appVector = new Point();
	nearestNeighbor = new Point();
	weightedError = INITIAL_WEIGHTED_ERROR;
	lastUpdateTo = 0;
	lastUpdateFrom = 0;
	sampleCount = 0;
	distanceDelta = 0;

	fixedNearestNeighborId = -1;
	fixedNearestNeighborDistance = 0;
	id = ctorCount++;
}

void Node::clearCoords () 
{
	for (uint i = 0; i < startCoords.size(); i++) 
	{
		Point *p = startCoords[i];
		delete p;
	}
	for (uint i = 0; i < currentCoords.size(); i++) 
	{
		Point *p = currentCoords[i];
		delete p;
	}

	startCoords.clear ();
	currentCoords.clear ();

}

Node::~Node () 
{
	for (map<int,Samples*>::iterator samplesIter = node2samples.begin();
		samplesIter != node2samples.end(); samplesIter++) 
	{
			Samples *samples = samplesIter->second;
			delete samples;
	}

	clearCoords ();

	delete vec;
	delete appVector;
	delete nearestNeighbor;
}

void Node::printCoord (FILE *fp) 
{
	for (int i = 0; i < DIMENSIONS; i++) 
	{
		fprintf (fp, "%.1f ", vec->v[i]);
	}
	if (USE_HEIGHT)
	{
		fprintf (fp, "h %.1f ", vec->height);
	}
}

void Node::printAppCoord (FILE *fp) 
{
	if (appVector != NULL)
	{
		for (int i = 0; i < DIMENSIONS; i++) 
		{
			fprintf (fp, "%.1f ", appVector->v[i]);
		}
	}
	if (USE_HEIGHT)
	{
		fprintf (fp, "h %.1f ", appVector->height);
	}
}

void Node::addDistanceDelta (double dd) 
{
	// EWMA on recent movement
	distanceDelta = (.05 * dd) + (.95 * distanceDelta);
}

void Node::printStat (FILE *fp) 
{
	fprintf (fp, "conf %f sC %d dd %f lastTo %d lastFrom %d", weightedError, sampleCount, distanceDelta, lastUpdateTo, lastUpdateFrom);
}

ostream& operator << (ostream& os, Node& n) 
{
	for (int i = 0; i < DIMENSIONS; i++)
	{
		os << n.vec->v[i] << " ";
	}
	os << "conf " << n.weightedError;
	os << "sC " << n.sampleCount;
	return os;
}

void Node::setFixedSampleArray (int nodeCount) 
{
	fixedSample.reserve (nodeCount);
	for (int i = 0; i < nodeCount; i++)
	{
		fixedSample.push_back (0);
	}
}

void Node::setFixedSample (int yourId, double sample)
{
	if (fixedNearestNeighborId < 0 ||
		sample < fixedNearestNeighborDistance)
	{
			fixedNearestNeighborDistance = sample;
			fixedNearestNeighborId = yourId;
	}

	fixedSample[yourId] = sample;
}

double Node::getFixedSample (int yourId) 
{
	return fixedSample[yourId];
}

double Node::getFixedSamplePercentile (double p) 
{
	return percentile (fixedSample, p);
}

void Node::printVector ()
{
	//  appVector->print();
	vec->print(stdout);
}