基于空間自相關性和模糊集的空間數據噪聲點檢測算法

朱付保　徐顯景　白慶春　朱顥東

(鄭州輕工業學院計算機與通信工程學院　河南 鄭州 450002)

?

基于空間自相關性和模糊集的空間數據噪聲點檢測算法

朱付保徐顯景白慶春朱顥東*

(鄭州輕工業學院計算機與通信工程學院河南 鄭州 450002)

大數據時代數據紛繁復雜，同時在數據挖掘過程中數據質量又至關重要，數據質量的高低將直接影響數據挖掘結果的好壞，但現實中數據缺失和噪聲數據的現象在所難免。針對上述問題，通過引入空間對象的自相關性理論和模糊集理論，提出一種基于空間自相關性和模糊集的空間數據噪聲點檢測算法。該算法首先運用鄰域對象的空間自相關性理論，計算出特定對象與鄰域內其他對象的距離，進而將距離以模糊隸屬度的概念予以表達，最后通過與該屬性的置信水平進行比較，以此來判定噪聲數據。理論分析和實驗對比結果均表明，該算法對于處理空間數據噪聲點問題是有效可行的。

噪聲數據數據預處理空間自相關性模糊集

0　引　言

隨著空間數據在社會、生活等各方面應用的深入，從空間數據庫中自動或半自動地挖掘隱藏的關系模式，進而根據現有關系模式預測空間對象未來可能發生的行為已變得更具價值。伴隨著大數據時代的到來，如何從大數據中提煉出大價值已成為數據挖掘領域研究的重點[1]。與此同時，數據的質量也變得尤為重要，數據預處理則是數據挖掘過程中一個重要步驟和數據質量提升的關鍵手段[2]。空間數據挖掘相較于傳統的數據挖掘具有更為復雜的數據特點，空間數據都不是孤零零的存在，一種事物總是與其他事物相關聯，而且距離相近的事物其相關性要大于距離較遠的事物，因此在特定的應用領域要更加注重空間數據對象間的自相關性問題。在大數據時代，數據類型更加多樣，規模更為龐大，數據間的關聯也更為復雜。在數據挖掘過程中，如果缺失數據處理不當，那么與之相關的有價值的知識也常常會被忽略[3]。大而低質量的數據有時不僅不能支撐有效的數據挖掘，反而還會給數據挖掘的結果造成不同程度的干擾，簡單地認為數據越多越好而不關心數據的質量會使得挖掘的結果變得難以預料[4]。

但是在現實世界中，由于人為的或自然的因素造成的數據缺失或噪聲數據在所難免，噪聲數據或缺失數據不可避免地會對空間數據挖掘的結果產生影響。在這方面許多人都曾做過比較深入的研究，文獻[5]對傳統的數據質量評估方法和數據質量提高技術做了分析比較，文獻[6]則著重分析了領域無關的數據清洗的特點，并對相關方法進行了分類介紹。異常數據檢測主要可以分為四類：基于分布、基于聚類、基于距離和基于密度的方法[7]。文獻[8]提出了基于空間局部偏離因子的離群點檢測算法，該算法運用空間局部偏離因子來衡量離群點問題，但對于給定對象鄰域范圍的定義采用的是對象的非空間屬性帶權距離小于特定值k的所有空間鄰居的集合，沒能充分利用空間對象在空間位置上的自相關性特點，而且在數據量大的情況下會造成很大的計算壓力。

為了有效控制數據質量，提高檢測的準確率和效率，本文通過研究空間數據的自相關性理論和模糊集理論在解決模糊問題方面的優勢，提出基于空間自相關性和模糊集的空間數據噪聲點檢測算法。該算法對空間數據離群點的度量方式進行了進一步的改進，以空間對象的空間位置作為對象鄰域劃定的標準，進而將該對象對于領域內其他對象的隸屬度和置信水平進行比較判定該對象的可靠性。

1　空間數據消噪模型

