K近邻算法(KNN)的C++实现

本文不对KNN算法做过多的理论上的解释，主要是针对问题，进行算法的设计和代码的注解。

KNN算法：

优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。

适用数据范围：数值型和标称性。

工作原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据及中前ｋ个最相似的数据，这就是k-近邻算法中k的出处，通常k选择不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。K-近邻算法的一般流程：

（1）收集数据：可以使用任何方法

（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式（3）分析数据：可以使用任何方法

（4）训练算法：此步骤不适用k-邻近算法

（5）测试算法：计算错误率

（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

问题一：现在我们假设一个场景，就是要为左边上的点进行分类，如下图所示：

上图一共12个左边点，每个坐标点都有相应的坐标(x,y)以及它所属的类别A/B，那么现在需要做的就是给定一个点坐标(x1,y1)，判断它属于的类别A或者B。

所有的坐标点在data.txt文件中：

0.0 1.1 A

1.0 1.0 A

2.0 1.0 B

0.5 0.5 A

2.5 0.5 B

0.0 0.0 A

1.0 0.0 A

2.0 0.0 B

3.0 0.0 B

0.0 -1.0 A

1.0 -1.0 A

2.0 -1.0 B

step1：通过类的默认构造函数去初始化训练数据集dataSet和测试数据testData。

step2：用get_distance()来计算测试数据testData和每一个训练数据dataSet[index]的距离，用map_index_dis来保存键值对

,其中index代表第几个训练数据，distance代表第index个训练数据和测试数据的距离。

step3：将map_index_dis按照value值（即distance值）从小到大的顺序排序，然后取前k个最小的value值，用map_label_freq来记录每一个类标签出现的频率。

step4：遍历map_label_freq中的value值，返回value最大的那个key 值，就是测试数据属于的类。

看一下代码KNN_https://www.doczj.com/doc/5815694863.html,：

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef char tLabel;

typedef double tData;

typedef pair PAIR;

constintcolLen = 2;

constintrowLen = 12;

ifstream fin;

ofstreamfout;

class KNN

{

private:

tDatadataSet[rowLen][colLen];

tLabel labels[rowLen];

tDatatestData[colLen];

int k;

mapmap_index_dis;

mapmap_label_freq;

doubleget_distance(tData *d1,tData *d2);

public:

KNN(int k);

voidget_all_distance();

voidget_max_freq_label();

structCmpByValue

{

bool operator() (const PAIR&lhs,const PAIR&rhs)

{

returnlhs.second

}

};

};

KNN::KNN(int k)

