Adaptive Estimation of Weight Coefficient in a Time-weighted Incremental EM-algorithm for Data Streams

Application of data stream clustering is quite general. Applications of data streams include mining data generated by sensor networks, meteorological analysis, stock market analysis, computer network traffic monitoring, long-term population-based, cognitive, real-time sociological studies etc. These applications involve datasets that are far too large to fit in main memory and are typically stored in a secondary storage device. Real-time processing of large volumes of data requires efficient, fast algorithms and data compression. Moreover, recently obtained objects are often more important than the old ones, so several clustering algorithms implement a damped window model with a user-defined decay coefficient. This coefficient is not obvious. An important task in the development of machine learning algorithms is to reduce the number of algorithm parameters (user-defined parameter) through the development of adaptive mechanisms. Such a mechanism for determining the decay coefficient proposed in this paper. A Gaussian mixture data stream algorithm is constructed with damped window model. Decay coefficient for the object according damped window is w=w(At) where At is time since object arrived from the stream into cluster, weight of the cluster W(t) is sum of all its objects. Recent objects receive higher weight than older ones, and the weights of the objects decrease with time. It is usually to assume w(At)=e (a>0), with following properties: 1) when arrives, the object weight is equal to one: w(0)=1; 2) over time object weight monotonic decreases to zero: lim w(At) = 0; At 3) if weight of object w(A^) after At! units of time is known, then after more At₂ it can be easily recalculates as w(Ati+At₂) = w(Atj)w(At₂); 4) if weight of cluster W(t) for the instant in time t is known, and during the next time period At there was no new objects arrived in this cluster, then weight of this cluster can be recalculates as W(t+At) = W(t)w(At). Let at initial instant in time we have a set of K Gaussian clusters C_k that described by their means ц and correlation matrixes X_k. Weight W_k at initial time defined as a number of objects in cluster C_k. Let {x₁, x₂, . ,.}eR is data stream, i.e. set of objects with timestamps t₁, t₂, .... When a new object x with timestamp t arrives to the cluster C_k, the following algorithm executes. Input: new object x, cluster parameters: mean correlation matrix X, weight W_k (k=1,2,...K), time period since last object arrives At. 1. Recalculate weights W_k = eW_k (k=1,2,...,K). W_k 9_k ( x\ ц_k, Z _K ) 2. Calculate probabilities of belonging x to the k-th cluster щ =--~i~\-. Put x into the most probable cluster. ZmWФ* (( Mi'' Z ) 3. For this cluster (in with x is, index of cluster is dropped) recalculate mean ц, correlation matrix X and weight W: W+ W (|~- x) ^ 2~+- W=W+1, w+1 i+ = _T ~ ; 2+ = w+1 w+1 where indexes - and + corresponds to the values before and after recalculation. Note that weight function depends on a>0, that may be defined individually for each C_k. We propose the following algorithm to recalculate a separately for each cluster at the time the object arrives into cluster. Input: xi, x₂,...,x_N - last N objects putted into cluster, t₁, ,t_N - their timestamps, |₀ - cluster mean Z₀ - cluster correlation matrix. 1. At initial instance of time t₀ adopt a=0, i.e. we assume that cluster is not moving. 2. When object x_i with timestamp t_i (i1 + x₂ + ...+ x_N)/Nand ft-t₀). v = (||0) _ 3. If i=N calculate ^n _{( )} using accumulated variables. Calculate a = -| v |ln e/r, where r is Euclidean distance be- 2 i=1i 0 tween |₀ and confidence ellipse boundary (confidence probability p = 1 - e) in direction of v vector. Set t₀=t_N, assign |₀ and Z₀ a corresponding values of cluster at the time t_N and return to step 1. We perform an experiment using an imitation model of Gaussian mixture clusters with moving centroids. Some results are shown in this article. Proposed algorithm is undemanding to resources (time, memory) and therefore is suitable for real-time monitoring in large dynamic systems, such as computer systems and networks. Quality of decay coefficient adaptation is acceptable as follows from the experimental data.

Keywords

Authors

References