大數(shù)據(jù)下數(shù)據(jù)預(yù)處理方法研究

孔 欽，葉長青，孫 赟

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

0 引 言

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

1 研究背景

大數(shù)據(jù)環(huán)境下，來自異構(gòu)系統(tǒng)的原始數(shù)據(jù)中存在若干問題：

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

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

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

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

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

1.1 數(shù)據(jù)清洗

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

圖1 數(shù)據(jù)清洗

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

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

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

圖2 缺失數(shù)據(jù)清洗

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

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

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

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

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

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

圖3 噪聲數(shù)據(jù)

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

1.2 數(shù)據(jù)集成

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

圖4 數(shù)據(jù)集成

1.3 數(shù)據(jù)變換

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

1.4 數(shù)據(jù)歸約

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

歸約過程涉及的重要技術(shù)包括：

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

(2)實例歸約(instance reduction)。當前很流行的一種減少數(shù)據(jù)集規(guī)模的算法是實例歸約算法。在減少數(shù)據(jù)量的同時，并沒有降低獲取知識的品質(zhì)。通過移除或者生成新的實例的方法，大大降低了數(shù)據(jù)規(guī)模。涉及技術(shù)包括:(a)實例選擇(instance selection)。好的實例選擇算法能夠生成一個最小的數(shù)據(jù)集，移除噪聲數(shù)據(jù)和冗余數(shù)據(jù)，獨立于隨后進行的數(shù)據(jù)挖據(jù)算法，符合數(shù)據(jù)分析和挖掘的要求。常見的算法有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)離散化技術(shù)(discretization)。目的在于減少給定連續(xù)屬性值的個數(shù)。離散化之前，首先要預(yù)估離散型數(shù)據(jù)的規(guī)模，接著對連續(xù)型數(shù)據(jù)進行排序，然后指定若干個分裂點把數(shù)據(jù)分為多個區(qū)間。將落在同一個區(qū)間內(nèi)的所有連續(xù)型數(shù)據(jù)通過統(tǒng)一的映射方法對應(yīng)到相同的離散型數(shù)據(jù)上[13]。根據(jù)分裂點認定方式的不同，離散化分為自頂向下和自底向上兩種，按照是否使用分類信息，又分為監(jiān)督和非監(jiān)督兩大類。目前大多數(shù)離散化方法分為兩大方向，一是從屬性出發(fā)，基于屬性的重要性進行離散處理，二是利用分辨矩陣進行映射。常見的算法包括：MDLP(minimum description length principle)、ChiMerge、CAIM(class-attribute interdependence maximization)等[14]。

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

2 結(jié)束語

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

參考文獻：

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

[2] 李小菲.數(shù)據(jù)預(yù)處理算法的研究與應(yīng)用[D].成都:西南交通大學(xué)，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] 關(guān)大偉.數(shù)據(jù)挖掘中的數(shù)據(jù)預(yù)處理[D].長春：吉林大學(xué),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.