gcluster.cpp

一个非常有用的开源代码

/*
	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 "GCluster.h"
#include "GArray.h"
#include "GArff.h"
#include "GKNN.h"
#include "GBitTable.h"
#include "GPointerQueue.h"
#include <math.h>

GNeighborClusterer::GNeighborClusterer(int nVectorCount)
{
	m_pClusters = new GIntArray(8);
	m_pVectors = new GIntArray(nVectorCount);
}

GNeighborClusterer::~GNeighborClusterer()
{
	delete(m_pClusters);
	delete(m_pVectors);
}

// static
GNeighborClusterer* GNeighborClusterer::Cluster(GArffRelation* pRelation, GArffData* pData, int nNeighbors)
{
	GNeighborFinder neighborFinder(pRelation, pData, MAX(8, nNeighbors));
	int nVectors = pData->GetSize();
	GNeighborClusterer* pClusterer = new GNeighborClusterer(nVectors);
	GBitTable bits(nVectors);
	GTEMPBUF(int, pNeighbors, nNeighbors);
	GTEMPBUF(double, pDistances, nNeighbors);
	int nFirstAvailable = 0;
	int i, j;
	double* pVector;
	while(true)
	{
		while(nFirstAvailable < nVectors && bits.GetBit(nFirstAvailable))
			nFirstAvailable++;
		if(nFirstAvailable >= nVectors)
			break;
		pClusterer->m_pClusters->AddInt(pClusterer->m_pVectors->GetSize());
		GIntQueue q;
		q.Push(nFirstAvailable);
		while(q.GetSize() > 0)
		{
			i = q.Pop();
			if(bits.GetBit(i))
				continue;
			pClusterer->m_pVectors->AddInt(i);
			bits.SetBit(i, true);
			pVector = pData->GetVector(i);
			neighborFinder.FindNeighbors(pNeighbors, pDistances, nNeighbors, pVector, i);
			for(j = 0; j < nNeighbors; j++)
				q.Push(pNeighbors[j]);
		}
	}
	return pClusterer;
}

int GNeighborClusterer::GetClusterCount()
{
	return m_pClusters->GetSize();
}

int GNeighborClusterer::GetClusterSize(int nCluster)
{
	if(nCluster < m_pClusters->GetSize() - 1)
		return m_pClusters->GetInt(nCluster + 1) - m_pClusters->GetInt(nCluster);
	else
		return m_pVectors->GetSize() - m_pClusters->GetInt(nCluster);
}

int GNeighborClusterer::GetVectorIndex(int nCluster, int nVector)
{
	return m_pVectors->GetInt(m_pClusters->GetInt(nCluster) + nVector);
}

#ifndef NO_TEST_CODE
//static
void GNeighborClusterer::Test()
{
	// Make a 3D data set with 3 entwined spirals
	GArffRelation rel;
	rel.AddAttribute(new GArffAttribute(true, 0, NULL));
	rel.AddAttribute(new GArffAttribute(true, 0, NULL));
	rel.AddAttribute(new GArffAttribute(true, 0, NULL));
	GArffData data(3000);
	double dThirdCircle = PI * 2 / 3;
	double* pVector;
	int i;
	for(i = 0; i < 1000; i++)
	{
		pVector = new double[3];
		pVector[0] = cos((double)i * 4 * PI / 1000);
		pVector[1] = sin((double)i * 4 * PI / 1000);
		pVector[2] = (double)i / 1000;
		data.AddVector(pVector);

		pVector = new double[3];
		pVector[0] = cos((double)i * 4 * PI / 1000 + dThirdCircle);
		pVector[1] = sin((double)i * 4 * PI / 1000 + dThirdCircle);
		pVector[2] = (double)i / 1000;
		data.AddVector(pVector);

		pVector = new double[3];
		pVector[0] = cos((double)i * 4 * PI / 1000 + dThirdCircle + dThirdCircle);
		pVector[1] = sin((double)i * 4 * PI / 1000 + dThirdCircle + dThirdCircle);
		pVector[2] = (double)i / 1000;
		data.AddVector(pVector);
	}

	// Cluster them
	GNeighborClusterer* pClusterer = GNeighborClusterer::Cluster(&rel, &data, 10);
	Holder<GNeighborClusterer*> hClusterer(pClusterer);

	// Check the answers
	if(pClusterer->GetClusterCount() != 3)
		throw "wrong number of clusters";
	int nClusterSize = pClusterer->GetClusterSize(0);
	if(pClusterer->GetClusterSize(1) != nClusterSize)
		throw "clusters different sizes";
	if(pClusterer->GetClusterSize(2) != nClusterSize)
		throw "clusters different sizes";
	for(i = 0; i < nClusterSize; i++)
	{
		if(pClusterer->GetVectorIndex(0, i) % 3 != 0)
			throw "vector in wrong cluster";
		if(pClusterer->GetVectorIndex(1, i) % 3 != 1)
			throw "vector in wrong cluster";
		if(pClusterer->GetVectorIndex(2, i) % 3 != 2)
			throw "vector in wrong cluster";
	}
}
#endif // NO_TEST_CODE