大數據下數據預處理方法研究

孔 欽，葉長青，孫 赟

(南京大學，江蘇 南京 210089)

0 引 言

大數據中蘊含的寶貴價值成為人們存儲和處理大數據的驅動力。在《大數據時代》一書中指出了大數據時代處理數據理念的三大轉變，即要全體不要抽樣，要效率不要絕對精確，要相關不要因果[1]。海量數據的處理對于當前存在的技術來說是一種極大的挑戰。大數據的涌現使人們處理計算問題時獲得了前所未有的大規模樣本，但同時也不得不面對更加復雜的數據對象。數據預處理作為數據分析、挖掘前的重要數據準備工作，可以保證數據挖掘結果的準確性和有效性。

1 研究背景

大數據環境下，來自異構系統的原始數據中存在若干問題：

(1)雜亂性。原始數據是從各個實際應用系統中獲取的，由于各應用系統的數據缺乏統一標準的定義，數據結構也有較大的差異，因此各系統間的數據存在較大的不一致性，往往不能直接拿來使用。

(2)重復性。是指對于同一個客觀事物在數據庫中存在其兩個或兩個以上完全相同的物理描述。這是應用系統實際使用過程中普遍存在的問題，幾乎所有應用系統中都存在數據的重復和信息的冗余現象[2]。

(3)模糊性。由于實際系統設計時存在的缺陷以及一些使用過程中的人為因素，數據記錄中可能會出現有些數據屬性的值丟失或不確定的情況，還可能缺失必需的數據而造成數據不完整。在實際使用的系統中，存在大量的模糊信息，有些數據甚至還具有一定的隨機性質。

如前所述，因為數據類型和組織模式多樣化、關聯關系繁雜、質量良莠不齊等內在的復雜性，使得數據的感知、表達、理解和計算等多個環節面臨著巨大的挑戰。因此，數據預處理是數據挖掘前的一個非常重要的數據準備工作，是知識發現過程(knowledge discovery in database，KDD)的關鍵環節之一[3]。一方面它可以保證挖掘數據的正確性和有效性，另一方面通過對數據格式和內容的調整，使數據更符合挖掘的需要。通過把一些與數據分析、挖掘無關的數據項清除掉，為挖掘算法提供更高質量的數據內核。

數據挖掘的首要前提是確保消除所有的“臟數據”，包含冗余數據、缺失數據、不確定數據和不一致數據。針對“臟數據”的預處理方法有以下幾種：清洗、集成、變換和歸約。

1.1 數據清洗

檢測數據中存在冗余、錯誤、不一致等噪聲數據，利用各種清洗技術，形成“干凈”的一致性數據集合。如圖1所示。

圖1 數據清洗

數據清洗技術包括清除重復數據、填充缺失數據、消除噪聲數據等。在分析“臟數據”的產生來源和存在形式后，充分利用新興的技術手段和方法去清洗“臟數據”，將“臟數據”轉化為滿足數據質量或應用要求的數據。美國最早對數據清洗技術展開研究。隨著信息業和商業的發展，數據清洗技術得到了進一步發展。數據清洗分為以下幾大類：

(1)重復數據的清洗。為了提高數據挖掘的速度和精度，有必要去除數據集合中的重復記錄。如果有兩個及以上的實例表示的是同一實體，那么即為重復記錄。為了發現重復實例，通常的做法是將每一個實例都與其他實例進行對比，找出與之相同的實例。對于實例中的數值型屬性，可以采用統計學的方法來檢測，根據不同的數值型屬性的均值和標準方差值，設置不同屬性的置信區間來識別異常屬性對應的記錄，識別出數據集合中的重復記錄，并加以消除。相似度計算是重復數據清洗過程中的常用方法，通過計算記錄的各屬性的相似度，再考慮每個屬性的不同權重值，加權平均后得到記錄的相似度。如果兩條記錄相似度超過了某一閾值，則認為兩條記錄是匹配的，否則，認為這兩條記錄指向不同實體[4]。另一種相似度計算算法基于基本近鄰排序算法。核心思想是為了減少記錄的比較次數，在按關鍵字排序后的數據集上移動一個大小固定的窗口，通過檢測窗口內的記錄來判定它們是否相似，從而確定重復記錄。

