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

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

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

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

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

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

6、的值。進(jìn)一步，數(shù)據(jù)點(diǎn)B也是一個(gè)噪聲數(shù)據(jù)，但是很難判定它在哪個(gè)屬性上的數(shù)據(jù)出現(xiàn)錯(cuò)誤。本方法試圖確定噪聲點(diǎn)B的噪聲屬性(即產(chǎn)生噪聲的具體屬性)，并對(duì)其進(jìn)行矯正。算法思想：首先通過聚類識(shí)別噪聲數(shù)據(jù)，并考察它們?cè)诟鱾€(gè)屬性上的值與其期望之間的距離以判定引起噪聲的屬性；然后，對(duì)于能夠判定噪聲屬性的記錄，尋找它所屬的分類，并利用它所屬分類中噪聲屬性上的值進(jìn)行矯正；對(duì)于不能判定噪聲屬性的記錄，因?yàn)樵肼曈涗浫コ窃肼晫傩院蟮娜匀皇窃肼曈涗?，同樣可以通過聚類判定其噪聲屬性并進(jìn)行矯正；整個(gè)過程記錄噪聲記錄在屬性上的分布情況。幾個(gè)定義如下：噪聲數(shù)據(jù)矩陣(NoiseMatrix,NM)：通過聚類算法得到的孤立數(shù)據(jù)點(diǎn)集合

7、矩陣，NM(i,j)的值對(duì)應(yīng)孤立點(diǎn)集合P中第i條記錄在屬性j上的值，即NM(i,j)=P污染矩陣(CorruptionMatrix,CM)：NM對(duì)應(yīng)的一個(gè)01布爾矩陣，NM(i,j)為噪聲=>CM(ij)=1；否則，CM(i,j)=0?；舅惴枋觯狠斎耄汉肼晹?shù)據(jù)的數(shù)據(jù)集S,S有N個(gè)數(shù)據(jù)對(duì)象，S的屬性集合D=D1,D2,?,Dk。輸出：噪聲數(shù)據(jù)矯正后的數(shù)據(jù)集合S,污染矩陣CM方法：(1)P=GetNo1seByClustering(SD);/*屬性集合D上對(duì)S進(jìn)行聚類，得到孤立點(diǎn)數(shù)據(jù)集臺(tái)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(chǔ))ThenCM(i,j)=1:/*替NM(i,j)與S中D1上的期望之間的距離大于某個(gè)閾值，則判定D1上產(chǎn)生了噪聲*/ElseCM(i,j)=0(3)ForEachDI(1<=i<=k)P'=GetNoiseByClustering(S.D-D);/*在D=DD上對(duì)S聚類；*/Form=1tolength(P)if(CM(m,i)=1)ThenNM(m,i)用行m所對(duì)應(yīng)的記錄rm所在的聚集D1上的(平均)值替換；/*對(duì)于能夠劃定

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

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

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

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

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

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

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

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

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

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