基于MapReduce的分布式快速聚類算法研究.pdf

1、隨著信息技術的高速發(fā)展，數(shù)據(jù)規(guī)模呈現(xiàn)指數(shù)級增長態(tài)勢，傳統(tǒng)聚類算法面臨巨大的挑戰(zhàn)。一是海量數(shù)據(jù)內的噪聲雜、冗余度高、價值密度低，聚類算法的準確率不高；二是串行聚類算法面對海量數(shù)據(jù)時，搜索鄰域代價巨大，執(zhí)行效率無法適應實際需求。針對上述問題，本文充分分析數(shù)據(jù)特點，基于MapReduce大數(shù)據(jù)處理框架，設計了分布式快速聚類算法，實現(xiàn)了高效、高精度的并行數(shù)據(jù)聚類。
　　針對海量數(shù)據(jù)中冗余度高，無價值數(shù)據(jù)繁多的問題，本文提出一種基于 Map

2、Reduce的分布式數(shù)據(jù)約減算法。通過一種新的抽樣算法計算數(shù)據(jù)點的矩形域和抽樣域，并在抽樣域中確定樣本數(shù)據(jù)，然后對樣本數(shù)據(jù)進行擴展抽樣來達到約減原始數(shù)據(jù)集的目的，最后提出一種代表性驗證策略來檢驗樣本集，從而解決海量數(shù)據(jù)聚類產生巨大I/O開銷和網絡開銷的問題。
　　針對搜索最近鄰代價消耗大，聚類執(zhí)行效率低的問題，本文利用Map任務對樣本數(shù)據(jù)集進行相等大小的數(shù)據(jù)劃分，Reduce任務對數(shù)據(jù)子集進行局部密度聚類，因此針對單節(jié)點提出基于擴

3、展區(qū)域查詢的密度聚類算法。首先通過基于固定網格的擴展區(qū)域查詢方法，確定數(shù)據(jù)點最近鄰和反最近鄰的鄰域關系，建立每個數(shù)據(jù)點的影響空間域，然后提出異常點判定函數(shù)，使算法能夠準確地識別噪聲點和邊界點。
　　Reduce聚類任務結束后輸出局部聚類結果，為得到面向整個數(shù)據(jù)集的全局聚類結果，本文提出一種基于簇間距離的局部類簇合并算法，通過簇間距離的計算確定局部類簇間的分布關系，得到可以兩兩合并的局部類簇對，然后根據(jù)連通子圖發(fā)現(xiàn)方法合并局部類簇對