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

1、噪聲數(shù)據(jù)處理綜述摘要：噪聲數(shù)據(jù)是指數(shù)據(jù)中存在著錯(cuò)誤或異常(偏離期望值)的數(shù)據(jù),不完整數(shù)據(jù)是指感興趣的屬性沒(méi)有值.不一致數(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ù)（noisy data）就是無(wú)意義的數(shù)據(jù)（meaningless data）。這個(gè)詞通常作為損壞數(shù)據(jù)（corrupt data）的同義詞使用。但是，現(xiàn)在它的意義已經(jīng)擴(kuò)展到包含所有難以被機(jī)器正確理解和翻譯的數(shù)據(jù)，如非結(jié)構(gòu)化文本。任何不

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

3、條記錄刪除將丟失大量有用的、干凈的信息。在數(shù)據(jù)倉(cāng)庫(kù)技術(shù)中，通常數(shù)據(jù)處理過(guò)程應(yīng)用在數(shù)據(jù)倉(cāng)庫(kù)之前，其目的是提高數(shù)據(jù)的質(zhì)量，使后繼的聯(lián)機(jī)處理分析(OLAP)和數(shù)據(jù)挖掘應(yīng)用得到盡可能正確的結(jié)果。然而，這個(gè)過(guò)程也可以反過(guò)來(lái)，即利用數(shù)據(jù)挖掘的一些技術(shù)來(lái)進(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)【l】給出了詳盡的介紹，其中噪聲數(shù)據(jù)(包含錯(cuò)誤或存在偏離期望的孤立點(diǎn)值)的處理是其中重要的一部分。數(shù)據(jù)含噪聲(包含錯(cuò)誤或存在偏離期望的孤立點(diǎn)值)可能有多種原因：收集數(shù)據(jù)本身難以得到精確的數(shù)據(jù)，收集數(shù)據(jù)的設(shè)備可

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

5、類分析發(fā)現(xiàn)孤立點(diǎn)的方法有：基于統(tǒng)計(jì)的孤立點(diǎn)檢測(cè)，基于距離的孤立點(diǎn)檢測(cè)和基于偏離的孤立點(diǎn)檢測(cè)。2.1.2算法介紹下面是一個(gè)利用聚類算法來(lái)發(fā)現(xiàn)關(guān)系數(shù)據(jù)庫(kù)中孤立點(diǎn)數(shù)據(jù)的例子：輸入：數(shù)據(jù)集S，包括N條記錄，屬性集D：年齡、收入；本文稱一條記錄為一個(gè)數(shù)據(jù)點(diǎn)(Data Point)，一條記錄上的每個(gè)屬性上的值為一個(gè)數(shù)據(jù)單元格(Data Cel1)。S有ND個(gè)數(shù)據(jù)單元格，其中某些數(shù)據(jù)單元格是噪聲數(shù)據(jù)。輸出：孤立數(shù)據(jù)點(diǎn)如圖1所示。圖1通過(guò)聚類發(fā)現(xiàn)噪聲數(shù)據(jù)的例子孤立點(diǎn)A是一個(gè)孤立點(diǎn)數(shù)據(jù)，我們認(rèn)為它是噪聲數(shù)據(jù)，很明顯它的噪聲屬性足收入，剩下的干凈信息即年齡屬性上的數(shù)據(jù)仍然可以用于預(yù)測(cè)或其他應(yīng)用，同時(shí)可以利用年齡屬

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

