📄 cluster.cpp

📁 用VC。NET2005实现优秀的最近邻搜索算法LB-TREE的模拟和图形显示。具有建立优良数据结构和搜索功能
💻 CPP
字号:
#include "StdAfx.h"
#include "Cluster.h"
#include "math.h"

Cluster::Cluster(void)
: dimension(0)
, MeanPoint(NULL)
, Radius(0)
, Level(0)
, Tag(-1)
, DisArray(NULL)
, PointNum(0)
{
}
Cluster::Cluster(int Dim,int Lev)
: dimension(Dim)
, Radius(0)
, Level(Lev)
, Tag(-1)
, DisArray(NULL)
, PointNum(0)
{
	MeanPoint=new NPoint(Dim);
}
Cluster::~Cluster(void)
{
	delete MeanPoint;
	SubCluster.RemoveAll();
}

// 获得聚类的维度
int Cluster::GetDimension(void)
{
	return dimension;
}

// 获得聚类的中心点
NPoint* Cluster::GetMeanPoint(void)
{
	return MeanPoint;
}

// 获得聚类的半径
double Cluster::GetRadius(void)
{
	return Radius;
}

// 插入新的子聚类
void Cluster::InsertSubCluster(Cluster* Sub)
{
	SubCluster.Add(Sub);
	ComputeMean();
	ComputeRadius();
}

// 获得聚类的层次信息
int Cluster::GetLevel(void)
{
	return Level;
}

// 计算聚类中心点
void Cluster::ComputeMean(void)
{
	if(SubCluster.GetSize()!=0)
	{	
		for(int i=0;i<dimension;i++)
        {
	        double value=0;
			for(int j=0;j<SubCluster.GetSize();j++)
			{
				value+=((Cluster*)(SubCluster.GetAt(j)))->GetMeanPoint()->GetValueAt(i);
			}
			MeanPoint->SetValueAt(i,value/SubCluster.GetSize());
	    }
	}
}

// 计算聚类的半径
void Cluster::ComputeRadius(void)
{
	if(SubCluster.GetSize()!=0)
	{
		Radius=0;
		for(int i=0;i<SubCluster.GetSize();i++)
		{
			double temp=MeanPoint->DistanceL(((Cluster*)(SubCluster.GetAt(i)))->GetMeanPoint(),Level);
			if(temp>Radius)
				Radius=temp;
		}
	}
	else
	{
		Radius=0;
	}
}

// 当聚类是叶子节点时，自身的点就是均值中心点
void Cluster::InitialMeanPoint(NPoint* PointPtr)
{
	for(int i=0;i<dimension;i++)
	{
		MeanPoint->SetValueAt(i,PointPtr->GetValueAt(i));
	}
}

// 获得子聚类的数组指针
CObArray* Cluster::GetSubCluster(void)
{
	return &SubCluster;
}

// 设置聚类层次
void Cluster::SetLevel(int Lev)
{
	Level=Lev;
}

// 获得标记信息
int Cluster::GetTag(void)
{
	return Tag;
}

// 设置标记位
void Cluster::SetTag(int T)
{
	Tag=T;
}

// 获得距离矩阵指针
double* Cluster::GetDisArray(void)
{
	return DisArray;
}

// 计算聚类之间的矩阵
void Cluster::ComputeDisArr(void)
{
	if((Tag==-1)&&(SubCluster.GetSize()!=0))
	{
		int ArrScale=(int)SubCluster.GetSize();
        PointNum=ArrScale;
		DisArray=new double[ArrScale*ArrScale];
		for(int i=0;i<ArrScale;i++)
			for(int j=0;j<ArrScale;j++)
			{
				*(DisArray+i*ArrScale+j)=((Cluster*)(SubCluster.GetAt(i)))->GetMeanPoint()->DistanceL(((Cluster*)(SubCluster.GetAt(j)))->GetMeanPoint(),Level+1);
			}
	}
}