(2)缺失數據清洗(missing values imputation)。完善缺失數據是數據清洗領域面臨的另一個重要問題。如圖2所示，在現實世界中，由于手動輸入的失誤操作、部分信息需要保密或者數據來源不可靠等各種各樣的原因，使得數據集中的內容殘缺不完整。比如某條記錄的屬性值被標記為NULL、空缺或“未知”等。一旦不完整、不準確的數據用于挖掘，則會影響抽取模式的正確性和導出規則的準確性。當錯誤的數據挖掘模型應用于前端的決策系統時，就會導致分析結果和執行決策出現嚴重偏差[5]。

圖2 缺失數據清洗

當前有很多方法用于缺失值清洗，可以分為兩類：

(a)忽略不完整數據。直接通過刪除屬性或實例，忽略不完整的數據[6]。在數據集規模不大、不完整數據較少的情況下，常常利用該方法來實現數據清洗。該方法因為執行效率高，因此經常作為缺省方法，但缺點也相當明顯。如果不完整數據集較大，一旦刪除了若干記錄之后，因為剩余的數據集規模較小，使得模型的構建不具備普適性和代表性，無法讓人信賴，可靠度大大降低。另外，因為刪除不完整數據帶來的數據集偏差也使得數據挖掘的分類、聚類模型產生嚴重傾斜，進而影響最終的挖掘結果，產生重大決策性誤導。

(b)基于填充技術的缺失值插補算法。上一種忽略法很有可能將潛在的有價值信息也一并刪除。因此更多的時候選擇填充不完整的數據。為了填充缺失值，用最接近缺失值的值來替代它，保證可挖掘數據的數量和質量。填充方法保留了潛在的有用數據，和刪除屬性或記錄相比，保留了更多數據樣本，不易于產生數據分析偏差，由此構建的模型更可靠，更有說服力。

目前常用的缺失值填充算法大體分為兩大類，一類是統計學方法，另一類是分類、聚類方法。

·采用統計學方法填充缺失值。分析數據集，獲取數據集的統計信息，利用數值信息填充缺失值。其中最簡單的方法是平均值填充方法[7]。它把所有完整數據的算術平均值作為缺失數據的值。這種方法的弊端在于有可能會影響缺失數據與其他數據之間原本的相關性。如果規模較大的數據集的缺失值全部采用平均值填充法進行填充，因為過多的中值存在，更多的尖峰態頻率分布有可能會誤導挖掘結果。

·采用分類、聚類方法填充缺失值。分類是在已有類標號的基礎上，通過輸入訓練樣本數據集，構造出分類器(如分類函數或者分類模型)。常用的數據分類技術包括決策樹、神經網絡、貝葉斯網絡、粗糙集理論、最臨近分類法等。利用完整記錄與缺失記錄之間的記錄相似度，通過最大相似度的計算，結合機器學習的相關技術，建立最大可能的完整的數據模型。聚類是在不考慮類標號的前提下，尋求類間的相似性，目的也是在海量的數據聚集的基礎上，構建較小的代表性的數據集，并基于該集合進一步分析和研究。常見的缺失值填充算法包括EM最大期望值算法(expectation-maximization algorithm)、MI算法(multiple imputation)和KNNI算法(k-nearest neighbor imputation)等。其中最大期望算法通過創建概率模型，尋找參數最大似然估計值或者最大后驗估計值，概率模型的成功與否依賴于無法觀測的隱藏變量(latent variable)[8-9]。

圖3 噪聲數據

