基于PVM的SLIQ算法的并行化研究.pdf

1、數(shù)據(jù)挖掘作為知識發(fā)現(xiàn)過程關(guān)鍵技術(shù)，已逐步得到廣泛應(yīng)用。分類是數(shù)據(jù)挖掘及CRM的重要組成部分。SLIQ串行算法是由IBMAlmaden研究中心提出的一種高速可伸縮的分類算法，廣泛應(yīng)用于大型商業(yè)的CRM、信用等級分級等領(lǐng)域。隨著應(yīng)用中數(shù)據(jù)量的迅速膨脹，采用并行技術(shù)是提高數(shù)據(jù)挖掘效率的一個重要途徑。本文首先分析了串行SLIQ算法的原理和特點，針對其不足提出了一些改進方法，然后在基于PVM的環(huán)境下實現(xiàn)了算法的并行化，分析了算法的時間復(fù)雜度和加速

2、比，提高了SLIQ算法的效率，具有一定的理論意義和實用價值。 串行SLIQ算法通過預(yù)排序和廣度優(yōu)先技術(shù)，能夠更加快速和準確地處理大量數(shù)據(jù)集，并能同時處理離散字段和連續(xù)字段。但是，原算法在計算決策樹節(jié)點的最佳分割點的時候，存在著對屬性和記錄的多余計算問題。本文提出應(yīng)該動態(tài)的刪除葉子節(jié)點的記錄以及當(dāng)前節(jié)點的祖先節(jié)點的分割屬性，從而可以明顯地減少不必要的計算以及屬性表在磁盤和內(nèi)存之間的IO交換操作。 由于難以解決數(shù)據(jù)挖掘中任務(wù)

3、劃分的問題，SLIQ算法并行化的主要方向是實現(xiàn)數(shù)據(jù)的并行。SLIQ算法采用了新穎的數(shù)據(jù)結(jié)構(gòu)，需要預(yù)先建立屬性表，所以應(yīng)該采取基于屬性的數(shù)據(jù)分割策略。算法在把屬性表和類表進行預(yù)先分配時采用的是靜態(tài)平衡策略，對數(shù)據(jù)的分配按照數(shù)據(jù)量平均分配，將連續(xù)屬性和離散屬性分別平均分配到各個結(jié)點上；在執(zhí)行分裂后，由于需要計算的屬性不斷減少，則采用了動態(tài)負載平衡的策略，通過消息傳遞的方式將部分計算任務(wù)分配給負載較輕的處理機單元。 通過對串行和并行算