KNN图像识别

KNN:

邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。
kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

本项目将图像进行二值化处理，将得到的数据转化成向量，形成训练数据集。再将待识别的图片二值化，利用欧氏距离求相似度，最相似的即为识别结果。

欧氏距离：

具体步骤：

1.把训练数据（已经识别的数据）二值化。

2.把第一步得到的数据转化成向量，形成训练数据集。

3.把待识别的图片二值化。

4.把二值化后类似矩阵的数据转化为向量。

5.把待识别数据向量和训练数据向量进行求相似度运算,利用欧氏距离。

6.选取最相似的K个，根据标签统计个数，且计算平均相似度。

材料准备:

待识别图像集合：数字0~9 每个数字取100张。

 

 

具体代码实施:

1.图像二值化

package KNN;

import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.*;
import java.util.Arrays;

//
public class ImageDemo {
        public void arrayImage() throws IOException {
           for (int sum = 1; sum <=20; sum++) {
                File file = new File("D:\\idea\\BD1803_hadoop\\target\\test\\7_31.png");
                //读入20*20像素的图像
                BufferedImage image = ImageIO.read(file);

                File file1 = new File("D:\\idea\\BD1803_hadoop\\target\\test\\7.txt");
                FileWriter out = new FileWriter(file1);
                //转化为向量写入文件中
                int width = image.getWidth();
                int height = image.getHeight();

                for (int i = 0; i < height; i++) {
                    for (int j = 0; j < width; j++) {
                        int rgb = image.getRGB(i, j);
                        Color gray = new Color(105, 105, 105);
                        int rgb_gray = gray.getRGB();
                        if (rgb > rgb_gray) {
                            out.write("1");//颜色比灰色深设为1
                            out.flush();
                        } else {
                            out.write("0");//颜色比灰色浅设为0
                            out.flush();
                        }
                    }


                }
                out.close();

   
            }

        }

    public static void main(String[] args) throws IOException {
        ImageDemo demo = new ImageDemo();
        demo.arrayImage();

    }
}

 

转化后图像变为一串01数字，存储在文件中，每一个图片对应转化一个文件，由于长度限制，只截取部分。

2.将待识别图片也转化成如上形式，即可利用欧式距离算出结果集。

package KNN;

import java.io.*;
import java.util.Arrays;

public class Compare {
    public static void main(String[] args) throws IOException {
        char[] c = new char[400];
        FileReader in = new FileReader
                ("D:\\idea\\BD1803_hadoop\\target\\test\\7.txt");
        in.read(c);
        int sum = 0;

        File file = new File("D:\\idea\\BD1803_hadoop\\target\\arrayImages");
        File[] files = file.listFiles();

        BufferedReader br;

        PrintWriter out = new PrintWriter
                ("D:\\idea\\BD1803_hadoop\\target\\test\\rs.txt");//将结果集写入文件中

        String s = "";

        char[] d = new char[400];

        for (File a : files) {
            sum = 0;
            br = new BufferedReader(new FileReader(a.getPath()));
            while ((s = br.readLine()) != null) {
                d = s.toCharArray();
            }
            for (int i = 0; i < 400; i++) {
                int x = Integer.parseInt(Character.toString(c[i]));


                int y = Integer.parseInt(Character.toString(d[i]));

                if (x != y) {//逐点进行比较，不同加一，相同不加。
                    sum++;
                }

            }
            
            double s1 = Math.sqrt(sum);
            out.write(a.getName() + "," + 1/s1+1);
            //距离的结果代表是否相似，为了表示相似度，
            //一般进行求倒运算  1/（x+1） x为距离值，+1为了避免 分母为0 
            out.write("\n");
            out.flush();
        }
    }
}

该步骤生成的结果集如下:

 3.构建复合类型NumVal，该类型包括文件名跟相似度的值，在进行相似度降序排序时保证文件名也能拿得到。

package KNN;

import org.apache.hadoop.io.DoubleWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.io.WritableComparable;

import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
//构建复合类型，方便进行key的排序。
public class NumVal implements WritableComparable<NumVal> {
    private Text tag=new Text();
    private DoubleWritable val=new DoubleWritable();
    private Text g=new Text();//一个标记,分组的时候用得到    

