并行大數據清洗過程優化范文

本站小編為你精心準備了并行大數據清洗過程優化參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《計算機學報》2016年第一期

摘要

數據質量問題會對大數據的應用產生致命影響，因此需要對存在數據質量問題的大數據進行清洗．MapReduce編程框架可以利用并行技術實現高可擴展性的大數據清洗，然而，由于缺乏有效的設計，在基于MapReduce的數據清洗過程中存在計算的冗余，導致性能降低．因此文中的目的是對并行數據清洗過程進行優化從而提高效率．通過研究，作者發現數據清洗中一些任務往往都運行在同一輸入文件上或者利用同樣的運算結果，基于該發現文中提出了一種新的優化技術———基于任務合并的優化技術．針對冗余計算和利用同一輸入文件的簡單計算進行合并，通過這種合并可以減少MapReduce的輪數從而減少系統運行的時間，最終達到系統優化的目標．文中針對數據清洗過程中多個復雜的模塊進行了優化，具體來說分別對實體識別模塊、不一致數據修復模塊和缺失值填充模塊進行了優化．實驗結果表明，文中提出的策略可以有效提高數據清洗的效率．

關鍵詞

大數據；多任務優化；海量數據；數據清洗；Hadoop；MapReduce

1引言

本節主要介紹研究背景及其意義、海量數據清洗系統、本文優化方法的主要思想、本文的貢獻與結構．

1．1研究背景及其意義現今企業的成功和社會的進步，越來越依賴于數據和對其所做的分析．為了獲得競爭優勢即使是小企業也會投入時間和精力來收集和分析數據．很多大公司都部署了自己的云服務平臺，國內比較著名的有百度云、阿里云、天翼云①等．但是如果一味地將精力投入到對數據所做的分析而不關注數據本身，很可能產生災難性的后果．統計表明，美國企業中1％～30％的數據存在各類錯誤和誤差［1］，醫療數據庫中13．6％～81％的關鍵數據不完整或陳舊［2］．根據市場研究公司Gartner的調查，全球財富1000強公司超過25％的關鍵數據不正確或不準確［3］．數據質量問題會使基于其的分析和研究毫無意義甚至還會產生災難性的后果，在美國由于數據錯誤引起的醫療事故每年使98000名患者喪生［4］．上述實例表明數據質量問題存在于社會生活的方方面面，數據清洗系統應運而生．在海量數據處理領域，MapReduce編程框架作為當下最流行的并行編程開發框架已被Google、Amazon、Yahoo！、Facebook以及國內的騰訊、阿里巴巴等大型互聯網公司奉為至寶．將Hadoop用于海量數據處理主要有如下優勢：易用性、高可擴展性、高容錯性．上述優勢使得基于MapReduce的海量數據清洗順其自然的產生了．海量數據上的數據分析往往需要相對高昂的硬件成本和時間成本，這就引起了人們對優化數據分析的興趣．當前已經有不少人開始研究大數據上的數據清洗系統，有對整個數據清洗系統進行研究［5－7］，也有對其中的數據一致性［8－10］，實體識別如文獻［11－14］等問題進行研究的．然而現在還沒有人對基于MapReduce的數據清洗系統的優化進行研究．現在幾乎所有的數據分析任務都可以用MapReduce編程框架來實現，但是在實現過程中往往會存在冗余的MapReduce，基于MapReduce的海量數據清洗系統也不例外．本文提出的基于任務合并的優化方法著眼于系統中冗余的MapReduce，從細節和流程的各個方面實施．

1．2海量數據清洗系統海量數據清洗系統如圖1所示，它在Hadoop平臺上實施，以一個靈活的結構來處理不同類型的數據質量問題，每種類型的數據質量問題都由一個或多個模塊來處理，由哈爾濱工業大學海量數據計算與研究中心提供源代碼．系統中的交互模塊提供一個輸入接口來輸入需要清洗的文件以及清洗數據的要求．結果展示模塊提供清潔數據的下載鏈接以及臟數據和清洗后的數據的對比情況．實體識別和真值發現模塊用于消冗，其中實體識別把指向同一現實世界實體的元組聚類，而真值發現用來在沖突中尋找出真實值．不一致檢測模塊發現數據中違反依賴規則的部分并且嘗試把數據修復到符合規則的狀態．數值填充部分檢測數據缺失部分并填充．用戶可以選擇合適的模塊來處理所遇到的數據質量問題。

