alo1.cpp

模式识别经典算法

#include<iostream>
#include<cmath>
#include"Alo1.h"
using namespace std;


//int Init(int &K,int &num_N,double &Aver_S,double &Distance,int &L,int &I,int &Nc)
int Init(int K,int num_N,double Aver_S,double Distance,int L,int I,int Nc)
{
	cout <<"请输入预期的聚类中心数K:   ";
	cin >> K;
	cout <<"请输入每一聚类域的阈值num_N:                  ";
	cin >> num_N;    
	cout << "一个聚类域中的样本距离的标准差Aver_S:        ";
	cin >> Aver_S;
	cout <<"两个聚类域的聚类中心间的最小距离Distance:     ";
	cin >> Distance;
	cout <<"每一次迭代运算中可以合并的聚类中心的最多对数L:";
	cin >> L;
	cout <<"迭代运算的次数序号I:      ";
	cin >> I;
	cout <<"请预选Nc个聚类中心Nc:     ";
	cin >> Nc;
    cout <<"依次输入聚类中心的坐标(x,y):                   " << endl;

	for(int i = 1; i <= Nc;i++)
	{
		cin >> Kr[i].x >> Kr[i].y;
		Kr[i].flag = i;
		cout << Kr[i].x <<" , " << Kr[i].y <<" , " << Kr[i].flag << endl;
	}
	
	return 0;
}

double distance2(Point x,Point y)
{
	double d = 0.0;
	d = sqrt((x.x - y.x)*(x.x - y.x)+(x.y - y.y)*(x.y - y.y));

	return d;
}

int Distribute(int N)
{
	for(int k = 0; k < 21; k++)
		Rec[k] = 0;

	for(int i = 1;i <= N;i++)
	{
		Rec[Min_Distan_Sequence(Nc,pt[i])]++;	 
	}
     
	//测试Rec的值
	cout <<"每一个分类的样本数目:  ";
	for(int kk = 1; kk <= Nc; kk++)
		cout << kk <<"   : " <<Rec[kk] << endl;
	//

    bool flg = 0;
	int nCount = 0;
	for(int j = 1;j <= Nc;j++)
	{
		if(Rec[j] < num_N)
		{
			Kr[j].x = Max;
			Kr[j].y = Max;
			nCount++;
			flg = 1;
		}
	}	

	if(flg == 1)
	{
		cout << "需要合并  " << endl;
		int n = 0;
		int m = 1;
		
		for(m = 1;m <= Nc; m++)
		{
			if(Kr[m].x < Max && Kr[m].y < Max)
			{
				n++;
				Kr1[n].x = Kr[m].x;
				Kr1[n].y = Kr[m].y;
			}
		}
		
		Nc -= nCount;
		for(m = 1;m <= Nc; m++)
		{
			Kr[m].x = Kr1[m].x;
			Kr[m].y = Kr1[m].y;
		}

		for(int k = 0; k < 21; k++)
			Rec[k] = 0;
		
		for(int i = 1;i <= N;i++)
		{
			Rec[Min_Distan_Sequence(Nc,pt[i])]++;
		}
	}	
	
	return 0;
}

int Min_Distan_Sequence(int Number,Point x)
//int Min_Distan_Sequence(int Number,Point &x)
{
	int i;
    double d = 100000;
	int j;
	for(i = 0;i < Number;i++)
	{
		Kr[i + 1].flag = i + 1;
		cout << Kr[i + 1].x <<" , " << Kr[i + 1].y <<" , " << Kr[i + 1].flag << 

endl;
		if(d > distance2(x,Kr[i + 1]))
		{
			d = distance2(x,Kr[i + 1]);
			//x.flag = i + 1;
			j = i + 1;
		}
	}

	x.flag = j;

	return Kr[j].flag;
}

int Average(int i,int j)    //第四步
{
	int m = 0,n = 0;
	int temp = 0;
	
	for(n = 1;n <= j;n++)
	{
		Point x = {0.0,0.0,0};
		temp = 0;
		for (m = 1; m <= i;m++)
		{
			if(pt[m].flag == n)
			{
				x.x += pt[m].x;
				x.y += pt[m].y;
				temp++;
			}
		}
		Kr[n].x = x.x / temp;
		Kr[n].y = x.y / temp;
		Kr[n].flag = n;	
		
		//测试修改后的聚类中心
		cout << "输出修改后的聚类中心:    ";
		cout << Kr[n].x <<"  " << Kr[n].y <<endl;
	}

	//第五步
	m = 0,n = 0;
	double x = 0.0;

	for(n = 1;n <= j;n++)
	{
		x = 0.0;
		temp = 0;
		for (m = 1; m <= i;m++)
		{
			if(pt[m].flag == n)
			{
				x += distance2(pt[m],Kr[n]);
				temp++;
			}
		}
		x /= temp;		
		M[n] = x;
		cout << "输出每一个分类的平均距离   ";
		cout << M[n]<< endl;
	}
	////

	x = 0.0;
	m = 0,n = 0;
	for(m = 0;m < j;m++)
	{
		x += M[m + 1]*Rec[m + 1];
	}

	M[0] = x / i;    //存入数组M的首元素M[0]
	//测试总的平均距离
	cout <<"测试总的平均距离:  "<< (x/i) << endl;
	//
	return 0;
}

