基于密度的數(shù)據(jù)清洗方法研究與評估

鄒杰，李書芳

(1.2.北京郵電大學信息與通信工程學院，北京 100876)

基于密度的數(shù)據(jù)清洗方法研究與評估

鄒杰1，李書芳2

(1.2.北京郵電大學信息與通信工程學院，北京 100876)

數(shù)據(jù)清洗的一個重要方面是發(fā)現(xiàn)數(shù)據(jù)中的異常數(shù)據(jù)或者噪聲，并對其進行處理。對于異常數(shù)據(jù)比例較多、數(shù)據(jù)質(zhì)量較差的數(shù)據(jù)，傳統(tǒng)的基于統(tǒng)計學的異常檢測方法結(jié)果往往不盡如人意，異常數(shù)據(jù)百分比越大，傳統(tǒng)的異常檢測算法的召回率越低。本文研究的數(shù)據(jù)清洗方法是采用數(shù)據(jù)挖掘領域中基于密度的異常數(shù)據(jù)挖掘算法，在數(shù)據(jù)質(zhì)量較差的情況下仍有較高的異常點召回率和準確率，對數(shù)據(jù)質(zhì)量的容忍度遠遠大于傳統(tǒng)的統(tǒng)計學方法。

數(shù)據(jù)清洗；數(shù)據(jù)挖掘；異常檢測

0 引言

近年來，各個行業(yè)的數(shù)據(jù)總量呈現(xiàn)爆炸式增長，例如，實時監(jiān)控數(shù)據(jù)、醫(yī)療大數(shù)據(jù)、互聯(lián)網(wǎng)流量數(shù)據(jù)、社交網(wǎng)絡大數(shù)據(jù)、網(wǎng)上金融交易數(shù)據(jù)、電網(wǎng)大數(shù)據(jù)等等。這些數(shù)據(jù)或短期內(nèi)數(shù)據(jù)規(guī)模極大，或采集時間特別長，或數(shù)據(jù)模式改變特別頻繁，或維數(shù)特別高。不像傳統(tǒng)的數(shù)據(jù)，由于數(shù)據(jù)量大的原因，它們不能像傳統(tǒng)那樣采用手工的方法進行數(shù)據(jù)清洗。一方面，手工清洗的成本太高，另一方面，手工清洗效率慢，所以基于數(shù)據(jù)挖掘和人工智能的數(shù)據(jù)清洗方法成為研究的熱點。數(shù)據(jù)清洗的內(nèi)容主要涉及異常數(shù)據(jù)檢測、重復記錄檢測和不同來源數(shù)據(jù)的集成等方面。異常數(shù)據(jù)檢測(anomaly data detection)是數(shù)據(jù)清洗的重要方面，也是一個數(shù)據(jù)挖掘的過程。異常數(shù)據(jù)檢測不僅能夠檢測臟數(shù)據(jù) (dirty data)，還能檢測網(wǎng)絡入侵、信用卡詐騙以及預測天氣、股市等。

異常數(shù)據(jù)挖掘是異常檢測和數(shù)據(jù)挖掘的交叉領域，又叫做離群點挖掘。傳統(tǒng)的異常檢測手段依賴統(tǒng)計學知識對數(shù)據(jù)進行全面的分析處理，如果一個觀測點遠離其他觀測點，那么這個觀測點就是一個異常數(shù)據(jù)[1]；而在數(shù)據(jù)挖掘領域，如果數(shù)據(jù)的特征或者模式與其他數(shù)據(jù)不相符，那么稱之為異常數(shù)據(jù)[2]。異常數(shù)據(jù)檢測廣泛應用于入侵檢測，欺詐檢測，故障檢測，系統(tǒng)健康監(jiān)測，傳感器網(wǎng)絡事件檢測等方面，提高系統(tǒng)的安全性。尤其在監(jiān)督學習算法的實驗中，去除異常數(shù)據(jù)通常極大的優(yōu)化結(jié)果。

1 相關工作

1.1 異常數(shù)據(jù)挖掘