1．3本文優化方法概要和其他優化方法本節首先給出基于任務合并的優化方法，然后對基于Hadoop平臺的海量數據清洗系統進行優化．一個實際的系統往往需要很多輪MapReduce來實現．有文獻表明，對于比較復雜的單一型人物，拆分開來執行的話性能反而更好．但是根據MapReduce編程方式的特點，往往需要將一個問題分解成很多簡單的任務，每一個任務由一輪MapReduce實現．在大多數情況下，這種“分解”是過度的，由此而產生冗余的MapReduce．將可以合并的任務進行適當的合并，并且在不改變原系統的算法復雜度與迭代可終止性等前提下，滿足可以減少原系統的MapReduce輪數和IO次數等條件進而達到優化的目的．與本文研究方向相同的工作最杰出的優化方法有MRShare［15－16］，后者是在前者的基礎上發展而來的優化方法并且實現過程復雜，優化效率提升不是很明顯．MRShare把多個共享相同的map輸入或輸出的任務合并成一個任務，減少掃描文件的次數，從而達到優化的目的．但當合并后的任務的較大的map輸出的sort代價高于合并之前的多個獨立的較小的map輸出的代價時，就不會有任何優化效果．本文提出的基于任務合并的優化技術針對冗余計算和利用同一輸入文件的簡單計算進行合并，通過這種合并可以減少MapReduce的輪數從而減少系統運行的時間．通過對整個系統的框架與流程進行優化設計，有效地提高系統的效率．

1．4本文的貢獻本文的主要貢獻有：（1）提出一種基于MapReduce的應用系統的優化方法．（2）對海量數據清洗系統中計算較為復雜的3個模塊進行討論并提出優化方案．（3）對海量數據清洗系統的各個模塊優化前后進行了大量的對比實驗．

1．5本文的結構本文第1節介紹背景、主要內容和本文結構；第2、3、4節詳細討論優化方法與實施過程；第5節給出實驗結果和分析；最后在第6節給出結論．

2優化的缺失值填充

在實際的生產生活中，數據缺失是一種不可避免的現象，尤其是在數據收集工作日趨自動化的今天．本模塊是一種利用樸素貝葉斯分類的缺失值填充機制．

2．1缺失值填充模塊介紹舉一個例子，假設一個學校有60％的男生和40％的女生．女生穿褲子的人數和穿裙子的人數相等，所有男生都穿褲子．一個人在遠處隨機看到了一個穿褲子的學生，那么該學生的性別是什么？（1）參數估計模塊整個缺失值填充系統是用貝葉斯分類的思想來計算出概率最大的取值作為填充值．參數估計模塊的任務是利用式（1）計算出所有的概率，其中P（X）對所有取值為常數，所以只需要計算P（X｜Ci）×P（Ci）即可．在各個取值的先驗概率未知的情況下，不妨假設其是等概率的，因此只需計算P（X｜Ci）即可。（2）連接模塊系統在填充模塊會根據式（2）計算出含有缺失值的元組在它的依賴屬性取值確定的所確定的各個待填充值的概率．但是由于MapReduce函數在map階段和reduce階段一次只能處理一條記錄，所以系統必須使依賴屬性取值和其條件概率關聯起來，這就是連接模塊存在的必要性和需要解決的問題．連接模塊的輸入數據為參數估計模塊的輸出數據和原待填充數據，輸出數據是將含缺失數據的元組中依賴屬性取值與該取值條件概率相關聯的文件．此模塊的輸入數據為原待填充數據和連接模塊的輸出，輸出數據為經過填充之后的數據．利用式（2）計算出每個Ci（待填充屬性可能的取值）對應的條件概率，選擇其中P（Ci｜X）概率最大的Ci進行填充．（3）填充模塊填充模塊由一輪MapReduce實現，首先將連接模塊的輸出結果和原始輸入數據以偏移量為鍵值進行連接運算，map階段和連接模塊類似，在此不再說明．reduce階段利用式（2）計算出每個Ci（待填充屬性可能的取值）對應的條件概率，選擇其中P（Ci｜X）概率最大的Ci進行填充．填充效果見圖3．以上是對缺失值填充模塊的簡要介紹，詳細介紹參考文獻［17］，本文僅對其離散類型的缺失值填充做考慮．

