基于非參數估計與隨機模擬的不確定數據流相似性度量方法

遲榮華,黃少濱,李熔盛

哈爾濱工程大學 計算機科學與技術學院,黑龍江 哈爾濱 150001

基于非參數估計與隨機模擬的不確定數據流相似性度量方法

遲榮華,黃少濱,李熔盛

哈爾濱工程大學 計算機科學與技術學院,黑龍江 哈爾濱 150001

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

不確定數據流;非參數估計;隨機模擬;相似性

隨著信息收集、存儲等技術與手段的不斷發展，信息的規模以及屬性都變的極為龐大，這不僅使信息科學的研究工作變得更加困難、復雜，也同時帶來了更多方面的挑戰和樂趣。例如，傳感器網絡、物聯網、RFID網絡、對象識別以及移動對象搜索等[1-5]。

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

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

1 基于非參數估計的不確定數據流對象建模以及距離度量

1.1 不確定數據流對象建模

非參數估計方法是在不假設數據分布的前提下，基于樣本點數據對不確定對象構建概率密度函數的較合適的方法。其中核密度估計是一種基于樣本數據特征，用于估計未知密度函數的非參數統計方法，不需要預先假設變量間的函數關系，其估計形式如式（1）所示。

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

1.2 相似性度量

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

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

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

根據公式可知，當兩個不確定對象的取值區域完全不同時，相對誤差和絕對誤差分別為1和2，而當取值區域完全相同時，相對誤差為0，絕對誤差可取[0,2]的任何值。因此，可以想象即使兩個對象在取值空間完全相同時，仍可能由于分布形式的不同而產生很高的誤差。

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

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

2 仿真實驗分析

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

首先，為了分析在不確定對象屬于相同區域而分布密度不同時的現象，本文模擬了屬于兩個不同分布類型的不確定對象分屬于不同級別的樣本數量時，相對誤差與絕對誤差的變化情況。如圖2可知，當兩個對象在相同區域內的概率密度幾乎完全相同時，由于分布類型的不同，絕對誤差較高仍可導致兩個對象具有較大的差別。然后，通過不同的迭代次數，觀察分析三組分布時誤差的距離誤差的變化情況如圖2。

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

通過仿真實驗可知均勻分布的誤差最高，指數分布的誤差次之，正態分布的誤差最小，考慮原因可能與核函數的假設有關，但當迭代次數趨近40000次時，誤差率普遍可以控制在0.5%以下，實驗效果明顯，而且當進行多組實驗時，結果依然穩定。

3 總結

本文面向數據屬性存在的不確定性，針對不確定對象建模以及不確定對象間相似性度量中面臨的主要問題，提出基于非參估計及隨機模擬相結合的相似性計算方法。本方法利用非參數估計對不確定對象建模，可以有效描述因為屬性以及存在所導致的不確定性問題，同時又采用隨機模擬方法解決了非參數估計函數復雜難于計算相似性的問題。最后，本文通過仿真實驗的方式對所提方法進行了驗證，實驗結果表明本方法不僅能夠有效地對建模，同時又能在有限次計算數量下較高精度地計算不確定對象間的相似度，理論和實驗都驗證了本文所提方法的有效性與準確性。

[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-),男,博士研究生.主要研究方向為不確定數據分析及人工智能.E-mail:chironghua@hrbeu.edu.cn