# An Incremental Kernel Density Estimator for Data Stream Computation

Authors: Yulin He; Jie Jiang; Dexin Dai; Klohoun Fabrice
Journal: Complexity
 (2020)

---

## Abstract

Probability density function (p.d.f.) estimation plays a very important role in the field of data mining. Kernel density estimator (KDE) is the mostly used technology to estimate the unknown p.d.f. for the given dataset. The existing KDEs are usually inefficient when handling the p.d.f. estimation problem for stream data because a bran-new KDE has to be retrained based on the combination of current data and newly coming data. This process increases the training time and wastes the computation resource. This article proposes an incremental kernel density estimator (I-KDE) which deals with the p.d.f. estimation problem in the way of data stream computation. The I-KDE updates the current KDE dynamically and gradually with the newly coming data rather than retraining the bran-new KDE with the combination of current data and newly coming data. The theoretical analysis proves the convergence of the I-KDE only if the estimated p.d.f. of newly coming data is convergent to its true p.d.f. In order to guarantee the convergence of the I-KDE, a new multivariate fixed-point iteration algorithm based on the unbiased cross validation (UCV) method is developed to determine the optimal bandwidth of the KDE. The experimental results on 10 univariate and 4 multivariate probability distributions demonstrate the feasibility and effectiveness of the I-KDE.


---

## Body

## 1. Introduction

Probability density function (p.d.f.) estimation [1] uses a nonparametric way to determine the p.d.f. of a random variable (r.v.) based on the given dataset. It plays a very important role in the fields of data mining because many machine learning tasks are related to the p.d.f. estimation, for example, Bayesian classification [2], density-based clustering [3], feature selection [4], time series analysis [5], and image processing [6]. The mostly used p.d.f. estimator is the Parzen window estimator [7] which is also termed kernel density estimator (KDE). The KDE uses the superposition of multiple kernels (e.g., triangular kernel, Epanechnikov kernel, biweight kernel, triweight kernel, cosine kernel, and Gaussian kernel) to fit the unknown p.d.f. of given dataset. How to select an appropriate window bandwidth or kernel size is the core of training an effective KDE: the large bandwidth will lead to the oversmoothed estimation, while the small bandwidth will result in the undersmoothed estimation. Until now, the studies regarding how to construct the KDEs mainly focus on the selection of optimal bandwidths.In order to select the optimal bandwidth, an effective error criterion should be deliberately designed [8]. The mean integrated square error (MISE) is a typical error criterion which measures the expected value of estimated error between the estimated p.d.f. and true p.d.f. Because the error criterion includes an unknown term, i.e., the true p.d.f., the bandwidth selection methods have to use the different approximation strategies to replace it and then determine the optimal bandwidths for the specific applications. There are many bandwidth selection methods which have been developed based on MISE criterion. The representative works are summarized as follows. The rule of thumb (RoT) [9] is the simplest method to determine a quick normal scale bandwidth by assuming the data obeying a normal distribution. However, when the data are not close to normal, RoT tends to oversmooth and masks the important features of data [8]. The bootstrap method [10] used the p.d.f. estimated with the resampled data to replace the true p.d.f. and then minimize the bootstrap criterion function to determine the bandwidth for p.d.f. estimation. The unbiased cross validation (UCV) method [11] which is also termed least squares cross validation (LSCV) used the leave-one-out strategy to estimate the true p.d.f. of error criterion. The expected value of UCV is equal to the difference between the expected value of integrated square error (ISE) and a constant related to the true p.d.f. The biased cross validation (BCV) method [12] derived a smoothed objective function to optimize the bandwidth based on an asymptotic MISE. The theoretical analysis showed that BCV had a good convergence rate of optimal bandwidth. A solve-the-equation approach [13] for univariate p.d.f. estimation was studied based on the plug-in strategy to approximate the true p.d.f. in the asymptotic MISE. Correspondingly, an iterative algorithm was designed to find the optimal bandwidth. The experimental results demonstrate that the aforementioned MISE-based KDEs and their variants [14–16] can obtain the good performances when handling the p.d.f. estimation problems in a stationary way.As far as we know, there is no such KDE which is specially designed to estimate thep.d.f. for the stream data, i.e., estimate the p.d.f. in a nonstationary or incremental way. The stream data [17] can be regarded as a dynamic dataset of which the amount gradually increases with the continuous collection of new data. When the data are obtained by the learning system in a batch way, the existing KDEs have to reestablish the bran-new p.d.f.s based on the combination of current data and newly coming data. This training mode severely wastes the computation resource because the information regarding p.d.f. estimated with the current data is fully discarded. In addition, it can significantly increase the computation time if the p.d.f. is estimated by putting the current data and newly coming data together. The existing KDEs cannot work well if the total amount of data with the progression of data batches is beyond the memory capacity of computer. The incremental learning [18] provides an efficient paradigm to deal with the stream data, especially in the big data age, and it also gives a flexible and feasible way to analyze the large-scale data.This article proposes an incremental kernel density estimator (I-KDE) for stream data mining. The I-KDE updates the current KDE dynamically and gradually with the newly coming data rather than retraining the bran-new KDE with the combination of current data and newly coming data. The I-KDE deals with thep.d.f. estimation problem in the way of data stream computation. The theoretical analysis proves the convergence of the I-KDE only if the estimated p.d.f. of newly coming data is convergent to its true p.d.f. In order to guarantee the convergence of the I-KDE, a new multivariate fixed-point iteration algorithm based on the unbiased cross validation (UCV) [11] is developed to determine the optimal bandwidth of the KDE. The experimental results on 10 univariate and 4 multivariate probability distributions demonstrate the feasibility and effectiveness of the I-KDE to estimate the p.d.f. of stream data. The remainder of this article is organized as follows. In Section 2, we introduce our problem formulation. The I-KDE is presented in Section 3. In Section 4, we report the experimental results to demonstrate the effectiveness of the I-KDE. Finally, we give our conclusions and suggestions for the future research in Section 5.


## 2. Problem Formulation