2．2系統分析與優化首先分析一下整個模塊各個子模塊之間的數據流和聯系紐帶．參數估計子模塊利用輸入數據中的不包含缺失數據元組來計算以依賴屬性的不同取值為條件的待填充屬性的各種取值的條件概率①．在計算填充值的過程中需要用到以各依賴屬性的當前取值為條件的待填充屬性的各種可能取值的條件概率②，②是①中的一組特定的值，②和①的聯系紐帶是依賴屬性的取值．而②和原始數據中的待填充元組之間的聯系是該元組的偏移量．因此在參數估計模塊和填充模塊之間增加了連接模塊．仔細觀察系統各階段數據流可以發現，在參數估計的map輸入和map輸出數據中均包含元組的偏移量，但是reduce輸出數據中只有屬性值和②．這種情況使系統必須通過增加一個連接運算才能將②與待填充元組的偏移量結合在一起．針對上述情況本文提出了一種將參數估計模塊和連接模塊的任務合并的優化方案，即在參數估計模塊就將輸出的條件概率與含有缺失值的元組偏移量關聯起來．其算法如下．下面舉例說明優化后的算法流程，表1為包含缺失值的數據，缺失值可能為y或n．前兩條元組不含缺失值，故僅將其按屬性拆分；第3條元組含有缺失值，我們在每種可能取值的情況下按屬性拆分，Map階段輸出結果見表2．Reduce階段檢查所有輸入數據的前綴，若不包含缺失值則進入條件概率計算環節；若包含缺失值則將其錄入likelihood（用于判定條件概率是否需要輸出）．最后選擇屬性值存在于likelihood中的條件概率進行輸出，輸出結果見表3．優化后的參數估計子模塊，Map階段的算法復雜度為O（n＋ML），其中n為不包含缺失值的元組的數量，M為包含缺失值的元組的數量，L為缺失值可能取值的數目．一般情況下Mn，故O（n＋ML）＝O（（1＋L）n）．因為L為一個遠小于n的常數，所以Map階段的算法復雜度為O（n）．Reduce階段的算法復雜度為O（n）．故整個參數估計子模塊的算法復雜度為O（n）．優化前后，參數估計子模塊的算法復雜度一直是O（n），填充子模塊未做優化．整個缺失值填充模塊的MapReduce輪數和IO次數均由優化前的3變為2，加速比為3／2，優化效果明顯．

3優化的實體識別

實體識別，就是識別出同一實體的不同表現形式．不同的數據來源對同一對象的表示形式往往有著不同的要求，并且在數據的存儲和傳遞過程中均會產生不可避免的錯誤，因此產生了同一實體的不同表現形式．關于MapReduce框架下的實體識別技術，現在已經有了相關研究工作［18－19］，但是他們只解決了異名實體識別問題，對同名問題沒有進行研究；而我們的工作可以同時解決了異名和同名問題．

3．1實體識別模塊介紹（1）預處理．系統讀入海量數據文件并進行預處理，給每一條輸入元組加上一個唯一的序號———實體ID，方便后續處理．（2）初步聚類．讀取預處理模塊生成的數據，按照相同屬性值進行初步聚類，生成屬性索引表．（3）實體識別．對實體進行識別，對同一屬性索引表中的實體對計算相似度并與閾值進行比較，大于閾值的相似對輸出成相似對集合文件．（4）實體劃分．依據相似對集合文件生成圖，通過對圖的劃分獲得實體劃分結果．以上是對實體識別模塊的簡要介紹，詳細介紹參考文獻［20］

