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

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

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

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

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