Assume there areTT=1,2,3,… datasets D1,D2,…,DT with N1,N2,…,NT D-dimensional samples, respectively, where(1)Dt=zitzit=zi1t,zi2t,…,ziDt,zidt∈ℜ,i=1,2,…,Nt,d=1,2,…,D,t=1,2,…,T.Let(2)DT=∪t=1TDt=xnTxnT=xn1T,xn2T,…,xnDT,xndT∈ℜ,n=1,2,…,NT,d=1,2,…,D,NT=∑t=1TNt,represent the combination of datasets D1,D2,…,DT. For any xnT∈D,n=1,2,…,N, there exists t∈1,2,…,T and i∈1,2,…,Nt such that xnT=zit. If we want to estimate the underlying p.d.f. for dataset DT, the mathematical model of classical KDE [7] is described as(3)P¯H¯TTx=1NT∑n=1NTKH¯Tx−xnT=1NT∑n=1NTκx1−xn1T/h¯1T,x2−xn2T/h¯2T,…,xD−xnDT/h¯DT∏d=1Dh¯dT,where(4)κx=12πDexp−12xTx=∏d=1D12πexp−12xd2,is the standard D-variate Gaussian kernel function and(5)H¯T=h¯1T,h¯2T,…,h¯DT,h¯dT>0,d=1,2,…,D,is the optimal window bandwidth which can be determined with the different bandwidth selection strategies, e.g., the bootstrap method [10], unbiased cross validation (UCV) method [11], biased cross validation (BCV) method [12], and the solve-the-equation method [13].In fact, the estimation paradigm as shown in equation (3) has the following three limitations. First, equation (3) cannot retain the information of current p.d.f. when the data arrive at the learning system sequentially. Second, the computation times are obviously different even for the newly coming data with the same size. The earlier the data arrive, the less training time is required. Third, equation (3) does not work well when the data amount is beyond the memory capacity of the computer. The main reason for these limitations is that the existing KDE must put all the data together to estimate a bran-new p.d.f. Our solution mainly focuses on how to retain the current p.d.f. and uses the newly coming data to update the current p.d.f. The research problem of this article is depicted as follows.Problem Statement. Assume the current p.d.f. estimated by the current learning system based on data DT=∪t=1TDt is P⌢Tx, where the positive integer T≥1 is the number of data batches. Our objective is to use the p.d.f. P¯H¯T+1T+1x estimated with newly coming data DT+1 to update P⌢Tx and then obtain the estimated p.d.f. P⌢T+1x for data DT+1=DT∪DT+1=∪t=1T+1Dt, i.e.,(6)P⌢T+1x=P⌢Tx⊕P¯H¯T+1T+1x,where the mathematical symbol ⊕ represents the incremental updating to previous result.


## 3. I-KDE: An Incremental Kernel Density Estimator