3．2系統分析與優化通過研究發現初步聚類模塊和實體識別模塊，對預處理結果重復利用了N次（N為待處理數據每條元組包含的屬性個數），而且后續的實體識別模塊也是在單一屬性上處理的．如果將預處理模塊和實體識別模塊看作一個整體（系統實際應用中也是這樣的），那么就是對輸入數據文件掃描多次，并且只能利用輸入數據中的一部分，系統對輸入數據的利用率很低．此外系統每次分配任務都需要消耗額外的資源．我們需要將分開處理各個屬性的初步聚類和實體識別合并成一次能處理所有屬性進而只運行一輪就能處理每條元組所有屬性的解決方案．為此本文針對實體識別模塊提出的優化思想是：在初步聚類子模塊一次處理所有屬性，生成所有屬性值的屬性索引表．這樣就能將原來按屬性分開處理的預處理和實體識別合并起來．下面給出具體的優化方案和算法．（1）初步聚類子模塊，map階段不是僅僅輸出第i個屬性值，而是將所有屬性值都輸出．但是為了區分初步聚類產生的結果———屬性索引表集合中的1101期楊東華等：基于任務合并的并行大數據清洗過程優化實體ID是來自不同的屬性，系統在map輸出數據的key上做了一些改動，在原key前加上了一個前綴，由“屬性值”變成“屬性序號＄屬性值”．因為MapReduce是按照key進行分類的，所以只有同一屬性的具有相同屬性值的實體才會進入同一屬性索引表．reduce階段將屬性序號作為實體ID的前綴加在實體ID中．以下是優化后的初步聚類算法．其中實體ID是每個元組的編號，在預處理階段為每一個元組（一行數據）設定唯一的實體ID．屬性ID是屬性在元組中的順序．下面舉例說明優化后的算法流程，待識別數據如表4所示．Map階段將所有元組的按屬性拆分后輸出，結果如表5所示．屬性值相同的實體會進入同一個reduce，并輸出成屬性索引表，如表6所示。優化后的初步聚類模塊，map階段的算法復雜度為O（n（x＋x2）），其中x為屬性個數，實際應用中x為一個很小的常數值，故其計算復雜度為O（n）．reduce階段除了在附加的讀取屬性序號外沒有任何改動，其計算復雜度為O（n）．綜上整個初步聚類模塊的算法復雜度為O（n）．（2）實體識別子模塊，因為整個實體識別模塊是在初步聚類生成的屬性索引表中進行的，而初步聚類模塊的改動保證了同一屬性的具有相同屬性值的實體ID聚集在同一個屬性索引表中，所以這一模塊的算法不需要修改．除了在第3個MapReduce的reduce階段去除實體ID中包含的前綴外，沒有任何更改．這樣做的目的是為了使同一實體的相似度能夠在第4個MapReduce中匯合．整個實體識別模塊的算法沒有經過改動，所以其算法的時間復雜度仍保持O（n）．由于本文只對系統Hadoop上運行部分進行優化處理，所以將實體劃分模塊視作常量．在時間復雜度方面，從上一小節對實體識別子系統的介紹和本小節前面的一部分的優化方案中算法的計算復雜度可以看出，優化前后沒有改變各個模塊以及各個模塊內部的各個MapReduce的計算復雜度．優化前的MapReduce輪數為1＋N（1＋4）＝5N＋1，優化之后的MapReduce輪數為1＋1＋4＝6，加速比為（5N＋1）／6．正常情況下N大于1，所以加速比大于1，并且N越大加速效果越明顯．IO次數也由先前的5N＋1次變為6次，IO次數減少使得系統用于IO的時間減少．另外由于MapReduce的輪數減少，系統用于任務調度的時間和資源也相應減少．綜上，從理論上講，通過本文的提供的優化方案能產生明顯的優化效果．

4優化的不一致數據修復

在實際的數據庫系統及相關應用中由于種種原因，其中包含的數據違反最初定義的完整性約束，所以存在大量不一致數據．本系統利用數據依賴理論中的條件函數依賴原理，定義完整性約束，利用完整性約束進行不一致數據修復．本文的重點在于提高不一致數據修復模塊的性能和效率，使之一致．至于如何保證這樣的修改過程是正確的，是由條件函數依賴理論所決定的，本文相關的理論證明和推導詳見文獻［9－10］．

4．1不一致數據修復模塊介紹不一致數據修復模塊步驟的簡要介紹如下：（1）系統讀入待修復的海量數據文件和cfds文件并進行預處理，將數據格式更改成符合系統要求的格式并對cfds進行初步檢測，方便后續處理．（2）對預處理結果中的數據文件進行檢測與修復，得到初次修復結果．（3）對初次修復結果進行檢測，判斷修復工作是否引入了新的不一致．若引入了新的不一致則返回步驟（1），否則進入步驟（3）．當然為了避免系統陷入死循環，系統為檢測與修復的次數設置了一個上限．（4）對修復結果進行后處理，將數據格式更改成數據的原始格式，使得修復結果能正常被其他系統使用．以上是對實體識別模塊的簡要介紹，詳細介紹見參考文獻［21］．