模糊集理論認為元素總是以一定的程度隸屬于某一集合，也可能是以不同的程度隸屬于多個集合，而非經典數學中的二元性，使得元素的隸屬度概念具有一種亦此亦彼的模糊性[9,10]。空間自相關描述的是一些變量在同一個分布區內的觀測數據之間潛在的相互依賴性關系。地理學第一定律指出任何事物與其他事物之間都是相關聯的，同時距離較近的事物比距離較遠的事物的關聯性更強[11,12]。對于空間數據庫而言，因為包含大量的空間信息，因此各數據元素之間的相關度比一般的業務型數據庫中數據的相關度更大，相互聯系更為緊密。本文據此提出了基于空間自相關性和模糊集理論的空間數據消噪模型。首先，計算指定對象與其鄰域內其他對象的平均距離；其次，在相似性概念的基礎上引入模糊集理論，在特定對象與鄰域內其他對象平均距離的基礎上定義其與領域內其他對象相似度的隸屬度函數；再次，根據計算所得的隸屬度與置信水平進行比較，在置信水平之內認定為可靠性數據，置信水平之外則認為是非可靠性數據；最后，依據對數據屬性的可靠性判斷，對非可靠性數據進行消噪處理。

在數據消噪處理過程中最重要而且最核心的問題是對數據噪聲點的檢測，所謂數據噪聲點指的是在數據集中與整體數據集或局部數據集有顯著異常或表現不一致的數據觀測點[13]，本文基于空間自相關性和模糊集理論來進行噪聲點數據的判定。

空間對象的屬性數據與鄰域內相應屬性數據的距離，可以有效地表達數據對于鄰域數據的融入度。屬性空間中對象與鄰域空間內其他對象的距離越小，說明越相似，進而表明對象的數據可靠性越高；距離越大，表明對象與鄰域空間內其他對象的差異越大，進而說明該數據的可靠性越低，出現錯誤的可能性就越大。設包含N個空間對象{O1,O2,…,ON}的空間數據集O，每個空間對象Oi具有M個可度量特征屬性Oi={Oi1,Oi2,…,OiM}，對象Oi的第k個特征屬性與其鄰域內對象Oj的第k個特征屬性的平均距離定義為：

(1)

(2)

(3)

2　基于自相關性和模糊集的空間數據消噪算法

2.1算法描述

通過對空間消噪模型的定義說明，基于空間自相關性和模糊集理論的空間數據消噪算法描述如下：

1) 初始化空間對象集合O，針對空間對象的M個可度量特征屬性，分別為每個屬性設置對應的鄰域半徑r、可靠性系數C和置信水平λ，以3*M的二維數組Arr形式存儲；

2) 將空間對象集合O中的所有對象投影到二維平面上；

3)FORi=1ToO.Length；

4)FORk=1ToM；

5) 令r=Arr[0][k-1]，C=Arr[1][k-1]，λ=Arr[2][k-1]；

9)ELSE;

10)Continue;

11)ENDFOR;

12)ENDFOR;

2.2參數控制說明

3　實驗結果與分析

根據上文介紹的算法思想，本文以某機場及其附近地區2003年至2009年各監測點利用永久散射體點(PS)監測到的地面沉降量數據為例進行實驗。實驗的軟件環境是：MicrosoftWindows7操作系統；MicrosoftSQLServer2008數據庫；Microsoft.NETFramework4.0；算法的實現語言為C#。

實驗選取數據集中的經度、緯度和年均沉降量3個屬性進行，數據量為39 195條，在此數據集中隨機加入240條噪聲數據組成新的數據集，實驗中以數據噪聲點檢測率和噪聲點檢測的錯檢率來度量算法的準確性。實驗結果如表1所示。

表1　噪聲數據檢測結果

從表1中的實驗結果可以看出，本文提出的算法相對于整個數據集而言具有檢測率高、錯檢率低的特點。同時，可靠性系數C和置信水平λ對數據噪聲點檢測的結果影響比較明顯，在同一數據集的基礎上，可靠性系數和置信水平的改變會相應地改變所檢測到的噪聲點數據的數量，因此運用該算法進行空間數據消噪處理時，需要根據數據的特性選擇合適的可靠性系數和置信水平。

為了進一步驗證本文所提出算法的有效性，本文算法與LOF算法、SLDF算法分別從正檢率、錯檢率和算法執行時間三個方面進行了對比，對比結果如表2所示。實驗結果表明，在相同情況下，本文所提算法在檢測率和算法執行時間方面都要優于LOF算法和SLDF算法，并且適用于數據集規模較大的空間數據檢測。

表2　實驗結果對比

4　結　語

