pr_isodata.cpp

模式识别中的ISODATA算法 自己编写的

#include "PR_ISODATA.h"
#include <algorithm>

 #include   <stdio.h>   

using std::cin;
using std::endl;
using std::string;

PR_ISODATA::PR_ISODATA(int m,int n)
{

}
PR_ISODATA::PR_ISODATA(std::ifstream &fin):K(2),Nc(1),SitaN(1),SitaS(1),Sitac(4),L(2),I(8),k(0.5),flag_split(false)
{
	int m(0),n(0);
	
	if(!fin)return;
	
	string str;

	while(!fin.eof()) 
	{ 
		getline(fin,str);//get the number of the samples

		m++;

		PR_unit* unit = new PR_unit();
		for(int i=0;i<str.size();i++)
		{
			string t_str;
			while(str[i] != ' '&& str[i] != '\n' && i<str.size())
			{
				t_str.push_back(str[i]);
				i++;
			}
			unit->unit.push_back(atof(t_str.c_str()));
			if(1 == m)
			{
				n++;
			}
		}
		samples.push_back(unit);
	}
	num_samples = m;
	num_vector = n;
	
	/*PR_Cluster *t_cluster = new PR_Cluster(num_vector);
	AddSampleToCluster(0,t_cluster);
	t_cluster->CalcCenter();
	clusters.push_back(t_cluster);*/

	clusters.clear();
	if(Nc > samples.size()) Nc = samples.size();
	for(int i=0;i<Nc;i++)
	{
		PR_Cluster *t_cluster = new PR_Cluster(num_vector);
		AddSampleToCluster(i,t_cluster);
		t_cluster->CalcCenter();
		clusters.push_back(t_cluster);
	}

}
void PR_ISODATA::PrintClusterCenter()			//print the center of the clusters
{
	for(int i=0;i<clusters.size();i++)
	{
		cout<<"clustercenter"<<i<<":\t";
		clusters[i]->PrintCenter();
		cout<<endl;
	}

}
void PR_ISODATA::PrintSamples()
{
	cout<<"Samples:"<<endl;
	for(int i=0;i<samples.size();i++)
	{
		cout<<i<<":\t";
		samples[i]->Print();
		cout<<endl;
	}
}
void PR_ISODATA::PrintClusters()				//print the result
{
	for(int i=0;i<clusters.size();i++)
	{
		cout<<"cluster"<<i<<":\t";
		clusters[i]->Print();
		cout<<endl;
	}
}
void PR_ISODATA::PrintDelta()
{
	for(int i=0;i<clusters.size();i++)
	{
		cout<<"delta"<<i<<":\t";
		clusters[i]->PrintDelta();
		cout<<endl;
	}
}
void PR_ISODATA::PrintDeltaMax()
{
	for(int i=0;i<clusters.size();i++)
	{
		cout<<"DeltaMax"<<":\t";
		clusters[i]->PrintDeltaMax();
	}	
	cout<<endl;
}
void PR_ISODATA::PrintD()
{
	cout<<"D"<<":\t";
	for(int i=0;i<clusters.size();i++)
	{
		clusters[i]->PrintD();
	}
	cout<<endl;

	cout<<"the whole D:"<<D<<endl;
}
void  PR_ISODATA::PrintDij()
{
	cout<<"Dij"<<endl;
	int n = 0;
	for(int i=0;i<clusters.size()-1;i++)
	{
		for(int j=i+1;j<clusters.size();j++)
		{
			cout<<Dij[n]->d<<"\t";
			n++;
		}
		cout<<endl;
	}
}
void PR_ISODATA::SetPrameters()
{
	int key = 0;
	while(key != 9)
	{
		PrintParameters();
		cin>>key;
		switch(key)
		{
		case 1:
			cout<<"K = ";
			cin >> K;
			break;
		case 2:
			cout<<"Nc = ";
			cin >> Nc;

			//initial again
			clusters.clear();
			if(Nc > samples.size()) Nc = samples.size();
			for(int i=0;i<Nc;i++)
			{
				PR_Cluster *t_cluster = new PR_Cluster(num_vector);
				AddSampleToCluster(i,t_cluster);
				t_cluster->CalcCenter();
				clusters.push_back(t_cluster);
			}

			break;
		case 3:
			cout<<"SitaN = ";
			cin >> SitaN;
			break;
		case 4:
			cout<<"SitaS = ";
			cin >> SitaS;
			break;
		case 5:
			cout<<"Sitac = ";
			cin >> Sitac;
			break;
		case 6:
			cout<<"L = ";
			cin >> L;
			break;
		case 7:
			cout<<"I = ";
			cin >> I;
			break;
		case 8:
			cout<<"k = ";
			cin >> k;
			break;
		case 9:
			break;
		default:break;
		}
	}
	

}
void PR_ISODATA::PrintParameters()
{
	system("cls");
	cout<<"///////////////////////////////////////////////////////////////"<<endl;
	cout<<"//\tPlease choose the Prameter number to change:pless 9 to exit"<<endl;
	cout<<"//\t1\tK:\t"<<K<<endl;
	cout<<"//\t2\tNc:\t"<<Nc<<endl;
	cout<<"//\t3\tSitaN:\t"<<SitaN<<endl;
	cout<<"//\t4\tSitaS:\t"<<SitaS<<endl;
	cout<<"//\t5\tSitac:\t"<<Sitac<<endl;
	cout<<"//\t6\tL:\t"<<L<<endl;
	cout<<"//\t7\tI:\t"<<I<<endl;
	cout<<"//\t8\tk:\t"<<k<<endl;
	cout<<"//\t9\texit"<<endl;
	cout<<"////////////////////////////////////////////////////////////////"<<endl;
}
void PR_ISODATA::AddSampleToCluster(int i,PR_Cluster* t_cluster)
{
	t_cluster->samples.push_back(samples[i]);
	t_cluster->serial.push_back(i);
	//t_cluster.CalcCenter();
}
/*
void PR_ISODATA::DeleteCluster(int i)
{
	clusters.erase(clusters.begin() + m);
}
void PR_ISODATA::AddCluster(PR_Cluster* t_cluster)
{

}*/
void PR_ISODATA::NearnestCluster()				//sort the samples to the nearest cluster
{
	for(int i = 0;i<clusters.size();i++)
	{
		clusters[i]->samples.clear();
		clusters[i]->serial.clear();
	}
	
	for(int i=0;i<samples.size();i++)
	{
		int min_num = 0;
		double min_dis = distance(samples[i],clusters[0]->center);

		for(int j = 0;j<clusters.size();j++)
		{
			double dd = distance(samples[i],clusters[j]->center);
			if( dd <= min_dis)
			{
				min_num = j;
				min_dis = dd;
			}
		}
		AddSampleToCluster(i,clusters[min_num]);
	}

	UpdateClusterCenter();

	//PrintClusters();
	//PrintClusterCenter();
}
void PR_ISODATA::CancelaCluster()				//if the number of samples in a cluster is samller than SitaC ,then cancel the cluster
{
	bool flag_cancel = true;
	while( flag_cancel )
	{
		flag_cancel = false;
		for(int i=0;i<clusters.size();i++)
		{
			if( clusters[i]->samples.size() < SitaN)
			{
				clusters.erase( clusters.begin() + i );
				Nc--;
				flag_cancel = true;
			}
		}
		if(flag_cancel)
		{
			NearnestCluster();
		}
	}
}
void PR_ISODATA::UpdateClusterCenter()			//update the center of clusters
{
	for(int i=0;i<clusters.size();i++)
	{
		clusters[i]->CalcCenter();
	}
}
void PR_ISODATA::CalcAverDis()					//calculate the average distance in each cluster
{
	for(int i=0;i<clusters.size();i++)
	{
		clusters[i]->CalcAverDis();
	}
}
void PR_ISODATA::CalcWholeAverDis()
{
	D = 0;
	for(int i=0;i<clusters.size();i++)
	{
		D += clusters[i]->samples.size() * clusters[i]->D;
	}
	D = D/samples.size();
}
void PR_ISODATA::CalcSDVector()
{
	for(int i=0;i<clusters.size();i++)
	{
		clusters[i]->CalcSDVector();
	}
}
void PR_ISODATA::CalcMaxComponent()
{
	for(int i=0;i<clusters.size();i++)
	{
		clusters[i]->CalcMaxComponent();
	}
}
void PR_ISODATA::CalcWholeClusterDis()
{
	Dij.clear();
	for(int i=0;i<clusters.size()-1;i++)
	{
		for(int j=i+1;j<clusters.size();j++)
		{
			DClusters *dd = new DClusters;
			dd->d = distance(clusters[i]->center,clusters[j]->center);
			dd->i = i;
			dd->j = j;
			Dij.push_back(dd);
		}
	}
}
bool DijGreater( DClusters *d1,DClusters *d2)
{
	return (d1->d) < (d2->d);
}
void PR_ISODATA::SortDij()
{
	sort(Dij.begin(),Dij.end(),DijGreater);
}
void PR_ISODATA::SplitaCluster()
{
	//PrintClusters();
	//PrintClusterCenter();
	//PrintD();
	//PrintDelta();
	//PrintDeltaMax();
	vector<int> t_int;
	flag_split = false;

	for(int i=0;i<clusters.size();i++)
	{
		if( clusters[i]->deltamax > SitaS)
		{
			if( (Nc <= K/2) || ( clusters[i]->D > D && clusters[i]->samples.size() > 2*(SitaN + 1) ) )
			{
				t_int.push_back(i);
			}
		}
	}
	
	if(t_int.size()>0)flag_split = true;

	for(int i=0;i<t_int.size();i++)
	{
		PR_Cluster* t_cluster1 = new PR_Cluster(num_vector);
		PR_Cluster* t_cluster2 = new PR_Cluster(num_vector);

		t_cluster1->center->unit = clusters[i]->center->unit;
		t_cluster2->center->unit = clusters[i]->center->unit;

		t_cluster1->center->unit[clusters[i]->num_max] += k * clusters[i]->deltamax;
		t_cluster2->center->unit[clusters[i]->num_max] -= k * clusters[i]->deltamax;

		clusters.erase(clusters.begin()+i);

		clusters.push_back(t_cluster1);
		clusters.push_back(t_cluster2);	

		Nc++;
		
		//cout<<Nc<<endl;
	}
}
void PR_ISODATA::Split()
{
	CalcSDVector();									//the 8th step
	CalcMaxComponent();								//the 9th step
	PrintDelta();
	PrintDeltaMax();
	SplitaCluster();								//the 10th step
}
void PR_ISODATA::Unite2cluster()
{
	vector<int> t_int;
	vector<int>::iterator result1,result2;
	
	int n=0;
	for(int i=0;i < Dij.size();i++)
	{
		if(Dij[i]->d < Sitac)
		{
			result1 = find(t_int.begin(),t_int.end(),Dij[i]->i);
			if( result1 != t_int.end() )continue;

			result2 = find(t_int.begin(),t_int.end(),Dij[i]->j); 
			if( result2 != t_int.end() )continue;
			
			t_int.push_back(Dij[i]->i);
			t_int.push_back(Dij[i]->j);
			//cout<<"the last step"<<endl;

			n++;
			if(n >= L) break;
		}
	}

	for(int i=0;i < t_int.size();i++)
	{
		cout<<t_int[i]<<"  ";
	}
	cout<<endl;

	for(int i=0;i < t_int.size();i++)
	{
		if(i%2 == 0)
		{
			int m = t_int[i];
			int n = t_int[i+1];

			PR_Cluster* t_cluster = new PR_Cluster(num_vector);
			
			*(t_cluster->center) = (*(clusters[m]->center) * clusters[m]->samples.size() +*(clusters[n]->center) * clusters[n]->samples.size())
								/(clusters[m]->samples.size() + clusters[n]->samples.size());

			clusters.erase(clusters.begin() + m);
			clusters.erase(clusters.begin() + n);

			clusters.push_back(t_cluster);
		}
	}

}
void PR_ISODATA::Unite()
{
	//PrintClusters();
	//PrintClusterCenter();
	CalcWholeClusterDis();							//the 11th step
	PrintDij();
	SortDij();										//the 12th step
	PrintDij();
	//PrintClusters();
	//PrintClusterCenter();
	Unite2cluster();								//the 13th step
	//PrintClusterCenter();
}
void PR_ISODATA::Rend()								//start the algorithm
{
	system("cls");  
	PrintSamples();
	char ch;

	for(int i=1;i <= I;i++)
	{
		if(i != 1)system("cls");

		cout<<"the "<<i<<"th iterator"<<endl;
		
		PrintClusterCenter();
		NearnestCluster();							//the 2th step
		PrintClusters();
		PrintClusterCenter();
		
		CancelaCluster();							//the 3th step
		//UpdateClusterCenter();						//the 4th step
		CalcAverDis();								//the 5th step
		CalcWholeAverDis();							//the 6th step
		PrintD();
		

		if(i == I)	//the last iteration time
		{
			Sitac = 0;
			Unite();
			break;
		}
		else if( Nc <= K/2)
		{
			Split();
			if(!flag_split)Unite();
		}
		else if(i%2 == 0 || Nc >= 2*K)
		{
			Unite();
		}
		else
		{
			Split();
			if(!flag_split)Unite();
		}

		//Unite();
		//PrintClusters();

		cout<<"Would you like to change the parameters:Y or N"<<endl;
		cin>>ch;
		if(ch == 'Y' || ch == 'y')
		{
			SetPrameters();
		}
	}
	system("cls");
	PrintClusters();
}