數據挖掘噪聲數據處理綜述

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

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

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

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

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

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

7、通過聚類算法得到的孤立數據點集合矩陣，NM(i,j)的值對應孤立點集合P中第i條記錄在屬性j上的值，即NM(i,j)=P污染矩陣(Corruption Matrix，CM)：NM 對應的一個01布爾矩陣，NM(i,j)為噪聲=CM（ij)=1；否則，CM(i,j)=0。基本算法描述：輸入：含噪聲數據的數據集S，S有N個數據對象，S的屬性集合D=D1，D2， ，Dk 。輸出：噪聲數據矯正后的數據集合S，污染矩陣CM方法：(1)P=GetNo1seByClustering(S、D);/* 屬性集合D上對S進行聚類，得到孤立點數據集臺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) ThenCM(i，j)=1：/* 替NM(i，j)與S中D1上的期望之間的距離大于某個閾值，則判定D1上產生了噪聲*/Else CM(i，j)=0 (3)For EachD1 (1=i=k)P=GetNoiseByClustering(SD-D );/*在 DDD上對S聚類；*/For m=1 to length(P)if(CM (m ，i)=1)ThenNM(m，i)用行m所對應的記錄rm所在的

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

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

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

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

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

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

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

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

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

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