[發明專利]一種基于Hadoop的并行k近鄰分類方法

無效

• 申請號: 201210071445.X
• 申請日: 2012-03-19
• 公開（公告）號: CN102622446A
• 公開（公告）日: 2012-08-01
• 發明（設計）人: 高陽;楊育彬;王靈江;商琳
• 申請（專利權）人: 南京大學;南京大學江陰信息技術研究院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 夏雪

技術領域

本發明涉及一種基于Hadoop的并行k近鄰分類方法。

背景技術

k近鄰分類方法是一種廣泛應用并行之有效的分類方法。如何處理海量數據規模的分類，如何高效地完成此類數據挖掘任務具有重大的研究價值。現有的技術是在Hadoop的Mapper端并行計算測試數據與所有訓練數據的距離，然后在Reducer端接收以測試數據為key的，距離和類標為value的數據，然后確定每個測試數據的k近鄰，最終確定測試數據的分類結果。該技術簡單易用，但其中間的傳輸數據過于龐大，特別是對于海量數據來說，基本是不可能完成的任務，所以必須解決實際應用中的效率問題。

發明內容

發明目的：針對上述現有技術存在的問題和不足，本發明的目的是提供一種基于Hadoop的并行k近鄰分類方法，能夠有效地解決海量數據的分類問題，大大提高分類的速度。

技術方案：為實現上述發明目的，本發明采用的技術方案為一種基于Hadoop的并行k近鄰分類方法，包括如下步驟：

(1)數據預處理；

(2)在Hadoop各個節點的Mapper端并行計算一個測試數據與位于該節點的訓練數據的距離；

(3)在所述Mapper端用選擇算法確定該測試數據的局部k近鄰數據，將所有局部k近鄰數據發送到Hadoop各個節點的Reducer端；

(4)在所述Reducer端接收該測試數據的所有局部k近鄰數據，用選擇算法確定全局k近鄰數據；

(5)利用所述全局k近鄰數據對該測試數據進行分類，得到該測試數據的分類結果；

(6)重復執行步驟(2)至(5)，得到所有測試數據的分類結果。

所述局部k近鄰數據可為(key，value)，其中key為測試數據，value為所述距離和訓練數據的類標的組合數據。

所述步驟(5)中，分類的依據可以是D-F理論。

有益效果：本發明充分利用數據密集的特性，采用并行化計算局部k近鄰數據，進而獲取全局k近鄰數據的方法。實驗結果表明，本發明方法能夠大大減少各個節點之間的數據傳輸量，從而大大提升分類效率；對于處理大規模數據的分類問題具有良好的效果，具有很好的加速比。

附圖說明

圖1為本發明方法的流程圖；

圖2為本發明方法與現有方法的分類時間的比較示意圖：測試數據為4.4M，訓練數據為39.7M的分類時間比較(縱坐標為分類時間/s，橫坐標為節點數)；

圖3為本發明方法與現有方法的運行速度的比較示意圖：測試數據為10.8M，訓練數據為97.8M的分類時間比較(縱坐標為分類時間/s，橫坐標為節點數)；

圖4為在數據量很大的情況下本發明方法在節點數不同的情況下所具備的加速比與理想加速比的比較示意圖：測試數據為4.4M，訓練數據為3.9G的加速比(縱坐標為加速倍數，橫坐標為節點數)。

具體實施方式

下面結合附圖和具體實施例，進一步闡明本發明，應理解這些實施例僅用于說明本發明而不用于限制本發明的范圍，在閱讀了本發明之后，本領域技術人員對本發明的各種等價形式的修改均落于本申請所附權利要求所限定的范圍。

如圖1所示，下面詳細說明本發明方法的步驟：

步驟1，數據預處理，例如計算文本數據的TF-IDF值。

步驟2，在Hadoop各個節點的Mapper端并行計算一個測試數據與位于該節點的訓練數據的距離(例如對于文本數據，計算其余弦距離；對于向量型數據，計算其歐幾里得距離)。

步驟3，在Mapper端用選擇算法確定該測試數據的局部k近鄰數據，以測試數據為key，距離和訓練數據的類標的組合數據(<距離，類標>的形式)為value，組成數據對，將所有局部k近鄰數據發送到Reducer端。

步驟4，在Reducer端接收同一個key的所有values，根據values里面的距離，用選擇算法確定最終的全局k近鄰數據。

步驟5，根本D-F理論，利用全局k近鄰數據對該測試數據進行分類，確定其類標。

步驟6，重復執行步驟2-5，得到所有測試數據的分類結果。