4．2系統分析與優化不一致數據修復子系統的4個模塊中除第1個模塊的CFD一致性檢測子模塊外都是在MapReduce編程框架上實現的，在本文的研究范圍內．本模塊的一個重要缺點是沒有掌握MapReduce編程“分解與合并”的精髓，將本來僅需要一個Map或者一輪MapReduce便可完成的任務拆分成一輪或多輪MapReduce，由此使系統效率下降．為此我們在不改變系統算法復雜度的條件下進行任務合并．（1）預處理模塊預處理模塊的臟數據預處理子模塊功能很簡單，就是給輸入數據建立索引，實施過程中沒有涉及到數據的分解與合并，可以通過一個map函數實現．算法如下．（2）不一致數據檢測與修復模塊不一致數據的檢測與修復模塊中常量違反檢測與修復模塊通過一輪MapReduce實現，map階段將元組重新分發了M份（M為輸入元組發生常量違反的次數），盡管M實際值一般不大，對reduce階段的計算復雜度幾乎沒有影響．但是M的存在會使中間數據量擴大M倍，對系統通信造成很大負擔．更重要的是在系統計算出建議修復值的同時就可以將其修復，那么就沒有必要將找到建議修復值的過程和修復過程分開．為此本文提出的優化方案是利用一個map函數實現常量違反檢測與修復子模塊．將常量違反與修復子模塊通過一個map函數實現之后，經過常量違反修復的數據直接進入變量違反修復環節．兩者輸入數據的格式是相同的，假如原始數據中不存在常量違反，那么兩者輸入文件就是完全相同的．基于上述觀點，本文提出了將常量違反修復與變量違反修復合并的優化方案．在這個優化方案中常量違反修復位于原變量違反修復的第1輪MapReduce的前端，讓常量違反的結果在Map函數內部直接應用于變量違反．算法如下．其中，offset為元組索引值，tuple表示該條元組，fix＿tag為修復標志，用來區分是否發生違反需要修復，0表示發生違反需要修復，1表示不需要修復．cfdindex是tuple違反的CFD的序號，ptindex是該tuple違反的CFD的模式表中的模式元組序號，attrindex標志該tuple的不一致數據項的屬性序號，fixvalue即為該屬性值應修復的結果．下面舉例說明優化后的算法流程，待修復數據如表7所示．為了便于說明，本例中僅使用1條cfd和一個tp，分別為1：（［CC，AC，PN］→［STR，CT，ST］）和T1：01，908，＿，＿，MH，＿．Map階段將每一條輸入的待修復元組與模式元組tp作比較，進行常量違反修復，然后再進行變量違反修復．第1條元組沒有發生常量違反，遂進入變量違反修復環節，其map輸出為表8中第1行．第2條元組發生常量違反，經常量違反修復進入變量違反修復環節，其map輸出為表8中第2行．下同．在時間復雜度方面，從預處理小節和本小節優化方案中算法的計算復雜度可以看出，優化前后沒有改變各個模塊以及各個模塊內部的各個MapReduce的計算復雜度．在MapReduce輪數和IO次數方面，系統的MapReduce輪數由優化前的1＋1＋2＋1＋1＋1＝7變成優化后的1＋2＋1＋1＝5．僅從MapReduce輪數來看系統的加速比為7／5．此外系統的優化工作還使得預處理模塊的MapReduce變成了map，這也會相應地減少系統的運行時間．隨著MapReduce輪數的減少，系統的IO次數也相應地減少，這也使得系統的IO負擔減小。綜上所述，通過本文提供的優化方案，不一致修復子系統會獲得理想的優化效果．

5實驗結果

整個系統在Ubuntu12．04．1操作系統中的Hadoop1．2．1平臺上，用java語言實現，軟件開發環境為Eclipse．實驗運行的集群采用12個節點，1個tasktraker（namenode），11個jobtracker（data－node）．集群由12臺機器組成，硬件環境為Inteli73770處理器，主頻為3．4GHz，內存8GB，1TB硬盤空間．

