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

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

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>

using namespace std;

//样本特征结构体
struct sample
{
 string type;
 vector<double> features;
};

//读取训练样本train.txt,训练样本格式:类型名+特征向量
void readTrain(vector<sample>& train, const string& file)
{
 ifstream fin(file.c_str()); //file是存储希望读写的文件名的string对象,fin是读的流
 if(!fin)
 {
 cerr<<"Unable to open the input file: "<<file<<endl;
 exit(1);
 }

 string line;
 double d=0.0;
 while(getline(fin,line)) //fin是读入流,getline从输入流fin读入一行到line
 {
 istringstream stream(line); //bind to stream to the line we read
 sample ts;
 stream>>ts.type;
 while(stream>>d) //read a word from line
 {
  ts.features.push_back(d); //在trains.features的末尾添加一个值为d的元素
 }
 train.push_back(ts); //在train的末尾添加一个值为ts的元素
 }
 fin.close();
}

//读取测试样本test.txt,每行都是一个特征向量
void readTest(vector<sample>& test, const string& file)
{
 ifstream fin(file.c_str());
 if(!fin)
 {
 cerr<<"Unable to open the input file: "<<file<<endl;
 exit(1);
 }

 string line;
 double d=0.0;
 while(getline(fin,line))
 {
 istringstream stream(line); //bind to stream to the line we read
 sample ts;
 while(stream>>d)
 {
  ts.features.push_back(d);
 }
 test.push_back(ts);
 }
 fin.close();
}

//输出结果,为每一个向量赋予一个类型,写入result.txt中
void writeResult(const vector<sample>& test, const string& file)
{
 ofstream fout(file.c_str());
 if(!fout)
 {
 cerr<<"Unable to write the input file: "<<endl;
 exit(1);
 }

 for(vector<sample>::size_type i=0;i!=test.size();++i)
 {
 fout << test[i].type << '\t';
 for(vector<double>::size_type j=0;j!=test[j].features.size();++j)
 {
  fout<<test[i].features[j]<<' ';
 }
 fout<<endl;
 }
}

