基于空間自相關(guān)性和模糊集的空間數(shù)據(jù)噪聲點檢測算法

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

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

?

基于空間自相關(guān)性和模糊集的空間數(shù)據(jù)噪聲點檢測算法

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

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

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

噪聲數(shù)據(jù)數(shù)據(jù)預(yù)處理空間自相關(guān)性模糊集

0　引　言

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

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

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

1　空間數(shù)據(jù)消噪模型

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

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

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

(1)

(2)

(3)

2　基于自相關(guān)性和模糊集的空間數(shù)據(jù)消噪算法

2.1算法描述

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

1) 初始化空間對象集合O，針對空間對象的M個可度量特征屬性，分別為每個屬性設(shè)置對應(yīng)的鄰域半徑r、可靠性系數(shù)C和置信水平λ，以3*M的二維數(shù)組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參數(shù)控制說明

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

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

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

表1　噪聲數(shù)據(jù)檢測結(jié)果

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

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

表2　實驗結(jié)果對比

4　結(jié)　語

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

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

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

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

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

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

[6] 曹建軍,刁興春,汪挺,等.領(lǐng)域無關(guān)數(shù)據(jù)清洗研究綜述[J].計算機科學(xué),2010,37(5):26-29.

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

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

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

[10] 趙立權(quán).模糊集、粗糙集和商空間理論的比較研究[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] 王偉一,郝文寧,趙水寧,等.基于相對密度的軍事高維數(shù)據(jù)噪聲點檢測方法[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。國家自然科學(xué)基金項目(61201447)；河南省科技攻關(guān)項目(122102210492)；河南省教育廳科學(xué)技術(shù)研究重點項目(13A520368，13A520367)。朱付保，副教授，主研領(lǐng)域：智能信息處理，空間數(shù)據(jù)庫。徐顯景，碩士生。白慶春，碩士生。朱顥東，副教授。

TP315

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