隨著數(shù)據(jù)挖掘的飛速發(fā)展，異常數(shù)據(jù)挖掘技術也呈現(xiàn)翻天覆地的變化，這些技術大致可以分為基于密度的異常數(shù)據(jù)挖掘算法[3]、基于神經(jīng)網(wǎng)絡的異常數(shù)據(jù)挖掘算法[4]、基于相關性的異常數(shù)據(jù)挖掘算法[5]、基于SVM的異常數(shù)據(jù)挖掘算法[6]、基于模糊邏輯的異常數(shù)據(jù)挖掘算法和基于集成技術的異常數(shù)據(jù)挖掘算法[7]。這些算法幾乎沒有優(yōu)劣之分，它們的性能很大程度上取決于數(shù)據(jù)集本身的特點以及參數(shù)的選擇。

1.2 基于密度的聚類

基于密度的聚類有非常多經(jīng)典算法，其中最有名的算法之一是k-Nearest Neighbor算法，簡稱k-NN。k-NN算法是模式識別中用于構造分類器和回歸模型的無參數(shù)算法[8]，其原理非常容易理解，是數(shù)據(jù)挖掘應用最廣泛的算法之一?；诿芏鹊漠惓?shù)據(jù)挖掘算法的重大飛躍要數(shù)Density-based spatial clustering of applications with noise (DBSCAN)算法，DSBCAN算法用來對海量數(shù)據(jù)進行聚類，它是一種無監(jiān)督的異常數(shù)據(jù)檢測算法，1996年由Martin Ester，Hans-Peter Kriegel，J?rg Sander 和 Xiaowei Xu共同提出[9]。相對于其它異常數(shù)據(jù)挖掘算法，DBSCAN算法具有更高的效率以及更廣泛的應用，2014年KDD授予它TEST OF TIME獎，用以表彰它同時具備極高的理論水準和廣泛的實用價值。DBSCAN不僅能夠高效地對靜態(tài)數(shù)據(jù)進行聚類，同時能夠識別數(shù)據(jù)集中的異常數(shù)據(jù)，所以可以識別數(shù)據(jù)集中的異常數(shù)據(jù)。DBSCAN與其他經(jīng)典的算法一樣也具有局限性，原作者在發(fā)表DBSCAN第3年把DBSCAN算法推廣到一般情況，稱之為Generalized DBSCAN(GDBSCAN)算法[10,11]；Campello等學者在前人的基礎上改進了DBSCA，他們把邊界值視為異常數(shù)據(jù)，從而避免了聚類結(jié)果的不確定性，從而使聚類結(jié)果具有更強的一致性[12]；Markus M.Breunig，Hans-Peter等人受到DBSCAN的啟發(fā)，提出了經(jīng)典的Ordering points to identify the clustering structure(OPTICS)算法，解決DBSCAN算法不能很好聚類數(shù)據(jù)集密度跨度較大的缺點[13]； Markus M.Breunig先后提出著名的異常數(shù)據(jù)檢測算法OPTICS-OF算法[14,15]和Local Outlier Factor(LOF)算法[16]，這兩種算法的思想大同小異，它們對特定數(shù)據(jù)集的異常數(shù)據(jù)檢測效率明顯高于其他異常數(shù)據(jù)檢測方法，后者LOF算法較OPTICS-OF算法更廣泛為人熟知。

2 基于密度的數(shù)據(jù)清洗框架

本節(jié)詳細描述基于密度的數(shù)據(jù)清洗框架，框架的圖形表示見圖1。

2.1 缺失數(shù)據(jù)處理

缺失數(shù)據(jù)(missing data)：由于數(shù)據(jù)采集器的性能受天氣、地理位置等因素影響，實際數(shù)據(jù)極易受到污染，容易出現(xiàn)數(shù)據(jù)缺失的情況。某些情況下，數(shù)據(jù)缺失并不會對結(jié)果造成很大的影響，比如非重要屬性的缺失。但是，重要屬性缺失卻能大大降低數(shù)據(jù)的質(zhì)量。

2.2 特征選擇

特征選擇(feature selection)：在數(shù)據(jù)挖掘中，特征選擇又叫做變量子集選擇或者屬性選擇，是構造模型過程中選擇相關的特征集合的子集的過程。數(shù)據(jù)集中總是涵括一些冗余或者不相關的特征，因此，特征選擇并不減少信息量。

2.3 密度特征提取

