KNN 在手写识别中的应用（Java 实现）
这篇博文主要介绍了一种基于机器学习的分类方法，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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 需要定义一个算法来计算每两个向量之间的距离
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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 然后我们就可以开始进行分类
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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 最后我们来测试一下算法
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); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
得到的结果是：
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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
完整的代码与测试数据详见：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
- 点赞
- 收藏
- 关注作者
评论（0）