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

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