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