(3)噪聲數據處理(noise treatment)。數據挖掘前，往往假設數據集不存在任何數據干擾。然而，實際應用中卻因為各種原因，在數據收集、整理的過程中，產生大量的噪聲數據，即“離群點”。因為噪聲數據不在合理的數據域內，所以分析、挖掘過程中輸入和輸出數據的質量難以保證，容易造成后續的挖掘結果不準確、不可靠，如圖3所示。常用的消除噪聲數據的方法分為兩種。一種叫噪聲平滑方法(data polishing)，常用的方法是分箱法。將預處理數據分布到不同的箱中，通過參考周圍實例平滑噪聲數據，包括等寬分箱和等深分箱兩大類。具體的分箱技術包括：按箱平均值平滑，即求取箱中的所有值的平均值，然后使用均值替代箱中所有數據；按中位數平滑，和上一種方法類似，采用中位數進行平滑；按設定的箱邊界平滑，定義箱邊界是箱中的最大和最小值。用最近的箱邊界值替換每一個值。另一種是噪聲過濾(data filters)，利用聚類方法對離群點進行分析、過濾。在訓練集中明確并去除噪聲實例。噪聲過濾的常用算法包括IPF算法(iterative partitioning filter)、EF算法(ensemble filter)[10]。

1.2 數據集成

數據集成(data integration)是將多文件或多數據庫運行環境中的異構數據進行合并處理，解決語義的模糊性。該部分主要涉及數據的選擇、數據的沖突問題以及不一致數據的處理問題，如圖4所示。

圖4 數據集成

1.3 數據變換

數據變換(data transformation)：是找到數據的特征表示，用維變換或轉換來減少有效變量的數目或找到數據的不變式，包括規格化、切換和投影等操作。數據變換是將數據轉換成適合于各種挖掘模式的形式，根據其后所使用的數據挖掘算法，決定選擇使用何種數據變換方法。常用變換方法包括：函數變換，使用數學函數對每個屬性值進行映射；對數據進行規范化，按比例縮放數據的屬性值，盡量落入較小的特定區間。規范化既有助于各類分類、聚類算法的實施，又避免了對度量單位的過度依賴，同時規避了權重不平衡發生。

1.4 數據歸約

數據歸約(data reduction)：是在對發現任務和數據本身內容理解的基礎上，尋找依賴于發現目標的表達數據的有用特征，以縮減數據模型，從而在盡可能保持數據原貌的前提下最大限度地精簡數據量，促進大數據挖掘更高效。其主要有兩個途徑：維歸約和數量歸約，分別針對數據庫中的屬性和記錄。目前海量數據上的數據歸約技術是數據預處理的重要問題之一。

歸約過程涉及的重要技術包括：

(1)針對高維數據的降維處理(dimensionality reduction)。涉及的技術包括特征值選擇(feature selection)和空間變換(space transformations)。維歸約的核心是減少隨機變量或者屬性的個數。特征值選擇目的是獲取能描述問題的關鍵特征的那部分屬性。刪除不相關的、冗余的屬性，使得機器學習過程更快，內存消耗更少。特征子集選擇方法，包括各類啟發式算法、貪心算法等，具體有向前選擇法、向后刪除法、決策樹歸納法等。數量歸約的重點在于減少數據量，從數據集中選擇較小的數據表示形式。主流的數值歸約技術，包括對數線性模型、直方圖、聚類、抽樣等。常用算法包括：LVF(Las Vegas filter)、MIFS(mutual information feature selection)、mRMR(minimum redundancy maximum relevance)、Relief算法?？臻g變化是另一種降低數據維度的方法。流行的算法有LLE(locally linear embedding)、PCA(principal components analysis)等[11]。

(2)實例歸約(instance reduction)。當前很流行的一種減少數據集規模的算法是實例歸約算法。在減少數據量的同時，并沒有降低獲取知識的品質。通過移除或者生成新的實例的方法，大大降低了數據規模。涉及技術包括:(a)實例選擇(instance selection)。好的實例選擇算法能夠生成一個最小的數據集，移除噪聲數據和冗余數據，獨立于隨后進行的數據挖據算法，符合數據分析和挖掘的要求。常見的算法有CNN(condensed nearest neighbor)、ENN(edited nearest neighbor)、ICF(iterative case filtering)、DROP(decremental reduction by ordered projections)等。(b)實例生成(instance generation)。建立各種原型用于實例生成，涉及算法包括LVQ(learning vector quantization)等[12]。

