欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数字手写识别——Java实现KNN算法

程序员文章站 2022-04-03 22:36:11
...

引言

手写识别也是当前机器学习的一大热点,数字手写识别是手写识别中的基础,我们用到的是knn算法,今天给大家讲一下我的实现方法;


环境

IDE:Eclipse
语言:Java


项目:数字手写识别

思路

数据采集:我们知道,一张图片可以被看作一个个点组成的矩阵,对于手写数字,我们只要创建一个全0数组当作背景,手写完毕把数字所占区域置为1,就可以保存当作一个样本了,如下图所示。
数字手写识别——Java实现KNN算法
算法:KNN算法,其距离度量我们采用欧拉距离。
欧拉距离计算方法:我们将数组看作40*40向量,采用距离公式计算。

数字手写识别——Java实现KNN算法

实现

一、面板

请原谅作者对于美笨拙的感知,我所绘制的界面不能够再简单了。如图:

面板按钮介绍

  • Identify:识别手写的数字;
  • Save this example: 保存这个样例到数据集;
  • 数字下拉框:相当于保存数据集的标签,例如,要保存手写“2”,先下拉选好2再保存即可

数字手写识别——Java实现KNN算法

二、存储

在数据读取存储上走了很多弯路,之后要好好总结下数据流的几个传输方式。
我们将每张图片转化为一个二维数组后,存放进一个txt文件中。对于每个单独的文件,我们要产生一个独一无二的文件名,所以文件取名方式采取“数字+随机id .txt”的格式命名,随机id我们通过构造UID对象,获取其hashcode值作为id。

            //获取下拉框选中的数字
            String selectedNumber=cbItem.getSelectedItem().toString();
            UID id=new UID();
            //文件的前缀路径
            String rootPath="C:\\Users\\DearYou\\eclipse-workspace\\GUI\\src\\Demo\\handwritingIdentify\\TrainingData\\";
            //生成文件名
            String fileName=selectedNumber+"-"+id.hashCode();
            //生成绝对路径下的一个文件
            String absoluteFile=rootPath+fileName+".txt";
            File file=new File(absoluteFile);
            try {
                //创建文件
                if(!file.exists())
                    file.createNewFile();
                //将数组写入文件
                FileWriter out = new FileWriter(file);
                for(int i=0;i<40;i++) {
                    for(int j=0;j<40;j++) {
                        out.write(pixel[i][j]+"");
                    }
                }
                out.flush();
                out.close();
            }catch(Exception e1) {
                e1.printStackTrace();
            }

三、Knn算法实现

Common thinking :KNN目的是找到k个离测试样本最近的训练样本,看了下同学的方法,大多都使用了排序,但自己想想排序实在是多余,一个排序就将复杂度升到了O(nlgn),数据容量一大,性能就会下降。
My thinking:我想我们只要找到k个距离最近的样本,和顺序并没有关系。笔者细想了一下,我么只要构建一个大小为k的数组或者队列,对于前k个元素,我们直接放进数组,后面的n-k个元素,我们找到存放在数组中的k个元素中最大值,将二者比较看是否替代。这样我们只需遍历一遍,复杂度降为O(n),也是一种小优化。

    伪代码:
    KnnNode[] dist=new KnnNode[k];
    for(int i=0->k){
        KnnNode temp=new KnnNode(distance);
        dist.append(temp)
    }
    for(the rest of test set){
        if(temp.distance < the maximum element in dist)
            dist[index of max]=temp;
    }

四、预测

方法如下展示:
数字手写识别——Java实现KNN算法
我们也可以在识别之后保存该样本,这样不能不断扩大数据集,让精度更高。


总结

虽然能在O(n)复杂度里实现Knn算法,但是我的knn延展性太差,我应该可以把这个knn的参数换成算好的距离,而不是传入的数组,这样就能将这个KNN封装好方便以后再用。
源代码参考地址:https://github.com/Gray-way/HandwritingRecognition