團隊簡介

本參賽團隊隊名為walker。其中隊長為顧榮，隊員分別為趙博、周文輝、楊書君，目前均為南京大學在讀碩士研究生。我們來自南京大學計算機系“大數據與云計算技術”課題組，該課題組主要從事大數據并行計算模型和框架、并行計算系統(tǒng)性能優(yōu)化、大數據索引和查詢技術、并行算法、以及大數據與云計算應用系統(tǒng)研究開發(fā)。

作品簡介

技術類第一題——調色板搜圖

算法思想簡介：

本道題目主要考察大規(guī)模圖像檢索問題。我們的調色板搜圖系統(tǒng)分為兩個階段：粗選和精選。

粗選階段：

目標：從給定的100萬張圖片中篩選出最有可能在最終100張圖片中的前K（K>=100）張圖，過濾掉其他圖片。

方法：縮略圖匹配。具體如下：

1. 離線處理步驟，按一定比例對給定的100萬張圖片，生成縮略圖。

2. 縮略圖匹配步驟，找出與調色板最匹配的K張圖片的縮略圖，供下面精選使用。

精選階段：

目標：從上階段粗選得到的K張圖中精確檢索出與調色板最匹配的前100張圖片。

方法：處理上一步選取出的K圖片（原圖），從中檢索出與給定調色板最匹配的100張圖片（按匹配度排序），檢索匹配算法和題目給定的一致。

算法流程圖：

圖1. 調色板搜圖賽題的算法流程圖

技術類第二題——多快好省的速遞員

算法思想簡介：

本道題目考察的是大規(guī)模路徑規(guī)劃問題。我們的設計的系統(tǒng)分為路況信息預測和路徑規(guī)劃兩個階段：

路況信息預測：

         這部分的工作包括生成地理位置信息以及對應的路況信息預測。這兩個任務之間是相互獨立的。生成地理位置信息比較簡單，可以離線時計算得出。第二個任務是預測給定日期的各個時段的路況信息。為完成該目標，我們主要結合兩方面信息，分別是歷史路況數據和給定日期的部分真實路況信息。預測路況的算法采用的數據挖掘方面的聚類結合數值分析中的插值計算。

路徑規(guī)劃：

　  這部分的工作是根據給定的投遞任務優(yōu)化投遞路徑選擇。路徑搜索階段同樣有兩個任務：投遞順序選擇，搜索相鄰投遞點間的最短路徑。其中，投遞順序選擇任務調用搜索相鄰投遞點間的最短路徑任務。第二個任務是搜索具體兩地點直接的通行路徑，我們沒有使用比較耗時的Dijkstra算法，而是使用了快速的A*算法。因此大大加快了路徑搜索的速度。考慮到有些路段會當天臨時關閉的情況，在盡量保證路徑選擇優(yōu)化的情況下，我們在算法中對這些臨時關閉的路段進行了選擇性的避讓。

  上述的這些算法都是精心設計以基于MapReduce實現，充分利用了集群的計算能力。

算法流程圖：

圖1. 多快好省郵遞員賽題的算法流程圖

技術類第四題——難舍難分

算法思想簡介：

本道題目是高維稀疏空間文本的分類問題，且在復賽實際測試中測試集含有一部分異類（未在訓練集中出現過的類）。由于大量實踐證實SVM針對高維空間數據較好，而且 分類器的速度較快OneClassSVM對于訓練集中樣本比例嚴重不平衡的問題有較好的分類效果，因此在我們使用了OneClassSVM+%20進行處理。訓練階段，對于多類（480類）問題，為了提高分類精度，我們針對每個類做了一個兩類分類器；接著為了在預測階段能較好地判別出異類，我們又將這480類訓練樣本看成同一類別的樣本來訓練處一個OneClassSVM模型。預測階段，對于給定的待預測樣本，我們首先用上面訓練好的OneClassSVM判定其是否屬于異類，如果屬于異類則直接標為異類并結束預測，否則我們則分別用這480個分類器對待預測的樣本進行類別相似度打分，最后選擇打分最高的類別作為該樣本的預測類別。為了提升訓練和分類速度，上述所有算法都在MapReduce框架下實現。

算法流程圖：