基于hadoop的KNN实现
13349009 陈榕涛
Part1设计概述
这次实践中,我打算在hadoop系统上实现KNN(KNearestNeighbors)算法。KNN算法比较简
单,一个testsample的label有K个与它最相似(距离最近)的trainsample的类别投票决定,各个
类别的权重为1:1。
我实现的版本是——把traindata分配到多个mapper上去计算,每个mapper计算其trainsample与
所有testsample的距离;然后在Combiner处做一遍本地的聚集,对于每一个testsample,从中选
择K个最小的距离,作为reduce的输入;最后reduce的时候,再次从所有的距离中,选择K个最
小的距离,投票决定类别。
Part2实现过程
1.数据
在实现的时候,考虑到一般是traindata比较庞大,所以我是将traindata作为map的输入,输入
格式按照默认的TextInputFormat,即读取每行作为一个mapper的输入。
而将所有的testdata全部读取放在内存中,为了在内存里只保存一个拷贝,我是将其作为
Mapper子类的一个static变量。另,其实testdata也可以做成分布式的,但是鉴于自己初学,还
没能对整个系统理解把握,所以就简单实现了。
2.各级的功能和keyvalue说明
注:Elem是自定义的一个类型,它包含三个属性:
1)两个sample之间的距离;2)主sample的label;3)从sample的label。
Mapper的输入:按照默认的的TextInputFormat读取的话,kv为(LongWritable,Text)。
Mapper的输出:kv为(IntWritable,Elem),key是指testsample的下标,唯一指代这个testsample
的键;value就是Elem,里面包含一个trainsample对于这个testsample的距离和两者的label。
本地Combiner的输入:同Mapper的输出(实质上二者就是相同的)。
本地Combiner的输出:kv为(IntWritable,Elem),解释同Mapper的输出,这里做的事情,是将
本地对于同个testsample的所有那些trainsample中,先选出K个距离最小的输出,这样可以较
少Reducer的负担和网络通信的负担。