dbscan.cpp

聚类研究

// Dbscan.cpp: implementation of the Dbscan class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "cluster.h"
#include "Dbscan.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Dbscan::Dbscan()
{
	dis = NULL;
	C = NULL;
	p = NULL;
}

void Dbscan::set(int _n,int _Eps,int _Minpts)
{
    dis = new int * [_n];
	for(int i = 0; i < _n; i++)
		dis[i] = new int [_n];
	for(int j = 0; j <_n; j++)
		for(int k = 0; k <_n; k++)
			dis[j][k] = 0 ;
    Eps = _Eps;
	N = _n;
	Minpts = _Minpts;
	p = new point[_n];
	C = new int[_n];
	for(int l = 0 ; l < _n ; l++)
		C[l] = -2;
	Class = 0;
}

void Dbscan::init_dis()
{
	int i,j;
	for(i = 0 ; i < N; i++)
		for(j = 0 ; j < N; j++)
			if( distance(p[i],p[j]) <= Eps*Eps )
				dis[i][j] = 1;
}

Dbscan::~Dbscan()
{
	if( p )
		delete [] p;
	if( C )
		delete [] C;
	if( dis )
	{
		for(int i = 0; i < N; i++)
			delete []dis[i];
		delete [] dis;
	}
}

long Dbscan::distance(point p1,point p2)
{
	long dis = 
		(p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
	return dis;
}

bool Dbscan::Core(int i)
{
	int sum = 0 ;
	for(int j = 0 ; j < N; j++)
		sum += dis[i][j];
	if(sum >= Minpts )
		return true;
	return false;
}

int Dbscan::visit_next()
{
	for(int i = 0; i < N ; i++)
		if( C[i] == -2 )
			return i;
	return -1 ;
}

void Dbscan::Db_scan()
{
	init_dis();
	time_t t;  
	srand((unsigned) time(&t));  
	int p = rand()%N;
	C_n q(N);
	do{
		if( Core(p) )
		{
			q.i = 0; 
			q.j = 0 ;
			q.Id[ q.j++ ] = p;
			C[p] = Class;
			for(int i = 0 ; i < N ; i ++)
				if( dis[p][i] == 1 && C[i] < 0 )
				{
					q.Id[ q.j++ ] = i;
					C[i] = Class;
				} 
			while( q.i < q.j )
			{
				if( Core( q.Id[ q.i ] ) )
					for( int j = 0 ; j < N; j++)
						if( dis[ q.Id[ q.i ] ][j] == 1 && C[ j ]< 0 )
						{
							q.Id[ q.j++ ] = j;
							C[ j ] = Class;
						}
				q.i++;
			}
			Class++;
		}
		else
			C[ p ] = -1;  //noise point
		p = visit_next();
		if( p < 0 )
			break;
	}while( true );
}