gmorph.cpp

一个由Mike Gashler完成的机器学习方面的includes neural net, naive bayesian classifier, decision tree, KNN, a genet

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

#include "GMorph.h"
#include "GBits.h"
#include "GArff.h"
#include "GArray.h"
#include "GVector.h"
#include "GKNN.h"
#include "GGraph.h"

GMorph::GMorph(GArffRelation* pRelation, GArffData* pData1, GArffData* pData2, double dOutputToInputRatio)
{
	m_pRelation = pRelation;
	m_pData1 = pData1;
	m_pData2 = pData2;
	m_dSquaredRatio = dOutputToInputRatio * dOutputToInputRatio;
	int nInputs = pRelation->GetInputCount();
	m_pEdgeMask = new double[2 * nInputs];
	m_pInputDelta = &m_pEdgeMask[nInputs];
	int i;
	for(i = 0; i < nInputs; i++)
		m_pEdgeMask[i] = GBits::GetRandomDouble();
}

GMorph::~GMorph()
{
	delete[] m_pEdgeMask;
}

// static
void GMorph::GetCorrespondingPoints(GArffRelation* pRelation, GArffData* pData1, GArffData* pData2, double dOutputToInputRatio, GIntArray* pPoints)
{
	GMorph morph(pRelation, pData1, pData2, dOutputToInputRatio);
	morph.FindCorrespondence(pPoints);
}

bool GMorph::CheckEdge(double* pOrigin, double* pTarget)
{
	int i, index;
	int nInputs = m_pRelation->GetInputCount();
	for(i = 0; i < nInputs; i++)
	{
		index = m_pRelation->GetInputIndex(i);
		m_pInputDelta[i] = pTarget[index] - pOrigin[index];
	}
	return(GVector::ComputeDotProduct(m_pInputDelta, m_pEdgeMask, nInputs) > 0);
}

void GMorph::MakeGraph(GGraphCut* pGraph, int nSource)
{
	double dOpeningSize = .001; // .1
	double dWallThickness = .7; // .5

	// Find the K-nearest neighbors in both data sets
	GNeighborFinder neighbors1(m_pRelation, m_pData1);
	GNeighborFinder neighbors2(m_pRelation, m_pData2);
	int nNeighbors = 2 * m_pRelation->GetInputCount();
	GTEMPBUF(int, pNeighbors, nNeighbors);
	GTEMPBUF(double, pNeighborDistances, nNeighbors);

	// Get some initial values
	int nInputs = m_pRelation->GetInputCount();
	GTEMPBUF(double, pWorkingVectors, nInputs * 4);
	double* pMins1 = &pWorkingVectors[0 * nInputs];
	double* pRanges1 = &pWorkingVectors[1 * nInputs];
	double* pMins2 = &pWorkingVectors[2 * nInputs];
	double* pRanges2 = &pWorkingVectors[3 * nInputs];
	int nPos1, nPos2, i, index;
	for(i = 0; i < nInputs; i++)
	{
		m_pData1->GetMinAndRange(i, &pMins1[i], &pRanges1[i]);
		m_pData2->GetMinAndRange(i, &pMins2[i], &pRanges2[i]);
	}

	// Make the graph
	int nNode = 0;
	double* pVec1;
	double* pVec2;
	double* pVec3;
	double cost, dClosestEdge1, dClosestEdge2, dInputGap, d;
	for(nPos1 = 0; nPos1 < m_pData1->GetSize(); nPos1++)
	{
		pVec1 = m_pData1->GetVector(nPos1);
		for(nPos2 = 0; nPos2 < m_pData2->GetSize(); nPos2++)
		{
			pVec2 = m_pData2->GetVector(nPos2);
			cost = m_pRelation->ComputeInputDistanceSquared(pVec1, pVec2) + m_pRelation->ComputeOutputDistanceSquared(pVec1, pVec2) * m_dSquaredRatio;

			// Make an edge to non-masked neighbors in m_pData1
			neighbors1.FindNeighbors(pNeighbors, pNeighborDistances, nNeighbors, pVec1, nPos1);
			for(i = 0; i < nNeighbors; i++)
			{
				pVec3 = m_pData1->GetVector(pNeighbors[i]);
				if(CheckEdge(pVec1, pVec3))
				{
					index = pNeighbors[i] * m_pData2->GetSize() + nPos2;
					pGraph->AddEdge(nNode, index, (float)cost);
				}
			}

			// Make an edge to non-masked neighbors in m_pData2
			neighbors2.FindNeighbors(pNeighbors, pNeighborDistances, nNeighbors, pVec2, nPos2);
			for(i = 0; i < nNeighbors; i++)
			{
				pVec3 = m_pData2->GetVector(pNeighbors[i]);
				if(CheckEdge(pVec2, pVec3))
				{
					index = nPos1 * m_pData2->GetSize() + pNeighbors[i];
					pGraph->AddEdge(nNode, index, (float)cost);
				}
			}

			// Connect to the source or sink if it's near the edge
			dClosestEdge1 = 1e200;
			dClosestEdge2 = 1e200;
			dInputGap = 0;
			for(i = 0; i < nInputs; i++)
			{
				index = m_pRelation->GetInputIndex(i);
				d = (pVec1[index] - pMins1[i]) / pRanges1[i];
				if(d < dClosestEdge1)
					dClosestEdge1 = d;
				d = 1.0 - (pVec2[index] - pMins2[i]) / pRanges2[i];
				if(d < dClosestEdge1)
					dClosestEdge1 = d;
				d = (pVec2[index] - pMins2[i]) / pRanges2[i];
				if(d < dClosestEdge2)
					dClosestEdge2 = d;
				d = 1.0 - (pVec1[index] - pMins1[i]) / pRanges1[i];
				if(d < dClosestEdge2)
					dClosestEdge2 = d;
				dInputGap = MAX(dInputGap, ABS((pVec1[index] - pMins1[i]) / pRanges1[i] - (pVec2[index] - pMins2[i]) / pRanges2[i]));
			}
			dInputGap -= dOpeningSize;
			dInputGap *= dWallThickness;
			if(dInputGap > dClosestEdge1)
			{
				// Connect to the source
				GAssert(dInputGap <= dClosestEdge2, "oh no, the walls overlap. This means there's no path across");
				pGraph->AddEdge(nNode, nSource, (float)1e30);
			}
			else if(dInputGap > dClosestEdge2)
			{
				// Connect to the sink
				pGraph->AddEdge(nNode, nSource + 1, (float)1e30);
			}
			nNode++;
		}
	}
}