    public NumVal(){}
    public NumVal(Text tag,DoubleWritable val){
        this.tag=new Text(tag.toString());
        this.val=new DoubleWritable(val.get());
    }

    public Text getTag(){
        return tag;
    }

    public DoubleWritable getVal(){
        return val;
    }

    public void setTag(Text tag) {
        this.tag = new Text(tag.toString());
    }

    public void setVal(DoubleWritable val){
        this.val=new DoubleWritable(val.get());
    }
    public NumVal(String tag, double val){
        this.tag=new Text(tag);
        this.val=new DoubleWritable(val);
    }
    @Override
    public int compareTo(NumVal o) {
        return o.val.compareTo(this.val);
    }

    @Override
    public void write(DataOutput dataOutput) throws IOException {
        tag.write(dataOutput);
        val.write(dataOutput);
    }

    @Override
    public void readFields(DataInput dataInput) throws IOException {
        tag.readFields(dataInput);
        val.readFields(dataInput);
    }
}

4.将结果集传入HDFS中进行MapReduce运算。

package KNN;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.conf.Configured;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.DoubleWritable;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.NullWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.TextInputFormat;
import org.apache.hadoop.mapreduce.lib.output.TextOutputFormat;
import org.apache.hadoop.util.Tool;
import org.apache.hadoop.util.ToolRunner;

import java.io.IOException;

public class SortMR extends Configured implements Tool{

    public static class SMapper extends Mapper<LongWritable,Text,NumVal,NullWritable>{
        @Override
        protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
            String[] arr = value.toString().split(",");
            String fileName=arr[0];//文件名
            String val=arr[1];//相似度
            Double d=Double.parseDouble(val);
            context.write(new NumVal(fileName,d),NullWritable.get());
        }
    }

    public static class SReducer extends Reducer<NumVal,NullWritable,Text,DoubleWritable>{
        @Override
        protected void reduce(NumVal key, Iterable<NullWritable> values, Context context) throws IOException, InterruptedException {
            for(NullWritable value:values){
                Text tag = key.getTag();
                DoubleWritable val = key.getVal();
                context.write(tag,val);//输出后结果对相似度全局有序。
            }

        }
    }

    public static void main(String[] args) throws Exception {
        ToolRunner.run(new SortMR(),args);
    }

    @Override
    public int run(String[] strings) throws Exception {
        Configuration conf=getConf();
        Job job=Job.getInstance(conf,"Sort_zj");
        job.setJarByClass(SortMR.class);

        job.setMapperClass(SMapper.class);
        job.setMapOutputKeyClass(NumVal.class);
        job.setMapOutputValueClass(NullWritable.class);

        job.setReducerClass(SReducer.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(DoubleWritable.class);


        TextInputFormat.addInputPath(job,new Path(conf.get("inpath")));
        TextOutputFormat.setOutputPath(job,new Path(conf.get("outpath")));

        job.setNumReduceTasks(1);

        return job.waitForCompletion(true)?0:1;
    }
}

第一个MapReduce程序结果如图：按相似度从大到小排列。

5.需要把结果输入到下一个MapReduce程序，但是需要他们进入同一个reduce形成一个整体， 这样才能拿到前二十个，不然默认按照文件名分组，各算各的，拿不到整体结果的前二十个。所以要设计分组方法，使他们进入同一个reduce。

分组代码：

package KNN;

import org.apache.hadoop.io.WritableComparable;
import org.apache.hadoop.io.WritableComparator;

public class SortGroupComparator extends WritableComparator {
    public SortGroupComparator(){
        super(NumVal.class,true);
    }

    @Override
    public int compare(WritableComparable a, WritableComparable b) {
        NumVal a1=(NumVal)a;
        NumVal b1=(NumVal)b;
        return a1.getG().compareTo(b1.getG());
    }
}

6.最后一个MapReduce较为复杂，分析一下，reduce端我们希望输出的是（文件名，平均相似度，出现次数）这样结果就一步到位，所以倒推到map端，map端输入还是上一个结果文件，输出可以为（NumVal，IntWritable（1）），每一个key分配一个1这样到reduce端可以利用HashMap进行出现次数的累加。