// 获得聚类中距离最近的两个子聚类
double Cluster::GetClosePairs(int& ClusterA, int& ClusterB)
{
	if(DisArray!=NULL)
	{
		int SubNum=(int)SubCluster.GetSize();
		double Min=9999;
		for(int i=1;i<SubNum;i++)
			for(int j=0;j<i;j++)
			{
				Cluster* A=(Cluster*)(SubCluster.GetAt(i));
				Cluster* B=(Cluster*)(SubCluster.GetAt(j));
				if(A->GetTag()!=-1)
				{
					if(B->GetTag()!=-1)
					{
						if(*(DisArray+A->GetTag()*PointNum+B->GetTag())<Min)
						{
							Min=*(DisArray+A->GetTag()*PointNum+B->GetTag());
                            ClusterA=i;
                            ClusterB=j;
						}
					}
					else
					{
						int BSubNum=(int)(B->GetSubCluster()->GetSize());
						double max=0;
						for(int k=0;k<BSubNum;k++)
						{
							Cluster* BSub=(Cluster*)(B->GetSubCluster()->GetAt(k));
						    if(*(DisArray+A->GetTag()*PointNum+BSub->GetTag())>max)
							{
								max=*(DisArray+A->GetTag()*PointNum+BSub->GetTag());
							}
						}
						if(max<Min)
						{
							Min=max;
                            ClusterA=i;
                            ClusterB=j;
						}
					}
				}
				else
				{
					if(B->GetTag()==-1)
					{
						int ASubNum=(int)(A->GetSubCluster()->GetSize());
						int BSubNum=(int)(B->GetSubCluster()->GetSize());
						double max=0;
						for(int k=0;k<ASubNum;k++)
						{
							for(int l=0;l<BSubNum;l++)
							{
								Cluster* ASub=(Cluster*)(A->GetSubCluster()->GetAt(k));
                                Cluster* BSub=(Cluster*)(B->GetSubCluster()->GetAt(l));
								if(*(DisArray+ASub->GetTag()*PointNum+BSub->GetTag())>max)
								{
									max=*(DisArray+ASub->GetTag()*PointNum+BSub->GetTag());
								}
							}
						}
						if(max<Min)
						{
							Min=max;
                            ClusterA=i;
                            ClusterB=j;
						}
					}
					else
					{
						int ASubNum=(int)(A->GetSubCluster()->GetSize());
						double max=0;
						for(int k=0;k<ASubNum;k++)
						{
							Cluster* ASub=(Cluster*)(A->GetSubCluster()->GetAt(k));
						    if(*(DisArray+ASub->GetTag()*PointNum+B->GetTag())>max)
							{
								max=*(DisArray+ASub->GetTag()*PointNum+B->GetTag());
							}
						}
						if(max<Min)
						{
							Min=max;
                            ClusterA=i;
                            ClusterB=j;
						}
					}
				}
			}
	    return  Min;
	}
    return -1;
}

// 聚合子聚类
void Cluster::AggSubCluster(double Threshold)
{
	if(((int)pow(2.0,Level)<dimension)&&(Tag==-1))
	{
		bool Condition=true;
		double DisAtoB=0;
		double Last=0;
		ComputeDisArr();
		while(Condition)
		{
			int ClusterA=0,ClusterB=0;
			DisAtoB=GetClosePairs(ClusterA,ClusterB);
			if((Level==-1)&&(SubCluster.GetSize()==3))
			{
				Condition=false;
			}
			else if((Level!=-1)&&(DisAtoB>2*Threshold))
			{
				Condition=false;
			}
			else
			{
				Cluster* SubA=(Cluster*)(SubCluster.GetAt(ClusterA));
				Cluster* SubB=(Cluster*)(SubCluster.GetAt(ClusterB));
				SubA->SetLevel(Level+2);
				SubB->SetLevel(Level+2);
				
				Cluster* Temp=new Cluster(dimension,Level+1);
				
				if(SubA->GetTag()==-1)
				{
					if(SubB->GetTag()==-1)
					{

						int num=(int)(SubA->GetSubCluster()->GetSize());
						for(int i=0;i<num;i++)
						{
							Temp->InsertSubCluster((Cluster*)(SubA->GetSubCluster()->GetAt(i)));
						}
						num=(int)(SubB->GetSubCluster()->GetSize());
						for(int i=0;i<num;i++)
						{
							Temp->InsertSubCluster((Cluster*)(SubB->GetSubCluster()->GetAt(i)));
						}
					}
					else
					{
						int num=(int)(SubA->GetSubCluster()->GetSize());
						for(int i=0;i<num;i++)
						{
							Temp->InsertSubCluster((Cluster*)(SubA->GetSubCluster()->GetAt(i)));
						}
						Temp->InsertSubCluster(SubB);
					}
				}
				else
				{
					if(SubB->GetTag()==-1)
					{
						int num=(int)(SubB->GetSubCluster()->GetSize());
						for(int i=0;i<num;i++)
						{
							Temp->InsertSubCluster((Cluster*)(SubB->GetSubCluster()->GetAt(i)));
						}
						Temp->InsertSubCluster(SubA);
					}
					else
					{
						Temp->InsertSubCluster(SubA);
						Temp->InsertSubCluster(SubB);
					}
				}
				SubCluster.RemoveAt(ClusterA);
				SubCluster.RemoveAt(ClusterB);
				SubCluster.Add(Temp);
				Last=Temp->GetRadius();
			}
		}
		int SubNum=(int)SubCluster.GetSize();
		for(int i=0;i<SubNum;i++)
		{
			int SubSpring=(int)((Cluster*)(SubCluster.GetAt(i)))->GetSubCluster()->GetSize();
			for(int j=0;j<SubSpring;j++)
			{
				((Cluster*)(((Cluster*)(SubCluster.GetAt(i)))->GetSubCluster()->GetAt(j)))->SetTag(j);
			}
            ((Cluster*)(SubCluster.GetAt(i)))->AggSubCluster(Last);
		}
	}
}

