基于MapReduce的分布式快速聚類(lèi)算法研究.pdf

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

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

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