5．1實體識別優化實驗為了使系統的優化效果更有說服力，所有實驗數據是來自DBLP的真實數據集．針對系統的特點，實驗分別從擴展性、集群的并行化程度和數據的屬性個數3個方面驗證系統的優化效果．DBLP的數據規模并不大，看似不需要在Hadoop上實現．但大家公認的數據源往往數據量比較小，使用DBLP數據集的意義不是因為其規模而是在于DBLP數據集是真實數據，這樣做可以增加本文實驗結果的可信度．

5．1．1擴展性實驗本實驗考慮數據集合大小對優化效果的影響，實驗采用由真實數據集DBLP數據集，選擇其中的title，authorandco－author，journalorurl這3個屬性，選擇大小分別為13．2MB、32．3MB、64．9MB、97．1MB、128．9MB的數據作為實驗數據．實驗中各屬性的權值分別為0．9、0．05、0．05，實驗結果如圖7所示．實驗中對比了基本的實現（Nave）、文獻［19］中的BlockSplit和PairRange與基于本文中任務合并的優化方法優化后的實體識別4種方法在不同數據集合大小下的運行結果．隨著數據集合的增大，優化前后系統的運行時間都在增加，但是優化前和優化后系統運行時間的比值（加速比）均在2．3左右．這是因為本次實驗所使用的數據具有3個屬性，按照2．2節中對優化效果的分析，應具有的理論加速比為（5×3＋1）／6＝2．67與實驗結果一致．由于基于BlockSplit和Pair－Range方法的實體識別實現過程的運行時間比基于任務合并的優化方法復雜，故其運行時間均比本文提出的優化方法對應的運行時間長．本實驗說明優化設計方案有良好的擴展性．

5．1．2集群的并行化程度對優化效果的影響實驗考慮集群中Reduce個數對優化效果的影響，實驗采用由真實數據集DBLP數據集，選擇其中的title，authorandco－author，journalorurl這3個屬性，選擇大小分別為128．9MB含有100000條記錄的數據作為實驗數據．實驗中各屬性的權值分別為0．9、0．05、0．05，設置Reduce個數為2、4、6、8、10，實驗結果如圖8所示，在不同的并行化程度下優化效果明顯．從圖8中可以看出系統運行時間隨并行化程度的增強而變長，這不符合大家普遍認為的“并行化程度越高，系統運行時間越短”的常識．產生這一現象的原因是，實驗數據集數據量較小，增加系統的并行度給系統帶來的開銷要大于由此帶來的好處．無論如何，系統在不同的并行度下達到了大約2．3的加速比，優化效果符合預期．5．1．3數據集的屬性個數對優化效果的影響針對優化方案的主要思想：充分利用輸入記錄中的所有屬性，設計了本實驗．實驗研究輸入元組中的屬性個數對優化效果的影響．實驗結果如圖9所示，在處理同樣大小（記錄條數）的記錄時，隨著記錄中包含的屬性的增多，優化效果越來越好．從上述數據可以看到：當處理的元組包含一條屬性時，系統的優化效果最差，比優化前運行效率還要低；但是隨著屬性的增加優化效果越來越好．本文的優化工作針對的是系統在處理多屬性時不能充分利用輸入數據，并且通過循環處理每一個屬性增加了MapReduce輪數；但是處理單屬性元組時優化后的方案產生的中間數據量多于優化前，并且處理過程變得更加復雜，因此產生了上述實驗現象．

5．2不一致數據數據修復優化實驗為了驗證系統在真實生產環境中的工作狀態，實驗采用來自真實數據集Adult的數據和由TPC－H生成的數據集．進行了在Adult數據集上的加速比驗證實驗、在人工數據集上的擴展性和并行性驗證實驗．

5．2．1加速比實驗實驗采用條件函數依賴總共包含2條cfd，共有5條模式元組．根據cfd及其模式元組為來自Adult數據集中的無缺失值元組注入錯誤，使其違反一條或者多條約束．實驗條件和實驗結果如表9所示，通過實驗證明系統在真實數據集上的加速效果明顯，符合優化方案設計預期．此次實驗加速比為1．39，理論加速比大于1．4，優化效果符合預期．