(3)離散化技術(discretization)。目的在于減少給定連續屬性值的個數。離散化之前，首先要預估離散型數據的規模，接著對連續型數據進行排序，然后指定若干個分裂點把數據分為多個區間。將落在同一個區間內的所有連續型數據通過統一的映射方法對應到相同的離散型數據上[13]。根據分裂點認定方式的不同，離散化分為自頂向下和自底向上兩種，按照是否使用分類信息，又分為監督和非監督兩大類。目前大多數離散化方法分為兩大方向，一是從屬性出發，基于屬性的重要性進行離散處理，二是利用分辨矩陣進行映射。常見的算法包括：MDLP(minimum description length principle)、ChiMerge、CAIM(class-attribute interdependence maximization)等[14]。

(4)不平衡學習(imbalanced learning)。在使用機器學習的有監督學習形成數據模型時，很容易在不同類型的數據集上產生巨大的優先級的差異。這種也叫做分類不平衡問題。很多標準的分類學習算法經常會傾向于大多數實例(majority class)而忽視少數特別實例(minority class)[15]。數據預處理相關技術可以避免出現類型分布不平衡的情況。主要方法是兩種：欠采樣方法，在抽樣創建原始數據集的子集用作數據挖掘時，盡量去除大多數實例；過度采樣方法，在抽樣時復制很多相同的實例或者創建新的實例。在眾多采樣算法中，最復雜最著名的遺傳算法是SMOTE(synthetic minority oversampling technique)。

2 結束語

大數據時代下，不同的應用領域、各種新興的云計算技術會促進數據預處理方法進一步的擴展和提升。數據預處理是知識發現過程中十分重要的環節，是數據挖掘算法能夠有效執行的必要前提。通過高效的預處理工作，清除冗余數據，糾正錯誤數據，完善殘缺數據，挑選出必需的數據進行集成，達到數據信息精練化、數據格式一致化和數據存儲集中化。在最精確、最可靠的數據集合上進行數據挖掘，極大地減少了系統挖掘的開銷，提高了知識發現的準確性、有效性和實用性。

參考文獻：

[1] 程學旗，靳小龍，王元卓，等.大數據系統和分析技術綜述[J].軟件學報，2014，25(9)：1889-1908.

[2] 李小菲.數據預處理算法的研究與應用[D].成都:西南交通大學，2006.

[3] WU X,ZHU X,WU G Q,et al.Data mining with big data[J].IEEE Transactions on Knowledge and Data Engineering，2014,26(1)：97-107.

[5] 關大偉.數據挖掘中的數據預處理[D].長春：吉林大學,2006.

[6] TRIGUERO I,PERALTA D,BACARDIT J,et al.MRPR:a MapReduce solution for prototype reduction in big data classification[J].Neurocomputing,2015,150：331-345.

[7] GALAR M,FERNNDEZ A,BARRENECHEA E,et al.A review on ensembles for the class imbalance problem:bagging-,boosting-,and hybrid-based approaches[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2012,42(4):463-484.

[8] GAO M,HONG X,CHEN S,et al.A combined SMOTE and PSO based RBF classifier for two-class imbalanced problems[J].Neurocomputing,2011,74(17):3456-3466.

[9] SOTOCA J M,PLA F.Supervised feature selection by clustering using conditional mutual information-based distances[J].Pattern Recognition,2010,43(6):2068-2081.

[10] MITRA P,MURTHY C A,PAL S K.Density-based multiscale data condensation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(6):734-747.

[11] WANG H,WANG S.Mining incomplete survey data through classification[J].Knowledge and Information Systerms,2010,24(2):221-233.

[12] PéREZORTIZ M,GUTIéRREZ P A,MARTNEZ C H,et al.Graph-based approaches for over-sampling in the context of ordinal regression[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(5):1233-1245.

[13] PRATI R C,BATISTA G E A P A,SILVA D F.Class imbalance revisited:a new exper-imental setup to assess the performance of treatment methods[J].Knowledge and Information Systems,2015,45(1):247-270.

[14] ANGIULLI F,FOLINO G.Distributed nearest neighbor-based condensation of very large data sets[J].IEEE Transcactions on Knowledge and Data Engineering,2007,19(12):1593-1606.

[15] BACARDIT J,WIDERA P,CHAMORRO A E M,et al.Contact map prediction using a large-scale ensemble of rule sets and the fusion of multiple predicted structural features[J].Bioinformatics,2012,28(19):2441-2448.