This section presents an incremental KDE (I-KDE) for the stream data mining. Assume the learning system has receivedTT≥1 batches of data D1,D2,…,DT and the newly coming dataset is(7)DT+1=ziT+1ziT+1=zi1T+1,zi2T+1,…,ziDT+1,zidT+1∈ℜ,i=1,2,…,NT+1,d=1,2,…,D.The estimatedp.d.f.s P¯H¯TTx, P¯H¯T+1T+1x, and P¯H¯T+1T+1x with data DT=∪t=1TDt, DT+1, and DT+1=DT∪DT+1 are(8)P¯H¯TTx=1NT∑n=1NTKH¯Tx−xnT,P¯H¯T+1T+1x=1NT+1∑n=1NT+1KH¯T+1x−znT+1,(9)P¯H¯T+1T+1x=1NT+1∑n=1NT+1KH¯T+1x−xnT+1=1NT+NT+1∑n=1NTKH¯T+1x−xnT+∑n=1NT+1KH¯T+1x−znT+1=NTNT+NT+11NT∑n=1NTKH¯T+1x−xnT+NT+1NT+NT+11NT+1∑n=1NT+1KH¯T+1x−znT+1=NTNT+NT+1P¯H¯T+1Tx+NT+1NT+NT+1P¯H¯T+1T+1x,respectively, where(10)H¯T+1=h¯1T+1,h¯2T+1,…,h¯DT+1,h¯dT+1>0,d=1,2,…,D,is the optimal bandwidth of p.d.f. P¯H¯T+1T+1x estimated with the newly coming data DT+1.In equation (10), we can find that it consumes less time to determine the bandwidth H¯T+1 than to determine H¯T and H¯T+1 when NT≫NT+1 and NT+1≫NT+1. Thus, the I-KDE only considers how to determine the optimal bandwidth for the newly coming data DT+1 and gives up to calculate the bandwidths for both the current data DT and the combination DT+1 of current data and newly coming data. Then, Eq. (9) can be represented as(11)P⌢T+1x=NTNT+NT+1P⌢Tx+NT+1NT+NT+1P¯H¯T+1T+1x.According to equation (11), we can iteratively derive the following equations:(12)P⌢Tx=NT−1NT−1+NTP⌢T−1x+NTNT−1+NTP¯H¯TTx,P⌢T−1x=NT−2NT−2+NT−1P⌢T−2x+NT−1NT−2+NT−1P¯H¯T−1T−1x,⋮P⌢2x=N1N1+N2P⌢1x+N2N1+N2P¯H¯22x.The learning system only receives the dataD1,(13)P⌢1x=P¯H¯11x,holds for D1=D1. Substituting equation (12) into equation (11) yields the mathematical model of the I-KDE as(14)P⌢T+1x=N1∑t=1TNt+NT+1P¯H¯11x+N2∑t=1TNt+NT+1P¯H¯22x+⋯+NT∑t=1TNt+NT+1P¯H¯TTx+NT+1∑t=1TNt+NT+1P¯H¯T+1T+1x=∑k=1T+1Nk∑t=1TNt+NT+1P¯H¯kkx,where H¯kk=1,2,…,T+1 is the optimal bandwidth of p.d.f. estimated with data Dk. Equation (14) reveals that the KDE trained based on the union of different data blocks can be decomposed into the different KDEs which are trained based on the corresponding data blocks in an independent way. In equation (14), we can find that the I-KDE is an asymptotic integration model of a series of KDEs which are trained gradually based on the different data blocks. The I-KDE provides an effective way to deal with the p.d.f. estimation problem for stream data and meanwhile makes it possible to estimate the p.d.f. for large-scale data by partitioning it into different data blocks. Figure 1 depicts the procedure of the I-KDE.Figure 1
When the newly coming dataDT+1 arrive at the learning system, I-KDE uses equation (14) to update the current p.d.f. rather than reestimate the p.d.f. for the combination of current data and newly coming data.We provide a brief analysis to the computation complexity of the I-KDE. The classical unbiased cross validation (UCV) method [11] is used in this article to determine the optimal bandwidth. Its computation complexity is ON2D, where N is the number of samples and D is the number of sample dimensions. Assume the learning system receives T batches of data D1,D2,…,DT; the time complexity of the I-KDE is(15)TI-KDE=ON12D+ON22D+⋯+ONT2D=O∑t=1TNt2D.If we reestablish a bran-newp.d.f. for each batch of data by training the KDE based on the combination of current data and newly coming data, the time complexity of full retraining scheme is(16)TRetraining1=ON12D+ON1+N22D+⋯+ON1+N2+⋯+NT2D=O∑t=1T∑k=1tNk2D,where(17)TRetraining2=ON1+N2+⋯+NT2D=O∑t=1TNt2D,is the time complexity of estimating the p.d.f. for data DT=∪t=1TDt. By comparing equation (15) with equation (16), we can get that the time complexity of the I-KDE is far less than the time complexity of retraining scheme, i.e., ∑t=1TNt2D≪∑t=1T∑k=1tNk2D. In addition, we can know that the I-DKE is able to deal with the p.d.f. estimation for large-scale data by comparing equation (15) with equation (17) because ∑t=1TNt2D≪∑t=1TNt2D. Figure 2 presents the comparison of time complexity between the I-KDE and retraining scheme.Figure 2
The comparison of time complexity between the I-KDE and retraining scheme. LetT=10, D=10, and Nt=10,000,t=1,2,…,T in the experimental simulation. The time complexity of the I-KDE is far less than the time complexity of retraining scheme. (a) TI-KDEvs.TRetraining1. (b) TI-KDEvs.TRetraining2.
(a)
(b)Now, we give the theoretical analysis to the convergence of I-KDE. First, a lemma regarding the consistency of probability distribution function is given.Lemma 1.
Assume the probability distribution functions ofD-dimensional random variables X1,X2,…,XT are ℱ1x,ℱ2x,…,ℱTx. Dt includes Nt observations which obey the probability distribution function ℱtx,t=1,2,…,T. If X1,X2,…,XT are mutually independent, then(18)ℱx=∑t=1TNtNℱtx,where N=∑t=1TNt,D=∪t=1TDt, and its probability distribution function is ℱx.Proof.
For anyx=x1,x2,…,xD∈ℜD, the number of observations u=u1,u2,…,uD∈Dt,t=1,2,…,T satisfying(19)u1≤x1,u2≤x2,…,uD≤xD,is(20)Ntℱtx.
Thus, the number of observationsv=v1,v2,…,vD∈D=∪t=1TDt satisfying(21)v1≤x1,v2≤x2,…,vD≤xD,is(22)∑t=1TNtℱtx.
Then, the probability distribution functionℱx is(23)ℱx=∑t=1TNtℱtxN=∑t=1TNtNℱtx.
This concludes the proof.Theorem 1 (convergence of I-KDE).
AssumeDt includes Nt observations of D-dimensional random variables Xt of which the p.d.f. is Ptx,t=1,2,…,T and D=∪t=1TDt includes N=∑t=1TNt observations of D-dimensional random variable X of which the p.d.f. is Px. If X1,X2,…,XT are mutually independent and there exists εt>0 such that Ptx−P¯tx<εt for t=1,2,…,T, then(24)Px−P¯x<∑t=1TNtNεt,where P¯tx is the estimated p.d.f. with the KDE on data Dt and P¯x=∑t=1TNt/NP¯tx are the estimated p.d.f.s with the I-KDE on data D.Proof.
Based on Lemma1, we have(25)Px=∑t=1TNtNPtx.
Then,(26)Px−P¯x=∑t=1TNtNPtx−∑t=1TNtNP¯tx=∑t=1TNtNPtx−P¯tx.
For the givenεt>0,t=1,2,…,T,Ptx−P¯tx<εt holds. Thus, we can derive(27)Px−P¯x≤∑t=1TNtNPtx−P¯tx≤∑t=1TNtNεt.
This completes the proof.
Note. When εt⟶0 for t=1,2,…,T, then ∑t=1TNt/Nεt⟶0. It means that P¯x can approximate Px well if P¯tx can approximate Ptx well.
Theorem1 demonstrates the convergence of the I-KDE when the estimated p.d.f. P¯tx converges to the true p.d.f. Ptx. In order to obtain an accurate p.d.f. estimation for P¯H¯ttx,t=1,2,…,T in equation (14), we use the multivariate fixed-point iteration to design the bandwidth optimization method based on UCV error criterion. The formulation [12] of UCV error criterion for D-dimensional observations Dt=zitzit=zi1t,zi2t,…,ziDt,zidt∈ℜ,i=1,2,…,Nt,d=1,2,…,D is(28)UCVHt=UCVh1t,h2t,…,hDt=12πDNth1th2t…hDt+12πDNt2h1th2t…hDt×∑i=1Nt∑j=1j≠iNtexp−14∑d=1DΔijdt2−2×2D/2exp−12∑d=1DΔijdt2,where(29)Δijdt=zidt−zjdthdt.
The optimal bandwidth for the estimatedp.d.f. P¯H¯ttx satisfies(30)H¯t=argminhdt>0,d=1,2,…,DUCVHt.
We calculate the partial derivative ofUCVHt with respect to hdt,d=1,2,…,D and let(31)∂UCVHt∂hdt=−12πDNt∏k=1k≠dDhkthdt2+−12πDNt2∏k=1k≠dDhkthdt2Δd1th1t,h2t,…,hDt+12πDNt2∏k=1k≠dDhkthdt4Δd2th1t,h2t,…,hDt=0where(32)Δd1th1t,h2t,…,hDt=∑i=1Nt∑j=1j≠iNtexp−14∑d=1DΔijdt2−2×2D/2exp−12∑d=1DΔijdt2,Δd2th1t,h2t,…,hDt=∑i=1Nt∑j=1j≠iNt12zidt−zjdt2exp−14∑d=1DΔijdt2−2×2D/2zidt−zjdt2exp−12∑d=1DΔijdt2.
It is very difficult to calculate the analytic solution ofhdt, d=1,2,…,D from equation (31). However, an iterative function with respect to hdt can be derived by simplifying equation (31):(33)hdt=Δd2th1t,h2t,…,hDtNt+Δd1th1t,h2t,…,hDt.
Furthermore, a multivariate fixed-point iteration algorithm can be designed based on the aforementioned iterative function to determine the optimal bandwidthH¯t=h¯1t,h¯2t,…,h¯Dt.


## 4. Experimental Results and Analysis

