dbscan.cpp

经典的基于密度的聚类算法

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MaxDimension 10
#define MaxNum 1000


int main()
{
	FILE *fp;
	fp=fopen("Data.txt","r");
	int MinPts;
	double Eps;
	int Dimension;
	int Num;
	int i,j,k;
	char temp;
	fscanf(fp,"%d %lf %d %d",&MinPts,&Eps,&Dimension,&Num);
	double Data[MaxNum][MaxDimension]; 
	double distance[MaxNum][MaxDimension]; 
	//读取数据
	for(i=0;i<Num;i++)
		for(j=0;j<Dimension;j++)
			fscanf(fp,"%lf%c",&Data[i][j],&temp);
	fclose(fp);


	//label表明当前样本点的归属，无归属为－1。IsCore表明样本点是否是核心点
	int *label = (int *)malloc(sizeof(int)*Num);
	double *IsCore = (double *)malloc(sizeof(double)*Num);

	for(i=0;i<Num;i++)
	{
		label[i] = -1;
		IsCore[i] = false;
	}

	//计算任意两样本之间的距离
	for(i=0;i<Num;i++)
	{
		for(j=0;j<Num;j++)
		{
			distance[i][j]=0;
			for(k=0;k<Dimension;k++)
				distance[i][j] += (Data[i][k]-Data[j][k])*(Data[i][k]-Data[j][k]);
			distance[i][j] = sqrt(distance[i][j]);
		}
	}

	//找到核心点，并将属于它的数据点表明归属
	for(i=0;i<Num;i++)
	{
		int count=0;//记录样本i的Eps邻域内的点的数量
		//统计样本i的Eps邻域内点的数量，并将iEps邻域内的点看作是属于i的。已经有归属的数据点不再作为当前归属i的对象
		for(j=0;j<Num;j++)
		{
			if(label[j]==-1)
			{
				if(distance[i][j]<Eps)label[j]=i;
				count++;
			}
		}
		//如果i的Eps邻域内点的数量超过MinPts，说明i是一个核心点。如果i不是一个核心点，还原i的Eps邻域内的点的归属。
		if(count>=MinPts)
			IsCore[i] = true;
		else 
		{
			for(j=0;j<Num;j++)
			{
				if(label[j] == i)
					label[j] = -1;
			}
		}
	}
	

	//扫描剩余点，将其分配到最近的聚类中
	for(i=0;i<Num;i++)
	{
		if(label[i]==-1)
		{
			double dis=99999.9;
			
			for(j=0;j<Num;j++)
			{
				if(IsCore[j])
				{
					if(distance[i][j]<dis)
					{
						dis = distance[i][j];
						label[i]=j;
					}
				}
			}
		}
	}

	//输出结果
	fp = fopen("Result.txt","w");
	for(i=0;i<Num;i++)
		if(IsCore[i])
		{
			int n=0;
			fprintf(fp,"属于核心点(");
			for(k=0;k<Dimension;k++)
				fprintf(fp,"%lf ",Data[i][k]);
			fprintf(fp,")的对象为：\n");
			for(j=0;j<Num;j++)
			{
				if(label[j]==i)
				{
					n++;
					for(k=0;k<Dimension;k++)
						fprintf(fp,"%lf ",Data[j][k]);
					fprintf(fp,"\n");
				}
			}
			fprintf(fp,"共%d个\n",n);
		}

	return 0;
}