5．2．2擴展性實驗為驗證優化工作在不同大小的數據集上同樣有明顯的優化效果設計了本實驗．實驗利用了由TPC－H生成的lineitem．tbl表中的5個屬性生成的數據集，CFDs由一條cfd包含2條tp構成．實驗結果如圖9所示，可見隨著數據集合的增大優化效果會變好，說明優化設計方案有良好的擴展性．從圖9可以看出優化前系統運行時間隨數據集增加呈線性增加，優化后系統運行時間隨數據集的增加也呈線性增加，但前者的斜率更大．此外，系統優化前后的加速比從1．59一直上升到2．20．一方面，優化前各個模塊的計算任務相當，但是優化工作大大減輕了除不一致數據檢測與修復模塊之外各模塊的負載；另一方面，實驗中為了突出數據集的大小對系統運行時間的影響，僅設置Reduce個數為2，故隨著數據集的增大優化前的系統率先滿負荷運行．從而出現了圖10中對比鮮明的實驗結果。

5．2．3并行性實驗為驗證并行程度對優化效果的影響，設計了本實驗．實驗利用了由TPC－H生成的lineitem．tbl表中的5個屬性生成的數據集，CFDs由一條cfd包含2條tp構成，詳見圖11．從圖10可以看出系統在并行度較低（Reduce個數為2）的情況下加速比最高達到2．20，之后隨著系統并行化程度增高優化效果變差，加速比降低．并且優化前的系統隨著系統的并行度的提高使得運行時間縮短，而優化后的系統基本保持不變．這是因為優化之前的系統處理數據的能力減弱，很容易滿負載運行，只能通過增加系統的并行化程度提高數據處理的效率，故隨著并行度增加系統運行時間減小；而優化后的系統吞吐量大，與處理和前者相同的數據一直都沒有處于滿負載狀態運行，故增加系統的并行度帶來的好處不明顯．

5．3缺失值填充優化實驗為了驗證系統在真實生產環境中的工作狀態，本文的實驗采用來自真實數據集Adult（www．archive．ics．uci．edu／ml／datasets．html）的數據和由TPC－H生成的數據集．進行了在Adult數據集上的缺失率對優化效果的驗證實驗、在人工數據集上的擴張性實驗和并行性驗證實驗．

5．3．1缺失率對優化效果的影響實驗主要研究不同的數據缺失率對優化結果的影響，通過將完整數據集按一定的比例（缺失率）隨機置空數據生成實驗所需的各種缺失率的數據．本文選取其中9個離散屬性，缺失屬性有7種取值，實驗結果見圖12．在圖中所示缺失率下，加速比穩定在1．5左右，與本模塊的理論加速比3／2相吻合．

5．3．2擴展性驗證實驗本實驗利用由TPC－H生成的數據表lineitem．tbl選取其中5個屬性，分別選擇不同的記錄條數生成實驗所需的數據．圖13所示實驗結果表明，無論優化前后，系統的運行時間均隨數據集的增大而增大，但是加速比均保持在1．5左右，與本模塊的理論加速比相吻合．

5．3．3并行性驗證實驗為了驗證系統在不同并行化程度下的優化效果，設計了本實驗．實驗利用由TPC－H生成的lineitem．tbl數據表，數據表共包含5個屬性，3000000條元組．隨機置空數據表第1列5％的數據（缺失率5％），記錄在不同的并行化程度下系統的優化效果．實驗結果見圖14．在給定數據集上，系統優化前后的運行效率都未隨著并行化程度的提高而變好．這是因為對于特定大小的數據集最適宜的Reduce數目是確定的，一味地提高并行化程度只會給系統帶來更多地任務分配的開銷．無論如何，在不同的并行化程度下優化效果明顯．

6結論

雖然整個行業對Hadoop的研究和使用已經有了相當的積累，但是由于使用者對MapReduce編程框架理解不夠深刻，所以利用MapReduce設計的軟件系統大都效率低下．為此本文提出了一種針對MapReduce編程框架設計的系統的優化方法，并通過了在海量數據清洗系統上的實施．本文提出的優化方法僅需對原系統解決問題的思路稍作改動，幾乎不影響其算法復雜性，通過減少MapReduce輪數和IO次數達到優化的目的．優化方法簡單，實用性強．未來的工作包括將這種思想利用到更多基于MapReduce的系統中，對實驗結果進行更為深入的分析以發現本文提供的優化方法的不足從而提出更好的優化方法．

作者：楊東華 李寧寧 王宏志 李建中 高宏 單位：哈爾濱工業大學計算機科學與技術學院 哈爾濱工業大學基礎與交叉科學研究院