写文章的起因

本人是一名大二的学生，原本对于人工智能方面的算法就有一定的兴趣，正巧碰上期末课设需要用到层次聚类来完成课设，就顺水推舟，用C++（准确来说是MFC）完成了层次聚类算法的课设，之所以没用python一方面是了解不够另一方面是为了照顾队友吧，然后深刻体会到python的方便233…， 鉴于本人还是一名新的幼稚猿，对于犯的错误，希望各位嘴下留情.

所用数据集及预处理

我们所采用的数据集是Iris数据集（鸢尾花数据集），算是一个比较经典的算法吧，借鉴了别家层次聚类的结果，我们采用了Iris数据集的后两位数据PWidth和PLength来作为我们划分聚类群的主要依据。同时也是为了更方便的用欧氏距离划分。网上百度可以轻易找到该数据集，然后是对数据集的处理，我们是用的Excel先提前打乱数据再采用C++文件读入流的形式，将数据读取到相应的类数组中。代码如下。

void CLeverView::ReadFile(CFlower *a)//自定义的数据类
{
   
	fstream f("\\\\Mac\\Home\\Desktop\\lever.txt",ios::in);
	//此处填要读的文件的地址
	for(int i=0;i<DataSum;i++)//DataSum数据总数，在构造函数中给出
	{
   
		f>>a[i].SLength>>a[i].SWidth;//依次读入数据
		f>>a[i].PLength>>a[i].PWidth>>a[i].Species;
		f.get();//用于读取换行
	}
	f.close();
}

划分簇的基础思维和结果

我们采用的是通过比较不同簇之间的欧氏距离和全连接的方法来计算如何划分的。起始的时候，根据每一个数据作为一个簇，然后依次合并有些类似最小生成树的合成hhh ，直到簇的数量等于我们要划分的种类数目。其后基于这个思维还对具体的代码逐步进行了优化，之后会讲到。然后结果我们是调用pDC->Ellipse的方法画出了散点图，由于精度问题，缺失了一部分数据足以显现python的优越性 ，先上一个最终的结果图。

开发中遇到的一些问题及算法优化

首先是我们起初一开始采用的算法，合并簇的方法是对于对应的距离矩阵，每次从i=0开始，依次找i+1到最大簇总数之间，距离最短的两个数据簇，并将其合并，簇的总数为；有些许类似选择排序的算法。
查找的复杂度至多只有n。最大的时间复杂度为（log2n）n**2，这种算法的缺陷在于，你所求出来的最短距离，可能只是局部最短的距离（单纯对于i来说的），而并不是所有的距离中最短的，效果也很差。如下图。

之后我们，重新改进了算法，重新改为求全局内的最短距离，很大程度上改进了算法，但是时间复杂度也上升了。但效果却很好，起初我们仅仅用了105个数据，所以数据的吻合程度很好，代码如下。

double CLeverView::Dist(CFlower &b,CFlower &c)
//计算某两个数据点之间的距离
{
   
	double tem;
	tem=pow((b.PWidth-c.PWidth),2)+pow((b.PLength-c.PLength),2);
	//计算不同的鸢尾花
	//tem=sqrt(tem);//平方效果更不好，故注释掉了。。
	return tem;
}

double CLeverView::AverageLinkage(int a,int b,int Point[][150])
//计算a簇和b簇间的平均距离
{
   
	int i,j;
	double DistSum=0;
	for(i=0;i<DataSum && Point[a][i]!=-1;i++)
	{
   
		for(j=0;j<DataSum && Point[b][j]!=-1;j++)
		{
   
			DistSum=Dist(A[Point[a][i]],A[Point[b][j]])+DistSum;
		}
	}
	if(DistSum!=0)
		return DistSum/(double)(i+1)*(j+1);
	else
		return 10000;
}

效果图如下：

但随着我逐渐增加数据量到150后，算法的正确率开始下降，于是我们又重新分析，可能是我们采用全连接的方式不一定够好，我才用了小组成员里将簇内信息平均来计算距离的方法，准确度更高了，但是我感觉到运行明显变慢？球球大家可能的话也给我支点招嘤嘤嘤， 附上代码和效果图。

