基于非參數(shù)估計(jì)與隨機(jī)模擬的不確定數(shù)據(jù)流相似性度量方法

遲榮華,黃少濱,李熔盛

哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001

基于非參數(shù)估計(jì)與隨機(jī)模擬的不確定數(shù)據(jù)流相似性度量方法

遲榮華,黃少濱,李熔盛

哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001

針對(duì)不確定數(shù)據(jù)流對(duì)象難于度量相似性的問題，本文提出一種非參數(shù)估計(jì)與隨機(jī)模擬相結(jié)合的方法。本方法利用非參數(shù)估計(jì)對(duì)不確定數(shù)據(jù)流對(duì)象建模，然后利用隨機(jī)模擬計(jì)算對(duì)象間的誤差相似性，通過相對(duì)距離與絕對(duì)距離判斷相似度。仿真實(shí)驗(yàn)驗(yàn)證了本方法不僅可以準(zhǔn)確地度量不確定對(duì)象間的相似性，而且在對(duì)象規(guī)模較大的情況下，依然可以獲得較快速和穩(wěn)定的計(jì)算結(jié)果。

不確定數(shù)據(jù)流;非參數(shù)估計(jì);隨機(jī)模擬;相似性

隨著信息收集、存儲(chǔ)等技術(shù)與手段的不斷發(fā)展，信息的規(guī)模以及屬性都變的極為龐大，這不僅使信息科學(xué)的研究工作變得更加困難、復(fù)雜，也同時(shí)帶來了更多方面的挑戰(zhàn)和樂趣。例如，傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)、RFID網(wǎng)絡(luò)、對(duì)象識(shí)別以及移動(dòng)對(duì)象搜索等[1-5]。

為了對(duì)不確定性數(shù)據(jù)進(jìn)行有效管理與分析，相關(guān)研究大多先對(duì)不確定性數(shù)據(jù)構(gòu)建模型以保留數(shù)據(jù)原始的自身特性。常見的數(shù)據(jù)模型如可能世界模型[6]，用于對(duì)數(shù)據(jù)存在的不確定性建模；以及概率密度函數(shù)，用于描述數(shù)據(jù)中屬性值的不確定性[7]。基于這些不確定性數(shù)據(jù)模型，進(jìn)一步對(duì)不確定性數(shù)據(jù)進(jìn)行管理分析，如不確定性數(shù)據(jù)的存儲(chǔ)與查詢，以及挖掘不確定性數(shù)據(jù)中蘊(yùn)涵知識(shí)的數(shù)據(jù)挖掘算法等[8-11]。目前，不確定對(duì)象建模方法的理論基礎(chǔ)一般是基于不確定對(duì)象的數(shù)據(jù)服從某種理論分布[12,13]，典型的密度分布函數(shù)代表了不確定對(duì)象的主要特征，這類方法雖然沒有忽略對(duì)象的不確定性，但不確定信息卻沒有得到很好的保留，而且這種簡(jiǎn)單的數(shù)據(jù)分布假設(shè)，相對(duì)實(shí)際的數(shù)據(jù)來說都有較大的偏差，導(dǎo)致理論模型與實(shí)際模型的誤差較大。

針對(duì)上述對(duì)于不確定對(duì)象建模與相似性度量存在的問題，本文提出了一種基于非參數(shù)估計(jì)與隨機(jī)模擬相結(jié)合的方法。該方法首先采用非參數(shù)的概率密度估計(jì)方法對(duì)不確定數(shù)據(jù)流對(duì)象進(jìn)行建模，然后利用蒙特卡洛隨機(jī)模擬方法對(duì)概率密度函數(shù)的相對(duì)距離與絕對(duì)距離進(jìn)行計(jì)算，通過兩個(gè)指標(biāo)的分析確定不確定對(duì)象的相似性。文本在第二節(jié)論述了基于非參數(shù)估計(jì)的不確定數(shù)據(jù)流對(duì)象模型的建模以及相似性度量方法，并從理論上給出了方法的有效性證明，然后在第三節(jié)通過仿真實(shí)驗(yàn)的方法驗(yàn)證了本方法的有效性與可靠性。