特征提取(feature extraction)：在數(shù)據(jù)挖掘、模式識別或者圖像處理中，特征提取是發(fā)現(xiàn)或者挖掘初始數(shù)據(jù)潛在的特征，以便于從更好的角度去解釋數(shù)據(jù)或者建立更好的學習模型。數(shù)據(jù)集的體量太大很多時候是因為冗余信息過多造成的，提取的特征一般包含數(shù)據(jù)集中相關的有重要價值的屬性信息，丟棄另外不相關的屬性，降低數(shù)據(jù)集的特征維度，從而使得數(shù)據(jù)集更適合學習模型。

圖1 基于密度的數(shù)據(jù)清洗框架

2.4 異常檢測

數(shù)據(jù)挖掘中異常檢測是指發(fā)現(xiàn)數(shù)據(jù)集中不滿足一定模式的數(shù)據(jù)或者觀測點，異常數(shù)據(jù)通常又稱為離群點、噪聲點、偏差點和例外點。例如，網(wǎng)絡入侵檢測通常不是發(fā)現(xiàn)特別罕見的事件，而是發(fā)現(xiàn)不可預測的突發(fā)性的活動。用傳統(tǒng)異常檢測方法，如統(tǒng)計學方法，就不太容易發(fā)現(xiàn)這種異常事件，于是基于聚類分析的算法有了用武之地，它能夠發(fā)現(xiàn)并且檢測到這些微小的簇和模式，從來檢測網(wǎng)絡入侵。

異常檢測通?？煞譃槿悾簾o監(jiān)督異常檢測、半監(jiān)督異常檢測和監(jiān)督異常檢測。無監(jiān)督異常檢測，顧名思義，是指檢測無標簽的數(shù)據(jù)集中的異常數(shù)據(jù)，無標簽數(shù)據(jù)中常規(guī)數(shù)據(jù)一般占一半以上。半監(jiān)督異常檢測指，從一個常規(guī)訓練數(shù)據(jù)集中構建一個模型，這個模型描述了數(shù)據(jù)集的一定模式，然后用測試實例來檢測模型的最大似然。監(jiān)督異常檢測，指對有標簽的數(shù)據(jù)集進行訓練得到一個分類器，然后利用分類器檢測測試數(shù)據(jù)。

3 基于密度的數(shù)據(jù)清洗算法

3.1 DBSCAN算法

在空間數(shù)據(jù)集中，任何一個數(shù)據(jù)對應笛卡爾坐標系中一個點，數(shù)據(jù)的每一個屬性即空間坐標系中的一個坐標軸。當數(shù)據(jù)集是一個以地理位置的經(jīng)緯度作為屬性時，那么每一個數(shù)據(jù)對應一個二維笛卡爾坐標系上的一個點；當給每個點增加一個海拔屬性時，每一個數(shù)據(jù)則對應三維笛卡爾坐標系上的一個點；以此類推。從數(shù)學原理出發(fā)，兩點之間直線最短，所以歐氏距離是兩點在歐氏空間上直線的距離。

給定一個空間數(shù)據(jù)集D，給出如下定義：

ε鄰域：以點p為圓心，半徑為ε的園覆蓋的區(qū)域稱為點p的ε鄰域；

核心點：如果點p的ε領域內(nèi)的數(shù)據(jù)點數(shù)大于或者等于minPts，那么點p為核心點，p對ε領域內(nèi)的所有點都是直接密度可達的。minPts是ε領域內(nèi)點數(shù)的臨界值。

根據(jù)核心點的定義不難得到：如果點p不是核心點，那么p對任何點都不是直接密度可達的。

密度可達：如果直接密度可達，也直接密度可達，那么密度可達。

密度相連：如果o點對p點和q點都是密度可達的，那么p點和q點是密度相連的。

異常點：非核心點中，都不密度可達的點稱為異常點。

臨界點：非核心點中，密度可達的點稱為臨界點。

圖2 基于DBSCAN算法的異常點示圖

圖2中，ε鄰域臨界值minPts=3，A點與其他黑色實心點ε領域內(nèi)的點數(shù)大于或者等于minPts，所以為核心點；F點、N點為為非核心點，距離F點最近的核心點直接密度可達F點，所以F點為臨界點，所有點N點密度不可達，于是N點是異常點。根據(jù)核心點的定義可以得到：如果點p不是核心點，那么p點不能密度可達所有點，即：非核心點（如B點和C點）可以被核心點密度達到，卻不能密度可達其他點，所以密度可達是非對稱關系；而根據(jù)密度相連的定義可以推出密度相連具有對稱關系。

