數(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)勢，實現(xiàn)高效的數(shù)據(jù)挖掘和管理功能。
　　本文首先闡述了數(shù)據(jù)密集型計算的特點和典型應用，討論了數(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ù)密集型計算應用，然后以一個實例為基礎(chǔ)介紹算法的運行過程，最后指出了算法的改進策略。MR-DIDC算法通過MapReduce編程框架的并行計算能力優(yōu)化決策樹節(jié)點擴展過程、最佳

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

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