1 基于非參數(shù)估計(jì)的不確定數(shù)據(jù)流對(duì)象建模以及距離度量

1.1 不確定數(shù)據(jù)流對(duì)象建模

非參數(shù)估計(jì)方法是在不假設(shè)數(shù)據(jù)分布的前提下，基于樣本點(diǎn)數(shù)據(jù)對(duì)不確定對(duì)象構(gòu)建概率密度函數(shù)的較合適的方法。其中核密度估計(jì)是一種基于樣本數(shù)據(jù)特征，用于估計(jì)未知密度函數(shù)的非參數(shù)統(tǒng)計(jì)方法，不需要預(yù)先假設(shè)變量間的函數(shù)關(guān)系，其估計(jì)形式如式（1）所示。

其中K為一個(gè)核函數(shù)，常見的形式如高斯核函數(shù)、三角核函數(shù)、均勻核函數(shù)等。核密度估計(jì)方法求得的概率密度函數(shù)能夠在樣本點(diǎn)與目標(biāo)數(shù)據(jù)量足夠大時(shí)，收斂到任意一種密度函數(shù)，因此在數(shù)據(jù)分布未知的情況下，為了獲取每個(gè)不確定對(duì)象的分布特征，本文利用非參數(shù)估計(jì)方法獲取不確定性對(duì)象的是分布特征。

1.2 相似性度量

現(xiàn)假設(shè)兩個(gè)不確定數(shù)據(jù)流對(duì)象X,Y，其中代表不確定數(shù)據(jù)流對(duì)象是所有由于不確定性產(chǎn)生或觀測(cè)到的分量集合，大小為因此當(dāng)存在不確定性現(xiàn)象時(shí)即數(shù)據(jù)流元素的取值不唯一。在計(jì)算不確定數(shù)據(jù)流的一般方法中，假設(shè)不確定數(shù)據(jù)流的距離定義為一般采用歐式距離的計(jì)算方法，那么滿足某特定距離閾值的概率為：

本文借鑒了這種方法的概率解釋的思想，并結(jié)合非參數(shù)估計(jì)的方法，將不確定的相似性問題轉(zhuǎn)化為概率密度的相似性問題。當(dāng)概率密度的取值區(qū)域不同，但密度中心相似時(shí)，也能有較好的匹配結(jié)果。假設(shè)有兩個(gè)不確定數(shù)據(jù)流對(duì)象可根據(jù)樣本獲得各自的概率密度函數(shù)因此任意兩個(gè)不確定數(shù)據(jù)流中的元素的相似性問題可表示為：

通過公式可以看出，相似性的計(jì)算包含三個(gè)主要因素，取值空間、相對(duì)誤差以及絕對(duì)誤差代表了取值空間，當(dāng)交集為Φ時(shí)表示沒有相似性，表示的相對(duì)誤差，當(dāng)取值空間完全相同時(shí)，相對(duì)誤差近似為 0。表示絕對(duì)誤差，描述了分布密度幾何結(jié)構(gòu)上的不同，兩種誤差可以互相彌補(bǔ)不足。取值空間決定了在允許精度下的取值空間，很大程度上決定計(jì)算的規(guī)模和效率。因此首先確定取值空間的計(jì)算方法。針對(duì)一個(gè)不確定數(shù)據(jù)流中的元素，假設(shè)取值空間誤差?，因此有：

根據(jù)公式可知，當(dāng)兩個(gè)不確定對(duì)象的取值區(qū)域完全不同時(shí)，相對(duì)誤差和絕對(duì)誤差分別為1和2，而當(dāng)取值區(qū)域完全相同時(shí)，相對(duì)誤差為0，絕對(duì)誤差可取[0,2]的任何值。因此，可以想象即使兩個(gè)對(duì)象在取值空間完全相同時(shí)，仍可能由于分布形式的不同而產(chǎn)生很高的誤差。