In this section, we conduct three experiments to demonstrate the feasibility and effectiveness of our proposed I-KDE based on 10 univariate and 4 multivariate probability distributions of which the details are listed in Table1 [19]. First, we validate the convergence of Algorithm 1. Second, we demonstrate the convergence of the I-KDE. Third, we test the p.d.f. estimation performance of the I-KDE.Table 1
The details of 10 univariate and 4 multivariate probability distributions (Pix in bimodal, trimodal, and quadrimodal normal distributions is the D-dimensional normal distribution with mean vector Θi=μ1i,μ2i,…,μDi and covariance matrix Σi=σ11iσ12i⋯σ1Diσ21iσ22i⋯σ2Di⋮⋮⋱⋮σD1iσD2i⋯σDDi).
#
Probability distribution
p.d.f.
Univariate
1
Beta
P
x
=
x
α
−
1
1
−
x
β
−
1
/
∫
0
1
x
α
−
1
1
−
x
β
−
1
d
x
,
α
>
0
,
β
>
0
;
x
∈
0,1
or
x
∈
0,1
2
Chi-squared
P
x
=
2
−
k
/
2
x
k
/
2
−
1
e
−
x
/
2
/
∫
0
+
∞
x
k
/
2
−
1
e
−
x
d
x
,
k
=
1,2,3
,
…
;
x
∈
0
,
+
∞ or x∈0,+∞
3
Exponential
P
x
=
1
/
μ
e
−
x
/
μ
,
μ
>
0
;
x
∈
0
,
+
∞
4
F
P
x
=
n
1
n
1
/
2
n
2
n
2
/
2
x
n
1
/
2
−
1
/
∫
0
1
x
n
1
/
2
−
1
1
−
x
n
2
/
2
−
1
d
x
n
1
x
+
n
2
n
1
+
n
2
/
2
,
n
1
,
n
2
=
1,2,3
,
…
;
x
∈
0
,
+
∞
5
Gamma
P
x
=
x
α
−
1
e
−
x
/
β
/
β
α
∫
0
+
∞
x
α
−
1
e
−
x
d
x
,
α
>
0
,
β
>
0
;
x
∈
0
,
+
∞
6
Lognormal
P
x
=
1
/
2
π
σ
x
e
−
1
/
2
In
x
−
μ
/
σ
2
,
μ
∈
−
∞
,
+
∞
,
σ
>
0
;
x
∈
0
,
+
∞
7
Normal
P
x
=
N
μ
,
σ
=
1
/
2
π
σ
e
−
1
/
2
x
−
μ
/
σ
2
,
μ
∈
−
∞
,
+
∞
,
σ
>
0
;
x
∈
−
∞
,
+
∞
8
Rayleigh
P
x
=
x
/
σ
2
e
−
1
/
2
x
/
σ
2
,
σ
>
0
;
x
∈
0
,
+
∞
9
Student’sT
P
x
=
∫
0
+
∞
x
v
+
1
/
2
−
1
e
−
x
d
x
/
π
v
∫
0
+
∞
x
v
/
2
−
1
e
−
x
d
x
1
+
x
2
/
v
−
v
+
1
/
2
,
v
>
0
;
x
∈
−
∞
,
+
∞
10
Weibull
P
x
=
β
/
α
β
x
β
−
1
e
−
x
/
α
β
,
σ
>
0
,
β
>
0
;
x
∈
0
,
+
∞
Multivariate
1
D-dimensional standard normal
P
x
=
2
π
−
D
/
2
Σ
−
1
/
2
e
−
1
/
2
x
−
Θ
T
Σ
−
1
x
−
Θ
,
x
=
x
1
,
x
2
,
…
,
x
D
,
x
d
∈
−
∞
,
+
∞
,
d
=
1,2
,
…
,
D
; Θ=μ1,μ2,...,μD is the mean vector, μd∈−∞,+∞,d=1,2,…,D; Σ=σ11σ12⋯σ1Dσ21σ22⋯σ2D⋮⋮⋱⋮σD1σD2⋯σDD is the covariance matrix, σij>0,i,j=1,2,…,D
2
D-dimensional bimodal normal
P
x
=
∑
i
=
1
2
ε
i
P
i
x
,
∑
i
=
1
2
ε
i
=
1
,
ε
i
≥
0
,
i
=
1,2
;
x
=
x
1
,
x
2
,
…
,
x
D
3
D-dimensional trimodal normal
P
x
=
∑
i
=
1
3
ε
i
P
i
x
,
∑
i
=
1
3
ε
i
=
1
,
ε
i
≥
0
,
i
=
1,2,3
;
x
=
x
1
,
x
2
,
…
,
x
D
4
D-dimensional quadrimodal normal
P
x
=
∑
i
=
1
4
ε
i
P
i
x
,
∑
i
=
1
4
ε
i
=
1
,
ε
i
≥
0
,
i
=
1,2,3,4
;
x
=
x
1
,
x
2
,
…
,
x
DAlgorithm 1: A multivariate fixed-point iteration algorithm to determine the optimal bandwidth for the I-KDE.
(1)
Input: the given data Dt; the initial bandwidth hdt>0,d=1,2,…,D; the stopping threshold ξ>0.
(2)
Output: the optimal bandwidth h¯dt>0,d=1,2,…,D.
(3)
Repeat
(4)
For d=1;d≤D;d=d+1 do
(5)
h¯dt=hdt;
(6)
hdt=Δd2th¯1t,h¯2t,…,h¯Dt/Nt+Δd1th¯1t,h¯2t,…,h¯Dt;
(7)
End For
(8)
Until H¯t−Ht1<ξ


### 4.1. Convergence of Algorithm 1

In this experiment, we check the convergence of Algorithm1 on 2 univariate (beta and normal) and 2 multivariate (2-dimensional bimodal and quadrimodal normal) probability distributions. For each distribution, 1000 samples are randomly generated under Matlab programming environment. The experimental results are listed in Figure 3 and confirm that our designed fixed-point iteration algorithm can find the optimal bandwidths for univariate and multivariate UCV error criteria.Figure 3
The convergence of Algorithm1 on 2 univariate and 2 multivariate distributions (a) Beta distribution α=2,β=5,andh¯=0.048. (b) Normal distribution μ=0,σ=1,andh¯=0.331. (c) 2-dimensional Bimodal normal distribution (Θ1=−2.5,−2.5,Θ2=2.5,2.5,Σ1andΣ2 are the identity matrices ε1=ε2=1/2,h¯1=0.546andh¯2=0.595). (d) 2-dimensional Quadrimodal normal distribution (Θ1=−2.5,−2.5,Θ2=2.5,2.5,Θ3=−2.5,2.5Θ4=2.5,−2.5,Σ1,Σ2,Σ3,andΣ4 are the identity matrices ε1=ε2=ε3=ε4=1/4,h¯1=0.451andh¯2=0.575).
(a)
(b)
(c)
(d)For the univariate probability distribution, e.g., the beta distribution in Figure3(a), we can see that the UCV error first decreases and then increases with the increase of bandwidth parameter. For the any initial bandwidth value 0.001 or 1, our designed fixed-point iteration algorithm can find the optimal bandwidth 0.048 for the I-KDE. For the multivariate probability distribution, e.g., the 2-dimensional quadrimodal normal distribution in Figure 3(d), we know that its UCV error has the minimum value −0.020. Algorithm 1 determines the optimal bandwidth vector (0.451, 0.575). The learning curves corresponding to the bandwidth optimization demonstrate the convergence of Algorithm 1.


