kmeans.cpp

经典的K-means对非链接主题无关网页关键资源页面判定

#include "StdAfx.h"
#include "KMeans.h"
#include "help.h"
#include <cmath>
#include <fstream>
#include <ctime>
KMeans::KMeans(void)
{
}

KMeans::~KMeans(void)
{
	cout<<"hello "<<endl;
	//delete nodes;
	 
	//delete lables;
}
KMeans::KMeans(int )
{
	
	
}
void KMeans::run()
{   

	initial();
//	initialCenter(  iteration
	for(int i=0;i<100;i++)
	{
		
		//if(i%10==0)
		//	initial();
		setLable();
		sortNodes();
		checkNewCent();
	
	 
	cout<<i<<" ------------The new cent :"<<endl;
	cout<<centA.x<<" "<<centA.y<<" "<<centA.z<<endl;
	cout<<centB.x<<" "<<centB.y<<" "<<centB.z<<endl;
	checkDerect();
	}
	// system("pause");
}
void   KMeans::checkNewCent()
{
	
	double * dis=NULL;//A,* disB=NULL;
	double  minDisA=999999999;
	double  minDisB=999999999;
	int  minIndexA,minIndexB=-1;
	//if(type==TYPEA)
	//{
	dis =new double [cCnt];
		for(int  i=0;i<sizeA;i++)
		{   
		    dis [i]=0;
		   for(int j=0;j<sizeA;j++)
		   {
		     if(i!=j)
				 dis [i]+=nodes[i].distance(nodes[j]);
		   }
		  // cout<<"the disA : "<<dis [i]<<endl;
		   if(dis [i]<minDisA)
		   {
			  
			   minDisA=dis [i];
			   minIndexA=i;
		   }
		}
        
		centA=nodes[minIndexA];
		//cout<<"centA :"<<endl;
		//cout<<"min index A : "<<minIndexA<<endl;
		//cout<<"sizeA is    : "<<sizeA<<endl;
		// centA.print();
		//system("pause");
		//}

   
       // disB=new double [sizeB];
		for(int  i=sizeA;i<cCnt;i++)
		{   
		    dis [i]=0;
			for(int j=sizeA;j<cCnt;j++)
		   {
		     if(i!=j)
				 dis [i]+=nodes[i].distance(nodes[j]);
		   }
		   if(dis [i]<minDisB)
		   {
			   minDisB=dis [i];
			   minIndexB=i;
		   }
		} 
		centB=nodes[minIndexB];
		 //cout<<"centB :"<<endl;
		// centB.print();
		// cout<<"min index B : "<<minIndexB<<endl;
		// cout<<"sizeB is    : "<<sizeB<<endl;

       delete dis ;
	   // delete  disB;

}
void  KMeans::setLable()
{
	for(int i =0;i<cCnt;i++)
	{

		//cout<<"A ------ ";
		//centA.print();
		//cout<<"B ------ ";
		//centB.print();
		//cout<<"the node["<<i<<"] ";
		//nodes[i].print();
		//cout<<"the dis is  : "<<nodes[i].distance(centA)<<" "<<nodes[i].distance(centB)<<endl;
		if(nodes[i].distance(centA)<nodes[i].distance(centB))
			lables[i]=TYPEA;
		else 
			lables[i]=TYPEB;
	                                   
	}
 /* 
	 for(int i =0;i<cCnt;i++)
	 {
		 cout<<"lable -- "<<lables[i]<<" "<<nodes[i].lable;  
		  cout<<endl;
	 }
	 system("pause");
 */ 	 
}
void  KMeans::sortNodes()
{  
	int i,j=0;
	j=cCnt;
	int  flag=-1;
 
	for(i=0;i<cCnt;i++)
	{
		if(lables[i]==TYPEB) 
		{
			//flag=-1;
			for(;j>=i;j--)
				if(lables[j]==TYPEA)
				{
					swap(lables[i],lables[j]);
					swap(nodes[i],nodes[j]);
					flag=1;
					break;
				}
				if(j==i-1)
				{
					//cout<<"JJJJ : "<<i<<endl;
					break;

				}
			 
		}
	}

    sizeA=i;
	 
	 
	sizeB=cCnt-sizeA;

  
  

}
void KMeans::initialCenter(int * cent,int size)
{

}
 
void  KMeans::initialCenter(Node & NodeA,Node &NodeB)
{
  centA=NodeA;
  centB=NodeB;
  cout<<"the cent nodes :"<<endl;
  centA.print();
  centB.print();
 // system("pause");
}

void  KMeans::initialCent(int type)
{
	if(type==RANDOMCENT)
	{
	 int indexCentA, indexCentB=-1;
	 srand((int)time(NULL));

	indexCentA=rand()%cCnt;
	indexCentB=rand()%cCnt;
	 cout<<indexCentA<<" "<<indexCentB<<endl;
	initialCenter(nodes[indexCentA],nodes[indexCentB]);
	}
	if(type==HEURISTICENT)
	{
	 
	 
	initialCenter(nodes[0],nodes[1]);
	}


}
void  KMeans::initial()
{
	iteration=ITERATION;
    sizeA=0;
    sizeB=0;
	/////initial the centA and the centB
	initialCent(CENTYPPE);
}
   
void  KMeans::readInstance(char *fileName)
{  
	fstream f;
	f.open(fileName,ios::in);
	f>>cCnt;
	nodes=new Node[cCnt];
	lables=new int[cCnt];
	double ID,x,  y, z, label; 
 
	for(int i=0;i<cCnt;i++)
	{
		 f>>ID;
		 f>>z;
		 f>>x;
		 f>>y;
		 f>>label;
		 
 		 nodes[i].setValue(ID,z,x,y,label);
		// cout<<label<<" "<<endl;
		 lables[i]=-1;
	}


	 
}
	//void  
void  KMeans::checkDerect()
{
	int  countA=0;
	int  countB=0;
    double ratioA=-1;
	double ratioB=-1;
	int  tatalA=0;
	int  tatalB=0;
	int  count_lableA=0;
	int  count_lableB=0;

   for(int i=0;i<cCnt;i++)
   {
	   
	   if(nodes[i].lable==TYPEA  )
		   tatalA++;
	    if(nodes[i].lable==TYPEB  )
		   tatalB++;
	   if(nodes[i].lable==TYPEA &&lables[i]==TYPEA)
		   countA++;
	    if(nodes[i].lable==TYPEB &&lables[i]==TYPEB)
		   countB++;

	    if(lables[i]==TYPEA)
			count_lableA++;
	    if(lables[i]==TYPEB)
			count_lableB++;
   }
   cout<<"  A :-- "<< countA <<"--tatal A : --"<<tatalA<<" the labled A : "<<count_lableA<<endl;
   cout<<"  B :-- "<< countB <<"--tatal B : --"<<tatalB<<" the labled B : "<<count_lableB<<endl;
   cout<<"ratio A :-- "<<double(countA)/tatalA<<" ---- "<<double(countA)/count_lableA<<endl;
   cout<<"ratio B :-- "<<double(countB)/tatalB<<" ---- "<<double(countB)/count_lableB<<endl;
}