圖1 不同樣本規(guī)模下的相對(duì)誤差（a）與絕對(duì)誤差（b）比較Fig.1 Comparison between relative error(a)and absolute error(b)at different sample size

為了分析不確定對(duì)象的概率密度的相對(duì)誤差與絕對(duì)誤差，本文模擬了兩個(gè)相同取值空間，但分布特征完全隨機(jī)的，并且不同樣本數(shù)的不確定對(duì)象的相對(duì)誤差與絕對(duì)誤差變化，從圖1可以看出，在隨機(jī)模擬的方法下，相對(duì)誤差基本穩(wěn)定在99%的概率密度上，但絕對(duì)誤差可體現(xiàn)出不同程度的變化?，F(xiàn)在可以知道，不確定對(duì)象可以通過概率密度的相對(duì)誤差與絕對(duì)誤差進(jìn)行準(zhǔn)確描述，但如何進(jìn)行這種計(jì)算同樣是一個(gè)復(fù)雜的問題。

2 仿真實(shí)驗(yàn)分析

為了從實(shí)際應(yīng)用的角度驗(yàn)證本文所提算法的可靠性，本文采用仿真的方法進(jìn)行實(shí)驗(yàn)。首先，本文分別生成三組仿真數(shù)據(jù)，對(duì)應(yīng)分布分別為正態(tài)分布、均勻分布和指數(shù)分布，每組50個(gè)數(shù)值，數(shù)值的取值空間為[0,1]，正態(tài)分布的均值為0方差為1，指數(shù)分布的均值為0.5。根據(jù)算法流程，分別對(duì)三組不確定對(duì)象進(jìn)行建模。然而，核概率密度函數(shù)的帶寬選擇是非參數(shù)估計(jì)方法的一個(gè)核心問題，帶寬選擇的合適與否決定了構(gòu)造密度函數(shù)的精度。本文選擇當(dāng)前較為普遍采用的基于均方誤差的計(jì)算方法，假設(shè)不確定對(duì)象的真實(shí)概率密度函數(shù)與估計(jì)的概率密度函數(shù)間的均方誤差：

首先，為了分析在不確定對(duì)象屬于相同區(qū)域而分布密度不同時(shí)的現(xiàn)象，本文模擬了屬于兩個(gè)不同分布類型的不確定對(duì)象分屬于不同級(jí)別的樣本數(shù)量時(shí)，相對(duì)誤差與絕對(duì)誤差的變化情況。如圖2可知，當(dāng)兩個(gè)對(duì)象在相同區(qū)域內(nèi)的概率密度幾乎完全相同時(shí)，由于分布類型的不同，絕對(duì)誤差較高仍可導(dǎo)致兩個(gè)對(duì)象具有較大的差別。然后，通過不同的迭代次數(shù)，觀察分析三組分布時(shí)誤差的距離誤差的變化情況如圖2。

圖2 三種典型分布下的模擬效果示意圖Fig.2 Simulation performances of three typical distributions

通過仿真實(shí)驗(yàn)可知均勻分布的誤差最高，指數(shù)分布的誤差次之，正態(tài)分布的誤差最小，考慮原因可能與核函數(shù)的假設(shè)有關(guān)，但當(dāng)?shù)螖?shù)趨近40000次時(shí)，誤差率普遍可以控制在0.5%以下，實(shí)驗(yàn)效果明顯，而且當(dāng)進(jìn)行多組實(shí)驗(yàn)時(shí)，結(jié)果依然穩(wěn)定。

3 總結(jié)

本文面向數(shù)據(jù)屬性存在的不確定性，針對(duì)不確定對(duì)象建模以及不確定對(duì)象間相似性度量中面臨的主要問題，提出基于非參估計(jì)及隨機(jī)模擬相結(jié)合的相似性計(jì)算方法。本方法利用非參數(shù)估計(jì)對(duì)不確定對(duì)象建模，可以有效描述因?yàn)閷傩砸约按嬖谒鶎?dǎo)致的不確定性問題，同時(shí)又采用隨機(jī)模擬方法解決了非參數(shù)估計(jì)函數(shù)復(fù)雜難于計(jì)算相似性的問題。最后，本文通過仿真實(shí)驗(yàn)的方式對(duì)所提方法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明本方法不僅能夠有效地對(duì)建模，同時(shí)又能在有限次計(jì)算數(shù)量下較高精度地計(jì)算不確定對(duì)象間的相似度，理論和實(shí)驗(yàn)都驗(yàn)證了本文所提方法的有效性與準(zhǔn)確性。

