數(shù)據(jù)挖掘噪聲數(shù)據(jù)處理綜述

1、噪聲數(shù)據(jù)處理綜述摘要：噪聲數(shù)據(jù)是指數(shù)據(jù)中存在著錯誤或異常(偏離期望值)的數(shù)據(jù)，不完整數(shù)據(jù)是指感興趣的屬性沒有值.不一致數(shù)據(jù)則是數(shù)據(jù)內(nèi)涵出現(xiàn)不一致的情況。為了更好的論述什么是噪聲數(shù)據(jù)處理，給出了兩種噪聲數(shù)據(jù)處理的算法：在屬性級別上處理噪聲數(shù)據(jù)的數(shù)據(jù)清洗算法和一種改進的應用于噪聲數(shù)據(jù)中的KNN算法。關鍵詞：噪聲數(shù)據(jù)噪聲數(shù)據(jù)處理數(shù)據(jù)清洗KNN算法1 .概述噪聲數(shù)據(jù)(noisydataj)就是無意義的數(shù)據(jù)(meaninglessdata。這個詞通常作為損壞數(shù)據(jù)(corruptdataj)的同義詞使用。但是，現(xiàn)在它的意義已經(jīng)擴展到包含所有難以被機器正確理解和翻譯的數(shù)據(jù)，如非結構化文本。任何不可被創(chuàng)造它的

2、源程序讀取和運用的數(shù)據(jù)，不管是已經(jīng)接收的、存儲的還是改變的，都被稱為噪聲。噪聲數(shù)據(jù)未必增加了需要的存儲空間容量，相反地，它可能會影響所有數(shù)據(jù)挖掘(datamining)分析的結果。統(tǒng)計分析可以運用歷史數(shù)據(jù)中收集的信息來清除噪聲數(shù)據(jù)從而促進數(shù)據(jù)挖掘。引起噪聲數(shù)據(jù)(noisydata)的原因可能是硬件故障、編程錯誤或者語音或光學字符識別程序(OCR中的亂碼。拼寫錯誤、行業(yè)簡稱和俚語也會阻礙機器讀取。噪聲數(shù)據(jù)處理是數(shù)據(jù)處理的一個重要環(huán)節(jié)，在對含有噪聲數(shù)據(jù)進行處理的過程中，現(xiàn)有的方法通常是找到這些孤立于其他數(shù)據(jù)的記錄并刪除掉，其缺點是事實上通常只有一個屬性上的數(shù)據(jù)需要刪除或修正，將整條記錄刪除將丟失大

3、量有用的、干凈的信息。在數(shù)據(jù)倉庫技術中，通常數(shù)據(jù)處理過程應用在數(shù)據(jù)倉庫之前，其目的是提高數(shù)據(jù)的質(zhì)量，使后繼的聯(lián)機處理分析(OLAP)和數(shù)據(jù)挖掘應用得到盡可能正確的結果。然而，這個過程也可以反過來，即利用數(shù)據(jù)挖掘的一些技術來進行數(shù)據(jù)處理，提高數(shù)據(jù)質(zhì)量。2 .噪聲數(shù)據(jù)處理2.1 在屬性級別上噪聲數(shù)據(jù)處理的數(shù)據(jù)清洗算法2.1.1 數(shù)據(jù)清洗和聚類分析介紹數(shù)據(jù)清洗包括許多的內(nèi)容，文獻川給出了詳盡的介紹，其中噪聲數(shù)據(jù)(包含錯誤或存在偏離期望的孤立點值)的處理是其中重要的一部分。數(shù)據(jù)含噪聲(包含錯誤或存在偏離期望的孤立點值)可能有多種原因：收集數(shù)據(jù)本身難以得到精確的數(shù)據(jù)，收集數(shù)據(jù)的設備可能出現(xiàn)故障，數(shù)據(jù)輸入

4、時可能出現(xiàn)錯誤，數(shù)據(jù)傳輸過程中可能出現(xiàn)錯誤，存儲介質(zhì)有可能出現(xiàn)損壞等。根據(jù)決策系統(tǒng)中“garbage門garbageout”(如果輸入的分析數(shù)據(jù)是垃圾，那么輸入的分析結果也將是垃圾)這條原理，必須處理這些噪聲數(shù)據(jù)。去掉噪聲、平滑數(shù)據(jù)的技術主要有：分箱(binning),聚類(clustering),同歸(regression痔。聚類(clustering)就是將數(shù)據(jù)對象分組成為多個類或簇(cluster),在同一個簇中的對象之間具有較高的相似度，而不同的簇間的對象差別較大。聚類分析可以用來進行孤立點挖掘。孤立點挖掘可以發(fā)現(xiàn)噪聲數(shù)據(jù)，因為噪聲本身就是孤立點、聚類分析發(fā)現(xiàn)孤立點的方法有：基于統(tǒng)計的

5、孤立點檢測，基于距離的孤立點檢測和基于偏離的孤立點檢測。.縛法介紹下面是一個利用聚類算法來發(fā)現(xiàn)關系數(shù)據(jù)庫中孤立點數(shù)據(jù)的例子：輸入：數(shù)據(jù)集S,包括N條記錄，屬性集D:年齡、收入;本文稱一條記錄為一個數(shù)據(jù)點(DataPoint),一條記錄上的每個屬性上的值為一個數(shù)據(jù)單元格(DataCel1)0S有NXD個數(shù)據(jù)單元格，其中某些數(shù)據(jù)單元格是噪聲數(shù)據(jù)。輸出：孤立數(shù)據(jù)點如圖1所示。圖1通過聚類發(fā)現(xiàn)噪聲數(shù)據(jù)的例子收6k4k2k4孤立點A是一個孤立點數(shù)據(jù)，我們認為它是噪聲數(shù)據(jù)，很明顯它的噪聲屬性足收入，剩下的干凈信息即年齡屬性上的數(shù)據(jù)仍然可以用于預測或其他應用，同時可以利用年齡屬性上的干凈數(shù)據(jù)來矯正A在收入上

6、的值。進一步，數(shù)據(jù)點B也是一個噪聲數(shù)據(jù)，但是很難判定它在哪個屬性上的數(shù)據(jù)出現(xiàn)錯誤。本方法試圖確定噪聲點B的噪聲屬性(即產(chǎn)生噪聲的具體屬性)，并對其進行矯正。算法思想：首先通過聚類識別噪聲數(shù)據(jù)，并考察它們在各個屬性上的值與其期望之間的距離以判定引起噪聲的屬性；然后，對于能夠判定噪聲屬性的記錄，尋找它所屬的分類，并利用它所屬分類中噪聲屬性上的值進行矯正；對于不能判定噪聲屬性的記錄，因為噪聲記錄去除非噪聲屬性后的仍然是噪聲記錄，同樣可以通過聚類判定其噪聲屬性并進行矯正；整個過程記錄噪聲記錄在屬性上的分布情況。幾個定義如下：噪聲數(shù)據(jù)矩陣(NoiseMatrix,NM)：通過聚類算法得到的孤立數(shù)據(jù)點集合

7、矩陣，NM(i,j)的值對應孤立點集合P中第i條記錄在屬性j上的值，即NM(i,j)=P污染矩陣(CorruptionMatrix,CM)：NM對應的一個01布爾矩陣，NM(i,j)為噪聲=>CM(ij)=1；否則，CM(i,j)=0。基本算法描述：輸入：含噪聲數(shù)據(jù)的數(shù)據(jù)集S,S有N個數(shù)據(jù)對象，S的屬性集合D=D1,D2,?,Dk。輸出：噪聲數(shù)據(jù)矯正后的數(shù)據(jù)集合S,污染矩陣CM方法：(1)P=GetNo1seByClustering(SD);/*屬性集合D上對S進行聚類，得到孤立點數(shù)據(jù)集臺P*/(2)If(P!=Nul1)ThenFori=Otolength(P)Forj=0tokNM(

8、i,j)=P(i,j);/*NM(i,j)為P中第i條，記錄在屬性D1上的值*/If(Distance(NM(i,j)、E(S,D1)>閾值A)ThenCM(i,j)=1:/*替NM(i,j)與S中D1上的期望之間的距離大于某個閾值，則判定D1上產(chǎn)生了噪聲*/ElseCM(i,j)=0(3)ForEachDI(1<=i<=k)P'=GetNoiseByClustering(S.D-D);/*在D=DD上對S聚類；*/Form=1tolength(P)if(CM(m,i)=1)ThenNM(m,i)用行m所對應的記錄rm所在的聚集D1上的(平均)值替換；/*對于能夠劃定

9、噪聲屬性的記錄，用干凈數(shù)據(jù)中D1上的(期望)值矯正*/Else1f(CM(m,j)=0)(1<=j<=k)ThenIf行m所對應的記錄rm所在新白勺聚類P中不是孤立點thenNM(m,i)用行m所對應的紀錄rm所在的聚集中D1上的(期望)值替換；/*對于不能判定噪聲屬性，并矯正*/CM(m,i)=l：(4)Form=1tolength(P)/*矯正原始數(shù)據(jù)S;*/Forj=0tokIf(CM=1)Then用NM(m,j)替換S中對應的記錄屬性D1上的值.(5)返回S和NM:其中，過程GetNoiseByCIustering(S,D)1l對數(shù)據(jù)求S在屬性集D上進行聚類返回的噪聲數(shù)據(jù)集

10、合。它可以通過聚類算法如k-means(k-平土譏S),k-medoids(k-中心點)實現(xiàn)，這里不作具體介紹。這個算法在判定噪聲屬性的時候采用與其期望值進行比較的方法。這個算法能在屬性的級別上發(fā)現(xiàn)噪聲數(shù)據(jù)，并且根據(jù)剩余的干凈數(shù)據(jù)來矯正噪聲而無需事先了解數(shù)據(jù)的結構。它還能為噪聲的產(chǎn)生過程建模，即得到了噪聲在屬性上的分布規(guī)律統(tǒng)計。它的時間復雜度為O(kf),其中k為數(shù)據(jù)集合的屬性數(shù)，f所選的聚類算法的時間復雜度.改進的用于噪聲數(shù)據(jù)中的KNN算法相關知識.相關處理方法K-近鄰算法是一種非常簡單直觀且有效的分類方法，廣泛應用于模式識別的各個領域。顧名思義，該方法就是找出未知樣本x的k個近鄰，根據(jù)k個

11、近鄰中多數(shù)實例所屬類別，把x歸為該類。具體地說，假設有L個類cl,c2,?,cL,第i個類的訓練樣本集L為wi,整個訓練樣本集為U,樣本總數(shù)Q,yi(i=1,2,Q)表示第i個訓練樣本。給定未知樣本x和距離測試，首先從Q個訓練樣本中找出X的k個近鄰，ki(1<=i<=L)表示這k個近鄰中屬于第i類的樣本數(shù)，那么把X歸為類cL,其中I=argmaxk,這就是所謂的K近鄰規(guī)則(分類方法)。我們用向量表示樣本或者樣本的特征向量，分類中采用EuclideaniK離。.KNINJ法中的噪聲處理。噪聲數(shù)據(jù)是永遠存在于機器學習領域的研究之中?，F(xiàn)在很多工作成果是關于如何處理噪聲數(shù)據(jù)以及噪聲數(shù)據(jù)對分

12、類學習算法的影響。在前人的工作中，大多沒有使用噪聲數(shù)據(jù)模型來有效地增強學習算法的分類效果。然而很少有工作研究如何充分利用噪聲模型來建立更優(yōu)的分類算法。K-近鄰算法是基于距離的局部最優(yōu)的算法。不可否認的是，當數(shù)據(jù)中存在噪聲時，局部最優(yōu)的基于距離的算法會受到明顯的影響。雖然合適的參數(shù)k能夠減弱突發(fā)性的噪聲數(shù)據(jù)對分類效果的影響。但當數(shù)據(jù)服從穩(wěn)定的噪聲模型時，其很難能夠從實質(zhì)上解決此問題。在前人的工作中，一種普遍被接受的觀點是，如果訓練數(shù)據(jù)集與測試數(shù)據(jù)集中存在相同的噪聲模型，則噪聲數(shù)據(jù)將會在訓練數(shù)據(jù)和測試數(shù)據(jù)中起到相同的作用，因而可以忽略輸入數(shù)據(jù)中的不確定性。然而，文獻明確指出考慮輸入數(shù)據(jù)的不確定性，

13、可以提高分類器的預測準確性。如果對于類標簽來說，所有條件屬性是同等重要的，那么將條件屬性值規(guī)范化于0,1區(qū)間后，歐基里德距離在計算對象之間的距離時是相當成功的。然而這種假設也不盡然，數(shù)據(jù)集中的條件屬性與類標簽之問不一定都是相關，且即使是與類標簽之問是相關的，相關程度也不盡相同。樸素的K近鄰算法中，每一個數(shù)據(jù)所起到的作用是等價的明顯存在漏洞。因而很多專家提出了用權重的方法來強調(diào)相關性強的屬性或減弱不相關的屬性在計算距離時的作用。權重的獲得有很多種方法，如信息嫡、互信息或各屬性在相同類標簽或不同類標簽的實例之間所起的作用來決定等等。2.2.2改進算法.K近鄰算法。盡管有很多種計算實例之間距離的方法

14、，但大多算法仍舊使用歐基里德距離引。一個實例(ai(1),a2(1),?,ak(1)和另一個實例(ai(2),%(2),?,ak(2)之間距離為：一.一一.，一其中，k為條件屬性個數(shù)。.噪聲模型。真實數(shù)據(jù)中的噪聲數(shù)據(jù)永遠都是存在的。但噪聲數(shù)據(jù)產(chǎn)生的原因有很多種，如手工的誤操作、機器本身存在的誤差、傳輸過程中發(fā)生的錯誤等等。系統(tǒng)誤差。實驗系統(tǒng)的組成包括：實驗儀器、環(huán)境、實驗的理論和方法以及實驗人員。由這四種組成所引起的有規(guī)律的誤差稱之為系統(tǒng)誤差。儀器誤差：又以其本身的固有缺陷、較正不完善或使用不當引起的。環(huán)境誤差：儀器所處的外界環(huán)境如：溫度、濕度、電磁場等環(huán)境的變化引發(fā)的誤差。方法誤差：由于計算

15、公式的近似，沒有完全滿足理論公式所給定的條件。例如，單擺測重力加速度的實驗中，采用了sin00的近似條。人員誤差：由測量者的個人因素造成的誤差。例如：按秒表時總是超前或滯后，讀數(shù)時頭總是向一邊偏等。隨機誤差。由某些偶然的、不確定的因素所造成的誤差稱之為隨機誤差。若從一次測量來看，隨機誤差是隨機的，沒有確定的規(guī)律，也不能預測。但當測量次數(shù)足夠多時，隨機誤差遵從一定的統(tǒng)計分布。因此，增加測量的次數(shù)，可以明顯地減少隨機誤差。其中一部分誤差是隨機的，沒有規(guī)律可循，如手工誤操作、傳輸錯誤等；而另外一類，是有一定規(guī)律可循的，也就是說這類噪聲往往有一點的范圍，服從一定的分布，如機器本身存在的誤差，一般在出廠

16、時都有一定的說明，明確指出其精確度。這些有效信息對數(shù)據(jù)本身的可靠性是最有力的證明。正態(tài)分布在概率論與數(shù)理統(tǒng)計的理論研究和實際應用中都占有十分重要的地位。在自然界和社會現(xiàn)象中，大量的隨機變量都服從或近似地服從正態(tài)分布。諸如各種測量誤差、計算誤差、產(chǎn)品的各類質(zhì)量指標等。因此，對于連續(xù)屬性值，本文討論假設誤差服從正態(tài)分布情況下的處理方法。對于屬性集中的某一個屬性ai,假設其噪聲服從N(1,(T2),為噪聲的均值，b為噪聲的方差，即表示噪聲的分散程度。為了計算兩個實例之間的距離，必需先計算公式(1)中各屬性之間的距離。以第一個屬性為例，討論正態(tài)分布中的兩個參數(shù)科和°對計算距離的影響。現(xiàn)計算實

17、例ei和e2的屬性a之間的距離。定理l對于某一屬性，其誤差服從正態(tài)分布，則其誤差均值不會對兩個實例的該屬性之間的距離產(chǎn)生影響，此距離只受方差的影響。但在數(shù)據(jù)集中，由于不同的屬性的度量單位不同，不同屬性的取值范圍也就不同。如對于屬性ai,的取值va2范圍為10,80,其方差b為3;而屬性a2的取值va2范圍為1,8,其方差也為3,很明顯同樣的方差3所反映出的數(shù)據(jù)中所含噪聲程度差別很大。為了避免這種情況對權值產(chǎn)生的不均衡的影響，令屬性的權重："'(2)從(2)式中可以看出，方差越大，權重越小，分母中方差加1,是為了防止當數(shù)據(jù)完全精確，方差為0時公式(2)無意義的情況。分子中取的是

18、屬性值區(qū)間長度，區(qū)間長度與方差的比值，可以消除由不同的屬性值范圍所帶來的影響。以前面所說為例，屬性a1的權重應為：(8010)7(3+1)=17.5;而屬性a2的權重為：(8-1)/(3+1)=1.75。從實際應用角度看，這是合理的。兩個實例之間的距離由公式(1)轉化為如下距離公式：D=Jw&diX才+岫出C)y+A&。，個萬予(3)從上式可以明確地看出，在計算實例之間距離時，屬性值誤差的方差起到了應有的作用，若某個屬性的誤碼差方差較大，則其權重則較小，從而在計算距離時所起到的作用就較小，減弱了誤差在K近算法中的影響。3.實驗在實驗中，為了反映本文改進算法的效果，分別使用了人工數(shù)據(jù)和真實數(shù)據(jù)集。在人工數(shù)據(jù)集中，采用的是三維空間坐標作為條件屬性，目標函數(shù)是一空間立體區(qū)域，若在這個區(qū)域中，則目標函數(shù)值（類標簽）為1,否則為00為了進一步了解，若數(shù)據(jù)集中存在不相關或相關性很小的數(shù)據(jù)時，改進算法的分類效率，在人工數(shù)據(jù)集中，加入了一個不相關屬性。在人工數(shù)據(jù)集和真實數(shù)據(jù)集中，都按照一定的正態(tài)分布參數(shù)，隨機地加入了噪聲數(shù)據(jù)。表1人工數(shù)據(jù)集實驗結果DataSet1DataSet1