7、通過(guò)聚類算法得到的孤立數(shù)據(jù)點(diǎn)集合矩陣，NM(i,j)的值對(duì)應(yīng)孤立點(diǎn)集合P中第i條記錄在屬性j上的值，即NM(i,j)=P污染矩陣(Corruption Matrix，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(S、D);/* 屬性集合D上對(duì)S進(jìn)行聚類，得到孤立點(diǎn)數(shù)據(jù)集臺(tái)P*/(2)If (P!=Nul1)ThenFor i=O to

8、length(P)For j=0 to kNM(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)生了噪聲*/Else CM(i，j)=0 (3)For EachD1 (1=i=k)P=GetNoiseByClustering(SD-D );/*在 DDD上對(duì)S聚類；*/For m=1 to length(P)if(CM (m ，i)=1)ThenNM(m，i)用行m所對(duì)應(yīng)的記錄rm所在的

9、聚集D1上的(平均)值替換；/*對(duì)于能夠劃定噪聲屬性的記錄，用干凈數(shù)據(jù)中D1上的(期望)值矯正*/Else 1f(CM(m，j)=0)(1=j=k)ThenIf行m所對(duì)應(yīng)的記錄rm 所在新的聚類P中不是孤立點(diǎn) then NM(m，i)用行m所對(duì)應(yīng)的紀(jì)錄rm 所在的聚集中D1上的(期望)值替換；/*對(duì)于不能判定噪聲屬性,并矯正*/ CM(m, i)=l： (4)For m=1 to length(P)/*矯正原始數(shù)據(jù) S;*/Forj=0 to kIf(CM=1)Then用NM(m，j)替換S中對(duì)應(yīng)的記錄屬性D1上的值 (5)返回S和NM：其中，過(guò)程GetNoiseByCIustering(S,

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

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

12、多工作成果是關(guān)于如何處理噪聲數(shù)據(jù)以及噪聲數(shù)據(jù)對(duì)分類學(xué)習(xí)算法的影響。在前人的工作中，大多沒(méi)有使用噪聲數(shù)據(jù)模型來(lái)有效地增強(qiáng)學(xué)習(xí)算法的分類效果。然而很少有工作研究如何充分利用噪聲模型來(lái)建立更優(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ì)上解決此問(wèn)題。在前人的工作中，一種普遍被接受的觀點(diǎn)是，如果訓(xùn)練數(shù)據(jù)集與測(cè)試數(shù)據(jù)集中存在相同的噪聲模型，則噪聲數(shù)據(jù)將會(huì)在訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)中起到相同的作用，因而可以忽略輸入數(shù)據(jù)中的不確定

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

14、1K近鄰算法。盡管有很多種計(jì)算實(shí)例之間距離的方法，但大多算法仍舊使用歐基里德距離 引。一個(gè)實(shí)例(a1 (1)，a2(1)， ，ak (1)和另一個(gè)實(shí)例(a1 (2)，a2(2)， ，ak (2)之間距離為： (1)其中，k為條件屬性個(gè)數(shù)。2噪聲模型。真實(shí)數(shù)據(jù)中的噪聲數(shù)據(jù)永遠(yuǎn)都是存在的。但噪聲數(shù)據(jù)產(chǎn)生的原因有很多種，如手工的誤操作、機(jī)器本身存在的誤差、傳輸過(guò)程中發(fā)生的錯(cuò)誤等等 。(1)系統(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)境如

15、：溫度、濕度、電磁場(chǎng)等環(huán)境的變化引發(fā)的誤差。方法誤差：由于計(jì)算公式的近似，沒(méi)有完全滿足理論公式所給定的條件。例如，單擺測(cè)重力加速度的實(shí)驗(yàn)中，采用了sin00的近似條。人員誤差：由測(cè)量者的個(gè)人因素造成的誤差。例如：按秒表時(shí)總是超前或滯后，讀數(shù)時(shí)頭總是向一邊偏等。(2)隨機(jī)誤差。由某些偶然的、不確定的因素所造成的誤差稱之為隨機(jī)誤差。若從一次測(cè)量來(lái)看，隨機(jī)誤差是隨機(jī)的，沒(méi)有確定的規(guī)律，也不能預(yù)測(cè)。但當(dāng)測(cè)量次數(shù)足夠多時(shí)，隨機(jī)誤差遵從一定的統(tǒng)計(jì)分布。因此，增加測(cè)量的次數(shù)，可以明顯地減少隨機(jī)誤差。其中一部分誤差是隨機(jī)的，沒(méi)有規(guī)律可循，如手工誤操作、傳輸錯(cuò)誤等；而另外一類，是有一定規(guī)律可循的，也就是說(shuō)這類噪

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

17、論正態(tài)分布中的兩個(gè)參數(shù)和對(duì)計(jì)算距離的影響?，F(xiàn)計(jì)算實(shí)例e1 和e2 的屬性a1 之間的距離。定理l對(duì)于某一屬性，其誤差服從正態(tài)分布，則其誤差均值 不會(huì)對(duì)兩個(gè)實(shí)例的該屬性之間的距離產(chǎn)生影響，此距離只受方差 的影響。但在數(shù)據(jù)集中，由于不同的屬性的度量單位不同，不同屬性的取值范圍也就不同。如對(duì)于屬性a1，的取值va2 范圍為10，80，其方差為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ù)完全精確

18、，方差為0時(shí)公式(2)無(wú)意義的情況。分子中取的是屬性值區(qū)間長(zhǎng)度，區(qū)間長(zhǎng)度與方差的比值，可以消除由不同的屬性值范圍所帶來(lái)的影響。以前面所說(shuō)為例，屬性a1的權(quán)重應(yīng)為：(80lO)/(3+1)=17.5；而屬性a2的權(quán)重為：(8-1)/(3+1)=1.75。從實(shí)際應(yīng)用角度看，這是合理的。兩個(gè)實(shí)例之間的距離由公式(1)轉(zhuǎn)化為如下距離公式： (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，否則為0。為了進(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é)果DataSet1DataSet1D