| 查看: 4103 | 回复: 9 | |||||
| 【奖励】 本帖被评价5次，作者stephenliu89增加金币 4 个 | |||||
[资源]
【原创】一个简单的kNN分类算法 (k-Nearest Neighbor algorithm) 的C++实现（附源码）
|
|||||
邻近算法 KNN算法的决策过程 k-Nearest Neighbor algorithm 是K最邻近结点算法（k-Nearest Neighbor algorithm）的缩写形式，是电子信息分类器算法的一种 该算法[5]的基本思路是[6]：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的 K 篇文本，根据这 K 篇文本所属的类别判定新文本所属的类别 左图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。 K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 KNN-主要应用领域 ·文本分类·聚类分析·数据挖掘·机器学习·预测分析·减少维度·模式识别·图像处理 我的kNN分类算法程序：   ------------------- Code written by Stephen Liu ----------------------- #include #include #define MAX 1000 using namespace std; int m, i, j; int types[100]; class str { public: float x; float y; float distance; int type; }; str data[ MAX ];//输入的已知类别的数据 str point;//需要根据kNN判断类别的未知数据 str temp; void input_data() { cout << "请输入已知点的个数："; cin >> m; for ( i = 1; i <= m; i++) { cout <<"请输入点 " << i <<" 的坐标x , y 和所属类别：" ; cin >> data.x >> data.y >> data.type; } } void Distance()//计算未知类别点与所有已知类别点的距离 { for ( i = 1; i <= m; i++ ) data.distance = sqrt ( (data.x - point.x) * (data.x - point.x) + (data.y - point.y) * (data.y - point.y) ); } void sort()//对距离进行从小到大排序 { for( i = 1; i <= m; i++) for(j = m; j > i; j--) { if(data[ j ].distance < data[ j - 1 ].distance) { temp=data[ j ]; data[ j ]=data[ j - 1 ]; data[ j - 1]=temp; } } } int kNN( ) { int the_type,num = 0, k; cout <<"请输入kNN的k值："; cin >> k; for ( i = 1; i <= 99; i++) types[ i ] = 0; for ( i = 1; i <= k; i++)//对已排序的前k位距离类别进行统计 types[ data.type ] ++; for ( i = 1; i <= 99; i++)//找出未知类别点属于的类别 { if (types > num ) { num = types; the_type = i; } } return ( the_type); } int main() { input_data(); cout <<"请输入未知类别点的坐标x,y（输入0 0退出)："; cin >> point.x >> point.y; do { Distance(); sort(); cout <<"点( " << point.x << " , " << point.y <<" )属于类"<< kNN() << endl; cout <<"请输入未知类别点的坐标x,y（输入0 0退出)："; cin >> point.x >> point.y; } while ( point.x != 0 && point.y != 0); cout <<"======= kNN分类算法 Stephen Liu E-mail:stephenliu1989@163.com 2010.8 ======= "; system("pause"  ;return 0; } ------------------------- Code end --------------------------------- 我的评价： 这是kNN分类算法的最简单的一种情况，当k取不同值时分类可能会出现不同。样本过大时，由于要比较的次数增多，效率降低。 |
回复此楼» 收录本帖的淘帖专辑推荐
 【计算机工具软件与技巧】专辑 | ML相关 | source |
» 猜你喜欢
回收溶剂求助
已经有7人回复
-
职称评审没过，求安慰
已经有40人回复
-
硝基苯如何除去
已经有3人回复
-
A期刊撤稿
已经有4人回复
-
垃圾破二本职称评审标准
已经有17人回复
-
投稿Elsevier的Neoplasia杂志，到最后选publishing options时页面空白，不能完成投稿
已经有22人回复
-
申请26博士
已经有5人回复
-
EST投稿状态问题
已经有7人回复
-
毕业后当辅导员了，天天各种学生超烦
已经有4人回复
-
求助文献
已经有3人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- C++一道题目，疑惑
已经有7人回复
- 科学计算首选语言是C++
已经有20人回复
- 求助一个简单程序
已经有3人回复
- 请教一个C++读文件的问题，
已经有12人回复
- 一个简单的C++程序运行问题
已经有8人回复
- Visual C++常用数值算法集【转载】
已经有187人回复
- Visual C++ CAD应用程序开发技术源代码（基于OPenGL技术开发的）
已经有76人回复
- 数据结构及算法经典
已经有227人回复
- 求一个简单好用的科学计算器软件。。
已经有4人回复
- 分类算法识别率为多少是可以接受的？
已经有5人回复
- 如何考察一个查询算法的时间
已经有6人回复
- 请问分类和回归树算法在哪个软件里面可以实现？
已经有3人回复
- java算法大全源码包（近100种）
已经有8人回复
- 一直没怎么接触过算法，如何实现算法改进。
已经有4人回复
- 什么是Nelder–Mead simplex algorithm
已经有5人回复
- 关于knn分类器的使用：在分类前需要正态化处理吗？
已经有4人回复
- 一个简单的式子，却算不正确
已经有10人回复
- 【分享】37码走埃及【已搜索无重复】
已经有4人回复
- 【分享】数据结构算法与应用 C++语言描述
已经有9人回复
- 【求助】求c++编一个简单计算器的源代码
已经有6人回复
- 【分享】c++ 课件及配套源码笔记
已经有6人回复
2楼2010-09-05 11:27:26
3楼2010-09-05 12:00:14
4楼2010-09-05 12:01:46
5楼2010-09-05 16:57:35
6楼2010-09-05 19:13:59
7楼2012-04-13 16:22:29
 本帖仅楼主可见 |
8楼2014-03-24 20:57:40
9楼2014-03-25 08:14:34
10楼2020-10-14 15:11:36