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

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

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

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