云計算下的海量數(shù)據(jù)挖掘研究

云計算下的海量數(shù)據(jù)挖掘研究 關(guān)鍵詞 -云計算 ；數(shù)據(jù)挖掘 ；Hadoop；SPRINT；MapReduc 云計算的出現(xiàn)為愈來愈多的中小企業(yè)分析海量數(shù)據(jù)提供廉價的解決方案。在介紹基于云計算的Hadoop集群框架和數(shù)據(jù)挖掘技術(shù)中的 SPRINT 分類算法的基礎(chǔ)上詳細(xì)描述 SPRINT并行算法在Hadoop中的 MapReduce編程模型上的執(zhí)行流程并利用分折出的決策樹模型對輸入數(shù)據(jù)進行分類 引 言 云計算的應(yīng)用價值得到了包括 IBM、 Google在內(nèi)的眾多公司的重視其未來將像工業(yè)革命一樣影響計算機應(yīng)用的發(fā)展 目前云計算處于研究和應(yīng)用的初級階段 ll1云計算走出實驗室邁向商業(yè)化指日可待云計算的特點使存儲及數(shù)據(jù)商業(yè)化海量數(shù)據(jù)存儲和挖掘是一個具有理論和應(yīng)用價值的研究領(lǐng)域本稿在云計算開源框架下對虛擬銀行提出海量數(shù)據(jù)挖掘算法和應(yīng)用并給出了實施步驟 Hadoop及 MapReduce Had00p是 Apache下的一個開源軟件，它最早是作為一個開源搜索引擎項目Nutch的基礎(chǔ)平臺而開發(fā)的隨著項目的進展， Hadoop被作為一個單獨的開源項目進行開發(fā)。 HadooD作為一個開源的軟件平臺使得編寫和運行用于處理海量數(shù)據(jù)的應(yīng)用程序更加容易。 Hadoop Hado0D框架中最核心的設(shè)計就是 MapReduce和 HDFS MapReduce的思想是由 Google的一篇論文所提及而被廣為流傳的簡單的一句話解釋 MapReduce就是任務(wù)的分解與結(jié)果的匯總。 HDFS是 Hado0p分布式文件系統(tǒng)Hado0D Distributed File System 的縮寫為分布式計算存儲提供了底層支持 MapReduc MapReduce從它名字上來看就大致可以看出個緣由兩個動詞 map和 reduce map就是將一個任務(wù)分解成為多個任務(wù) reduce就是將分解后多任務(wù)處理的結(jié)果匯總起來得出最后的分析結(jié)果 這不是什么新思想其實在多線程、多任務(wù)的設(shè)計中就可以找到這種思想的影子 .不論是現(xiàn)實社會，還是在程序設(shè)計中 一項工作往往可以被拆分成為多個任務(wù) .任務(wù)之間的關(guān)系可以分為兩種 :一種是不相關(guān)的任務(wù) ,可以并行執(zhí)行 ；另一種是任務(wù)之間有相互的依賴 ,先后順序不能夠顛倒 .這類任務(wù)是無法并行處理的 在分布式系統(tǒng)中 機器集群就可以看作硬件資源池將并行的任務(wù)拆分然后交由每一個空閑機器資源去處理能夠極大地提高計算效率同時這種資源無關(guān)性對于計算集群的擴展無疑提供了最好的設(shè)計保證 任務(wù)分解處理以后那就需要將處理以后的結(jié)果再匯總起來。這就是 reduce要做的工作 圖 1展示了 MapReduce的工作模式 map負(fù)責(zé)分解任務(wù)， reduce負(fù)責(zé)將分解的任務(wù)進行合并 SPRINT算法改進 SPRINT算法很早就用于數(shù)據(jù)挖掘中的分類中在數(shù)據(jù)挖掘中具有很高的價值 31。在云計算下具有分布特點在對比其他算法的情況下，借用 SPRINT分類特性經(jīng)過改進用于云計算海量數(shù)據(jù)挖掘 決策樹是一樹狀結(jié)構(gòu) .從根節(jié)點開始 ,對數(shù)據(jù)樣本進行測試 .根據(jù)不同的結(jié)果將數(shù)據(jù)樣本劃分成不同的數(shù)據(jù)樣本子集 .每個數(shù)據(jù)樣本子集構(gòu)成一子節(jié)點 通過一系列規(guī)則對數(shù)據(jù)進行分類的過程它提供一種在什么條件下會得到什么值的類似規(guī)則的方法。 多數(shù)決策樹算法都包括兩個階段：構(gòu)造樹階段和樹剪枝階段。在構(gòu)造樹階段，通過對分類算法的遞歸調(diào)用產(chǎn)生一棵完全生長的決策樹。樹剪枝階段的目的是要剪去過分適應(yīng)訓(xùn)練樣本集的枝條。這里主要研究構(gòu)造樹的階段 決策樹的概念 SPKINT 改進后的基本思想 直方圖附屬在節(jié)點上用來描述節(jié)點上某個屬性的類別分布。當(dāng)描述數(shù)值型屬性的類分布時，節(jié)點上關(guān)聯(lián) 2個直方圖。 前者描述已處理樣本的類別分布后者描述未處理樣本的類別分布二者的值皆隨運算進行更新。當(dāng)描述離散屬性的類分布時，節(jié)點上只有一個直方圖 SPRINT剪枝采用了最小描述長度原則。 屬性表由一個屬性值、一個類別標(biāo)識和數(shù)據(jù)記錄的索引3個字段組成。記錄全部數(shù)據(jù)無法駐留于內(nèi)存可將屬性列表存于硬盤上。屬性表隨節(jié)點的擴展而劃分并附屬于相應(yīng)的子節(jié)點。 改進 SPRINT算法定義了兩種數(shù)據(jù)結(jié)構(gòu)，分別是屬性表和直方圖。 最佳分裂屬性的選擇 分裂指數(shù)是屬性分裂規(guī)則優(yōu)劣程度的一個度量 Gini指數(shù)方法能夠有效地搜索最佳分裂點提供最小 Gini指數(shù)的分割具有最大信息增益被選為最佳分割。在 SPRINT算法中采用了 Gini指數(shù)方法，這對于生成一棵好的決策樹至關(guān)重要。 Gini指數(shù)方法可以簡述如下： (1)如果集合 T包含 n個類別的 m條記錄，則其 Gini指數(shù)為： (2)如果集合 T分成 T1和 T2兩部分，分別對應(yīng) m1和 m2條記錄，則此分割的 Gini指數(shù)為 尋找分裂屬性及最佳分裂點： 根據(jù)以上方法得到所有屬性的候選最佳分裂點 選擇具有最小Gini值的侯選最佳分裂點。即為最終的最佳分裂點 相應(yīng)屬性為當(dāng)前分裂屬性。 SPRINT并行處理 在云計算下海量數(shù)據(jù)，多有并行數(shù)據(jù)發(fā)生。處理好并行數(shù)據(jù)，減少數(shù)據(jù)容錯性。 數(shù)據(jù)結(jié)構(gòu) SPRINT并行算法除了屬性表和直方圖外還需要引入哈希表數(shù)據(jù)結(jié)構(gòu)來存儲分割點兩側(cè)的數(shù)據(jù)記錄，為并行節(jié)點提供分割依據(jù)。哈希表第 i條記錄的值代表原數(shù)據(jù)中第 i條記錄被劃分到的樹節(jié)點號。哈希表分為兩項： (NodeID，SubNodeID)， NodeID代表樹節(jié)點號 SubNodeID表示當(dāng)前樹節(jié)點的兒子節(jié)點號默認(rèn) SubNodeID為 0時表示該記錄位于樹節(jié)點的左子節(jié)點為 1時位于樹節(jié)點的右子節(jié)點。 并行算法 希表。各分站點根據(jù)哈希表分割其他屬性列表，列表分割同時生成屬性直方圖。 SPRINT移植 經(jīng)過以上對 SPRINT算法改進后可以將算法移植到云計算的 MapReduce框架下進行分布合成處理。 SPRINT與 MapReduce水平劃分結(jié)合算法描述 從隊列取出第一個節(jié)點 N.初始階段所有數(shù)據(jù)記錄都在根節(jié)點 N.訓(xùn)練樣本只有一份 Hadoop的MapReduce要求輸入數(shù)據(jù)對訓(xùn)練樣本進行水平平均分割分割數(shù)目為 M份此工作由InputFormat完成。將數(shù)據(jù)塊劃分為InputSplit 對 1 M的訓(xùn)練集進行輸入格式化水平劃分后要對數(shù)據(jù)格式進行統(tǒng)一 InputFormat實現(xiàn)了RecordReader接口，可以將數(shù)據(jù)格式化為 對。具體格式化為 A ， ，這里A 表示數(shù)據(jù)表被平均分為 M份后，第 n份表中的 A列。 對應(yīng)第 n個表中屬性列表的數(shù)據(jù)單元的索引值，對第 n 個表中對應(yīng)屬性的值。Class 代表記錄的類別。這樣就可以做 map操作了。這里也是對訓(xùn)練樣本進行垂直分割 水平分割和垂直分割過程 例如 map生成了 R個 partition文件，key值為 A， B，C，這里會把partition中含有 A的交給同一個reduce， B和 C同樣 由 partition利用模計算將每個文件分配到指定的reduce上。 map操作過程的主要任務(wù)是對輸入的每個記錄進行掃描，將相同 key的鍵值對進行劃分歸類，寫到相應(yīng)文件中 reduce操作。對于連續(xù)屬性要對屬性值進行從小到大排序排序同時生成直方圖，初始階段為 0，為該節(jié)點對應(yīng)記錄的類分布每個reduce的任務(wù) 計算分裂點的 Gini值實時地更新直方圖。對于離散屬性。無需排序直方圖也無需更新 第一次掃描數(shù)據(jù)記錄就生成直方圖。計算每個分類子集的 Gini值。最后每個 reduce都會得出它所計算屬性列的最小分裂 Gini值及其分裂點 每個 reduce根據(jù)分裂點生成哈希表。哈希表化為鍵值對的數(shù)據(jù)結(jié)構(gòu)為 id 哈希表第 N條記錄的值代表原數(shù)據(jù)中第 N條記錄被劃分到的樹節(jié)點 將 reduce的輸出進行比較。選擇最小 Gini值所對應(yīng)的屬性及其分裂點和哈希表對原數(shù)據(jù)表進行分裂。從節(jié)點 N生成 N 和 N：節(jié)點，將 N ， N 壓入隊列 對 N1和 N2:循環(huán)進行 (1) (8)操作。數(shù)據(jù) 樣本都屬于一類或者沒有屬性 可操作或者訓(xùn)練數(shù)據(jù)樣本 太少，則返回 隊列如果 隊列為空 退出 程序 SPRINT 與 MapReduce垂直劃分結(jié)合算法描述 垂直劃分的 SPRINT算法和水平算法相近只是在輸人格式化階段，對每個 Inap的輸入是不同的，最終具有相同鍵的輸人被分配到唯一一個 reduce上 A、 B、 C和 D分別代表以屬性類別為 key的鍵值對的集合，經(jīng)過 map的分配任務(wù)。將具有相同鍵即 key通過 Partition分配到唯一一個 reduce中 這樣在每個 reduce中就可以對每個屬性列進行求解最小 Gini值和最佳分裂點，并