### 4.2. Convergence of I-KDE

The objective of this experiment is to check whether the estimation of I-KDE which is trained by means of data stream computation can converge to the estimation of KDE which is trained based on the combination of current data and newly coming data. The initial bandwidths in Algorithm1 are determined based on the RoT method. The experimental results are presented in Figure 4.Figure 4
The convergence of the I-KDE on univariate and multivariate distributions. (a) Univariate case (the black curve represents thep.d.f. of newly coming data; the green curve represents the p.d.f. estimated with the KDE based on the combination of current data and newly coming data; and the red curve represents the p.d.f. estimated with the I-KDE in the way of data stream computation). (b) Multivariate case (the symbol ∪ represents the p.d.f. estimated with the KDE based on the combination of current data and newly coming data and the symbol ⊕ represents the p.d.f. estimated with the I-KDE in the way of data stream computation).
(a)
(b)For the univariate case, we use 10 different probability distributions as shown in Table1. For each distribution, 5000 samples are randomly generated. The parameter settings of these p.d.f.s are summarized as follows: α=2 and β=2 for beta, k=2 for chi-squared, μ=1.5 for exponential, n1=100 and n2=100 for F, α=9 and β=0.5 for gamma, μ=0 and σ=0.25 for lognormal, μ=0 and σ=1 for normal, σ=1 for Rayleigh, v=1 for Student’s T, and α=1 and β=5 for Weibull. In Figure 4(a), we can see that the red and green curves almost coincide with the coming of new data. It is very hard to distinguish the red and green curves.The similar situation exists in the multivariate case. For the multivariate case, 5 different probability distributions are selected. In Figure4(b), the parameter settings of these p.d.f.s are summarized as follows: Θ=2.5,2.5 and Σ=1,0;0,1 for D1, Θ=0,0 and Σ=1,1.5;1.5,3 for D2, Θ1=−2.5,−2.5, Θ2=2.5,2.5, Σ1=Σ2=1,0;0,1 and ε1=ε2=1/2 for D3, Θ1=−2.5,−2.5, Θ2=2.5,2.5, Θ3=0,0, Σ1=Σ2=Σ3=1,0;0,1 and ε1=ε2=ε3=1/3 for D4, Θ1=−2.5,−2.5, Θ2=2.5,2.5, Θ3=−2.5,2.5, Θ4=2.5,−2.5, Σ1=Σ2=Σ3=Σ4=1,0;0,1, and ε1=ε2=ε3=ε4=1/4 for D5. We can see that the I-KDE and KDE obtain the similar probability distributions with the different estimation ways. The experimental results visually reflect that the I-KDE can converge to the KDE in an incremental manner.In addition, we use the Jensen–Shannon (JS) divergence to measure the similarity between two differentp.d.f.s estimated with the KDE and I-KDE, respectively. The JS divergence is a variant of Kullback–Leibler (KL) divergence [20]. The smaller the JS divergence is, the more similar the two p.d.f.s are. In Figure 4, we can see that the JS divergences are small and the quantitative measures also reflect that the differences between KDEs and I-KDEs are small.We also test the convergence performance of the I-KDE on the testing data corresponding to beta (α=2 and β=2) and 2-dimensional trimodal normal Θ1=−5,−5,Θ2=5,−3,Θ3=−2,5Σ1=Σ2=Σ3=0.5,0;0,0.5andε1=ε2=ε3=1/3 distributions as shown in Figure 5. For each distribution, 2000 training samples are randomly generated and partitioned into 20 data blocks. We check the ratio of testing samples with the smaller absolute error to all testing samples. In Figure 5, we can see that the win ratios (i.e., the proportions of data points with smaller estimation errors) of the I-KDE and KDE are almost same with the increase of data blocks. This indicates that the I-KDE has the equivalent estimation capability with the KDE. Figure 5 also provides the comparison of training time. We can find that the training time of the I-KDE is far less than the KDE.Figure 5
The convergence of the I-KDE on beta and 2-dimensional trimodal normal distributions. (a) Univariate case on beta distribution (99 testing samples are selected from 0.01 to 0.99 with incremental step of 0.01). (b) Multivariate case on 2-dimensional trimodal normal distribution (40000 testing samples are selected with the incremental steps of (0.01, 0.01) in the space of [−9.9, 10] ∪ [−9.9, 10]).
(a)
(b)Figure6 shows the convergence tendency of the I-KDE on 2-dimensional bimodal normal Θ1=−5,−5,Θ2=5,5,Σ1=Σ2=0.5,0;0,0.5andε1=ε2=1/2 distribution. 2000 training samples are randomly generated and partitioned into 20 data blocks. 20000 testing samples are selected with the incremental steps of (0.01, 0.01) in the space of [−9.9, 10] ∪ [0.1, 10]. In Figure 6, the black points are training samples and the red points are the testing samples estimated by the I-KDE with the smaller absolute error. We can see that the estimation performance of the I-KDE will gradually converge to a stable state with the increase of training samples.Figure 6
The convergence tendency of the I-KDE on 2-dimensional bimodal normal distribution (the value in the parenthesis is the win ratio of the I-KDE). (a) 1 data block (1.000). (b) 2 data blocks (0.783). (c) 3 data blocks (0.790). (d) 4 data blocks (0.739). (e) 5 data blocks (0.748). (f) 6 data blocks (0.727). (g) 7 data blocks (0.705). (h) 8 data blocks (0.675). (i) 9 data blocks (0.672). (j) 10 data blocks (0.613). (k) 11 data blocks (0.625). (l) 12 data blocks (0.626). (m) 13 data blocks (0.634). (n) 14 data blocks (0.628). (o) 15 data blocks (0.621). (p) 16 data blocks (0.638). (q) 17 data blocks (0.620). (r) 18 data blocks (0.614). (s) 19 data blocks (0.610). (t) 20 data blocks (0.604).
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
(m)
(n)
(o)
(p)
(q)
(r)
(s)
(t)


### 4.3. Estimation Performance of I-KDE

