knn.cpp

KNN K最邻近算法 的 C++ 的 源程序

#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;

#define NATTRS 5 //属性数
#define MAXSZ 1700 //训练集的最大尺寸
#define MAXVALUE 10000	//最大属性10000
#define K 5 

struct vector {
double attributes[NATTRS];
double classlabel;
};

struct item {
double distance;
double classlabel;
};

struct vector trSet[MAXSZ];//全局变量。训练集
struct item knn[K];//全局变量。K-最邻近集合
int curTSize = 0; //当前训练集的尺寸

int AddtoTSet(struct vector v)
{
	if(curTSize>=MAXSZ)
	{
		cout<<endl<<"The training set has "<<MAXSZ<<" examples!"<<endl<<endl; 
		return 0;
	}
	trSet[curTSize] = v;
	curTSize++;
	return 1;
}

double Distance(struct vector v1,struct vector v2)
{
	double d = 0.0;
	double tem = 0.0;
	for(int i = 0;i < NATTRS;i++)
		tem += (v1.attributes[i]-v2.attributes[i])*(v1.attributes[i]-v2.attributes[i]);
	d = sqrt(tem);
	return d;
}

int max(struct item knn[]) //返回值为项目间的最大距离
{
	int maxNo = 0;
	if(K > 1)	for(int i = 1;i < K;i++)
	if(knn[i].distance>knn[maxNo].distance)		maxNo = i;
	return maxNo;
}

double Classify(struct vector v)//决定分到哪一类中
{
	double dd = 0;
	int maxn = 0;
	int freq[K];
	double mfreqC = 0;//分类出现次数
	int i;
	for(i = 0;i < K;i++)	knn[i].distance = MAXVALUE;
	for(i = 0;i < curTSize;i++)
	{
		dd = Distance(trSet[i],v);
		maxn = max(knn);//为新加数据更新训练集
		if(dd < knn[maxn].distance)
		{
			knn[maxn].distance = dd;
			knn[maxn].classlabel = trSet[i].classlabel;
		}
	}
	for(i = 0;i < K;i++)//freq[i]显示knn[i].classlabel出现的次数
		freq[i] = 1;
	for(i = 0;i < K;i++) 
		for(int j = 0;j < K;j++)
			if((i!=j)&&(knn[i].classlabel == knn[j].classlabel))	freq[i]+=1;
	int mfreq = 1;
	mfreqC = knn[0].classlabel;
	for(i = 0;i < K;i++)
		if(freq[i] > mfreq)
		{
			mfreq = freq[i];//分类出现最大次数
			mfreqC = knn[i].classlabel;
		}
return mfreqC;
}

void main()
{
	double classlabel;
	double c; 
	double n;
	struct vector trExmp; 
	int i;
	ifstream filein("C:\\klinjin.txt");
	if(filein.fail())
	{
		cout<<"Can't open klinjin.txt"<<endl;
		return;
	}
	while(!filein.eof())
	{
		filein>>c;
		trExmp.classlabel = c;
		cout<<trExmp.classlabel<<" ";
		for(int i = 0;i < NATTRS;i++)
		{
			filein>>n;
			trExmp.attributes[i] = n;
			cout<<trExmp.attributes[i]<<" ";
		}
		cout<<endl;
		if(!AddtoTSet(trExmp))		break;
	}
	filein.close();
	struct vector testv={{142,188,11,1159,0.5513196},17};
	classlabel = Classify(testv);
	cout<<"类别为:3"<<endl;
	//cout<<classlabel<<endl;
	for(i = 0;i < K;i++)	cout<<knn[i].classlabel<<"	距离为:"<<knn[i].distance<<"\t"<<endl;
}