//KNN算法的实现
void knnProcess(vector<sample>& test, const vector<sample>& train, const vector<vector<double> >& dm, unsigned int k)
{
 for (vector<sample>::size_type i = 0; i != test.size(); ++i)
 {
 multimap<double, string> dts; //保存与测试样本i距离最近的k个点

 for (vector<double>::size_type j = 0; j != dm[i].size(); ++j)
 {
  if (dts.size() < k) //把前面k个插入dts中
  {
  dts.insert(make_pair(dm[i][j], train[j].type)); //插入时会自动排序,按dts中的double排序,最小的排在最后
  }
  else
  {
  multimap<double, string>::iterator it = dts.end();
  --it;

  if (dm[i][j] < it->first) //把当前测试样本i到当前训练样本之间的欧氏距离与dts中最小距离比较,若更小就更新dts
  {
   dts.erase(it);
   dts.insert(make_pair(dm[i][j], train[j].type));
  }
  }
 }
 map<string, double> tds;
 string type = "";
 double weight = 0.0;
 //下面for循环主要是求出与测试样本i最邻近的k个样本点中大多数属于的类别,即将其作为测试样本点i的类别
 for (multimap<double, string>::const_iterator cit = 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;
 }
}

// 计算欧氏距离
double euclideanDistance(const vector<double>& v1, const vector<double>& v2)
{
 if(v1.size() != v2.size())
 {
 cerr<<"Unable to get a distance! "<<endl;
 }

 else
 {
 double distance = 0.0;

 for (vector<double>::size_type i = 0; i != v1.size(); ++i)
 {
  distance += (v1[i] - v2[i]) * (v1[i] - v2[i]);
 }
 return sqrt(distance);
 }
}

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

//封装
void xfxKnn(const string& file1, const string& file2, const string& file3, int k)
{
 vector<sample> train,test;
 readTrain(train, file1.c_str());
 readTest(test, file2.c_str());
 vector< vector<double> > dm;
 initDistanceMatrix(dm, train, test);
 knnProcess(test, train, dm, k);
 writeResult(test, file3.c_str());
}

// 测试
int main()
{
 xfxKnn("train.txt", "test.txt", "result.txt", 5);
 return 0;
}

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

(0)

相关推荐

  • 浅谈C++中的构造函数分类及调用规则

    构造函数的分类 这里简单地将C++中的构造函数分一下类,直接看下面的代码表达,说明在注释中: #include <iostream> using namespace std; class Text { public: Text() // 无参数构造函数 { m_a = 0; m_b = 0; cout << "无参数构造函数" << endl; } Text(int a) // 有参数构造函数 { m_a = a; m_b = 0; cout <

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

    K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一.该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别.KNN算法中,所选择的邻居都是已经正确分类的对象.该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别. KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关.由于KNN方法主要靠周围有限的邻

  • 基于python实现KNN分类算法

    kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性.该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别. kNN方法在类别决策时,只与极少量的相邻样本有关.由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合. 通俗简单的说,就是将这个样本进行分类,怎么分类,就是用该样本的

  • Python基于sklearn库的分类算法简单应用示例

    本文实例讲述了Python基于sklearn库的分类算法简单应用.分享给大家供大家参考,具体如下: scikit-learn已经包含在Anaconda中.也可以在官方下载源码包进行安装.本文代码里封装了如下机器学习算法,我们修改数据加载函数,即可一键测试: # coding=gbk ''' Created on 2016年6月4日 @author: bryan ''' import time from sklearn import metrics import pickle as pickle

  • 用Python实现KNN分类算法

    本文实例为大家分享了Python KNN分类算法的具体代码,供大家参考,具体内容如下 KNN分类算法应该算得上是机器学习中最简单的分类算法了,所谓KNN即为K-NearestNeighbor(K个最邻近样本节点).在进行分类之前KNN分类器会读取较多数量带有分类标签的样本数据作为分类的参照数据,当它对类别未知的样本进行分类时,会计算当前样本与所有参照样本的差异大小:该差异大小是通过数据点在样本特征的多维度空间中的距离来进行衡量的,也就是说,如果两个样本点在在其特征数据多维度空间中的距离越近,则这

  • Python KNN分类算法学习

    本文实例为大家分享了Python KNN分类算法的具体代码,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距

  • 原生python实现knn分类算法

    一.题目要求 用原生Python实现knn分类算法. 二.题目分析 数据来源:鸢尾花数据集(见附录Iris.txt) 数据集包含150个数据集,分为3类,分别是:Iris Setosa(山鸢尾).Iris Versicolour(杂色鸢尾)和Iris Virginica(维吉尼亚鸢尾).每类有50个数据,每个数据包含四个属性,分别是:Sepal.Length(花萼长度).Sepal.Width(花萼宽度).Petal.Length(花瓣长度)和Petal.Width(花瓣宽度). 将得到的数据集

  • 使用python实现kNN分类算法

    k-近邻算法是基本的机器学习算法,算法的原理非常简单: 输入样本数据后,计算输入样本和参考样本之间的距离,找出离输入样本距离最近的k个样本,找出这k个样本中出现频率最高的类标签作为输入样本的类标签,很直观也很简单,就是和参考样本集中的样本做对比.下面讲一讲用python实现kNN算法的方法,这里主要用了python中常用的numpy模块,采用的数据集是来自UCI的一个数据集,总共包含1055个样本,每个样本有41个real的属性和一个类标签,包含两类(RB和NRB).我选取800条样本作为参考样

  • python机器学习之KNN分类算法

    本文为大家分享了python机器学习之KNN分类算法,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距离,一

  • python实现KNN分类算法

    一.KNN算法简介 邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一.所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表. kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性.该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别. kNN方法在类别决策时,只与极少量的相邻样本有

  • python运用sklearn实现KNN分类算法

    KNN(K-Nearest-Neighbours Classiflication)分类算法,供大家参考,具体内容如下 最简单的分类算法,易于理解和实现 实现步骤:通过选取与该点距离最近的k个样本,在这k个样本中哪一个类别的数量多,就把k归为哪一类. 注意 该算法需要保存训练集的观察值,以此判定待分类数据属于哪一类 k需要进行自定义,一般选取k<30 距离一般用欧氏距离,即​  通过sklearn对数据使用KNN算法进行分类 代码如下: ## 导入鸢尾花数据集 iris = datasets.lo

随机推荐