double Max_Value(Point x)
{
	double value;
	value = (x.x > x.y ) ? x.x :x.y;
	return value;
}

int Split(int i,int j)
{
	int m = 0,n = 0,temp = 0;
	double x = 0.0;
	double y = 0.0;
	for( m = 1; m <= j;m++)
	{
		x = 0.0;
		y = 0.0;
		temp = 0;
		for(n = 1;n <= i;n++)
		{
			if(pt[n].flag == m)
			{
				temp++;
				x += (pt[n].x - Kr[m].x)*(pt[n].x - Kr[m].x);
			    y += (pt[n].y - Kr[m].y)*(pt[n].y - Kr[m].y);
			}
		}
		Meen[m].x = sqrt(x / temp);
		Meen[m].y = sqrt(y / temp);
		Meen_Max[m] = Max_Value(Meen[m]);

		//测试语句
		cout <<"输出第八步计算的标准向量差:   " << Meen[m].x <<"  ,  " <<Meen[m].y << endl;
		cout << "输出最大维向量:  " << Meen_Max[m] << endl;
		//
	}
   
	return 0;
}

int Dismense(int i,int N)
{
	int m = 1;
	int k = 0;
	for(m;m <= N;m++)
	{
		if(pt[m].flag == i)
			k++;
	}
	return k;
}

int Incorporate(int Nc,int N)
{
	int i = 1,j = 1,k = 0;
	for(i = 1; i < Nc; i++)
	{
		for(j = i + 1; j <= Nc; j++)
		{
			k++;
			Distance_Center[k].x = distance2(Kr[i],Kr[j]);
			Distance_Center[k].i = i;
			Distance_Center[k].j = j;
		}
	}

	//快速排序
	for(i = 2; i <= Nc * (Nc - 1) / 2;i++)
	{
		Distance_Center[0].x = Distance_Center[i].x;
		Distance_Center[0].i = Distance_Center[i].i;
		Distance_Center[0].j = Distance_Center[i].j;

		int low = 1;
		int high = i - 1;
		int m = 0;
		while(low <= high)
		{
			m = (low + high) / 2;
			if(Distance_Center[0].x < Distance_Center[m].x)
				high = m - 1;
			else 
				low = m + 1;
		}
		for(int j = i - 1; j >= high + 1;--j)
		{
			Distance_Center[j + 1].x =Distance_Center[j].x;
			Distance_Center[j + 1].i =Distance_Center[j].i;
			Distance_Center[j + 1].j =Distance_Center[j].j;
		}
		Distance_Center[high + 1].x =Distance_Center[0].x;
		Distance_Center[high + 1].i =Distance_Center[0].i;
		Distance_Center[high + 1].j =Distance_Center[0].j;
	} //for快速排序

	if(Distance_Center[1].x < Distance)
	{
		int N1 = Dismense(Distance_Center[1].i,N);
		int N2 = Dismense(Distance_Center[1].j,N);
		Point x;
		x.x = (N1 * Kr[Distance_Center[1].i].x + N2 * Kr[Distance_Center[1].j].x) / (N1 + N2);
        x.y = (N1 * Kr[Distance_Center[1].i].y + N2 * Kr[Distance_Center[1].j].y) / (N1 + N2);
		/*		
        Kr[Distance_Center[1].i].x = x.x;
		Kr[Distance_Center[1].i].y = x.y;
		Kr[Distance_Center[1].j].x = Max;
		Kr[Distance_Center[1].j].y = Max;
		*/

		k = ((Distance_Center[1].i > Distance_Center[1].j) ? Distance_Center[1].j:Distance_Center[1].i);
		Kr[k].x = x.x;
		Kr[k].y = x.y;
		Nc --;
	}
	else 
	{
		cout <<"输出最小的距离:   ";
		cout << Distance_Center[1].x << endl;

		cout <<"所有点的聚类情况详单:  "<< endl;
		for(i = 1; i <= N ;i++)
		{
			cout << pt[i].x <<" , " << pt[i].y <<" , "<< pt[i].flag << endl;
		}

		cout <<"所有的聚类中心:  " << endl;
		for(i = 1;i <= Nc; i++)
		{
			cout << Kr[i].x <<" , " << Kr[i].y << " , " << Kr[i].flag << endl;
		}
	}
	
	return 0;
}