// 在二维坐标系下图形显示聚类
void Cluster::Illustrate(CDC* pDC, int Zoom, int CoordinateX, int CoordinateY,int Order,NPoint* Mean)
{
	CBrush *pBrush=CBrush::FromHandle((HBRUSH)GetStockObject(NULL_BRUSH));
	CBrush* OldB=pDC->SelectObject(pBrush);
	CPen pen;
	CPen* OldP=NULL;	
	int Red=0,Blue=0,Green=0;
	if(Tag!=-1)
	{
		int color=Order%3;
		switch(color)
		{
			case 0:Red=255;break;
			case 1:Blue=255;break;
			case 2:Green=255;break;
		}
        pen.CreatePen(0,1,RGB(Red,Green,Blue));
        OldP=pDC->SelectObject(&pen);
        int x=CoordinateX+100*Zoom+(int)(MeanPoint->GetValueAt(0)*100*Zoom);
        int y=CoordinateY+100*Zoom+(int)(MeanPoint->GetValueAt(1)*100*Zoom);
		pDC->MoveTo(x,y);
        int x2=CoordinateX+100*Zoom+(int)(Mean->GetValueAt(0)*100*Zoom);
        int y2=CoordinateY+100*Zoom+(int)(Mean->GetValueAt(1)*100*Zoom);
		pDC->LineTo(x2,y2);
		pDC->Ellipse(x-Zoom,y-Zoom,x+Zoom,y+Zoom);
		pDC->SelectObject(OldP);
	}
	else
	{
		int color=Order%3;
		switch(color)
		{
			case 0:Red=255;break;
			case 1:Blue=255;break;
			case 2:Green=255;break;
		}
		pen.CreatePen(0,1,RGB(Red,Green,Blue));
		OldP=pDC->SelectObject(&pen);
        int x=CoordinateX+100*Zoom+(int)(MeanPoint->GetValueAt(0)*100*Zoom);
        int y=CoordinateY+100*Zoom+(int)(MeanPoint->GetValueAt(1)*100*Zoom);
		int R=(int)(Radius*100*Zoom);
        if(Level==0)
		{
			pDC->MoveTo(x+R+Zoom,CoordinateY);
			pDC->LineTo(x+R+Zoom,CoordinateY+200*Zoom);
		}
		else
		{
			pDC->Ellipse(x-R-Zoom,y-R-Zoom,x+R+Zoom,y+R+Zoom);
		}
		int SubNum=(int)SubCluster.GetSize();
		for(int i=0;i<SubNum;i++)
		{
			((Cluster*)(SubCluster.GetAt(i)))->Illustrate(pDC,Zoom,CoordinateX,CoordinateY,i,MeanPoint);
		}
		pDC->SelectObject(OldP);
	}
	pDC->SelectObject(OldB);
}

// 计算查询点到此举类的下限距离
double Cluster::DisLB(NPoint* QueryPoint)
{
	return MeanPoint->DistanceL(QueryPoint,Level)-Radius;
}
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -