基于改進DBS CAN算法的異常數(shù)據(jù)處理

黃靜 官易楠

摘要：隨著智慧農(nóng)業(yè)的發(fā)展，農(nóng)業(yè)生產(chǎn)中海量數(shù)據(jù)不斷涌現(xiàn)。在海量數(shù)據(jù)中難免存在噪聲數(shù)據(jù)，這些數(shù)據(jù)不僅難以提供有效價值，還會影響信息挖掘。針對該問題，采用基于密度的DBSCAN聚類算法進行異常數(shù)據(jù)處理。鑒于DBSCAN算法對參數(shù)敏感，結(jié)合數(shù)據(jù)集本身特性與統(tǒng)計學(xué)思想以繪制各點之間的距離升序曲線，預(yù)估出DBSCAN的Eps參數(shù)。仿真實驗結(jié)果表明，改進算法平均準(zhǔn)確率達(dá)到99.6%，較傳統(tǒng)算法提高了1.7個百分點，并且在10次檢測中，改進算法只有3個數(shù)據(jù)判定錯誤，證明該參數(shù)設(shè)置方法對異常數(shù)據(jù)處理準(zhǔn)確率更高，穩(wěn)定性也更好。

關(guān)鍵詞：智慧農(nóng)業(yè);聚類算法;DBSCAN;異常數(shù)據(jù)

DOI： 10. 11907/rjdk.191763

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP39

文獻標(biāo)識碼：A

文章編號：1672-7800（2020）004-0219-05

0 引言

在現(xiàn)代農(nóng)業(yè)發(fā)展過程中，智慧農(nóng)業(yè)越來越受到重視，其突出表現(xiàn)是人們通過數(shù)據(jù)采集設(shè)備獲取農(nóng)作物生長信息，從而更實時精確地了解農(nóng)作物生長狀況，較好地擺脫了傳統(tǒng)僅依靠經(jīng)驗種植的不足[1]。但是在采集到的海量數(shù)據(jù)中，由于外界干擾或者設(shè)備異常等原因會存在噪聲數(shù)據(jù)。這些數(shù)據(jù)不僅不能反映農(nóng)作物真實情況，可能還會影響農(nóng)作物生長狀況分析，導(dǎo)致分析結(jié)果出現(xiàn)偏差甚至錯誤[2]。

針對異常數(shù)據(jù)處理，依據(jù)異常數(shù)據(jù)在數(shù)據(jù)集中數(shù)量較少且離散分布的特點[3]，在統(tǒng)計學(xué)中有標(biāo)準(zhǔn)差法和t一檢驗法等異常數(shù)據(jù)檢驗方法[4]。這些方法通過分析數(shù)據(jù)分布情況，判斷數(shù)據(jù)點在數(shù)據(jù)集中出現(xiàn)的概率，當(dāng)數(shù)據(jù)出現(xiàn)概率特別低時，判定該數(shù)據(jù)為異常數(shù)據(jù)。此類方法在一定程度上可識別出異常數(shù)據(jù)，但不能較好地對數(shù)據(jù)進行處理[5]。

數(shù)據(jù)挖掘中常用聚類工具可以對異常數(shù)據(jù)進行檢測和處理。通過對數(shù)據(jù)集進行聚類分析，將相似數(shù)據(jù)點歸為一個聚類簇，出現(xiàn)單個數(shù)據(jù)為一類或者極少數(shù)數(shù)據(jù)為一類的數(shù)據(jù)點可以判定為異常數(shù)據(jù)。聚類算法有許多種類，其中基于密度的聚類算法[6]可以通過聚類密度劃分聚類簇，分析聚類密度，密度較為密集的被認(rèn)定為一個簇，密度特別稀疏的可以被認(rèn)定為噪聲數(shù)據(jù)?；诿芏鹊脑肼晳?yīng)用空間聚類（Densitv-Based Spatial Clustering of Applicationswith Noise，DBSCAN）[7]是其中具有代表性的一種算法。DBSCAN算法在異常數(shù)據(jù)處理中得到了廣泛應(yīng)用。馬世欣等[8]利用DBSCAN算法能夠?qū)Ξ惓?shù)據(jù)進行篩選的特點，對局部背景像元中的雜亂點進行過濾，以降低異常數(shù)據(jù)點對協(xié)同探測算法結(jié)果的干擾;潘淵洋等[9]利用DBSCAN算法進行傳感器網(wǎng)絡(luò)測量數(shù)據(jù)的異常檢測，提出通過提取環(huán)境數(shù)據(jù)的特征集，根據(jù)特征集進行異常數(shù)據(jù)監(jiān)測，達(dá)到對測量數(shù)據(jù)實時監(jiān)測的效果。

DBSCAN算法雖然能夠識別并處理異常數(shù)據(jù)，但是由于算法對參數(shù)比較敏感，不同的參數(shù)對結(jié)果影響較大。針對此問題，宋金玉等[10]提出了Eps和MinPts兩個參數(shù)的配置方法，通過將數(shù)據(jù)集本身統(tǒng)計特性與圖表可視化展示相結(jié)合，為算法確定合適的參數(shù);夏魯寧等[11]通過對數(shù)據(jù)集進行統(tǒng)計分析自動確定Eps和MinPts參數(shù)，從而避免了聚類過程的人工干預(yù)，實現(xiàn)聚類過程的全自動化，提高算法的準(zhǔn)確率和穩(wěn)定性。

以上方法都能夠在一定程度上實現(xiàn)對異常數(shù)據(jù)的檢測和處理，但是大多數(shù)方法檢測出異常數(shù)據(jù)后都是將數(shù)據(jù)直接刪除，這樣會造成信息丟失。因此，在處理異常數(shù)據(jù)時，將噪聲數(shù)據(jù)與其距離較近的聚類簇中心值進行替換[12]。本文依據(jù)以往研究成果，提出將DBSCAN算法與統(tǒng)計學(xué)思想相結(jié)合，通過對數(shù)據(jù)集中對象的距離值進行統(tǒng)計分析，預(yù)估出Eps參數(shù)。由于傳感器采集數(shù)據(jù)變化較為平緩，在以往研究中MinPts的值一般較為固定，因而MinPts采用經(jīng)驗進行確定。本文采用統(tǒng)計思想與經(jīng)驗判斷相結(jié)合的參數(shù)設(shè)置方式，在提高異常數(shù)據(jù)檢測準(zhǔn)確率的同時，還減少了計算量和時間，同時采用聚類簇中心值替換噪聲數(shù)據(jù)的異常數(shù)據(jù)處理方式，一定程度上保留了數(shù)據(jù)信息。

1 DNSCAN算法

1.1 算法原理

DBSCAN算法是一種通過數(shù)據(jù)對象密度進行查找相似屬性的聚類算法[13]。該算法不需要提前確定聚類簇的數(shù)量，不僅能夠?qū)θ我鈹?shù)據(jù)進行聚類，還能識別數(shù)據(jù)中的噪聲點，因而可以用來對異常數(shù)據(jù)進行處理[14]。其中DB-SCAN算法關(guān)鍵定義如下：

（7）簇。所有密度相連的點組成的集合。

在一個數(shù)據(jù)集中，并不是所有數(shù)據(jù)對象都是核心對象，還有邊緣對象和噪聲對象。邊緣對象表示數(shù)據(jù)對象不是核心對象，但是存在于某個核心對象的8-鄰域中;噪聲對象表示該數(shù)據(jù)對象不是核心對象，也不存在于任何核心對象的ε-鄰域中。

1.2 算法流程

通過以上定義可知，DBSCAN算法的核心在于參數(shù)Eps和MinPts，通過這兩個參數(shù)確定每個點的鄰域和核心對象，繼而通過核心對象尋找密度可達(dá)點，從而實現(xiàn)數(shù)據(jù)對象聚類。

DBSCAN算法流程如下：

Stepl：輸入的數(shù)據(jù)集D={x1，x2，…，xn}，ε為半徑參數(shù)，MinPts為最小對象參數(shù)，將數(shù)據(jù)集D中所有對象標(biāo)記為未讀。

Step2：從數(shù)據(jù)集D中取包含任意個數(shù)據(jù)對象p的數(shù)據(jù)集Di，其中Di∈D，i=1，2，3-，并將Di標(biāo)記為已讀。

Step3：通過ε和MinPts參數(shù)對p進行判斷，如果p為核心對象，找出p的所有密度可達(dá)數(shù)據(jù)對象，并標(biāo)記為已讀。若p不是核心對象，且沒有哪個對象對p密度可達(dá)，將p標(biāo)記為噪聲數(shù)據(jù)。

Step4：在滿足Di∩ Di=1.∈⑦的條件下，重復(fù)Step2和Step3，直至所有數(shù)據(jù)都標(biāo)記為已讀。

Step5：將其中一個核心對象作為種子，將該對象的所有密度可達(dá)點都?xì)w為一類，形成一個較大范圍的數(shù)據(jù)對象集合，也稱為聚類簇。

Step6：不斷循環(huán)Step5直至所有核心對象都遍歷完，剩下沒有歸為一類的數(shù)據(jù)便為噪聲點。

DBSCAN算法流程如圖1所示。

DBSCAN算法有眾多優(yōu)點，比如：算法可以聚類任意形狀的集群，能夠較好地發(fā)現(xiàn)噪聲點[15]。但是DBSCAN參數(shù)Eps不同，對聚類效果會產(chǎn)生很大影響[16]，當(dāng)Eps選擇過小時，會使得很多點被定義為噪聲點，影響數(shù)據(jù)信息;當(dāng)Eps選取過大時，會把幾個聚類簇合在一起，并且有許多噪聲點將無法很好地被識別出來[17]。針對DBSCAN中另一個參數(shù)MinPts，由于農(nóng)業(yè)數(shù)據(jù)變化較為平緩，因而通常在算法執(zhí)行過程中該值較為固定，可以依據(jù)經(jīng)驗進行判定[18]。

2 DBSCAN算法改進

針對DBSCAN中參數(shù)Eps值對結(jié)果影響較大的問題，對數(shù)據(jù)集中各點之間的距離進行計算，得出各點之間的距離值。由于噪聲點具有數(shù)量少且離散分布的特點，利用統(tǒng)計學(xué)思想，尋找一個Eps值，能夠?qū)⒋罅空７植嫉臄?shù)據(jù)和少部分離群分布的數(shù)據(jù)分割出來[19-20]，較好地提高算法異常數(shù)據(jù)尋找準(zhǔn)確率。

按照式（2）取參數(shù)p=2的歐式距離公式，計算每個點之間的距離用并用d（i，j）表示，并將所有d（i，j）構(gòu)造成一個Dist n×n矩陣，表示如式（3）所示。

Distn×n=（d（i ，j）|1≤i≤n，1

（3）

矩陣Dist n×n中，每一行表示某個點到所有其它點的距離。將Dist n×n矩陣每一行中的值按升序進行排列，排列之后矩陣第i列表示距離每個點第i近的點。每一行矩陣表示每個點到其它點的距離由小到大排列，由此可通過數(shù)值統(tǒng)計方法得出每一行數(shù)據(jù)的距離升序曲線如圖2所示，通過判斷圖中陡峭點位置，確定參數(shù)Eps最優(yōu)值范圍。其中，數(shù)據(jù)集采用之后實驗使用的含噪聲原始數(shù)據(jù)。

圖2是由7條按距離升序排列繪制的圖形，且最下面的那條曲線為距離參考點最近的距離升序圖，最上面的那條曲線為距離參考點最遠(yuǎn)的距離升序圖。由圖2可知，圖像在前中期比較均勻，趨勢也較平緩，當(dāng)圖形到達(dá)接近距離為0.35-0.45時，在圖中箭頭標(biāo)注的位置出現(xiàn)較為密集的陡峭點，因此可以預(yù)計DBSCAN的最優(yōu)Eps參數(shù)在0.35-0.45。依據(jù)經(jīng)驗MinPts的值選取6，通過觀察圖2可以發(fā)現(xiàn)從下往上第6條曲線的陡峭點接近0.4，可以將最優(yōu)的Eps設(shè)置為0.4。

其原理為：針對異常數(shù)據(jù)量少并且分散的特點，當(dāng)曲線比較平緩時，說明此時在該距離范圍內(nèi)，數(shù)據(jù)量的數(shù)量仍然較多。當(dāng)出現(xiàn)陡峭點時，之后距離范圍內(nèi)所含的數(shù)據(jù)量較少。因此，可以利用該陡峭點對應(yīng)的距離大小較好地區(qū)分出異常數(shù)據(jù)，且將極大減少正常數(shù)據(jù)誤判幾率[21]。

3 實驗驗證

3.1 實驗設(shè)計

為了驗證設(shè)置參數(shù)的有效性，選取縉云縣某處茶園空氣溫度傳感器在某一時間段采集到的140組茶園空氣溫度數(shù)據(jù)，并向其中隨機添加25組離散點，以此數(shù)據(jù)作為實驗數(shù)據(jù)。由于傳感器采集數(shù)據(jù)屬于一維數(shù)據(jù)，進行聚類時效果不好，在聚類之前首先將一維數(shù)據(jù)轉(zhuǎn)化為二維?？梢詫⑾噜彽膬蓚€值一個歸為X坐標(biāo)值，另一個歸為Y坐標(biāo)值，即將數(shù)據(jù)變?yōu)槎S。比如數(shù)據(jù)D={ d1，d2，d3，…，dn}轉(zhuǎn)化為D={ （d1，d2），（d3，d4），…，（dn-1，dn）}，140組一維數(shù)據(jù)可以轉(zhuǎn)化為70組二維數(shù)據(jù)。對數(shù)據(jù)使用DBSCAN算法進行處理，尋找核心對象及其密度可達(dá)的每個對象點作為一個類。另外一些密度不夠且不為任何核心對象點的密度可達(dá)的點，被判定為噪聲，將由距離較近聚類中所有核心對象均值替代。通過統(tǒng)計分析可知，Eps參數(shù)最優(yōu)值為0.4，再取Eps參數(shù)分別為0.35、0.38、0.4、0.45，MinPts參數(shù)為6進行實驗分析，通過識別出的異常點個數(shù)、誤判的異常點個數(shù)和去除異常數(shù)據(jù)后數(shù)據(jù)變化情況判斷異常數(shù)據(jù)處理效果。

3.2 實驗結(jié)果與分析

分別將Eps參數(shù)設(shè)定為0.45，0.4，0.38，0.35，MinPts設(shè)定為6，采用DBSCAN進行聚類，得到聚類簇，并求出各聚類簇中心點的值，將各噪聲點采用距離最近簇的中心值進行替代，得出去除噪聲數(shù)據(jù)的濾波效果圖，通過Matlab進行仿真實驗，實驗結(jié)果如圖3所示（彩圖掃描OSID碼可見，下文同）。

圖3-圖6為取不同Eps參數(shù)的聚類效果和濾波效果。其中，聚類效果圖中黑色圓圈為算法識別出的噪聲數(shù)據(jù)，其余顏色為聚類簇;濾波效果圖中粉紅色為原始實驗數(shù)據(jù)，藍(lán)色為濾波后的數(shù)據(jù)。

通過以上實驗可知，各參數(shù)識別出的噪聲點情況如表1所示。

由表1可知，當(dāng)Eps參數(shù)設(shè)為0.4時，將噪聲點全部識別出來，且與0.4較為接近的參數(shù)0.38，其準(zhǔn)確率達(dá)到98.57%，比距離0.4較遠(yuǎn)的參數(shù)0.35和0.45準(zhǔn)確率高，證明采用此方法進行參數(shù)預(yù)估效果可行。且從實驗結(jié)果中的濾波效果看，通過采用聚類簇中心值代替噪聲點數(shù)據(jù)的方式，較好地降低了數(shù)據(jù)偏離程度，從而可以減少異常數(shù)據(jù)對于結(jié)果分析的影響。

為了避免實驗的偶然性，隨機選取茶園10個時間段的140組空氣溫度數(shù)據(jù)進行測試，并向每組數(shù)據(jù)中隨機加入25個噪聲點。按照以上方法進行仿真實驗，在10次檢測中，有3個數(shù)據(jù)判斷錯誤，準(zhǔn)確率達(dá)到99.6%。按照傳統(tǒng)方法，由于不能確定哪個Eps參數(shù)較優(yōu)，通常選取之前某個Eps作為固定值，此處選取0.4作為10次固定的Eps值，在10次檢測中，有15個數(shù)據(jù)判斷錯誤，準(zhǔn)確率為97.9%?？梢钥闯?，改進算法提升了異常數(shù)據(jù)識別準(zhǔn)確率與穩(wěn)定性。

4 結(jié)語

本文為解決農(nóng)業(yè)傳感器采集數(shù)據(jù)中異常數(shù)據(jù)處理問題，采用基于密度的DNSCAB算法進行異常數(shù)據(jù)檢測與處理。針對DBSCAN算法參數(shù)敏感的特點，采用統(tǒng)計學(xué)中的圖表對數(shù)據(jù)集中各點相互距離進行統(tǒng)計分析，預(yù)估出參數(shù)Eps的值。實驗驗證表明，該方法獲取的參數(shù)識別異常數(shù)據(jù)準(zhǔn)確率較高。同時，針對直接將噪聲數(shù)據(jù)刪除導(dǎo)致信息丟失的問題，采用聚類簇中心點對噪聲數(shù)據(jù)進行替代，通過此方法可以減少離散點偏移。

目前，雖然采用該方法對數(shù)據(jù)集中各點相互距離值統(tǒng)計分析可確定參數(shù)的一個范圍，但參數(shù)值的具體取值仍需人為估計，導(dǎo)致參數(shù)并不是十分精確，需作進一步研究。