DBSCAN算法如下：

算法一：DBSCAN算法

（1）遍歷沒有訪問過的點p:

若p的ε領域的點數(shù)大于或等于minPts，建立一個新簇Ci，將ε領域內(nèi)的所有點加入點集NeighborPts；

若p的ε鄰域的點數(shù)小于minPts，p點標記為Noise；

（2）遍歷NeighborPts中未訪問過的點p’：

若p’的ε領域的點數(shù)大于或等于minPts，則將p’鄰域的點加入點集NeighborPts；

若p’不屬于任何一個類，則加入族Ci；

DBSCAN算法參數(shù)有兩個，分別是鄰域半徑ε和臨界值minPts。初始每個點都設為未訪問標志，然后開始訪問每一個未訪問點，如果該點的ε鄰域內(nèi)的點數(shù)（包括本身）大于minPts，那么標記該點為核心點，并且新建一個簇，并且包含該點；如果不是核心點，則標記為異常點。

對于每個簇內(nèi)的每個點，它們的ε鄰域包含的點的密度如果超過臨界值minPts，那么這些點也是簇的一部分，這樣，每個簇能夠發(fā)現(xiàn)附近密度近似的簇并且與其合并成一個更大的簇。當所有密度相連的簇都合并完成后，再對下一個未訪問的點進行同樣的處理，循環(huán)直到所有的點都訪問完成為止。

3.2 LOF算法

LOF算法和DBSCAN的許多概念相同，比如鄰域、歐式距離、密度可達等，也有不一樣的概念。給定一個數(shù)據(jù)集D，距離點A由近及遠的k個點記為NK(A)，A與NK(A)的距離記為k-distance(A)。那么A與B的可達距離定義為：

點A的局部可達密度(local reachable density)lrd(A)為：

lrd(A)表示A與鄰域的平均可達距離的倒數(shù)。局部異常因子為：

如果點A的局部異常因子近似為1，它表示點A的密度與其領域點密度屬于同一種模式；如果點A的局部可達密度遠小于或者遠大于1，它表示點A的密度與其領域點密度不屬于同一個模式，點A為異常點。LOF算法通過計算與相鄰點的可達密度偏差發(fā)現(xiàn)異常數(shù)據(jù)，也是一種基于密度的數(shù)據(jù)清洗算法[15]。其算法可描述為：

算法二：LOF算法

遍歷沒有訪問過的點p:

計算點p與的距離k-distance(p，0)；

計算p與領域點o的可達距離；

利用公式（3）計算點p的局部可達密度lrd(p)；

利用公式（4）計算p的局部異常因子，如果p的局部異常因子遠小于或者遠大于1，則標記p點為異常點；如果p約為1，那么p為聚類點。

與DBSCAN一樣，LOF也是基于密度的數(shù)據(jù)清洗算法。它定義點的局部k鄰域點集，然后計算該點的局部密度，通過比較該點的局部密度與領域點的局部密度來判斷該點是否為異常點。密度可達是通過該點的鄰域點估算的可達距離來確定的，它在LOF算法中能夠極大提高結(jié)果的穩(wěn)定性。

4 實驗結(jié)果及其評估

4.1 數(shù)據(jù)集簡介

數(shù)據(jù)集(dataset)：大部分數(shù)據(jù)集對應數(shù)據(jù)庫的一張表或者一個數(shù)據(jù)矩陣，表的每列代表一個特定含義的屬性或者變量，每行對應一條記錄，通常為一組采集的數(shù)據(jù)，每一行均描述每一個屬性或者變量的數(shù)值。常見的空間數(shù)據(jù)集一般用經(jīng)緯度、海拔等屬性用來描述實體的地理位置，除此之外，還有利用復雜的幾何圖形如點、線、以及多邊形來描述實體的空間位置，這樣的數(shù)據(jù)集一般存儲在具有復雜數(shù)據(jù)存儲結(jié)構的數(shù)據(jù)庫中，例如3D結(jié)構數(shù)據(jù)庫，拓撲覆蓋結(jié)構數(shù)據(jù)庫，線性網(wǎng)絡結(jié)構數(shù)據(jù)庫，TIN(triangulated irregular network)結(jié)構數(shù)據(jù)庫。

