C++基于特征向量的KNN分类算法

2023-09-02 09:50:04 63

K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

#include"stdafx.h"
#include
#include
#include
#include
#include
#include
#include
#include

usingnamespacestd;

//样本特征结构体
structsample
{
stringtype;
vectorfeatures;
};

//读取训练样本train.txt，训练样本格式：类型名+特征向量
voidreadTrain(vector&train,conststring&file)
{
ifstreamfin(file.c_str());//file是存储希望读写的文件名的string对象，fin是读的流
if(!fin)
{
cerr<<"Unabletoopentheinputfile:"<>ts.type;
while(stream>>d)//readawordfromline
{
ts.features.push_back(d);//在trains.features的末尾添加一个值为d的元素
}
train.push_back(ts);//在train的末尾添加一个值为ts的元素
}
fin.close();
}

//读取测试样本test.txt，每行都是一个特征向量
voidreadTest(vector&test,conststring&file)
{
ifstreamfin(file.c_str());
if(!fin)
{
cerr<<"Unabletoopentheinputfile:"<>d)
{
ts.features.push_back(d);
}
test.push_back(ts);
}
fin.close();
}

//输出结果，为每一个向量赋予一个类型，写入result.txt中
voidwriteResult(constvector&test,conststring&file)
{
ofstreamfout(file.c_str());
if(!fout)
{
cerr<<"Unabletowritetheinputfile:"<::size_typei=0;i!=test.size();++i)
{
fout<::size_typej=0;j!=test[j].features.size();++j)
{
fout<&test,constvector&train,constvector>&dm,unsignedintk)
{
for(vector::size_typei=0;i!=test.size();++i)
{
multimapdts;//保存与测试样本i距离最近的k个点

for(vector::size_typej=0;j!=dm[i].size();++j)
{
if(dts.size()::iteratorit=dts.end();
--it;

if(dm[i][j]first)//把当前测试样本i到当前训练样本之间的欧氏距离与dts中最小距离比较，若更小就更新dts
{
dts.erase(it);
dts.insert(make_pair(dm[i][j],train[j].type));
}
}
}
maptds;
stringtype="";
doubleweight=0.0;
//下面for循环主要是求出与测试样本i最邻近的k个样本点中大多数属于的类别，即将其作为测试样本点i的类别
for(multimap::const_iteratorcit=dts.begin();cit!=dts.end();++cit)
{
//不考虑权重的情况，在k个样例中只要出现就加1
//++tds[cit->second];

//这里是考虑距离与权重的关系，距离越大权重越小
tds[cit->second]+=1.0/cit->first;
if(tds[cit->second]>weight)
{
weight=tds[cit->second];
type=cit->second;//保存一下类别
}
}
test[i].type=type;
}
}

//计算欧氏距离
doubleeuclideanDistance(constvector&v1,constvector&v2)
{
if(v1.size()!=v2.size())
{
cerr<<"Unabletogetadistance!"<::size_typei=0;i!=v1.size();++i)
{
distance+=(v1[i]-v2[i])*(v1[i]-v2[i]);
}
returnsqrt(distance);
}
}

/*初始化距离矩阵，该矩阵是根据训练样本和测试样本而得，
矩阵的行数为测试样本的数目，列数为训练样本的数目，
每一行为一个测试样本到各个训练样本之间的欧式距离组成的数组*/
voidinitDistanceMatrix(vector>&dm,constvector&train,constvector&test)
{
for(vector::size_typei=0;i!=test.size();++i)
{
vectorvd;
for(vector::size_typej=0;j!=train.size();++j)
{
vd.push_back(euclideanDistance(test[i].features,train[j].features));
}
dm.push_back(vd);
}
}

//封装
voidxfxKnn(conststring&file1,conststring&file2,conststring&file3,intk)
{
vectortrain,test;
readTrain(train,file1.c_str());
readTest(test,file2.c_str());
vector>dm;
initDistanceMatrix(dm,train,test);
knnProcess(test,train,dm,k);
writeResult(test,file3.c_str());
}

//测试
intmain()
{
xfxKnn("train.txt","test.txt","result.txt",5);
return0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

C++基于特征向量的KNN分类算法

热门推荐

随机推荐