double CLeverView::Dist(int b,int c,int Point[][150])//距离函数重载
{
   

	double tem=10000;//记录暂时的距离
	double bPWidth=0,bPLength=0,cPWidth=0,cPLength=0;
	int i,j;
	for(i=0;i<DataSum && Point[b][i]!=-1;i++)//将簇b中的数据都累加并求平均值
	{
   
		bPWidth=A[Point[b][i]].PWidth+bPWidth;
		bPLength=A[Point[b][i]].PLength+bPLength;
	}
	bPWidth=bPWidth/i;		//求平均值
	bPLength=bPLength/i;	//求平均值
	for(j=0;j<DataSum && Point[c][j]!=-1;j++)//将簇c中数据都累加并求平均值
	{
   
		cPWidth=A[Point[c][j]].PWidth+cPWidth;
		cPLength=A[Point[c][j]].PLength+cPLength;
	}
	cPWidth=cPWidth/j;
	cPLength=cPLength/j;
	tem=pow((bPWidth-cPWidth),2)+pow((bPLength-cPLength),2);//计算不同的鸢尾花
	return tem;
}

150个数据也依旧精确。

预测错误率的算法

我们预测错误率的算法是，通过统计最后Point数组簇中的大部分的数据点的类型，将其作为本簇的一个分类，然后再循环一遍查找不对应的数据，然后错误数据除以总数据，代码如下。

void CLeverView::TestClassfiy(CDC *pDC,int Point[][150])//检查算法的正确率
{
   
	int i,j,set=0,ver=0,vir=0;
	CString tem;
	int Cluster[3],num=0;
	double sum=0,err=0;
	double AllSum=0,AllErr=0;
	memset(Cluster,-1,3);//初始化簇信息表
	for(i=0;i<DataSum;i++)//将簇信息移动到前三行
	{
   
		if(Point[i][0]!=-1)
		{
   
			for(j=0;j<DataSum;j++)
			{
   
				Point[num][j]=Point[i][j];
			}
			num++;
		}
		
	}
	num=0;//重新赋值
	for(i=0;i<3;i++)
	{
   
		for(j=0;j<DataSum && Point[i][j]!=-1;j++)
		{
   
			if(!strcmp("setosa",A[Point[i][j]].Species))
			{
   
				set++;
			}
			if(!strcmp("versicolor",A[Point[i][j]].Species))
			{
   
				ver++;
			}
			if(!strcmp("virginica",A[Point[i][j]].Species))
			{
   
				vir++;
			}
		}
		if(set>ver && set>vir)//根据簇里大部分的类型来判断簇类型
		{
   
			Cluster[num++]=setosa;//宏定义
			set=ver=vir=0;//重新置为0
		}
		else
		{
   
			if(ver>set && ver>vir)
			{
   
				Cluster[num++]=versicolor;
				set=ver=vir=0;//重新置为0
			}
			else
			{
   
				if(vir>set && vir>ver)
				{
   
					Cluster[num++]=virginica;
					set=ver=vir=0;//重新置为0
				}
			}
		}
	}//for
	for(i=0;i<3;i++)//统计错误的个数
	{
   
		sum=0;
		err=0;
		switch(Cluster[i])//判断当前组的簇的类别
		{
   
		case setosa:
			strcpy(Type[i],"setosa");
			pDC->SetTextColor(RGB(0,255,0));//绿色
			break;
		case versicolor:
			strcpy(Type[i],"versicolor");
			pDC->SetTextColor(RGB(0,0,255));//蓝色
			break;
		case virginica:
			strcpy(Type[i],"virginica");
			pDC->SetTextColor(RGB(255,0,0));//红色
			break;
		}
		for(j=0;j<DataSum && Point[i][j]!=-1;j++)
		{
   
			if(strcmp(A[Point[i][j]].Species,Type[i]))//若匹配不成功错误数+1
			{
   
				err++;
			}
			sum++;//i类的总数
		}
		tem.Format("%s：总数为%.f 错误率为%.3f",Type[i],sum,err/sum);
		pDC->TextOutA(800,i*50,tem);//输出各类数据
		AllSum=AllSum+sum;
		AllErr=AllErr+err;
	}
	pDC->SetTextColor(RGB(0,0,0));//黑色
	tem.Format("总数为：%.f 总错误率为：%.3f",AllSum,AllErr/AllSum);
	pDC->TextOutA(800,150,tem);
}

写在后面的话

写这个博文也不是为了什么，单纯只是为了记录自己开发完成一个小项目的经过吧，可能对于很大一部分人是班门弄斧吧，但是也期待着可以解决某些有特殊需求的人，然后有什么建议也欢迎留言，互相学习嘿嘿嘿。
----------来自笑傲菌小弟的一些话