Table2 presents the comparison between the KDE and I-KDE on 10 univariate and 4 multivariate distributions, where the parameter settings of beta, chi-squared, exponential, F, gamma, lognormal, Rayleigh, Student’s T, Weibull, 2-dimensional bimodal normal, and 2-dimensional trimodal normal distributions are the same as Figures 4(a), 5, and 6. The p.d.f. of Bimodal normal is Px=3/4N0,1+1/4N3/2,1/3. The parameters of 2-dimensional standard normal distribution are Θ=0,0 and Σ=1,0;0,1. The parameters of 2-dimensional quadrimodal normal distributions are Θ1=−2,−4,Θ2=3,4,Θ3=−4,3,Θ4=4,−2,Σ1=Σ2=Σ3=Σ4=0.5,0;0,0.5,andε1=ε2=ε3=ε4=1/4. In addition, the initial bandwidths in Algorithm 1 are determined based on the RoT method. For each distribution, the mean absolute error (MAE) and number of win samples are the average values of 10 runs of different trainings. We give a statistical analysis to the experimental results in Table 2 and confirm that the I-KDE is statistically convergent to the KDE. Taking Exponential distribution for example, we use the Wilcoxon signed-ranks test [21] to check whether the difference between the I-KDE and KDE is significant. Table 3 lists the comparative results of the I-KDE and KDE on 10 different training datasets of exponential distribution.Table 2
The comparison between the KDE and I-KDE on 10 univariate and 4 multivariate distributions.
#
Probability distribution
Training samples
Testing space
Testing samples
KDE
I-KDE
MAE
Win samples
MAE
Win samples
Univariate
1
Beta
2000
[0.01, 0.99]
99
0.053
52
0.048
47
2
Chi-squared
2000
[0.01, 20]
2000
0.005
437
0.004
1563
3
Exponential
2000
[0.01, 10]
1000
0.014
178
0.013
822
4
F
2000
[0.01, 10]
1000
0.007
241
0.008
759
5
Gamma
2000
[1.01, 11]
1000
0.005
540
0.008
460
6
Lognormal
2000
[0.01, 20]
2000
0.005
501
0.006
1499
7
Bimodal normal
2000
[−4.99, 5]
1000
0.040
252
0.038
748
8
Rayleigh
2000
[0.01, 1]
100
0.062
45
0.064
55
9
Student’sT
2000
[−9.99, 10]
2000
0.003
820
0.004
1180
10
Weibull
2000
[0.01, 10]
1000
0.012
176
0.010
824
Multivariate
1
2-dimensionalStandard normal
2400
[−4.9, 5][−4.9, 5]
10000
0.001
5489
0.002
4511
2
2-dimensionalBimodal normal
2400
[−9.9, 10][0.1, 10]
20000
0.001
7660
0.001
12340
3
2-dimensionalTrimodal normal
2400
[−9.9, 10][−9.9, 10]
40000
0.000
19936
0.001
20064
4
2-dimensionalQuadrimodal normal
2400
[−9.9, 10][−9.9, 10]
40000
0.000
20113
0.001
19887
The training datasets can be downloaded from BaiduPan (https://pan.baidu.com/s/1wgj-gTzEZL51WTtl2RpCzA) with the extraction code “kai5.”Table 3
The comparison of MAE for the KDE and I-KDE on exponential distribution.
MAE of KDE
MAE of I-KDE
Difference
Rank
Training dataset 1
0.012
0.013
d
1
=
+
0.001
rank
d
1
=
5.5
Training dataset 2
0.016
0.013
d
2
=
−
0.003
rank
d
2
=
9.5
Training dataset 3
0.014
0.013
d
3
=
−
0.001
rank
d
3
=
5.5
Training dataset 4
0.016
0.014
d
4
=
−
0.002
rank
d
4
=
8
Training dataset 5
0.013
0.014
d
5
=
+
0.001
rank
d
5
=
5.5
Training dataset 6
0.014
0.013
d
6
=
−
0.001
rank
d
6
=
5.5
Training dataset 7
0.014
0.014
d
7
=
+
0.000
rank
d
7
=
2
Training dataset 8
0.012
0.012
d
8
=
+
0.000
rank
d
8
=
2
Training dataset 9
0.013
0.013
d
9
=
+
0.000
rank
d
9
=
2
Training dataset 10
0.016
0.013
d
10
=
−
0.003
rank
d
10
=
9.5LetR+ be the sum of ranks for the training dataset on which the KDE outperforms the I-KDE and R− be the sum of ranks for the training datasets on which the I-KDE outperforms the KDE. We can calculate(34)R+=∑di>0rankdi+12∑di=0rankdi=41and(35)R−=∑di<0rankdi+12∑di=0rankdi=14.We construct the statistics(36)z=minR+,R−−1/4TT+11/24TT+12T+1=14−1/4×10×10+11/24×10×10+1×2×10+1=−1.37,which is distributed approximately normally. The null hypothesis that the KDE and I-KDE perform equally well can be rejected if z is smaller than −1.96 under the confidence level of 0.05. Because z>−1.96, we accept the null hypothesis, i.e., the difference between the KDE and I-KDE is not significant. The similar result exists for the other distributions in Table 2. To sum up, we demonstrate that the I-KDE can obtain the equivalent p.d.f. estimation performance with the less training time in comparison to the KDE. The experimental results reveal that it is feasible to use I-KDE to deal with the p.d.f. estimation problem of large-scale data in the way of data stream computation.


## 4.1. Convergence of Algorithm 1

In this experiment, we check the convergence of Algorithm1 on 2 univariate (beta and normal) and 2 multivariate (2-dimensional bimodal and quadrimodal normal) probability distributions. For each distribution, 1000 samples are randomly generated under Matlab programming environment. The experimental results are listed in Figure 3 and confirm that our designed fixed-point iteration algorithm can find the optimal bandwidths for univariate and multivariate UCV error criteria.Figure 3
The convergence of Algorithm1 on 2 univariate and 2 multivariate distributions (a) Beta distribution α=2,β=5,andh¯=0.048. (b) Normal distribution μ=0,σ=1,andh¯=0.331. (c) 2-dimensional Bimodal normal distribution (Θ1=−2.5,−2.5,Θ2=2.5,2.5,Σ1andΣ2 are the identity matrices ε1=ε2=1/2,h¯1=0.546andh¯2=0.595). (d) 2-dimensional Quadrimodal normal distribution (Θ1=−2.5,−2.5,Θ2=2.5,2.5,Θ3=−2.5,2.5Θ4=2.5,−2.5,Σ1,Σ2,Σ3,andΣ4 are the identity matrices ε1=ε2=ε3=ε4=1/4,h¯1=0.451andh¯2=0.575).
(a)
(b)
(c)
(d)For the univariate probability distribution, e.g., the beta distribution in Figure3(a), we can see that the UCV error first decreases and then increases with the increase of bandwidth parameter. For the any initial bandwidth value 0.001 or 1, our designed fixed-point iteration algorithm can find the optimal bandwidth 0.048 for the I-KDE. For the multivariate probability distribution, e.g., the 2-dimensional quadrimodal normal distribution in Figure 3(d), we know that its UCV error has the minimum value −0.020. Algorithm 1 determines the optimal bandwidth vector (0.451, 0.575). The learning curves corresponding to the bandwidth optimization demonstrate the convergence of Algorithm 1.


## 4.2. Convergence of I-KDE

The objective of this experiment is to check whether the estimation of I-KDE which is trained by means of data stream computation can converge to the estimation of KDE which is trained based on the combination of current data and newly coming data. The initial bandwidths in Algorithm1 are determined based on the RoT method. The experimental results are presented in Figure 4.Figure 4
The convergence of the I-KDE on univariate and multivariate distributions. (a) Univariate case (the black curve represents thep.d.f. of newly coming data; the green curve represents the p.d.f. estimated with the KDE based on the combination of current data and newly coming data; and the red curve represents the p.d.f. estimated with the I-KDE in the way of data stream computation). (b) Multivariate case (the symbol ∪ represents the p.d.f. estimated with the KDE based on the combination of current data and newly coming data and the symbol ⊕ represents the p.d.f. estimated with the I-KDE in the way of data stream computation).
(a)
(b)For the univariate case, we use 10 different probability distributions as shown in Table1. For each distribution, 5000 samples are randomly generated. The parameter settings of these p.d.f.s are summarized as follows: α=2 and β=2 for beta, k=2 for chi-squared, μ=1.5 for exponential, n1=100 and n2=100 for F, α=9 and β=0.5 for gamma, μ=0 and σ=0.25 for lognormal, μ=0 and σ=1 for normal, σ=1 for Rayleigh, v=1 for Student’s T, and α=1 and β=5 for Weibull. In Figure 4(a), we can see that the red and green curves almost coincide with the coming of new data. It is very hard to distinguish the red and green curves.The similar situation exists in the multivariate case. For the multivariate case, 5 different probability distributions are selected. In Figure4(b), the parameter settings of these p.d.f.s are summarized as follows: Θ=2.5,2.5 and Σ=1,0;0,1 for D1, Θ=0,0 and Σ=1,1.5;1.5,3 for D2, Θ1=−2.5,−2.5, Θ2=2.5,2.5, Σ1=Σ2=1,0;0,1 and ε1=ε2=1/2 for D3, Θ1=−2.5,−2.5, Θ2=2.5,2.5, Θ3=0,0, Σ1=Σ2=Σ3=1,0;0,1 and ε1=ε2=ε3=1/3 for D4, Θ1=−2.5,−2.5, Θ2=2.5,2.5, Θ3=−2.5,2.5, Θ4=2.5,−2.5, Σ1=Σ2=Σ3=Σ4=1,0;0,1, and ε1=ε2=ε3=ε4=1/4 for D5. We can see that the I-KDE and KDE obtain the similar probability distributions with the different estimation ways. The experimental results visually reflect that the I-KDE can converge to the KDE in an incremental manner.In addition, we use the Jensen–Shannon (JS) divergence to measure the similarity between two differentp.d.f.s estimated with the KDE and I-KDE, respectively. The JS divergence is a variant of Kullback–Leibler (KL) divergence [20]. The smaller the JS divergence is, the more similar the two p.d.f.s are. In Figure 4, we can see that the JS divergences are small and the quantitative measures also reflect that the differences between KDEs and I-KDEs are small.We also test the convergence performance of the I-KDE on the testing data corresponding to beta (α=2 and β=2) and 2-dimensional trimodal normal Θ1=−5,−5,Θ2=5,−3,Θ3=−2,5Σ1=Σ2=Σ3=0.5,0;0,0.5andε1=ε2=ε3=1/3 distributions as shown in Figure 5. For each distribution, 2000 training samples are randomly generated and partitioned into 20 data blocks. We check the ratio of testing samples with the smaller absolute error to all testing samples. In Figure 5, we can see that the win ratios (i.e., the proportions of data points with smaller estimation errors) of the I-KDE and KDE are almost same with the increase of data blocks. This indicates that the I-KDE has the equivalent estimation capability with the KDE. Figure 5 also provides the comparison of training time. We can find that the training time of the I-KDE is far less than the KDE.Figure 5
The convergence of the I-KDE on beta and 2-dimensional trimodal normal distributions. (a) Univariate case on beta distribution (99 testing samples are selected from 0.01 to 0.99 with incremental step of 0.01). (b) Multivariate case on 2-dimensional trimodal normal distribution (40000 testing samples are selected with the incremental steps of (0.01, 0.01) in the space of [−9.9, 10] ∪ [−9.9, 10]).
(a)
(b)Figure6 shows the convergence tendency of the I-KDE on 2-dimensional bimodal normal Θ1=−5,−5,Θ2=5,5,Σ1=Σ2=0.5,0;0,0.5andε1=ε2=1/2 distribution. 2000 training samples are randomly generated and partitioned into 20 data blocks. 20000 testing samples are selected with the incremental steps of (0.01, 0.01) in the space of [−9.9, 10] ∪ [0.1, 10]. In Figure 6, the black points are training samples and the red points are the testing samples estimated by the I-KDE with the smaller absolute error. We can see that the estimation performance of the I-KDE will gradually converge to a stable state with the increase of training samples.Figure 6
The convergence tendency of the I-KDE on 2-dimensional bimodal normal distribution (the value in the parenthesis is the win ratio of the I-KDE). (a) 1 data block (1.000). (b) 2 data blocks (0.783). (c) 3 data blocks (0.790). (d) 4 data blocks (0.739). (e) 5 data blocks (0.748). (f) 6 data blocks (0.727). (g) 7 data blocks (0.705). (h) 8 data blocks (0.675). (i) 9 data blocks (0.672). (j) 10 data blocks (0.613). (k) 11 data blocks (0.625). (l) 12 data blocks (0.626). (m) 13 data blocks (0.634). (n) 14 data blocks (0.628). (o) 15 data blocks (0.621). (p) 16 data blocks (0.638). (q) 17 data blocks (0.620). (r) 18 data blocks (0.614). (s) 19 data blocks (0.610). (t) 20 data blocks (0.604).
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
(m)
(n)
(o)
(p)
(q)
(r)
(s)
(t)


## 4.3. Estimation Performance of I-KDE

Table2 presents the comparison between the KDE and I-KDE on 10 univariate and 4 multivariate distributions, where the parameter settings of beta, chi-squared, exponential, F, gamma, lognormal, Rayleigh, Student’s T, Weibull, 2-dimensional bimodal normal, and 2-dimensional trimodal normal distributions are the same as Figures 4(a), 5, and 6. The p.d.f. of Bimodal normal is Px=3/4N0,1+1/4N3/2,1/3. The parameters of 2-dimensional standard normal distribution are Θ=0,0 and Σ=1,0;0,1. The parameters of 2-dimensional quadrimodal normal distributions are Θ1=−2,−4,Θ2=3,4,Θ3=−4,3,Θ4=4,−2,Σ1=Σ2=Σ3=Σ4=0.5,0;0,0.5,andε1=ε2=ε3=ε4=1/4. In addition, the initial bandwidths in Algorithm 1 are determined based on the RoT method. For each distribution, the mean absolute error (MAE) and number of win samples are the average values of 10 runs of different trainings. We give a statistical analysis to the experimental results in Table 2 and confirm that the I-KDE is statistically convergent to the KDE. Taking Exponential distribution for example, we use the Wilcoxon signed-ranks test [21] to check whether the difference between the I-KDE and KDE is significant. Table 3 lists the comparative results of the I-KDE and KDE on 10 different training datasets of exponential distribution.Table 2
The comparison between the KDE and I-KDE on 10 univariate and 4 multivariate distributions.
#
Probability distribution
Training samples
Testing space
Testing samples
KDE
I-KDE
MAE
Win samples
MAE
Win samples
Univariate
1
Beta
2000
[0.01, 0.99]
99
0.053
52
0.048
47
2
Chi-squared
2000
[0.01, 20]
2000
0.005
437
0.004
1563
3
Exponential
2000
[0.01, 10]
1000
0.014
178
0.013
822
4
F
2000
[0.01, 10]
1000
0.007
241
0.008
759
5
Gamma
2000
[1.01, 11]
1000
0.005
540
0.008
460
6
Lognormal
2000
[0.01, 20]
2000
0.005
501
0.006
1499
7
Bimodal normal
2000
[−4.99, 5]
1000
0.040
252
0.038
748
8
Rayleigh
2000
[0.01, 1]
100
0.062
45
0.064
55
9
Student’sT
2000
[−9.99, 10]
2000
0.003
820
0.004
1180
10
Weibull
2000
[0.01, 10]
1000
0.012
176
0.010
824
Multivariate
1
2-dimensionalStandard normal
2400
[−4.9, 5][−4.9, 5]
10000
0.001
5489
0.002
4511
2
2-dimensionalBimodal normal
2400
[−9.9, 10][0.1, 10]
20000
0.001
7660
0.001
12340
3
2-dimensionalTrimodal normal
2400
[−9.9, 10][−9.9, 10]
40000
0.000
19936
0.001
20064
4
2-dimensionalQuadrimodal normal
2400
[−9.9, 10][−9.9, 10]
40000
0.000
20113
0.001
19887
The training datasets can be downloaded from BaiduPan (https://pan.baidu.com/s/1wgj-gTzEZL51WTtl2RpCzA) with the extraction code “kai5.”Table 3
The comparison of MAE for the KDE and I-KDE on exponential distribution.
MAE of KDE
MAE of I-KDE
Difference
Rank
Training dataset 1
0.012
0.013
d
1
=
+
0.001
rank
d
1
=
5.5
Training dataset 2
0.016
0.013
d
2
=
−
0.003
rank
d
2
=
9.5
Training dataset 3
0.014
0.013
d
3
=
−
0.001
rank
d
3
=
5.5
Training dataset 4
0.016
0.014
d
4
=
−
0.002
rank
d
4
=
8
Training dataset 5
0.013
0.014
d
5
=
+
0.001
rank
d
5
=
5.5
Training dataset 6
0.014
0.013
d
6
=
−
0.001
rank
d
6
=
5.5
Training dataset 7
0.014
0.014
d
7
=
+
0.000
rank
d
7
=
2
Training dataset 8
0.012
0.012
d
8
=
+
0.000
rank
d
8
=
2
Training dataset 9
0.013
0.013
d
9
=
+
0.000
rank
d
9
=
2
Training dataset 10
0.016
0.013
d
10
=
−
0.003
rank
d
10
=
9.5LetR+ be the sum of ranks for the training dataset on which the KDE outperforms the I-KDE and R− be the sum of ranks for the training datasets on which the I-KDE outperforms the KDE. We can calculate(34)R+=∑di>0rankdi+12∑di=0rankdi=41and(35)R−=∑di<0rankdi+12∑di=0rankdi=14.We construct the statistics(36)z=minR+,R−−1/4TT+11/24TT+12T+1=14−1/4×10×10+11/24×10×10+1×2×10+1=−1.37,which is distributed approximately normally. The null hypothesis that the KDE and I-KDE perform equally well can be rejected if z is smaller than −1.96 under the confidence level of 0.05. Because z>−1.96, we accept the null hypothesis, i.e., the difference between the KDE and I-KDE is not significant. The similar result exists for the other distributions in Table 2. To sum up, we demonstrate that the I-KDE can obtain the equivalent p.d.f. estimation performance with the less training time in comparison to the KDE. The experimental results reveal that it is feasible to use I-KDE to deal with the p.d.f. estimation problem of large-scale data in the way of data stream computation.


## 5. Conclusions and Future Works

In this article, we proposed an incremental kernel density estimator (I-KDE) to deal with the probability density function (p.d.f.) estimation problem in the way of data stream computation. The I-KDE updated the current KDE dynamically and gradually with the newly coming data rather than retraining the bran-new KDE with the combination of current data and newly coming data. The theoretical analysis proved the convergence of the I-KDE only if the estimated p.d.f. of newly coming data is convergent to its true p.d.f. The experimental results on 10 univariate and 4 multivariate probability distributions demonstrated that the I-KDE obtained the equivalent p.d.f. estimation performance with the less training time in comparison to the KDE and thus indicated that the I-KDE can be used to deal with the p.d.f. estimation problem of large-scale data in the way of data stream computation. In future, we will try to combine the I-KDE with the random sample partition (RSP) model [22, 23] of big data and seek the practical applications for the I-KDE, e.g., Bayesian classification, density-based clustering, and big data reduction [24].



---

*Source: 1803525-2020-02-21.xml*