这篇博文主要介绍了一种基于机器学习的分类方法，K-邻近（KNN），并且使用这种方法来完成了一个简单的手写数字识别系统。

KNN 概述

什么是 KNN

KNN（K–nearest-neighbor），即 K-邻近算法，所谓 K 邻近，就是 K 个最近邻居的意思，说的是每个样本都可以用与它最接近的K 个邻居来进行表示。

工作原理

存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所述分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签，一般来讲，我们只取样本集数据中前 K 个最相似的数据，最后在这 K 个数据中统计处出现次数最多的分类，最为新数据的分类。

算法特点

优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型

算法流程

对未知类别属性的数据集中的每个店依次执行以下操作：

计算已知类别数据集中的点与当前点之间的距离
按照距离递增次序排列
选取与当前点距离最小的 K 个点
确定前 K 个点所在类别的出现频率
返回前 K 个点出现频率最高的类别作为当前点的预测分类

对于距离的计算，我们采用欧氏距离公式：

KNN的应用实例 - 手写识别（Java）

简述

我们所做的手写识别是来识别简单的手写数字，数据形式是如下图的文本文件：

我们有一些样本数据，然后用一些测试数据来进行算法的测试。

对于算法源码以及数据样本，详情见：https://github.com/luoyhang003/machine-learning-in-java/tree/master/k-Nearest-Neighbour

具体实现

代码写的比较烂，只是实现了 KNN 的算法，并没有优化，敬请见谅！

首先我们需要将这些文本转换为向量，可以存储于数组中

 public static int[] data2Vec(String fileName){ int arr[] = new int[32 * 32]; try{ FileReader reader = new FileReader(fileName); BufferedReader buffer = new BufferedReader(reader); for(int index = 0; index < 32; index++){ String str = buffer.readLine(); int length = str.length(); for(int i = 0; i < length; i++){ String c = str.substring(i, i + 1); arr[32*index+i] = Integer.parseInt(c); } } }catch (FileNotFoundException e){ e.printStackTrace(); }catch (IOException e){ e.printStackTrace(); } return arr; }

需要定义一个算法来计算每两个向量之间的距离

 public static double calDistance(int[] a, int[] b){ double result = 0.0; int temp = 0; for(int i = 0; i < a.length; i++){ temp += (a[i] - b[i])*(a[i] - b[i]); } result = Math.sqrt(temp); return result; }

然后我们就可以开始进行分类

 public static int[] classify(String fileName){ int result[] = new int[2]; int arr[] = data2Vec("samples/testDigits/"+fileName); result[0] = Integer.parseInt(fileName.split("_")[0]); double dis[] = new double[K]; int num[] = new int[K]; for(int index = 0; index < K; index++){ dis[index] = 32; num[index] = -1; } for(int i = 0; i <= 9; i++){ for(int j = 0; j < 100; j++){ int temp_arr[] = data2Vec("samples/trainingDigits/"+i+"_"+j+".txt"); double temp_dis = calDistance(arr, temp_arr); for(int k = 0; k < K; k++){ if(temp_dis < dis[k]){ dis[k] = temp_dis; num[k] = i; break; } } } } int count[] = new int[10]; for(int i = 0; i < 10; i++) count[i] = 0; for(int i = 0; i < K; i++){ if(num[i]!=-1) count[num[i]]++; } int max = 0; for(int i = 0; i < 10; i++){ if(count[i]>max){ max = count[i]; result[1] = i; } } return result; }

最后我们来测试一下算法

 public static void main(String args[]){ double right = 0; double sum = 0; for(int i = 0; i < 10; i++){ for(int j = 0; j < 50; j++){ int result[] = classify(""+i+"_"+j+".txt"); System.out.println("the classifier came back with: "+result[1]+" , the real answer is: " +result[0]); sum++; if(result[0]==result[1]) right++; } } System.out.println("right:"+right); System.out.println("sum:"+sum); double rate = right/sum; System.out.println("the total right rate is: " + rate); }

得到的结果是：

the classifier came back with: 0 , the real answer is: 0
the classifier came back with: 0 , the real answer is: 0
the classifier came back with: 0 , the real answer is: 0
the classifier came back with: 0 , the real answer is: 0
……


the classifier came back with: 9 , the real answer is: 9
the classifier came back with: 9 , the real answer is: 9
the classifier came back with: 9 , the real answer is: 9
the classifier came back with: 9 , the real answer is: 9
the classifier came back with: 9 , the real answer is: 9
right:486.0
sum:500.0
the total right rate is: 0.972

完整的代码与测试数据详见：https://github.com/luoyhang003/machine-learning-in-java/tree/master/k-Nearest-Neighbour

文章来源：http://blog.luoyuanhang.com

文章来源: blog.csdn.net，作者：冰水比水冰，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/luoyhang003/article/details/48266651

（完）