本章的數(shù)據(jù)清洗對象為空間數(shù)據(jù)集?？臻g數(shù)據(jù)集通常可以表示為一個矩陣，一個M行記錄、N列字段數(shù)據(jù)集DS表示為M×N的矩陣，數(shù)學符號表示為:

也可以表示為：

本章的數(shù)據(jù)存儲在PLT文件中，每個文件夾下包含若干個PLT格式文件，每個PLT文件的文件名為數(shù)據(jù)開始采集的時間，例如“20081023025304.plt”文件名表示數(shù)據(jù)于2008年10月23日02:53:04開始采集，時間均以GMT(Greenwich Mean Time)為準，“.plt”為文件格式。

PLT文件格式說明：

第一行…第六行：沒有實際意義的可以忽略的數(shù)據(jù)。

從第七行開始到最后一行：

字段1：緯度，十進制。

字段2：經(jīng)度：十進制。

字段3：所有均為0，無意義。

字段4：海拔高度，單位英尺（-777表示為空）

字段5：日期，記錄1899年12月30日起到現(xiàn)在經(jīng)過多少天。

字段6：日期，“XXXX-XX-XX”格式。

字段7：時間，“XX:XX:XX”格式

例子：

表1 GPS軌跡數(shù)據(jù)示例

本文處理的空間數(shù)據(jù)來自于某開源數(shù)據(jù)庫GPS軌跡數(shù)據(jù)集，該項目的數(shù)據(jù)采集時間跨度超過5年（50,176小時），數(shù)據(jù)集包括17621條軌跡，總長度達1,292,95千米。數(shù)據(jù)采集自不同手機的GPS模塊，采樣頻率從1秒/次到5秒/次或者5米/次到10米/次。雖然數(shù)據(jù)的地理位置橫跨太平洋與大西洋，但是大部分數(shù)據(jù)具有地理密集的特點，91.5%集中在北京市（北緯39’’26’至41’’03’，東經(jīng)115’’25’至 117’’30’）。

在數(shù)據(jù)收集過程中，一部分樣本采集時間長達數(shù)年，然而也有一部分樣本采集時間才幾個星期，圖3表示空間軌跡數(shù)據(jù)距離分布；圖4表示空間軌跡數(shù)據(jù)總時長分布；圖5表示空間軌跡數(shù)據(jù)時間段分布；圖6表示采集時間分布和采集軌跡數(shù)量分布。

圖3 空間軌跡數(shù)據(jù)距離分布

圖4 空間軌跡數(shù)據(jù)總時長分布

圖5 空間軌跡數(shù)據(jù)時間段分布

圖6 空間軌跡數(shù)據(jù)軌跡數(shù)量分布

4.2 性能評估指標

為了評估算法的性能，有兩種衡量清洗結(jié)果的評估指標：召回率（或者查全率）(recall rate)、誤報率（或者查準率）(false alarm rate)。查全率和查準率是評估分類算法性能的最廣泛的指標，本節(jié)查全率是正確檢測的異常數(shù)據(jù)占樣本總異常點的百分比，記作Detection Rate；誤報率是指被誤認為異常的正常數(shù)據(jù)占總的正常數(shù)據(jù)的百分比，記作False Alarm Rate。兩種指標定義如下：

4.3 性能評估

以數(shù)據(jù)點數(shù)作為變量，研究基于密度的數(shù)據(jù)清洗方法（DBSCAN算法與LOF算法）與傳統(tǒng)的統(tǒng)計方法進行比較，實驗結(jié)果如圖7~圖12。

圖7 5%異常數(shù)據(jù)集的召回率

圖8 10%異常數(shù)據(jù)集的召回率

圖9 15%異常數(shù)據(jù)集的召回率

圖10 20%異常數(shù)據(jù)集的召回率

圖11 25%異常數(shù)據(jù)集的召回率

圖12 30%異常數(shù)據(jù)集的召回率

通過分析圖7~圖8可以得出結(jié)論，當異常數(shù)據(jù)比例不大于10%的時候，基于密度的數(shù)據(jù)清洗算法與傳統(tǒng)算法的異常點召回率均能達到90%以上，尤其是基于DBSCAN的數(shù)據(jù)清洗算法能夠達到98%以上的召回率；通過分析圖11~圖12可以得出結(jié)論，當異常數(shù)據(jù)比例高于25%的時候，DBSCAN算法和LOF算法的異常點召回率均在90%以上，而傳統(tǒng)的統(tǒng)計學方法的異常點召回率低于90%，基于密度的數(shù)據(jù)清洗算法的性能遠遠超過傳統(tǒng)的數(shù)據(jù)統(tǒng)計方法。

