walker

团队简介

本参赛团队队名为walker。其中队长为顾荣，队员分别为赵博、周文辉、杨书君，目前均为南京大学在读硕士研究生。我们来自南京大学计算机系“大数据与云计算技术”课题组，该课题组主要从事大数据并行计算模型和框架、并行计算系统性能优化、大数据索引和查询技术、并行算法、以及大数据与云计算应用系统研究开发。

作品简介

技术类第一题——调色板搜图

算法思想简介：

本道题目主要考察大规模图像检索问题。我们的调色板搜图系统分为两个阶段：粗选和精选。

粗选阶段：

目标：从给定的100万张图片中筛选出最有可能在最终100张图片中的前K（K>=100）张图，过滤掉其他图片。

方法：缩略图匹配。具体如下：

1. 离线处理步骤，按一定比例对给定的100万张图片，生成缩略图。

2. 缩略图匹配步骤，找出与调色板最匹配的K张图片的缩略图，供下面精选使用。

精选阶段：

目标：从上阶段粗选得到的K张图中精确检索出与调色板最匹配的前100张图片。

方法：处理上一步选取出的K图片（原图），从中检索出与给定调色板最匹配的100张图片（按匹配度排序），检索匹配算法和题目给定的一致。

算法流程图：

图1. 调色板搜图赛题的算法流程图

技术类第二题——多快好省的速递员

算法思想简介：

本道题目考察的是大规模路径规划问题。我们的设计的系统分为路况信息预测和路径规划两个阶段：

路况信息预测：

         这部分的工作包括生成地理位置信息以及对应的路况信息预测。这两个任务之间是相互独立的。生成地理位置信息比较简单，可以离线时计算得出。第二个任务是预测给定日期的各个时段的路况信息。为完成该目标，我们主要结合两方面信息，分别是历史路况数据和给定日期的部分真实路况信息。预测路况的算法采用的数据挖掘方面的聚类结合数值分析中的插值计算。

路径规划：

　  这部分的工作是根据给定的投递任务优化投递路径选择。路径搜索阶段同样有两个任务：投递顺序选择，搜索相邻投递点间的最短路径。其中，投递顺序选择任务调用搜索相邻投递点间的最短路径任务。第二个任务是搜索具体两地点直接的通行路径，我们没有使用比较耗时的Dijkstra算法，而是使用了快速的A*算法。因此大大加快了路径搜索的速度。考虑到有些路段会当天临时关闭的情况，在尽量保证路径选择优化的情况下，我们在算法中对这些临时关闭的路段进行了选择性的避让。

  上述的这些算法都是精心设计以基于MapReduce实现，充分利用了集群的计算能力。

算法流程图：

图1. 多快好省邮递员赛题的算法流程图

技术类第四题——难舍难分

算法思想简介：

本道题目是高维稀疏空间文本的分类问题，且在复赛实际测试中测试集含有一部分异类（未在训练集中出现过的类）。由于大量实践证实SVM针对高维空间数据较好，而且 分类器的速度较快OneClassSVM对于训练集中样本比例严重不平衡的问题有较好的分类效果，因此在我们使用了OneClassSVM+%20进行处理。训练阶段，对于多类（480类）问题，为了提高分类精度，我们针对每个类做了一个两类分类器；接着为了在预测阶段能较好地判别出异类，我们又将这480类训练样本看成同一类别的样本来训练处一个OneClassSVM模型。预测阶段，对于给定的待预测样本，我们首先用上面训练好的OneClassSVM判定其是否属于异类，如果属于异类则直接标为异类并结束预测，否则我们则分别用这480个分类器对待预测的样本进行类别相似度打分，最后选择打分最高的类别作为该样本的预测类别。为了提升训练和分类速度，上述所有算法都在MapReduce框架下实现。

算法流程图：