void GMorph::GatherPathPoints(GGraphCut* pGraph, GIntArray* pPoints)
{
	GGraphEdgeIterator itt(pGraph, 0); 
	bool bSource;
	double* pVec1;
	double* pVec2;
	int nNode = 0;
	float fWeight;
	int nPos1, nPos2, nNeighbor, i, j;
	for(nPos1 = 0; nPos1 < m_pData1->GetSize(); nPos1++)
	{
		for(nPos2 = 0; nPos2 < m_pData2->GetSize(); nPos2++)
		{
			if(pGraph->DoesBorderTheCut(nNode))
			{
				bSource = pGraph->IsSource(nNode);
				itt.Reset(nNode);
				while(itt.GetNext(&nNeighbor, &fWeight))
				{
					if(pGraph->IsSource(nNeighbor) == bSource)
						continue;
					i = nNeighbor / m_pData2->GetSize();
					j = nNeighbor % m_pData2->GetSize();
					if(i == nPos1)
					{
						GAssert(j != nPos2, "expected a difference");
						pVec1 = m_pData2->GetVector(nPos2);
						pVec2 = m_pData2->GetVector(j);
					}
					else
					{
						GAssert(j == nPos2, "expected one of the values to be the same");
						pVec1 = m_pData1->GetVector(nPos1);
						pVec2 = m_pData1->GetVector(i);
					}
					if(!CheckEdge(pVec1, pVec2))
						continue;
					pPoints->AddInt(nNode);
					break;
				}
			}
			nNode++;
		}
	}
}

void GMorph::FindCorrespondence(GIntArray* pPoints)
{
	int nSource = m_pData1->GetSize() * m_pData2->GetSize();
	GGraphCut graph(nSource + 2);
	MakeGraph(&graph, nSource);
	graph.Cut(nSource, nSource + 1);
	GatherPathPoints(&graph, pPoints);
}