[1]Yang Z,Liu Y.Quality of trilateration:Confidence-based iterative localization[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(5):631-640

[2]Mokbel MF,Chow CY,Aref WG.The new casper:Query processing for location services without compromising privacy[J].Proceedings of the 32nd international conference on very large data bases,2006,34(4):763-774

[3]Jeffery SR,Franklin MJ,Garofalakis M.An adaptive RFID middle ware for supporting metaphysical data independence[J].The International Journal on Very Large Data Bases,2008,17(2):265-289

[4]Bohm C,Pryakhin A,Schubert M.The gauss-tree:Efficient object identification in databases of probabilistic feature vectors[C].Proceedings of the 22nd International Conference on IEEE,2006:9

[5]Chen L,?zsu MT,Oria V.Robust and fast similarity search for moving object trajectories[C].USA:Proceedings of the 2005ACM SIGMOD international conference on Management of data,ACM,2005:491-502

[6]Muzammal M,Raman R.Mining sequential patterns from probabilistic databases[C].Springer Heidelberg Berlin:Pacific-Asia Conference on Knowledge Discovery and Data Mining,2011:210-221

[7]Soliman MA,Ilyas IF,Chang KCC.Top-k query processing in uncertain databases[C].IEEE 23rd International Conference on Data Engineering,2007:896-905

[8]Barbará D,Garcia-Molina H,Porter D.The management of probabilistic data[J].IEEE Transactions on knowledge and data engineering,1992,4(5):487-502

[9]Antova L,Jansen T,Koch C,et al.Fast and simple relational processing of uncertain data[C].IEEE 24th International Conference on Data Engineering,2008:983-992.

[10]Tang R,Cheng R,Wu H,et al.A framework for conditioning uncertain relational data[C].Springer Heidelberg Berlin:International Conference on Database and Expert SystemsApplications,2012:71-87

[11]Taskar B,Segal E,Koller D.Probabilistic classification and clustering in relational data[C].Lawrence Erlbaum Associates Ltd.:International Joint Conference onArtificial Intelligence,2001,17(1):870-878

[12]Kriegel HP,Kunath P,Pfeifle M,et al.Probabilistic similarity join on uncertain data[C].Springer Heidelberg Berlin:International Conference on Database Systems for AdvancedApplications,2006:295-309

[13]Agarwal PK,Aronov B,Har-Peled S,et al.Nearest-neighbor searching under uncertaintyⅡ[J].Symposium on Principles of Database Systems,2013,13(1):115-126

An Uncertain Data Stream Similarity Measurement Method Based on Nonparametric Estimation and Stochastic Simulation

CHI Rong-hua,HUANG Shao-bin,LI Rong-sheng
College of Computer Science and Technology/Harbin Engineering University,Harbin150001,China

.To solve the problem that the current uncertain data stream is difficult to measure the similarity,this paper proposes a method combining non-parametric estimation with stochastic simulation.The method used the non-parametric estimation to model the uncertain data stream objects,and then used stochastic simulation to calculate the error similarity between objects,judged the similarity by relative distance and absolute distance.Simulation experiment verified this method can not only measure the similarity between the uncertain objects accurately,but also can obtain fast and stable results when the object scale is large.

Uncertain data stream;non-parametric estimation;stochastic simulation;similarity

TP274+.2

A

1000-2324(2017)04-0521-04

2015-01-05

2015-03-06

遲榮華(1981-),男,博士研究生.主要研究方向?yàn)椴淮_定數(shù)據(jù)分析及人工智能.E-mail:chironghua@hrbeu.edu.cn