KNN 在手写识别中的应用（Java 实现）

发表于 | 0 comments | 阅读次数

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

#KNN 概述

##什么是 KNN

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

##工作原理

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

##算法特点

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

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

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

##算法流程

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

  • 计算已知类别数据集中的点与当前点之间的距离

  • 按照距离递增次序排列

  • 选取与当前点距离最小的 K 个点

  • 确定前 K 个点所在类别的出现频率

  • 返回前 K 个点出现频率最高的类别作为当前点的预测分类

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

image

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

##简述

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

image

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

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

##具体实现

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

  • 首先我们需要将这些文本转换为向量，可以存储于数组中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
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
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 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
   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
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