針對空間數據具有自相關性的特點和模糊集在解決模糊問題方面的優勢，本文提出了一種基于空間自相關性和模糊集理論的空間數據噪聲點檢測算法。該算法主要利用空間數據的自相關性，對數據對象的離群度度量方式進行了進一步改進，將對于某一點數據對象的判定借助于其鄰域內其他的數據對象來進行，進而通過可靠性系數得出該點相對于鄰域對象的隸屬度關系，通過隸屬度與置信度水平來檢測空間數據庫中可能存在的噪聲點數據。將該算法在實驗數據集上進行相關實驗，并與文獻[14]的LOF算法和文獻[8]的SLDF算法分別進行比較。理論分析與實驗結果表明，本文算法在檢測較大規模空間數據集的噪聲點問題時，具有較高的效率和準確率。

[1] 王樹良,丁剛毅,鐘鳴.大數據下的空間數據挖掘思考[J].中國電子科學研究院學報,2013,8(1):8-17.

[2] 汪偉,鄒璇,詹雪.論數據挖掘中的數據預處理技術[J].煤炭技術,2013,32(5):152-153.

[3] 武森,馮小東,單志廣.基于不完備數據聚類的缺失數據填補方法[J].計算機學報,2012,35(8):1727-1737.

[4] 靳小龍,王元卓,程學旗.大數據的研究體系與現狀[J].信息通信技術,2013,7(6):35-42.

[5] 韓京宇,徐立臻,董逸生.數據質量研究綜述[J].計算機科學,2008,35(2):1-5.

[6] 曹建軍,刁興春,汪挺,等.領域無關數據清洗研究綜述[J].計算機科學,2010,37(5):26-29.

[7] 薛安榮,姚林.離群點挖掘方法綜述[J].計算機科學,2008,35(11):13-18.

[8] 張天佑,王小玲.基于空間局部偏離因子的離群點檢測算法[J].計算機工程,2011,37(14):282-284.

[9]PrzemysawGrzegorzewski.Onpossibleandnecessaryinclusionofintuitionisticfuzzysets[J].InformationSciences,2011,181(2):342-350.

[10] 趙立權.模糊集、粗糙集和商空間理論的比較研究[J].計算機工程,2011,37(2):22-24.

[11]DanielaStojanova,MichelangeloCeci,AnnalisaAppice,etal.Dealingwithspatialautocorrelationwhenlearningpredictiveclusteringtrees[J].EcologicalInformatics,2013,13(1):22-39.

[12]XiQu,LungfeiLee.LMtestsforspatialcorrelationinspatialmodelswithlimiteddependentvariables[J].RegionalScienceandUrbanEconomics,2012,42(3):430-445.

[13] 王偉一,郝文寧,趙水寧,等.基于相對密度的軍事高維數據噪聲點檢測方法[J].計算機工程,2009,35(5):50-52.

[14]BreunigMM,KriegelHP,NgRT,etal.LOF:IdentifyingDensity-basedLocalOutliers[C]//Proc.ofACMSIGMODConference.NewYork,USA:ACMPress,2000:427-438.

SPATIALDATANOISEDETECTIONALGORITHMBASEDONSPATIALAUTO-CORRELATIONANDFUZZYSET

ZhuFubaoXuXianjingBaiQingchunZhuHaodong*

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,Henan,China)

Datashowsmorecomplexcharacteristicsintheeraofbigdata.Meanwhile,thequalityofdataiscrucialintheprocessofdataminingandwilldirectlyaffecttheresultsofdatamining,butthephenomenaofdatamissingandnoisedataareinevitableinreality.Aimingattheaboveproblems,byintroducingthetheoryofspatialauto-correlationofspatialobjectandthetheoryoffuzzysetweproposeaspatialdatanoisepointdetectionalgorithm.First,thealgorithmcalculatesthedistancebetweenthespecificobjectandotherobjectswithinitsneighbourhoodbyusingspatialauto-correlationtheoryofneighbourhoodobject.Thenitexpressesthedistancebytheconceptoffuzzymembershipdegree.Finally,itdetermineswhetherthereisanoisedatabycomparingwiththeconfidenceleveloftheattribute.Theoreticalanalysisandexperimentalcomparisonresultsallshowthatthismethodiseffectiveandfeasibleinhandlingtheproblemofspatialdatanoisepoint.

NoisedataDataprepossessingSpatialauto-correlationFuzzyset

2014-08-09。國家自然科學基金項目(61201447)；河南省科技攻關項目(122102210492)；河南省教育廳科學技術研究重點項目(13A520368，13A520367)。朱付保，副教授，主研領域：智能信息處理，空間數據庫。徐顯景，碩士生。白慶春，碩士生。朱顥東，副教授。

TP315

ADOI:10.3969/j.issn.1000-386x.2016.03.062