{

this->k = k;

fin.open("data.txt");

if(!fin)

{

cout<<"can not open the file data.txt"<

exit(1);

}

/* input the dataSet */

for(inti=0;i

{

for(int j=0;j

{

fin>>dataSet[i][j];

}

fin>>labels[i];

}

cout<<"please input the test data :"<

/* inuput the test data */

for(inti=0;i

cin>>testData[i];

}

/*

* calculate the distance between test data and dataSet[i]

*/

double KNN:: get_distance(tData *d1,tData *d2)

{

double sum = 0;

for(inti=0;i

{

sum += pow( (d1[i]-d2[i]) , 2 );

}

// cout<<"the sum is = "<

returnsqrt(sum);

}

/*

* calculate all the distance between test data and each training data

*/

void KNN:: get_all_distance()

{

double distance;

inti;

for(i=0;i

{

distance = get_distance(dataSet[i],testData);

// =>

map_index_dis[i] = distance;

}

//traverse the map to print the index and distance

map::const_iterator it = map_index_dis.begin();

while(it!=map_index_dis.end())

{

cout<<"index = "<first<<" distance = "<second<

it++;

}

}

/*

* check which label the test data belongs to to classify the test data

*/

void KNN:: get_max_freq_label()

{

//transform the map_index_dis to vec_index_dis

vectorvec_index_dis( map_index_dis.begin(),map_index_dis.end() );

//sort the vec_index_dis by distance from low to high to get the nearest data

sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue());

for(inti=0;i

{

cout<<"the index = "<

"<

//calculate the count of each label

map_label_freq[ labels[ vec_index_dis[i].first ] ]++;

}

map::const_iteratormap_it = map_label_freq.begin();

tLabel label;

intmax_freq = 0;

//find the most frequent label

while(map_it != map_label_freq.end() )

{

if(map_it->second >max_freq )

{

max_freq = map_it->second;

label = map_it->first;

}

map_it++;

}

cout<<"The test data belongs to the "<

}

int main()

{

int k ;

cout<<"please input the k value : "<

cin>>k;

KNN knn(k);

knn.get_all_distance();

knn.get_max_freq_label();

system("pause");

return 0;

}

我们来测试一下这个分类器(k=5)：testData(5.0,5.0):

testData(-5.0,-5.0):

testData(1.6,0.5):

分类结果的正确性可以通过坐标系来判断，可以看出结果都是正确的。问题二：使用k-近邻算法改进约会网站的匹配效果

情景如下：我的朋友海伦一直使用在线约会网站寻找合适自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：

>不喜欢的人

>魅力一般的人

>极具魅力的人

尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会哪些魅力一般的人，而周末

则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好的帮助她将匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。海伦已经收集数据一段时间。她把这些数据存放在文本文件datingTestSet.txt（文件链接：https://www.doczj.com/doc/5815694863.html,/QUL6SxtiJFPfN）中，每个样本占据一行，总共有1000行。海伦的样本主要包含3中特征：>每年获得的飞行常客里程数

>玩视频游戏所耗时间的百分比

>每周消费的冰淇淋公升数

数据预处理：归一化数据

我们可以看到，每年获取的飞行常客里程数对于计算结果的影响将远大于其他两个特征。而产生这种现象的唯一原因，仅仅是因为飞行常客书远大于其他特征值。但是这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客数不应该如此严重地影响到计算结果。

处理这种不同取值范围的特征值时，我们通常采用的方法是数值归一化，如将取值范围处理为0到1或者-1到1之间。

公式为：newValue = (oldValue - min) / (max - min)

其中min和max分别是数据集中的最小特征值和最大特征值。我们增

加一个auto_norm_data函数来归一化数据。

同事还要设计一个get_error_rate来计算分类的错误率，选总体数据

的10%作为测试数据，90%作为训练数据，当然也可以自己设定百分比。

其他的算法设计都与问题一类似。

代码如下KNN_https://www.doczj.com/doc/5815694863.html,（k=7）：

/* add the get_error_rate function */

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef string tLabel;

typedef double tData;

typedef pair PAIR;

constintMaxColLen = 10;

constintMaxRowLen = 10000;

ifstream fin;

ofstreamfout;

class KNN

{

private:

tDatadataSet[MaxRowLen][MaxColLen];

tLabel labels[MaxRowLen];

tDatatestData[MaxColLen];

introwLen;

intcolLen;

int k;

inttest_data_num;

mapmap_index_dis;

mapmap_label_freq;

doubleget_distance(tData *d1,tData *d2);

public:

KNN(int k , introwLen , intcolLen , char *filename);

voidget_all_distance();

tLabelget_max_freq_label();

voidauto_norm_data();

voidget_error_rate();

structCmpByValue

{

bool operator() (const PAIR&lhs,const PAIR&rhs)

{

returnlhs.second

}

};

~KNN();

};

KNN::~KNN()

{

fin.close();

fout.close();

map_index_dis.clear();

map_label_freq.clear();

}

KNN::KNN(int k , int row ,int col , char *filename)

{

this->rowLen = row;

this->colLen = col;

this->k = k;

test_data_num = 0;

fin.open(filename);

fout.open("result.txt");

if( !fin || !fout )

cout<<"can not open the file"<

exit(0);

}

for(inti=0;i

{

for(int j=0;j

{

fin>>dataSet[i][j];

fout<

}

fin>>labels[i];

fout<

}

}

void KNN:: get_error_rate()

{

inti,j,count = 0;

tLabel label;

cout<<"please input the number of test data : "<

cin>>test_data_num;

for(i=0;i

{

for(j=0;j

{

testData[j] = dataSet[i][j];

}

get_all_distance();

label = get_max_freq_label();

if( label!=labels[i] )

count++;

map_index_dis.clear();

map_label_freq.clear();

cout<<"the error rate is = "<<(double)count/(double)test_data_num<

double KNN:: get_distance(tData *d1,tData *d2)

{

double sum = 0;

for(inti=0;i

{

sum += pow( (d1[i]-d2[i]) , 2 );

}

//cout<<"the sum is = "<

returnsqrt(sum);

}

void KNN:: get_all_distance()

{

double distance;

inti;

for(i=test_data_num;i

{

distance = get_distance(dataSet[i],testData);

map_index_dis[i] = distance;

}

// map::const_iterator it = map_index_dis.begin();

// while(it!=map_index_dis.end())

// {

// cout<<"index = "<first<<" distance = "<second<

// }

}

tLabel KNN:: get_max_freq_label()

{

vectorvec_index_dis( map_index_dis.begin(),map_index_dis.end() );

sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue());

for(inti=0;i

{

cout<<"the index = "<

"<

int j;

for(j=0;j

{

cout<

}

cout<

map_label_freq[ labels[ vec_index_dis[i].first ] ]++;

}

map::const_iteratormap_it = map_label_freq.begin();

tLabel label;

intmax_freq = 0;

while(map_it != map_label_freq.end() )

{

if(map_it->second >max_freq )

{

max_freq = map_it->second;

label = map_it->first;

}

map_it++;

}

cout<<"The test data belongs to the "<

return label;

}

void KNN::auto_norm_data()

{

tDatamaxa[colLen] ;

tData mina[colLen] ;

tData range[colLen] ;

inti,j;

for(i=0;i

{

maxa[i] = max(dataSet[0][i],dataSet[1][i]);

mina[i] = min(dataSet[0][i],dataSet[1][i]);

}

for(i=2;i

{

for(j=0;j

{

if(dataSet[i][j]>maxa[j] )

{

maxa[j] = dataSet[i][j];

}

else if( dataSet[i][j]

{

mina[j] = dataSet[i][j];

}

}

}

for(i=0;i

{

range[i] = maxa[i] - mina[i] ;

//normalize the test data set

testData[i] = ( testData[i] - mina[i] )/range[i] ;

}

//normalize the training data set

for(i=0;i

{

for(j=0;j

{

dataSet[i][j] = ( dataSet[i][j] - mina[j] )/range[j];

}

}

}

int main(intargc , char** argv)

{

intk,row,col;

char *filename;

if(argc!=5 )

{

cout<<"The input should be like this : ./a.out k row col filename"<

exit(1);

}

k = atoi(argv[1]);

row = atoi(argv[2]);

col = atoi(argv[3]);

filename = argv[4];

KNN knn(k,row,col,filename);

knn.auto_norm_data();

knn.get_error_rate();

// knn.get_all_distance();

// knn.get_max_freq_label();

return 0;

}

makefile:

target:

g++ KNN_https://www.doczj.com/doc/5815694863.html,

./a.out 7 1000 3 datingTestSet.txt

结果：

可以看到：在测试数据为10%和训练数据90%的比例下，可以看到错误率为4%，相对来讲还是很准确的。

构建完整可用系统：

已经通过使用数据对分类器进行了测试，现在可以使用分类器为海伦来对人进行分类。

代码KNN_https://www.doczj.com/doc/5815694863.html,（k=7）：

/* add the auto_norm_data */

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef string tLabel;

typedef double tData;

typedef pair PAIR;

constintMaxColLen = 10;

constintMaxRowLen = 10000;

ifstream fin;

ofstreamfout;

class KNN

{

private:

tDatadataSet[MaxRowLen][MaxColLen];

tLabel labels[MaxRowLen];

tDatatestData[MaxColLen];

introwLen;

intcolLen;

int k;

mapmap_index_dis;

mapmap_label_freq;

doubleget_distance(tData *d1,tData *d2);

public:

KNN(int k , introwLen , intcolLen , char *filename);

voidget_all_distance();

tLabelget_max_freq_label();

voidauto_norm_data();

structCmpByValue

{

bool operator() (const PAIR&lhs,const PAIR&rhs)

{

returnlhs.second

}

};

~KNN();

};

KNN::~KNN()

{

fin.close();

fout.close();

map_index_dis.clear();

map_label_freq.clear();

KNN::KNN(int k , int row ,int col , char *filename)

{

this->rowLen = row;

this->colLen = col;

this->k = k;

fin.open(filename);

fout.open("result.txt");

if( !fin || !fout )

{

cout<<"can not open the file"<

exit(0);

}

//input the training data set

for(inti=0;i

{

for(int j=0;j

{

fin>>dataSet[i][j];

fout<

}

fin>>labels[i];

fout<

}

//input the test data

cout<<"frequent flier miles earned per year?";

cin>>testData[0];

cout<<"percentage of time spent playing video games?";

cin>>testData[1];

cout<<"liters of ice cream consumed per year?";

cin>>testData[2];

}

k近邻分类算法

第2章k-近邻算法(kNN) 引言 本章介绍kNN算法的基本理论以及如何使用距离测量的方法分类物品。其次，将使用python从文本文件中导入并解析数据，然后，当存在许多数据来源时，如何避免计算距离时可能碰到的一些常见的错识。 2.1 k-近邻算法概述 k-近邻(k Nearest Neighbors)算法采用测量不同特征之间的距离方法进行分类。它的工作原理是：存在一个样本数据集合，并且样本集中每个数据都存在标签，即我们知道样本每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。一般来说，我们只选择样本数据集中前k 个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。 k-近邻算法的优点是精度高，对异常值不敏感，无数据输入假定；缺点是计算复杂度高、空间复杂度高。适用于数值和离散型数据。 2.1.1 准备知识：使用python导入数据 首先，创建名为kNN.py的python模块，然后添加下面代码： from numpy import * #引入科学计算包 import operator #经典python函数库。运算符模块。

#创建数据集 def createDataSet(): group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels=['A','A','B','B'] return group,labels 测试：>>> import kNN >>> group,labels=kNN.createDataSet() 注意：要将kNN.py文件放到Python27文件夹下，否则提示找不到文件。 2.2.2 实施kNN算法 使用k-近邻算法将每组数据划分到某个类中，其伪代码如下： 对未知类别属性的数据集中的每个点依次执行以下操作： 1.计算已知类别数据集中的点与当前点之间的距离； 2.按照距离递增交序排序； 3.选取与当前点距离最小的k个点； 4.确定前k个点所在类别的出现频率； 5.返回前k个点出现频率最高的类别作为当前点的预测分类。 用欧氏距离公式，计算两个向量点xA和xB之间的距离： 例如，点(0, 0)与(1, 2)之间的距离计算为: python函数classify()程序如下所示：

模式识别(K近邻算法)

K 近邻算法 1.算法思想 取未知样本的x 的k 个近邻,看这k 个近邻中多数属于哪一类，就把x 归于哪一类。具体说就是在N 个已知的样本中,找出x 的k 个近邻。设这N 个样本中，来自1w 类的样本有1N 个，来自2w 的样本有2N 个，...，来自c w 类的样本有c N 个，若c k k k ,,,21 分别是k 个近邻中属于c w w w ,,,21 类的样本数，则我们可以定义判别函数为： c i k x g i i ,,2,1,)( == 决策规则为： 若i i j k x g max )(=，则决策j w x ∈ 2.程序代码 %KNN 算法程序 function error=knn(X,Y ,K) %error 为分类错误率 data=X; [M,N]=size(X); Y0=Y; [m0,n0]=size(Y); t=[1 2 3];%3类向量 ch=randperm(M);%随机排列1—M error=0; for i=1:10 Y1=Y0; b=ch(1+(i-1)*M/10:i*M/10); X1=X(b,:); X(b,:)=[]; Y1(b,:)=[]; c=X; [m,n]=size(X1); %m=15,n=4 [m1,n]=size(c); %m1=135,n=4 for ii=1:m for j=1:m1 ss(j,:)=sum((X1(ii,:)-c(j,:)).^2); end [z1,z2]=sort(ss); %由小到大排序 hh=hist(Y1(z2(1:K)),t); [w,best]=max(hh); yy(i,ii)=t(best); %保存修改的分类结果 end

kNN算法综述

kNN算法综述 王宇航13120476 (北京交通大学计算机与信息技术学院，北京，100044) 摘要：kNN算法是著名的模式识别统计学方法，是最好的文本分类算法之一，在机器学习分类算法中占有相当大的地位，是最简单的机器学习算法 之一。本文对kNN算法及相关文献做一份总结，详细介绍kNN算法的思想、原理、实现步骤以及具体实现代码，并分析了算法的优缺点及其各种改进方 案。本文还介绍了kNN算法的发展历程、重要的发表的论文。本文在最后介 绍了kNN算法的应用领域，并重点说明其在文本分类中的实现。 关键字：kNN算法；k近邻算法；机器学习；文本分类 Abstract:KNN algorithm,a famous statistical method of pattern recognition, which is one of the best algorithms for dealing with text categorization,is playing an important role in machine learning classification algorithm,and it is one of the simplest algorithms in machine learning.This paper mainly summaries the kNN algorithm and its related literature,and detailed introduces its main idea,principle, implementation steps and specific implementation code,as well as analyzes the advantages and disadvantages of the algorithm and its various improvement schemes.This paper also introduces the development course of kNN algorithm,its important published paper.In the final,this paper introduces the application field of kNN algorithm,and especially in text categorization. Keywords:KNN algorithm,K neighbor algorithm,Machine learning,Text classification 1引言 分类是数据挖掘中的核心和基础技术，在经营、决策、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、kNN分类、人工神经网络等。在这些方法中，kNN分类是一种简单、有效、非参数的方法，现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对kNN算法进行较为全面的总结。 本文的结构如下： 在第二部分，主要介绍kNN算法的基本原理、思想、实现步骤、Java实现代码以及发展历程和经典论文。 第三部分是对kNN算法的诸多不足之处进行的讨论，并给出一些改进的方案。 第四部分介绍的是kNN算法如何处理多标签数据。 第五部分介绍了kNN算法目前的主要应用领域，并着重说明了其在文本分类中的出色表现。

基于K近邻的分类算法研究-WORD

K近邻算法 算法介绍： K最近邻(k-Nearest neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

机器学习十大算法8：kNN

Chapter8 k NN:k-Nearest Neighbors Michael Steinbach and Pang-Ning Tan Contents 8.1Introduction (151) 8.2Description of the Algorithm (152) 8.2.1High-Level Description (152) 8.2.2Issues (153) 8.2.3Software Implementations (155) 8.3Examples (155) 8.4Advanced Topics (157) 8.5Exercises (158) Acknowledgments (159) References (159) 8.1Introduction One of the simplest and rather trivial classi?ers is the Rote classi?er,which memorizes the entire training data and performs classi?cation only if the attributes of the test object exactly match the attributes of one of the training objects.An obvious problem with this approach is that many test records will not be classi?ed because they do not exactly match any of the training records.Another issue arises when two or more training records have the same attributes but different class labels. A more sophisticated approach,k-nearest neighbor(k NN)classi?cation[10,11,21],?nds a group of k objects in the training set that are closest to the test object,and bases the assignment of a label on the predominance of a particular class in this neighborhood.This addresses the issue that,in many data sets,it is unlikely that one object will exactly match another,as well as the fact that con?icting information about the class of an object may be provided by the objects closest to it.There are several key elements of this approach:(i)the set of labeled objects to be used for evaluating a test object’s class,1(ii)a distance or similarity metric that can be used to compute This need not be the entire training set. 151

K近邻分类数据模拟和实例分析

K近邻分类数据模拟和实例分析 3.1 数据模拟 用MATLAB随机生成150组数据，类别为三类，编程如下 # 程序1： A1=rand(50,2); hold on plot(A1(:,1),A1(:,2),'.') A2=rand(50,2)+0.75; hold on plot(A2(:,1),A2(:,2),'.') hold on A3=rand(50,2)+1.5; plot(A3(:,1),A3(:,2),'.') 再用k近邻分类算法对这150组数据进行分类，取k=15近邻，程序如下# 程序 2： clear all

clc y=importdata('C:\Users\adm\Desktop\test.txt'); p=y(:,2:3); p=p'; Add=zeros(150,1); Add(1:50,:)=ones(50,1); Add(51:100,:)=2*ones(50,1); Add(101:150,:)=3*ones(50,1); figure(1),plot(y(:,1),Add,'g.'); hold on grid on; count=0; for i=1:3 for j=1:50 for k=1:150 distance(k)=mse(p(:,k)-p(:,(i-1)*50+j));%保存每个向量与所有训练样本之间的距离 end [d1 index1]=sort(distance);%对距离distance向量进行从小到大的排序 num=[0 0 0]; for m=1:20 % 考察num，存放的是排序后distance前20个属于每一类别的个数 if index1(m)<=50 num(1)=num(1)+1; elseif index1(m)<=100 num(2)=num(2)+1; else num(3)=num(3)+1; end end [d2 class]=max(num);%属于哪类的个数最多，就属于哪类，class 即就是该向量所属的类别 if i==class count=count+1; end A((i-1)*50+j)=class;%存放判断的结果 end end count rate=count/150 figure(2),plot(y(:,1),A,'r.');grid on;%画图分类 程序运行后得到 count =143 rate =0.9533

第6章-k近邻算法--机器学习与应用第二版

第6章k 近邻算法 k 近邻算法（kNN 算法）由Thomas 等人在1967年提出[1]。它基于以下朴素思想：要确定一个样本的类别，可以计算它与所有训练样本的距离，然后找出和该样本最接近的k 个样本，统计这些样本的类别进行投票，票数最多的那个类就是分类结果。因为直接比较待预测样本和训练样本的距离，kNN 算法也被称为基于实例的算法。 6.1基本概念 确定样本所属类别的一种最简单的方法是直接比较它和所有训练样本的相似度，然后将其归类为最相似的样本所属的那个类，这是一种模板匹配的思想。k 近邻算法采用了这种思路，下图6.1是使用k 近邻思想进行分类的一个例子： 图6.1k 近邻分类示意图 在上图中有红色和绿色两类样本。对于待分类样本即图中的黑色点，我们寻找离该样本最近的一部分训练样本，在图中是以这个矩形样本为圆心的某一圆范围内的所有样本。然后统计这些样本所属的类别，在这里红色点有12个，绿色有2个，因此把这个样本判定为红色这一类。上面的例子是二分类的情况，我们可以推广到多类，k 近邻算法天然支持多类分类问题。 6.2预测算法 k 近邻算法没有要求解的模型参数，因此没有训练过程，参数k 由人工指定。它在预测时才会计算待预测样本与训练样本的距离。 对于分类问题，给定l 个训练样本(),i i y x ，其中i x 为维特征向量，i y 为标签值，设定

参数k ，假设类型数为c ，待分类样本的特征向量为x 。预测算法的流程为： 1.在训练样本集中找出离x 最近的k 个样本，假设这些样本的集合为N 。 2.统计集合N 中每一类样本的个数,1,...,i C i c =。 3.最终的分类结果为arg max i i C 。 在这里arg max i i C 表示最大的i C 值对应的那个类i 。如果1k =，k 近邻算法退化成最近邻算法。 k 近邻算法实现简单，缺点是当训练样本数大、特征向量维数很高时计算复杂度高。因为每次预测时要计算待预测样本和每一个训练样本的距离，而且要对距离进行排序找到最近的k 个样本。我们可以使用高效的部分排序算法，只找出最小的k 个数；另外一种加速手段是k-d 树实现快速的近邻样本查找。 一个需要解决的问题是参数k 的取值。它需要根据问题和数据的特点来确定。在实现时可以考虑样本的权重，即每个样本有不同的投票权重，这称方法称为为带权重的k 近邻算法。另外还其他改进措施，如模糊k 近邻算法[2]。 kNN 算法也可以用于回归问题。假设离测试样本最近的k 个训练样本的标签值为i y ，则对样本的回归预测输出值为： 1/k i i y y k =??= ??? ∑即所有邻居的标签均值，在这里最近的k 个邻居的贡献被认为是相等的。同样的也可以采用带权重的方案。带样本权重的回归预测函数为： 1/k i i i y w y k =??= ??? ∑其中i w 为第i 个样本的权重。权重值可以人工设定，或者用其他方法来确定，例如设置为与距离成反比。 6.3距离定义 kNN 算法的实现依赖于样本之间的距离值，因此需要定义距离的计算方式。本节介绍几种常用的距离定义，它们适用于不同特点的数据。 两个向量之间的距离为() ,i j d x x ，这是一个将两个维数相同的向量映射为一个实数的函数。距离函数必须满足以下条件，第一个条件是三角不等式：()()() ,,,i k k j i j d d d +≥x x x x x x 这与几何中的三角不等式吻合。第二个条件是非负性，即距离不能是一个负数： (),0 i j d ≥x x 第三个条件是对称性，即A 到B 的距离和B 到A 的距离必须相等：

模式识别 最近邻法和K近邻法MATLAB实现

最近邻法和k-近邻法 学号：02105120姓名：吴林一.基本概念： 最近邻法：对于未知样本x，比较x与N个已知类别的样本之间的欧式距离，并决策x与距离它最近的样本同类。 K近邻法：取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。K取奇数，为了是避免k1=k2的情况。 二.问题分析： 要判别x属于哪一类，关键要求得与x最近的k个样本（当k=1时，即是最近邻法），然后判别这k个样本的多数属于哪一类。 可采用欧式距离公式求得两个样本间的距离s=sqrt（（x1-x2）^2+(y1-y2)^2） 三.算法分析： 该算法中任取每类样本的一半作为训练样本，其余作为测试样本。例如iris中取每类样本的25组作为训练样本，剩余25组作为测试样本，依次求得与一测试样本x距离最近的k 个样本，并判断k个样本多数属于哪一类，则x就属于哪类。测试10次，取10次分类正确率的平均值来检验算法的性能。 四.MATLAB代码： 最近邻算实现对Iris分类 clc; totalsum=0; for ii=1:10 data=load('iris.txt'); data1=data(1:50,1:4);%任取Iris-setosa数据的25组 rbow1=randperm(50); trainsample1=data1(rbow1(:,1:25),1:4); rbow1(:,26:50)=sort(rbow1(:,26:50));%剩余的25组按行下标大小顺序排列testsample1=data1(rbow1(:,26:50),1:4); data2=data(51:100,1:4);%任取Iris-versicolor数据的25组 rbow2=randperm(50); trainsample2=data2(rbow2(:,1:25),1:4); rbow2(:,26:50)=sort(rbow2(:,26:50)); testsample2=data2(rbow2(:,26:50),1:4); data3=data(101:150,1:4);%任取Iris-virginica数据的25组 rbow3=randperm(50); trainsample3=data3(rbow3(:,1:25),1:4); rbow3(:,26:50)=sort(rbow3(:,26:50)); testsample3=data3(rbow3(:,26:50),1:4);

(完整word版)各种聚类算法介绍及对比

一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个 类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类” 的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。

k近邻模型和算法

k 近邻模型和算法 2.1 K 近邻模型 K 近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素 —-距离度量、k 值得选择和分类规则决定。 2.1.1 模型 K 近邻法中，当训练集、距离度量（如欧式距离）、k 值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所述的类。这一事实从最近邻算法中可以看得很清楚。 特征空间中，对每个实例点i x ,距离该点比其他店更近的所有点组成一个区域，叫做单元。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特 征空间的一个划分。最近邻法将实例i x 的类i y 作为其单元中所有点的类标记。这样，每个单元的实例点的类别时确定的。下图是二维特征空间划分的一个例子。 2.1.2 距离度量

特征空间中两个实例点的距离是两个点相似程度的反映。K 近邻模型的特征空间一般是n 维实数向量空间Rn 。使用的距离是欧式距离，但也可以是其他距离，如更一般的Lp 或闽科夫斯基距离。 设特征空间χ是n 维实数向量空间n R ，i x ，,),,,(,) ()2()1(T n i i i i j x x x x x =∈χ ,),,,() ()2()1(T n j j j j x x x x =j i x x ,的距离定义为P L p n l p l j l i j i p x x x x L 11),(? ?? ??-=∑= 这里1≥p 。当2=p 时，称为欧式距离，即 2 1 122,??? ??-=∑=n l l j l i j i x x x x L ） （ 当 时，称为曼哈顿距离，即 ∑=-=n l l j l i j i x x x x L 1 1,） （ 当∞=p 时，它是各个距离坐标的最大值，即 l j l i l j i x x x x L -=∞max ),( 2.1.3 K 值的选择 k 值的选择会对k 近邻法的结果产生重大影响。 如果选择较小的k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果近邻的实例点恰巧是噪声，预测就会出错。换句话说，k 值得减小就意味着整体模型变得复杂，容易发生过拟合。 如果选择较大的k 值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，是预测发生错误。K 值得增大就意味着整体的模型变得简单。 如果k=N ，那么无论输入实例是什么，都将简单的预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。 2.1.4 分类决策规则 1 =p

k近邻算法

k近邻算法(knn, k nearest neighbor) 前两天受朋友之托，帮忙与两个k近邻算法，k近邻的非正式描述，就是给定一个样本集exset，样本数为M，每个样本点是N维向量，对于给定目标点d，d也为N维向量，要从exset中找出与d距离最近的k个点(k<=N)，当k=1时，knn问题就变成了最近邻问题。最naive的方法就是求出exset中所有样本与d的距离，进行按出小到大排序，取前k个即为所求，但这样的复杂度为O(N)，当样本数大时，效率非常低下. 我实现了层次knn(HKNN)和kdtree knn，它们都是通过对树进行剪枝达到提高搜索效率的目的，hknn的剪枝原理是(以最近邻问题为例)，如果目标点d与当前最近邻点x的距离，小于d与某结点Kp中心的距离加上Kp的半径，那么结点Kp中的任何一点到目标点的距离都会大于d 与当前最近邻点的距离，从而它们不可能是最近邻点(K近邻问题类似于它)，这个结点可以被排除掉。 kdtree对样本集所在超平面进行划分成子超平面，剪枝原理是，如果某个子超平面与目标点的最近距离大于d与当前最近点x的距离，则该超平面上的点到d的距离都大于当前最近邻点，从而被剪掉。两个算法均用matlab实现(应要求)，把代码帖在下面，以备将来查用或者需要的朋友可以参考. function y = VecDist(a, b) %%返回两向量距离的平方 assert(length(a) == length(b)); y = sum((a-b).^2); end 下面是HKNN的代码

classdef Node < handle %UNTITLED2 Summary of this class goes here % Detailed explanation goes here % Node 层次树中的一个结点，对应一个样本子集Kp properties Np; %Kp的样本数 Mp; %Kp的样本均值，即中心 Rp; %Kp中样本到Mp的最大距离 Leafs; %生成的子节点的叶子,C * k矩阵,C为中心数量，k是样本维数。如果不是叶结点，则为空 SubNode; %子节点, 行向量 end methods function obj = Node(samples, maxLeaf) global SAMPLES

R语言与机器学习(1)K-近邻算法

K-近邻算法原理及举例 工作原理：我们知道样本集中每一个数据与所属分类的对应关系，输入没有标签的新数据后，将新数据与训练集的数据对应特征进行比较，找出“距离”最近的k(通常k<20)数据，选择这k个数据中出现最多的分类作为新数据的分类。 算法描述： (1) 计算已知类别数据及中的点与当前点的距离; (2) 按距离递增次序排序 (3) 选取与当前点距离最小的k个点 (4) 确定前K个点所在类别出现的频率 (5) 返回频率最高的类别作为当前类别的预测 这里我们使用最常见欧氏距离作为衡量标准，以鸢尾花数据集为例来说明K-近邻算法：鸢尾花数据集包含150个数据，测量变量为花瓣，花萼的长度与宽度，分类变量为setosa, versicolor, 和 virginica。 准备数据：

为了了解数据，我们先通过作图分析，相关分析来看看数据分类指标的合理性，这一点十分重要，有助于减少分类指标中的噪声。 从上图可以看出，我们通过这2个变量大致是可以把鸢尾花分类的，也就是说分类的特征变量选择是合理的，(同理可以分析另外2个，分类效果不如这两个，但大致上还是能区分的)当然我们也可以选择计算相关系数来看特征变量的合理性。 我们很容易发现，数值差最大的属性对距离的影响最大，所以在特征值等权重的假定下，我们先得归一化特征值，计算公式为： Newvalue=(oldvalue-min)/(max-min) R代码：

autonorm<-function(data){ for(iin 1:length(data)) data[i]<-(data[i]-min(data))/(max(data)-min(data)) return(data) } data<-as.matrix(apply(iris[,1:4],2,autonorm)) 得到了归一化后的数据集，下面计算距离。我们在这里取三个数据作为验证集来看看分类的效果，首先将验证集归一化： x<-iris[13,1:4] y<-iris[79,1:4] z<-iris[100,1:4] x<-(x-apply(iris[c(-13,-79,-100),1:4],2,min))/(apply(iris[c(-13,-79,-100),1:4],2,max)-apply(iris[c(-13,-79,-100),1:4],2,min)) y<-(y-apply(iris[c(-13,-79,-100),1:4],2,min))/(apply(iris[c(-13,-79,-100),1:4],2,max)-apply(iris[c(-13,-79,-100),1:4],2,min)) z<-(z-apply(iris[c(-13,-79,-100),1:4],2,min))/(apply(iris[c(-13,-79,-100),1:4],2,max)-apply(iris[c(-13,-79,-100),1:4],2,min)) 计算距离，仅以x为例，运行代码：(k取5) dis<-rep(0,length(data[,1])) for(iin 1:length(data[,1])) dis[i]<-sqrt(sum((z-data[i,1:4])^2)) table(data[order(dis)[1:5],5]) x,y,z的输出结果为 标签xyyz

K近邻分类算法

K近邻分类算法（K –nearest neighbors，简称KNN） 1算法的提出与发展 最初的近邻法是由Cover和Hart与1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。 2算法原理 2.1 基本原理 最近邻方法(k-nearest neighbor,简称kNN)是一种简洁而有效的非参数分类方法，是最简单的机器学习算法之一，该算法最初由Cover和Hart提出的，用于解决文本的分类问题。 K 近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的K 个近邻中出现最多的那个类别。K 近邻算法从测试样本点x开始生长，不断的扩大区域，直到包含进K 个训练样本点为止，并且把测试样本点x归为这最近的K 个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。 如果K 值固定，并且允许训练样本个数趋向于无穷大，那么，所有的这K 个近邻都将收敛于x。如同最近邻规则一样，K 个近邻的标记都是随机变量，概率P（w i|x），i=1,2,…,K 都是相互独立的。假设P（w m|x）是较大的那个后验概率，那么根据贝叶斯分类规则，则选取类别w m。而最近邻规则以概率P（w m|x）选取类别。而根据K近邻规则，只有当K个最近邻中的大多数的标记记为w m，才判定为类别w m。做出这样断定的概率为 通常K值越大，选择类别w m概率也越大。 2.2K值的选择 K近邻规则可以被看作是另一种从样本中估计后验概率P（w i|x）的方法。为了得到可高的估计必须是的K值越大越好。另一方面，又希望又希望x的K 个近邻x 距离x1越近越好，因为这样才能保证P（w i|x1）尽可能逼近P（w i|x）。在选取K 值的时候，就不得不做出某种折衷。只有当n趋近于无穷大时，才能保证K 近邻规则几乎是最优的分类规则。 K值的选择：需要消除K值过低，预测目标容易产生变动性，同时高k值时，预测目标有过平滑现象。推定k值的有益途径是通过有效参数的数目这个概念。有效参数的数目是和k值相关的，大致等于n/k，其中，n是这个训练数据集中实例的数目。 确定K的值：通过实验确定。进行若干次实验，取分类误差率最小的k值。 2.3算法步骤 1)依公式计算Item 与D1、D2 ……、Dj 之相似度。得到Sim(Item, D1)、Sim(Item, D2)……、Sim(Item, Dj)。 2)将Sim(Item, D1)、Sim(Item, D2)……、Sim(Item, Dj)排序，若是超过相似度门槛t则放入 邻居案例集合NN。 3)自邻居案例集合NN中取出前k名，依多数决，得到Item可能类别。 3KNN优缺点 优点：1）原理简单，实现起来比较方便； 2）支持增量学习；

k最近邻算法实验报告

题目k-最近邻算法实现学生姓名 学生学号 专业班级 指导教师 2015-1-2

实验二 k-最近邻算法实现 一、实验目的 1.加强对k-最近邻算法的理解； 2.锻炼分析问题、解决问题并动手实践的能力。 二、实验要求 使用一种你熟悉的程序设计语言，如C++或Java，给定最近邻数k和描述每个元组的属性数n，实现k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能。 三、实验环境 Win7 旗舰版 + Visual Studio 2010 语言：C++ 四、算法描述 KNN(k Nearest Neighbors)算法又叫k最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类， KNN就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待

分样本集来说，KNN 方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K 个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 1、 算法思路 K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的（未标记的）样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练样本由N 维数值属性描述，每个样本代表N 维空间的一个点。这样，所有训练样本都存放在N 维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的K 个训练样本。这K 个训练样本是未知样本的K 个“近邻”。“临近性”又称为相异度（Dissimilarity ），由欧几里德距离定义，其中两个点 X （x1,x2,…,xn ）和Y （y1,y2,…,yn ）的欧几里德距离是： 2 222211)()()(),(n n y x y x y x y x D -+?+-+-= 未知样本被分配到K 个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间中与之最临近的训练样本的类。 2、 算法步骤 初始化距离为最大值； 计算未知样本和每个训练样本的距离dist ； 得到目前K 个最临近样本中的最大距离maxdist ； 如果dist 小于maxdist ，则将该训练样本作为K-最近邻样本； 重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完； 统计K-最近邻样本中每个类标号出现的次数； 选择出现频率最大的类标号作为未知样本的类标号。

KNN算法原理及应用

KNN分类算法（理论）

目录 1.KNN算法 (1) 2.KNN算法描述 (1) 3.KNN主要的应用领域 (2) 4.KNN算法的优、缺点 (2)

1.KNN算法 KNN算法，右又叫K最邻近分类算法，是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。 KNN算法概括来说，就是已知一个样本空间里的部分样本分成几个类，然后，给定一个待分类的数据，通过计算找出与自己最接近的K个样本，由这K个样本投票决定待分类数据归为哪一类。kNN算法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。 2.KNN算法描述 一个比较经典的KNN图如下： 从上图中我们可以看到，图中的有两个类型的样本数据，一类是蓝色的正方形，另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。 如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形。

如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形。 3.KNN主要的应用领域 文本分类、聚类分析、预测分析、模式识别、图像处理。 KNN算法不仅可以用于分类，还可以用于预测。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。 4.KNN算法的优、缺点 优点 (1) 简单，易于理解，易于实现，无需估计参数，无需训练； (2) 适合对稀有事件进行分类； (3) 特别适合于多分类问题(multi-modal,对象具有多个类别标签)，kNN比SVM的表现要好。 缺点 (1) 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 (2) 计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

K近邻分类的算法实现

K近邻分类的算法实现 K近邻（KNN）法的输入为实例的特征向量，对应于特征空间的点；输入为实例的类别，可以取多类。K近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此K近邻不具有显式的学习过程。K近邻法实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 1.1 选题背景 现如今，数据的爆炸式增长、广泛可用和巨大数量使得我们的时代成为真正的数据时代。急需功能强大和通用的工具，以便从这些海量数据中发现有价值的信息，把这些数据转化成有组织的知识。这种需求导致了数据挖掘的诞生。这个领域是年轻的、动态变化的、生机勃勃的。数据挖掘已经并且将继续在我们从数据时代大步跨入信息时代的历程中作出贡献。 K近邻方法是20世纪50年代早期首次引进的。当给定大量数据集时，该方法是计算密集的，直到20世纪60年代计算能力大大增强之后才流行起来。此后它广泛用于模式识别领域。 K近邻分类法是基于类比学习，即通过将给定的检验元组与它相似的训练元组进行比较来学习。训练元组用n个属性描述。每个元组代表n维空间的一个点。这样，所有的训练元组都存放在n维模式空间中。当给定一个未知元组时，k近邻分类法搜索模式空间，找出最接近元组的k个训练元组。这k个训练元组即为该元组的k个“最近邻”。 1.2 研究现状 国内外学者为此算法在实际生活中更好地应用做出了许多努力。例如对k近邻方法的不足做出的一些改进如文献[2]，[7]，[8]，[9]，[10]等等。在其他领域的应用如文献[5]将K近邻算法改进为非线性分类算法，以达到分类动态心电图波形的目的。文献[6]在KNN算法的基础上提出了图像自动分类模型。在生物学上，K近邻方法也得到了广泛地应用，有文献利用蛋白质相互作用网络,提出