參考文獻：

[1]劉亞東.物聯(lián)網(wǎng)與智慧農(nóng)業(yè)[J].農(nóng)業(yè)工程，2012，2（1）：1-7.

[2] 張永峰.對數(shù)據(jù)采集器等受雷擊情況的分析及對策[J].電子科技，2004（7）：58-60.

[3]劉云，袁浩恒，數(shù)據(jù)挖掘中并行離散化數(shù)據(jù)準(zhǔn)備優(yōu)化[J].四川大學(xué)學(xué)報（自然科學(xué)版），2018，55（5）：103-109.

[4] 康團結(jié).多傳感器數(shù)據(jù)處理的列車環(huán)境監(jiān)測系統(tǒng)[D].成都：西南交通大學(xué)，2018.

[5]毛李帆，姚建剛，金永順，等.中長期負(fù)荷預(yù)測的異常數(shù)據(jù)辨識與缺失數(shù)據(jù)處理[J].電網(wǎng)技術(shù)，2010，34，（7）：148-153.

[6] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報，2008（1）：48-61.

[7]ESTER M. KRIECEL H P，XU X.A density-based algorithm for dis-covering clusters a density-based algorithm for discovering clusters inlarge spatial datahases with noise [Cl. International Conference onKnowledge Discovery& Data Mining， 1996.

[8]馬世欣，劉春桐，李洪才，等.基于空譜聯(lián)合聚類的改進核協(xié)同高光譜異常檢測[J].光子學(xué)報，2019，48（1）：0110003.

[9]潘淵洋，李光輝，徐勇軍.基于DBSCAN的環(huán)境傳感器網(wǎng)絡(luò)異常數(shù)據(jù)檢測方法[J].計算機應(yīng)用與軟件，2012（ 11）：69-72.

[10] 宋金玉，郭一平，王斌.DBSCAN聚類算法的參數(shù)配置方法研究[J].計算機技術(shù)與發(fā)展，2019（5）：1-8.

[11] 夏魯寧，荊繼武.SA-DBSCAN：-種自適應(yīng)基于密度聚類算法[J].中國科學(xué)院大學(xué)學(xué)報，2009，26（4）：530-538.

[12] 朱振國，馮應(yīng)柱.基于數(shù)據(jù)場的類簇中心選取及其聚類[J].計算機工程與應(yīng)用，2018.54（8）：131-136.

[13] 針對非均勻密度環(huán)境的DBSCAN自適應(yīng)聚類算法的研究[D].重慶：重慶大學(xué)，2015.

[14] 多密度聚類算法研究[D].無錫：江南大學(xué)，2018.

[15]吳偉民，黃煥坤.基于差分隱私保護的DP-DBScan聚類算法研究[J].計算機工程與科學(xué)，2015，37（4）：830-834.

[16]SHAH G H.An improved DBSCAN.a density based clustering algo-rithm with parameter selection for high dimensional data sets [C].Nirma University International Conference on Engineering， 2013.

[17]SUN X， ZHENCH，HUI LI，et aI.Bad data identification for leakagereactance parameters of transformer based on improved DBSCAN Al-gorithm [Jl. Automation of Electric Power Systems， 2017， 41（9）：96-101。

[18] 石鴻雁，馬曉娟.改進的DBSCAN聚類和LAOF兩階段混合數(shù)據(jù)離群點檢測方法[J].小型微型計算機系統(tǒng)，2018，39（1）：74-77.

[19] 侯雄文.淺析DBSCAN算法中參數(shù)設(shè)置問題的研究[J].科教導(dǎo)刊（電子版），2017（ 30）：266-266.

[20]王兆豐，單甘霖，一種基于k-均值的DBSCAN算法參數(shù)動態(tài)選擇方法[J].計算機工程與應(yīng)用，2017，53（3）：80-86.

[21] 曹科研.不確定數(shù)據(jù)的聚類分析與異常點檢測算法[D].沈陽：東北大學(xué)，2014.

（責(zé)任編輯：孫娟）

作者簡介：黃靜（1965-），女，博士，浙江理工大學(xué)信息學(xué)院教授、碩士生導(dǎo)師，研究方向為嵌入式系統(tǒng)、專用測試設(shè)備、電子功能材料計算設(shè)計及獨立分析軟件設(shè)計;官易楠（1993-），男，浙江理工大學(xué)信息學(xué)院碩士研究生，研究方向為農(nóng)業(yè)數(shù)據(jù)挖掘與計算機應(yīng)用，本文通訊作者：黃靜。