reduce端不可能输出三个值，所以要想办法构建复合类型，经思考，平均相似度跟出现次数关系较密切，所以选择构建<平均相似度，出现次数>复合类型，便于输出。而且在reduce端还要对文件名进行简单的处理，使数字开头相同的进入同一个map<>中。代码如下:

package KNN;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.conf.Configured;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.DoubleWritable;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.TextInputFormat;
import org.apache.hadoop.mapreduce.lib.output.TextOutputFormat;
import org.apache.hadoop.util.Tool;
import org.apache.hadoop.util.ToolRunner;

import java.io.IOException;
import java.util.*;
import java.util.stream.Stream;

public class FinalRSMR extends Configured implements Tool{

    public static class FMapper extends Mapper<LongWritable,Text,NumVal,IntWritable>{
        @Override
        protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
            String[] arr = value.toString().trim().split(",");
            String tag=arr[0].trim();
            Double d=Double.parseDouble(arr[1]);
            NumVal td=new NumVal(tag,d);
            td.setG(new Text("a"));//设置标记，标记相同进入同一个reduce
            context.write(td,new IntWritable(1));
        }
    }

    public static class FReducer extends Reducer<NumVal,IntWritable,Text,Text>{
        @Override
        protected void reduce(NumVal key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException {
            Map<String,AvgNum> map=new HashMap<>();
            Iterator<IntWritable> it = values.iterator();
            int i=0;
            while(i<20){//取前二十个
                IntWritable next = it.next();
                String tag = key.getTag().toString();
                String[] arr = tag.split("_");
                String fileName=arr[0];
                DoubleWritable val = key.getVal();
                if(!map.containsKey(fileName)){//第一次存进去
                    AvgNum an=new AvgNum(val,new IntWritable(1));
                    map.put(fileName,an);
                }else {
                    AvgNum an=map.get(fileName);//拿到AvgNum对象出去其中的属性
                    DoubleWritable old_avg=an.getAvg();
                    IntWritable old_num=an.getNum();
                    IntWritable new_num=new IntWritable(old_num.get()+1);
                    double sum=old_avg.get()*old_num.get()+val.get();//新的总和
                    double new_avg=sum/new_num.get();//新的平均相似度
                    AvgNum ana=new AvgNum(new_avg,new_num.get());//组合成新的AvgNum对象
                    map.put(fileName,ana);
                }
                i++;
            }
            Set<Map.Entry<String, AvgNum>> ent = map.entrySet();
            for(Map.Entry v:ent){
                context.write(new Text(v.getKey().toString()),
                        new Text(v.getValue().toString()));
            }
        }
    }

    @Override
    public int run(String[] strings) throws Exception {
        Configuration conf=getConf();
        Job job=Job.getInstance(conf,"F_zj");
        job.setJarByClass(FinalRSMR.class);

        job.setMapperClass(FMapper.class);
        job.setMapOutputKeyClass(NumVal.class);
        job.setMapOutputValueClass(IntWritable.class);

        job.setReducerClass(FReducer.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(Text.class);

        job.setGroupingComparatorClass(SortGroupComparator.class);
        //设置分组使他们进入一个reduce
        TextInputFormat.addInputPath(job,new Path(conf.get("inpath")));
        TextOutputFormat.setOutputPath(job,new Path(conf.get("outpath")));
        job.setNumReduceTasks(1);


        return job.waitForCompletion(true)?0:1;
    }

    public static void main(String[] args) throws Exception {
        ToolRunner.run(new FinalRSMR(),args);
    }
}

运行成功，结果如下:

成功得出，7为识别结果，但是从相似度结果来看，误差还是比较大，而且欧氏距离计算相似度只是很粗略的一种方法。应该加大测试样本量。

7.总结

本项目运用了欧氏距离计算相似度，先是通过二值化方法将图片在本地转化成01数组，之后将结果集传入集群中，对其进行倒序排序，之后需要提取样本前n个进行分析，但是如何在MR程序中提取结果集的前二十个就成了问题，MR本身的分组方法是按照key进行分组，这样到话结果集就会被分到许多reduce中进行运算，无法拿到整体结果的前20个。所以在这里牵扯到自定义分组的问题，我们需要设计一个分组方法将所有结果进入一个reduce进行后续计算，所以我们在Numval中设置了一个标记G,它仅仅为了分组使用。结果有待优化，优化方式，提升样本数量，改变算法。