以數(shù)據(jù)點數(shù)作為變量，研究基于密度的數(shù)據(jù)清洗方法（DBSCAN算法與LOF算法）與傳統(tǒng)的統(tǒng)計方法進行比較，實驗結(jié)果如圖13~圖16。

圖13 2000數(shù)據(jù)點的召回率

圖14 4000數(shù)據(jù)集的召回率

圖15 6000數(shù)據(jù)集的召回率

圖16 8000數(shù)據(jù)集的召回率

通過分析圖13~圖16可以得出結(jié)論，當異常數(shù)據(jù)百分比小于25%時，數(shù)據(jù)集的體量越大，異常數(shù)據(jù)的召回率越低；當異常數(shù)據(jù)百分比大于25%時，基于密度的數(shù)據(jù)清洗算法召回率趨近于穩(wěn)定，而傳統(tǒng)的統(tǒng)計學方法召回率仍越來越低。

4.4 數(shù)據(jù)量對運行時間的影響

本節(jié)主要研究數(shù)據(jù)量的大小對算法（DBSCAN、LOF和統(tǒng)計學方法）運行時間的影響，數(shù)據(jù)量大小為2000~10000，運行結(jié)果如圖17。

從表中可以看出，基于傳統(tǒng)統(tǒng)計學方法的數(shù)據(jù)清洗時間非常小，基于數(shù)據(jù)挖掘的數(shù)據(jù)清洗算法隨著數(shù)據(jù)量增大，運行時間呈指數(shù)增長，其中LOF算法增長率最大；隨著數(shù)據(jù)量超9000點，基于挖掘算法的數(shù)據(jù)清洗時間遠遠大于基于統(tǒng)計方法的數(shù)據(jù)清洗時間。基于以上分析，可以預測當數(shù)據(jù)量特別大的時候，基于密度的數(shù)據(jù)清洗算法運行時間會是一個急需解決的問題。

圖17 數(shù)據(jù)體量對運行時間的影響

5 結(jié)論

本章的主要工作是建立一個基于密度的異常數(shù)據(jù)清洗框架，對空間數(shù)據(jù)集進行數(shù)據(jù)清洗，并且利用相關算法性能指標對DBCSAN算法、LOF算法和傳統(tǒng)的統(tǒng)計學方法在異常數(shù)據(jù)檢測方面的性能進行比較，最后研究數(shù)據(jù)量的大小與DBSCAN算法、LOF算法和傳統(tǒng)統(tǒng)計學方法的運行時間之間的關系。實驗結(jié)果表明，基于密度的數(shù)據(jù)清洗算法的召回率性能優(yōu)于傳統(tǒng)的統(tǒng)計方法；當異常數(shù)據(jù)百分比越大，基于密度的數(shù)據(jù)清洗算法越能體現(xiàn)其優(yōu)秀的異常數(shù)據(jù)檢測性能；傳統(tǒng)的統(tǒng)計學方法的運行時間比小于基于密度的數(shù)據(jù)清洗算法；數(shù)據(jù)量越大，傳統(tǒng)的統(tǒng)計學方法基本呈線性增加，基于密度的數(shù)據(jù)清洗算法運行時間呈指數(shù)增長。

[1]Grubbs， F.E.Procedures for detecting outlying observations in samples[J].Technometrics.196，11（1）：1-21.

[2]Chandola， V.; Banerjee， A.; Kumar， V.Anomaly detection： A survey[J].ACM Computing Surveys.2009 41 （3）： 1-58.

[3]Knorr， E.M.; Ng， R.T.; Tucakov， V.Distance-based outliers： Algorithms and applications[J].The VLDB Journal the International Journal on Very Large Data Bases.2000 8 （3-4）：237–253.

[4]Hawkins， Simon; He， Hongxing; Williams， Graham; Baxter， Rohan.Outlier Detection Using Replicator Neural Networks[J].Data Warehousing and Knowledge Discovery.Lecture Notes in Computer Science.2002 2454.pp.170-180.

