數(shù)據(jù)密集型計算環(huán)境下數(shù)據(jù)分類算法研究.pdf

1、數(shù)據(jù)密集型計算隨著大數(shù)據(jù)時代的到來受到了業(yè)界的廣泛關(guān)注，而針對數(shù)據(jù)密集型計算環(huán)境下大數(shù)據(jù)的數(shù)據(jù)挖掘的研究卻仍然處于起步階段。目前針對數(shù)據(jù)密集型計算環(huán)境下數(shù)據(jù)挖掘的研究主要集中在如何利用大規(guī)模集群系統(tǒng)所具有的可伸縮性和容錯性等優(yōu)勢，實(shí)現(xiàn)高效的數(shù)據(jù)挖掘和管理功能。
　　本文首先闡述了數(shù)據(jù)密集型計算的特點(diǎn)和典型應(yīng)用，討論了數(shù)據(jù)密集型計算環(huán)境下數(shù)據(jù)挖掘的研究現(xiàn)狀和傳統(tǒng)分類方法，著重介紹了ID3、C4.5、CART、SLIQ和SPRINT等

2、典型決策樹算法和并行挖掘策略，同時也對Hadoop開源分布式系統(tǒng)架構(gòu)這一分布式數(shù)據(jù)處理的最佳平臺做了簡要的介紹。
　　本文提出了一種基于MapReduce編程框架和SPRINT算法的決策樹分類算法MR-DIDC，結(jié)合MapReduce的優(yōu)秀特性，使其更適用于數(shù)據(jù)密集型計算應(yīng)用，然后以一個實(shí)例為基礎(chǔ)介紹算法的運(yùn)行過程，最后指出了算法的改進(jìn)策略。MR-DIDC算法通過MapReduce編程框架的并行計算能力優(yōu)化決策樹節(jié)點(diǎn)擴(kuò)展過程、最佳

3、分裂屬性選擇及其分裂點(diǎn)計算和屬性列表分割，提高算法的執(zhí)行效率。MR-DIDC改進(jìn)和引入了以下幾種數(shù)據(jù)結(jié)構(gòu)，分別為直方圖、塊計數(shù)矩陣、塊哈希表和塊直方圖，通過改進(jìn)策略提高算法的并行性能。屬性列表的結(jié)構(gòu)與SPRINT算法相同，用來記錄屬性取值和所屬類標(biāo)的對應(yīng)關(guān)系，連續(xù)屬性的屬性列表需進(jìn)行預(yù)排序。連續(xù)屬性維護(hù)直方圖信息，直方圖為兩行，分別對應(yīng)Cabove和Cbelow，記錄當(dāng)前數(shù)據(jù)節(jié)點(diǎn)分裂點(diǎn)前后的類標(biāo)數(shù)量分布；離散屬性維護(hù)塊計數(shù)矩陣信息，塊計

4、數(shù)矩陣的行數(shù)為離散屬性值域的大小，每行表示當(dāng)前數(shù)據(jù)節(jié)點(diǎn)該屬性為某值時類標(biāo)的數(shù)量分布；塊直方圖是算法引入的新型數(shù)據(jù)結(jié)構(gòu)，用來記錄每一數(shù)據(jù)節(jié)點(diǎn)的類標(biāo)數(shù)量分布，輔助直方圖簡化分裂點(diǎn)的計算過程。分裂點(diǎn)的計算過程中，各數(shù)據(jù)節(jié)點(diǎn)間無需相互通信，可通過塊直方圖來獲得全局的類標(biāo)分布，減少各分片間互相通信而產(chǎn)生的I/O次數(shù)，有效的提高算法的數(shù)據(jù)可用性。塊哈希表在節(jié)點(diǎn)擴(kuò)展的過程中用來記錄當(dāng)前數(shù)據(jù)節(jié)點(diǎn)分裂點(diǎn)兩側(cè)的數(shù)據(jù)劃分。
　　最后通過實(shí)驗對MR-DI