[5]Kriegel， H.P.; Kroger， P.; Schubert， E.; Zimek， A.Outlier Detection in Arbitrarily Oriented Subspaces[C].2012 IEEE 12th International Conference on Data Mining.2012 p.379.

[6]Sch?lkopf， B.; Platt， J.C.; Shawe-Taylor， J.; Smola， A.J.; Williamson， R.C.Estimating the Support of a High-Dimensional Distribution[C].Neural Computation.2001 13 （7）： 1443-71.

[7]Lazarevic， A.; Kumar， V.Feature bagging for outlier detection[C].Proc.11th ACM SIGKDD international conference on Knowledge Discovery in Data Mining： 2005 p.157-166.

[8]Altman， N.S.An introduction to kernel and nearest-neighbor nonparametric regression[J].The American Statistician.1992，46 （3）： 175-185.

[9]Ester， Martin; Kriegel， Hans-Peter; Sander， J?rg; Xu， Xiaowei.Simoudis， Evangelos; Han， Jiawei; Fayyad， Usama M.， eds.A densitybased algorithm for discovering clusters in large spatial databases with noise[C].Proceedings of the Second International Conference on Knowledge Discovery and Data Mining （KDD-96）.AAAI Press.1996 pp.226-231.

[10]Sander， J?rg.Generalized Density-Based Clustering for Spatial Data Mining[C].München： Herbert Utz Verlag.1998.

[11]Sander， J?rg; Ester， Martin; Kriegel， Hans-Peter; Xu， Xiaowei.Density-Based Clustering in Spatial Databases： The Algorithm GDBSCAN and Its Applications[C].Data Mining and Knowledge Discovery.Berlin： Springer-Verlag.1998，2 （2）： 169-194.

[12]Campello， R.J.G.B.; Moulavi， D.; Sander， J.Density-Based Clustering Based on Hierarchical Density Estimates[C].Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery in Databases， PAKDD 2013.Lecture Notes in Computer Science.2013 7819.p.160.

[13]Mihael Ankerst， Markus M.Breunig， Hans-Peter Kriegel， J?rg Sander.OPTICS： Ordering Points To Identify the Clustering Structure[C].ACM SIGMOD international conference on Management of data.ACM Press.1999 pp.49-60.

[14]Markus M.Breunig， Hans-Peter Kriegel， Raymond T.Ng and J?rg Sander.OPTICS-OF： Identifying Local Outliers[C].Principles of Data Mining and Knowledge Discovery.Berlin： Springer-Verlag.1999.pp.262-270.

[15]Breunig， M.M.; Kriegel， H.-P.; Ng， R.T.; Sander， J.LOF： Identifying Density-based Local Outliers[C].Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.SIGMOD.2000 pp.93-104.

Density-based Data Cleaning Method Research and Evaluation

ZHOU Jie1, LI Shu-fang2
(School of communication engineering, Beijing University of Posts and Telecommunications,Beijing 100876)

One of the important aspects of data cleaning is to fi nd out the anomaly data or noise in the data, and to deal with it.For data with large percentage of anomaly, or data of poor quality, the traditional anomaly detection method based on statistics is not satisfactory, because the greater the percentage of abnormal data is, the lower the recall rate of traditional anomaly detection algorithms is.Data cleaning methods in this paper are density-based outlier data mining algorithms in the fi eld of data mining, on the condition of poor quality of the data, this method still perform with high recall rate and accuracy, the data quality tolerance is far greater than the traditional statistical methods.

Data cleaning; Data mining; Anomaly detection

本文引用格式：鄒杰,李書芳.基于密度的數(shù)據(jù)清洗方法研究與評估.電子元器件與信息技術[J]，2017，1（1）：50-58.

項目名稱：2016國家電網(wǎng)科技項目（基于營配信息貫通的業(yè)務融合與數(shù)據(jù)共享服務技術）

鄒杰，男，主要研究領域為數(shù)據(jù)分析，數(shù)據(jù)清洗，機器學習；李書芳，女，教授，博士生導師，主要研究領域為無線射頻新技術和標準研究，數(shù)據(jù)挖掘與分析。

:ZHOU Jie, LI Shu-fang.Density-based Data Cleaning Method Research and Evaluation.Journal of electronic components and information technology[J]，2017，1（1）：50-58.